class Bundler::Molinillo::Resolver::Resolution

A specific resolution from a given {Resolver}

Constants

Conflict

A conflict that the resolution process encountered @attr [Object] requirement the requirement that immediately led to the conflict @attr [{String,Nil=>}] requirements the requirements that caused the conflict @attr [Object, nil] existing the existing spec that was in conflict with

the {#possibility}

@attr [Object] possibility_set the set of specs that was unable to be

activated due to a conflict.

@attr [Object] locked_requirement the relevant locking requirement. @attr [Array<Array<Object>>] #requirement_trees the different requirement

trees that led to every requirement for the conflicting name.

@attr [{String=>Object}] activated_by_name the already-activated specs. @attr [Object] underlying_error an error that has occurred during resolution, and

will be raised at the end of it if no resolution is found.
PossibilitySet

A collection of possibility states that share the same dependencies @attr [Array] dependencies the dependencies for this set of possibilities @attr [Array] possibilities the possibilities

UnwindDetails

Details of the state to unwind to when a conflict occurs, and the cause of the unwind @attr [Integer] state_index the index of the state to unwind to @attr [Object] state_requirement the requirement of the state we're unwinding to @attr [Array] requirement_tree for the requirement we're relaxing @attr [Array] conflicting_requirements the requirements that combined to cause the conflict @attr [Array] #requirement_trees for the conflict @attr [Array] requirements_unwound_to_instead array of unwind requirements that were chosen over this unwind

Attributes

base[R]

@return [DependencyGraph] the base dependency graph to which

dependencies should be 'locked'
original_requested[R]

@return [Array] the dependencies that were explicitly required

resolver_ui[R]

@return [UI] the UI that knows how to communicate feedback about the

resolution process back to the user
specification_provider[R]

@return [SpecificationProvider] the provider that knows about

dependencies, requirements, specifications, versions, etc.

Public Class Methods

new(specification_provider, resolver_ui, requested, base) click to toggle source

Initializes a new resolution. @param [SpecificationProvider] #specification_provider

see {#specification_provider}

@param [UI] #resolver_ui see {#resolver_ui} @param [Array] requested see {#original_requested} @param [DependencyGraph] base see {#base}

# File lib/bundler/vendor/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

Public Instance Methods

activate_new_spec() click to toggle source

Add the current {#possibility} to the dependency graph of the current {#state} @return [void]

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 725
def activate_new_spec
  conflicts.delete(name)
  debug(depth) { "Activated #{name} at #{possibility}" }
  activated.set_payload(name, possibility)
  require_nested_dependencies_for(possibility)
end
attempt_to_activate() click to toggle source

Attempts to activate the current {#possibility} @return [void]

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 668
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
    # use reject!(!satisfied) for 1.8.7 compatibility
    possibility.possibilities.reject! 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
attempt_to_filter_existing_spec(vertex) click to toggle source

Attempts to update the existing vertex's `PossibilitySet` with a filtered version @return [void]

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 693
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
binding_requirement_in_set?(requirement, possible_binding_requirements, possibilities) click to toggle source

@param [Object] requirement we wish to check @param [Array] array of requirements @param [Array] array of possibilities the requirements will be used to filter @return [Boolean] whether or not the given requirement is required to filter

out all elements of the array of possibilities.
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 565
def binding_requirement_in_set?(requirement, possible_binding_requirements, possibilities)
  possibilities.any? do |poss|
    possibility_satisfies_requirements?(poss, possible_binding_requirements - [requirement])
  end
end
binding_requirements_for_conflict(conflict) click to toggle source

@param [Conflict] conflict @return [Array] minimal array of requirements that would cause the passed

conflict to occur.
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 522
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
build_details_for_unwind() click to toggle source

@return [UnwindDetails] Details of the nearest index to which we could unwind

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 332
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
conflict_fixing_possibilities?(state, binding_requirements) click to toggle source

@param [DependencyState] state @param [Array] array of requirements @return [Boolean] whether or not the given state has any possibilities

that could satisfy the given requirements
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 435
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
create_conflict(underlying_error = nil) click to toggle source

@return [Conflict] a {Conflict} that reflects the failure to activate

the {#possibility} in conjunction with the current {#state}
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 597
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
debug(depth = 0, &block) click to toggle source

Calls the {#resolver_ui}'s {UI#debug} method @param [Integer] depth the depth of the {#states} stack @param [Proc] block a block that yields a {#to_s} @return [void]

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 662
def debug(depth = 0, &block)
  resolver_ui.debug(depth, &block)
end
end_resolution() click to toggle source

Ends the resolution process @return [void]

# File lib/bundler/vendor/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
filter_possibilities_after_unwind(unwind_details) click to toggle source

Filter's a state's possibilities to remove any that would not fix the conflict we've just rewound from @param [UnwindDetails] details of the conflict just unwound from @return [void]

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 449
  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

  # Filter's a state's possibilities to remove any that would not satisfy
  # the requirements in the conflict we've just rewound from
  # @param [UnwindDetails] details of the conflict just unwound from
  # @return [void]
  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

  # @param [Object] possibility a single possibility
  # @param [Array] requirements an array of requirements
  # @return [Boolean] whether the possibility satisfies all of the
  #    given requirements
  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

  # Filter's a state's possibilities to remove any that would (eventually)
  # create a requirement in the conflict we've just rewound from
  # @param [UnwindDetails] details of the conflict just unwound from
  # @return [void]
  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 = Compatibility.flat_map(primary_unwinds) 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 = Compatibility.flat_map(parent_unwinds, &: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

  # @param [Conflict] conflict
  # @return [Array] minimal array of requirements that would cause the passed
  #    conflict to occur.
  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

  # @param [Object] requirement we wish to check
  # @param [Array] array of requirements
  # @param [Array] array of possibilities the requirements will be used to filter
  # @return [Boolean] whether or not the given requirement is required to filter
  #    out all elements of the array of possibilities.
  def binding_requirement_in_set?(requirement, possible_binding_requirements, possibilities)
    possibilities.any? do |poss|
      possibility_satisfies_requirements?(poss, possible_binding_requirements - [requirement])
    end
  end

  # @return [Object] the requirement that led to `requirement` being added
  #   to the list of requirements.
  def parent_of(requirement)
    return unless requirement
    return unless index = @parents_of[requirement].last
    return unless parent_state = @states[index]
    parent_state.requirement
  end

  # @return [Object] the requirement that led to a version of a possibility
  #   with the given name being activated.
  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

  # @return [ResolutionState] the state whose `requirement` is the given
  #   `requirement`.
  def find_state_for(requirement)
    return nil unless requirement
    states.find { |i| requirement == i.requirement }
  end

  # @return [Conflict] a {Conflict} that reflects the failure to activate
  #   the {#possibility} in conjunction with the current {#state}
  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

  # @return [Array<Array<Object>>] The different requirement
  #   trees that led to every requirement for the current spec.
  def requirement_trees
    vertex = activated.vertex_named(name)
    vertex.requirements.map { |r| requirement_tree_for(r) }
  end

  # @return [Array<Object>] the list of requirements that led to
  #   `requirement` being required.
  def requirement_tree_for(requirement)
    tree = []
    while requirement
      tree.unshift(requirement)
      requirement = parent_of(requirement)
    end
    tree
  end

  # Indicates progress roughly once every second
  # @return [void]
  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

  # Calls the {#resolver_ui}'s {UI#debug} method
  # @param [Integer] depth the depth of the {#states} stack
  # @param [Proc] block a block that yields a {#to_s}
  # @return [void]
  def debug(depth = 0, &block)
    resolver_ui.debug(depth, &block)
  end

  # Attempts to activate the current {#possibility}
  # @return [void]
  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
      # use reject!(!satisfied) for 1.8.7 compatibility
      possibility.possibilities.reject! 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

  # Attempts to update the existing vertex's `PossibilitySet` with a filtered version
  # @return [void]
  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

  # Generates a filtered version of the existing vertex's `PossibilitySet` using the
  # current state's `requirement`
  # @param [Object] existing vertex
  # @return [PossibilitySet] filtered possibility set
  def filtered_possibility_set(vertex)
    PossibilitySet.new(vertex.payload.dependencies, vertex.payload.possibilities & possibility.possibilities)
  end

  # @param [String] requirement_name the spec name to search for
  # @return [Object] the locked spec named `requirement_name`, if one
  #   is found on {#base}
  def locked_requirement_named(requirement_name)
    vertex = base.vertex_named(requirement_name)
    vertex && vertex.payload
  end

  # Add the current {#possibility} to the dependency graph of the current
  # {#state}
  # @return [void]
  def activate_new_spec
    conflicts.delete(name)
    debug(depth) { "Activated #{name} at #{possibility}" }
    activated.set_payload(name, possibility)
    require_nested_dependencies_for(possibility)
  end

  # Requires the dependencies that the recently activated spec has
  # @param [Object] activated_possibility the PossibilitySet that has just been
  #   activated
  # @return [void]
  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

  # Pushes a new {DependencyState} that encapsulates both existing and new
  # requirements
  # @param [Array] new_requirements
  # @return [void]
  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

  # Checks a proposed requirement with any existing locked requirement
  # before generating an array of possibilities for it.
  # @param [Object] the proposed requirement
  # @return [Array] possibilities
  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

  # @param [Object] the proposed requirement
  # @return [Array] possibility set containing only the locked requirement, if any
  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

  # Build an array of PossibilitySets, with each element representing a group of
  # dependency versions that all have the same sub-dependency version constraints
  # and are contiguous.
  # @param [Array] an array of possibilities
  # @return [Array] an array of possibility sets
  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

  # Pushes a new {DependencyState}.
  # If the {#specification_provider} says to
  # {SpecificationProvider#allow_missing?} that particular requirement, and
  # there are no possibilities for that requirement, then `state` is not
  # pushed, and the vertex in {#activated} is removed, and we continue
  # resolving the remaining requirements.
  # @param [DependencyState] state
  # @return [void]
  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
end
filter_possibilities_for_parent_unwind(unwind_details) click to toggle source

Filter's a state's possibilities to remove any that would (eventually) create a requirement in the conflict we've just rewound from @param [UnwindDetails] details of the conflict just unwound from @return [void]

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 496
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 = Compatibility.flat_map(primary_unwinds) 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 = Compatibility.flat_map(parent_unwinds, &: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
filter_possibilities_for_primary_unwind(unwind_details) click to toggle source

Filter's a state's possibilities to remove any that would not satisfy the requirements in the conflict we've just rewound from @param [UnwindDetails] details of the conflict just unwound from @return [void]

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 463
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
filtered_possibility_set(vertex) click to toggle source

Generates a filtered version of the existing vertex's `PossibilitySet` using the current state's `requirement` @param [Object] existing vertex @return [PossibilitySet] filtered possibility set

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 710
def filtered_possibility_set(vertex)
  PossibilitySet.new(vertex.payload.dependencies, vertex.payload.possibilities & possibility.possibilities)
end
find_state_for(requirement) click to toggle source

@return [ResolutionState] the state whose `requirement` is the given

`requirement`.
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 590
def find_state_for(requirement)
  return nil unless requirement
  states.find { |i| requirement == i.requirement }
end
group_possibilities(possibilities) click to toggle source

Build an array of PossibilitySets, with each element representing a group of dependency versions that all have the same sub-dependency version constraints and are contiguous. @param [Array] an array of possibilities @return [Array] an array of possibility sets

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 802
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
handle_missing_or_push_dependency_state(state) click to toggle source

Pushes a new {DependencyState}. If the {#specification_provider} says to {SpecificationProvider#allow_missing?} that particular requirement, and there are no possibilities for that requirement, then `state` is not pushed, and the vertex in {#activated} is removed, and we continue resolving the remaining requirements. @param [DependencyState] state @return [void]

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 827
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
indicate_progress() click to toggle source

Indicates progress roughly once every second @return [void]

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 644
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
initial_state() click to toggle source

Creates the initial state for the resolution, based upon the {#requested} dependencies @return [DependencyState] the initial state for the resolution

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 279
def 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

  requirements = sort_dependencies(original_requested, graph, {})
  initial_requirement = requirements.shift
  DependencyState.new(
    initial_requirement && name_for(initial_requirement),
    requirements,
    graph,
    initial_requirement,
    possibilities_for_requirement(initial_requirement, graph),
    0,
    {},
    []
  )
end
locked_requirement_named(requirement_name) click to toggle source

@param [String] requirement_name the spec name to search for @return [Object] the locked spec named `requirement_name`, if one

is found on {#base}
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 717
def locked_requirement_named(requirement_name)
  vertex = base.vertex_named(requirement_name)
  vertex && vertex.payload
end
locked_requirement_possibility_set(requirement, activated = self.activated) click to toggle source

@param [Object] the proposed requirement @return [Array] possibility set containing only the locked requirement, if any

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 783
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
parent_of(requirement) click to toggle source

@return [Object] the requirement that led to `requirement` being added

to the list of requirements.
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 573
    def parent_of(requirement)
      return unless requirement
      return unless index = @parents_of[requirement].last
      return unless parent_state = @states[index]
      parent_state.requirement
    end

    # @return [Object] the requirement that led to a version of a possibility
    #   with the given name being activated.
    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

    # @return [ResolutionState] the state whose `requirement` is the given
    #   `requirement`.
    def find_state_for(requirement)
      return nil unless requirement
      states.find { |i| requirement == i.requirement }
    end

    # @return [Conflict] a {Conflict} that reflects the failure to activate
    #   the {#possibility} in conjunction with the current {#state}
    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

    # @return [Array<Array<Object>>] The different requirement
    #   trees that led to every requirement for the current spec.
    def requirement_trees
      vertex = activated.vertex_named(name)
      vertex.requirements.map { |r| requirement_tree_for(r) }
    end

    # @return [Array<Object>] the list of requirements that led to
    #   `requirement` being required.
    def requirement_tree_for(requirement)
      tree = []
      while requirement
        tree.unshift(requirement)
        requirement = parent_of(requirement)
      end
      tree
    end

    # Indicates progress roughly once every second
    # @return [void]
    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

    # Calls the {#resolver_ui}'s {UI#debug} method
    # @param [Integer] depth the depth of the {#states} stack
    # @param [Proc] block a block that yields a {#to_s}
    # @return [void]
    def debug(depth = 0, &block)
      resolver_ui.debug(depth, &block)
    end

    # Attempts to activate the current {#possibility}
    # @return [void]
    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
        # use reject!(!satisfied) for 1.8.7 compatibility
        possibility.possibilities.reject! 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

    # Attempts to update the existing vertex's `PossibilitySet` with a filtered version
    # @return [void]
    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

    # Generates a filtered version of the existing vertex's `PossibilitySet` using the
    # current state's `requirement`
    # @param [Object] existing vertex
    # @return [PossibilitySet] filtered possibility set
    def filtered_possibility_set(vertex)
      PossibilitySet.new(vertex.payload.dependencies, vertex.payload.possibilities & possibility.possibilities)
    end

    # @param [String] requirement_name the spec name to search for
    # @return [Object] the locked spec named `requirement_name`, if one
    #   is found on {#base}
    def locked_requirement_named(requirement_name)
      vertex = base.vertex_named(requirement_name)
      vertex && vertex.payload
    end

    # Add the current {#possibility} to the dependency graph of the current
    # {#state}
    # @return [void]
    def activate_new_spec
      conflicts.delete(name)
      debug(depth) { "Activated #{name} at #{possibility}" }
      activated.set_payload(name, possibility)
      require_nested_dependencies_for(possibility)
    end

    # Requires the dependencies that the recently activated spec has
    # @param [Object] activated_possibility the PossibilitySet that has just been
    #   activated
    # @return [void]
    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

    # Pushes a new {DependencyState} that encapsulates both existing and new
    # requirements
    # @param [Array] new_requirements
    # @return [void]
    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

    # Checks a proposed requirement with any existing locked requirement
    # before generating an array of possibilities for it.
    # @param [Object] the proposed requirement
    # @return [Array] possibilities
    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

    # @param [Object] the proposed requirement
    # @return [Array] possibility set containing only the locked requirement, if any
    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

    # Build an array of PossibilitySets, with each element representing a group of
    # dependency versions that all have the same sub-dependency version constraints
    # and are contiguous.
    # @param [Array] an array of possibilities
    # @return [Array] an array of possibility sets
    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

    # Pushes a new {DependencyState}.
    # If the {#specification_provider} says to
    # {SpecificationProvider#allow_missing?} that particular requirement, and
    # there are no possibilities for that requirement, then `state` is not
    # pushed, and the vertex in {#activated} is removed, and we continue
    # resolving the remaining requirements.
    # @param [DependencyState] state
    # @return [void]
    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
  end
end
possibilities_for_requirement(requirement, activated = self.activated) click to toggle source

Checks a proposed requirement with any existing locked requirement before generating an array of possibilities for it. @param [Object] the proposed requirement @return [Array] possibilities

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 772
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
possibility() click to toggle source

@return [Object] the current possibility that the resolution is trying

to activate
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 266
def possibility
  possibilities.last
end
possibility_satisfies_requirements?(possibility, requirements) click to toggle source

@param [Object] possibility a single possibility @param [Array] requirements an array of requirements @return [Boolean] whether the possibility satisfies all of the

given requirements
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 481
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
process_topmost_state() click to toggle source

Processes the topmost available {RequirementState} on the stack @return [void]

# File lib/bundler/vendor/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
push_state_for_requirements(new_requirements, requires_sort = true, new_activated = activated) click to toggle source

Pushes a new {DependencyState} that encapsulates both existing and new requirements @param [Array] new_requirements @return [void]

# File lib/bundler/vendor/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

  # Checks a proposed requirement with any existing locked requirement
  # before generating an array of possibilities for it.
  # @param [Object] the proposed requirement
  # @return [Array] possibilities
  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

  # @param [Object] the proposed requirement
  # @return [Array] possibility set containing only the locked requirement, if any
  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

  # Build an array of PossibilitySets, with each element representing a group of
  # dependency versions that all have the same sub-dependency version constraints
  # and are contiguous.
  # @param [Array] an array of possibilities
  # @return [Array] an array of possibility sets
  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

  # Pushes a new {DependencyState}.
  # If the {#specification_provider} says to
  # {SpecificationProvider#allow_missing?} that particular requirement, and
  # there are no possibilities for that requirement, then `state` is not
  # pushed, and the vertex in {#activated} is removed, and we continue
  # resolving the remaining requirements.
  # @param [DependencyState] state
  # @return [void]
  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
end
raise_error_unless_state(conflicts) click to toggle source

Raises a VersionConflict error, or any underlying error, if there is no current state @return [void]

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 324
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

# @return [UnwindDetails] Details of the nearest index to which we could unwind
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

# @param [Array<Object>] array of requirements that combine to create a conflict
# @return [Array<UnwindDetails>] array of UnwindDetails that have a chance
#    of resolving the passed requirements
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

# @param [DependencyState] state
# @param [Array] array of requirements
# @return [Boolean] whether or not the given state has any possibilities
#    that could satisfy the given requirements
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

# Filter's a state's possibilities to remove any that would not fix the
# conflict we've just rewound from
# @param [UnwindDetails] details of the conflict just unwound from
# @return [void]
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

# Filter's a state's possibilities to remove any that would not satisfy
# the requirements in the conflict we've just rewound from
# @param [UnwindDetails] details of the conflict just unwound from
# @return [void]
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

# @param [Object] possibility a single possibility
# @param [Array] requirements an array of requirements
# @return [Boolean] whether the possibility satisfies all of the
#    given requirements
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

# Filter's a state's possibilities to remove any that would (eventually)
# create a requirement in the conflict we've just rewound from
# @param [UnwindDetails] details of the conflict just unwound from
# @return [void]
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 = Compatibility.flat_map(primary_unwinds) 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 = Compatibility.flat_map(parent_unwinds, &: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

# @param [Conflict] conflict
# @return [Array] minimal array of requirements that would cause the passed
#    conflict to occur.
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

# @param [Object] requirement we wish to check
# @param [Array] array of requirements
# @param [Array] array of possibilities the requirements will be used to filter
# @return [Boolean] whether or not the given requirement is required to filter
#    out all elements of the array of possibilities.
def binding_requirement_in_set?(requirement, possible_binding_requirements, possibilities)
  possibilities.any? do |poss|
    possibility_satisfies_requirements?(poss, possible_binding_requirements - [requirement])
  end
end

# @return [Object] the requirement that led to `requirement` being added
#   to the list of requirements.
def parent_of(requirement)
  return unless requirement
  return unless index = @parents_of[requirement].last
  return unless parent_state = @states[index]
  parent_state.requirement
end

# @return [Object] the requirement that led to a version of a possibility
#   with the given name being activated.
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

# @return [ResolutionState] the state whose `requirement` is the given
#   `requirement`.
def find_state_for(requirement)
  return nil unless requirement
  states.find { |i| requirement == i.requirement }
end

# @return [Conflict] a {Conflict} that reflects the failure to activate
#   the {#possibility} in conjunction with the current {#state}
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

# @return [Array<Array<Object>>] The different requirement
#   trees that led to every requirement for the current spec.
def requirement_trees
  vertex = activated.vertex_named(name)
  vertex.requirements.map { |r| requirement_tree_for(r) }
end

# @return [Array<Object>] the list of requirements that led to
#   `requirement` being required.
def requirement_tree_for(requirement)
  tree = []
  while requirement
    tree.unshift(requirement)
    requirement = parent_of(requirement)
  end
  tree
end

# Indicates progress roughly once every second
# @return [void]
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

# Calls the {#resolver_ui}'s {UI#debug} method
# @param [Integer] depth the depth of the {#states} stack
# @param [Proc] block a block that yields a {#to_s}
# @return [void]
def debug(depth = 0, &block)
  resolver_ui.debug(depth, &block)
end

# Attempts to activate the current {#possibility}
# @return [void]
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
    # use reject!(!satisfied) for 1.8.7 compatibility
    possibility.possibilities.reject! 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

# Attempts to update the existing vertex's `PossibilitySet` with a filtered version
# @return [void]
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

# Generates a filtered version of the existing vertex's `PossibilitySet` using the
# current state's `requirement`
# @param [Object] existing vertex
# @return [PossibilitySet] filtered possibility set
def filtered_possibility_set(vertex)
  PossibilitySet.new(vertex.payload.dependencies, vertex.payload.possibilities & possibility.possibilities)
end

# @param [String] requirement_name the spec name to search for
# @return [Object] the locked spec named `requirement_name`, if one
#   is found on {#base}
def locked_requirement_named(requirement_name)
  vertex = base.vertex_named(requirement_name)
  vertex && vertex.payload
end

# Add the current {#possibility} to the dependency graph of the current
# {#state}
# @return [void]
def activate_new_spec
  conflicts.delete(name)
  debug(depth) { "Activated #{name} at #{possibility}" }
  activated.set_payload(name, possibility)
  require_nested_dependencies_for(possibility)
end

# Requires the dependencies that the recently activated spec has
# @param [Object] activated_possibility the PossibilitySet that has just been
#   activated
# @return [void]
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

# Pushes a new {DependencyState} that encapsulates both existing and new
# requirements
# @param [Array] new_requirements
# @return [void]
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

# Checks a proposed requirement with any existing locked requirement
# before generating an array of possibilities for it.
# @param [Object] the proposed requirement
# @return [Array] possibilities
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

# @param [Object] the proposed requirement
# @return [Array] possibility set containing only the locked requirement, if any
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

# Build an array of PossibilitySets, with each element representing a group of
# dependency versions that all have the same sub-dependency version constraints
# and are contiguous.
# @param [Array] an array of possibilities
# @return [Array] an array of possibility sets
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

# Pushes a new {DependencyState}.
# If the {#specification_provider} says to
# {SpecificationProvider#allow_missing?} that particular requirement, and
# there are no possibilities for that requirement, then `state` is not
# pushed, and the vertex in {#activated} is removed, and we continue
# resolving the remaining requirements.
# @param [DependencyState] state
# @return [void]
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
    
require_nested_dependencies_for(possibility_set) click to toggle source

Requires the dependencies that the recently activated spec has @param [Object] activated_possibility the PossibilitySet that has just been

activated

@return [void]

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 736
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
requirement_for_existing_name(name) click to toggle source

@return [Object] the requirement that led to a version of a possibility

with the given name being activated.
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 582
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
requirement_tree_for(requirement) click to toggle source

@return [Array<Object>] the list of requirements that led to

`requirement` being required.
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 633
def requirement_tree_for(requirement)
  tree = []
  while requirement
    tree.unshift(requirement)
    requirement = parent_of(requirement)
  end
  tree
end
requirement_trees() click to toggle source

@return [Array<Array<Object>>] The different requirement

trees that led to every requirement for the current spec.
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 626
def requirement_trees
  vertex = activated.vertex_named(name)
  vertex.requirements.map { |r| requirement_tree_for(r) }
end
resolve() click to toggle source

Resolves the {#original_requested} dependencies into a full dependency

graph

@raise [ResolverError] if successful resolution is impossible @return [DependencyGraph] the dependency graph of successfully resolved

dependencies
# File lib/bundler/vendor/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

# @return [Integer] the number of resolver iterations in between calls to
#   {#resolver_ui}'s {UI#indicate_progress} method
attr_accessor :iteration_rate
private :iteration_rate

# @return [Time] the time at which resolution began
attr_accessor :started_at
private :started_at

# @return [Array<ResolutionState>] the stack of states for the resolution
attr_accessor :states
private :states

private

# Sets up the resolution process
# @return [void]
def start_resolution
  @started_at = Time.now

  handle_missing_or_push_dependency_state(initial_state)

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

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

# Ends the resolution process
# @return [void]
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

require 'bundler/vendor/molinillo/lib/molinillo/state'
require 'bundler/vendor/molinillo/lib/molinillo/modules/specification_provider'

require 'bundler/vendor/molinillo/lib/molinillo/delegates/resolution_state'
require 'bundler/vendor/molinillo/lib/molinillo/delegates/specification_provider'

include Bundler::Molinillo::Delegates::ResolutionState
include Bundler::Molinillo::Delegates::SpecificationProvider

# Processes the topmost available {RequirementState} on the stack
# @return [void]
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

# @return [Object] the current possibility that the resolution is trying
#   to activate
def possibility
  possibilities.last
end

# @return [RequirementState] the current state the resolution is
#   operating upon
def state
  states.last
end

# Creates the initial state for the resolution, based upon the
# {#requested} dependencies
# @return [DependencyState] the initial state for the resolution
def 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

  requirements = sort_dependencies(original_requested, graph, {})
  initial_requirement = requirements.shift
  DependencyState.new(
    initial_requirement && name_for(initial_requirement),
    requirements,
    graph,
    initial_requirement,
    possibilities_for_requirement(initial_requirement, graph),
    0,
    {},
    []
  )
end

# Unwinds the states stack because a conflict has been encountered
# @return [void]
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

# Raises a VersionConflict error, or any underlying error, if there is no
# current state
# @return [void]
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

# @return [UnwindDetails] Details of the nearest index to which we could unwind
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

# @param [Array<Object>] array of requirements that combine to create a conflict
# @return [Array<UnwindDetails>] array of UnwindDetails that have a chance
#    of resolving the passed requirements
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

# @param [DependencyState] state
# @param [Array] array of requirements
# @return [Boolean] whether or not the given state has any possibilities
#    that could satisfy the given requirements
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

# Filter's a state's possibilities to remove any that would not fix the
# conflict we've just rewound from
# @param [UnwindDetails] details of the conflict just unwound from
# @return [void]
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

# Filter's a state's possibilities to remove any that would not satisfy
# the requirements in the conflict we've just rewound from
# @param [UnwindDetails] details of the conflict just unwound from
# @return [void]
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

# @param [Object] possibility a single possibility
# @param [Array] requirements an array of requirements
# @return [Boolean] whether the possibility satisfies all of the
#    given requirements
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

# Filter's a state's possibilities to remove any that would (eventually)
# create a requirement in the conflict we've just rewound from
# @param [UnwindDetails] details of the conflict just unwound from
# @return [void]
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 = Compatibility.flat_map(primary_unwinds) 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 = Compatibility.flat_map(parent_unwinds, &: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

# @param [Conflict] conflict
# @return [Array] minimal array of requirements that would cause the passed
#    conflict to occur.
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

# @param [Object] requirement we wish to check
# @param [Array] array of requirements
# @param [Array] array of possibilities the requirements will be used to filter
# @return [Boolean] whether or not the given requirement is required to filter
#    out all elements of the array of possibilities.
def binding_requirement_in_set?(requirement, possible_binding_requirements, possibilities)
  possibilities.any? do |poss|
    possibility_satisfies_requirements?(poss, possible_binding_requirements - [requirement])
  end
end

# @return [Object] the requirement that led to `requirement` being added
#   to the list of requirements.
def parent_of(requirement)
  return unless requirement
  return unless index = @parents_of[requirement].last
  return unless parent_state = @states[index]
  parent_state.requirement
end

# @return [Object] the requirement that led to a version of a possibility
#   with the given name being activated.
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

# @return [ResolutionState] the state whose `requirement` is the given
#   `requirement`.
def find_state_for(requirement)
  return nil unless requirement
  states.find { |i| requirement == i.requirement }
end

# @return [Conflict] a {Conflict} that reflects the failure to activate
#   the {#possibility} in conjunction with the current {#state}
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

# @return [Array<Array<Object>>] The different requirement
#   trees that led to every requirement for the current spec.
def requirement_trees
  vertex = activated.vertex_named(name)
  vertex.requirements.map { |r| requirement_tree_for(r) }
end

# @return [Array<Object>] the list of requirements that led to
#   `requirement` being required.
def requirement_tree_for(requirement)
  tree = []
  while requirement
    tree.unshift(requirement)
    requirement = parent_of(requirement)
  end
  tree
end

# Indicates progress roughly once every second
# @return [void]
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

# Calls the {#resolver_ui}'s {UI#debug} method
# @param [Integer] depth the depth of the {#states} stack
# @param [Proc] block a block that yields a {#to_s}
# @return [void]
def debug(depth = 0, &block)
  resolver_ui.debug(depth, &block)
end

# Attempts to activate the current {#possibility}
# @return [void]
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
    # use reject!(!satisfied) for 1.8.7 compatibility
    possibility.possibilities.reject! 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

# Attempts to update the existing vertex's `PossibilitySet` with a filtered version
# @return [void]
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

# Generates a filtered version of the existing vertex's `PossibilitySet` using the
# current state's `requirement`
# @param [Object] existing vertex
# @return [PossibilitySet] filtered possibility set
def filtered_possibility_set(vertex)
  PossibilitySet.new(vertex.payload.dependencies, vertex.payload.possibilities & possibility.possibilities)
end

# @param [String] requirement_name the spec name to search for
# @return [Object] the locked spec named `requirement_name`, if one
#   is found on {#base}
def locked_requirement_named(requirement_name)
  vertex = base.vertex_named(requirement_name)
  vertex && vertex.payload
end

# Add the current {#possibility} to the dependency graph of the current
# {#state}
# @return [void]
def activate_new_spec
  conflicts.delete(name)
  debug(depth) { "Activated #{name} at #{possibility}" }
  activated.set_payload(name, possibility)
  require_nested_dependencies_for(possibility)
end

# Requires the dependencies that the recently activated spec has
# @param [Object] activated_possibility the PossibilitySet that has just been
#   activated
# @return [void]
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

# Pushes a new {DependencyState} that encapsulates both existing and new
# requirements
# @param [Array] new_requirements
# @return [void]
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

# Checks a proposed requirement with any existing locked requirement
# before generating an array of possibilities for it.
# @param [Object] the proposed requirement
# @return [Array] possibilities
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

# @param [Object] the proposed requirement
# @return [Array] possibility set containing only the locked requirement, if any
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

# Build an array of PossibilitySets, with each element representing a group of
# dependency versions that all have the same sub-dependency version constraints
# and are contiguous.
# @param [Array] an array of possibilities
# @return [Array] an array of possibility sets
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

# Pushes a new {DependencyState}.
# If the {#specification_provider} says to
# {SpecificationProvider#allow_missing?} that particular requirement, and
# there are no possibilities for that requirement, then `state` is not
# pushed, and the vertex in {#activated} is removed, and we continue
# resolving the remaining requirements.
# @param [DependencyState] state
# @return [void]
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
resolve_activated_specs() click to toggle source
# File lib/bundler/vendor/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
start_resolution() click to toggle source

Sets up the resolution process @return [void]

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

  handle_missing_or_push_dependency_state(initial_state)

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

@return [RequirementState] the current state the resolution is

operating upon
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 272
def state
  states.last
end
unwind_for_conflict() click to toggle source

Unwinds the states stack because a conflict has been encountered @return [void]

# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 304
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
unwind_options_for_requirements(binding_requirements) click to toggle source

@param [Array<Object>] array of requirements that combine to create a conflict @return [Array<UnwindDetails>] array of UnwindDetails that have a chance

of resolving the passed requirements
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 367
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