module GraphQL::StaticValidation::DefinitionDependencies

def dependency_map(&block)
  @dependency_map ||= resolve_dependencies(&block)
end

def initialize(*)
  super
  @defdep_node_paths = {}
  # { name => [node, ...] } pairs for fragments (although duplicate-named fragments are _invalid_, they are _possible_)
  @defdep_fragment_definitions = Hash.new{ |h, k| h[k] = [] }
  # This tracks dependencies from fragment to Node where it was used
  # { fragment_definition_name => [dependent_node, dependent_node]}
  @defdep_dependent_definitions = Hash.new { |h, k| h[k] = Set.new }
  # First-level usages of spreads within definitions
  # (When a key has an empty list as its value,
  #  we can resolve that key's dependents)
  # { definition_node => [node, node ...] }
  @defdep_immediate_dependencies = Hash.new { |h, k| h[k] = Set.new }
  # When we encounter a spread,
  # this node is the one who depends on it
  @defdep_current_parent = nil
end

def on_document(node, parent)
  node.definitions.each do |definition|
    if definition.is_a? GraphQL::Language::Nodes::FragmentDefinition
      @defdep_fragment_definitions[definition.name] << definition
    end
  end
  super
  @dependencies = dependency_map { |defn, spreads, frag|
    context.on_dependency_resolve_handlers.each { |h| h.call(defn, spreads, frag) }
  }
end

def on_fragment_definition(node, parent)
  @defdep_node_paths[node] = NodeWithPath.new(node, context.path)
  @defdep_current_parent = node
  super
  @defdep_current_parent = nil
end

def on_fragment_spread(node, parent)
  @defdep_node_paths[node] = NodeWithPath.new(node, context.path)
  # Track both sides of the dependency
  @defdep_dependent_definitions[node.name] << @defdep_current_parent
  @defdep_immediate_dependencies[@defdep_current_parent] << node
  super
end

def on_operation_definition(node, prev_node)
  @defdep_node_paths[node.name] = NodeWithPath.new(node, context.path)
  @defdep_current_parent = node
  super
  @defdep_current_parent = nil
end

def resolve_dependencies
  dependency_map = DependencyMap.new
  # Don't allow the loop to run more times
  # than the number of fragments in the document
  max_loops = 0
  @defdep_fragment_definitions.each_value do |v|
    max_loops += v.size
  end
  loops = 0
  # Instead of tracking independent fragments _as you visit_,
  # determine them at the end. This way, we can treat fragments with the
  # same name as if they were the same name. If _any_ of the fragments
  # with that name has a dependency, we record it.
  independent_fragment_nodes = @defdep_fragment_definitions.values.flatten - @defdep_immediate_dependencies.keys
  visited_fragment_names = Set.new
  while fragment_node = independent_fragment_nodes.pop
    if visited_fragment_names.add?(fragment_node.name)
      # this is a new fragment name
    else
      # this is a duplicate fragment name
      next
    end
    loops += 1
    if loops > max_loops
      raise("Resolution loops exceeded the number of definitions; infinite loop detected. (Max: #{max_loops}, Current: #{loops})")
    end
    # Since it's independent, let's remove it from here.
    # That way, we can use the remainder to identify cycles
    @defdep_immediate_dependencies.delete(fragment_node)
    fragment_usages = @defdep_dependent_definitions[fragment_node.name]
    if fragment_usages.empty?
      # If we didn't record any usages during the visit,
      # then this fragment is unused.
      dependency_map.unused_dependencies << @defdep_node_paths[fragment_node]
    else
      fragment_usages.each do |definition_node|
        # Register the dependency AND second-order dependencies
        dependency_map[definition_node] << fragment_node
        dependency_map[definition_node].concat(dependency_map[fragment_node])
        # Since we've registered it, remove it from our to-do list
        deps = @defdep_immediate_dependencies[definition_node]
        # Can't find a way to _just_ delete from `deps` and return the deleted entries
        removed, remaining = deps.partition { |spread| spread.name == fragment_node.name }
        @defdep_immediate_dependencies[definition_node] = remaining
        if block_given?
          yield(definition_node, removed, fragment_node)
        end
        if remaining.empty? &&
          definition_node.is_a?(GraphQL::Language::Nodes::FragmentDefinition) &&
          definition_node.name != fragment_node.name
          # If all of this definition's dependencies have
          # been resolved, we can now resolve its
          # own dependents.
          #
          # But, it's possible to have a duplicate-named fragment here.
          # Skip it in that case
          independent_fragment_nodes << definition_node
        end
      end
    end
  end
  # If any dependencies were _unmet_
  # (eg, spreads with no corresponding definition)
  # then they're still in there
  @defdep_immediate_dependencies.each do |defn_node, deps|
    deps.each do |spread|
      if !@defdep_fragment_definitions.key?(spread.name)
        dependency_map.unmet_dependencies[@defdep_node_paths[defn_node]] << @defdep_node_paths[spread]
        deps.delete(spread)
      end
    end
    if deps.empty?
      @defdep_immediate_dependencies.delete(defn_node)
    end
  end
  # Anything left in @immediate_dependencies is cyclical
  cyclical_nodes = @defdep_immediate_dependencies.keys.map { |n| @defdep_node_paths[n] }
  # @immediate_dependencies also includes operation names, but we don't care about
  # those. They became nil when we looked them up on `@fragment_definitions`, so remove them.
  cyclical_nodes.compact!
  dependency_map.cyclical_definitions.concat(cyclical_nodes)
  dependency_map
end