From 8137ec36062d95863e279a5d4cd0566c7d308087 Mon Sep 17 00:00:00 2001
From: Yehuda Katz + Carl Lerche <ykatz+clerche@engineyard.com>
Date: Tue, 28 Jul 2009 14:07:09 -0700
Subject: Speed up the resolver for failing cases

---
 lib/bundler/resolver.rb | 46 ++++++++++++++++++++++++++++++++++------------
 1 file changed, 34 insertions(+), 12 deletions(-)

(limited to 'lib')

diff --git a/lib/bundler/resolver.rb b/lib/bundler/resolver.rb
index 1b0c0ce98d..d1595d393f 100644
--- a/lib/bundler/resolver.rb
+++ b/lib/bundler/resolver.rb
@@ -1,9 +1,21 @@
+# Extending Gem classes to add necessary tracking information
+module Gem
+  class Dependency
+    attr_accessor :required_by
+  end
+  class Specification
+    attr_accessor :required_by
+  end
+end
+
 module Bundler
 
   class Resolver
     def self.resolve(requirements, index = Gem.source_index)
       result = catch(:success) do
-        new(index).resolve(requirements, {})
+        resolver = new(index)
+        resolver.resolve(requirements, {})
+        nil
       end
       result && result.values
     end
@@ -13,7 +25,7 @@ module Bundler
     end
 
     def resolve(reqs, activated)
-      return activated if reqs.empty?
+      throw :success, activated if reqs.empty?
 
       reqs = reqs.sort_by {|dep| @index.search(dep).size }
       activated = activated.dup
@@ -22,20 +34,30 @@ module Bundler
       if existing = activated[current.name]
         if current.version_requirements.satisfied_by?(existing.version)
           resolve(reqs, activated)
+        else
+          throw current.required_by ? current.required_by.name : existing.required_by.name
         end
       else
-        specs = @index.search(current)
-        specs.reverse!
-        specs.each do |spec|
-          activated[spec.name] = spec
-          new_reqs = reqs + spec.dependencies.select do |d|
-            d.type != :development
-          end
-          retval = resolve(new_reqs, activated)
-          throw :success, retval if retval
+        @index.search(current).reverse_each do |spec|
+          resolve_requirement(spec, current, reqs.dup, activated.dup)
         end
-        nil
       end
     end
+
+    def resolve_requirement(spec, requirement, reqs, activated)
+      spec.required_by     = requirement
+      activated[spec.name] = spec
+
+      spec.dependencies.each do |dep|
+        next if dep.type == :development
+        dep.required_by = requirement
+        reqs << dep
+      end
+
+      catch(requirement.name) do
+        resolve(reqs, activated)
+      end
+    end
+
   end
 end
\ No newline at end of file
-- 
cgit v1.2.1