EPIC WIN!!!

  After many iterations of writing a gem dependency resolver
  it seems that we have something that works for all cases
  of gem conflicts that we have encountered.

  There are still some issues left to resolve, such as providing
  good error messages when gem dependencies cannot be resolved.

12 files changed, 103 insertions, 462 deletions

diff --git a/lib/bundler/finder.rb b/lib/bundler/finder.rb
index bc4711387e..ab9d95146e 100644
--- a/lib/bundler/finder.rb
+++ b/lib/bundler/finder.rb
@@ -33,7 +33,7 @@ module Bundler
       Bundler.logger.info "Calculating dependencies..."
 
       resolved = Resolver.resolve(dependencies, self)
-      resolved && GemBundle.new(resolved.all_specs)
+      resolved && GemBundle.new(resolved)
     end
 
     # Fetches the index from the remote source
diff --git a/lib/bundler/manifest.rb b/lib/bundler/manifest.rb
index 31d69f8ae1..7d765ac31e 100644
--- a/lib/bundler/manifest.rb
+++ b/lib/bundler/manifest.rb
@@ -39,7 +39,7 @@ module Bundler
       deps     = deps.select { |d| d.in?(environment) } if environment
       deps     = deps.map { |d| d.to_gem_dependency }
       index    = Gem::SourceIndex.from_gems_in(@gem_path.join("specifications"))
-      Resolver.resolve(deps, index).all_specs
+      Resolver.resolve(deps, index)
     end
     alias gems gems_for
 
diff --git a/lib/bundler/resolver.rb b/lib/bundler/resolver.rb
index 1ec89e53c4..1b0c0ce98d 100644
--- a/lib/bundler/resolver.rb
+++ b/lib/bundler/resolver.rb
@@ -1,19 +1,41 @@
-require 'bundler/resolver/inspect'
-require 'bundler/resolver/search'
-require 'bundler/resolver/engine'
-require 'bundler/resolver/stack'
-require 'bundler/resolver/state'
-
 module Bundler
-  module Resolver
-    def self.resolve(deps, source_index = Gem.source_index, logger = nil)
-      unless logger
-        logger = Logger.new($stderr)
-        logger.datetime_format = ""
-        logger.level = ENV["GEM_RESOLVER_DEBUG"] ? Logger::DEBUG : Logger::ERROR
+
+  class Resolver
+    def self.resolve(requirements, index = Gem.source_index)
+      result = catch(:success) do
+        new(index).resolve(requirements, {})
       end
+      result && result.values
+    end
+
+    def initialize(index)
+      @index = index
+    end
+
+    def resolve(reqs, activated)
+      return activated if reqs.empty?
 
-      Engine.resolve(deps, source_index, logger)
+      reqs = reqs.sort_by {|dep| @index.search(dep).size }
+      activated = activated.dup
+      current   = reqs.shift
+
+      if existing = activated[current.name]
+        if current.version_requirements.satisfied_by?(existing.version)
+          resolve(reqs, activated)
+        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
+        end
+        nil
+      end
     end
   end
 end
\ No newline at end of file
diff --git a/lib/bundler/resolver/builders.rb b/lib/bundler/resolver/builders.rb
deleted file mode 100644
index 2b7b48211c..0000000000
--- a/lib/bundler/resolver/builders.rb
+++ /dev/null
@@ -1,61 +0,0 @@
-module Bundler
-  module Resolver
-    module Builders
-      def build_index(&block)
-        index = Gem::SourceIndex.new
-        IndexBuilder.run(index, &block) if block_given?
-        index
-      end
-
-      def build_spec(name, version, &block)
-        spec = Gem::Specification.new
-        spec.instance_variable_set(:@name, name)
-        spec.instance_variable_set(:@version, Gem::Version.new(version))
-        DepBuilder.run(spec, &block) if block_given?
-        spec
-      end
-
-      def build_dep(name, requirements, type = :runtime)
-        Gem::Dependency.new(name, requirements, type)
-      end
-
-      class IndexBuilder
-        include Builders
-
-        def self.run(index, &block)
-          new(index).run(&block)
-        end
-
-        def initialize(index)
-          @index = index
-        end
-
-        def run(&block)
-          instance_eval(&block)
-        end
-
-        def add_spec(*args, &block)
-          @index.add_spec(build_spec(*args, &block))
-        end
-      end
-
-      class DepBuilder
-        def self.run(spec, &block)
-          new(spec).run(&block)
-        end
-
-        def initialize(spec)
-          @spec = spec
-        end
-
-        def run(&block)
-          instance_eval(&block)
-        end
-
-        def runtime(name, requirements)
-          @spec.add_runtime_dependency(name, requirements)
-        end
-      end
-    end
-  end
-end
\ No newline at end of file
diff --git a/lib/bundler/resolver/engine.rb b/lib/bundler/resolver/engine.rb
deleted file mode 100644
index 6412aefca8..0000000000
--- a/lib/bundler/resolver/engine.rb
+++ /dev/null
@@ -1,40 +0,0 @@
-module Bundler
-  module Resolver
-    class ClosedSet < Set
-    end
-
-    class Engine
-      include Search, Inspect
-
-      def self.resolve(deps, source_index, logger)
-        new(deps, source_index, logger).resolve
-      end
-
-      def initialize(deps, source_index, logger)
-        @deps, @source_index, @logger = deps, source_index, logger
-        logger.debug "searching for #{gem_resolver_inspect(@deps)}"
-      end
-      attr_reader :deps, :source_index, :logger, :solution
-
-      def resolve
-        @deps = @deps.sort_by { |dep| @source_index.search(dep).size }
-
-        state = State.initial(self, [], Stack.new, Stack.new([[[], @deps.dup]]))
-        if solution = search(state)
-          logger.info "got the solution with #{solution.all_specs.size} specs"
-          solution.dump(Logger::INFO)
-          solution
-        end
-      end
-
-      def open
-        @open ||= []
-      end
-
-      def closed
-        @closed ||= ClosedSet.new
-      end
-    end
-  end
-
-end
\ No newline at end of file
diff --git a/lib/bundler/resolver/inspect.rb b/lib/bundler/resolver/inspect.rb
deleted file mode 100644
index 59640aa5f3..0000000000
--- a/lib/bundler/resolver/inspect.rb
+++ /dev/null
@@ -1,24 +0,0 @@
-module Bundler
-  module Resolver
-    module Inspect
-      def gem_resolver_inspect(o)
-        case o
-        when Gem::Specification
-          "#<Spec: #{o.full_name}>"
-        when Array
-          '[' + o.map {|x| gem_resolver_inspect(x)}.join(", ") + ']'
-        when Set
-          gem_resolver_inspect(o.to_a)
-        when Hash
-          '{' + o.map {|k,v| "#{gem_resolver_inspect(k)} => #{gem_resolver_inspect(v)}"}.join(", ") + '}'
-        when Stack
-          o.gem_resolver_inspect
-        else
-          o.inspect
-        end
-      end
-
-      module_function :gem_resolver_inspect
-    end
-  end
-end
\ No newline at end of file
diff --git a/lib/bundler/resolver/search.rb b/lib/bundler/resolver/search.rb
deleted file mode 100644
index 34102ff04c..0000000000
--- a/lib/bundler/resolver/search.rb
+++ /dev/null
@@ -1,71 +0,0 @@
-module Bundler
-  module Resolver
-    module Search
-      def search(initial, max_depth = (1.0 / 0.0))
-        if initial.goal_met?
-          return initial
-        end
-
-        open << initial
-
-        while open.any?
-          current = open.pop
-          closed << current
-
-          new = []
-          current.each_possibility do |attempt|
-            unless closed.include?(attempt)
-              if attempt.goal_met?
-                return attempt
-              elsif attempt.depth < max_depth
-                new << attempt
-              end
-            end
-          end
-          new.reverse.each do |state|
-            open << state
-          end
-        end
-
-        nil
-      end
-
-      def open
-        raise "implement #open in #{self.class}"
-      end
-
-      def closed
-        raise "implement #closed in #{self.class}"
-      end
-
-      module Node
-        def self.included(base)
-          base.extend(ClassMethods)
-        end
-
-        module ClassMethods
-          def initial(*data)
-            new(0, *data)
-          end
-        end
-
-        def initialize(depth)
-          @depth = depth
-        end
-        attr_reader :depth
-
-        def child(*data)
-          self.class.new(@depth + 1, *data)
-        end
-
-        def each_possibility
-          raise "implement #each_possibility on #{self.class}"
-        end
-
-        def goal_met?
-          raise "implement #goal_met? on #{self.class}"
-        end
-      end
-    end
-  end
-end
\ No newline at end of file
diff --git a/lib/bundler/resolver/stack.rb b/lib/bundler/resolver/stack.rb
deleted file mode 100644
index 6e1ac67e1f..0000000000
--- a/lib/bundler/resolver/stack.rb
+++ /dev/null
@@ -1,72 +0,0 @@
-module Bundler
-  module Resolver
-    class Stack
-      def initialize(initial = [])
-        @data = []
-        initial.each do |(path,value)|
-          self[path] = value
-        end
-      end
-
-      def last
-        @data.last
-      end
-
-      def []=(path, value)
-        raise ArgumentError, "#{path.inspect} already has a value" if key?(path)
-        @data << [path.dup, value]
-      end
-
-      def [](path)
-        if key?(path)
-          _, value = @data.find do |(k,v)|
-            k == path
-          end
-          value
-        else
-          raise "No value for #{path.inspect}"
-        end
-      end
-
-      def key?(path)
-        @data.any? do |(k,v)|
-          k == path
-        end
-      end
-
-      def each
-        @data.each do |(k,v)|
-          yield k, v
-        end
-      end
-
-      def map
-        @data.map do |(k,v)|
-          yield k, v
-        end
-      end
-
-      def each_value
-        @data.each do |(k,v)|
-          yield v
-        end
-      end
-
-      def dup
-        self.class.new(@data.dup)
-      end
-
-      def to_s
-        @data.to_s
-      end
-
-      def inspect
-        @data.inspect
-      end
-
-      def gem_resolver_inspect
-        Inspect.gem_resolver_inspect(@data)
-      end
-    end
-  end
-end
\ No newline at end of file
diff --git a/lib/bundler/resolver/state.rb b/lib/bundler/resolver/state.rb
deleted file mode 100644
index f13ecbbee7..0000000000
--- a/lib/bundler/resolver/state.rb
+++ /dev/null
@@ -1,172 +0,0 @@
-module Bundler
-  module Resolver
-    class State
-      include Search::Node, Inspect
-
-      def initialize(depth, engine, path, spec_stack, dep_stack)
-        super(depth)
-        @engine, @path, @spec_stack, @dep_stack = engine, path, spec_stack, dep_stack
-      end
-      attr_reader :path
-
-      def logger
-        @engine.logger
-      end
-
-      def goal_met?
-        logger.info "checking if goal is met"
-        dump
-        no_duplicates?
-        all_deps.all? do |dep|
-          dependency_satisfied?(dep)
-        end
-      end
-
-      def no_duplicates?
-        names = []
-        all_specs.each do |s|
-          if names.include?(s.name)
-            raise "somehow got duplicates for #{s.name}"
-          end
-          names << s.name
-        end
-      end
-
-      def dependency_satisfied?(dep)
-        all_specs.any? do |spec|
-          spec.satisfies_requirement?(dep)
-        end
-      end
-
-      def each_possibility(&block)
-        index, dep = remaining_deps.first
-        if dep
-          logger.warn "working on #{dep} for #{spec_name}"
-          handle_dep(index, dep, &block)
-        else
-          logger.warn "no dependencies left for #{spec_name}"
-          jump_to_parent(&block)
-        end
-      end
-
-      def handle_dep(index, dep)
-        specs = @engine.source_index.search(dep)
-
-        specs.reverse.each do |s|
-          logger.info "attempting with spec: #{s.full_name}"
-          new_path = @path + [index]
-          new_spec_stack = @spec_stack.dup
-          new_dep_stack = @dep_stack.dup
-
-          new_spec_stack[new_path] = s
-          new_dep_stack[new_path] = s.runtime_dependencies.sort_by do |dep|
-            @engine.source_index.search(dep).size
-          end
-          yield child(@engine, new_path, new_spec_stack, new_dep_stack)
-        end
-      end
-
-      def jump_to_parent
-        if @path.empty?
-          dump
-          logger.warn "at the end"
-          return
-        end
-
-        logger.info "jumping to parent for #{spec_name}"
-        new_path = @path[0..-2]
-        new_spec_stack = @spec_stack.dup
-        new_dep_stack = @dep_stack.dup
-
-        yield child(@engine, new_path, new_spec_stack, new_dep_stack)
-      end
-
-      def remaining_deps
-        remaining_deps_for(@path)
-      end
-
-      def remaining_deps_for(path)
-        no_duplicates?
-        remaining = []
-        @dep_stack[path].each_with_index do |dep,i|
-          remaining << [i, dep] unless all_specs.find {|s| s.name == dep.name}
-        end
-        remaining
-      end
-
-      def deps
-        @dep_stack[@path]
-      end
-
-      def spec
-        @spec_stack[@path]
-      end
-
-      def spec_name
-        @path.empty? ? "<top>" : spec.full_name
-      end
-
-      def all_deps
-        all_deps = Set.new
-        @dep_stack.each_value do |deps|
-          all_deps.merge(deps)
-        end
-        all_deps.to_a
-      end
-
-      def all_specs
-        @spec_stack.map do |path,spec|
-          spec
-        end
-      end
-
-      def dump(level = Logger::DEBUG)
-        logger.add level, "v" * 80
-        logger.add level, "path: #{@path.inspect}"
-        logger.add level, "deps: (#{deps.size})"
-        deps.map do |dep|
-          logger.add level, gem_resolver_inspect(dep)
-        end
-        logger.add level, "remaining_deps: (#{remaining_deps.size})"
-        remaining_deps.each do |dep|
-          logger.add level, gem_resolver_inspect(dep)
-        end
-        logger.add level, "dep_stack: "
-        @dep_stack.each do |path,deps|
-          logger.add level, "#{path.inspect} (#{deps.size})"
-          deps.each do |dep|
-            logger.add level, "-> #{gem_resolver_inspect(dep)}"
-          end
-        end
-        logger.add level, "spec_stack: "
-        @spec_stack.each do |path,spec|
-          logger.add level, "#{path.inspect}: #{gem_resolver_inspect(spec)}"
-        end
-        logger.add level, "^" * 80
-      end
-
-      def to_dot
-        io = StringIO.new
-        io.puts 'digraph deps {'
-        io.puts '  fontname = "Courier";'
-        io.puts '  mincross = 4.0;'
-        io.puts '  ratio = "auto";'
-        dump_to_dot(io, "<top>", [])
-        io.puts '}'
-        io.string
-      end
-
-      def dump_to_dot(io, name, path)
-        @dep_stack[path].each_with_index do |dep,i|
-          new_path = path + [i]
-          spec_name = all_specs.find {|x| x.name == dep.name}.full_name
-          io.puts '  "%s" -> "%s";' % [name, dep.to_s]
-          io.puts '  "%s" -> "%s";' % [dep.to_s, spec_name]
-          if @spec_stack.key?(new_path)
-            dump_to_dot(io, spec_name, new_path)
-          end
-        end
-      end
-    end
-  end
-end
\ No newline at end of file
diff --git a/spec/builders.rb b/spec/builders.rb
new file mode 100644
index 0000000000..f13a9594f8
--- /dev/null
+++ b/spec/builders.rb
@@ -0,0 +1,59 @@
+module Spec
+  module Builders
+    def build_index(&block)
+      index = Gem::SourceIndex.new
+      IndexBuilder.run(index, &block) if block_given?
+      index
+    end
+
+    def build_spec(name, version, &block)
+      spec = Gem::Specification.new
+      spec.instance_variable_set(:@name, name)
+      spec.instance_variable_set(:@version, Gem::Version.new(version))
+      DepBuilder.run(spec, &block) if block_given?
+      spec
+    end
+
+    def build_dep(name, requirements, type = :runtime)
+      Gem::Dependency.new(name, requirements, type)
+    end
+
+    class IndexBuilder
+      include Builders
+
+      def self.run(index, &block)
+        new(index).run(&block)
+      end
+
+      def initialize(index)
+        @index = index
+      end
+
+      def run(&block)
+        instance_eval(&block)
+      end
+
+      def add_spec(*args, &block)
+        @index.add_spec(build_spec(*args, &block))
+      end
+    end
+
+    class DepBuilder
+      def self.run(spec, &block)
+        new(spec).run(&block)
+      end
+
+      def initialize(spec)
+        @spec = spec
+      end
+
+      def run(&block)
+        instance_eval(&block)
+      end
+
+      def runtime(name, requirements)
+        @spec.add_runtime_dependency(name, requirements)
+      end
+    end
+  end
+end
\ No newline at end of file
diff --git a/spec/resolver/engine_spec.rb b/spec/resolver/engine_spec.rb
index e519a0e61c..e7d0f1953e 100644
--- a/spec/resolver/engine_spec.rb
+++ b/spec/resolver/engine_spec.rb
@@ -11,7 +11,7 @@ describe "Resolving specs" do
     ]
 
     solution = Bundler::Resolver.resolve(deps, index)
-    solution.all_specs.should match_gems(
+    solution.should match_gems(
       "bar" => ["2.0.0"]
     )
   end
@@ -34,7 +34,7 @@ describe "Resolving specs" do
     ]
 
     solution = Bundler::Resolver.resolve(deps, index)
-    solution.all_specs.should match_gems(
+    solution.should match_gems(
       "activemerchant" => ["1.4.1"],
       "action_pack" => ["2.3.2"],
       "activesupport" => ["2.3.2"]
@@ -54,7 +54,7 @@ describe "Resolving specs" do
     ]
 
     solution = Bundler::Resolver.resolve(deps, index)
-    solution.all_specs.should match_gems(
+    solution.should match_gems(
       "bar" => ["2.0.0"],
       "foo" => ["1.1"]
     )
@@ -78,7 +78,7 @@ describe "Resolving specs" do
     ]
 
     solution = Bundler::Resolver.resolve(deps, index)
-    solution.all_specs.should match_gems(
+    solution.should match_gems(
       "bar" => ["1.0"],
       "foo" => ["1.0"]
     )
@@ -92,7 +92,7 @@ describe "Resolving specs" do
     ]
 
     solution = Bundler::Resolver.resolve(deps, index)
-    solution.all_specs.should match_gems(
+    solution.should match_gems(
       "merb-core"=>["1.0.7.1"],
       "rake"=>["0.8.7"],
       "thor"=>["0.9.9"],
diff --git a/spec/spec_helper.rb b/spec/spec_helper.rb
index 902900ff48..b0b49ecbcd 100644
--- a/spec/spec_helper.rb
+++ b/spec/spec_helper.rb
@@ -1,7 +1,7 @@
 $:.unshift File.join(File.dirname(__FILE__), '..', 'lib')
 $:.push File.join(File.dirname(__FILE__))
 require "bundler"
-require "bundler/resolver/builders"
+require "builders"
 require "matchers"
 require "pathname"
 require "pp"
@@ -81,7 +81,7 @@ module Spec
 end
 
 Spec::Runner.configure do |config|
-  config.include Bundler::Resolver::Builders
+  config.include Spec::Builders
   config.include Spec::Matchers
   config.include Spec::Helpers