diff options
Diffstat (limited to 'lib')
-rw-r--r-- | lib/rubygems/basic_specification.rb | 4 | ||||
-rw-r--r-- | lib/rubygems/request.rb | 5 | ||||
-rw-r--r-- | lib/rubygems/resolver.rb | 2 | ||||
-rw-r--r-- | lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb | 153 | ||||
-rw-r--r-- | lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb | 2 | ||||
-rw-r--r-- | lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb | 28 | ||||
-rw-r--r-- | lib/rubygems/specification.rb | 3 | ||||
-rw-r--r-- | lib/rubygems/util/licenses.rb | 22 |
8 files changed, 129 insertions, 90 deletions
diff --git a/lib/rubygems/basic_specification.rb b/lib/rubygems/basic_specification.rb index fb0e67ea72..3e411f33bc 100644 --- a/lib/rubygems/basic_specification.rb +++ b/lib/rubygems/basic_specification.rb @@ -171,8 +171,8 @@ class Gem::BasicSpecification begin fullpath = nil suffixes = Gem.suffixes - full_require_paths.find do |dir| - suffixes.find do |suf| + suffixes.find do |suf| + full_require_paths.find do |dir| File.file?(fullpath = "#{dir}/#{path}#{suf}") end end ? fullpath : nil diff --git a/lib/rubygems/request.rb b/lib/rubygems/request.rb index 702769c500..b1d041d8ea 100644 --- a/lib/rubygems/request.rb +++ b/lib/rubygems/request.rb @@ -185,6 +185,10 @@ class Gem::Request bad_response = true retry + rescue Net::HTTPFatalError + verbose "fatal error" + + raise Gem::RemoteFetcher::FetchError.new('fatal error', @uri) # HACK work around EOFError bug in Net::HTTP # NOTE Errno::ECONNABORTED raised a lot on Windows, and make impossible # to install gems. @@ -241,4 +245,3 @@ end require 'rubygems/request/http_pool' require 'rubygems/request/https_pool' require 'rubygems/request/connection_pools' - diff --git a/lib/rubygems/resolver.rb b/lib/rubygems/resolver.rb index 4c2974e553..dcd33ce10d 100644 --- a/lib/rubygems/resolver.rb +++ b/lib/rubygems/resolver.rb @@ -187,7 +187,7 @@ class Gem::Resolver def resolve locking_dg = Molinillo::DependencyGraph.new - Molinillo::Resolver.new(self, self).resolve(@needed.map { |d| DependencyRequest.new d, nil }, locking_dg).tsort.map(&:payload) + Molinillo::Resolver.new(self, self).resolve(@needed.map { |d| DependencyRequest.new d, nil }, locking_dg).tsort.map(&:payload).compact rescue Molinillo::VersionConflict => e conflict = e.conflicts.values.first raise Gem::DependencyResolutionError, Conflict.new(conflict.requirement_trees.first.first, conflict.existing, conflict.requirement) 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<Edge>] 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<Object>] 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<Edge>] 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<Edge>] 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<Vertex>] the vertices of {#graph} that have an edge with + # @return [Array<Vertex>] 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<Vertex>] 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<Vertex>] the vertices of {#graph} that have an edge with + # @return [Array<Vertex>] 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<Vertex>] the vertices of {#graph} where `self` is an + # @return [Array<Vertex>] 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<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. 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<Array<Object>>] 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<Object>] 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 diff --git a/lib/rubygems/specification.rb b/lib/rubygems/specification.rb index 750cc1056f..1be285e4ef 100644 --- a/lib/rubygems/specification.rb +++ b/lib/rubygems/specification.rb @@ -2593,6 +2593,7 @@ class Gem::Specification < Gem::BasicSpecification trail.push(self) begin dependencies.each do |dep| + next unless dep.runtime? dep.to_specs.reverse_each do |dep_spec| next if visited.has_key?(dep_spec) visited[dep_spec] = true @@ -2744,7 +2745,7 @@ class Gem::Specification < Gem::BasicSpecification "each license must be 64 characters or less" end - if !Gem::Licenses::IDENTIFIERS.include?(license) && !license.eql?(Gem::Licenses::NONSTANDARD) + if !Gem::Licenses.match?(license) warning <<-warning WARNING: license value '#{license}' is invalid. Use a license identifier from http://spdx.org/licenses or '#{Gem::Licenses::NONSTANDARD}' for a nonstandard license. diff --git a/lib/rubygems/util/licenses.rb b/lib/rubygems/util/licenses.rb index 280d148625..a15b556c3e 100644 --- a/lib/rubygems/util/licenses.rb +++ b/lib/rubygems/util/licenses.rb @@ -4,7 +4,8 @@ class Gem::Licenses # Software Package Data Exchange (SPDX) standard open-source software # license identifiers IDENTIFIERS = %w( - AAL + 0BSD + AAL ADSL AFL-1.1 AFL-1.2 @@ -89,6 +90,7 @@ class Gem::Licenses CECILL-1.0 CECILL-1.1 CECILL-2.0 + CECILL-2.1 CECILL-B CECILL-C CNRI-Jython @@ -102,6 +104,7 @@ class Gem::Licenses ClArtistic Condor-1.1 Crossword + CrystalStacker Cube D-FSL-1.0 DOC @@ -146,6 +149,7 @@ class Gem::Licenses Imlib2 Intel Intel-ACPI + Interbase-1.0 JSON JasPer-2.0 LGPL-2.0 @@ -254,6 +258,7 @@ class Gem::Licenses SPL-1.0 SWL Saxpath + Sendmail SimPL-2.0 Sleepycat Spencer-86 @@ -306,4 +311,19 @@ class Gem::Licenses xpp zlib-acknowledgement ).freeze + + REGEXP = %r{ + \A + ( + #{Regexp.union(IDENTIFIERS)} + \+? + (\s WITH \s .+)? + | #{NONSTANDARD} + ) + \Z + }ox.freeze + + def self.match?(license) + !REGEXP.match(license).nil? + end end |