Use Molinillo for dependency resolution

Merge remote-tracking branch 'segiddins/seg-molinillo' into molinillo

19 files changed, 1167 insertions, 396 deletions

diff --git a/Rakefile b/Rakefile
index d4d08da058..19c9cf37ca 100644
--- a/Rakefile
+++ b/Rakefile
@@ -27,6 +27,29 @@ module Rake
   end
 end
 
+namespace :molinillo do
+  task :namespace do
+    files = Dir.glob('lib/bundler/vendor/Molinillo*/**/*.rb')
+    sh "sed -i.bak 's/Molinillo/Bundler::Molinillo/g' #{files.join(' ')}"
+    sh "rm #{files.join('.bak ')}.bak"
+  end
+
+  task :clean do
+    files = Dir.glob('lib/bundler/vendor/Molinillo*/*', File::FNM_DOTMATCH).reject { |f| %(. .. lib).include? f.split('/').last }
+    puts files
+    sh "rm -r #{files.join(' ')}"
+  end
+
+  task :update, [:tag] => [] do |t, args|
+    tag = args[:tag]
+    Dir.chdir 'lib/bundler/vendor' do
+      `curl -L https://github.com/CocoaPods/molinillo/archive/#{tag}.tar.gz | tar -xz`
+    end
+    Rake::Task['molinillo:namespace'].invoke
+    Rake::Task['molinillo:clean'].invoke
+  end
+end
+
 namespace :spec do
   desc "Ensure spec dependencies are installed"
   task :deps do
diff --git a/lib/bundler/dep_proxy.rb b/lib/bundler/dep_proxy.rb
index bc810dc58c..ef98a35128 100644
--- a/lib/bundler/dep_proxy.rb
+++ b/lib/bundler/dep_proxy.rb
@@ -1,10 +1,10 @@
 module Bundler
   class DepProxy
 
-    attr_reader :required_by, :__platform, :dep
+    attr_reader :__platform, :dep
 
     def initialize(dep, platform)
-      @dep, @__platform, @required_by = dep, platform, []
+      @dep, @__platform = dep, platform
     end
 
     def hash
diff --git a/lib/bundler/resolver.rb b/lib/bundler/resolver.rb
index 218a69969d..df2c515cc5 100644
--- a/lib/bundler/resolver.rb
+++ b/lib/bundler/resolver.rb
@@ -1,27 +1,73 @@
 require 'set'
+
 # This is the latest iteration of the gem dependency resolving algorithm. As of now,
 # it can resolve (as a success or failure) any set of gem dependencies we throw at it
 # in a reasonable amount of time. The most iterations I've seen it take is about 150.
 # The actual implementation of the algorithm is not as good as it could be yet, but that
 # can come later.
 
-# Extending Gem classes to add necessary tracking information
-module Gem
-  class Specification
-    def required_by
-      @required_by ||= []
-    end
-  end
-  class Dependency
-    def required_by
-      @required_by ||= []
-    end
-  end
-end
-
 module Bundler
   class Resolver
 
+    require 'bundler/vendored_molinillo'
+
+    class Molinillo::VersionConflict
+      def clean_req(req)
+        if req.to_s.include?(">= 0")
+          req.to_s.gsub(/ \(.*?\)$/, '')
+        else
+          req.to_s.gsub(/\, (runtime|development)\)$/, ')')
+        end
+      end
+
+      def message
+        conflicts.values.flatten.reduce('') do |o, conflict|
+          o << %(Bundler could not find compatible versions for gem "#{conflict.requirement.name}":\n)
+          if conflict.locked_requirement
+            o << %(  In snapshot (Gemfile.lock):\n)
+            o << %(    #{clean_req conflict.locked_requirement}\n)
+            o << %(\n)
+          end
+          o << %(  In Gemfile:\n)
+          o << conflict.requirement_trees.map do |tree|
+            t = ''
+            depth = 2
+            tree.each do |req|
+              t << '  ' * depth << %(#{clean_req req})
+              t << %( depends on) unless tree[-1] == req
+              t << %(\n)
+              depth += 1
+            end
+            t
+          end.join("\n")
+
+          if conflict.requirement.name == 'bundler'
+            o << %(\n  Current Bundler version:\n    bundler (#{Bundler::VERSION}))
+            other_bundler_required = !conflict.requirement.requirement.satisfied_by?(Gem::Version.new Bundler::VERSION)
+          end
+
+          if conflict.requirement.name == "bundler" && other_bundler_required
+            o << "\n"
+            o << "This Gemfile requires a different version of Bundler.\n"
+            o << "Perhaps you need to update Bundler by running `gem install bundler`?\n"
+          end
+          if conflict.locked_requirement
+            o << "\n"
+            o << %(Running `bundle update` will rebuild your snapshot from scratch, using only\n)
+            o << %(the gems in your Gemfile, which may resolve the conflict.\n)
+          elsif !conflict.existing
+            if conflict.requirement_trees.first.size > 1
+              o << "Could not find gem '#{clean_req(conflict.requirement)}', which is required by "
+              o << "gem '#{clean_req(conflict.requirement_trees.first[-2])}', in any of the sources."
+            else
+              o << "Could not find gem '#{clean_req(conflict.requirement)} in any of the sources\n"
+            end
+          end
+          o
+        end
+      end
+    end
+
     ALL = Bundler::Dependency::PLATFORM_MAP.values.uniq.freeze
 
     class SpecGroup < Array
@@ -65,8 +111,10 @@ module Bundler
 
       def activate_platform(platform)
         unless @activated.include?(platform)
-          @activated << platform
-          return __dependencies[platform] || []
+          if for?(platform)
+            @activated << platform
+            return __dependencies[platform] || []
+          end
         end
         []
       end
@@ -91,6 +139,14 @@ module Bundler
         "#{name} (#{version})"
       end
 
+      def dependencies_for_activated_platforms
+        @activated.map { |p| __dependencies[p] }.flatten
+      end
+
+      def platforms_for_dependency_named(dependency)
+        __dependencies.select { |p, deps| deps.map(&:name).include? dependency }.keys
+      end
+
     private
 
       def __dependencies
@@ -110,8 +166,6 @@ module Bundler
       end
     end
 
-    attr_reader :errors, :started_at, :iteration_rate, :iteration_counter
-
     # Figures out the best possible configuration of gems that satisfies
     # the list of passed dependencies and any child dependencies without
     # causing any gem activation errors.
@@ -123,277 +177,85 @@ module Bundler
     # <GemBundle>,nil:: If the list of dependencies can be resolved, a
     #   collection of gemspecs is returned. Otherwise, nil is returned.
     def self.resolve(requirements, index, source_requirements = {}, base = [])
-      Bundler.ui.info "Resolving dependencies...", false
       base = SpecSet.new(base) unless base.is_a?(SpecSet)
       resolver = new(index, source_requirements, base)
       result = resolver.start(requirements)
-      Bundler.ui.info "" # new line now that dots are done
       SpecSet.new(result)
-    rescue => e
-      Bundler.ui.info "" # new line before the error
-      raise e
-    end
-
-    def initialize(index, source_requirements, base)
-      @errors               = {}
-      @base                 = base
-      @index                = index
-      @deps_for             = {}
-      @missing_gems         = Hash.new(0)
-      @prereleases_cache    = Hash.new { |h,k| h[k] = k.prerelease? }
-      @source_requirements  = source_requirements
-      @iteration_counter    = 0
-      @started_at           = Time.now
     end
 
-    def debug
-      if ENV['DEBUG_RESOLVER']
-        debug_info = yield
-        debug_info = debug_info.inspect unless debug_info.is_a?(String)
-        $stderr.puts debug_info
-      end
-    end
 
-    def successify(activated)
-      activated.values.map { |s| s.to_specs }.flatten.compact
+    def initialize(index, source_requirements, base)
+      @index = index
+      @source_requirements = source_requirements
+      @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
 
-    def start(reqs)
-      activated = {}
-      @gems_size = Hash[reqs.map { |r| [r, gems_size(r)] }]
-
-      resolve(reqs, activated)
+    def start(requirements)
+      verify_gemfile_dependencies_are_found!(requirements)
+      dg = @resolver.resolve(requirements, @base_dg)
+      dg.map(&:payload).map(&:to_specs).flatten
+    rescue Molinillo::VersionConflict => e
+      raise VersionConflict.new(e.conflicts.keys.uniq, e.message)
+    rescue Molinillo::CircularDependencyError => e
+      names = e.dependencies.sort_by(&:name).map { |d| "gem '#{d.name}'"}
+      raise CyclicDependencyError, "Your Gemfile requires gems that depend" \
+        " on each other, creating an infinite loop. Please remove" \
+        " #{names.count > 1 ? 'either ' : '' }#{names.join(' or ')}" \
+        " and try again."
     end
 
-    class State < Struct.new(:reqs, :activated, :requirement, :possibles, :depth, :conflicts)
-      def name
-        requirement.name
-      end
-    end
+    include Molinillo::UI
 
-    def handle_conflict(current, states, existing=nil)
-      until current.nil? && existing.nil?
-        current_state = find_state(current, states)
-        existing_state = find_state(existing, states)
-        return current if state_any?(current_state)
-        return existing if state_any?(existing_state)
-        existing = existing.required_by.last if existing
-        current = current.required_by.last if current
+    # Conveys debug information to the user.
+    #
+    # @param [Integer] depth the current depth of the resolution process.
+    # @return [void]
+    def debug(depth = 0)
+      if debug?
+        debug_info = yield
+        debug_info = debug_info.inspect unless debug_info.is_a?(String)
+        STDERR.puts debug_info.split("\n").map { |s| '  ' * depth + s }
       end
     end
 
-    def state_any?(state)
-      state && state.possibles.any?
-    end
-
-    def find_state(current, states)
-      states.detect { |i| current && current.name == i.name }
-    end
-
-    def other_possible?(conflict, states)
-      return unless conflict
-      state = states.detect { |i| i.name == conflict.name }
-      state && state.possibles.any?
+    def debug?
+      ENV['DEBUG_RESOLVER'] || ENV['DEBUG_RESOLVER_TREE']
     end
 
-    def find_conflict_state(conflict, states)
-      return unless conflict
-      until states.empty? do
-        state = states.pop
-        return state if conflict.name == state.name
-      end
+    def before_resolution
+      Bundler.ui.info 'Resolving dependencies...', false
     end
 
-    def activate_gem(reqs, activated, requirement, current)
-      requirement.required_by.replace current.required_by
-      requirement.required_by << current
-      activated[requirement.name] = requirement
-
-      debug { "  Activating: #{requirement.name} (#{requirement.version})" }
-      debug { requirement.required_by.map { |d| "    * #{d.name} (#{d.requirement})" }.join("\n") }
-
-      dependencies = requirement.activate_platform(current.__platform)
-
-      debug { "    Dependencies"}
-      dependencies.each do |dep|
-        next if dep.type == :development
-        dep.required_by.replace(current.required_by)
-        dep.required_by << current
-        @gems_size[dep] ||= gems_size(dep)
-        reqs << dep
-      end
+    def after_resolution
+      Bundler.ui.info ''
     end
 
-    def resolve_for_conflict(state)
-      raise version_conflict if state.nil? || state.possibles.empty?
-      reqs, activated, depth, conflicts = state.reqs.dup, state.activated.dup, state.depth, state.conflicts.dup
-      requirement = state.requirement
-      possible = state.possibles.pop
-
-      activate_gem(reqs, activated, possible, requirement)
-
-      return reqs, activated, depth, conflicts
+    def indicate_progress
+      Bundler.ui.info '.', false
     end
 
-    def resolve_conflict(current, states)
-      # Find the state where the conflict has occurred
-      state = find_conflict_state(current, states)
-
-      debug { "    -> Going to: #{current.name} state" } if current
-
-      # Resolve the conflicts by rewinding the state
-      # when the conflicted gem was activated
-      reqs, activated, depth, conflicts = resolve_for_conflict(state)
+    private
 
-      # Keep the state around if it still has other possibilities
-      states << state unless state.possibles.empty?
-      clear_search_cache
+    include Molinillo::SpecificationProvider
 
-      return reqs, activated, depth, conflicts
+    def dependencies_for(specification)
+      specification.dependencies_for_activated_platforms
     end
 
-    def resolve(reqs, activated)
-      states = []
-      depth = 0
-      conflicts = Set.new
-
-      until reqs.empty?
-
-        indicate_progress
-
-        debug { print "\e[2J\e[f" ; "==== Iterating ====\n\n" }
-
-        reqs = reqs.sort_by do |a|
-          [ activated[a.name] ? 0 : 1,
-            @prereleases_cache[a.requirement] ? 0 : 1,
-            @errors[a.name]   ? 0 : 1,
-            activated[a.name] ? 0 : @gems_size[a] ]
+    def search_for(dependency)
+      platform = dependency.__platform
+      dependency = dependency.dep unless dependency.is_a? Gem::Dependency
+      search = @search_for[dependency] ||= begin
+        index = @source_requirements[dependency.name] || @index
+        results = index.search(dependency, @base[dependency.name])
+        if vertex = @base_dg.vertex_named(dependency.name)
+          locked_requirement = vertex.payload.requirement
         end
-
-        debug { "Activated:\n" + activated.values.map {|a| "  #{a}" }.join("\n") }
-        debug { "Requirements:\n" + reqs.map {|r| "  #{r}"}.join("\n") }
-
-        current = reqs.shift
-
-        $stderr.puts "#{' ' * depth}#{current}" if ENV['DEBUG_RESOLVER_TREE']
-
-        debug { "Attempting:\n  #{current}"}
-
-        existing = activated[current.name]
-
-
-        if existing || current.name == 'bundler'
-          # Force the current
-          if current.name == 'bundler' && !existing
-            existing = search(DepProxy.new(Gem::Dependency.new('bundler', VERSION), Gem::Platform::RUBY)).first
-            raise GemNotFound, %Q{Bundler could not find gem "bundler" (#{VERSION})} unless existing
-            existing.required_by << existing
-            activated['bundler'] = existing
-          end
-
-          if current.requirement.satisfied_by?(existing.version)
-            debug { "    * [SUCCESS] Already activated" }
-            @errors.delete(existing.name)
-            dependencies = existing.activate_platform(current.__platform)
-            reqs.concat dependencies
-
-            dependencies.each do |dep|
-              next if dep.type == :development
-              @gems_size[dep] ||= gems_size(dep)
-            end
-
-            depth += 1
-            next
-          else
-            debug { "    * [FAIL] Already activated" }
-            @errors[existing.name] = [existing, current]
-
-            conflicts << current.name
-
-            parent = current.required_by.last
-            if existing.respond_to?(:required_by)
-              parent = handle_conflict(current, states, existing.required_by[-2]) unless other_possible?(parent, states)
-            else
-              parent = handle_conflict(current, states) unless other_possible?(parent, states)
-            end
-
-            if parent.nil? && !conflicts.empty?
-              parent = states.reverse.detect { |i| conflicts.include?(i.name) && state_any?(i)}
-            end
-
-            raise version_conflict if parent.nil? || parent.name == 'bundler'
-
-            reqs, activated, depth, conflicts = resolve_conflict(parent, states)
-          end
-        else
-          matching_versions = search(current)
-
-          # If we found no versions that match the current requirement
-          if matching_versions.empty?
-            # If this is a top-level Gemfile requirement
-            if current.required_by.empty?
-              if base = @base[current.name] and !base.empty?
-                version = base.first.version
-                message = "You have requested:\n" \
-                  "  #{current.name} #{current.requirement}\n\n" \
-                  "The bundle currently has #{current.name} locked at #{version}.\n" \
-                  "Try running `bundle update #{current.name}`"
-              elsif current.source
-                name = current.name
-                versions = @source_requirements[name][name].map { |s| s.version }
-                message  = "Could not find gem '#{current}' in #{current.source}.\n"
-                if versions.any?
-                  message << "Source contains '#{name}' at: #{versions.join(', ')}"
-                else
-                  message << "Source does not contain any versions of '#{current}'"
-                end
-              else
-                message = "Could not find gem '#{current}' "
-                if @index.source_types.include?(Bundler::Source::Rubygems)
-                  message << "in any of the gem sources listed in your Gemfile."
-                else
-                  message << "in the gems available on this machine."
-                end
-              end
-              raise GemNotFound, message
-              # This is not a top-level Gemfile requirement
-            else
-              @errors[current.name] = [nil, current]
-              parent = handle_conflict(current, states)
-              reqs, activated, depth = resolve_conflict(parent, states)
-              next
-            end
-          end
-
-          state = State.new(reqs.dup, activated.dup, current, matching_versions, depth, conflicts)
-          states << state
-          requirement = state.possibles.pop
-          activate_gem(reqs, activated, requirement, current)
-        end
-      end
-      successify(activated)
-    end
-
-    def gems_size(dep)
-      search(dep).size
-    end
-
-    def clear_search_cache
-      @deps_for = {}
-    end
-
-    def search(dep)
-      if base = @base[dep.name] and base.any?
-        reqs = [dep.requirement.as_list, base.first.version.to_s].flatten.compact
-        d = Gem::Dependency.new(base.first.name, *reqs)
-      else
-        d = dep.dep
-      end
-
-      @deps_for[d.hash] ||= begin
-        index = @source_requirements[d.name] || @index
-        results = index.search(d, @base[d.name])
-
         if results.any?
           version = results.first.version
           nested  = [[]]
@@ -404,132 +266,74 @@ module Bundler
             end
             nested.last << spec
           end
-          deps = nested.map{|a| SpecGroup.new(a) }.select{|sg| sg.for?(dep.__platform) }
+          groups = nested.map { |a| SpecGroup.new(a) }
+          !locked_requirement ? groups : groups.select { |sg| locked_requirement.satisfied_by? sg.version }
         else
-          deps = []
+          []
         end
       end
+      search.select { |sg| sg.for?(platform) }.each { |sg| sg.activate_platform(platform) }
     end
 
-    def clean_req(req)
-      if req.to_s.include?(">= 0")
-        req.to_s.gsub(/ \(.*?\)$/, '')
-      else
-        req.to_s.gsub(/\, (runtime|development)\)$/, ')')
-      end
+    def name_for(dependency)
+      dependency.name
     end
 
-    def version_conflict
-      VersionConflict.new(errors.keys, error_message)
+    def name_for_explicit_dependency_source
+      'Gemfile'
     end
 
-    # For a given conflicted requirement, print out what exactly went wrong
-    def gem_message(requirement, required_by=[])
-      m = ""
-
-      # A requirement that is required by itself is actually in the Gemfile, and does
-      # not "depend on" itself
-      if requirement.required_by.first && requirement.required_by.first.name != requirement.name
-        dependency_tree(m, required_by)
-        m << "#{clean_req(requirement)}\n"
-      else
-        m << "    #{clean_req(requirement)}\n"
-      end
-      m << "\n"
+    def name_for_locking_dependency_source
+      'Gemfile.lock'
     end
 
-    def dependency_tree(m, requirements)
-      requirements.each_with_index do |i, j|
-        m << "    " << ("  " * j)
-        m << "#{clean_req(i)}"
-        m << " depends on\n"
-      end
-      m << "    " << ("  " * requirements.size)
+    def requirement_satisfied_by?(requirement, activated, spec)
+      requirement.matches_spec?(spec)
     end
 
-    def error_message
-      errors.inject("") do |o, (conflict, (origin, requirement))|
-
-        # origin is the SpecSet of specs from the Gemfile that is conflicted with
-        if origin
-
-          o << %{Bundler could not find compatible versions for gem "#{origin.name}":\n}
-          o << "  In Gemfile:\n"
-
-          required_by = requirement.required_by
-          o << gem_message(requirement, required_by)
-
-          # If the origin is "bundler", the conflict is us
-          if origin.name == "bundler"
-            o << "  Current Bundler version:\n"
-            other_bundler_required = !requirement.requirement.satisfied_by?(origin.version)
-          # If the origin is a LockfileParser, it does not respond_to :required_by
-          elsif !origin.respond_to?(:required_by) || !(origin.required_by.first)
-            o << "  In snapshot (Gemfile.lock):\n"
-          end
-
-          required_by = origin.required_by[0..-2]
-          o << gem_message(origin, required_by)
-
-          # If the bundle wants a newer bundler than the running bundler, explain
-          if origin.name == "bundler" && other_bundler_required
-            o << "This Gemfile requires a different version of Bundler.\n"
-            o << "Perhaps you need to update Bundler by running `gem install bundler`?"
-          end
-
-        # origin is nil if the required gem and version cannot be found in any of
-        # the specified sources
-        else
-
-          # if the gem cannot be found because of a version conflict between lockfile and gemfile,
-          # print a useful error that suggests running `bundle update`, which may fix things
-          #
-          # @base is a SpecSet of the gems in the lockfile
-          # conflict is the name of the gem that could not be found
-          if locked = @base[conflict].first
-            o << "Bundler could not find compatible versions for gem #{conflict.inspect}:\n"
-            o << "  In snapshot (Gemfile.lock):\n"
-            o << "    #{clean_req(locked)}\n\n"
-
-            o << "  In Gemfile:\n"
-
-            required_by = requirement.required_by
-            o << gem_message(requirement, required_by)
-            o << "Running `bundle update` will rebuild your snapshot from scratch, using only\n"
-            o << "the gems in your Gemfile, which may resolve the conflict.\n"
+    def sort_dependencies(dependencies, activated, conflicts)
+      dependencies.sort_by do |dependency|
+        name = name_for(dependency)
+        [
+          activated.vertex_named(name).payload ? 0 : 1,
+          @prereleases_cache[dependency.requirement] ? 0 : 1,
+          conflicts[name] ? 0 : 1,
+          activated.vertex_named(name).payload ? 0 : search_for(dependency).count,
+        ]
+      end
+    end
 
-          # the rest of the time, the gem cannot be found because it does not exist in the known sources
+    def verify_gemfile_dependencies_are_found!(requirements)
+      requirements.each do |requirement|
+        next if requirement.name == 'bundler'
+        if search_for(requirement).empty?
+          if base = @base[requirement.name] and !base.empty?
+            version = base.first.version
+            message = "You have requested:\n" \
+              "  #{requirement.name} #{requirement.requirement}\n\n" \
+              "The bundle currently has #{requirement.name} locked at #{version}.\n" \
+              "Try running `bundle update #{requirement.name}`"
+          elsif requirement.source
+            name = requirement.name
+            versions = @source_requirements[name][name].map { |s| s.version }
+            message  = "Could not find gem '#{requirement}' in #{requirement.source}.\n"
+            if versions.any?
+              message << "Source contains '#{name}' at: #{versions.join(', ')}"
+            else
+              message << "Source does not contain any versions of '#{requirement}'"
+            end
           else
-            if requirement.required_by.first
-              o << "Could not find gem '#{clean_req(requirement)}', which is required by "
-              o << "gem '#{clean_req(requirement.required_by.first)}', in any of the sources."
+            message = "Could not find gem '#{requirement}' "
+            if @index.source_types.include?(Bundler::Source::Rubygems)
+              message << "in any of the gem sources listed in your Gemfile."
             else
-              o << "Could not find gem '#{clean_req(requirement)} in any of the sources\n"
+              message << "in the gems available on this machine."
             end
           end
-
+          raise GemNotFound, message
         end
-        o
       end
     end
 
-    private
-
-    # Indicates progress by writing a '.' every iteration_rate time which is
-    # approximately every second. iteration_rate is calculated in the first
-    # second of resolve running.
-    def indicate_progress
-      @iteration_counter += 1
-
-      if iteration_rate.nil?
-        if ((Time.now - started_at) % 3600).round >= 1
-          @iteration_rate = iteration_counter
-        end
-      else
-        if ((iteration_counter % iteration_rate) == 0)
-          Bundler.ui.info ".", false
-        end
-      end
-    end
   end
 end
diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo.rb
new file mode 100644
index 0000000000..bf740e4848
--- /dev/null
+++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo.rb
@@ -0,0 +1,5 @@
+require 'molinillo/gem_metadata'
+require 'molinillo/errors'
+require 'molinillo/resolver'
+require 'molinillo/modules/ui'
+require 'molinillo/modules/specification_provider'
diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/dependency_graph.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/dependency_graph.rb
new file mode 100644
index 0000000000..6eab86b661
--- /dev/null
+++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/dependency_graph.rb
@@ -0,0 +1,244 @@
+require 'set'
+
+module Bundler::Molinillo
+  # A directed acyclic graph that is tuned to hold named dependencies
+  class DependencyGraph
+    include Enumerable
+
+    def each
+      vertices.values.each { |v| yield v }
+    end
+
+    # A directed edge of a {DependencyGraph}
+    # @attr [Vertex] origin The origin of the directed edge
+    # @attr [Vertex] destination The destination of the directed edge
+    # @attr [Array] requirements The requirements the directed edge represents
+    Edge = Struct.new(:origin, :destination, :requirements)
+
+    # @return [{String => Vertex}] vertices that have no {Vertex#predecessors},
+    #   keyed by by {Vertex#name}
+    attr_reader :root_vertices
+    # @return [{String => Vertex}] the vertices of the dependency graph, keyed
+    #   by {Vertex#name}
+    attr_reader :vertices
+    # @return [Set<Edge>] the edges of the dependency graph
+    attr_reader :edges
+
+    def initialize
+      @vertices = {}
+      @edges = Set.new
+      @root_vertices = {}
+    end
+
+    # Initializes a copy of a {DependencyGraph}, ensuring that all {#vertices}
+    # have the correct {Vertex#graph} set
+    def initialize_copy(other)
+      super
+      @vertices = other.vertices.reduce({}) do |vertices, (name, vertex)|
+        vertices.tap do |hash|
+          hash[name] = vertex.dup.tap { |v| v.graph = self }
+        end
+      end
+      @root_vertices = Hash[vertices.select { |n, _v| other.root_vertices[n] }]
+      @edges = other.edges.map do |edge|
+        Edge.new(
+          vertex_named(edge.origin.name),
+          vertex_named(edge.destination.name),
+          edge.requirements.dup
+        )
+      end
+    end
+
+    # @return [String] a string suitable for debugging
+    def inspect
+      "#{self.class}:#{vertices.values.inspect}"
+    end
+
+    # @return [Boolean] whether the two dependency graphs are equal, determined
+    #   by a recursive traversal of each {#root_vertices} and its
+    #   {Vertex#successors}
+    def ==(other)
+      root_vertices == other.root_vertices
+    end
+
+    # @param [String] name
+    # @param [Object] payload
+    # @param [Array<String>] parent_names
+    # @param [Object] requirement the requirement that is requiring the child
+    # @return [void]
+    def add_child_vertex(name, payload, parent_names, requirement)
+      is_root = parent_names.include?(nil)
+      parent_nodes = parent_names.compact.map { |n| vertex_named(n) }
+      vertex = vertex_named(name) || if is_root
+                                       add_root_vertex(name, payload)
+                                     else
+                                       add_vertex(name, payload)
+                                     end
+      vertex.payload ||= payload
+      parent_nodes.each do |parent_node|
+        add_edge(parent_node, vertex, requirement)
+      end
+      vertex
+    end
+
+    # @param [String] name
+    # @param [Object] payload
+    # @return [Vertex] the vertex that was added to `self`
+    def add_vertex(name, payload)
+      vertex = vertices[name] ||= Vertex.new(self, name, payload)
+      vertex.tap { |v| v.payload = payload }
+    end
+
+    # @param [String] name
+    # @param [Object] payload
+    # @return [Vertex] the vertex that was added to `self`
+    def add_root_vertex(name, payload)
+      add_vertex(name, payload).tap { |v| root_vertices[name] = v }
+    end
+
+    # Detaches the {#vertex_named} `name` {Vertex} from the graph, recursively
+    # removing any non-root vertices that were orphaned in the process
+    # @param [String] name
+    # @return [void]
+    def detach_vertex_named(name)
+      vertex = vertex_named(name)
+      return unless vertex
+      successors = vertex.successors
+      vertices.delete(name)
+      edges.reject! { |e| e.origin == vertex || e.destination == vertex }
+      successors.each { |v| detach_vertex_named(v.name) unless root_vertices[v.name] || v.predecessors.any? }
+    end
+
+    # @param [String] name
+    # @return [Vertex,nil] the vertex with the given name
+    def vertex_named(name)
+      vertices[name]
+    end
+
+    # @param [String] name
+    # @return [Vertex,nil] the root vertex with the given name
+    def root_vertex_named(name)
+      root_vertices[name]
+    end
+
+    # Adds a new {Edge} to the dependency graph
+    # @param [Vertex] origin
+    # @param [Vertex] destination
+    # @param [Object] requirement the requirement that this edge represents
+    # @return [Edge] the added edge
+    def add_edge(origin, destination, requirement)
+      if origin == destination || destination.path_to?(origin)
+        raise CircularDependencyError.new([origin, destination])
+      end
+      Edge.new(origin, destination, [requirement]).tap { |e| edges << e }
+    end
+
+    # A vertex in a {DependencyGraph} that encapsulates a {#name} and a
+    # {#payload}
+    class Vertex
+      # @return [DependencyGraph] the graph this vertex is a node of
+      attr_accessor :graph
+
+      # @return [String] the name of the vertex
+      attr_accessor :name
+
+      # @return [Object] the payload the vertex holds
+      attr_accessor :payload
+
+      # @return [Arrary<Object>] the explicit requirements that required
+      #   this vertex
+      attr_reader :explicit_requirements
+
+      # @param [DependencyGraph] graph see {#graph}
+      # @param [String] name see {#name}
+      # @param [Object] payload see {#payload}
+      def initialize(graph, name, payload)
+        @graph = graph
+        @name = name
+        @payload = payload
+        @explicit_requirements = []
+      end
+
+      # @return [Array<Object>] all of the requirements that required
+      #   this vertex
+      def requirements
+        incoming_edges.map(&:requirements).flatten + explicit_requirements
+      end
+
+      # @return [Array<Edge>] the edges of {#graph} that have `self` as their
+      #   {Edge#origin}
+      def outgoing_edges
+        graph.edges.select { |e| e.origin.shallow_eql?(self) }
+      end
+
+      # @return [Array<Edge>] the edges of {#graph} that have `self` as their
+      #   {Edge#destination}
+      def incoming_edges
+        graph.edges.select { |e| e.destination.shallow_eql?(self) }
+      end
+
+      # @return [Set<Vertex>] the vertices of {#graph} that have an edge with
+      #   `self` as their {Edge#destination}
+      def predecessors
+        incoming_edges.map(&:origin).to_set
+      end
+
+      # @return [Set<Vertex>] the vertices of {#graph} that have an edge with
+      #   `self` as their {Edge#origin}
+      def successors
+        outgoing_edges.map(&:destination).to_set
+      end
+
+      # @return [Set<Vertex>] the vertices of {#graph} where `self` is an
+      #   {#ancestor?}
+      def recursive_successors
+        successors + successors.map(&:recursive_successors).reduce(Set.new, &:+)
+      end
+
+      # @return [String] a string suitable for debugging
+      def inspect
+        "#{self.class}:#{name}(#{payload.inspect})"
+      end
+
+      # @return [Boolean] whether the two vertices are equal, determined
+      #   by a recursive traversal of each {Vertex#successors}
+      def ==(other)
+        shallow_eql?(other) &&
+          successors == other.successors
+      end
+
+      # @return [Boolean] whether the two vertices are equal, determined
+      #   solely by {#name} and {#payload} equality
+      def shallow_eql?(other)
+        other &&
+          name == other.name &&
+          payload == other.payload
+      end
+
+      alias_method :eql?, :==
+
+      # @return [Fixnum] a hash for the vertex based upon its {#name}
+      def hash
+        name.hash
+      end
+
+      # Is there a path from `self` to `other` following edges in the
+      # dependency graph?
+      # @return true iff there is a path following edges within this {#graph}
+      def path_to?(other)
+        successors.include?(other) || successors.any? { |v| v.path_to?(other) }
+      end
+
+      alias_method :descendent?, :path_to?
+
+      # Is there a path from `other` to `self` following edges in the
+      # dependency graph?
+      # @return true iff there is a path following edges within this {#graph}
+      def ancestor?(other)
+        predecessors.include?(other) || predecessors.any? { |v| v.ancestor?(other) }
+      end
+
+      alias_method :is_reachable_from?, :ancestor?
+    end
+  end
+end
diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/errors.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/errors.rb
new file mode 100644
index 0000000000..b828d0c20d
--- /dev/null
+++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/errors.rb
@@ -0,0 +1,69 @@
+module Bundler::Molinillo
+  # An error that occurred during the resolution process
+  class ResolverError < StandardError; end
+
+  # An error caused by searching for a dependency that is completely unknown,
+  # i.e. has no versions available whatsoever.
+  class NoSuchDependencyError < ResolverError
+    # @return [Object] the dependency that could not be found
+    attr_accessor :dependency
+
+    # @return [Array<Object>] the specifications that depended upon {#dependency}
+    attr_accessor :required_by
+
+    # @param [Object] dependency @see {#dependency}
+    # @param [Array<Object>] required_by @see {#required_by}
+    def initialize(dependency, required_by = [])
+      @dependency = dependency
+      @required_by = required_by
+      super()
+    end
+
+    def message
+      sources = required_by.map { |r| "`#{r}`" }.join(' and ')
+      message = "Unable to find a specification for `#{dependency}`"
+      message << " depended upon by #{sources}" unless sources.empty?
+      message
+    end
+  end
+
+  # An error caused by attempting to fulfil a dependency that was circular
+  #
+  # @note This exception will be thrown iff a {Vertex} is added to a
+  #   {DependencyGraph} that has a {DependencyGraph::Vertex#path_to?} an
+  #   existing {DependencyGraph::Vertex}
+  class CircularDependencyError < ResolverError
+    # [Set<Object>] the dependencies responsible for causing the error
+    attr_reader :dependencies
+
+    # @param [Array<DependencyGraph::Vertex>] nodes the nodes in the dependency
+    #   that caused the error
+    def initialize(nodes)
+      super "There is a circular dependency between #{nodes.map(&:name).join(' and ')}"
+      @dependencies = nodes.map(&:payload).to_set
+    end
+  end
+
+  # An error caused by conflicts in version
+  class VersionConflict < ResolverError
+    # @return [{String => Resolution::Conflict}] the conflicts that caused
+    #   resolution to fail
+    attr_reader :conflicts
+
+    # @param [{String => Resolution::Conflict}] conflicts see {#conflicts}
+    def initialize(conflicts)
+      pairs = []
+      conflicts.values.flatten.map(&:requirements).flatten.each do |conflicting|
+        conflicting.each do |source, conflict_requirements|
+          conflict_requirements.each do |c|
+            pairs << [c, source]
+          end
+        end
+      end
+
+      super "Unable to satisfy the following requirements:\n\n" \
+        "#{pairs.map { |r, d| "- `#{r}` required by `#{d}`" }.join("\n")}"
+      @conflicts = conflicts
+    end
+  end
+end
diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/gem_metadata.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/gem_metadata.rb
new file mode 100644
index 0000000000..5305fcfc66
--- /dev/null
+++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/gem_metadata.rb
@@ -0,0 +1,3 @@
+module Bundler::Molinillo
+  VERSION = '0.1.2'
+end
diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/specification_provider.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/specification_provider.rb
new file mode 100644
index 0000000000..79a85e778f
--- /dev/null
+++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/specification_provider.rb
@@ -0,0 +1,90 @@
+module Bundler::Molinillo
+  # Provides information about specifcations and dependencies to the resolver,
+  # allowing the {Resolver} class to remain generic while still providing power
+  # and flexibility.
+  #
+  # This module contains the methods that users of Bundler::Molinillo must to implement,
+  # using knowledge of their own model classes.
+  module SpecificationProvider
+    # Search for the specifications that match the given dependency.
+    # The specifications in the returned array will be considered in reverse
+    # order, so the latest version ought to be last.
+    # @note This method should be 'pure', i.e. the return value should depend
+    #   only on the `dependency` parameter.
+    #
+    # @param [Object] dependency
+    # @return [Array<Object>] the specifications that satisfy the given
+    #   `dependency`.
+    def search_for(dependency)
+      []
+    end
+
+    # Returns the dependencies of `specification`.
+    # @note This method should be 'pure', i.e. the return value should depend
+    #   only on the `specification` parameter.
+    #
+    # @param [Object] specification
+    # @return [Array<Object>] the dependencies that are required by the given
+    #   `specification`.
+    def dependencies_for(specification)
+      []
+    end
+
+    # Determines whether the given `requirement` is satisfied by the given
+    # `spec`, in the context of the current `activated` dependency graph.
+    #
+    # @param [Object] requirement
+    # @param [DependencyGraph] activated the current dependency graph in the
+    #   resolution process.
+    # @param [Object] spec
+    # @return [Boolean] whether `requirement` is satisfied by `spec` in the
+    #   context of the current `activated` dependency graph.
+    def requirement_satisfied_by?(requirement, activated, spec)
+      true
+    end
+
+    # Returns the name for the given `dependency`.
+    # @note This method should be 'pure', i.e. the return value should depend
+    #   only on the `dependency` parameter.
+    #
+    # @param [Object] dependency
+    # @return [String] the name for the given `dependency`.
+    def name_for(dependency)
+      dependency.to_s
+    end
+
+    # @return [String] the name of the source of explicit dependencies, i.e.
+    #   those passed to {Resolver#resolve} directly.
+    def name_for_explicit_dependency_source
+      'user-specified dependency'
+    end
+
+    # @return [String] the name of the source of 'locked' dependencies, i.e.
+    #   those passed to {Resolver#resolve} directly as the `base`
+    def name_for_locking_dependency_source
+      'Lockfile'
+    end
+
+    # Sort dependencies so that the ones that are easiest to resolve are first.
+    # Easiest to resolve is (usually) defined by:
+    #   1) Is this dependency already activated?
+    #   2) How relaxed are the requirements?
+    #   3) Are there any conflicts for this dependency?
+    #   4) How many possibilities are there to satisfy this dependency?
+    #
+    # @param [Array<Object>] dependencies
+    # @param [DependencyGraph] activated the current dependency graph in the
+    #   resolution process.
+    # @param [{String => Array<Conflict>}] conflicts
+    # @return [Array<Object>] a sorted copy of `dependencies`.
+    def sort_dependencies(dependencies, activated, conflicts)
+      dependencies.sort_by do |dependency|
+        name = name_for(dependency)
+        [
+          activated.vertex_named(name).payload ? 0 : 1,
+          conflicts[name] ? 0 : 1,
+        ]
+      end
+    end
+  end
+end
diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/ui.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/ui.rb
new file mode 100644
index 0000000000..097c0264ac
--- /dev/null
+++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/modules/ui.rb
@@ -0,0 +1,63 @@
+module Bundler::Molinillo
+  # Conveys information about the resolution process to a user.
+  module UI
+    # The {IO} object that should be used to print output. `STDOUT`, by default.
+    #
+    # @return [IO]
+    def output
+      STDOUT
+    end
+
+    # Called roughly every {#progress_rate}, this method should convey progress
+    # to the user.
+    #
+    # @return [void]
+    def indicate_progress
+      output.print '.' unless debug?
+    end
+
+    # How often progress should be conveyed to the user via
+    # {#indicate_progress}, in seconds. A third of a second, by default.
+    #
+    # @return [Float]
+    def progress_rate
+      0.33
+    end
+
+    # Called before resolution begins.
+    #
+    # @return [void]
+    def before_resolution
+      output.print 'Resolving dependencies...'
+    end
+
+    # Called after resolution ends (either successfully or with an error).
+    # By default, prints a newline.
+    #
+    # @return [void]
+    def after_resolution
+      output.puts
+    end
+
+    # Conveys debug information to the user.
+    #
+    # @param [Integer] depth the current depth of the resolution process.
+    # @return [void]
+    def debug(depth = 0)
+      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 }
+      end
+    end
+
+    # Whether or not debug messages should be printed.
+    # By default, whether or not the `MOLINILLO_DEBUG` environment variable is
+    # set.
+    #
+    # @return [Boolean]
+    def debug?
+      @debug_mode ||= ENV['MOLINILLO_DEBUG']
+    end
+  end
+end
diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolution.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolution.rb
new file mode 100644
index 0000000000..13cb379936
--- /dev/null
+++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolution.rb
@@ -0,0 +1,400 @@
+module Bundler::Molinillo
+  class Resolver
+    # A specific resolution from a given {Resolver}
+    class Resolution
+      # A conflict that the resolution process encountered
+      # @attr [Object] requirement the requirement that immediately led to the conflict
+      # @attr [{String,Nil=>[Object]}] requirements the requirements that caused the conflict
+      # @attr [Object, nil] existing the existing spec that was in conflict with
+      #   the {#possibility}
+      # @attr [Object] possibility the spec that was unable to be activated due
+      #   to a conflict
+      # @attr [Object] locked_requirement the relevant locking requirement.
+      # @attr [Array<Array<Object>>] requirement_trees the different requirement
+      #   trees that led to every requirement for the conflicting name.
+      Conflict = Struct.new(
+        :requirement,
+        :requirements,
+        :existing,
+        :possibility,
+        :locked_requirement,
+        :requirement_trees
+      )
+
+      # @return [SpecificationProvider] the provider that knows about
+      #   dependencies, requirements, specifications, versions, etc.
+      attr_reader :specification_provider
+
+      # @return [UI] the UI that knows how to communicate feedback about the
+      #   resolution process back to the user
+      attr_reader :resolver_ui
+
+      # @return [DependencyGraph] the base dependency graph to which
+      #   dependencies should be 'locked'
+      attr_reader :base
+
+      # @return [Array] the dependencies that were explicitly required
+      attr_reader :original_requested
+
+      # @param [SpecificationProvider] specification_provider
+      #   see {#specification_provider}
+      # @param [UI] resolver_ui see {#resolver_ui}
+      # @param [Array] requested see {#original_requested}
+      # @param [DependencyGraph] base see {#base}
+      def initialize(specification_provider, resolver_ui, requested, base)
+        @specification_provider = specification_provider
+        @resolver_ui = resolver_ui
+        @original_requested = requested
+        @base = base
+        @states = []
+        @iteration_counter = 0
+      end
+
+      # Resolves the {#original_requested} dependencies into a full dependency
+      #   graph
+      # @raise [ResolverError] if successful resolution is impossible
+      # @return [DependencyGraph] the dependency graph of successfully resolved
+      #   dependencies
+      def resolve
+        start_resolution
+
+        while state
+          break unless state.requirements.any? || state.requirement
+          indicate_progress
+          if state.respond_to?(:pop_possibility_state) # DependencyState
+            debug(depth) { "Creating possibility state for #{requirement} (#{possibilities.count} remaining)" }
+            state.pop_possibility_state.tap { |s| states.push(s) if s }
+          end
+          process_topmost_state
+        end
+
+        activated.freeze
+      ensure
+        end_resolution
+      end
+
+      private
+
+      # Sets up the resolution process
+      # @return [void]
+      def start_resolution
+        @started_at = Time.now
+
+        states.push(initial_state)
+
+        debug { "Starting resolution (#{@started_at})" }
+        resolver_ui.before_resolution
+      end
+
+      # Ends the resolution process
+      # @return [void]
+      def end_resolution
+        resolver_ui.after_resolution
+        debug do
+          "Finished resolution (#{@iteration_counter} steps) " \
+          "(Took #{(ended_at = Time.now) - @started_at} seconds) (#{ended_at})"
+        end
+        debug { 'Unactivated: ' + Hash[activated.vertices.reject { |_n, v| v.payload }].keys.join(', ') } if state
+        debug { 'Activated: ' + Hash[activated.vertices.select { |_n, v| v.payload }].keys.join(', ') } if state
+      end
+
+      require 'molinillo/state'
+      require 'molinillo/modules/specification_provider'
+
+      # @return [Integer] the number of resolver iterations in between calls to
+      #   {#resolver_ui}'s {UI#indicate_progress} method
+      attr_accessor :iteration_rate
+
+      # @return [Time] the time at which resolution began
+      attr_accessor :started_at
+
+      # @return [Array<ResolutionState>] the stack of states for the resolution
+      attr_accessor :states
+
+      ResolutionState.new.members.each do |member|
+        define_method member do |*args, &block|
+          state.send(member, *args, &block)
+        end
+      end
+
+      SpecificationProvider.instance_methods(false).each do |instance_method|
+        define_method instance_method do |*args, &block|
+          begin
+            specification_provider.send(instance_method, *args, &block)
+          rescue NoSuchDependencyError => error
+            if state
+              vertex = activated.vertex_named(name_for error.dependency)
+              error.required_by += vertex.incoming_edges.map { |e| e.origin.name }
+              error.required_by << name_for_explicit_dependency_source unless vertex.explicit_requirements.empty?
+            end
+            raise
+          end
+        end
+      end
+
+      # Processes the topmost available {RequirementState} on the stack
+      # @return [void]
+      def process_topmost_state
+        if possibility
+          attempt_to_activate
+        else
+          create_conflict if state.is_a? PossibilityState
+          unwind_for_conflict until possibility && state.is_a?(DependencyState)
+        end
+      end
+
+      # @return [Object] the current possibility that the resolution is trying
+      #   to activate
+      def possibility
+        possibilities.last
+      end
+
+      # @return [RequirementState] the current state the resolution is
+      #   operating upon
+      def state
+        states.last
+      end
+
+      # Creates the initial state for the resolution, based upon the
+      # {#requested} dependencies
+      # @return [DependencyState] the initial state for the resolution
+      def initial_state
+        graph = DependencyGraph.new.tap do |dg|
+          original_requested.each { |r| dg.add_root_vertex(name_for(r), nil).tap { |v| v.explicit_requirements << r } }
+        end
+
+        requirements = sort_dependencies(original_requested, graph, {})
+        initial_requirement = requirements.shift
+        DependencyState.new(
+          initial_requirement && name_for(initial_requirement),
+          requirements,
+          graph,
+          initial_requirement,
+          initial_requirement && search_for(initial_requirement),
+          0,
+          {}
+        )
+      end
+
+      # Unwinds the states stack because a conflict has been encountered
+      # @return [void]
+      def unwind_for_conflict
+        debug(depth) { "Unwinding for conflict: #{requirement}" }
+        conflicts.tap do |c|
+          states.slice!((state_index_for_unwind + 1)..-1)
+          raise VersionConflict.new(c) unless state
+          state.conflicts = c
+        end
+      end
+
+      # @return [Integer] The index to which the resolution should unwind in the
+      #   case of conflict.
+      def state_index_for_unwind
+        current_requirement = requirement
+        existing_requirement = requirement_for_existing_name(name)
+        until current_requirement.nil?
+          current_state = find_state_for(current_requirement)
+          return states.index(current_state) if state_any?(current_state)
+          current_requirement = parent_of(current_requirement)
+        end
+
+        until existing_requirement.nil?
+          existing_state = find_state_for(existing_requirement)
+          return states.index(existing_state) if state_any?(existing_state)
+          existing_requirement = parent_of(existing_requirement)
+        end
+        -1
+      end
+
+      # @return [Object] the requirement that led to `requirement` being added
+      #   to the list of requirements.
+      def parent_of(requirement)
+        return nil unless requirement
+        seen = false
+        state = states.reverse_each.find do |s|
+          seen ||= s.requirement == requirement
+          seen && s.requirement != requirement && !s.requirements.include?(requirement)
+        end
+        state && state.requirement
+      end
+
+      # @return [Object] the requirement that led to a version of a possibility
+      #   with the given name being activated.
+      def requirement_for_existing_name(name)
+        return nil unless activated.vertex_named(name).payload
+        states.reverse_each.find { |s| !s.activated.vertex_named(name).payload }.requirement
+      end
+
+      # @return [ResolutionState] the state whose `requirement` is the given
+      #   `requirement`.
+      def find_state_for(requirement)
+        return nil unless requirement
+        states.find { |i| requirement == i.requirement }
+      end
+
+      # @return [Boolean] whether or not the given state has any possibilities
+      #   left.
+      def state_any?(state)
+        state && state.possibilities.any?
+      end
+
+      # @return [Conflict] a {Conflict} that reflects the failure to activate
+      #   the {#possibility} in conjunction with the current {#state}
+      def create_conflict
+        vertex = activated.vertex_named(name)
+        requirements = {
+          name_for_explicit_dependency_source => vertex.explicit_requirements,
+          name_for_locking_dependency_source => Array(locked_requirement_named(name)),
+        }
+        vertex.incoming_edges.each { |edge| (requirements[edge.origin.payload] ||= []).unshift(*edge.requirements) }
+        conflicts[name] = Conflict.new(
+          requirement,
+          Hash[requirements.select { |_, r| !r.empty? }],
+          vertex.payload,
+          possibility,
+          locked_requirement_named(name),
+          requirement_trees
+        )
+      end
+
+      # @return [Array<Array<Object>>] The different requirement
+      #   trees that led to every requirement for the current spec.
+      def requirement_trees
+        activated.vertex_named(name).requirements.map { |r| requirement_tree_for(r) }
+      end
+
+      # @return [Array<Object>] the list of requirements that led to
+      #   `requirement` being required.
+      def requirement_tree_for(requirement)
+        tree = []
+        while requirement
+          tree.unshift(requirement)
+          requirement = parent_of(requirement)
+        end
+        tree
+      end
+
+      # Indicates progress roughly once every second
+      # @return [void]
+      def indicate_progress
+        @iteration_counter += 1
+        @progress_rate ||= resolver_ui.progress_rate
+        if iteration_rate.nil?
+          if Time.now - started_at >= @progress_rate
+            self.iteration_rate = @iteration_counter
+          end
+        end
+
+        if iteration_rate && (@iteration_counter % iteration_rate) == 0
+          resolver_ui.indicate_progress
+        end
+      end
+
+      # Calls the {#resolver_ui}'s {UI#debug} method
+      # @param [Integer] depth the depth of the {#states} stack
+      # @param [Proc] block a block that yields a {#to_s}
+      # @return [void]
+      def debug(depth = 0, &block)
+        resolver_ui.debug(depth, &block)
+      end
+
+      # Attempts to activate the current {#possibility}
+      # @return [void]
+      def attempt_to_activate
+        debug(depth) { 'Attempting to activate ' + possibility.to_s }
+        existing_node = activated.vertex_named(name)
+        if existing_node.payload
+          debug(depth) { "Found existing spec (#{existing_node.payload})" }
+          attempt_to_activate_existing_spec(existing_node)
+        else
+          attempt_to_activate_new_spec
+        end
+      end
+
+      # Attempts to activate the current {#possibility} (given that it has
+      # already been activated)
+      # @return [void]
+      def attempt_to_activate_existing_spec(existing_node)
+        existing_spec = existing_node.payload
+        if requirement_satisfied_by?(requirement, activated, existing_spec)
+          new_requirements = requirements.dup
+          push_state_for_requirements(new_requirements)
+        else
+          create_conflict
+          debug(depth) { "Unsatisfied by existing spec (#{existing_node.payload})" }
+          unwind_for_conflict
+        end
+      end
+
+      # Attempts to activate the current {#possibility} (given that it hasn't
+      # already been activated)
+      # @return [void]
+      def attempt_to_activate_new_spec
+        satisfied = begin
+          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
+        end
+        if satisfied
+          activate_spec
+        else
+          create_conflict
+          unwind_for_conflict
+        end
+      end
+
+      # @param [String] requirement_name the spec name to search for
+      # @return [Object] the locked spec named `requirement_name`, if one
+      #   is found on {#base}
+      def locked_requirement_named(requirement_name)
+        vertex = base.vertex_named(requirement_name)
+        vertex && vertex.payload
+      end
+
+      # Add the current {#possibility} to the dependency graph of the current
+      # {#state}
+      # @return [void]
+      def activate_spec
+        conflicts.delete(name)
+        debug(depth) { 'Activated ' + name + ' at ' + possibility.to_s }
+        vertex = activated.vertex_named(name)
+        vertex.payload = possibility
+        require_nested_dependencies_for(possibility)
+      end
+
+      # Requires the dependencies that the recently activated spec has
+      # @param [Object] activated_spec the specification that has just been
+      #   activated
+      # @return [void]
+      def require_nested_dependencies_for(activated_spec)
+        nested_dependencies = dependencies_for(activated_spec)
+        debug(depth) { "Requiring nested dependencies (#{nested_dependencies.map(&:to_s).join(', ')})" }
+        nested_dependencies.each { |d|  activated.add_child_vertex name_for(d), nil, [name_for(activated_spec)], d }
+
+        push_state_for_requirements(requirements + nested_dependencies)
+      end
+
+      # Pushes a new {DependencyState} that encapsulates both existing and new
+      # requirements
+      # @param [Array] new_requirements
+      # @return [void]
+      def push_state_for_requirements(new_requirements)
+        new_requirements = sort_dependencies(new_requirements, activated, conflicts)
+        new_requirement = new_requirements.shift
+        states.push DependencyState.new(
+          new_requirement ? name_for(new_requirement) : '',
+          new_requirements,
+          activated.dup,
+          new_requirement,
+          new_requirement ? search_for(new_requirement) : [],
+          depth,
+          conflicts.dup
+        )
+      end
+    end
+  end
+end
diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolver.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolver.rb
new file mode 100644
index 0000000000..7cfe914d34
--- /dev/null
+++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/resolver.rb
@@ -0,0 +1,43 @@
+require 'molinillo/dependency_graph'
+
+module Bundler::Molinillo
+  # This class encapsulates a dependency resolver.
+  # The resolver is responsible for determining which set of dependencies to
+  # activate, with feedback from the the {#specification_provider}
+  #
+  #
+  class Resolver
+    require 'molinillo/resolution'
+
+    # @return [SpecificationProvider] the specification provider used
+    #   in the resolution process
+    attr_reader :specification_provider
+
+    # @return [UI] the UI module used to communicate back to the user
+    #   during the resolution process
+    attr_reader :resolver_ui
+
+    # @param  [SpecificationProvider] specification_provider
+    #   see {#specification_provider}
+    # @param  [UI] resolver_ui
+    #   see {#resolver_ui}
+    def initialize(specification_provider, resolver_ui)
+      @specification_provider = specification_provider
+      @resolver_ui = resolver_ui
+    end
+
+    # Resolves the requested dependencies into a {DependencyGraph},
+    # locking to the base dependency graph (if specified)
+    # @param [Array] requested an array of 'requested' dependencies that the
+    #   {#specification_provider} can understand
+    # @param [DependencyGraph,nil] base the base dependency graph to which
+    #   dependencies should be 'locked'
+    def resolve(requested, base = DependencyGraph.new)
+      Resolution.new(specification_provider,
+                     resolver_ui,
+                     requested,
+                     base).
+        resolve
+    end
+  end
+end
diff --git a/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/state.rb b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/state.rb
new file mode 100644
index 0000000000..8e394f8672
--- /dev/null
+++ b/lib/bundler/vendor/Molinillo-double-backjumping/lib/molinillo/state.rb
@@ -0,0 +1,43 @@
+module Bundler::Molinillo
+  # A state that a {Resolution} can be in
+  # @attr [String] name
+  # @attr [Array<Object>] requirements
+  # @attr [DependencyGraph] activated
+  # @attr [Object] requirement
+  # @attr [Object] possibility
+  # @attr [Integer] depth
+  # @attr [Set<Object>] conflicts
+  ResolutionState = Struct.new(
+    :name,
+    :requirements,
+    :activated,
+    :requirement,
+    :possibilities,
+    :depth,
+    :conflicts
+  )
+
+  # A state that encapsulates a set of {#requirements} with an {Array} of
+  # possibilities
+  class DependencyState < ResolutionState
+    # Removes a possibility from `self`
+    # @return [PossibilityState] a state with a single possibility,
+    #  the possibility that was removed from `self`
+    def pop_possibility_state
+      PossibilityState.new(
+        name,
+        requirements.dup,
+        activated.dup,
+        requirement,
+        [possibilities.pop],
+        depth + 1,
+        conflicts.dup
+      )
+    end
+  end
+
+  # A state that encapsulates a single possibility to fulfill the given
+  # {#requirement}
+  class PossibilityState < ResolutionState
+  end
+end
diff --git a/lib/bundler/vendored_molinillo.rb b/lib/bundler/vendored_molinillo.rb
new file mode 100644
index 0000000000..daf52b8293
--- /dev/null
+++ b/lib/bundler/vendored_molinillo.rb
@@ -0,0 +1,5 @@
+vendor = File.expand_path('../vendor/Molinillo-double-backjumping/lib', __FILE__)
+loaded = $:.include?(vendor)
+$:.unshift(vendor) unless loaded
+require 'molinillo'
+$:.delete(vendor) unless loaded
diff --git a/spec/install/bundler_spec.rb b/spec/install/bundler_spec.rb
index b85ddf8c94..066b9309c5 100644
--- a/spec/install/bundler_spec.rb
+++ b/spec/install/bundler_spec.rb
@@ -104,7 +104,7 @@ describe "bundle install" do
               activesupport (>= 2.0.0) ruby
 
             rails_fail (>= 0) ruby depends on
-              activesupport (1.2.3)
+              activesupport (= 1.2.3) ruby
       E
       expect(out).to eq(nice_error)
     end
@@ -124,7 +124,7 @@ describe "bundle install" do
             rails_fail (>= 0) ruby depends on
               activesupport (= 1.2.3) ruby
 
-            activesupport (2.3.5)
+            activesupport (= 2.3.5) ruby
       E
       expect(out).to eq(nice_error)
     end
diff --git a/spec/install/gems/flex_spec.rb b/spec/install/gems/flex_spec.rb
index dbf9278af7..691a6a86bb 100644
--- a/spec/install/gems/flex_spec.rb
+++ b/spec/install/gems/flex_spec.rb
@@ -197,7 +197,7 @@ describe "bundle flex_install" do
         Resolving dependencies...
         Bundler could not find compatible versions for gem "rack":
           In snapshot (Gemfile.lock):
-            rack (0.9.1)
+            rack (= 0.9.1)
 
           In Gemfile:
             rack-obama (= 2.0) ruby depends on
diff --git a/spec/install/gems/resolving_spec.rb b/spec/install/gems/resolving_spec.rb
index 6e07073bcd..ef8aecf1ab 100644
--- a/spec/install/gems/resolving_spec.rb
+++ b/spec/install/gems/resolving_spec.rb
@@ -80,7 +80,7 @@ describe "bundle install with gem sources" do
             bundle :install, :env => {"DEBUG_RESOLVER" => "1"}
           end
 
-          expect(resolve_output).to include("==== Iterating ====")
+          expect(resolve_output).to include("Creating possibility state for net_c")
         end
       end
 
diff --git a/spec/quality_spec.rb b/spec/quality_spec.rb
index 0a3887055f..378f62d3ec 100644
--- a/spec/quality_spec.rb
+++ b/spec/quality_spec.rb
@@ -96,7 +96,7 @@ describe "The library itself" do
       end
     end
 
-    expect(@err).to eq("")
+    expect(@err.split("\n").reject { |f| f =~ %r{lib/bundler/vendor} }).to eq([])
     expect(@out).to eq("")
   end
 end
diff --git a/spec/realworld/parallel_spec.rb b/spec/realworld/parallel_spec.rb
index b0abdc507f..25adfefdf5 100644
--- a/spec/realworld/parallel_spec.rb
+++ b/spec/realworld/parallel_spec.rb
@@ -21,26 +21,6 @@ describe "parallel", :realworld => true do
     expect(out).to match(/: "4"/)
   end
 
-  it "installs even with circular dependency", :ruby => "1.9" do
-    gemfile <<-G
-      source 'https://rubygems.org'
-      gem 'activesupport', '~> 3.2.13'
-      gem 'mongoid_auto_increment', "0.1.1"
-    G
-
-    bundle :install, :jobs => 4, :env => {"DEBUG" => "1"}
-    expect(out).to match(/[1-3]: /)
-
-    bundle "show activesupport"
-    expect(out).to match(/activesupport/)
-
-    bundle "show mongoid_auto_increment"
-    expect(out).to match(%r{gems/mongoid_auto_increment})
-
-    bundle "config jobs"
-    expect(out).to match(/: "4"/)
-  end
-
   it "updates" do
     install_gemfile <<-G
       source "https://rubygems.org"
diff --git a/spec/resolver/basic_spec.rb b/spec/resolver/basic_spec.rb
index e588c9ecf1..1245898564 100644
--- a/spec/resolver/basic_spec.rb
+++ b/spec/resolver/basic_spec.rb
@@ -57,10 +57,9 @@ describe "Resolving" do
     @index = a_circular_index
     dep "circular_app"
 
-    got = resolve
     expect {
-      got = got.map { |s| s.full_name }.sort
-    }.to raise_error(Bundler::CyclicDependencyError, /please remove either gem 'foo' or gem 'bar'/i)
+      resolve
+    }.to raise_error(Bundler::CyclicDependencyError, /please remove either gem 'bar' or gem 'foo'/i)
   end
 
 end