Merge rubygems-2.6.11

  This version fixed regression of rubygems-2.6.10.
  https://github.com/rubygems/rubygems/pull/1856

  See details of changelogs for 2.6.11 release:
  https://github.com/rubygems/rubygems/blob/adfcf40502716080bd9cdfdd2e43bd4296872784/History.txt#L3

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@57998 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

12 files changed, 102 insertions, 33 deletions

diff --git a/lib/rubygems.rb b/lib/rubygems.rb
index 0c698b2813..5cd1a4c47a 100644
--- a/lib/rubygems.rb
+++ b/lib/rubygems.rb
@@ -10,7 +10,7 @@ require 'rbconfig'
 require 'thread'
 
 module Gem
-  VERSION = "2.6.10"
+  VERSION = "2.6.11"
 end
 
 # Must be first since it unloads the prelude from 1.9.2
diff --git a/lib/rubygems/request_set/lockfile/tokenizer.rb b/lib/rubygems/request_set/lockfile/tokenizer.rb
index c9f1fac75b..a758743dda 100644
--- a/lib/rubygems/request_set/lockfile/tokenizer.rb
+++ b/lib/rubygems/request_set/lockfile/tokenizer.rb
@@ -1,5 +1,4 @@
 # frozen_string_literal: true
-require 'strscan'
 require 'rubygems/request_set/lockfile/parser'
 
 class Gem::RequestSet::Lockfile::Tokenizer
@@ -58,6 +57,7 @@ class Gem::RequestSet::Lockfile::Tokenizer
   private
 
   def tokenize input
+    require 'strscan'
     s = StringScanner.new input
 
     until s.eos? do
diff --git a/lib/rubygems/resolver.rb b/lib/rubygems/resolver.rb
index 50a547e1be..a7b11179c8 100644
--- a/lib/rubygems/resolver.rb
+++ b/lib/rubygems/resolver.rb
@@ -4,9 +4,6 @@ require 'rubygems/exceptions'
 require 'rubygems/util'
 require 'rubygems/util/list'
 
-require 'uri'
-require 'net/http'
-
 ##
 # Given a set of Gem::Dependency objects as +needed+ and a way to query the
 # set of available specs via +set+, calculates a set of ActivationRequest
@@ -256,6 +253,44 @@ class Gem::Resolver
     @soft_missing
   end
 
+  def sort_dependencies(dependencies, activated, conflicts)
+    dependencies.sort_by do |dependency|
+      name = name_for(dependency)
+      [
+        activated.vertex_named(name).payload ? 0 : 1,
+        amount_constrained(dependency),
+        conflicts[name] ? 0 : 1,
+        activated.vertex_named(name).payload ? 0 : search_for(dependency).count,
+      ]
+    end
+  end
+
+  SINGLE_POSSIBILITY_CONSTRAINT_PENALTY = 1_000_000
+  private_constant :SINGLE_POSSIBILITY_CONSTRAINT_PENALTY if defined?(private_constant)
+
+  # returns an integer \in (-\infty, 0]
+  # a number closer to 0 means the dependency is less constraining
+  #
+  # dependencies w/ 0 or 1 possibilities (ignoring version requirements)
+  # are given very negative values, so they _always_ sort first,
+  # before dependencies that are unconstrained
+  def amount_constrained(dependency)
+    @amount_constrained ||= {}
+    @amount_constrained[dependency.name] ||= begin
+      name_dependency = Gem::Dependency.new(dependency.name)
+      dependency_request_for_name = Gem::Resolver::DependencyRequest.new(name_dependency, dependency.requester)
+      all = @set.find_all(dependency_request_for_name).size
+
+      if all <= 1
+        all - SINGLE_POSSIBILITY_CONSTRAINT_PENALTY
+      else
+        search = search_for(dependency).size
+        search - all
+      end
+    end
+  end
+  private :amount_constrained
+
 end
 
 ##
diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb
index 139165102e..b413e3ab6a 100644
--- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb
@@ -98,18 +98,27 @@ module Gem::Resolver::Molinillo
       "#{self.class}:#{vertices.values.inspect}"
     end
 
+    # @param [Hash] options options for dot output.
     # @return [String] Returns a dot format representation of the graph
-    def to_dot
+    def to_dot(options = {})
+      edge_label = options.delete(:edge_label)
+      raise ArgumentError, "Unknown options: #{options.keys}" unless options.empty?
+
       dot_vertices = []
       dot_edges = []
       vertices.each do |n, v|
         dot_vertices << "  #{n} [label=\"{#{n}|#{v.payload}}\"]"
         v.outgoing_edges.each do |e|
-          dot_edges << "  #{e.origin.name} -> #{e.destination.name} [label=\"#{e.requirement}\"]"
+          label = edge_label ? edge_label.call(e) : e.requirement
+          dot_edges << "  #{e.origin.name} -> #{e.destination.name} [label=#{label.to_s.dump}]"
         end
       end
+
+      dot_vertices.uniq!
       dot_vertices.sort!
+      dot_edges.uniq!
       dot_edges.sort!
+
       dot = dot_vertices.unshift('digraph G {').push('') + dot_edges.push('}')
       dot.join("\n")
     end
@@ -123,7 +132,8 @@ module Gem::Resolver::Molinillo
       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
+        return false unless vertex.payload == other_vertex.payload
+        return false unless other_vertex.successors.to_set == vertex.successors.to_set
       end
     end
 
diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb
index b052e3a38e..e994e59d05 100644
--- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb
@@ -23,8 +23,8 @@ module Gem::Resolver::Molinillo
       # (see Action#down)
       def down(graph)
         edge = make_edge(graph)
-        edge.origin.outgoing_edges.delete(edge)
-        edge.destination.incoming_edges.delete(edge)
+        delete_first(edge.origin.outgoing_edges, edge)
+        delete_first(edge.destination.incoming_edges, edge)
       end
 
       # @!group AddEdgeNoCircular
@@ -53,6 +53,13 @@ module Gem::Resolver::Molinillo
         @destination = destination
         @requirement = requirement
       end
+
+      private
+
+      def delete_first(array, item)
+        return unless index = array.index(item)
+        array.delete_at(index)
+      end
     end
   end
 end
diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/vertex.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/vertex.rb
index b5a0688a32..cebd9cafdd 100644
--- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/vertex.rb
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/vertex.rb
@@ -10,7 +10,7 @@ module Gem::Resolver::Molinillo
       # @return [Object] the payload the vertex holds
       attr_accessor :payload
 
-      # @return [Arrary<Object>] the explicit requirements that required
+      # @return [Array<Object>] the explicit requirements that required
       #   this vertex
       attr_reader :explicit_requirements
 
diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb
index dfddafe993..c5b5bd729f 100644
--- a/lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb
@@ -1,5 +1,5 @@
 # frozen_string_literal: true
 module Gem::Resolver::Molinillo
   # The version of Gem::Resolver::Molinillo.
-  VERSION = '0.5.5'.freeze
+  VERSION = '0.5.7'.freeze
 end
diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/modules/ui.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/modules/ui.rb
index 540b5b809c..dbc4e000e4 100644
--- a/lib/rubygems/resolver/molinillo/lib/molinillo/modules/ui.rb
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo/modules/ui.rb
@@ -48,7 +48,7 @@ module Gem::Resolver::Molinillo
       if debug?
         debug_info = yield
         debug_info = debug_info.inspect unless debug_info.is_a?(String)
-        output.puts debug_info.split("\n").map { |s| '  ' * depth + s }
+        output.puts debug_info.split("\n").map { |s| ' ' * depth + s }
       end
     end
 
diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb
index ea497ddcaf..73a4242157 100644
--- a/lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb
@@ -52,7 +52,7 @@ module Gem::Resolver::Molinillo
         @base = base
         @states = []
         @iteration_counter = 0
-        @parent_of = {}
+        @parents_of = Hash.new { |h, k| h[k] = [] }
       end
 
       # Resolves the {#original_requested} dependencies into a full dependency
@@ -105,7 +105,7 @@ module Gem::Resolver::Molinillo
 
         handle_missing_or_push_dependency_state(initial_state)
 
-        debug { "Starting resolution (#{@started_at})" }
+        debug { "Starting resolution (#{@started_at})\nUser-requested dependencies: #{original_requested}" }
         resolver_ui.before_resolution
       end
 
@@ -178,14 +178,14 @@ module Gem::Resolver::Molinillo
       # Unwinds the states stack because a conflict has been encountered
       # @return [void]
       def unwind_for_conflict
-        debug(depth) { "Unwinding for conflict: #{requirement}" }
+        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
-          @parent_of.reject! { |_, i| i >= index }
+          @parents_of.each { |_, a| a.reject! { |i| i >= index } }
         end
       end
 
@@ -214,7 +214,7 @@ module Gem::Resolver::Molinillo
       #   to the list of requirements.
       def parent_of(requirement)
         return unless requirement
-        return unless index = @parent_of[requirement]
+        return unless index = @parents_of[requirement].last
         return unless parent_state = @states[index]
         parent_state.requirement
       end
@@ -356,16 +356,25 @@ module Gem::Resolver::Molinillo
       # Ensures there are no orphaned successors to the given {vertex}.
       # @param [DependencyGraph::Vertex] vertex the vertex to fix up.
       # @return [void]
-      def fixup_swapped_children(vertex)
+      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|
-          @parent_of[outgoing_edge.requirement] = states.size - 1
+          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| @parent_of.delete(r) }
+            succ.requirements.each { |r| @parents_of.delete(r) }
 
             removed_names = activated.detach_vertex_named(succ.name).map(&:name)
             requirements.delete_if do |r|
@@ -373,9 +382,14 @@ module Gem::Resolver::Molinillo
               # so it's safe to delete only based upon name here
               removed_names.include?(name_for(r))
             end
-          elsif !matching_deps.include?(outgoing_edge.requirement)
+          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(outgoing_edge.requirement)
+            requirements.delete(requirement)
           end
         end
       end
@@ -395,13 +409,18 @@ module Gem::Resolver::Molinillo
       # @return [Boolean] whether the current spec is satisfied as a new
       # possibility.
       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)
-        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
+
+        locked_spec_satisfied
       end
 
       # @param [String] requirement_name the spec name to search for
@@ -417,7 +436,7 @@ module Gem::Resolver::Molinillo
       # @return [void]
       def activate_spec
         conflicts.delete(name)
-        debug(depth) { 'Activated ' + name + ' at ' + possibility.to_s }
+        debug(depth) { "Activated #{name} at #{possibility}" }
         activated.set_payload(name, possibility)
         require_nested_dependencies_for(possibility)
       end
@@ -432,7 +451,8 @@ module Gem::Resolver::Molinillo
         nested_dependencies.each do |d|
           activated.add_child_vertex(name_for(d), nil, [name_for(activated_spec)], d)
           parent_index = states.size - 1
-          @parent_of[d] ||= parent_index
+          parents = @parents_of[d]
+          parents << parent_index if parents.empty?
         end
 
         push_state_for_requirements(requirements + nested_dependencies, !nested_dependencies.empty?)
diff --git a/lib/rubygems/resolver/set.rb b/lib/rubygems/resolver/set.rb
index cc12633d46..11704d5c4c 100644
--- a/lib/rubygems/resolver/set.rb
+++ b/lib/rubygems/resolver/set.rb
@@ -21,6 +21,7 @@ class Gem::Resolver::Set
   attr_accessor :prerelease
 
   def initialize # :nodoc:
+    require 'uri'
     @prerelease = false
     @remote     = true
     @errors     = []
@@ -54,4 +55,3 @@ class Gem::Resolver::Set
   end
 
 end
-
diff --git a/lib/rubygems/specification.rb b/lib/rubygems/specification.rb
index a2f289d162..5bbaec3911 100644
--- a/lib/rubygems/specification.rb
+++ b/lib/rubygems/specification.rb
@@ -1128,9 +1128,6 @@ class Gem::Specification < Gem::BasicSpecification
     native = {}
 
     specs.reverse_each do |spec|
-      unless spec
-        raise Gem::Exception, "unexpectedly spec is nil: #{specs}"
-      end
       next if spec.version.prerelease? unless prerelease
 
       native[spec.name] = spec.version if spec.platform == Gem::Platform::RUBY
diff --git a/lib/rubygems/test_case.rb b/lib/rubygems/test_case.rb
index f7ae97cd8d..86b68e1efb 100644
--- a/lib/rubygems/test_case.rb
+++ b/lib/rubygems/test_case.rb
@@ -1334,7 +1334,7 @@ Also, a list:
   end
 
   ##
-  # create_gemspec creates gem specification in given +direcotry+ or '.'
+  # create_gemspec creates gem specification in given +directory+ or '.'
   # for the given +name+ and +version+.
   #
   # Yields the +specification+ to the block, if given