[Resolver] Modify sorting heuristic to check how constraining the requirements areseg-resolver-constrained

This should speed up cases where a simple-looking requirement actually eliminates a lot of the possibilities

1 files changed, 11 insertions, 3 deletions

diff --git a/lib/bundler/resolver.rb b/lib/bundler/resolver.rb
index 3cbe73979e..0673c2af54 100644
--- a/lib/bundler/resolver.rb
+++ b/lib/bundler/resolver.rb
@@ -190,7 +190,6 @@ module Bundler
       @base = base
       @resolver = Molinillo::Resolver.new(self, self)
       @search_for = {}
-      @prereleases_cache = Hash.new { |h,k| h[k] = k.prerelease? }
       @base_dg = Molinillo::DependencyGraph.new
       @base.each { |ls| @base_dg.add_root_vertex ls.name, Dependency.new(ls.name, ls.version) }
     end
@@ -296,14 +295,23 @@ module Bundler
         name = name_for(dependency)
         [
           activated.vertex_named(name).payload ? 0 : 1,
-          @prereleases_cache[dependency.requirement] ? 0 : 1,
-          dependency.requirements_list.size,
+          amount_constrained(dependency),
           conflicts[name] ? 0 : 1,
           activated.vertex_named(name).payload ? 0 : search_for(dependency).count,
         ]
       end
     end
 
+    def amount_constrained(dependency)
+      @amount_constrained ||= {}
+      @amount_constrained[dependency.name] ||= begin
+        base_dep = Dependency.new dependency.name, '>= 0.a'
+        all = search_for(DepProxy.new base_dep, dependency.__platform)
+        return 0 if all.empty?
+        search_for(dependency).size.to_f / all.size.to_f
+      end
+    end
+
     def verify_gemfile_dependencies_are_found!(requirements)
       requirements.each do |requirement|
         next if requirement.name == 'bundler'