(*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 *)

open Reason
open Flow_ast_visitor
open Loc_collections
open Name_def
open Dependency_sigs
module EnvMap = Env_api.EnvMap
module EnvSet = Env_api.EnvSet

module EnvMapToEnvSet = struct
  type key = Env_api.EnvKey.t

  type value = EnvSet.t

  type t = ALoc.t Nel.t EnvMap.t EnvMap.t

  let find key map = EnvMap.find key map |> EnvMap.keys |> EnvSet.of_list
end

module Tarjan =
  Tarjan.Make
    (struct
      include Env_api.EnvKey

      let to_string (_, l) = ALoc.debug_to_string l
    end)
    (EnvSet)
    (EnvMapToEnvSet)

type 'k blame = {
  payload: 'k;
  reason: ALoc.t virtual_reason;
  annot_locs: ALoc.t Env_api.annot_loc list;
  recursion: ALoc.t list;
}

type element =
  | Normal of Env_api.EnvKey.t
  | Resolvable of Env_api.EnvKey.t
  | Illegal of Env_api.EnvKey.t blame

type result =
  | Singleton of element
  | ResolvableSCC of element Nel.t
  | IllegalSCC of (element blame * bool) Nel.t

let string_of_element graph =
  let print_elt k =
    match EnvMap.find_opt k graph with
    | None -> "MISSING DEFINITION"
    | Some (def, _, _, _) -> Print.string_of_source def
  in
  function
  | Normal (k, l) ->
    Utils_js.spf
      "[%s (%s): %s]"
      (ALoc.debug_to_string l)
      (Env_api.show_def_loc_type k)
      (print_elt (k, l))
  | Resolvable (k, l) ->
    Utils_js.spf
      "[recursive %s (%s): %s]"
      (ALoc.debug_to_string l)
      (Env_api.show_def_loc_type k)
      (print_elt (k, l))
  | Illegal { payload = (k, l); _ } ->
    Utils_js.spf
      "[illegal %s (%s): %s]"
      (ALoc.debug_to_string l)
      (Env_api.show_def_loc_type k)
      (print_elt (k, l))

let string_of_component graph = function
  | Singleton elt -> string_of_element graph elt
  | ResolvableSCC elts ->
    Utils_js.spf
      "{(recursive cycle)\n%s\n}"
      (Nel.to_list elts |> Base.List.map ~f:(string_of_element graph) |> String.concat ",\n")
  | IllegalSCC elts ->
    Utils_js.spf
      "{(illegal cycle)\n%s\n}"
      (Nel.to_list elts
      |> Base.List.map ~f:(fun ({ payload = elt; _ }, _) -> string_of_element graph elt)
      |> String.concat ",\n"
      )

class toplevel_expression_collector =
  object (this)
    inherit [(ALoc.t, ALoc.t) Ast.Expression.t list, ALoc.t] Flow_ast_visitor.visitor ~init:[]

    method! expression expr =
      this#update_acc (fun acc -> expr :: acc);
      expr

    method! class_ _ x = x

    method! record_declaration _ x = x

    method! function_declaration _ x = x

    method! function_expression _ x = x

    method! arrow_function _ x = x
  end

module type S = sig
  type cx

  val build_graph :
    cx ->
    autocomplete_hooks:Env_api.With_ALoc.autocomplete_hooks ->
    Env_api.env_info ->
    (Name_def.def * 'a * ALoc.t list * ALoc.t Reason.virtual_reason) EnvMap.t ->
    ALoc.t Nel.t EnvMap.t EnvMap.t

  val build_ordering :
    cx ->
    autocomplete_hooks:Env_api.With_ALoc.autocomplete_hooks ->
    Env_api.env_info ->
    (Name_def.def * 'a * ALoc.t list * ALoc.t Reason.virtual_reason) EnvMap.t ->
    result Base.List.t
end

module Make (Context : C) (FlowAPIUtils : F with type cx = Context.t) : S with type cx = Context.t =
struct
  type cx = Context.t

  module FindDependencies : sig
    val depends :
      Context.t ->
      autocomplete_hooks:Env_api.With_ALoc.autocomplete_hooks ->
      EnvMap.key EnvMap.t ->
      Env_api.env_info ->
      Env_api.def_loc_type ->
      ALoc.t ->
      Name_def.def ->
      ALoc.t Nel.t EnvMap.t

    val recursively_resolvable : Name_def.def -> bool
  end = struct
    (* This analysis consumes variable defs and returns a map representing the variables that need to be
       resolved before we can resolve this def.

       Consider for example the program

         1: var x = 42;
         2: type T = typeof x;

       And let's specifically look at the def `TypeAlias(type T = typeof x)`, which will be one of the
       defs generated by the analysis in `name_def.ml`. Given this def, the question that this module
       answers is what variable definitions need to be resolved before the `TypeAlias` def itself can be resolved.

       We can see that the type alias depends on reading `x`, so in order to actually resolve the type alias, we
       first need to know the type of `x`. In order to do that, we need to have resolved the writes that (according
       to the name_resolver) reach this reference to `x`. That's what this analysis tells us--it will traverse the
       TypeAlias def, find the read of `x`, and add the writes to `x` that reach that read to the set of defs that need to
       be resolved before the type alias can be resolved. We'll ultimately use this to figure out the correct ordering
       of nodes.

       The actual output of this analysis is a map, whose keys are the locations of variables whose defs need to be resolved
       before this def can be. The values of this map are the locations within the def itself that led us to those variable definitions--
       in this case, the result will be [def of `x`] => [dereference of `x`]. This information is included for good error messages eventually,
       but the more important bit for the correctness of the analysis is the keys of the map--it may be easier to think of the map
       as a set and ignore the values.
    *)

    (* Helper class for the dependency analysis--traverse the AST nodes
       in a def to determine which variables appear *)
    class use_visitor
      cx
      ~named_only_for_synthesis
      this_super_dep_loc_map
      ({ Env_api.env_values; env_entries; providers; _ } as env)
      init =
      object (this)
        inherit [ALoc.t Nel.t EnvMap.t, ALoc.t] Flow_ast_visitor.visitor ~init as super

        val mutable seen : ALocSet.t = ALocSet.empty

        method add ~why t =
          if Env_api.has_assigning_write t env_entries then
            this#update_acc (fun uses ->
                EnvMap.update
                  t
                  (function
                    | None -> Some (Nel.one why)
                    | Some locs ->
                      Some
                        ( if Nel.mem ~equal:ALoc.equal why locs then
                          locs
                        else
                          Nel.cons why locs
                        ))
                  uses
            )

        method add_write_locs ~for_type write_locs =
          let writes =
            write_locs
            |> Base.List.concat_map ~f:(Env_api.writes_of_write_loc ~for_type providers)
            |> Base.List.map ~f:(fun kind_and_loc ->
                   EnvMap.find_opt kind_and_loc this_super_dep_loc_map
                   |> Base.Option.value ~default:kind_and_loc
               )
          in
          let refinements =
            Base.List.concat_map ~f:(Env_api.refinements_of_write_loc env) write_locs
          in
          let rec writes_of_refinement refi =
            let open Env_api.Refi in
            match refi with
            | InstanceOfR { expr; context = _ } -> ignore (this#expression expr)
            | LatentR { func; targs; arguments; index = _ } ->
              ignore @@ this#expression func;
              run_opt this#call_type_args targs;
              ignore @@ this#arg_list arguments
            | LatentThisR { func; targs; arguments } ->
              ignore @@ this#expression func;
              run_opt this#call_type_args targs;
              ignore @@ this#arg_list arguments
            | SentinelR { prop = _; other_loc } ->
              this#add ~why:other_loc (Env_api.ExpressionLoc, other_loc)
            | EqR loc -> this#add ~why:loc (Env_api.ExpressionLoc, loc)
            | AndR (l, r)
            | OrR (l, r) ->
              writes_of_refinement l;
              writes_of_refinement r
            | NotR r -> writes_of_refinement r
            | TruthyR
            | NullR
            | UndefinedR
            | MaybeR
            | IsArrayR
            | ArrLenR _
            | BoolR _
            | FunctionR
            | NumberR _
            | BigIntR _
            | ObjectR
            | StringR _
            | SymbolR _
            | SingletonBoolR _
            | SingletonStrR _
            | SingletonNumR _
            | SingletonBigIntR _
            | PropExistsR _
            | PropNullishR _
            | PropIsExactlyNullR _
            | PropNonVoidR _
            | PropTruthyR _
            | ImpossibleR ->
              ()
          in
          Base.List.iter ~f:writes_of_refinement refinements;
          writes

        method find_writes ~for_type ?(allow_missing = false) loc =
          let write_locs =
            try Env_api.write_locs_of_read_loc env_values loc with
            | Not_found ->
              if not allow_missing then
                FlowAPIUtils.add_output cx Error_message.(EInternal (loc, MissingEnvRead loc));
              []
          in
          this#add_write_locs ~for_type write_locs

        (* In order to resolve a def containing a variable read, the writes that the
           Name_resolver determines reach the variable must be resolved *)
        method! identifier ((loc, _) as id) =
          let writes = this#find_writes ~for_type:false loc in
          Base.List.iter ~f:(this#add ~why:loc) writes;
          id

        method! type_identifier_reference ((loc, _) as id) =
          let writes = this#find_writes ~for_type:true loc in
          Base.List.iter ~f:(this#add ~why:loc) writes;
          id

        (* In order to resolve a def containing a variable read, the writes that the
           Name_resolver determines reach the variable must be resolved *)
        method! yield loc yield =
          let writes = this#find_writes ~for_type:false loc in
          Base.List.iter ~f:(this#add ~why:loc) writes;
          super#yield loc yield

        method! match_ _ ~on_case_body x =
          let { Ast.Match.arg; cases; match_keyword_loc; comments = _ } = x in
          ignore @@ this#expression arg;
          ignore
          @@ this#pattern_identifier
               ~kind:Ast.Variable.Const
               (Flow_ast_utils.match_root_ident match_keyword_loc);
          Base.List.iter cases ~f:(fun (case_loc, case) ->
              let { Ast.Match.Case.case_match_root_loc; _ } = case in
              ignore @@ this#identifier (Flow_ast_utils.match_root_ident case_match_root_loc);
              ignore @@ super#match_case ~on_case_body (case_loc, case)
          );
          ignore @@ this#identifier (Flow_ast_utils.match_root_ident match_keyword_loc);
          x

        (* In order to resolve a def containing a variable write, the
           write itself should first be resolved *)
        method! pattern_identifier ?kind:_ ((loc, _) as id) =
          ( if Provider_api.is_provider providers loc then
            (* If this is a provider, then we still need to have *all* providers,
               for this location added, because type-at-pos will show their union. We
               won't call this method directly when resolving an assignment--only when
               resolving a larger name_def (e.g. an unsynthesizable function) that
               includes an assignment expression. *)
            let { Provider_api.providers = provider_entries; _ } =
              Base.Option.value_exn (Provider_api.providers_of_def providers loc)
            in
            Base.List.iter
              ~f:(fun { Provider_api.reason = r; _ } ->
                let key = (Env_api.OrdinaryNameLoc, Reason.loc_of_reason r) in
                this#add ~why:loc key)
              provider_entries
          );
          (* Ignore cases that don't have bindings in the environment, like `var x;`
             and illegal or unreachable writes. *)
          this#add ~why:loc (Env_api.OrdinaryNameLoc, loc);
          id

        method! binding_type_identifier ((loc, _) as id) =
          this#add ~why:loc (Env_api.OrdinaryNameLoc, loc);
          id

        method! this_expression loc this_ =
          let writes = this#find_writes ~for_type:false loc in
          Base.List.iter ~f:(this#add ~why:loc) writes;
          this_

        method! super_expression loc this_ =
          let writes = this#find_writes ~for_type:false loc in
          Base.List.iter ~f:(this#add ~why:loc) writes;
          this_

        method! jsx_element_name_identifier (ident : (ALoc.t, ALoc.t) Ast.JSX.Identifier.t) =
          let (loc, _) = ident in
          let writes = this#find_writes ~for_type:false loc in
          Base.List.iter ~f:(this#add ~why:loc) writes;
          super#jsx_identifier ident

        method private jsx_function_call loc =
          match (Context.react_runtime cx, Context.jsx cx) with
          | (Options.ReactRuntimeClassic, Options.Jsx_react) ->
            let writes = this#find_writes ~for_type:false loc in
            Base.List.iter ~f:(this#add ~why:loc) writes
          | (_, Options.Jsx_pragma (_, (_, Ast.Expression.Identifier _))) ->
            let writes = this#find_writes ~for_type:false loc in
            Base.List.iter ~f:(this#add ~why:loc) writes
          | (Options.ReactRuntimeClassic, Options.Jsx_pragma (_, ast)) ->
            ignore @@ this#expression ast
          | _ -> ()

        method! jsx_element loc expr =
          let open Ast.JSX in
          let { opening_element; closing_element; _ } = expr in
          let loc =
            match closing_element with
            | None -> fst opening_element
            | _ -> loc
          in
          this#jsx_function_call loc;
          super#jsx_element loc expr

        method! jsx_fragment loc expr =
          this#jsx_function_call loc;
          super#jsx_fragment loc expr

        method component_ref_param_maybe param =
          let (_, { Ast.Statement.ComponentDeclaration.Param.name; _ }) = param in
          begin
            match (name, Context.react_runtime cx, Context.jsx cx) with
            | ( ( Ast.Statement.ComponentDeclaration.Param.Identifier
                    (loc, { Ast.Identifier.name = "ref"; _ })
                | Ast.Statement.ComponentDeclaration.Param.StringLiteral
                    (loc, { Ast.StringLiteral.value = "ref"; _ }) ),
                Options.ReactRuntimeClassic,
                Options.Jsx_react
              ) ->
              let writes = this#find_writes ~for_type:false loc in
              Base.List.iter ~f:(this#add ~why:loc) writes
            | _ -> ()
          end

        method! component_param param =
          this#component_ref_param_maybe param;
          super#component_param param

        (* Skip names in function parameter types (e.g. declared functions) *)
        method! function_param_type (fpt : ('loc, 'loc) Ast.Type.Function.Param.t) =
          let open Ast.Type.Function.Param in
          let (_, { annot; _ }) = fpt in
          run this#type_ annot;
          fpt

        method! member_property_identifier (id : (ALoc.t, ALoc.t) Ast.Identifier.t) = id

        method! typeof_member_identifier ident = ident

        method! member_type_identifier (id : (ALoc.t, ALoc.t) Ast.Identifier.t) = id

        method! pattern_object_property_identifier_key ?kind:_ id = id

        method! match_object_pattern_property key = key

        method! enum_member_identifier id = id

        method! object_key_identifier (id : (ALoc.t, ALoc.t) Ast.Identifier.t) = id

        method! remote_identifier ident = ident

        method! component_param_name name = name

        method! export_named_declaration_specifier
            (spec : ('loc, 'loc) Ast.Statement.ExportNamedDeclaration.ExportSpecifier.t) =
          let open Ast.Statement.ExportNamedDeclaration.ExportSpecifier in
          (* Ignore renamed export *)
          let (_, { local; exported = _; from_remote = _; imported_name_def_loc = _ }) = spec in
          run this#identifier local;
          spec

        (* For classes/functions that are known to be fully annotated, we skip property bodies *)
        method function_def ~fully_annotated (expr : ('loc, 'loc) Ast.Function.t) =
          let { Ast.Function.params; body; predicate; return; tparams; _ } = expr in
          run this#function_return_annotation return;
          if fully_annotated then
            this#function_params_annotated params
          else (
            run this#function_body_any body;
            run this#function_params params;
            run_opt this#predicate predicate
          );
          run_opt (this#type_params ~kind:Flow_ast_mapper.FunctionTP) tparams

        method component_def (expr : ('loc, 'loc) Ast.Statement.ComponentDeclaration.t) =
          let { Ast.Statement.ComponentDeclaration.params; renders; tparams; _ } = expr in
          run this#component_renders_annotation renders;
          run this#component_params_annotated params;
          run_opt (this#type_params ~kind:Flow_ast_mapper.ComponentDeclarationTP) tparams

        method! declare_component _ (expr : ('loc, 'loc) Ast.Statement.DeclareComponent.t) =
          let { Ast.Statement.DeclareComponent.params; renders; tparams; _ } = expr in
          run this#component_renders_annotation renders;
          run_opt (this#type_params ~kind:Flow_ast_mapper.DeclareComponentTP) tparams;
          run this#component_type_params params;
          expr

        method function_param_pattern_annotated (expr : ('loc, 'loc) Ast.Pattern.t) =
          let open Ast.Pattern in
          let (_, patt) = expr in
          begin
            match patt with
            | Object { Object.properties; annot; comments = _ } ->
              Base.List.iter ~f:this#function_param_pattern_object_p_annotated properties;
              run this#type_annotation_hint annot
            | Array { Array.elements; annot; comments = _ } ->
              Base.List.iter ~f:this#function_param_pattern_array_e_annotated elements;
              run this#type_annotation_hint annot
            | Identifier { Identifier.name; annot; optional = _ } ->
              run this#pattern_identifier name;
              run this#type_annotation_hint annot
            | Expression e -> run this#pattern_expression e
          end;
          expr

        method! function_param param =
          let open Ast.Function.Param in
          let (loc, { argument; default = _ }) = param in
          if (not (Flow_ast_utils.pattern_has_binding argument)) && not (pattern_has_annot argument)
          then
            this#add ~why:loc (Env_api.FunctionParamLoc, loc);
          super#function_param param

        method visit_annotation_in_pattern (expr : ('loc, 'loc) Ast.Pattern.t) =
          let open Ast.Pattern in
          let (_, patt) = expr in
          match patt with
          | Object { Object.properties = _; annot; comments = _ }
          | Array { Array.elements = _; annot; comments = _ }
          | Identifier { Identifier.name = _; annot; optional = _ } ->
            ignore @@ this#type_annotation_hint annot
          | Expression _ -> ()

        method function_param_pattern_object_p_annotated
            (p : ('loc, 'loc) Ast.Pattern.Object.property) =
          let open Ast.Pattern.Object in
          match p with
          | Property prop -> run this#function_param_pattern_object_property_annotated prop
          | RestElement prop -> run this#function_param_pattern_object_rest_property_annotated prop

        method function_param_pattern_object_property_annotated
            (prop : ('loc, 'loc) Ast.Pattern.Object.Property.t) =
          let open Ast.Pattern.Object.Property in
          let (_, { key; pattern; default = _; shorthand = _ }) = prop in
          run this#pattern_object_property_key key;
          run this#function_param_pattern_annotated pattern;
          (* Skip default *)
          prop

        method function_param_pattern_object_rest_property_annotated
            (prop : ('loc, 'loc) Ast.Pattern.RestElement.t) =
          let open Ast.Pattern.RestElement in
          let (_, { argument; comments = _ }) = prop in
          run this#function_param_pattern_annotated argument;
          prop

        method function_param_pattern_array_e_annotated (e : ('loc, 'loc) Ast.Pattern.Array.element)
            =
          let open Ast.Pattern.Array in
          match e with
          | Hole _ -> ()
          | Element elem -> run this#function_param_pattern_array_element_annotated elem
          | RestElement elem -> run this#function_param_pattern_array_rest_element_annotated elem

        method function_param_pattern_array_element_annotated
            (elem : ('loc, 'loc) Ast.Pattern.Array.Element.t) =
          let open Ast.Pattern.Array.Element in
          let (_, { argument; default = _ }) = elem in
          run this#function_param_pattern_annotated argument;
          (* Skip default *)
          elem

        method function_param_pattern_array_rest_element_annotated
            (elem : ('loc, 'loc) Ast.Pattern.RestElement.t) =
          let open Ast.Pattern.RestElement in
          let (_, { argument; comments = _ }) = elem in
          run this#function_param_pattern_annotated argument;
          elem

        method component_params_annotated
            (params : ('loc, 'loc) Ast.Statement.ComponentDeclaration.Params.t) =
          let open Ast.Statement.ComponentDeclaration in
          let (_, { Params.params = params_list; rest; comments = _ }) = params in
          run_list this#component_param_annotated params_list;
          run_opt this#component_rest_param_annotated rest;
          params

        method component_param_annotated
            (param : ('loc, 'loc) Ast.Statement.ComponentDeclaration.Param.t) =
          let open Ast.Statement.ComponentDeclaration.Param in
          let (_, { local; _ }) = param in
          run this#function_param_pattern_annotated local;
          this#component_ref_param_maybe param;
          param

        method component_rest_param_annotated
            (param : ('loc, 'loc) Ast.Statement.ComponentDeclaration.RestParam.t) =
          let open Ast.Statement.ComponentDeclaration.RestParam in
          let (_, { argument; _ }) = param in
          run this#function_param_pattern_annotated argument;
          param

        method function_params_annotated (params : ('loc, 'loc) Ast.Function.Params.t) =
          let open Ast.Function in
          let (_, { Params.params = params_list; rest; comments = _; this_ }) = params in
          run_list this#function_param_annotated params_list;
          run_opt this#function_rest_param_annotated rest;
          run_opt this#function_this_param this_

        method function_param_annotated (param : ('loc, 'loc) Ast.Function.Param.t) =
          let open Ast.Function.Param in
          let (loc, { argument; default = _ }) = param in
          (* Skip default *)
          run this#function_param_pattern_annotated argument;
          if (not (Flow_ast_utils.pattern_has_binding argument)) && not (pattern_has_annot argument)
          then
            this#add ~why:loc (Env_api.FunctionParamLoc, loc);
          param

        method function_rest_param_annotated (expr : ('loc, 'loc) Ast.Function.RestParam.t) =
          let open Ast.Function.RestParam in
          let (_, { argument; comments = _ }) = expr in
          run this#function_param_pattern_annotated argument;
          expr

        method! type_guard guard =
          let open Ast.Type.TypeGuard in
          let (_, { guard = (_x, t); _ }) = guard in
          (* We don't need to include the type guard name here *)
          run_opt this#type_ t;
          guard

        method! function_ loc expr =
          let { Ast.Function.id; params; return; _ } = expr in
          if not named_only_for_synthesis then (
            (match id with
            | Some _ -> ()
            | None -> this#add ~why:loc (Env_api.OrdinaryNameLoc, loc));

            super#function_ loc expr
          ) else (
            (* Even if we skip the body of the function,
               we still need to collect dependencies on the signature of a function. *)
            ignore @@ this#function_return_annotation return;
            let (_, { Ast.Function.Params.params = params_list; rest; comments = _; this_ }) =
              params
            in
            Base.List.iter params_list ~f:(fun (_, { Ast.Function.Param.argument; _ }) ->
                this#visit_annotation_in_pattern argument
            );
            Base.Option.iter rest ~f:(fun (_, { Ast.Function.RestParam.argument; _ }) ->
                this#visit_annotation_in_pattern argument
            );
            Base.Option.iter this_ ~f:(fun (_, { Ast.Function.ThisParam.annot; _ }) ->
                ignore @@ this#type_annotation annot
            );
            expr
          )

        method class_extends_sig
            ((_, { Ast.Class.Extends.expr; targs; comments = _ }) : ('loc, 'loc) Ast.Class.Extends.t)
            : unit =
          run_opt this#type_args targs;
          (* We only visit expressions that is used to generate the class signature. *)
          let rec visit_expr_for_sig ((_, expr') as expr) =
            let open Ast.Expression in
            match expr' with
            | Identifier _ -> ignore @@ this#expression expr
            | Member { Member._object; property = Member.PropertyIdentifier _; comments = _ } ->
              visit_expr_for_sig _object
            | AsExpression { AsExpression.expression = _; annot; comments = _ }
            | TypeCast { TypeCast.expression = _; annot; comments = _ } ->
              ignore @@ this#type_annotation annot
            | _ -> ()
          in
          visit_expr_for_sig expr

        method class_body_annotated (cls_body : ('loc, 'loc) Ast.Class.Body.t) =
          let open Ast.Class.Body in
          let (_, { body; comments = _ }) = cls_body in
          Base.List.iter ~f:this#class_element_annotated body;
          cls_body

        method class_element_annotated (elem : ('loc, 'loc) Ast.Class.Body.element) =
          let open Ast.Class.Body in
          match elem with
          | Method (_, meth) -> this#class_method_annotated meth
          | Property (_, prop) -> this#class_property_annotated prop
          | PrivateField (_, field) -> this#class_private_field_annotated field
          | StaticBlock _ -> ()

        method class_method_annotated (meth : ('loc, 'loc) Ast.Class.Method.t') =
          let open Ast.Class.Method in
          let { kind = _; key; value = (_, value); static = _; decorators; comments = _ } = meth in
          run_list this#class_decorator decorators;
          run this#object_key key;
          this#function_def ~fully_annotated:true value

        method private class_property_value_annotated value =
          let open Ast.Class.Property in
          match value with
          | Initialized
              ((_, Ast.Expression.ArrowFunction function_) | (_, Ast.Expression.Function function_))
            ->
            this#function_def ~fully_annotated:true function_
          | Initialized _
          | Declared
          | Uninitialized ->
            ()

        method class_property_annotated (prop : ('loc, 'loc) Ast.Class.Property.t') =
          let open Ast.Class.Property in
          let { key; value; annot; static = _; variance = _; decorators; comments = _ } = prop in
          run_list this#class_decorator decorators;
          run this#object_key key;
          run this#type_annotation_hint annot;
          match annot with
          | Ast.Type.Missing _ -> this#class_property_value_annotated value
          | Ast.Type.Available _ -> ()

        method class_private_field_annotated (prop : ('loc, 'loc) Ast.Class.PrivateField.t') =
          let open Ast.Class.PrivateField in
          let { key; value; annot; static = _; variance = _; decorators; comments = _ } = prop in
          run_list this#class_decorator decorators;
          run this#private_name key;
          run this#type_annotation_hint annot;
          match annot with
          | Ast.Type.Missing _ -> this#class_property_value_annotated value
          | Ast.Type.Available _ -> ()

        method record_body_annotated (rec_body : ('loc, 'loc) Ast.Statement.RecordDeclaration.Body.t)
            =
          let open Ast.Statement.RecordDeclaration.Body in
          let (_, { body; comments = _ }) = rec_body in
          Base.List.iter ~f:this#record_element_annotated body;
          rec_body

        method record_element_annotated
            (elem : ('loc, 'loc) Ast.Statement.RecordDeclaration.Body.element) =
          let open Ast.Statement.RecordDeclaration.Body in
          match elem with
          | Method (_, meth) -> this#class_method_annotated meth
          | Property prop -> this#record_property_annotated prop
          | StaticProperty prop -> this#record_static_property_annotated prop

        method record_property_annotated
            ((_loc, prop) : ('loc, 'loc) Ast.Statement.RecordDeclaration.Property.t) =
          let open Ast.Statement.RecordDeclaration.Property in
          let { key = _; annot; default_value; comments = _; invalid_syntax = _ } = prop in
          run this#type_annotation annot;
          (* Records always have annotations, but check default_value for functions *)
          Base.Option.iter default_value ~f:(fun value ->
              match value with
              | (_, Ast.Expression.ArrowFunction function_)
              | (_, Ast.Expression.Function function_) ->
                this#function_def ~fully_annotated:true function_
              | _ -> ()
          )

        method record_static_property_annotated
            ((_loc, prop) : ('loc, 'loc) Ast.Statement.RecordDeclaration.StaticProperty.t) =
          let open Ast.Statement.RecordDeclaration.StaticProperty in
          let { key = _; annot; value; comments = _; invalid_syntax = _ } = prop in
          run this#type_annotation annot;
          match value with
          | (_, Ast.Expression.ArrowFunction function_)
          | (_, Ast.Expression.Function function_) ->
            this#function_def ~fully_annotated:true function_
          | _ -> ()

        (* In order to resolve a def containing a read, the writes that the
           Name_resolver determines reach the variable must be resolved *)
        method! expression ((loc, _) as expr) =
          if ALocSet.mem loc seen then
            expr
          else begin
            seen <- ALocSet.add loc seen;
            (* An expression might read an refined value. e.g. if (foo.bar) foo.bar.
               Therefore, we need to record these writes. *)
            let writes = this#find_writes ~for_type:false ~allow_missing:true loc in
            Base.List.iter ~f:(this#add ~why:loc) writes;
            if not named_only_for_synthesis then (
              this#add ~why:loc (Env_api.OrdinaryNameLoc, loc);
              this#add ~why:loc (Env_api.ExpressionLoc, loc);
              this#add ~why:loc (Env_api.ArrayProviderLoc, loc)
            );
            super#expression expr
          end

        method visit_expression_for_expression_writes ((loc, _) as expr) =
          let writes = this#find_writes ~for_type:false ~allow_missing:true loc in
          Base.List.iter ~f:(this#add ~why:loc) writes;
          ignore @@ super#expression expr
      end

    (* For all the possible defs, explore the def's structure with the class above
       to find what variables have to be resolved before this def itself can be resolved *)
    let depends
        cx
        ~autocomplete_hooks
        this_super_dep_loc_map
        ({ Env_api.providers; env_entries; _ } as env)
        kind
        id_loc =
      let depends_of_node ?(named_only_for_synthesis = false) mk_visit state =
        let visitor =
          new use_visitor cx ~named_only_for_synthesis this_super_dep_loc_map env EnvMap.empty
        in
        visitor#set_acc state;
        let node_visit () = mk_visit visitor in
        visitor#eval node_visit ()
      in
      let depends_of_tparams_map tparams_map =
        depends_of_node (fun visitor ->
            ALocMap.iter
              (fun loc _ -> visitor#add ~why:loc (Env_api.OrdinaryNameLoc, loc))
              tparams_map
        )
      in
      (* depends_of_annotation and of_expression take the `state` parameter from
         `depends_of_node` above as an additional currried parameter. *)
      let depends_of_annotation tparams_map anno state =
        state
        |> depends_of_tparams_map tparams_map
        |> depends_of_node (fun visitor -> ignore @@ visitor#type_annotation anno)
      in
      let depends_of_expression
          ?(named_only_for_synthesis = false) ?(for_expression_writes = false) expr =
        depends_of_node ~named_only_for_synthesis (fun visitor ->
            if for_expression_writes then
              visitor#visit_expression_for_expression_writes expr
            else
              ignore @@ visitor#expression expr
        )
      in
      let rec depends_of_hint_node state = function
        | AnnotationHint (tparams_map, anno) -> depends_of_annotation tparams_map anno state
        | ValueHint (_, e) -> depends_of_expression e state
        | ProvidersHint providers ->
          Nel.fold_left
            (fun state loc ->
              depends_of_node
                (fun visitor -> visitor#add ~why:loc (Env_api.OrdinaryNameLoc, loc))
                state)
            state
            providers
        | WriteLocHint (kind, loc) ->
          depends_of_node (fun visitor -> visitor#add ~why:loc (kind, loc)) state
        | StringLiteralType _ -> state
        | ReactFragmentType -> state
        | ReactNodeType -> state
        | AnyErrorHint _ -> state
        | ComposedArrayPatternHint (_, elements) ->
          Base.List.fold elements ~init:state ~f:(fun state -> function
            | ArrayElementPatternHint h
            | ArrayRestElementPatternHint h ->
              depends_of_hint_node state h
          )
        | ComposedObjectPatternHint (_, props) ->
          Base.List.fold props ~init:state ~f:(fun state -> function
            | ObjectPropPatternHint (_, _, h)
            | ObjectSpreadPropPatternHint h ->
              depends_of_hint_node state h
          )
      in
      let rec depends_of_hint state = function
        | Hint.Hint_Placeholder -> state
        | Hint.Hint_t (hint_node, _) -> depends_of_hint_node state hint_node
        | Hint.Hint_Decomp (ops, hint_node, _) ->
          let depends_on_synthesizable_toplevel_expressions acc ~collect =
            let collector = new toplevel_expression_collector in
            collect collector;
            Base.List.fold collector#acc ~init:acc ~f:(fun acc e ->
                if Name_def.expression_is_definitely_synthesizable ~autocomplete_hooks e then
                  depends_of_expression e acc
                else
                  depends_of_expression ~named_only_for_synthesis:true e acc
            )
          in
          Nel.fold_left
            (fun acc (_id, op) ->
              match op with
              | Hint.Decomp_ObjComputed r ->
                let loc = loc_of_reason r in
                depends_of_node
                  (fun visitor -> visitor#add ~why:loc (Env_api.ExpressionLoc, loc))
                  acc
              | Hint.Decomp_SentinelRefinement checks ->
                SMap.fold
                  (fun _ check acc ->
                    match check with
                    | Hint.Member r ->
                      let loc = loc_of_reason r in
                      depends_of_node
                        (fun visitor -> visitor#add ~why:loc (Env_api.ExpressionLoc, loc))
                        acc
                    | _ -> acc)
                  checks
                  acc
              | Hint.Instantiate_Component
                  { Hint.jsx_props_and_children = (jsx_props, jsx_children); _ } ->
                depends_on_synthesizable_toplevel_expressions acc ~collect:(fun collector ->
                    Base.List.iter jsx_props ~f:(fun prop ->
                        ignore @@ collector#jsx_opening_attribute prop
                    );
                    ignore @@ collector#jsx_children jsx_children
                )
              | Hint.Instantiate_Callee
                  { Hint.return_hints; arg_list; arg_index; targs; reason = _ } ->
                let acc =
                  depends_of_node
                    (fun collector ->
                      Base.Option.iter (Lazy.force targs) ~f:(fun targs ->
                          ignore @@ collector#call_type_args targs
                      ))
                    acc
                in
                let rec loop acc i = function
                  | [] -> acc
                  | arg :: rest when i >= arg_index ->
                    let acc =
                      depends_on_synthesizable_toplevel_expressions acc ~collect:(fun collector ->
                          ignore @@ collector#expression_or_spread arg
                      )
                    in
                    loop acc (i + 1) rest
                  | arg :: rest ->
                    let acc =
                      depends_of_node
                        (fun visitor -> ignore @@ visitor#expression_or_spread arg)
                        acc
                    in
                    loop acc (i + 1) rest
                in
                let (_, { Ast.Expression.ArgList.arguments; comments = _ }) = Lazy.force arg_list in
                loop (depends_of_hints acc (Lazy.force return_hints)) 0 arguments
              | _ -> acc)
            (depends_of_hint_node state hint_node)
            ops
      and depends_of_hints state = Base.List.fold ~init:state ~f:depends_of_hint in

      let depends_of_fun synth tparams_map ~hints ~statics function_ state =
        let (fully_annotated, state) =
          match synth with
          | FunctionSynthesizable -> (true, state)
          | _ -> (false, state)
        in
        let state = depends_of_hints state hints in
        let state =
          depends_of_node
            (fun visitor -> visitor#function_def ~fully_annotated function_)
            (depends_of_tparams_map tparams_map state)
        in
        depends_of_node (fun visitor -> SMap.iter (fun _ -> visitor#add ~why:id_loc) statics) state
      in
      let depends_of_component tparams_map component state =
        depends_of_node
          (fun visitor -> visitor#component_def component)
          (depends_of_tparams_map tparams_map state)
      in
      let depends_of_class
          { Ast.Class.id = _; body; tparams; extends; implements; class_decorators; comments = _ } =
        depends_of_node
          (fun visitor ->
            run visitor#class_body_annotated body;
            Base.Option.iter ~f:visitor#class_extends_sig extends;
            run_opt visitor#class_implements implements;
            run_list visitor#class_decorator class_decorators;
            run_opt (visitor#type_params ~kind:Flow_ast_mapper.ClassTP) tparams;
            ())
          EnvMap.empty
      in
      let depends_of_record
          { Ast.Statement.RecordDeclaration.id = _; tparams; implements; body; comments = _ } =
        depends_of_node
          (fun visitor ->
            run visitor#record_body_annotated body;
            run_opt visitor#class_implements implements;
            run_opt (visitor#type_params ~kind:Flow_ast_mapper.RecordTP) tparams;
            ())
          EnvMap.empty
      in
      let depends_of_declared_class
          {
            Ast.Statement.DeclareClass.id = _;
            tparams;
            body;
            extends;
            mixins;
            implements;
            comments = _;
          } =
        depends_of_node
          (fun visitor ->
            run_opt (visitor#type_params ~kind:Flow_ast_mapper.DeclareClassTP) tparams;
            run_loc visitor#object_type body;
            run_loc_opt visitor#generic_type extends;
            Base.List.iter ~f:(run_loc visitor#generic_type) mixins;
            run_opt visitor#class_implements implements;
            ())
          EnvMap.empty
      in
      let depends_of_declared_component loc component =
        depends_of_node
          (fun visitor ->
            let (_ : (_, _) Ast.Statement.DeclareComponent.t) =
              visitor#declare_component loc component
            in
            ())
          EnvMap.empty
      in
      let depends_of_declared_namespace
          { Ast.Statement.DeclareNamespace.id = _; body; comments = _ } =
        depends_of_node
          (fun visitor ->
            run_loc visitor#block body;
            ())
          EnvMap.empty
      in
      let depends_of_alias { Ast.Statement.TypeAlias.tparams; right; _ } =
        depends_of_node
          (fun visitor ->
            run_opt (visitor#type_params ~kind:Flow_ast_mapper.TypeAliasTP) tparams;
            run visitor#type_ right;
            ())
          EnvMap.empty
      in
      let depends_of_opaque
          {
            Ast.Statement.OpaqueType.tparams;
            impl_type;
            lower_bound;
            upper_bound;
            legacy_upper_bound;
            _;
          } =
        depends_of_node
          (fun visitor ->
            run_opt (visitor#type_params ~kind:Flow_ast_mapper.OpaqueTypeTP) tparams;
            run_opt visitor#type_ impl_type;
            run_opt visitor#type_ lower_bound;
            run_opt visitor#type_ upper_bound;
            run_opt visitor#type_ legacy_upper_bound;
            ())
          EnvMap.empty
      in
      let depends_of_tparam tparams_map (_, { Ast.Type.TypeParam.bound; variance; default; _ }) =
        depends_of_node
          (fun visitor ->
            run visitor#type_annotation_hint bound;
            run visitor#variance_opt variance;
            run_opt visitor#type_ default;
            ())
          (depends_of_tparams_map tparams_map EnvMap.empty)
      in
      let depends_of_interface { Ast.Statement.Interface.tparams; extends; body; _ } =
        depends_of_node
          (fun visitor ->
            run_opt (visitor#type_params ~kind:Flow_ast_mapper.InterfaceTP) tparams;
            Base.List.iter ~f:(run_loc visitor#generic_type) extends;
            run_loc visitor#object_type body;
            ())
          EnvMap.empty
      in
      let depends_of_hinted_expression ~for_expression_writes hints expr state =
        let state = depends_of_expression ~for_expression_writes expr state in
        depends_of_hints state hints
      in
      let depends_on_match_pattern case_match_root_loc pattern state =
        depends_of_node
          (fun visitor ->
            run visitor#identifier (Flow_ast_utils.match_root_ident case_match_root_loc);
            run visitor#match_pattern pattern;
            ())
          state
      in
      let depends_of_root state = function
        | Annotation { annot; tparams_map; _ } -> depends_of_annotation tparams_map annot state
        | Value { hints; expr; decl_kind = _; as_const = _ } ->
          let state = depends_of_hints state hints in
          depends_of_expression expr state
        | MatchCaseRoot { case_match_root_loc; root_pattern_loc = _; prev_pattern_locs_rev } ->
          depends_of_node
            (fun visitor ->
              run visitor#identifier (Flow_ast_utils.match_root_ident case_match_root_loc);
              Base.List.iter prev_pattern_locs_rev ~f:(fun loc ->
                  visitor#add ~why:loc (Env_api.MatchCasePatternLoc, loc)
              ))
            state
        | ObjectValue { obj; synthesizable = ObjectSynthesizable _; _ } ->
          let open Ast.Expression.Object in
          let open Ast.Expression.Object.Property in
          let open Ast.Expression.Object.SpreadProperty in
          let rec depends_of_synthesizable_expression state ((exp_loc, exp) as expression) =
            match exp with
            | Ast.Expression.Object obj -> loop state obj
            | Ast.Expression.TypeCast { Ast.Expression.TypeCast.annot; _ }
            | Ast.Expression.AsExpression { Ast.Expression.AsExpression.annot; _ } ->
              depends_of_annotation ALocMap.empty annot state
            | Ast.Expression.Array { Ast.Expression.Array.elements; _ } ->
              Base.List.fold elements ~init:state ~f:(fun state -> function
                | Ast.Expression.Array.Expression exp
                | Ast.Expression.Array.Spread (_, { Ast.Expression.SpreadElement.argument = exp; _ })
                  ->
                  depends_of_synthesizable_expression state exp
                | Ast.Expression.Array.Hole _ -> state
              )
            | Ast.Expression.Function fn
            | Ast.Expression.ArrowFunction fn ->
              depends_of_fun
                FunctionSynthesizable
                ALocMap.empty
                ~hints:[]
                ~statics:SMap.empty
                fn
                state
            | Ast.Expression.Member
                {
                  Ast.Expression.Member._object;
                  property = Ast.Expression.Member.PropertyIdentifier _;
                  _;
                } ->
              let state =
                let visitor =
                  new use_visitor
                    cx
                    ~named_only_for_synthesis:false
                    this_super_dep_loc_map
                    env
                    state
                in
                let writes = visitor#find_writes ~for_type:false ~allow_missing:true exp_loc in
                Base.List.iter ~f:(visitor#add ~why:exp_loc) writes;
                visitor#acc
              in
              depends_of_synthesizable_expression state _object
            | _ -> depends_of_expression expression state
          and loop state { Ast.Expression.Object.properties; _ } =
            Base.List.fold properties ~init:state ~f:(fun state -> function
              | SpreadProperty (_, { argument; _ }) -> depends_of_expression argument state
              | Property (_, Method { key = Identifier _; value = (_, fn); _ }) ->
                depends_of_fun
                  FunctionSynthesizable
                  ALocMap.empty
                  ~hints:[]
                  ~statics:SMap.empty
                  fn
                  state
              | Property (_, Init { key = Identifier _; value; _ }) ->
                depends_of_synthesizable_expression state value
              | _ ->
                raise Env_api.(Env_invariant (Some id_loc, Impossible "Object not synthesizable"))
            )
          in
          loop state obj
        | ObjectValue { obj; obj_loc; _ } ->
          depends_of_expression (obj_loc, Ast.Expression.Object obj) EnvMap.empty
        | FunctionValue
            {
              hints;
              synthesizable_from_annotation;
              function_loc = _;
              function_;
              statics;
              arrow = _;
              tparams_map;
            } ->
          depends_of_fun synthesizable_from_annotation tparams_map ~hints ~statics function_ state
        | EmptyArray { array_providers; _ } ->
          ALocSet.fold
            (fun loc acc ->
              EnvMap.update
                (Env_api.ArrayProviderLoc, loc)
                (function
                  | None -> Some (Nel.one id_loc)
                  | Some locs -> Some (Nel.cons id_loc locs))
                acc)
            array_providers
            state
        | For (_, exp) -> depends_of_expression exp state
        | Contextual { reason = _; hints; optional = _; default_expression } ->
          let state =
            Base.Option.value_map default_expression ~default:state ~f:(fun e ->
                depends_of_expression e state
            )
          in
          depends_of_hints state hints
        | CatchUnannotated -> state
        | UnannotatedParameter _ -> state
      in
      let depends_of_selector state = function
        | Selector.Computed { expression; _ } -> depends_of_expression expression state
        | Selector.Prop { prop_loc; _ } ->
          (* In `const {d: {a, b}} = obj`, each prop might be reading from a refined value, \
             which is a write. We need to track these dependencies as well. *)
          let visitor =
            new use_visitor cx ~named_only_for_synthesis:false this_super_dep_loc_map env state
          in
          let writes = visitor#find_writes ~for_type:false ~allow_missing:true prop_loc in
          Base.List.iter ~f:(visitor#add ~why:prop_loc) writes;
          visitor#acc
        | Selector.Default
        | Selector.Elem _
        | Selector.ObjRest _
        | Selector.ArrRest _ ->
          state
      in
      let depends_of_lhs id_loc lhs_member_expression =
        (* When looking at a binding def, like `x = y`, in order to resolve this def we need
             to have resolved the providers for `x`, as well as the type of `y`, in order to check
             the type of `y` against `x`. So in addition to exploring the RHS, we also add the providers
             for `x` to the set of dependencies. *)
        match lhs_member_expression with
        | Some e -> depends_of_expression ~for_expression_writes:true e EnvMap.empty
        | None ->
          (match Provider_api.providers_of_def providers id_loc with
          | Some { Provider_api.providers = provider_entries; _ } ->
            if not @@ Provider_api.is_provider providers id_loc then
              Base.List.fold
                ~init:EnvMap.empty
                ~f:(fun acc { Provider_api.reason = r; _ } ->
                  let key = (Env_api.OrdinaryNameLoc, Reason.loc_of_reason r) in
                  if Env_api.has_assigning_write key env_entries then
                    EnvMap.update
                      key
                      (function
                        | None -> Some (Nel.one id_loc)
                        | Some locs -> Some (Nel.cons id_loc locs))
                      acc
                  else
                    acc)
                provider_entries
            else
              EnvMap.empty
          | None -> EnvMap.empty)
      in
      let rec depends_of_binding bind =
        let state =
          if kind = Env_api.PatternLoc || kind = Env_api.FunctionParamLoc then
            EnvMap.empty
          else
            depends_of_lhs id_loc None
        in
        match bind with
        | Root root -> depends_of_root state root
        | Hooklike bind -> depends_of_binding bind
        | Select { selector; parent = (parent_loc, _) } ->
          let state = depends_of_selector state selector in
          depends_of_node
            (fun visitor -> visitor#add ~why:parent_loc (Env_api.PatternLoc, parent_loc))
            state
      in
      let depends_of_update lhs =
        let state = depends_of_lhs id_loc lhs in
        match lhs with
        | Some _ -> (* assigning to member *) state
        | None ->
          (* assigning to identifier *)
          let visitor =
            new use_visitor cx ~named_only_for_synthesis:false this_super_dep_loc_map env state
          in
          let writes = visitor#find_writes ~for_type:false id_loc in
          Base.List.iter ~f:(visitor#add ~why:id_loc) writes;
          visitor#acc
      in
      let depends_of_op_assign lhs rhs =
        let lhs =
          let (lhs, _) = Flow_ast_utils.unwrap_nonnull_lhs lhs in
          match lhs with
          | (_, Ast.Pattern.Expression e) -> Some e
          | _ -> None
        in
        (* reusing depends_of_update, since the LHS of an op-assign is handled identically to an update *)
        let state = depends_of_update lhs in
        depends_of_expression rhs state
      in
      let depends_of_member_assign member_loc member rhs =
        let state =
          depends_of_node (fun visitor -> ignore @@ visitor#member member_loc member) EnvMap.empty
        in
        depends_of_expression rhs state
      in
      function
      | Binding binding -> depends_of_binding binding
      | MatchCasePattern { case_match_root_loc; has_guard = _; pattern } ->
        depends_on_match_pattern case_match_root_loc pattern EnvMap.empty
      | ExpressionDef { expr; hints; _ } ->
        depends_of_hinted_expression ~for_expression_writes:true hints expr EnvMap.empty
      | Update _ -> depends_of_update None
      | MemberAssign { member_loc; member; rhs; _ } ->
        depends_of_member_assign member_loc member rhs
      | OpAssign { lhs; rhs; _ } -> depends_of_op_assign lhs rhs
      | Function
          {
            synthesizable_from_annotation;
            arrow = _;
            function_;
            has_this_def = _;
            function_loc = _;
            tparams_map;
            statics;
            hints;
          } ->
        depends_of_fun
          synthesizable_from_annotation
          tparams_map
          ~hints
          ~statics
          function_
          EnvMap.empty
      | Component { tparams_map; component; component_loc = _ } ->
        depends_of_component tparams_map component EnvMap.empty
      | Class { class_; class_loc = _; this_super_write_locs = _; kind = _ } ->
        depends_of_class class_
      | Record { record; record_loc = _; this_super_write_locs = _; defaulted_props = _ } ->
        depends_of_record record
      | DeclaredClass (_, decl) -> depends_of_declared_class decl
      | DeclaredComponent (loc, decl) -> depends_of_declared_component loc decl
      | TypeAlias (_, alias) -> depends_of_alias alias
      | OpaqueType (_, alias) -> depends_of_opaque alias
      | TypeParam { tparams_map; kind = _; tparam } -> depends_of_tparam tparams_map tparam
      | Interface (_, inter) -> depends_of_interface inter
      | GeneratorNext (Some { return_annot; tparams_map; _ }) ->
        depends_of_annotation tparams_map return_annot EnvMap.empty
      | DeclaredNamespace (_, ns) -> depends_of_declared_namespace ns
      | GeneratorNext None -> EnvMap.empty
      | Enum _ ->
        (* Enums don't contain any code or type references, they're literal-like *) EnvMap.empty
      | Import _ -> (* same with all imports *) EnvMap.empty
      | MissingThisAnnot -> EnvMap.empty

    (* Is the variable defined by this def able to be recursively depended on, e.g. created as a 0->1 tvar before being
       resolved? *)
    let recursively_resolvable =
      let rec bind_loop b =
        match b with
        | Root CatchUnannotated -> true
        | Root (UnannotatedParameter _) -> true
        | Root (Annotation _) -> true
        | Root (ObjectValue { synthesizable = ObjectSynthesizable _; _ }) -> true
        | Root
            ( For _ | Value _ | MatchCaseRoot _ | FunctionValue _ | Contextual _ | EmptyArray _
            | ObjectValue _ ) ->
          false
        | Select { selector = Selector.Computed _; _ } -> false
        | Select { parent = (_, binding); _ } -> bind_loop binding
        | Hooklike binding -> bind_loop binding
      in
      let rec expression_resolvable (_, expr) =
        (* A variable read or member expression is assumed to be recursively resolvable if the
           write that reaches the read is also resolvable, and we can extend this to
           ExpressionDef nodes as long as they only contain such expressions. These nodes will
           always depend on the definition of the variable or member, and if the definitions
           are not resolvable, the entire component won't be either. *)
        match expr with
        | Ast.Expression.StringLiteral _
        | Ast.Expression.NumberLiteral _
        | Ast.Expression.BooleanLiteral _
        | Ast.Expression.NullLiteral _
        | Ast.Expression.BigIntLiteral _
        | Ast.Expression.RegExpLiteral _
        | Ast.Expression.ModuleRefLiteral _
        | Ast.Expression.Identifier _ ->
          true
        | Ast.Expression.Member
            {
              Ast.Expression.Member._object;
              property = Ast.Expression.Member.(PropertyIdentifier _);
              _;
            } ->
          expression_resolvable _object
        | _ -> false
      in
      function
      | Binding bind -> bind_loop bind
      | ExpressionDef { hints = []; expr; chain = _; cond_context = _ } ->
        expression_resolvable expr
      | GeneratorNext _
      | TypeAlias _
      | OpaqueType _
      | TypeParam _
      | Interface _
      (* Imports are academic here since they can't be in a cycle anyways, since they depend on nothing *)
      | Import { import_kind = Ast.Statement.ImportDeclaration.(ImportType | ImportTypeof); _ }
      | Import
          {
            import =
              Named { kind = Some Ast.Statement.ImportDeclaration.(ImportType | ImportTypeof); _ };
            _;
          }
      | Class _
      | Record _
      | MissingThisAnnot
      | DeclaredComponent _
      | DeclaredClass _
      | DeclaredNamespace _
      | Function { synthesizable_from_annotation = FunctionSynthesizable; _ }
      | Component _ ->
        true
      | MatchCasePattern _
      | ExpressionDef _
      | Update _
      | MemberAssign _
      | OpAssign _
      | Function _
      | Enum _
      | Import _ ->
        false
  end

  let annotation_locs scopes providers kind loc =
    let rec bind_loop b =
      match b with
      | Root CatchUnannotated
      | Root (UnannotatedParameter _)
      | Root (Annotation _)
      | Root (ObjectValue { synthesizable = ObjectSynthesizable _; _ }) ->
        []
      | Root (FunctionValue { synthesizable_from_annotation = MissingReturn loc; _ }) ->
        [Env_api.Loc loc]
      | Root (ObjectValue { synthesizable = MissingMemberAnnots { locs }; _ }) ->
        let (functions, others) =
          Base.List.fold
            ~f:
              (fun (functions, others) -> function
                | OtherMissingAnnot l -> (functions, l :: others)
                | FuncMissingAnnot l -> (Env_api.Loc l :: functions, others))
            ~init:([], [])
            (Nel.to_list locs)
        in
        if List.length others = 0 then
          functions
        else begin
          try
            let { Provider_api.state; _ } =
              Base.Option.value_exn (Provider_api.providers_of_def providers loc)
            in
            match state with
            | Find_providers.AnnotatedVar { contextual = false; _ } -> functions
            | _ ->
              let { Scope_api.With_ALoc.Def.locs = (loc, _); _ } =
                Scope_api.With_ALoc.def_of_use scopes loc
              in
              Env_api.Object { loc; props = others } :: functions
          with
          | Scope_api.With_ALoc.Missing_def _ -> functions
        end
      | Root
          ( For _ | Value _ | MatchCaseRoot _ | FunctionValue _ | Contextual _ | EmptyArray _
          | ObjectValue _ ) -> begin
        try
          let { Provider_api.state; _ } =
            Base.Option.value_exn (Provider_api.providers_of_def providers loc)
          in
          match state with
          | Find_providers.AnnotatedVar { contextual = false; _ } -> []
          | _ ->
            let { Scope_api.With_ALoc.Def.locs = (loc, _); _ } =
              Scope_api.With_ALoc.def_of_use scopes loc
            in
            [Env_api.Loc loc]
        with
        | Scope_api.With_ALoc.Missing_def _ -> []
      end
      | Hooklike bind -> bind_loop bind
      | Select _ -> []
    in
    function
    | _ when kind = Env_api.PatternLoc -> []
    | Binding bind -> bind_loop bind
    | GeneratorNext None -> [Env_api.Loc loc]
    | Function { synthesizable_from_annotation = MissingReturn loc; _ } -> [Env_api.Loc loc]
    | Component _
    | TypeAlias _
    | OpaqueType _
    | TypeParam _
    | Function _
    | Interface _
    | Enum _
    | Import _
    | Class _
    | Record _
    | DeclaredClass _
    | DeclaredComponent _
    | MatchCasePattern _
    | ExpressionDef _
    | DeclaredNamespace _
    | MissingThisAnnot
    | GeneratorNext (Some _) ->
      []
    (* TODO *)
    | Update _
    | MemberAssign _
    | OpAssign _ ->
      []

  let dependencies cx ~autocomplete_hooks this_super_dep_loc_map env (kind, loc) (def, _, _, _) acc
      =
    let depends =
      FindDependencies.depends cx ~autocomplete_hooks this_super_dep_loc_map env kind loc def
    in
    EnvMap.update
      (kind, loc)
      (function
        | None -> Some depends
        | Some _ ->
          raise
            Env_api.(
              Env_invariant (Some loc, Impossible "Duplicate name defs for the same location")
            ))
      acc

  let build_graph cx ~autocomplete_hooks env map =
    (* This is a forwarding map from the def loc of this and super to the def loc of the functions
       and classes that define this and super. We need this forwarding mechanism, because this and
       super are not write entries that will be resolved by env_resolution. Instead, they are
       indirectly resolved when resolving their defining functions and classes. Therefore, when
       we see a read of `this`/`super`, instead of saying it depends on the write of `this`/`super`,
       we use this forwarding map to say it actually depends on the functions/classes that define
       `this`/`super`. *)
    let this_super_dep_loc_map =
      EnvMap.fold
        (fun kind_and_loc def acc ->
          match def with
          | (Class { this_super_write_locs = locs; _ }, _, _, _)
          | (Record { this_super_write_locs = locs; _ }, _, _, _)
          | ( Binding
                (Root
                  (ObjectValue { synthesizable = ObjectSynthesizable { this_write_locs = locs }; _ })
                  ),
              _,
              _,
              _
            ) ->
            acc
            |> EnvSet.fold
                 (fun this_super_kind_and_loc acc ->
                   EnvMap.add this_super_kind_and_loc kind_and_loc acc)
                 locs
          | _ -> acc)
        map
        EnvMap.empty
    in
    EnvMap.fold (dependencies cx ~autocomplete_hooks this_super_dep_loc_map env) map EnvMap.empty

  let build_ordering cx ~autocomplete_hooks ({ Env_api.scopes; providers; _ } as env) map =
    let env_map_find k map =
      match EnvMap.find_opt k map with
      | Some t -> t
      | None -> raise Env_api.(Env_invariant (None, NameDefGraphMismatch))
    in
    let graph = build_graph cx ~autocomplete_hooks env map in
    let order_graph = EnvMap.map (fun deps -> EnvMap.keys deps |> EnvSet.of_list) graph in
    let roots = EnvMap.keys order_graph |> EnvSet.of_list in
    let sort =
      try Tarjan.topsort ~roots graph |> List.rev with
      | Not_found ->
        let all_locs =
          EnvMap.values order_graph
          |> List.map EnvSet.elements
          |> List.flatten
          |> EnvSet.of_list
          |> EnvSet.elements
        in
        let all = List.map snd all_locs in
        let missing_roots =
          all_locs |> Base.List.filter ~f:(fun l -> not @@ EnvSet.mem l roots) |> List.map snd
        in
        let roots = EnvSet.elements roots |> List.map snd in
        raise Env_api.(Env_invariant (None, NameDefOrderingFailure { all; missing_roots; roots }))
    in
    let result_of_scc (fst, rest) =
      let element_of_loc (kind, loc) =
        let (def, _, _, reason) = env_map_find (kind, loc) map in
        if EnvSet.mem (kind, loc) (env_map_find (kind, loc) order_graph) then
          if FindDependencies.recursively_resolvable def then
            Resolvable (kind, loc)
          else
            let depends = env_map_find (kind, loc) graph in
            let recursion = env_map_find (kind, loc) depends |> Nel.to_list in
            Illegal
              {
                payload = (kind, loc);
                reason;
                recursion;
                annot_locs = annotation_locs scopes providers kind loc def;
              }
        else
          Normal (kind, loc)
      in
      match rest with
      | [] -> Singleton (element_of_loc fst)
      | _ ->
        let component = (fst, rest) in
        if
          Base.List.for_all
            ~f:(fun m ->
              let (def, _, _, _) = env_map_find m map in
              FindDependencies.recursively_resolvable def)
            (fst :: rest)
        then
          ResolvableSCC (Nel.map element_of_loc component)
        else
          let rec shortest_cycle targ seen parents q =
            (* BFS search *)
            match Queue.take_opt q with
            | None -> None
            | Some cur ->
              let adj = env_map_find cur order_graph in
              if EnvSet.mem targ adj then
                let rec path x =
                  match EnvMap.find_opt x parents with
                  | Some y -> x :: path y
                  | None -> [x]
                in
                Some (targ :: path cur)
              else
                let seen = EnvSet.add cur seen in
                let adj = EnvSet.diff adj seen in
                let parents =
                  EnvSet.fold
                    (fun next parents ->
                      Queue.add next q;
                      EnvMap.add next cur parents)
                    adj
                    parents
                in
                shortest_cycle targ seen parents q
          in
          let cycle_elts =
            Base.List.filter_map (Nel.to_list component) ~f:(fun payload ->
                let (def, _, _, _) = EnvMap.find payload map in
                if FindDependencies.recursively_resolvable def then
                  None
                else
                  let q = Queue.create () in
                  Queue.add payload q;
                  shortest_cycle payload EnvSet.empty EnvMap.empty q
            )
            |> Base.List.concat
            |> EnvSet.of_list
          in
          let elements =
            Nel.map
              (fun (kind, loc) ->
                let (def, _, _, reason) = env_map_find (kind, loc) map in
                let depends = env_map_find (kind, loc) graph in
                let edges =
                  EnvMap.fold
                    (fun ((_, kl) as k) v acc ->
                      if (not (ALoc.equal kl loc)) && EnvSet.mem k cycle_elts then
                        let rev_v =
                          Base.List.rev_filter ~f:(fun l -> not (ALoc.equal l loc)) (Nel.to_list v)
                        in
                        Base.List.rev_append rev_v acc
                      else
                        acc)
                    depends
                    []
                in
                let display = EnvSet.mem (kind, loc) cycle_elts in
                ( {
                    payload = element_of_loc (kind, loc);
                    reason;
                    recursion = edges;
                    annot_locs = annotation_locs scopes providers kind loc def;
                  },
                  display
                ))
              component
          in

          IllegalSCC elements
    in
    Base.List.map ~f:result_of_scc sort
end

module DummyFlow (Context : C) = struct
  type cx = Context.t

  let add_output _ _ = ()
end

module Make_Test_With_Cx (Context : C) = Make (Context) (DummyFlow (Context))
