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 the spec 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.
Attributes
@return [DependencyGraph] the base dependency graph to which
dependencies should be 'locked'
@return [Integer] the number of resolver iterations in between calls to
{#resolver_ui}'s {UI#indicate_progress} method
@return [Array] the dependencies that were explicitly required
@return [UI] the UI that knows how to communicate feedback about the
resolution process back to the user
@return [SpecificationProvider] the provider that knows about
dependencies, requirements, specifications, versions, etc.
@return [Time] the time at which resolution began
@return [Array<ResolutionState>] the stack of states for the resolution
Public Class Methods
@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 44 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 end
Public Instance Methods
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 58 def resolve start_resolution while state break unless state.requirements.any? || state.requirement 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 { |s| states.push(s) if s } end process_topmost_state end activated.freeze ensure end_resolution end
Private Instance Methods
Add the current {#possibility} to the dependency graph of the current {#state} @return [void]
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 376 def activate_spec conflicts.delete(name) debug(depth) { 'Activated ' + name + ' at ' + possibility.to_s } vertex = activated.vertex_named(name) vertex.payload = possibility require_nested_dependencies_for(possibility) end
Attempts to activate the current {#possibility} @return [void]
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 306 def attempt_to_activate debug(depth) { 'Attempting to activate ' + possibility.to_s } existing_node = activated.vertex_named(name) if existing_node.payload debug(depth) { "Found existing spec (#{existing_node.payload})" } attempt_to_activate_existing_spec(existing_node) else attempt_to_activate_new_spec end end
Attempts to activate the current {#possibility} (given that it has already been activated) @return [void]
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 320 def attempt_to_activate_existing_spec(existing_node) existing_spec = existing_node.payload if requirement_satisfied_by?(requirement, activated, existing_spec) new_requirements = requirements.dup push_state_for_requirements(new_requirements) else return if attempt_to_swap_possibility create_conflict debug(depth) { "Unsatisfied by existing spec (#{existing_node.payload})" } unwind_for_conflict end end
Attempts to activate the current {#possibility} (given that it hasn't already been activated) @return [void]
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 347 def attempt_to_activate_new_spec satisfied = begin locked_requirement = locked_requirement_named(name) requested_spec_satisfied = requirement_satisfied_by?(requirement, activated, possibility) locked_spec_satisfied = !locked_requirement || requirement_satisfied_by?(locked_requirement, activated, possibility) debug(depth) { 'Unsatisfied by requested spec' } unless requested_spec_satisfied debug(depth) { 'Unsatisfied by locked spec' } unless locked_spec_satisfied requested_spec_satisfied && locked_spec_satisfied end if satisfied activate_spec else create_conflict unwind_for_conflict end end
Attempts to swp the current {#possibility} with the already-activated spec with the given name @return [Boolean] Whether the possibility was swapped into {#activated}
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 336 def attempt_to_swap_possibility swapped = activated.dup swapped.vertex_named(name).payload = possibility return unless swapped.vertex_named(name).requirements. all? { |r| requirement_satisfied_by?(r, swapped, possibility) } attempt_to_activate_new_spec end
@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 246 def create_conflict vertex = activated.vertex_named(name) requirements = { name_for_explicit_dependency_source => vertex.explicit_requirements, name_for_locking_dependency_source => Array(locked_requirement_named(name)), } vertex.incoming_edges.each { |edge| (requirements[edge.origin.payload] ||= []).unshift(*edge.requirements) } conflicts[name] = Conflict.new( requirement, Hash[requirements.select { |_, r| !r.empty? }], vertex.payload, possibility, locked_requirement_named(name), requirement_trees ) 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]
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 300 def debug(depth = 0, &block) resolver_ui.debug(depth, &block) end
Ends the resolution process @return [void]
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 104 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
@return [ResolutionState] the state whose `requirement` is the given
`requirement`.
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 233 def find_state_for(requirement) return nil unless requirement states.reverse_each.find { |i| requirement == i.requirement && i.is_a?(DependencyState) } end
Indicates progress roughly once every second @return [void]
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 282 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
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 164 def initial_state graph = DependencyGraph.new.tap do |dg| original_requested.each { |r| dg.add_root_vertex(name_for(r), nil).tap { |v| v.explicit_requirements << r } } end requirements = sort_dependencies(original_requested, graph, {}) initial_requirement = requirements.shift DependencyState.new( initial_requirement && name_for(initial_requirement), requirements, graph, initial_requirement, initial_requirement && search_for(initial_requirement), 0, {} ) 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}
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 368 def locked_requirement_named(requirement_name) vertex = base.vertex_named(requirement_name) vertex && vertex.payload end
@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 214 def parent_of(requirement) return nil unless requirement seen = false state = states.reverse_each.find do |s| seen ||= s.requirement == requirement seen && s.requirement != requirement && !s.requirements.include?(requirement) end state && state.requirement end
@return [Object] the current possibility that the resolution is trying
to activate
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 151 def possibility possibilities.last end
Processes the topmost available {RequirementState} on the stack @return [void]
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 140 def process_topmost_state if possibility attempt_to_activate else create_conflict if state.is_a? PossibilityState unwind_for_conflict until possibility && state.is_a?(DependencyState) end end
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 400 def push_state_for_requirements(new_requirements) new_requirements = sort_dependencies(new_requirements.uniq, activated, conflicts) new_requirement = new_requirements.shift states.push DependencyState.new( new_requirement ? name_for(new_requirement) : '', new_requirements, activated.dup, new_requirement, new_requirement ? search_for(new_requirement) : [], depth, conflicts.dup ) end
Requires the dependencies that the recently activated spec has @param [Object] activated_spec the specification that has just been
activated
@return [void]
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 388 def require_nested_dependencies_for(activated_spec) nested_dependencies = dependencies_for(activated_spec) debug(depth) { "Requiring nested dependencies (#{nested_dependencies.map(&:to_s).join(', ')})" } nested_dependencies.each { |d| activated.add_child_vertex name_for(d), nil, [name_for(activated_spec)], d } push_state_for_requirements(requirements + nested_dependencies) end
@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 226 def requirement_for_existing_name(name) return nil unless activated.vertex_named(name).payload states.reverse_each.find { |s| !s.activated.vertex_named(name).payload }.requirement end
@return [Array<Object>] the list of requirements that led to
`requirement` being required.
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 271 def requirement_tree_for(requirement) tree = [] while requirement tree.unshift(requirement) requirement = parent_of(requirement) end tree end
@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 265 def requirement_trees activated.vertex_named(name).requirements.map { |r| requirement_tree_for(r) } end
Sets up the resolution process @return [void]
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 93 def start_resolution @started_at = Time.now states.push(initial_state) debug { "Starting resolution (#{@started_at})" } resolver_ui.before_resolution end
@return [RequirementState] the current state the resolution is
operating upon
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 157 def state states.last end
@return [Boolean] whether or not the given state has any possibilities
left.
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 240 def state_any?(state) state && state.possibilities.any? end
@return [Integer] The index to which the resolution should unwind in the
case of conflict.
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 195 def state_index_for_unwind current_requirement = requirement existing_requirement = requirement_for_existing_name(name) until current_requirement.nil? current_state = find_state_for(current_requirement) return states.index(current_state) if state_any?(current_state) current_requirement = parent_of(current_requirement) end until existing_requirement.nil? existing_state = find_state_for(existing_requirement) return states.index(existing_state) if state_any?(existing_state) existing_requirement = parent_of(existing_requirement) end -1 end
Unwinds the states stack because a conflict has been encountered @return [void]
# File lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb, line 184 def unwind_for_conflict debug(depth) { "Unwinding for conflict: #{requirement}" } conflicts.tap do |c| states.slice!((state_index_for_unwind + 1)..-1) raise VersionConflict.new(c) unless state state.conflicts = c end end