From 5f6715275e703ab49666a0440e6fcbb92a24c32f Mon Sep 17 00:00:00 2001 From: hsbt Date: Thu, 19 Nov 2015 06:16:19 +0000 Subject: * lib/rubygems: Update to RubyGems 2.5.0+ HEAD(c6b4946). this version includes #1114, #1314, #1322, #1375, #1383, #1387 * test/rubygems: ditto. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@52666 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- .../molinillo/lib/molinillo/dependency_graph.rb | 153 +++++++++++---------- .../molinillo/lib/molinillo/gem_metadata.rb | 2 +- .../resolver/molinillo/lib/molinillo/resolution.rb | 28 ++-- 3 files changed, 99 insertions(+), 84 deletions(-) (limited to 'lib/rubygems/resolver') diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb index b6db1b7417..9780200e6f 100644 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb +++ b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb @@ -34,40 +34,34 @@ module Gem::Resolver::Molinillo # A directed edge of a {DependencyGraph} # @attr [Vertex] origin The origin of the directed edge # @attr [Vertex] destination The destination of the directed edge - # @attr [Array] requirements The requirements the directed edge represents - Edge = Struct.new(:origin, :destination, :requirements) + # @attr [Object] requirement The requirement the directed edge represents + Edge = Struct.new(:origin, :destination, :requirement) - # @return [{String => Vertex}] vertices that have no {Vertex#predecessors}, - # keyed by by {Vertex#name} - attr_reader :root_vertices # @return [{String => Vertex}] the vertices of the dependency graph, keyed # by {Vertex#name} attr_reader :vertices - # @return [Set] the edges of the dependency graph - attr_reader :edges def initialize @vertices = {} - @edges = Set.new - @root_vertices = {} end # Initializes a copy of a {DependencyGraph}, ensuring that all {#vertices} - # have the correct {Vertex#graph} set + # are properly copied. def initialize_copy(other) super - @vertices = other.vertices.reduce({}) do |vertices, (name, vertex)| - vertices.tap do |hash| - hash[name] = vertex.dup.tap { |v| v.graph = self } + @vertices = {} + traverse = lambda do |new_v, old_v| + return if new_v.outgoing_edges.size == old_v.outgoing_edges.size + old_v.outgoing_edges.each do |edge| + destination = add_vertex(edge.destination.name, edge.destination.payload) + add_edge_no_circular(new_v, destination, edge.requirement) + traverse.call(destination, edge.destination) end end - @root_vertices = Hash[@vertices.select { |n, _v| other.root_vertices[n] }] - @edges = other.edges.map do |edge| - Edge.new( - vertex_named(edge.origin.name), - vertex_named(edge.destination.name), - edge.requirements.dup - ) + other.vertices.each do |name, vertex| + new_vertex = add_vertex(name, vertex.payload, vertex.root?) + new_vertex.explicit_requirements.replace(vertex.explicit_requirements) + traverse.call(new_vertex, vertex) end end @@ -80,7 +74,12 @@ module Gem::Resolver::Molinillo # by a recursive traversal of each {#root_vertices} and its # {Vertex#successors} def ==(other) - root_vertices == other.root_vertices + return false unless other + vertices.each do |name, vertex| + other_vertex = other.vertex_named(name) + return false unless other_vertex + return false unless other_vertex.successors.map(&:name).to_set == vertex.successors.map(&:name).to_set + end end # @param [String] name @@ -89,15 +88,13 @@ module Gem::Resolver::Molinillo # @param [Object] requirement the requirement that is requiring the child # @return [void] def add_child_vertex(name, payload, parent_names, requirement) - is_root = parent_names.include?(nil) - parent_nodes = parent_names.compact.map { |n| vertex_named(n) } - vertex = vertex_named(name) || if is_root - add_root_vertex(name, payload) - else - add_vertex(name, payload) - end - vertex.payload ||= payload - parent_nodes.each do |parent_node| + vertex = add_vertex(name, payload) + parent_names.each do |parent_name| + unless parent_name + vertex.root = true + next + end + parent_node = vertex_named(parent_name) add_edge(parent_node, vertex, requirement) end vertex @@ -106,16 +103,11 @@ module Gem::Resolver::Molinillo # @param [String] name # @param [Object] payload # @return [Vertex] the vertex that was added to `self` - def add_vertex(name, payload) - vertex = vertices[name] ||= Vertex.new(self, name, payload) - vertex.tap { |v| v.payload = payload } - end - - # @param [String] name - # @param [Object] payload - # @return [Vertex] the vertex that was added to `self` - def add_root_vertex(name, payload) - add_vertex(name, payload).tap { |v| root_vertices[name] = v } + def add_vertex(name, payload, root = false) + vertex = vertices[name] ||= Vertex.new(name, payload) + vertex.payload ||= payload + vertex.root ||= root + vertex end # Detaches the {#vertex_named} `name` {Vertex} from the graph, recursively @@ -123,12 +115,12 @@ module Gem::Resolver::Molinillo # @param [String] name # @return [void] def detach_vertex_named(name) - vertex = vertex_named(name) - return unless vertex - successors = vertex.successors - vertices.delete(name) - edges.reject! { |e| e.origin == vertex || e.destination == vertex } - successors.each { |v| detach_vertex_named(v.name) unless root_vertices[v.name] || v.predecessors.any? } + return unless vertex = vertices.delete(name) + vertex.outgoing_edges.each do |e| + v = e.destination + v.incoming_edges.delete(e) + detach_vertex_named(v.name) unless v.root? || v.predecessors.any? + end end # @param [String] name @@ -140,7 +132,8 @@ module Gem::Resolver::Molinillo # @param [String] name # @return [Vertex,nil] the root vertex with the given name def root_vertex_named(name) - root_vertices[name] + vertex = vertex_named(name) + vertex if vertex && vertex.root? end # Adds a new {Edge} to the dependency graph @@ -149,18 +142,24 @@ module Gem::Resolver::Molinillo # @param [Object] requirement the requirement that this edge represents # @return [Edge] the added edge def add_edge(origin, destination, requirement) - if origin == destination || destination.path_to?(origin) + if destination.path_to?(origin) raise CircularDependencyError.new([origin, destination]) end - Edge.new(origin, destination, [requirement]).tap { |e| edges << e } + add_edge_no_circular(origin, destination, requirement) + end + + private + + def add_edge_no_circular(origin, destination, requirement) + edge = Edge.new(origin, destination, requirement) + origin.outgoing_edges << edge + destination.incoming_edges << edge + edge end # A vertex in a {DependencyGraph} that encapsulates a {#name} and a # {#payload} class Vertex - # @return [DependencyGraph] the graph this vertex is a node of - attr_accessor :graph - # @return [String] the name of the vertex attr_accessor :name @@ -171,50 +170,62 @@ module Gem::Resolver::Molinillo # this vertex attr_reader :explicit_requirements - # @param [DependencyGraph] graph see {#graph} + # @return [Boolean] whether the vertex is considered a root vertex + attr_accessor :root + alias_method :root?, :root + # @param [String] name see {#name} # @param [Object] payload see {#payload} - def initialize(graph, name, payload) - @graph = graph + def initialize(name, payload) @name = name @payload = payload @explicit_requirements = [] + @outgoing_edges = [] + @incoming_edges = [] end # @return [Array] all of the requirements that required # this vertex def requirements - incoming_edges.map(&:requirements).flatten + explicit_requirements + incoming_edges.map(&:requirement) + explicit_requirements end # @return [Array] the edges of {#graph} that have `self` as their # {Edge#origin} - def outgoing_edges - graph.edges.select { |e| e.origin.shallow_eql?(self) } - end + attr_accessor :outgoing_edges # @return [Array] the edges of {#graph} that have `self` as their # {Edge#destination} - def incoming_edges - graph.edges.select { |e| e.destination.shallow_eql?(self) } - end + attr_accessor :incoming_edges - # @return [Set] the vertices of {#graph} that have an edge with + # @return [Array] the vertices of {#graph} that have an edge with # `self` as their {Edge#destination} def predecessors - incoming_edges.map(&:origin).to_set + incoming_edges.map(&:origin) + end + + # @return [Array] the vertices of {#graph} where `self` is a + # {#descendent?} + def recursive_predecessors + vertices = predecessors + vertices += vertices.map(&:recursive_predecessors).flatten(1) + vertices.uniq! + vertices end - # @return [Set] the vertices of {#graph} that have an edge with + # @return [Array] the vertices of {#graph} that have an edge with # `self` as their {Edge#origin} def successors - outgoing_edges.map(&:destination).to_set + outgoing_edges.map(&:destination) end - # @return [Set] the vertices of {#graph} where `self` is an + # @return [Array] the vertices of {#graph} where `self` is an # {#ancestor?} def recursive_successors - successors + successors.map(&:recursive_successors).reduce(Set.new, &:+) + vertices = successors + vertices += vertices.map(&:recursive_successors).flatten(1) + vertices.uniq! + vertices end # @return [String] a string suitable for debugging @@ -226,7 +237,7 @@ module Gem::Resolver::Molinillo # by a recursive traversal of each {Vertex#successors} def ==(other) shallow_eql?(other) && - successors == other.successors + successors.to_set == other.successors.to_set end # @return [Boolean] whether the two vertices are equal, determined @@ -248,7 +259,7 @@ module Gem::Resolver::Molinillo # dependency graph? # @return true iff there is a path following edges within this {#graph} def path_to?(other) - successors.include?(other) || successors.any? { |v| v.path_to?(other) } + equal?(other) || successors.any? { |v| v.path_to?(other) } end alias_method :descendent?, :path_to? @@ -257,7 +268,7 @@ module Gem::Resolver::Molinillo # dependency graph? # @return true iff there is a path following edges within this {#graph} def ancestor?(other) - predecessors.include?(other) || predecessors.any? { |v| v.ancestor?(other) } + other.path_to?(self) end alias_method :is_reachable_from?, :ancestor? diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb index 8568c623e6..73a0daa528 100644 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb +++ b/lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb @@ -1,3 +1,3 @@ module Gem::Resolver::Molinillo - VERSION = '0.3.0' + VERSION = '0.4.0' end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb index 712864495f..cc572b411a 100644 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb +++ b/lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb @@ -12,13 +12,15 @@ module Gem::Resolver::Molinillo # @attr [Object] locked_requirement the relevant locking requirement. # @attr [Array>] 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. Conflict = Struct.new( :requirement, :requirements, :existing, :possibility, :locked_requirement, - :requirement_trees + :requirement_trees, + :activated_by_name ) # @return [SpecificationProvider] the provider that knows about @@ -164,7 +166,7 @@ module Gem::Resolver::Molinillo # @return [DependencyState] the initial state for the resolution 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 } } + 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, {}) @@ -216,7 +218,7 @@ module Gem::Resolver::Molinillo 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) seen && s.requirement != requirement && !s.requirements.include?(requirement) end state && state.requirement @@ -250,21 +252,23 @@ module Gem::Resolver::Molinillo 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) } + 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 + requirement_trees, + Hash[activated.map { |v| [v.name, v.payload] }.select(&:last)] ) end # @return [Array>] The different requirement # trees that led to every requirement for the current spec. def requirement_trees - activated.vertex_named(name).requirements.map { |r| requirement_tree_for(r) } + vertex = activated.vertex_named(name) + vertex.requirements.map { |r| requirement_tree_for(r) } end # @return [Array] the list of requirements that led to @@ -322,7 +326,7 @@ module Gem::Resolver::Molinillo existing_spec = existing_node.payload if requirement_satisfied_by?(requirement, activated, existing_spec) new_requirements = requirements.dup - push_state_for_requirements(new_requirements) + push_state_for_requirements(new_requirements, false) else return if attempt_to_swap_possibility create_conflict @@ -389,17 +393,17 @@ module Gem::Resolver::Molinillo 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 } + nested_dependencies.each { |d| activated.add_child_vertex(name_for(d), nil, [name_for(activated_spec)], d) } - push_state_for_requirements(requirements + nested_dependencies) + push_state_for_requirements(requirements + nested_dependencies, nested_dependencies.size > 0) 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, new_activated = activated.dup) - new_requirements = sort_dependencies(new_requirements.uniq, new_activated, conflicts) + 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) : [] @@ -420,7 +424,7 @@ module Gem::Resolver::Molinillo 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, state.activated) + push_state_for_requirements(state.requirements.dup, false, state.activated) else states.push state end -- cgit v1.2.3