From 7bf7a4a33be8387d9ff1ddfb762f97caeb8021f5 Mon Sep 17 00:00:00 2001
From: hsbt <hsbt@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>
Date: Wed, 1 Jul 2015 21:50:14 +0000
Subject: * lib/rubygems: Update to RubyGems HEAD(c202db2).   this version
 contains many enhancements see http://git.io/vtNwF * test/rubygems: ditto.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@51092 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
---
 lib/rubygems/basic_specification.rb                |  40 +-
 lib/rubygems/commands/dependency_command.rb        |  40 +-
 lib/rubygems/commands/install_command.rb           |   2 +-
 lib/rubygems/commands/list_command.rb              |   2 +-
 lib/rubygems/commands/pristine_command.rb          |   2 +-
 lib/rubygems/commands/query_command.rb             |   2 +-
 lib/rubygems/core_ext/kernel_require.rb            |   4 +-
 lib/rubygems/dependency.rb                         |   9 +-
 lib/rubygems/dependency_list.rb                    |   3 +
 lib/rubygems/ext/builder.rb                        |   2 +
 lib/rubygems/ext/ext_conf_builder.rb               |   7 +-
 lib/rubygems/indexer.rb                            |  26 +-
 lib/rubygems/installer.rb                          |  84 ++--
 lib/rubygems/installer_test_case.rb                |   4 +-
 lib/rubygems/package.rb                            |  24 +-
 lib/rubygems/package/old.rb                        |   4 +-
 lib/rubygems/package/tar_reader/entry.rb           |   8 +-
 lib/rubygems/package/tar_test_case.rb              |  15 +-
 lib/rubygems/package/tar_writer.rb                 |  20 +-
 lib/rubygems/platform.rb                           |   1 +
 lib/rubygems/rdoc.rb                               |   3 +-
 lib/rubygems/request/connection_pools.rb           |  12 +-
 lib/rubygems/request_set.rb                        |   7 +-
 lib/rubygems/request_set/gem_dependency_api.rb     |   2 +-
 lib/rubygems/request_set/lockfile.rb               |   2 +-
 lib/rubygems/resolver.rb                           | 286 +++-----------
 lib/rubygems/resolver/activation_request.rb        |   3 +-
 lib/rubygems/resolver/conflict.rb                  |   1 -
 lib/rubygems/resolver/dependency_request.rb        |   5 +-
 lib/rubygems/resolver/git_specification.rb         |   3 +-
 lib/rubygems/resolver/molinillo.rb                 |   1 +
 lib/rubygems/resolver/molinillo/lib/molinillo.rb   |   5 +
 .../molinillo/lib/molinillo/dependency_graph.rb    | 266 +++++++++++++
 .../resolver/molinillo/lib/molinillo/errors.rb     |  69 ++++
 .../molinillo/lib/molinillo/gem_metadata.rb        |   3 +
 .../molinillo/modules/specification_provider.rb    |  99 +++++
 .../resolver/molinillo/lib/molinillo/modules/ui.rb |  63 +++
 .../resolver/molinillo/lib/molinillo/resolution.rb | 430 +++++++++++++++++++++
 .../resolver/molinillo/lib/molinillo/resolver.rb   |  43 +++
 .../resolver/molinillo/lib/molinillo/state.rb      |  51 +++
 lib/rubygems/resolver/specification.rb             |   2 +-
 lib/rubygems/specification.rb                      | 237 ++++++++----
 lib/rubygems/stub_specification.rb                 |  39 +-
 lib/rubygems/test_case.rb                          |  49 ++-
 lib/rubygems/test_utilities.rb                     |  36 +-
 lib/rubygems/uninstaller.rb                        |   2 +-
 lib/rubygems/util.rb                               |   8 +-
 lib/rubygems/util/list.rb                          |  30 +-
 lib/rubygems/util/stringio.rb                      |  34 --
 lib/rubygems/version.rb                            |  12 +-
 50 files changed, 1565 insertions(+), 537 deletions(-)
 create mode 100644 lib/rubygems/resolver/molinillo.rb
 create mode 100644 lib/rubygems/resolver/molinillo/lib/molinillo.rb
 create mode 100644 lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb
 create mode 100644 lib/rubygems/resolver/molinillo/lib/molinillo/errors.rb
 create mode 100644 lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb
 create mode 100644 lib/rubygems/resolver/molinillo/lib/molinillo/modules/specification_provider.rb
 create mode 100644 lib/rubygems/resolver/molinillo/lib/molinillo/modules/ui.rb
 create mode 100644 lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb
 create mode 100644 lib/rubygems/resolver/molinillo/lib/molinillo/resolver.rb
 create mode 100644 lib/rubygems/resolver/molinillo/lib/molinillo/state.rb
 delete mode 100644 lib/rubygems/util/stringio.rb

(limited to 'lib/rubygems')

diff --git a/lib/rubygems/basic_specification.rb b/lib/rubygems/basic_specification.rb
index e27b261d7e..78a45c1190 100644
--- a/lib/rubygems/basic_specification.rb
+++ b/lib/rubygems/basic_specification.rb
@@ -22,13 +22,17 @@ class Gem::BasicSpecification
   ##
   # The path this gemspec was loaded from.  This attribute is not persisted.
 
-  attr_reader :loaded_from
+  attr_accessor :loaded_from
 
   ##
   # Allows correct activation of git: and path: gems.
 
   attr_writer :full_gem_path # :nodoc:
 
+  def initialize
+    internal_init
+  end
+
   def self.default_specifications_dir
     File.join(Gem.default_dir, "specifications", "default")
   end
@@ -141,7 +145,7 @@ class Gem::BasicSpecification
     @full_require_paths ||=
     begin
       full_paths = raw_require_paths.map do |path|
-        File.join full_gem_path, path
+        File.join full_gem_path, path.untaint
       end
 
       full_paths << extension_dir unless @extensions.nil? || @extensions.empty?
@@ -189,13 +193,7 @@ class Gem::BasicSpecification
     @gems_dir ||= File.join(loaded_from && base_dir || Gem.dir, "gems")
   end
 
-  ##
-  # Set the path the Specification was loaded from. +path+ is converted to a
-  # String.
-
-  def loaded_from= path
-    @loaded_from   = path && path.to_s
-
+  def internal_init # :nodoc:
     @extension_dir = nil
     @extensions_dir = nil
     @full_gem_path         = nil
@@ -263,6 +261,30 @@ class Gem::BasicSpecification
     paths.uniq
   end
 
+  ##
+  # Return all files in this gem that match for +glob+.
+
+  def matches_for_glob glob # TODO: rename?
+    # TODO: do we need these?? Kill it
+    glob = File.join(self.lib_dirs_glob, glob)
+
+    Dir[glob].map { |f| f.untaint } # FIX our tests are broken, run w/ SAFE=1
+  end
+
+  ##
+  # Returns a string usable in Dir.glob to match all requirable paths
+  # for this spec.
+
+  def lib_dirs_glob
+    dirs = if self.require_paths.size > 1 then
+             "{#{self.require_paths.join(',')}}"
+           else
+             self.require_paths.first
+           end
+
+    "#{self.full_gem_path}/#{dirs}"
+  end
+
   ##
   # Return a Gem::Specification from this gem
 
diff --git a/lib/rubygems/commands/dependency_command.rb b/lib/rubygems/commands/dependency_command.rb
index 4a54a3e385..9d4b3e0f50 100644
--- a/lib/rubygems/commands/dependency_command.rb
+++ b/lib/rubygems/commands/dependency_command.rb
@@ -61,10 +61,16 @@ use with other commands.
     ss.map { |spec, _| spec }
   end
 
-  def fetch_specs dependency # :nodoc:
+  def fetch_specs name_pattern, dependency # :nodoc:
     specs = []
 
-    specs.concat dependency.matching_specs     if local?
+    if local?
+      specs.concat Gem::Specification.stubs.find_all { |spec|
+        name_pattern =~ spec.name and
+          dependency.requirement.satisfied_by? spec.version
+      }.map(&:to_spec)
+    end
+
     specs.concat fetch_remote_specs dependency if remote?
 
     ensure_specs specs
@@ -72,16 +78,7 @@ use with other commands.
     specs.uniq.sort
   end
 
-  def gem_dependency args, version, prerelease # :nodoc:
-    args << '' if args.empty?
-
-    pattern = if args.length == 1 and args.first =~ /\A\/(.*)\/(i)?\z/m then
-                flags = $2 ? Regexp::IGNORECASE : nil
-                Regexp.new $1, flags
-              else
-                /\A#{Regexp.union(*args)}/
-              end
-
+  def gem_dependency pattern, version, prerelease # :nodoc:
     dependency = Gem::Deprecate.skip_during {
       Gem::Dependency.new pattern, version
     }
@@ -121,10 +118,12 @@ use with other commands.
   def execute
     ensure_local_only_reverse_dependencies
 
+    pattern = name_pattern options[:args]
+
     dependency =
-      gem_dependency options[:args], options[:version], options[:prerelease]
+      gem_dependency pattern, options[:version], options[:prerelease]
 
-    specs = fetch_specs dependency
+    specs = fetch_specs pattern, dependency
 
     reverse = reverse_dependencies specs
 
@@ -203,5 +202,16 @@ use with other commands.
     result
   end
 
-end
+  private
 
+  def name_pattern args
+    args << '' if args.empty?
+
+    if args.length == 1 and args.first =~ /\A\/(.*)\/(i)?\z/m then
+      flags = $2 ? Regexp::IGNORECASE : nil
+      Regexp.new $1, flags
+    else
+      /\A#{Regexp.union(*args)}/
+    end
+  end
+end
diff --git a/lib/rubygems/commands/install_command.rb b/lib/rubygems/commands/install_command.rb
index 1bf5928ebb..7e3a953d19 100644
--- a/lib/rubygems/commands/install_command.rb
+++ b/lib/rubygems/commands/install_command.rb
@@ -275,7 +275,7 @@ to write the specification by hand.  For example:
       gem = fetcher.download_to_cache dependency
     end
 
-    inst = Gem::Installer.new gem, options
+    inst = Gem::Installer.at gem, options
     inst.install
 
     require 'rubygems/dependency_installer'
diff --git a/lib/rubygems/commands/list_command.rb b/lib/rubygems/commands/list_command.rb
index c6ff237311..1842aaacca 100644
--- a/lib/rubygems/commands/list_command.rb
+++ b/lib/rubygems/commands/list_command.rb
@@ -33,7 +33,7 @@ To search for remote gems use the search command.
   end
 
   def usage # :nodoc:
-    "#{program_name} [STRING ...]"
+    "#{program_name} [REGEXP ...]"
   end
 
 end
diff --git a/lib/rubygems/commands/pristine_command.rb b/lib/rubygems/commands/pristine_command.rb
index 91308d83f6..5a36b12358 100644
--- a/lib/rubygems/commands/pristine_command.rb
+++ b/lib/rubygems/commands/pristine_command.rb
@@ -156,7 +156,7 @@ extensions will be restored.
           install_defaults.to_s['--env-shebang']
         end
 
-      installer = Gem::Installer.new(gem,
+      installer = Gem::Installer.at(gem,
                                      :wrappers => true,
                                      :force => true,
                                      :install_dir => spec.base_dir,
diff --git a/lib/rubygems/commands/query_command.rb b/lib/rubygems/commands/query_command.rb
index 432250e033..0d28711de8 100644
--- a/lib/rubygems/commands/query_command.rb
+++ b/lib/rubygems/commands/query_command.rb
@@ -227,7 +227,7 @@ is too hard to use.
 
     name_tuple, spec = detail_tuple
 
-    spec = spec.fetch_spec name_tuple unless Gem::Specification === spec
+    spec = spec.fetch_spec name_tuple if spec.respond_to? :fetch_spec
 
     entry << "\n"
 
diff --git a/lib/rubygems/core_ext/kernel_require.rb b/lib/rubygems/core_ext/kernel_require.rb
index 8f2cddee4d..0a073adb7b 100755
--- a/lib/rubygems/core_ext/kernel_require.rb
+++ b/lib/rubygems/core_ext/kernel_require.rb
@@ -66,7 +66,7 @@ module Kernel
 
     begin
       RUBYGEMS_ACTIVATION_MONITOR.exit
-      return gem_original_require(spec.to_fullpath(path) || path)
+      return gem_original_require(path)
     end if spec
 
     # Attempt to find +path+ in any unresolved gems...
@@ -105,7 +105,7 @@ module Kernel
 
       # Ok, now find a gem that has no conflicts, starting
       # at the highest version.
-      valid = found_specs.select { |s| s.conflicts.empty? }.last
+      valid = found_specs.reject { |s| s.has_conflicts? }.last
 
       unless valid then
         le = Gem::LoadError.new "unable to find a version of '#{names.first}' to activate"
diff --git a/lib/rubygems/dependency.rb b/lib/rubygems/dependency.rb
index 5924d2fc6b..b4a6dd8673 100644
--- a/lib/rubygems/dependency.rb
+++ b/lib/rubygems/dependency.rb
@@ -164,6 +164,10 @@ class Gem::Dependency
     @type ||= :runtime
   end
 
+  def runtime?
+    @type == :runtime || !@type
+  end
+
   def == other # :nodoc:
     Gem::Dependency === other &&
       self.name        == other.name &&
@@ -270,9 +274,8 @@ class Gem::Dependency
   end
 
   def matching_specs platform_only = false
-    matches = Gem::Specification.stubs.find_all { |spec|
-      self.name === spec.name and # TODO: == instead of ===
-        requirement.satisfied_by? spec.version
+    matches = Gem::Specification.stubs_for(name).find_all { |spec|
+      requirement.satisfied_by? spec.version
     }.map(&:to_spec)
 
     if platform_only
diff --git a/lib/rubygems/dependency_list.rb b/lib/rubygems/dependency_list.rb
index ad7a82a86e..c034bb6589 100644
--- a/lib/rubygems/dependency_list.rb
+++ b/lib/rubygems/dependency_list.rb
@@ -141,6 +141,9 @@ class Gem::DependencyList
   def ok_to_remove?(full_name, check_dev=true)
     gem_to_remove = find_name full_name
 
+    # If the state is inconsistent, at least don't crash
+    return true unless gem_to_remove
+
     siblings = @specs.find_all { |s|
       s.name == gem_to_remove.name &&
         s.full_name != gem_to_remove.full_name
diff --git a/lib/rubygems/ext/builder.rb b/lib/rubygems/ext/builder.rb
index 548f1262a8..abcc09ce57 100644
--- a/lib/rubygems/ext/builder.rb
+++ b/lib/rubygems/ext/builder.rb
@@ -66,9 +66,11 @@ class Gem::Ext::Builder
       # TODO use Process.spawn when ruby 1.8 support is dropped.
       rubygems_gemdeps, ENV['RUBYGEMS_GEMDEPS'] = ENV['RUBYGEMS_GEMDEPS'], nil
       if verbose
+        puts("current directory: #{Dir.pwd}")
         puts(command)
         system(command)
       else
+        results << "current directory: #{Dir.pwd}"
         results << command
         results << `#{command} #{redirector}`
       end
diff --git a/lib/rubygems/ext/ext_conf_builder.rb b/lib/rubygems/ext/ext_conf_builder.rb
index d11d1ac328..f5c4c8ce84 100644
--- a/lib/rubygems/ext/ext_conf_builder.rb
+++ b/lib/rubygems/ext/ext_conf_builder.rb
@@ -35,7 +35,12 @@ class Gem::Ext::ExtConfBuilder < Gem::Ext::Builder
         begin
           run cmd, results
         ensure
-          FileUtils.mv 'mkmf.log', dest_path if File.exist? 'mkmf.log'
+          if File.exist? 'mkmf.log'
+            results << "To see why this extension failed to compile, please check" \
+              " the mkmf.log which can be found here:\n"
+            results << "  " + File.join(dest_path, 'mkmf.log') + "\n"
+            FileUtils.mv 'mkmf.log', dest_path
+          end
           siteconf.unlink
         end
 
diff --git a/lib/rubygems/indexer.rb b/lib/rubygems/indexer.rb
index 99938d013a..23279f40ec 100644
--- a/lib/rubygems/indexer.rb
+++ b/lib/rubygems/indexer.rb
@@ -96,11 +96,10 @@ class Gem::Indexer
   # Build various indices
 
   def build_indices
-    Gem::Specification.dirs = []
-    Gem::Specification.add_specs(*map_gems_to_specs(gem_file_list))
-
-    build_marshal_gemspecs
-    build_modern_indices if @build_modern
+    specs = map_gems_to_specs gem_file_list
+    Gem::Specification._resort! specs
+    build_marshal_gemspecs specs
+    build_modern_indices specs if @build_modern
 
     compress_indices
   end
@@ -108,8 +107,8 @@ class Gem::Indexer
   ##
   # Builds Marshal quick index gemspecs.
 
-  def build_marshal_gemspecs
-    count = Gem::Specification.count { |s| not s.default_gem? }
+  def build_marshal_gemspecs specs
+    count = specs.count
     progress = ui.progress_reporter count,
                                     "Generating Marshal quick index gemspecs for #{count} gems",
                                     "Complete"
@@ -117,7 +116,7 @@ class Gem::Indexer
     files = []
 
     Gem.time 'Generated Marshal quick index gemspecs' do
-      Gem::Specification.each do |spec|
+      specs.each do |spec|
         next if spec.default_gem?
         spec_file_name = "#{spec.original_name}.gemspec.rz"
         marshal_name = File.join @quick_marshal_dir, spec_file_name
@@ -171,14 +170,12 @@ class Gem::Indexer
   ##
   # Builds indices for RubyGems 1.2 and newer. Handles full, latest, prerelease
 
-  def build_modern_indices
-    specs = Gem::Specification.reject { |s| s.default_gem? }
-
+  def build_modern_indices specs
     prerelease, released = specs.partition { |s|
       s.version.prerelease?
     }
     latest_specs =
-      Gem::Specification.latest_specs.reject { |s| s.default_gem? }
+      Gem::Specification._latest_specs specs
 
     build_modern_index(released.sort, @specs_index, 'specs')
     build_modern_index(latest_specs.sort, @latest_specs_index, 'latest specs')
@@ -376,10 +373,7 @@ class Gem::Indexer
     specs = map_gems_to_specs updated_gems
     prerelease, released = specs.partition { |s| s.version.prerelease? }
 
-    Gem::Specification.dirs = []
-    Gem::Specification.add_specs(*specs)
-
-    files = build_marshal_gemspecs
+    files = build_marshal_gemspecs specs
 
     Gem.time 'Updated indexes' do
       update_specs_index released, @dest_specs_index, @specs_index
diff --git a/lib/rubygems/installer.rb b/lib/rubygems/installer.rb
index 10fc1a34a5..efaea83187 100644
--- a/lib/rubygems/installer.rb
+++ b/lib/rubygems/installer.rb
@@ -61,11 +61,6 @@ class Gem::Installer
 
   attr_reader :options
 
-  ##
-  # Sets the specification for .gem-less installs.
-
-  attr_writer :spec
-
   @path_warning = false
 
   @install_lock = Mutex.new
@@ -99,6 +94,46 @@ class Gem::Installer
 
   end
 
+  ##
+  # Construct an installer object for the gem file located at +path+
+
+  def self.at path, options = {}
+    security_policy = options[:security_policy]
+    package = Gem::Package.new path, security_policy
+    new package, options
+  end
+
+  class FakePackage
+    attr_accessor :spec
+
+    def initialize(spec)
+      @spec = spec
+    end
+
+    def extract_files destination_dir, pattern = '*'
+      FileUtils.mkdir_p destination_dir
+
+      spec.files.each do |file|
+        file = File.join destination_dir, file
+        next if File.exist? file
+        FileUtils.mkdir_p File.dirname(file)
+        File.open file, 'w' do |fp| fp.puts "# #{file}" end
+      end
+    end
+
+    def copy_to path
+    end
+  end
+
+  ##
+  # Construct an installer object for an ephemeral gem (one where we don't
+  # actually have a .gem file, just a spec)
+
+  def self.for_spec spec, options = {}
+    # FIXME: we should have a real Package class for this
+    new FakePackage.new(spec), options
+  end
+
   ##
   # Constructs an Installer instance that will install the gem located at
   # +gem+.  +options+ is a Hash with the following keys:
@@ -122,17 +157,22 @@ class Gem::Installer
   # :build_args:: An Array of arguments to pass to the extension builder
   #               process. If not set, then Gem::Command.build_args is used
 
-  def initialize(gem, options={})
+  def initialize(package, options={})
     require 'fileutils'
 
-    @gem = gem
     @options = options
-    @package = Gem::Package.new @gem
+    if package.is_a? String
+      security_policy = options[:security_policy]
+      @package = Gem::Package.new package, security_policy
+      if $VERBOSE
+        warn "constructing an Installer object with a string is deprecated. Please use Gem::Installer.at (called from: #{caller.first})"
+      end
+    else
+      @package = package
+    end
 
     process_options
 
-    @package.security_policy = @security_policy
-
     if options[:user_install] and not options[:unpack] then
       @gem_home = Gem.user_dir
       @bin_dir = Gem.bindir gem_home unless options[:bin_dir]
@@ -211,7 +251,7 @@ class Gem::Installer
   # Lazy accessor for the installer's spec.
 
   def spec
-    @spec ||= @package.spec
+    @package.spec
   rescue Gem::Package::Error => e
     raise Gem::InstallError, "invalid gem: #{e.message}"
   end
@@ -230,7 +270,7 @@ class Gem::Installer
   def install
     pre_install_checks
 
-    FileUtils.rm_f File.join gem_home, 'specifications', @spec.spec_name
+    FileUtils.rm_f File.join gem_home, 'specifications', spec.spec_name
 
     run_pre_install_hooks
 
@@ -239,12 +279,12 @@ class Gem::Installer
 
     FileUtils.mkdir_p gem_dir
 
-    spec.loaded_from = spec_file
-
     if @options[:install_as_default]
+      spec.loaded_from = default_spec_file
       extract_bin
       write_default_spec
     else
+      spec.loaded_from = spec_file
       extract_files
 
       build_extensions
@@ -258,7 +298,7 @@ class Gem::Installer
 
     say spec.post_install_message unless spec.post_install_message.nil?
 
-    Gem::Installer.install_lock.synchronize { Gem::Specification.add_spec spec }
+    Gem::Installer.install_lock.synchronize { Gem::Specification.reset }
 
     run_post_install_hooks
 
@@ -363,7 +403,7 @@ class Gem::Installer
   #
 
   def default_spec_file
-    File.join gem_home, "specifications/default", "#{spec.full_name}.gemspec"
+    File.join Gem::Specification.default_specifications_dir, "#{spec.full_name}.gemspec"
   end
 
   ##
@@ -595,7 +635,6 @@ class Gem::Installer
     @gem_home            = options[:install_dir] || Gem.dir
     @ignore_dependencies = options[:ignore_dependencies]
     @format_executable   = options[:format_executable]
-    @security_policy     = options[:security_policy]
     @wrappers            = options[:wrappers]
     @only_install_dir    = options[:only_install_dir]
 
@@ -661,7 +700,7 @@ class Gem::Installer
 
 require 'rubygems'
 
-version = "#{Gem::Requirement.default}"
+version = "#{Gem::Requirement.default}.a"
 
 if ARGV.first
   str = ARGV.first
@@ -764,11 +803,6 @@ TEXT
   def pre_install_checks
     verify_gem_home options[:unpack]
 
-    # If we're forcing the install then disable security unless the security
-    # policy says that we only install signed gems.
-    @security_policy = nil if
-      @force and @security_policy and not @security_policy.only_signed
-
     ensure_loadable_spec
 
     if options[:install_as_default]
@@ -811,9 +845,7 @@ TEXT
 
   def write_cache_file
     cache_file = File.join gem_home, 'cache', spec.file_name
-
-    FileUtils.cp @gem, cache_file unless File.exist? cache_file
+    @package.copy_to cache_file
   end
 
 end
-
diff --git a/lib/rubygems/installer_test_case.rb b/lib/rubygems/installer_test_case.rb
index 549de011e4..f4aa773114 100644
--- a/lib/rubygems/installer_test_case.rb
+++ b/lib/rubygems/installer_test_case.rb
@@ -176,7 +176,7 @@ class Gem::InstallerTestCase < Gem::TestCase
       end
     end
 
-    @installer = Gem::Installer.new @gem
+    @installer = Gem::Installer.at @gem
   end
 
   ##
@@ -184,7 +184,7 @@ class Gem::InstallerTestCase < Gem::TestCase
   # +user+ is true a user-install will be performed.
 
   def util_installer(spec, gem_home, user=false)
-    Gem::Installer.new(spec.cache_file,
+    Gem::Installer.at(spec.cache_file,
                        :install_dir => gem_home,
                        :user_install => user)
   end
diff --git a/lib/rubygems/package.rb b/lib/rubygems/package.rb
index e8b8b38b06..64beae5550 100644
--- a/lib/rubygems/package.rb
+++ b/lib/rubygems/package.rb
@@ -123,7 +123,7 @@ class Gem::Package
   # If +gem+ is an existing file in the old format a Gem::Package::Old will be
   # returned.
 
-  def self.new gem
+  def self.new gem, security_policy = nil
     gem = if gem.is_a?(Gem::Package::Source)
             gem
           elsif gem.respond_to? :read
@@ -132,7 +132,7 @@ class Gem::Package
             Gem::Package::FileSource.new gem
           end
 
-    return super(gem) unless Gem::Package == self
+    return super unless Gem::Package == self
     return super unless gem.present?
 
     return super unless gem.start
@@ -144,7 +144,7 @@ class Gem::Package
   ##
   # Creates a new package that will read or write to the file +gem+.
 
-  def initialize gem # :notnew:
+  def initialize gem, security_policy # :notnew:
     @gem = gem
 
     @build_time      = Time.now
@@ -152,12 +152,19 @@ class Gem::Package
     @contents        = nil
     @digests         = Hash.new { |h, algorithm| h[algorithm] = {} }
     @files           = nil
-    @security_policy = nil
+    @security_policy = security_policy
     @signatures      = {}
     @signer          = nil
     @spec            = nil
   end
 
+  ##
+  # Copies this package to +path+ (if possible)
+
+  def copy_to path
+    FileUtils.cp @gem.path, path unless File.exist? path
+  end
+
   ##
   # Adds a checksum for each entry in the gem to checksums.yaml.gz.
 
@@ -200,7 +207,11 @@ class Gem::Package
 
   def add_files tar # :nodoc:
     @spec.files.each do |file|
-      stat = File.stat file
+      stat = File.lstat file
+
+      if stat.symlink?
+        tar.add_symlink file, File.readlink(file), stat.mode
+      end
 
       next unless stat.file?
 
@@ -371,6 +382,8 @@ EOM
           FileUtils.chmod entry.header.mode, destination
         end if entry.file?
 
+        File.symlink(install_location(entry.header.linkname, destination_dir), destination) if entry.symlink?
+
         verbose destination
       end
     end
@@ -611,4 +624,3 @@ require 'rubygems/package/tar_header'
 require 'rubygems/package/tar_reader'
 require 'rubygems/package/tar_reader/entry'
 require 'rubygems/package/tar_writer'
-
diff --git a/lib/rubygems/package/old.rb b/lib/rubygems/package/old.rb
index d7b228d893..bcf60a00c9 100644
--- a/lib/rubygems/package/old.rb
+++ b/lib/rubygems/package/old.rb
@@ -18,14 +18,14 @@ class Gem::Package::Old < Gem::Package
   # Creates a new old-format package reader for +gem+.  Old-format packages
   # cannot be written.
 
-  def initialize gem
+  def initialize gem, security_policy
     require 'fileutils'
     require 'zlib'
     Gem.load_yaml
 
     @contents        = nil
     @gem             = gem
-    @security_policy = nil
+    @security_policy = security_policy
     @spec            = nil
   end
 
diff --git a/lib/rubygems/package/tar_reader/entry.rb b/lib/rubygems/package/tar_reader/entry.rb
index 737c7639c6..1d917a81ac 100644
--- a/lib/rubygems/package/tar_reader/entry.rb
+++ b/lib/rubygems/package/tar_reader/entry.rb
@@ -102,6 +102,13 @@ class Gem::Package::TarReader::Entry
     @header.typeflag == "0"
   end
 
+  ##
+  # Is this tar entry a symlink?
+
+  def symlink?
+    @header.typeflag == "2"
+  end
+
   ##
   # The position in the tar entry
 
@@ -144,4 +151,3 @@ class Gem::Package::TarReader::Entry
   end
 
 end
-
diff --git a/lib/rubygems/package/tar_test_case.rb b/lib/rubygems/package/tar_test_case.rb
index 5253e32f36..b2d6f4ea77 100644
--- a/lib/rubygems/package/tar_test_case.rb
+++ b/lib/rubygems/package/tar_test_case.rb
@@ -71,7 +71,7 @@ class Gem::Package::TarTestCase < Gem::TestCase
     SP(Z(to_oct(sum, 6)))
   end
 
-  def header(type, fname, dname, length, mode, mtime, checksum = nil)
+  def header(type, fname, dname, length, mode, mtime, checksum = nil, linkname = "")
     checksum ||= " " * 8
 
     arr = [                  # struct tarfile_entry_posix
@@ -83,7 +83,7 @@ class Gem::Package::TarTestCase < Gem::TestCase
       Z(to_oct(mtime, 11)),  # char mtime[12];     0 padded, octal, null
       checksum,              # char checksum[8];   0 padded, octal, null, space
       type,                  # char typeflag[1];   file: "0"  dir: "5"
-      "\0" * 100,            # char linkname[100]; ASCII + (Z unless filled)
+      ASCIIZ(linkname, 100), # char linkname[100]; ASCII + (Z unless filled)
       "ustar\0",             # char magic[6];      "ustar\0"
       "00",                  # char version[2];    "00"
       ASCIIZ("wheel", 32),   # char uname[32];     ASCIIZ
@@ -117,6 +117,12 @@ class Gem::Package::TarTestCase < Gem::TestCase
     header("0", fname, dname, length, mode, mtime, checksum)
   end
 
+  def tar_symlink_header(fname, prefix, mode, mtime, linkname)
+    h = header("2", fname, prefix, 0, mode, mtime, nil, linkname)
+    checksum = calc_checksum(h)
+    header("2", fname, prefix, 0, mode, mtime, checksum, linkname)
+  end
+
   def to_oct(n, pad_size)
     "%0#{pad_size}o" % n
   end
@@ -133,5 +139,8 @@ class Gem::Package::TarTestCase < Gem::TestCase
     util_entry tar_dir_header("foo", "bar", 0, Time.now)
   end
 
-end
+  def util_symlink_entry
+    util_entry tar_symlink_header("foo", "bar", 0, Time.now, "link")
+  end
 
+end
diff --git a/lib/rubygems/package/tar_writer.rb b/lib/rubygems/package/tar_writer.rb
index dfd635724b..fff02e9235 100644
--- a/lib/rubygems/package/tar_writer.rb
+++ b/lib/rubygems/package/tar_writer.rb
@@ -233,6 +233,25 @@ class Gem::Package::TarWriter
     self
   end
 
+  ##
+  # Adds symlink +name+ with permissions +mode+, linking to +target+.
+
+  def add_symlink(name, target, mode)
+    check_closed
+
+    name, prefix = split_name name
+
+    header = Gem::Package::TarHeader.new(:name => name, :mode => mode,
+                                         :size => 0, :typeflag => "2",
+                                         :linkname => target,
+                                         :prefix => prefix,
+                                         :mtime => Time.now).to_s
+
+    @io.write header
+
+    self
+  end
+
   ##
   # Raises IOError if the TarWriter is closed
 
@@ -323,4 +342,3 @@ class Gem::Package::TarWriter
   end
 
 end
-
diff --git a/lib/rubygems/platform.rb b/lib/rubygems/platform.rb
index fa56141631..10d699d6b9 100644
--- a/lib/rubygems/platform.rb
+++ b/lib/rubygems/platform.rb
@@ -95,6 +95,7 @@ class Gem::Platform
                         [os, version]
                       when /netbsdelf/ then             [ 'netbsdelf', nil ]
                       when /openbsd(\d+\.\d+)?/ then    [ 'openbsd',   $1  ]
+                      when /bitrig(\d+\.\d+)?/ then     [ 'bitrig',    $1  ]
                       when /solaris(\d+\.\d+)?/ then    [ 'solaris',   $1  ]
                       # test
                       when /^(\w+_platform)(\d+)?/ then [ $1,          $2  ]
diff --git a/lib/rubygems/rdoc.rb b/lib/rubygems/rdoc.rb
index 180b95fbf3..7591346306 100644
--- a/lib/rubygems/rdoc.rb
+++ b/lib/rubygems/rdoc.rb
@@ -20,7 +20,7 @@ begin
   require 'rdoc/rubygems_hook'
   loaded_hook = true
   module Gem
-    RDoc = RDoc::RubygemsHook
+    RDoc = ::RDoc::RubygemsHook
   end
 rescue LoadError
 end
@@ -332,4 +332,3 @@ class Gem::RDoc # :nodoc: all
 end unless loaded_hook
 
 Gem.done_installing(&Gem::RDoc.method(:generation_hook))
-
diff --git a/lib/rubygems/request/connection_pools.rb b/lib/rubygems/request/connection_pools.rb
index 7a0a6e6e74..271b32b2b1 100644
--- a/lib/rubygems/request/connection_pools.rb
+++ b/lib/rubygems/request/connection_pools.rb
@@ -61,18 +61,22 @@ class Gem::Request::ConnectionPools # :nodoc:
   end
 
   def net_http_args uri, proxy_uri
-    net_http_args = [uri.host, uri.port]
+    # URI::Generic#hostname was added in ruby 1.9.3, use it if exists, otherwise
+    # don't support IPv6 literals and use host.
+    hostname = uri.respond_to?(:hostname) ? uri.hostname : uri.host
+    net_http_args = [hostname, uri.port]
 
     no_proxy = get_no_proxy_from_env
 
-    if proxy_uri and not no_proxy?(uri.host, no_proxy) then
+    if proxy_uri and not no_proxy?(hostname, no_proxy) then
+      proxy_hostname = proxy_uri.respond_to?(:hostname) ? proxy_uri.hostname : proxy_uri.host
       net_http_args + [
-        proxy_uri.host,
+        proxy_hostname,
         proxy_uri.port,
         Gem::UriFormatter.new(proxy_uri.user).unescape,
         Gem::UriFormatter.new(proxy_uri.password).unescape,
       ]
-    elsif no_proxy? uri.host, no_proxy then
+    elsif no_proxy? hostname, no_proxy then
       net_http_args + [nil, nil]
     else
       net_http_args
diff --git a/lib/rubygems/request_set.rb b/lib/rubygems/request_set.rb
index cfbc955ed9..12806836aa 100644
--- a/lib/rubygems/request_set.rb
+++ b/lib/rubygems/request_set.rb
@@ -159,16 +159,13 @@ class Gem::RequestSet
 
       path = req.download cache_dir
 
-      inst = Gem::Installer.new path, options
+      inst = Gem::Installer.at path, options
 
       yield req, inst if block_given?
 
       requests << inst.install
     end
 
-    requests
-  ensure
-    raise if $!
     return requests if options[:gemdeps]
 
     specs = requests.map do |request|
@@ -187,6 +184,8 @@ class Gem::RequestSet
     Gem.done_installing_hooks.each do |hook|
       hook.call inst, specs
     end unless Gem.done_installing_hooks.empty?
+
+    requests
   end
 
   ##
diff --git a/lib/rubygems/request_set/gem_dependency_api.rb b/lib/rubygems/request_set/gem_dependency_api.rb
index 6dd7892b4c..cf5c2185d9 100644
--- a/lib/rubygems/request_set/gem_dependency_api.rb
+++ b/lib/rubygems/request_set/gem_dependency_api.rb
@@ -174,7 +174,7 @@ class Gem::RequestSet::GemDependencyAPI
   ##
   # A Hash containing gem names and files to require from those gems.
 
-  attr_reader :requires # :nodoc:
+  attr_reader :requires
 
   ##
   # A set of gems that are loaded via the +:path+ option to #gem
diff --git a/lib/rubygems/request_set/lockfile.rb b/lib/rubygems/request_set/lockfile.rb
index 3c54785aad..b79a377248 100644
--- a/lib/rubygems/request_set/lockfile.rb
+++ b/lib/rubygems/request_set/lockfile.rb
@@ -185,7 +185,7 @@ class Gem::RequestSet::Lockfile
 
     platforms = platforms.sort_by { |platform| platform.to_s }
 
-    platforms.sort.each do |platform|
+    platforms.each do |platform|
       out << "  #{platform}"
     end
 
diff --git a/lib/rubygems/resolver.rb b/lib/rubygems/resolver.rb
index ef17d682ac..dcd1ade0d6 100644
--- a/lib/rubygems/resolver.rb
+++ b/lib/rubygems/resolver.rb
@@ -12,6 +12,7 @@ require 'net/http'
 # all the requirements.
 
 class Gem::Resolver
+  require 'rubygems/resolver/molinillo'
 
   ##
   # If the DEBUG_RESOLVER environment variable is set then debugging mode is
@@ -20,13 +21,6 @@ class Gem::Resolver
 
   DEBUG_RESOLVER = !ENV['DEBUG_RESOLVER'].nil?
 
-  require 'pp' if DEBUG_RESOLVER
-
-  ##
-  # Contains all the conflicts encountered while doing resolution
-
-  attr_reader :conflicts
-
   ##
   # Set to true if all development dependencies should be considered.
 
@@ -110,7 +104,6 @@ class Gem::Resolver
     @set = set || Gem::Resolver::IndexSet.new
     @needed = needed
 
-    @conflicts           = []
     @development         = false
     @development_shallow = false
     @ignore_dependencies = false
@@ -153,7 +146,7 @@ class Gem::Resolver
     return spec, activation_request
   end
 
-  def requests s, act, reqs=nil # :nodoc:
+  def requests s, act, reqs=[] # :nodoc:
     return reqs if @ignore_dependencies
 
     s.fetch_development_dependencies if @development
@@ -165,7 +158,7 @@ class Gem::Resolver
       next if d.type == :development and @development_shallow and
               act.parent
 
-      reqs.add Gem::Resolver::DependencyRequest.new(d, act)
+      reqs << Gem::Resolver::DependencyRequest.new(d, act)
       @stats.requirement!
     end
 
@@ -176,29 +169,27 @@ class Gem::Resolver
     reqs
   end
 
-  ##
-  # Proceed with resolution! Returns an array of ActivationRequest objects.
-
-  def resolve
-    @conflicts = []
-
-    needed = Gem::Resolver::RequirementList.new
+  include Molinillo::UI
 
-    @needed.reverse_each do |n|
-      request = Gem::Resolver::DependencyRequest.new n, nil
-
-      needed.add request
-      @stats.requirement!
-    end
+  def output
+    @output ||= debug? ? $stdout : File.open('/dev/null', 'w')
+  end
 
-    @stats.record_requirements needed
+  def debug?
+    DEBUG_RESOLVER
+  end
 
-    res = resolve_for needed, nil
+  include Molinillo::SpecificationProvider
 
-    raise Gem::DependencyResolutionError, res if
-      res.kind_of? Gem::Resolver::Conflict
+  ##
+  # Proceed with resolution! Returns an array of ActivationRequest objects.
 
-    res.to_a
+  def resolve
+    locking_dg = Molinillo::DependencyGraph.new
+    Molinillo::Resolver.new(self, self).resolve(@needed.map { |d| DependencyRequest.new d, nil }, locking_dg).tsort.map(&:payload)
+  rescue Molinillo::VersionConflict => e
+    conflict = e.conflicts.values.first
+    raise Gem::DependencyResolutionError, Conflict.new(conflict.requirement_trees.first.first, conflict.existing, conflict.requirement)
   end
 
   ##
@@ -221,232 +212,44 @@ class Gem::Resolver
     return matching_platform, all
   end
 
-  def handle_conflict(dep, existing) # :nodoc:
-    # There is a conflict! We return the conflict object which will be seen by
-    # the caller and be handled at the right level.
-
-    # If the existing activation indicates that there are other possibles for
-    # it, then issue the conflict on the dependency for the activation itself.
-    # Otherwise, if there was a requester, issue it on the requester's
-    # request itself.
-    # Finally, if the existing request has no requester (toplevel) unwind to
-    # it anyway.
-
-    if existing.others_possible?
-      conflict =
-        Gem::Resolver::Conflict.new dep, existing
-    elsif dep.requester
-      depreq = dep.requester.request
-      conflict =
-        Gem::Resolver::Conflict.new depreq, existing, dep
-    elsif existing.request.requester.nil?
-      conflict =
-        Gem::Resolver::Conflict.new dep, existing
-    else
-      raise Gem::DependencyError, "Unable to figure out how to unwind conflict"
-    end
-
-    @conflicts << conflict unless @conflicts.include? conflict
-
-    return conflict
-  end
-
-  # Contains the state for attempting activation of a set of possible specs.
-  # +needed+ is a Gem::List of DependencyRequest objects that, well, need
-  # to be satisfied.
-  # +specs+ is the List of ActivationRequest that are being tested.
-  # +dep+ is the DependencyRequest that was used to generate this state.
-  # +spec+ is the Specification for this state.
-  # +possible+ is List of DependencyRequest objects that can be tried to
-  # find a  complete set.
-  # +conflicts+ is a [DependencyRequest, Conflict] hit tried to
-  # activate the state.
-  #
-  State = Struct.new(:needed, :specs, :dep, :spec, :possibles, :conflicts) do
-    def summary # :nodoc:
-      nd = needed.map { |s| s.to_s }.sort if nd
-
-      if specs then
-        ss = specs.map { |s| s.full_name }.sort
-        ss.unshift ss.length
-      end
-
-      d = dep.to_s
-      d << " from #{dep.requester.full_name}" if dep.requester
-
-      ps = possibles.map { |p| p.full_name }.sort
-      ps.unshift ps.length
-
-      cs = conflicts.map do |(s, c)|
-        [s.full_name, c.conflicting_dependencies.map { |cd| cd.to_s }]
-      end
-
-      { :needed => nd, :specs => ss, :dep => d, :spec => spec.full_name,
-        :possibles => ps, :conflicts => cs }
-    end
-  end
-
   ##
-  # The meat of the algorithm. Given +needed+ DependencyRequest objects and
-  # +specs+ being a list to ActivationRequest, calculate a new list of
-  # ActivationRequest objects.
-
-  def resolve_for needed, specs # :nodoc:
-    # The State objects that are used to attempt the activation tree.
-    states = []
-
-    while !needed.empty?
-      @stats.iteration!
-
-      dep = needed.remove
-      explain :try, [dep, dep.requester ? dep.requester.request : :toplevel]
-      explain_list(:next5) { needed.next5 }
-      explain_list(:specs) { Array(specs).map { |x| x.full_name }.sort }
-
-      # If there is already a spec activated for the requested name...
-      if specs && existing = specs.find { |s| dep.name == s.name }
-        # then we're done since this new dep matches the existing spec.
-        next if dep.matches_spec? existing
-
-        conflict = handle_conflict dep, existing
-
-        return conflict unless dep.requester
-
-        explain :conflict, dep, :existing, existing.full_name
-
-        depreq = dep.requester.request
-
-        state = nil
-        until states.empty?
-          x = states.pop
-
-          i = existing.request.requester
-          explain :consider, x.spec.full_name, [depreq.name, dep.name, i ? i.name : :top]
-
-          if x.spec.name == depreq.name or
-              x.spec.name == dep.name or
-              (i && (i.name == x.spec.name))
-            explain :found, x.spec.full_name
-            state = x
-            break
-          end
-        end
-
-        return conflict unless state
-
-        @stats.backtracking!
-
-        needed, specs = resolve_for_conflict needed, specs, state
-
-        states << state unless state.possibles.empty?
-
-        next
-      end
-
-      matching, all = find_possible dep
+  # Returns the gems in +specs+ that match the local platform.
 
-      case matching.size
-      when 0
-        resolve_for_zero dep, all
-      when 1
-        needed, specs =
-          resolve_for_single needed, specs, dep, matching
-      else
-        needed, specs =
-          resolve_for_multiple needed, specs, states, dep, matching
-      end
+  def select_local_platforms specs # :nodoc:
+    specs.select do |spec|
+      Gem::Platform.installable? spec
     end
-
-    specs
-  end
-
-  ##
-  # Rewinds +needed+ and +specs+ to a previous state in +state+ for a conflict
-  # between +dep+ and +existing+.
-
-  def resolve_for_conflict needed, specs, state # :nodoc:
-    # We exhausted the possibles so it's definitely not going to work out,
-    # bail out.
-    raise Gem::ImpossibleDependenciesError.new state.dep, state.conflicts if
-      state.possibles.empty?
-
-    # Retry resolution with this spec and add it's dependencies
-    spec, act = activation_request state.dep, state.possibles
-
-    needed = requests spec, act, state.needed.dup
-    specs = Gem::List.prepend state.specs, act
-
-    return needed, specs
   end
 
-  ##
-  # There are multiple +possible+ specifications for this +dep+.  Updates
-  # +needed+, +specs+ and +states+ for further resolution of the +possible+
-  # choices.
-
-  def resolve_for_multiple needed, specs, states, dep, possible # :nodoc:
-    # Sort them so that we try the highest versions first.
-    possible = possible.sort_by do |s|
-      [s.source, s.version, s.platform == Gem::Platform::RUBY ? -1 : 1]
+  def search_for(dependency)
+    possibles, all = find_possible(dependency)
+    if !@soft_missing && possibles.empty?
+      @missing << dependency
+      exc = Gem::UnsatisfiableDependencyError.new dependency, all
+      exc.errors = @set.errors
+      raise exc
     end
-
-    spec, act = activation_request dep, possible
-
-    # We may need to try all of +possible+, so we setup state to unwind back
-    # to current +needed+ and +specs+ so we can try another. This is code is
-    # what makes conflict resolution possible.
-    states << State.new(needed.dup, specs, dep, spec, possible, [])
-
-    @stats.record_depth states
-
-    explain :states, states.map { |s| s.dep }
-
-    needed = requests spec, act, needed
-    specs = Gem::List.prepend specs, act
-
-    return needed, specs
+    possibles.sort_by { |s| [s.source, s.version, s.platform == Gem::Platform.local.to_s ? 1 : 0] }.
+      map { |s| ActivationRequest.new s, dependency, [] }
   end
 
-  ##
-  # Add the spec from the +possible+ list to +specs+ and process the spec's
-  # dependencies by adding them to +needed+.
-
-  def resolve_for_single needed, specs, dep, possible # :nodoc:
-    spec, act = activation_request dep, possible
-
-    specs = Gem::List.prepend specs, act
-
-    # Put the deps for at the beginning of needed
-    # rather than the end to match the depth first
-    # searching done by the multiple case code below.
-    #
-    # This keeps the error messages consistent.
-    needed = requests spec, act, needed
-
-    return needed, specs
+  def dependencies_for(specification)
+    return [] if @ignore_dependencies
+    spec = specification.spec
+    requests(spec, specification)
   end
 
-  ##
-  # When there are no possible specifications for +dep+ our work is done.
-
-  def resolve_for_zero dep, platform_mismatch # :nodoc:
-    @missing << dep
-
-    unless @soft_missing
-      exc = Gem::UnsatisfiableDependencyError.new dep, platform_mismatch
-      exc.errors = @set.errors
-
-      raise exc
-    end
+  def requirement_satisfied_by?(requirement, activated, spec)
+    requirement.matches_spec? spec
   end
 
-  ##
-  # Returns the gems in +specs+ that match the local platform.
+  def name_for(dependency)
+    dependency.name
+  end
 
-  def select_local_platforms specs # :nodoc:
-    specs.select do |spec|
-      Gem::Platform.installable? spec
-    end
+  def allow_missing?(dependency)
+    @missing << dependency
+    @soft_missing
   end
 
 end
@@ -482,4 +285,3 @@ require 'rubygems/resolver/installed_specification'
 require 'rubygems/resolver/local_specification'
 require 'rubygems/resolver/lock_specification'
 require 'rubygems/resolver/vendor_specification'
-
diff --git a/lib/rubygems/resolver/activation_request.rb b/lib/rubygems/resolver/activation_request.rb
index 56c6363e4f..03dd8d083b 100644
--- a/lib/rubygems/resolver/activation_request.rb
+++ b/lib/rubygems/resolver/activation_request.rb
@@ -67,6 +67,8 @@ class Gem::Resolver::ActivationRequest
     @spec.full_name
   end
 
+  alias_method :to_s, :full_name
+
   ##
   # The Gem::Specification for this activation request.
 
@@ -169,4 +171,3 @@ class Gem::Resolver::ActivationRequest
   end
 
 end
-
diff --git a/lib/rubygems/resolver/conflict.rb b/lib/rubygems/resolver/conflict.rb
index 902c286b6b..0b6c704d6a 100644
--- a/lib/rubygems/resolver/conflict.rb
+++ b/lib/rubygems/resolver/conflict.rb
@@ -157,4 +157,3 @@ end
 # TODO: Remove in RubyGems 3
 
 Gem::Resolver::DependencyConflict = Gem::Resolver::Conflict # :nodoc:
-
diff --git a/lib/rubygems/resolver/dependency_request.rb b/lib/rubygems/resolver/dependency_request.rb
index 79690bec4c..6c6ea8f4da 100644
--- a/lib/rubygems/resolver/dependency_request.rb
+++ b/lib/rubygems/resolver/dependency_request.rb
@@ -67,6 +67,10 @@ class Gem::Resolver::DependencyRequest
     @dependency.name
   end
 
+  def type
+    @dependency.type
+  end
+
   ##
   # Indicate that the request is for a gem explicitly requested by the user
 
@@ -113,4 +117,3 @@ class Gem::Resolver::DependencyRequest
   end
 
 end
-
diff --git a/lib/rubygems/resolver/git_specification.rb b/lib/rubygems/resolver/git_specification.rb
index 55e180e525..dcfb2ad855 100644
--- a/lib/rubygems/resolver/git_specification.rb
+++ b/lib/rubygems/resolver/git_specification.rb
@@ -23,8 +23,7 @@ class Gem::Resolver::GitSpecification < Gem::Resolver::SpecSpecification
   def install options = {}
     require 'rubygems/installer'
 
-    installer = Gem::Installer.new '', options
-    installer.spec = spec
+    installer = Gem::Installer.for_spec spec, options
 
     yield installer if block_given?
 
diff --git a/lib/rubygems/resolver/molinillo.rb b/lib/rubygems/resolver/molinillo.rb
new file mode 100644
index 0000000000..24ac0f9b2d
--- /dev/null
+++ b/lib/rubygems/resolver/molinillo.rb
@@ -0,0 +1 @@
+require 'rubygems/resolver/molinillo/lib/molinillo'
diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo.rb b/lib/rubygems/resolver/molinillo/lib/molinillo.rb
new file mode 100644
index 0000000000..47b4518321
--- /dev/null
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo.rb
@@ -0,0 +1,5 @@
+require 'rubygems/resolver/molinillo/lib/molinillo/gem_metadata'
+require 'rubygems/resolver/molinillo/lib/molinillo/errors'
+require 'rubygems/resolver/molinillo/lib/molinillo/resolver'
+require 'rubygems/resolver/molinillo/lib/molinillo/modules/ui'
+require 'rubygems/resolver/molinillo/lib/molinillo/modules/specification_provider'
diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb
new file mode 100644
index 0000000000..b6db1b7417
--- /dev/null
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb
@@ -0,0 +1,266 @@
+require 'set'
+require 'tsort'
+
+module Gem::Resolver::Molinillo
+  # A directed acyclic graph that is tuned to hold named dependencies
+  class DependencyGraph
+    include Enumerable
+
+    # Enumerates through the vertices of the graph.
+    # @return [Array<Vertex>] The graph's vertices.
+    def each
+      vertices.values.each { |v| yield v }
+    end
+
+    include TSort
+
+    alias_method :tsort_each_node, :each
+
+    def tsort_each_child(vertex, &block)
+      vertex.successors.each(&block)
+    end
+
+    # Topologically sorts the given vertices.
+    # @param [Enumerable<Vertex>] vertices the vertices to be sorted, which must
+    #   all belong to the same graph.
+    # @return [Array<Vertex>] The sorted vertices.
+    def self.tsort(vertices)
+      TSort.tsort(
+        lambda { |b| vertices.each(&b) },
+        lambda { |v, &b| (v.successors & vertices).each(&b) }
+      )
+    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/rubygems/resolver/molinillo/lib/molinillo/errors.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/errors.rb
new file mode 100644
index 0000000000..cc9f636ed5
--- /dev/null
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo/errors.rb
@@ -0,0 +1,69 @@
+module Gem::Resolver::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/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb
new file mode 100644
index 0000000000..8568c623e6
--- /dev/null
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb
@@ -0,0 +1,3 @@
+module Gem::Resolver::Molinillo
+  VERSION = '0.3.0'
+end
diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/modules/specification_provider.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/modules/specification_provider.rb
new file mode 100644
index 0000000000..848392b215
--- /dev/null
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo/modules/specification_provider.rb
@@ -0,0 +1,99 @@
+module Gem::Resolver::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 Gem::Resolver::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
+
+    # Returns whether this dependency, which has no possible matching
+    # specifications, can safely be ignored.
+    #
+    # @param [Object] dependency
+    # @return [Boolean] whether this dependency can safely be skipped.
+    def allow_missing?(dependency)
+      false
+    end
+  end
+end
diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/modules/ui.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/modules/ui.rb
new file mode 100644
index 0000000000..18f5363950
--- /dev/null
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo/modules/ui.rb
@@ -0,0 +1,63 @@
+module Gem::Resolver::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/rubygems/resolver/molinillo/lib/molinillo/resolution.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb
new file mode 100644
index 0000000000..712864495f
--- /dev/null
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb
@@ -0,0 +1,430 @@
+module Gem::Resolver::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
+
+      # @return [Integer] the number of resolver iterations in between calls to
+      #   {#resolver_ui}'s {UI#indicate_progress} method
+      attr_accessor :iteration_rate
+      private :iteration_rate
+
+      # @return [Time] the time at which resolution began
+      attr_accessor :started_at
+      private :started_at
+
+      # @return [Array<ResolutionState>] the stack of states for the resolution
+      attr_accessor :states
+      private :states
+
+      private
+
+      # Sets up the resolution process
+      # @return [void]
+      def start_resolution
+        @started_at = Time.now
+
+        handle_missing_or_push_dependency_state(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 'rubygems/resolver/molinillo/lib/molinillo/state'
+      require 'rubygems/resolver/molinillo/lib/molinillo/modules/specification_provider'
+
+      ResolutionState.new.members.each do |member|
+        define_method member do |*args, &block|
+          current_state = state || ResolutionState.empty
+          current_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.reverse_each.find { |i| requirement == i.requirement && i.is_a?(DependencyState) }
+      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
+          return if attempt_to_swap_possibility
+          create_conflict
+          debug(depth) { "Unsatisfied by existing spec (#{existing_node.payload})" }
+          unwind_for_conflict
+        end
+      end
+
+      # Attempts to swp the current {#possibility} with the already-activated
+      # spec with the given name
+      # @return [Boolean] Whether the possibility was swapped into {#activated}
+      def attempt_to_swap_possibility
+        swapped = activated.dup
+        swapped.vertex_named(name).payload = possibility
+        return unless swapped.vertex_named(name).requirements.
+            all? { |r| requirement_satisfied_by?(r, swapped, possibility) }
+        attempt_to_activate_new_spec
+      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_activated = activated.dup)
+        new_requirements = sort_dependencies(new_requirements.uniq, new_activated, conflicts)
+        new_requirement = new_requirements.shift
+        new_name = new_requirement ? name_for(new_requirement) : ''
+        possibilities = new_requirement ? search_for(new_requirement) : []
+        handle_missing_or_push_dependency_state DependencyState.new(
+          new_name, new_requirements, new_activated,
+          new_requirement, possibilities, depth, conflicts.dup
+        )
+      end
+
+      # Pushes a new {DependencyState}.
+      # If the {#specification_provider} says to
+      # {SpecificationProvider#allow_missing?} that particular requirement, and
+      # there are no possibilities for that requirement, then `state` is not
+      # pushed, and the node in {#activated} is removed, and we continue
+      # resolving the remaining requirements.
+      # @param [DependencyState] state
+      # @return [void]
+      def handle_missing_or_push_dependency_state(state)
+        if state.requirement && state.possibilities.empty? && allow_missing?(state.requirement)
+          state.activated.detach_vertex_named(state.name)
+          push_state_for_requirements(state.requirements, state.activated)
+        else
+          states.push state
+        end
+      end
+    end
+  end
+end
diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/resolver.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/resolver.rb
new file mode 100644
index 0000000000..b22caf44da
--- /dev/null
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo/resolver.rb
@@ -0,0 +1,43 @@
+require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph'
+
+module Gem::Resolver::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 'rubygems/resolver/molinillo/lib/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/rubygems/resolver/molinillo/lib/molinillo/state.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/state.rb
new file mode 100644
index 0000000000..f0317185ab
--- /dev/null
+++ b/lib/rubygems/resolver/molinillo/lib/molinillo/state.rb
@@ -0,0 +1,51 @@
+module Gem::Resolver::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
+  )
+
+  class ResolutionState
+    # Returns an empty resolution state
+    # @return [ResolutionState] an empty state
+    def self.empty
+      new(nil, [], DependencyGraph.new, nil, nil, 0, Set.new)
+    end
+  end
+
+  # 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/rubygems/resolver/specification.rb b/lib/rubygems/resolver/specification.rb
index 4d77293262..9b597f1916 100644
--- a/lib/rubygems/resolver/specification.rb
+++ b/lib/rubygems/resolver/specification.rb
@@ -89,7 +89,7 @@ class Gem::Resolver::Specification
 
     gem = source.download spec, destination
 
-    installer = Gem::Installer.new gem, options
+    installer = Gem::Installer.at gem, options
 
     yield installer if block_given?
 
diff --git a/lib/rubygems/specification.rb b/lib/rubygems/specification.rb
index b73c563e2e..5ddf5fd931 100644
--- a/lib/rubygems/specification.rb
+++ b/lib/rubygems/specification.rb
@@ -12,7 +12,8 @@ require 'rubygems/platform'
 require 'rubygems/deprecate'
 require 'rubygems/basic_specification'
 require 'rubygems/stub_specification'
-require 'rubygems/util/stringio'
+require 'rubygems/util/list'
+require 'stringio'
 
 ##
 # The Specification class contains the information for a Gem.  Typically
@@ -172,6 +173,8 @@ class Gem::Specification < Gem::BasicSpecification
     @@default_value[k].nil?
   }
 
+  @@stubs_by_name = {}
+
   ######################################################################
   # :section: Required gemspec attributes
 
@@ -345,7 +348,7 @@ class Gem::Specification < Gem::BasicSpecification
               add_bindir(@executables),
               @extra_rdoc_files,
               @extensions,
-             ].flatten.uniq.compact.sort
+             ].flatten.compact.uniq.sort
   end
 
   ######################################################################
@@ -729,12 +732,57 @@ class Gem::Specification < Gem::BasicSpecification
     end
   end
 
-  def self.each_stub(dirs) # :nodoc:
-    each_gemspec(dirs) do |path|
-      stub = Gem::StubSpecification.new(path)
-      yield stub if stub.valid?
+  def self.gemspec_stubs_in dir, pattern
+    Dir[File.join(dir, pattern)].map { |path|
+      if dir == default_specifications_dir
+        Gem::StubSpecification.default_gemspec_stub(path)
+      else
+        Gem::StubSpecification.gemspec_stub(path)
+      end
+    }.select(&:valid?)
+  end
+  private_class_method :gemspec_stubs_in
+
+  if [].respond_to? :flat_map
+    def self.map_stubs(dirs, pattern) # :nodoc:
+      dirs.flat_map { |dir| gemspec_stubs_in(dir, pattern) }
+    end
+  else # FIXME: remove when 1.8 is dropped
+    def self.map_stubs(dirs, pattern) # :nodoc:
+      dirs.map { |dir| gemspec_stubs_in(dir, pattern) }.flatten 1
     end
   end
+  private_class_method :map_stubs
+
+  uniq_takes_a_block = false
+  [1,2].uniq { uniq_takes_a_block = true }
+
+  if uniq_takes_a_block
+    def self.uniq_by(list, &block) # :nodoc:
+      list.uniq(&block)
+    end
+  else # FIXME: remove when 1.8 is dropped
+    def self.uniq_by(list) # :nodoc:
+      values = {}
+      list.each { |item|
+        value = yield item
+        values[value] ||= item
+      }
+      values.values
+    end
+  end
+  private_class_method :uniq_by
+
+  if [].respond_to? :sort_by!
+    def self.sort_by! list, &block
+      list.sort_by!(&block)
+    end
+  else # FIXME: remove when 1.8 is dropped
+    def self.sort_by! list, &block
+      list.replace list.sort_by(&block)
+    end
+  end
+  private_class_method :sort_by!
 
   def self.each_spec(dirs) # :nodoc:
     each_gemspec(dirs) do |path|
@@ -748,17 +796,33 @@ class Gem::Specification < Gem::BasicSpecification
 
   def self.stubs
     @@stubs ||= begin
-      stubs = {}
-      each_stub([default_specifications_dir] + dirs) do |stub|
-        stubs[stub.full_name] ||= stub
-      end
+      stubs = map_stubs([default_specifications_dir] + dirs, "*.gemspec")
+      stubs = uniq_by(stubs) { |stub| stub.full_name }
 
-      stubs = stubs.values
       _resort!(stubs)
+      @@stubs_by_name = stubs.group_by(&:name)
       stubs
     end
   end
 
+  EMPTY = [].freeze # :nodoc:
+
+  ##
+  # Returns a Gem::StubSpecification for installed gem named +name+
+
+  def self.stubs_for name
+    if @@stubs || @@stubs_by_name[name]
+      @@stubs_by_name[name] || []
+    else
+      stubs = map_stubs([default_specifications_dir] + dirs, "#{name}-*.gemspec")
+      stubs = uniq_by(stubs) { |stub| stub.full_name }.group_by(&:name)
+      stubs.each_value { |v| sort_by!(v) { |i| i.version } }
+
+      @@stubs_by_name.merge! stubs
+      @@stubs_by_name[name] ||= EMPTY
+    end
+  end
+
   def self._resort!(specs) # :nodoc:
     specs.sort! { |a, b|
       names = a.name <=> b.name
@@ -783,6 +847,7 @@ class Gem::Specification < Gem::BasicSpecification
   # properly sorted.
 
   def self.add_spec spec
+    warn "Gem::Specification.add_spec is deprecated and will be removed in Rubygems 3.0" unless Gem::Deprecate.skip
     # TODO: find all extraneous adds
     # puts
     # p :add_spec => [spec.full_name, caller.reject { |s| s =~ /minitest/ }]
@@ -797,6 +862,8 @@ class Gem::Specification < Gem::BasicSpecification
 
     _all << spec
     stubs << spec
+    (@@stubs_by_name[spec.name] ||= []) << spec
+    sort_by!(@@stubs_by_name[spec.name]) { |s| s.version }
     _resort!(_all)
     _resort!(stubs)
   end
@@ -805,14 +872,18 @@ class Gem::Specification < Gem::BasicSpecification
   # Adds multiple specs to the known specifications.
 
   def self.add_specs *specs
+    warn "Gem::Specification.add_specs is deprecated and will be removed in Rubygems 3.0" unless Gem::Deprecate.skip
+
     raise "nil spec!" if specs.any?(&:nil?) # TODO: remove once we're happy
 
     # TODO: this is much more efficient, but we need the extra checks for now
     # _all.concat specs
     # _resort!
 
-    specs.each do |spec| # TODO: slow
-      add_spec spec
+    Gem::Deprecate.skip_during do
+      specs.each do |spec| # TODO: slow
+        add_spec spec
+      end
     end
   end
 
@@ -839,6 +910,7 @@ class Gem::Specification < Gem::BasicSpecification
   # -- wilsonb
 
   def self.all= specs
+    @@stubs_by_name = specs.group_by(&:name)
     @@all = @@stubs = specs
   end
 
@@ -927,9 +999,10 @@ class Gem::Specification < Gem::BasicSpecification
   # Return the best specification that contains the file matching +path+.
 
   def self.find_by_path path
-    self.find { |spec|
+    stub = stubs.find { |spec|
       spec.contains_requirable_file? path
     }
+    stub && stub.to_spec
   end
 
   ##
@@ -961,15 +1034,13 @@ class Gem::Specification < Gem::BasicSpecification
     specs = unresolved_deps.values.map { |dep| dep.to_specs }.flatten
 
     specs.reverse_each do |spec|
-      trails = []
       spec.traverse do |from_spec, dep, to_spec, trail|
-        next unless to_spec.conflicts.empty?
-        trails << trail if to_spec.contains_requirable_file? path
+        if to_spec.has_conflicts? || to_spec.conficts_when_loaded_with?(trail)
+          :next
+        else
+          return trail.reverse if to_spec.contains_requirable_file? path
+        end
       end
-
-      next if trails.empty?
-
-      return trails.map(&:reverse).sort.first.reverse
     end
 
     []
@@ -1008,10 +1079,14 @@ class Gem::Specification < Gem::BasicSpecification
   # +prerelease+ is true.
 
   def self.latest_specs prerelease = false
+    _latest_specs Gem::Specification._all, prerelease
+  end
+
+  def self._latest_specs specs, prerelease = false # :nodoc:
     result = Hash.new { |h,k| h[k] = {} }
     native = {}
 
-    Gem::Specification.reverse_each do |spec|
+    specs.reverse_each do |spec|
       next if spec.version.prerelease? unless prerelease
 
       native[spec.name] = spec.version if spec.platform == Gem::Platform::RUBY
@@ -1029,12 +1104,13 @@ class Gem::Specification < Gem::BasicSpecification
 
   def self.load file
     return unless file
-    file = file.dup.untaint
-    return unless File.file?(file)
 
     _spec = LOAD_CACHE[file]
     return _spec if _spec
 
+    file = file.dup.untaint
+    return unless File.file?(file)
+
     code = if defined? Encoding
              File.read file, :mode => 'r:UTF-8:-'
            else
@@ -1126,8 +1202,11 @@ class Gem::Specification < Gem::BasicSpecification
   # Removes +spec+ from the known specs.
 
   def self.remove_spec spec
+    warn "Gem::Specification.remove_spec is deprecated and will be removed in Rubygems 3.0" unless Gem::Deprecate.skip
     _all.delete spec
     stubs.delete_if { |s| s.full_name == spec.full_name }
+    (@@stubs_by_name[spec.name] || []).delete_if { |s| s.full_name == spec.full_name }
+    reset
   end
 
   ##
@@ -1153,6 +1232,7 @@ class Gem::Specification < Gem::BasicSpecification
     Gem.pre_reset_hooks.each { |hook| hook.call }
     @@all = nil
     @@stubs = nil
+    @@stubs_by_name = {}
     _clear_load_cache
     unresolved = unresolved_deps
     unless unresolved.empty? then
@@ -1563,6 +1643,30 @@ class Gem::Specification < Gem::BasicSpecification
     conflicts
   end
 
+  ##
+  # return true if there will be conflict when spec if loaded together with the list of specs.
+
+  def conficts_when_loaded_with?(list_of_specs) # :nodoc:
+    result = list_of_specs.any? { |spec|
+      spec.dependencies.any? { |dep| dep.runtime? && (dep.name == name) && !satisfies_requirement?(dep) }
+    }
+    result
+  end
+
+  ##
+  # Return true if there are possible conflicts against the currently loaded specs.
+
+  def has_conflicts?
+    self.dependencies.any? { |dep|
+      if dep.runtime? then
+        spec = Gem.loaded_specs[dep.name]
+        spec and not spec.satisfies_requirement? dep
+      else
+        false
+      end
+    }
+  end
+
   ##
   # The date this gem was created.  Lazily defaults to the current UTC date.
   #
@@ -1883,9 +1987,10 @@ class Gem::Specification < Gem::BasicSpecification
   # +version+.
 
   def initialize name = nil, version = nil
+    super()
     @loaded = false
     @activated = false
-    self.loaded_from = nil
+    @loaded_from = nil
     @original_platform = nil
     @installed_by_version = nil
 
@@ -1951,20 +2056,6 @@ class Gem::Specification < Gem::BasicSpecification
     end
   end
 
-  ##
-  # Returns a string usable in Dir.glob to match all requirable paths
-  # for this spec.
-
-  def lib_dirs_glob
-    dirs = if self.require_paths.size > 1 then
-             "{#{self.require_paths.join(',')}}"
-           else
-             self.require_paths.first
-           end
-
-    "#{self.full_gem_path}/#{dirs}"
-  end
-
   ##
   # Files in the Gem under one of the require_paths
 
@@ -1992,9 +2083,8 @@ class Gem::Specification < Gem::BasicSpecification
     @licenses ||= []
   end
 
-  def loaded_from= path # :nodoc:
+  def internal_init # :nodoc:
     super
-
     @bin_dir       = nil
     @cache_dir     = nil
     @cache_file    = nil
@@ -2011,16 +2101,6 @@ class Gem::Specification < Gem::BasicSpecification
     @rubygems_version = Gem::VERSION
   end
 
-  ##
-  # Return all files in this gem that match for +glob+.
-
-  def matches_for_glob glob # TODO: rename?
-    # TODO: do we need these?? Kill it
-    glob = File.join(self.lib_dirs_glob, glob)
-
-    Dir[glob].map { |f| f.untaint } # FIX our tests are broken, run w/ SAFE=1
-  end
-
   ##
   # Warn about unknown attributes while loading a spec.
 
@@ -2154,10 +2234,8 @@ class Gem::Specification < Gem::BasicSpecification
   # Check the spec for possible conflicts and freak out if there are any.
 
   def raise_if_conflicts # :nodoc:
-    conf = self.conflicts
-
-    unless conf.empty? then
-      raise Gem::ConflictError.new self, conf
+    if has_conflicts? then
+      raise Gem::ConflictError.new self, conflicts
     end
   end
 
@@ -2234,7 +2312,7 @@ class Gem::Specification < Gem::BasicSpecification
   # List of dependencies that will automatically be activated at runtime.
 
   def runtime_dependencies
-    dependencies.select { |d| d.type == :runtime }
+    dependencies.select(&:runtime?)
   end
 
   ##
@@ -2461,7 +2539,7 @@ class Gem::Specification < Gem::BasicSpecification
       builder << self
       ast = builder.tree
 
-      io = Gem::StringSink.new
+      io = StringIO.new
       io.set_encoding Encoding::UTF_8 if Object.const_defined? :Encoding
 
       Psych::Visitors::Emitter.new(io).accept(ast)
@@ -2480,14 +2558,28 @@ class Gem::Specification < Gem::BasicSpecification
   # Recursively walk dependencies of this spec, executing the +block+ for each
   # hop.
 
-  def traverse trail = [], &block
-    trail = trail + [self]
-    runtime_dependencies.each do |dep|
-      dep.to_specs.each do |dep_spec|
-        block[self, dep, dep_spec, trail + [dep_spec]]
-        dep_spec.traverse(trail, &block) unless
-          trail.map(&:name).include? dep_spec.name
+  def traverse trail = [], visited = {}, &block
+    trail.push(self)
+    begin
+      dependencies.each do |dep|
+        dep.to_specs.reverse_each do |dep_spec|
+          next if visited.has_key?(dep_spec)
+          visited[dep_spec] = true
+          trail.push(dep_spec)
+          begin
+            result = block[self, dep, dep_spec, trail]
+          ensure
+            trail.pop
+          end
+          unless result == :next
+            spec_name = dep_spec.name
+            dep_spec.traverse(trail, visited, &block) unless
+              trail.any? { |s| s.name == spec_name }
+          end
+        end
       end
+    ensure
+      trail.pop
     end
   end
 
@@ -2535,13 +2627,13 @@ class Gem::Specification < Gem::BasicSpecification
             'specification must have at least one require_path'
     end
 
-    @files.delete_if            { |x| File.directory?(x) }
-    @test_files.delete_if       { |x| File.directory?(x) }
+    @files.delete_if            { |x| File.directory?(x) && !File.symlink?(x) }
+    @test_files.delete_if       { |x| File.directory?(x) && !File.symlink?(x) }
     @executables.delete_if      { |x| File.directory?(File.join(@bindir, x)) }
-    @extra_rdoc_files.delete_if { |x| File.directory?(x) }
-    @extensions.delete_if       { |x| File.directory?(x) }
+    @extra_rdoc_files.delete_if { |x| File.directory?(x) && !File.symlink?(x) }
+    @extensions.delete_if       { |x| File.directory?(x) && !File.symlink?(x) }
 
-    non_files = files.reject { |x| File.file?(x) }
+    non_files = files.reject { |x| File.file?(x) || File.symlink?(x) }
 
     unless not packaging or non_files.empty? then
       raise Gem::InvalidSpecificationException,
@@ -2676,6 +2768,11 @@ http://opensource.org/licenses/alphabetical
       warning "#{executable_path} is missing #! line" unless shebang
     end
 
+    files.each do |file|
+      next unless File.symlink?(file)
+      warning "#{file} is a symlink, which is not supported on all platforms"
+    end
+
     validate_dependencies
 
     true
@@ -2761,12 +2858,14 @@ open-ended dependency on #{dep} is not recommended
     return if Gem.win_platform?
 
     files.each do |file|
+      next unless File.file?(file)
       next if File.stat(file).mode & 0444 == 0444
       warning "#{file} is not world-readable"
     end
 
     executables.each do |name|
       exec = File.join @bindir, name
+      next unless File.file?(exec)
       next if File.stat(exec).executable?
       warning "#{exec} is not executable"
     end
diff --git a/lib/rubygems/stub_specification.rb b/lib/rubygems/stub_specification.rb
index b184d29d5e..ed07e8011f 100644
--- a/lib/rubygems/stub_specification.rb
+++ b/lib/rubygems/stub_specification.rb
@@ -15,35 +15,32 @@ class Gem::StubSpecification < Gem::BasicSpecification
     end
 
   class StubLine # :nodoc: all
-    attr_reader :parts
+    attr_reader :name, :version, :platform, :require_paths
 
     def initialize(data)
-      @parts = data[PREFIX.length..-1].split(" ")
-    end
-
-    def name
-      @parts[0]
-    end
-
-    def version
-      Gem::Version.new @parts[1]
+      parts          = data[PREFIX.length..-1].split(" ")
+      @name          = parts[0]
+      @version       = Gem::Version.new parts[1]
+      @platform      = Gem::Platform.new parts[2]
+      @require_paths = parts.drop(3).join(" ").split("\0")
     end
+  end
 
-    def platform
-      Gem::Platform.new @parts[2]
-    end
+  def self.default_gemspec_stub filename
+    new filename, true
+  end
 
-    def require_paths
-      @parts[3..-1].join(" ").split("\0")
-    end
+  def self.gemspec_stub filename
+    new filename, false
   end
 
-  def initialize(filename)
+  def initialize filename, default_gem
     self.loaded_from = filename
     @data            = nil
     @extensions      = nil
     @name            = nil
     @spec            = nil
+    @default_gem     = default_gem
   end
 
   ##
@@ -57,6 +54,10 @@ class Gem::StubSpecification < Gem::BasicSpecification
     end
   end
 
+  def default_gem?
+    @default_gem
+  end
+
   def build_extensions # :nodoc:
     return if default_gem?
     return if extensions.empty?
@@ -135,14 +136,14 @@ class Gem::StubSpecification < Gem::BasicSpecification
   # Name of the gem
 
   def name
-    @name ||= data.name
+    data.name
   end
 
   ##
   # Platform of the gem
 
   def platform
-    @platform ||= data.platform
+    data.platform
   end
 
   ##
diff --git a/lib/rubygems/test_case.rb b/lib/rubygems/test_case.rb
index 306edcc3f6..aee4b75773 100644
--- a/lib/rubygems/test_case.rb
+++ b/lib/rubygems/test_case.rb
@@ -36,6 +36,7 @@ require 'shellwords'
 require 'tmpdir'
 require 'uri'
 require 'zlib'
+require 'benchmark' # stdlib
 
 Gem.load_yaml
 
@@ -275,6 +276,7 @@ class Gem::TestCase < MiniTest::Unit::TestCase
     @orig_ENV_HOME = ENV['HOME']
     ENV['HOME'] = @userhome
     Gem.instance_variable_set :@user_home, nil
+    Gem.instance_variable_set :@gemdeps, nil
     Gem.send :remove_instance_variable, :@ruby_version if
       Gem.instance_variables.include? :@ruby_version
 
@@ -329,6 +331,7 @@ class Gem::TestCase < MiniTest::Unit::TestCase
     end
 
     @marshal_version = "#{Marshal::MAJOR_VERSION}.#{Marshal::MINOR_VERSION}"
+    @orig_LOADED_FEATURES = $LOADED_FEATURES.dup
   end
 
   ##
@@ -337,6 +340,7 @@ class Gem::TestCase < MiniTest::Unit::TestCase
 
   def teardown
     $LOAD_PATH.replace @orig_LOAD_PATH if @orig_LOAD_PATH
+    $LOADED_FEATURES.replace @orig_LOADED_FEATURES if @orig_LOADED_FEATURES
 
     if @orig_BASERUBY
       RbConfig::CONFIG['BASERUBY'] = @orig_BASERUBY
@@ -373,6 +377,7 @@ class Gem::TestCase < MiniTest::Unit::TestCase
     ENV['GEM_PRIVATE_KEY_PASSPHRASE'] = @orig_gem_private_key_passphrase
 
     Gem::Specification._clear_load_cache
+    Gem::Specification.unresolved_deps.clear
   end
 
   def common_installer_setup
@@ -488,7 +493,7 @@ class Gem::TestCase < MiniTest::Unit::TestCase
       gem = File.join(@tempdir, File.basename(spec.cache_file)).untaint
     end
 
-    Gem::Installer.new(gem, options.merge({:wrappers => true})).install
+    Gem::Installer.at(gem, options.merge({:wrappers => true})).install
   end
 
   ##
@@ -503,8 +508,11 @@ class Gem::TestCase < MiniTest::Unit::TestCase
   def uninstall_gem spec
     require 'rubygems/uninstaller'
 
-    Gem::Uninstaller.new(spec.name,
-                         :executables => true, :user_install => true).uninstall
+    Class.new(Gem::Uninstaller) {
+      def ask_if_ok spec
+        true
+      end
+    }.new(spec.name, :executables => true, :user_install => true).uninstall
   end
 
   ##
@@ -598,7 +606,7 @@ class Gem::TestCase < MiniTest::Unit::TestCase
 
     spec.loaded_from = spec.loaded_from = written_path
 
-    Gem::Specification.add_spec spec.for_cache
+    Gem::Specification.reset
 
     return spec
   end
@@ -654,7 +662,10 @@ class Gem::TestCase < MiniTest::Unit::TestCase
   # Install the provided specs
 
   def install_specs(*specs)
-    Gem::Specification.add_specs(*specs)
+    specs.each do |spec|
+      Gem::Installer.for_spec(spec).install
+    end
+
     Gem.searcher = nil
   end
 
@@ -675,8 +686,9 @@ class Gem::TestCase < MiniTest::Unit::TestCase
   # Install the provided default specs
 
   def install_default_specs(*specs)
-    install_specs(*specs)
     specs.each do |spec|
+      installer = Gem::Installer.for_spec(spec, :install_as_default => true)
+      installer.install
       Gem.register_default_spec(spec)
     end
   end
@@ -788,9 +800,7 @@ class Gem::TestCase < MiniTest::Unit::TestCase
       end
     end
 
-    spec.loaded_from = spec.spec_file
-
-    Gem::Specification.add_spec spec
+    Gem::Specification.reset
 
     return spec
   end
@@ -977,14 +987,13 @@ Also, a list:
   # Best used with +@all_gems+ from #util_setup_fake_fetcher.
 
   def util_setup_spec_fetcher(*specs)
-    specs -= Gem::Specification._all
-    Gem::Specification.add_specs(*specs)
+    all_specs = Gem::Specification.to_a + specs
+    Gem::Specification._resort! all_specs
 
     spec_fetcher = Gem::SpecFetcher.fetcher
 
-    prerelease, all = Gem::Specification.partition { |spec|
-      spec.version.prerelease?
-    }
+    prerelease, all = all_specs.partition { |spec| spec.version.prerelease?  }
+    latest = Gem::Specification._latest_specs all_specs
 
     spec_fetcher.specs[@uri] = []
     all.each do |spec|
@@ -992,7 +1001,7 @@ Also, a list:
     end
 
     spec_fetcher.latest_specs[@uri] = []
-    Gem::Specification.latest_specs.each do |spec|
+    latest.each do |spec|
       spec_fetcher.latest_specs[@uri] << spec.name_tuple
     end
 
@@ -1008,7 +1017,7 @@ Also, a list:
       specs = all.map { |spec| spec.name_tuple }
       s_zip = util_gzip Marshal.dump Gem::NameTuple.to_basic specs
 
-      latest_specs = Gem::Specification.latest_specs.map do |spec|
+      latest_specs = latest.map do |spec|
         spec.name_tuple
       end
 
@@ -1023,7 +1032,7 @@ Also, a list:
 
       v = Gem.marshal_version
 
-      Gem::Specification.each do |spec|
+      all_specs.each do |spec|
         path = "#{@gem_repo}quick/Marshal.#{v}/#{spec.original_name}.gemspec.rz"
         data = Marshal.dump spec
         data_deflate = Zlib::Deflate.deflate data
@@ -1450,6 +1459,12 @@ begin
 rescue LoadError, Gem::LoadError
 end
 
+begin
+  gem 'builder'
+  require 'builder/xchar'
+rescue LoadError, Gem::LoadError
+end
+
 require 'rubygems/test_utilities'
 tmpdirs = []
 tmpdirs << (ENV['GEM_HOME'] = Dir.mktmpdir("home"))
diff --git a/lib/rubygems/test_utilities.rb b/lib/rubygems/test_utilities.rb
index 25786e6a21..6789f6efc5 100644
--- a/lib/rubygems/test_utilities.rb
+++ b/lib/rubygems/test_utilities.rb
@@ -186,7 +186,6 @@ end
 #     f.gem  'a', 1
 #     f.spec 'a', 2
 #     f.gem  'b', 1' 'a' => '~> 1.0'
-#     f.clear
 #   end
 #
 # The above declaration creates two gems, a-1 and b-1, with a dependency from
@@ -214,18 +213,11 @@ class Gem::TestCase::SpecFetcherSetup
     @repository = repository
 
     @gems       = {}
+    @downloaded = []
     @installed  = []
     @operations = []
   end
 
-  ##
-  # Removes any created gems or specifications from Gem.dir (the default
-  # install location).
-
-  def clear
-    @operations << [:clear]
-  end
-
   ##
   # Returns a Hash of created Specification full names and the corresponding
   # Specification.
@@ -254,9 +246,6 @@ class Gem::TestCase::SpecFetcherSetup
   def execute_operations # :nodoc:
     @operations.each do |operation, *arguments|
       case operation
-      when :clear then
-        @test.util_clear_gems
-        @installed.clear
       when :gem then
         spec, gem = @test.util_gem(*arguments, &arguments.pop)
 
@@ -264,6 +253,11 @@ class Gem::TestCase::SpecFetcherSetup
 
         @gems[spec] = gem
         @installed << spec
+      when :download then
+        spec, gem = @test.util_gem(*arguments, &arguments.pop)
+
+        @gems[spec] = gem
+        @downloaded << spec
       when :spec then
         spec = @test.util_spec(*arguments, &arguments.pop)
 
@@ -286,6 +280,17 @@ class Gem::TestCase::SpecFetcherSetup
     @operations << [:gem, name, version, dependencies, block]
   end
 
+  ##
+  # Creates a gem with +name+, +version+ and +deps+.  The created gem is
+  # downloaded in to the cache directory but is not installed
+  #
+  # The specification will be yielded before gem creation for customization,
+  # but only the block or the dependencies may be set, not both.
+
+  def download name, version, dependencies = nil, &block
+    @operations << [:download, name, version, dependencies, block]
+  end
+
   ##
   # Creates a legacy platform spec with the name 'pl' and version 1
 
@@ -312,17 +317,12 @@ class Gem::TestCase::SpecFetcherSetup
       gem_repo, @test.gem_repo = @test.gem_repo, @repository
       @test.uri = URI @repository
 
-      @test.util_setup_spec_fetcher(*@gems.keys)
+      @test.util_setup_spec_fetcher(*@downloaded)
     ensure
       @test.gem_repo = gem_repo
       @test.uri = URI gem_repo
     end
 
-    # This works around util_setup_spec_fetcher adding all created gems to the
-    # installed set.
-    Gem::Specification.reset
-    Gem::Specification.add_specs(*@installed)
-
     @gems.each do |spec, gem|
       next unless gem
 
diff --git a/lib/rubygems/uninstaller.rb b/lib/rubygems/uninstaller.rb
index 2a6edc6131..bb3e204c8d 100644
--- a/lib/rubygems/uninstaller.rb
+++ b/lib/rubygems/uninstaller.rb
@@ -271,7 +271,7 @@ class Gem::Uninstaller
 
     say "Successfully uninstalled #{spec.full_name}"
 
-    Gem::Specification.remove_spec spec
+    Gem::Specification.reset
   end
 
   ##
diff --git a/lib/rubygems/util.rb b/lib/rubygems/util.rb
index cd0af4d8fe..9bfe13f815 100644
--- a/lib/rubygems/util.rb
+++ b/lib/rubygems/util.rb
@@ -10,8 +10,8 @@ module Gem::Util
 
   def self.gunzip(data)
     require 'zlib'
-    require 'rubygems/util/stringio'
-    data = Gem::StringSource.new data
+    require 'stringio'
+    data = StringIO.new(data, 'r')
 
     unzipped = Zlib::GzipReader.new(data).read
     unzipped.force_encoding Encoding::BINARY if Object.const_defined? :Encoding
@@ -23,8 +23,8 @@ module Gem::Util
 
   def self.gzip(data)
     require 'zlib'
-    require 'rubygems/util/stringio'
-    zipped = Gem::StringSink.new
+    require 'stringio'
+    zipped = StringIO.new('','w')
     zipped.set_encoding Encoding::BINARY if Object.const_defined? :Encoding
 
     Zlib::GzipWriter.wrap zipped do |io| io.write data end
diff --git a/lib/rubygems/util/list.rb b/lib/rubygems/util/list.rb
index 9bc11fe334..6fa767646c 100644
--- a/lib/rubygems/util/list.rb
+++ b/lib/rubygems/util/list.rb
@@ -1,7 +1,13 @@
 module Gem
-  List = Struct.new(:value, :tail)
-
   class List
+    include Enumerable
+    attr_accessor :value, :tail
+
+    def initialize(value = nil, tail = nil)
+      @value = value
+      @tail = tail
+    end
+
     def each
       n = self
       while n
@@ -11,25 +17,7 @@ module Gem
     end
 
     def to_a
-      ary = []
-      n = self
-      while n
-        ary.unshift n.value
-        n = n.tail
-      end
-
-      ary
-    end
-
-    def find
-      n = self
-      while n
-        v = n.value
-        return v if yield(v)
-        n = n.tail
-      end
-
-      nil
+      super.reverse
     end
 
     def prepend(value)
diff --git a/lib/rubygems/util/stringio.rb b/lib/rubygems/util/stringio.rb
deleted file mode 100644
index 2ea69617bc..0000000000
--- a/lib/rubygems/util/stringio.rb
+++ /dev/null
@@ -1,34 +0,0 @@
-class Gem::StringSink
-  def initialize
-    @string = ""
-  end
-
-  attr_reader :string
-
-  def write(s)
-    @string += s
-    s.size
-  end
-
-  def set_encoding(enc)
-    @string.force_encoding enc
-  end
-end
-
-class Gem::StringSource
-  def initialize(str)
-    @string = str.dup
-  end
-
-  def read(count=nil)
-    if count
-      @string.slice!(0,count)
-    else
-      s = @string
-      @string = ""
-      s
-    end
-  end
-
-  alias_method :readpartial, :read
-end
diff --git a/lib/rubygems/version.rb b/lib/rubygems/version.rb
index c581aa367f..e2ee59a0c2 100644
--- a/lib/rubygems/version.rb
+++ b/lib/rubygems/version.rb
@@ -232,11 +232,11 @@ class Gem::Version
   # same precision. Version "1.0" is not the same as version "1".
 
   def eql? other
-    self.class === other and @version == other.version
+    self.class === other and @version == other._version
   end
 
   def hash # :nodoc:
-    @hash ||= segments.hash
+    @version.hash
   end
 
   def init_with coder # :nodoc:
@@ -333,7 +333,7 @@ class Gem::Version
 
   def <=> other
     return unless Gem::Version === other
-    return 0 if @version == other.version
+    return 0 if @version == other._version
 
     lhsegments = segments
     rhsegments = other.segments
@@ -357,4 +357,10 @@ class Gem::Version
 
     return 0
   end
+
+  protected
+
+  def _version
+    @version
+  end
 end
-- 
cgit v1.2.3