class Gem::Resolver::Molinillo::Resolver::Resolution

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 152
def initialize(specification_provider, resolver_ui, requested, base)
  @specification_provider = specification_provider
  @resolver_ui = resolver_ui
  @original_requested = requested
  @base = base
  @states = []
  @iteration_counter = 0
  @parents_of = Hash.new { |h, k| h[k] = [] }
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 167
def resolve
  start_resolution

  while state
    break if !state.requirement && state.requirements.empty?
    indicate_progress
    if state.respond_to?(:pop_possibility_state) # DependencyState
      debug(depth) { "Creating possibility state for #{requirement} (#{possibilities.count} remaining)" }
      state.pop_possibility_state.tap do |s|
        if s
          states.push(s)
          activated.tag(s)
        end
      end
    end
    process_topmost_state
  end

  resolve_activated_specs
ensure
  end_resolution
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 723
def activate_new_spec
  conflicts.delete(name)
  debug(depth) { "Activated #{name} at #{possibility}" }
  activated.set_payload(name, possibility)
  require_nested_dependencies_for(possibility)
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 667
def attempt_to_activate
  debug(depth) { 'Attempting to activate ' + possibility.to_s }
  existing_vertex = activated.vertex_named(name)
  if existing_vertex.payload
    debug(depth) { "Found existing spec (#{existing_vertex.payload})" }
    attempt_to_filter_existing_spec(existing_vertex)
  else
    latest = possibility.latest_version
    possibility.possibilities.select! do |possibility|
      requirement_satisfied_by?(requirement, activated, possibility)
    end
    if possibility.latest_version.nil?
      # ensure there's a possibility for better error messages
      possibility.possibilities << latest if latest
      create_conflict
      unwind_for_conflict
    else
      activate_new_spec
    end
  end
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 691
def attempt_to_filter_existing_spec(vertex)
  filtered_set = filtered_possibility_set(vertex)
  if !filtered_set.possibilities.empty?
    activated.set_payload(name, filtered_set)
    new_requirements = requirements.dup
    push_state_for_requirements(new_requirements, false)
  else
    create_conflict
    debug(depth) { "Unsatisfied by existing spec (#{vertex.payload})" }
    unwind_for_conflict
  end
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 559
def binding_requirement_in_set?(requirement, possible_binding_requirements, possibilities)
  possibilities.any? do |poss|
    possibility_satisfies_requirements?(poss, possible_binding_requirements - [requirement])
  end
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 516
def binding_requirements_for_conflict(conflict)
  return [conflict.requirement] if conflict.possibility.nil?

  possible_binding_requirements = conflict.requirements.values.flatten(1).uniq

  # When there's a `CircularDependency` error the conflicting requirement
  # (the one causing the circular) won't be `conflict.requirement`
  # (which won't be for the right state, because we won't have created it,
  # because it's circular).
  # We need to make sure we have that requirement in the conflict's list,
  # otherwise we won't be able to unwind properly, so we just return all
  # the requirements for the conflict.
  return possible_binding_requirements if conflict.underlying_error

  possibilities = search_for(conflict.requirement)

  # If all the requirements together don't filter out all possibilities,
  # then the only two requirements we need to consider are the initial one
  # (where the dependency's version was first chosen) and the last
  if binding_requirement_in_set?(nil, possible_binding_requirements, possibilities)
    return [conflict.requirement, requirement_for_existing_name(name_for(conflict.requirement))].compact
  end

  # Loop through the possible binding requirements, removing each one
  # that doesn't bind. Use a `reverse_each` as we want the earliest set of
  # binding requirements, and don't use `reject!` as we wish to refine the
  # array *on each iteration*.
  binding_requirements = possible_binding_requirements.dup
  possible_binding_requirements.reverse_each do |req|
    next if req == conflict.requirement
    unless binding_requirement_in_set?(req, binding_requirements, possibilities)
      binding_requirements -= [req]
    end
  end

  binding_requirements
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 321
def build_details_for_unwind
  # Get the possible unwinds for the current conflict
  current_conflict = conflicts[name]
  binding_requirements = binding_requirements_for_conflict(current_conflict)
  unwind_details = unwind_options_for_requirements(binding_requirements)

  last_detail_for_current_unwind = unwind_details.sort.last
  current_detail = last_detail_for_current_unwind

  # Look for past conflicts that could be unwound to affect the
  # requirement tree for the current conflict
  all_reqs = last_detail_for_current_unwind.all_requirements
  all_reqs_size = all_reqs.size
  relevant_unused_unwinds = unused_unwind_options.select do |alternative|
    diff_reqs = all_reqs - alternative.requirements_unwound_to_instead
    next if diff_reqs.size == all_reqs_size
    # Find the highest index unwind whilst looping through
    current_detail = alternative if alternative > current_detail
    alternative
  end

  # Add the current unwind options to the `unused_unwind_options` array.
  # The "used" option will be filtered out during `unwind_for_conflict`.
  state.unused_unwind_options += unwind_details.reject { |detail| detail.state_index == -1 }

  # Update the requirements_unwound_to_instead on any relevant unused unwinds
  relevant_unused_unwinds.each do |d|
    (d.requirements_unwound_to_instead << current_detail.state_requirement).uniq!
  end
  unwind_details.each do |d|
    (d.requirements_unwound_to_instead << current_detail.state_requirement).uniq!
  end

  current_detail
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 428
def conflict_fixing_possibilities?(state, binding_requirements)
  return false unless state

  state.possibilities.any? do |possibility_set|
    possibility_set.possibilities.any? do |poss|
      possibility_satisfies_requirements?(poss, binding_requirements)
    end
  end
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 595
def create_conflict(underlying_error = nil)
  vertex = activated.vertex_named(name)
  locked_requirement = locked_requirement_named(name)

  requirements = {}
  unless vertex.explicit_requirements.empty?
    requirements[name_for_explicit_dependency_source] = vertex.explicit_requirements
  end
  requirements[name_for_locking_dependency_source] = [locked_requirement] if locked_requirement
  vertex.incoming_edges.each do |edge|
    (requirements[edge.origin.payload.latest_version] ||= []).unshift(edge.requirement)
  end

  activated_by_name = {}
  activated.each { |v| activated_by_name[v.name] = v.payload.latest_version if v.payload }
  conflicts[name] = Conflict.new(
    requirement,
    requirements,
    vertex.payload && vertex.payload.latest_version,
    possibility,
    locked_requirement,
    requirement_trees,
    activated_by_name,
    underlying_error
  )
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 661
def debug(depth = 0, &block)
  resolver_ui.debug(depth, &block)
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 231
def end_resolution
  resolver_ui.after_resolution
  debug do
    "Finished resolution (#{@iteration_counter} steps) " \
    "(Took #{(ended_at = Time.now) - @started_at} seconds) (#{ended_at})"
  end
  debug { 'Unactivated: ' + Hash[activated.vertices.reject { |_n, v| v.payload }].keys.join(', ') } if state
  debug { 'Activated: ' + Hash[activated.vertices.select { |_n, v| v.payload }].keys.join(', ') } if state
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 443
def filter_possibilities_after_unwind(unwind_details)
  return unless state && !state.possibilities.empty?

  if unwind_details.unwinding_to_primary_requirement?
    filter_possibilities_for_primary_unwind(unwind_details)
  else
    filter_possibilities_for_parent_unwind(unwind_details)
  end
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 490
def filter_possibilities_for_parent_unwind(unwind_details)
  unwinds_to_state = unused_unwind_options.select { |uw| uw.state_index == unwind_details.state_index }
  unwinds_to_state << unwind_details

  primary_unwinds = unwinds_to_state.select(&:unwinding_to_primary_requirement?).uniq
  parent_unwinds = unwinds_to_state.uniq - primary_unwinds

  allowed_possibility_sets = primary_unwinds.flat_map do |unwind|
    states[unwind.state_index].possibilities.select do |possibility_set|
      possibility_set.possibilities.any? do |poss|
        possibility_satisfies_requirements?(poss, unwind.conflicting_requirements)
      end
    end
  end

  requirements_to_avoid = parent_unwinds.flat_map(&:sub_dependencies_to_avoid)

  state.possibilities.reject! do |possibility_set|
    !allowed_possibility_sets.include?(possibility_set) &&
      (requirements_to_avoid - possibility_set.dependencies).empty?
  end
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 457
def filter_possibilities_for_primary_unwind(unwind_details)
  unwinds_to_state = unused_unwind_options.select { |uw| uw.state_index == unwind_details.state_index }
  unwinds_to_state << unwind_details
  unwind_requirement_sets = unwinds_to_state.map(&:conflicting_requirements)

  state.possibilities.reject! do |possibility_set|
    possibility_set.possibilities.none? do |poss|
      unwind_requirement_sets.any? do |requirements|
        possibility_satisfies_requirements?(poss, requirements)
      end
    end
  end
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 708
def filtered_possibility_set(vertex)
  PossibilitySet.new(vertex.payload.dependencies, vertex.payload.possibilities & possibility.possibilities)
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 587
def find_state_for(requirement)
  return nil unless requirement
  states.find { |i| requirement == i.requirement }
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 804
def group_possibilities(possibilities)
  possibility_sets = []
  current_possibility_set = nil

  possibilities.reverse_each do |possibility|
    dependencies = dependencies_for(possibility)
    if current_possibility_set && dependencies_equal?(current_possibility_set.dependencies, dependencies)
      current_possibility_set.possibilities.unshift(possibility)
    else
      possibility_sets.unshift(PossibilitySet.new(dependencies, [possibility]))
      current_possibility_set = possibility_sets.first
    end
  end

  possibility_sets
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 829
def handle_missing_or_push_dependency_state(state)
  if state.requirement && state.possibilities.empty? && allow_missing?(state.requirement)
    state.activated.detach_vertex_named(state.name)
    push_state_for_requirements(state.requirements.dup, false, state.activated)
  else
    states.push(state).tap { activated.tag(state) }
  end
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 643
def indicate_progress
  @iteration_counter += 1
  @progress_rate ||= resolver_ui.progress_rate
  if iteration_rate.nil?
    if Time.now - started_at >= @progress_rate
      self.iteration_rate = @iteration_counter
    end
  end

  if iteration_rate && (@iteration_counter % iteration_rate) == 0
    resolver_ui.indicate_progress
  end
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 715
def locked_requirement_named(requirement_name)
  vertex = base.vertex_named(requirement_name)
  vertex && vertex.payload
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 785
def locked_requirement_possibility_set(requirement, activated = self.activated)
  all_possibilities = search_for(requirement)
  locked_requirement = locked_requirement_named(name_for(requirement))

  # Longwinded way to build a possibilities array with either the locked
  # requirement or nothing in it. Required, since the API for
  # locked_requirement isn't guaranteed.
  locked_possibilities = all_possibilities.select do |possibility|
    requirement_satisfied_by?(locked_requirement, activated, possibility)
  end

  group_possibilities(locked_possibilities)
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 568
def parent_of(requirement)
  return unless requirement
  return unless index = @parents_of[requirement].last
  return unless parent_state = @states[index]
  parent_state.requirement
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 773
def possibilities_for_requirement(requirement, activated = self.activated)
  return [] unless requirement
  if locked_requirement_named(name_for(requirement))
    return locked_requirement_possibility_set(requirement, activated)
  end

  group_possibilities(search_for(requirement))
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 266
def possibility
  possibilities.last
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 475
def possibility_satisfies_requirements?(possibility, requirements)
  name = name_for(possibility)

  activated.tag(:swap)
  activated.set_payload(name, possibility) if activated.vertex_named(name)
  satisfied = requirements.all? { |r| requirement_satisfied_by?(r, activated, possibility) }
  activated.rewind_to(:swap)

  satisfied
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 252
def process_topmost_state
  if possibility
    attempt_to_activate
  else
    create_conflict
    unwind_for_conflict
  end
rescue CircularDependencyError => underlying_error
  create_conflict(underlying_error)
  unwind_for_conflict
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 279
def push_initial_state
  graph = DependencyGraph.new.tap do |dg|
    original_requested.each do |requested|
      vertex = dg.add_vertex(name_for(requested), nil, true)
      vertex.explicit_requirements << requested
    end
    dg.tag(:initial_state)
  end

  push_state_for_requirements(original_requested, true, graph)
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 753
def push_state_for_requirements(new_requirements, requires_sort = true, new_activated = activated)
  new_requirements = sort_dependencies(new_requirements.uniq, new_activated, conflicts) if requires_sort
  new_requirement = nil
  loop do
    new_requirement = new_requirements.shift
    break if new_requirement.nil? || states.none? { |s| s.requirement == new_requirement }
  end
  new_name = new_requirement ? name_for(new_requirement) : ''.freeze
  possibilities = possibilities_for_requirement(new_requirement)
  handle_missing_or_push_dependency_state DependencyState.new(
    new_name, new_requirements, new_activated,
    new_requirement, possibilities, depth, conflicts.dup, unused_unwind_options.dup
  )
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 313
def raise_error_unless_state(conflicts)
  return if state

  error = conflicts.values.map(&:underlying_error).compact.first
  raise error || VersionConflict.new(conflicts, specification_provider)
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 734
def require_nested_dependencies_for(possibility_set)
  nested_dependencies = dependencies_for(possibility_set.latest_version)
  debug(depth) { "Requiring nested dependencies (#{nested_dependencies.join(', ')})" }
  nested_dependencies.each do |d|
    activated.add_child_vertex(name_for(d), nil, [name_for(possibility_set.latest_version)], d)
    parent_index = states.size - 1
    parents = @parents_of[d]
    parents << parent_index if parents.empty?
  end

  push_state_for_requirements(requirements + nested_dependencies, !nested_dependencies.empty?)
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 578
def requirement_for_existing_name(name)
  return nil unless vertex = activated.vertex_named(name)
  return nil unless vertex.payload
  states.find { |s| s.name == name }.requirement
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 632
def requirement_tree_for(requirement)
  tree = []
  while requirement
    tree.unshift(requirement)
    requirement = parent_of(requirement)
  end
  tree
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 624
def requirement_trees
  vertex = activated.vertex_named(name)
  vertex.requirements.map { |r| requirement_tree_for(r) }
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 216
def resolve_activated_specs
  activated.vertices.each do |_, vertex|
    next unless vertex.payload

    latest_version = vertex.payload.possibilities.reverse_each.find do |possibility|
      vertex.requirements.all? { |req| requirement_satisfied_by?(req, activated, possibility) }
    end

    activated.set_payload(vertex.name, latest_version)
  end
  activated.freeze
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 207
def start_resolution
  @started_at = Time.now

  push_initial_state

  debug { "Starting resolution (#{@started_at})\nUser-requested dependencies: #{original_requested}" }
  resolver_ui.before_resolution
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 272
def state
  states.last
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 293
def unwind_for_conflict
  details_for_unwind = build_details_for_unwind
  unwind_options = unused_unwind_options
  debug(depth) { "Unwinding for conflict: #{requirement} to #{details_for_unwind.state_index / 2}" }
  conflicts.tap do |c|
    sliced_states = states.slice!((details_for_unwind.state_index + 1)..-1)
    raise_error_unless_state(c)
    activated.rewind_to(sliced_states.first || :initial_state) if sliced_states
    state.conflicts = c
    state.unused_unwind_options = unwind_options
    filter_possibilities_after_unwind(details_for_unwind)
    index = states.size - 1
    @parents_of.each { |_, a| a.reject! { |i| i >= index } }
    state.unused_unwind_options.reject! { |uw| uw.state_index >= index }
  end
end

# File rubygems/resolver/molinillo/lib/molinillo/resolution.rb, line 360
def unwind_options_for_requirements(binding_requirements)
  unwind_details = []

  trees = []
  binding_requirements.reverse_each do |r|
    partial_tree = [r]
    trees << partial_tree
    unwind_details << UnwindDetails.new(-1, nil, partial_tree, binding_requirements, trees, [])

    # If this requirement has alternative possibilities, check if any would
    # satisfy the other requirements that created this conflict
    requirement_state = find_state_for(r)
    if conflict_fixing_possibilities?(requirement_state, binding_requirements)
      unwind_details << UnwindDetails.new(
        states.index(requirement_state),
        r,
        partial_tree,
        binding_requirements,
        trees,
        []
      )
    end

    # Next, look at the parent of this requirement, and check if the requirement
    # could have been avoided if an alternative PossibilitySet had been chosen
    parent_r = parent_of(r)
    next if parent_r.nil?
    partial_tree.unshift(parent_r)
    requirement_state = find_state_for(parent_r)
    if requirement_state.possibilities.any? { |set| !set.dependencies.include?(r) }
      unwind_details << UnwindDetails.new(
        states.index(requirement_state),
        parent_r,
        partial_tree,
        binding_requirements,
        trees,
        []
      )
    end

    # Finally, look at the grandparent and up of this requirement, looking
    # for any possibilities that wouldn't create their parent requirement
    grandparent_r = parent_of(parent_r)
    until grandparent_r.nil?
      partial_tree.unshift(grandparent_r)
      requirement_state = find_state_for(grandparent_r)
      if requirement_state.possibilities.any? { |set| !set.dependencies.include?(parent_r) }
        unwind_details << UnwindDetails.new(
          states.index(requirement_state),
          grandparent_r,
          partial_tree,
          binding_requirements,
          trees,
          []
        )
      end
      parent_r = grandparent_r
      grandparent_r = parent_of(parent_r)
    end
  end

  unwind_details
end