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

def activate_new_spec
  conflicts.delete(name)
  debug(depth) { "Activated #{name} at #{possibility}" }
  activated.set_payload(name, possibility)
  require_nested_dependencies_for(possibility)
end

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

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

def binding_requirement_in_set?(requirement, possible_binding_requirements, possibilities)
  possibilities.any? do |poss|
    possibility_satisfies_requirements?(poss, possible_binding_requirements - [requirement])
  end
end

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

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
  relevant_unused_unwinds = unused_unwind_options.select do |alternative|
    intersecting_requirements =
      last_detail_for_current_unwind.all_requirements &
      alternative.requirements_unwound_to_instead
    next if intersecting_requirements.empty?
    # 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 { |d| d.requirements_unwound_to_instead << current_detail.state_requirement }
  unwind_details.each { |d| d.requirements_unwound_to_instead << current_detail.state_requirement }
  current_detail
end

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

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

def debug(depth = 0, &block)
  resolver_ui.debug(depth, &block)
end

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

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

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

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

def filtered_possibility_set(vertex)
  PossibilitySet.new(vertex.payload.dependencies, vertex.payload.possibilities & possibility.possibilities)
end

def find_state_for(requirement)
  return nil unless requirement
  states.find { |i| requirement == i.requirement }
end

def group_possibilities(possibilities)
  possibility_sets = []
  current_possibility_set = nil
  possibilities.reverse_each do |possibility|
    dependencies = dependencies_for(possibility)
    if current_possibility_set && 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

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

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

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

def locked_requirement_named(requirement_name)
  vertex = base.vertex_named(requirement_name)
  vertex && vertex.payload
end

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

def parent_of(requirement)
  return unless requirement
  return unless index = @parents_of[requirement].last
  return unless parent_state = @states[index]
  parent_state.requirement
end

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

def possibility
  possibilities.last
end

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

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

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

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

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

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

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