Auto merge of #6128 - greysteil:prioritise-requested-gems, r=segiddins

Prioritise explicitly requested gems in dependency resolution sort order

### What was the end-user problem that led to this PR?

Calling `bundle update github-pages` on https://github.com/Floppy/cv was causing a downgrade in the `github-pages` version.

### What was your diagnosis of the problem?

The `Bundler::Resolver#sort_dependencies` method didn't have any logic to prioritise explicitly requested gems. Therefore, where two rival resolutions were possible (in this case one with `activesupport` at 5.1.4 and `github-pages` at 24, and one with `github-pages` at 166 and `activesupport` at 4.2.9), Bundler didn't always correct the most desirable resolution.

### What is your fix for the problem, implemented in this PR?

My fix is to explicitly prioritise requested gems in the dependency sort order during resolution.

### Why did you choose this fix out of the possible options?

I chose this fix because it's intuitive.

4 files changed, 36 insertions, 3 deletions

diff --git a/lib/bundler/installer.rb b/lib/bundler/installer.rb
index baf5333479..71f79ab8c9 100644
--- a/lib/bundler/installer.rb
+++ b/lib/bundler/installer.rb
@@ -52,7 +52,7 @@ module Bundler
     #
     # Fourthly, Bundler checks if the Gemfile.lock exists, and if so
     # then proceeds to set up a definition based on the Gemfile and the Gemfile.lock.
-    # During this step Bundler will also download infomrmation about any new gems
+    # During this step Bundler will also download information about any new gems
     # that are not in the Gemfile.lock and resolve any dependencies if needed.
     #
     # Fifthly, Bundler resolves the dependencies either through a cache of gems or by remote.
diff --git a/lib/bundler/resolver.rb b/lib/bundler/resolver.rb
index 965a1d55ad..f75c669534 100644
--- a/lib/bundler/resolver.rb
+++ b/lib/bundler/resolver.rb
@@ -205,12 +205,14 @@ module Bundler
       dependencies.sort_by do |dependency|
         dependency.all_sources = relevant_sources_for_vertex(activated.vertex_named(dependency.name))
         name = name_for(dependency)
+        vertex = activated.vertex_named(name)
         [
           @base_dg.vertex_named(name) ? 0 : 1,
-          activated.vertex_named(name).payload ? 0 : 1,
+          vertex.payload ? 0 : 1,
+          vertex.root? ? 0 : 1,
           amount_constrained(dependency),
           conflicts[name] ? 0 : 1,
-          activated.vertex_named(name).payload ? 0 : search_for(dependency).count,
+          vertex.payload ? 0 : search_for(dependency).count,
           self.class.platform_sort_key(dependency.__platform),
         ]
       end
diff --git a/spec/resolver/basic_spec.rb b/spec/resolver/basic_spec.rb
index 4db119d6f1..d5658824ba 100644
--- a/spec/resolver/basic_spec.rb
+++ b/spec/resolver/basic_spec.rb
@@ -35,6 +35,13 @@ RSpec.describe "Resolving" do
     should_resolve_as %w[berkshelf-2.0.7 chef-10.26 chef_app-1.0.0 json-1.7.7]
   end
 
+  it "prefers expicitly requested dependencies when resolving an index which would otherwise be ambiguous" do
+    @index = an_ambiguous_index
+    dep "a"
+    dep "b"
+    should_resolve_as %w[a-1.0.0 b-2.0.0 c-1.0.0 d-1.0.0]
+  end
+
   it "resolves a index with root level conflict on child" do
     @index = a_index_with_root_conflict_on_child
     dep "i18n", "~> 0.4"
diff --git a/spec/support/indexes.rb b/spec/support/indexes.rb
index ba10716114..05605195b1 100644
--- a/spec/support/indexes.rb
+++ b/spec/support/indexes.rb
@@ -377,5 +377,29 @@ module Spec
         end
       end
     end
+
+    def an_ambiguous_index
+      build_index do
+        gem("a", "1.0.0") do
+          dep "c", ">= 0"
+        end
+
+        gem("b", %w[0.5.0 1.0.0])
+
+        gem("b", "2.0.0") do
+          dep "c", "< 2.0.0"
+        end
+
+        gem("c", "1.0.0") do
+          dep "d", "1.0.0"
+        end
+
+        gem("c", "2.0.0") do
+          dep "d", "2.0.0"
+        end
+
+        gem("d", %w[1.0.0 2.0.0])
+      end
+    end
   end
 end