Class: Gem::Resolver::Molinillo::Resolver::Resolution
Relationships & Source Files | |
Namespace Children | |
Classes:
| |
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
- #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
-
#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.dup) ⇒ 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.
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 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 82
attr_accessor :iteration_rate
#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 86
attr_accessor :started_at
#states ⇒ Array
<ResolutionState> (rw, private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 90
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 383
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
#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 313
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 327
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 354
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
#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 343
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
#create_conflict ⇒ Conflict (private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 251
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.requirement) } conflicts[name] = Conflict.new( requirement, Hash[requirements.select { |_, r| !r.empty? }], vertex.payload, possibility, locked_requirement_named(name), requirement_trees, Hash[activated.map { |v| [v.name, v.payload] }.select(&:last)] ) 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 307
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 108
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 238
def find_state_for(requirement) return nil unless requirement states.reverse_each.find { |i| requirement == i.requirement && i.is_a?(DependencyState) } 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 426
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 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 289
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 169
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 } } 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 375
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 219
def parent_of(requirement) return nil unless requirement seen = false state = states.reverse_each.find do |s| seen ||= s.requirement == requirement || s.requirements.include?(requirement) seen && s.requirement != requirement && !s.requirements.include?(requirement) end state && state.requirement end
#possibility ⇒ Object
(private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 156
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 145
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.dup) ⇒ 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 407
def push_state_for_requirements(new_requirements, requires_sort = true, new_activated = activated.dup) 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) : '' 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 395
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, nested_dependencies.size > 0) end
#requirement_for_existing_name(name) ⇒ Object
(private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 231
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
#requirement_tree_for(requirement) ⇒ Array
<Object
> (private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 278
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 271
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 62
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
#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 97
def start_resolution @started_at = Time.now handle_missing_or_push_dependency_state(initial_state) debug { "Starting resolution (#{@started_at})" } resolver_ui.before_resolution end
#state ⇒ RequirementState
(private)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb', line 162
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 200
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
#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 189
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