Class: Gem::Resolver::Molinillo::Resolver::Resolution
Relationships & Source Files | |
Namespace Children | |
Classes:
| |
Super Chains via Extension / Inclusion / Inheritance | |
Instance Chain:
|
|
Inherits: | Object |
Defined in: | lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb |
Overview
A specific resolution from a given ::Gem::Resolver::Molinillo::Resolver
Class Method Summary
-
.new(specification_provider, resolver_ui, requested, base) ⇒ Resolution
constructor
Initializes a new resolution.
Instance Attribute Summary
- #base ⇒ DependencyGraph readonly
- #original_requested ⇒ Array readonly
- #resolver_ui ⇒ UI readonly
- #specification_provider ⇒ SpecificationProvider readonly
- #iteration_rate ⇒ Integer rw private
-
#new_spec_satisfied? ⇒ Boolean
readonly
private
possibility.
- #started_at ⇒ Time rw private
- #states ⇒ Array<ResolutionState> rw private
Instance Method Summary
-
#resolve ⇒ DependencyGraph
Resolves the #original_requested dependencies into a full dependency graph.
-
#activate_spec ⇒ void
private
Add the current #possibility to the dependency graph of the current #state
-
#attempt_to_activate ⇒ void
private
Attempts to activate the current #possibility
-
#attempt_to_activate_existing_spec(existing_node) ⇒ void
private
Attempts to activate the current #possibility (given that it has already been activated).
-
#attempt_to_activate_new_spec ⇒ void
private
Attempts to activate the current #possibility (given that it hasn’t already been activated).
-
#attempt_to_swap_possibility ⇒ Boolean
private
Attempts to swp the current #possibility with the already-activated spec with the given name.
- #create_conflict ⇒ Conflict private
-
#debug(depth = 0, &block) ⇒ void
private
Calls the #resolver_ui‘s UI#debug method.
-
#end_resolution ⇒ void
private
Ends the resolution process.
- #find_state_for(requirement) ⇒ ResolutionState private
-
#fixup_swapped_children(vertex) ⇒ void
private
Ensures there are no orphaned successors to the given
vertex
. -
#handle_missing_or_push_dependency_state(state) ⇒ void
private
Pushes a new
::Gem::Resolver::Molinillo::DependencyState
. -
#indicate_progress ⇒ void
private
Indicates progress roughly once every second.
-
#initial_state ⇒ DependencyState
private
Creates the initial state for the resolution, based upon the
#requested
dependencies. - #locked_requirement_named(requirement_name) ⇒ Object private
- #parent_of(requirement) ⇒ Object private
- #possibility ⇒ Object private
-
#process_topmost_state ⇒ void
private
Processes the topmost available
RequirementState
on the stack. -
#push_state_for_requirements(new_requirements, requires_sort = true, new_activated = activated) ⇒ void
private
Pushes a new
::Gem::Resolver::Molinillo::DependencyState
that encapsulates both existing and new requirements. -
#require_nested_dependencies_for(activated_spec) ⇒ void
private
Requires the dependencies that the recently activated spec has.
- #requirement_for_existing_name(name) ⇒ Object private
- #requirement_tree_for(requirement) ⇒ Array<Object> private
- #requirement_trees ⇒ Array<Array<Object>> private
-
#start_resolution ⇒ void
private
Sets up the resolution process.
- #state ⇒ RequirementState private
- #state_any?(state) ⇒ Boolean private
- #state_index_for_unwind ⇒ Integer private
-
#unwind_for_conflict ⇒ void
private
Unwinds the states stack because a conflict has been encountered.
::Gem::Resolver::Molinillo::Delegates::SpecificationProvider
- Included
#allow_missing? | Returns whether this dependency, which has no possible matching specifications, can safely be ignored. |
#dependencies_for | Returns the dependencies of |
#name_for | Returns the name for the given |
#name_for_explicit_dependency_source, #name_for_locking_dependency_source, | |
#requirement_satisfied_by? | Determines whether the given |
#search_for | Search for the specifications that match the given dependency. |
#sort_dependencies | Sort dependencies so that the ones that are easiest to resolve are first. |
#with_no_such_dependency_error_handling | Ensures any raised |
::Gem::Resolver::Molinillo::Delegates::ResolutionState
- Included
#activated | A state that a |
#conflicts | A state that a |
#depth | A state that a |
#name | A state that a |
#possibilities | A state that a |
#requirement | A state that a |
#requirements | A state that a |
Constructor Details
.new(specification_provider, resolver_ui, requested, base) ⇒ Resolution
Initializes a new resolution.
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 48
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
Instance Attribute Details
#base ⇒ DependencyGraph (readonly)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 37
attr_reader :base
#iteration_rate ⇒ Integer
(rw, private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 88
attr_accessor :iteration_rate
#new_spec_satisfied? ⇒ Boolean
(readonly, private)
possibility.
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 411
def new_spec_satisfied? unless requirement_satisfied_by?(requirement, activated, possibility) debug(depth) { 'Unsatisfied by requested spec' } return false end locked_requirement = locked_requirement_named(name) locked_spec_satisfied = !locked_requirement || requirement_satisfied_by?(locked_requirement, activated, possibility) debug(depth) { 'Unsatisfied by locked spec' } unless locked_spec_satisfied locked_spec_satisfied end
#original_requested ⇒ Array
(readonly)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 40
attr_reader :original_requested
#resolver_ui ⇒ UI (readonly)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 33
attr_reader :resolver_ui
#specification_provider ⇒ SpecificationProvider (readonly)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 29
attr_reader :specification_provider
#started_at ⇒ Time
(rw, private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 92
attr_accessor :started_at
#states ⇒ Array
<ResolutionState> (rw, private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 96
attr_accessor :states
Instance Method Details
#activate_spec ⇒ void
(private)
This method returns an undefined value.
Add the current #possibility to the dependency graph of the current #state
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 437
def activate_spec conflicts.delete(name) debug(depth) { "Activated #{name} at #{possibility}" } activated.set_payload(name, possibility) require_nested_dependencies_for(possibility) end
#attempt_to_activate ⇒ void
(private)
This method returns an undefined value.
Attempts to activate the current #possibility
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 312
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
#attempt_to_activate_existing_spec(existing_node) ⇒ void
(private)
This method returns an undefined value.
Attempts to activate the current #possibility (given that it has already been activated)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 326
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, false) else return if attempt_to_swap_possibility create_conflict debug(depth) { "Unsatisfied by existing spec (#{existing_node.payload})" } unwind_for_conflict end end
#attempt_to_activate_new_spec ⇒ void
(private)
This method returns an undefined value.
Attempts to activate the current #possibility (given that it hasn’t already been activated)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 400
def attempt_to_activate_new_spec if new_spec_satisfied? activate_spec else create_conflict unwind_for_conflict end end
#attempt_to_swap_possibility ⇒ Boolean
(private)
Attempts to swp the current #possibility with the already-activated spec with the given name
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 342
def attempt_to_swap_possibility activated.tag(:swap) vertex = activated.vertex_named(name) activated.set_payload(name, possibility) if !vertex.requirements. all? { |r| requirement_satisfied_by?(r, activated, possibility) } || !new_spec_satisfied? activated.rewind_to(:swap) return end fixup_swapped_children(vertex) activate_spec end
#create_conflict ⇒ Conflict (private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 244
def create_conflict 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 { |edge| (requirements[edge.origin.payload] ||= []).unshift(edge.requirement) } activated_by_name = {} activated.each { |v| activated_by_name[v.name] = v.payload if v.payload } conflicts[name] = Conflict.new( requirement, requirements, vertex.payload, possibility, locked_requirement, requirement_trees, activated_by_name ) end
#debug(depth = 0, &block) ⇒ void
(private)
This method returns an undefined value.
Calls the #resolver_ui‘s UI#debug method
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 306
def debug(depth = 0, &block) resolver_ui.debug(depth, &block) end
#end_resolution ⇒ void
(private)
This method returns an undefined value.
Ends the resolution process
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 114
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
#find_state_for(requirement) ⇒ ResolutionState (private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 231
def find_state_for(requirement) return nil unless requirement states.reverse_each.find { |i| requirement == i.requirement && i.is_a?(DependencyState) } end
#fixup_swapped_children(vertex) ⇒ void
(private)
This method returns an undefined value.
Ensures there are no orphaned successors to the given vertex
.
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 359
def fixup_swapped_children(vertex) # rubocop:disable Metrics/CyclomaticComplexity payload = vertex.payload deps = dependencies_for(payload).group_by(&method(:name_for)) vertex.outgoing_edges.each do |outgoing_edge| requirement = outgoing_edge.requirement parent_index = @parents_of[requirement].last succ = outgoing_edge.destination matching_deps = Array(deps[succ.name]) dep_matched = matching_deps.include?(requirement) # only push the current index when it was originally required by the # same named spec if parent_index && states[parent_index].name == name @parents_of[requirement].push(states.size - 1) end if matching_deps.empty? && !succ.root? && succ.predecessors.to_a == [vertex] debug(depth) { "Removing orphaned spec #{succ.name} after swapping #{name}" } succ.requirements.each { |r| @parents_of.delete(r) } removed_names = activated.detach_vertex_named(succ.name).map(&:name) requirements.delete_if do |r| # the only removed vertices are those with no other requirements, # so it's safe to delete only based upon name here removed_names.include?(name_for(r)) end elsif !dep_matched debug(depth) { "Removing orphaned dependency #{requirement} after swapping #{name}" } # also reset if we're removing the edge, but only if its parent has # already been fixed up @parents_of[requirement].push(states.size - 1) if @parents_of[requirement].empty? activated.delete_edge(outgoing_edge) requirements.delete(requirement) end end end
#handle_missing_or_push_dependency_state(state) ⇒ void
(private)
This method returns an undefined value.
Pushes a new ::Gem::Resolver::Molinillo::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 node in #activated
is removed, and we continue resolving the remaining requirements.
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 484
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 ⇒ void
(private)
This method returns an undefined value.
Indicates progress roughly once every second
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 288
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 ⇒ DependencyState (private)
Creates the initial state for the resolution, based upon the #requested
dependencies
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 159
def initial_state graph = DependencyGraph.new.tap do |dg| original_requested.each { |r| dg.add_vertex(name_for(r), nil, true).tap { |v| v.explicit_requirements << r } } 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, initial_requirement && search_for(initial_requirement), 0, {} ) end
#locked_requirement_named(requirement_name) ⇒ Object
(private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 429
def locked_requirement_named(requirement_name) vertex = base.vertex_named(requirement_name) vertex && vertex.payload end
#parent_of(requirement) ⇒ Object
(private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 215
def parent_of(requirement) return unless requirement return unless index = @parents_of[requirement].last return unless parent_state = @states[index] parent_state.requirement end
#possibility ⇒ Object
(private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 146
def possibility possibilities.last end
#process_topmost_state ⇒ void
(private)
This method returns an undefined value.
Processes the topmost available RequirementState
on the stack
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 135
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
#push_state_for_requirements(new_requirements, requires_sort = true, new_activated = activated) ⇒ void
(private)
This method returns an undefined value.
Pushes a new ::Gem::Resolver::Molinillo::DependencyState
that encapsulates both existing and new requirements
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 465
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 = new_requirements.shift new_name = new_requirement ? name_for(new_requirement) : ''.freeze possibilities = new_requirement ? search_for(new_requirement) : [] handle_missing_or_push_dependency_state DependencyState.new( new_name, new_requirements, new_activated, new_requirement, possibilities, depth, conflicts.dup ) end
#require_nested_dependencies_for(activated_spec) ⇒ void
(private)
This method returns an undefined value.
Requires the dependencies that the recently activated spec has
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 448
def require_nested_dependencies_for(activated_spec) nested_dependencies = dependencies_for(activated_spec) debug(depth) { "Requiring nested dependencies (#{nested_dependencies.join(', ')})" } nested_dependencies.each do |d| activated.add_child_vertex(name_for(d), nil, [name_for(activated_spec)], 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) ⇒ Object
(private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 224
def requirement_for_existing_name(name) return nil unless activated.vertex_named(name).payload states.find { |s| s.name == name }.requirement end
#requirement_tree_for(requirement) ⇒ Array
<Object
> (private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 277
def requirement_tree_for(requirement) tree = [] while requirement tree.unshift(requirement) requirement = parent_of(requirement) end tree end
#requirement_trees ⇒ Array
<Array
<Object
>> (private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 270
def requirement_trees vertex = activated.vertex_named(name) vertex.requirements.map { |r| requirement_tree_for(r) } end
#resolve ⇒ DependencyGraph
Resolves the #original_requested dependencies into a full dependency graph
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 63
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 do |s| if s states.push(s) activated.tag(s) end end end process_topmost_state end activated.freeze ensure end_resolution end
#start_resolution ⇒ void
(private)
This method returns an undefined value.
Sets up the resolution process
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 103
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 ⇒ RequirementState
(private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 152
def state states.last end
#state_any?(state) ⇒ Boolean
(private)
#state_index_for_unwind ⇒ Integer
(private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 194
def state_index_for_unwind current_requirement = requirement existing_requirement = requirement_for_existing_name(name) index = -1 [current_requirement, existing_requirement].each do |r| until r.nil? current_state = find_state_for(r) if state_any?(current_state) current_index = states.index(current_state) index = current_index if current_index > index break end r = parent_of(r) end end index end
#unwind_for_conflict ⇒ void
(private)
This method returns an undefined value.
Unwinds the states stack because a conflict has been encountered
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 180
def unwind_for_conflict debug(depth) { "Unwinding for conflict: #{requirement} to #{state_index_for_unwind / 2}" } conflicts.tap do |c| sliced_states = states.slice!((state_index_for_unwind + 1)..-1) raise VersionConflict.new(c) unless state activated.rewind_to(sliced_states.first || :initial_state) if sliced_states state.conflicts = c index = states.size - 1 @parents_of.each { |_, a| a.reject! { |i| i >= index } } end end