Auto merge of #4580 - bundler:seg-resolver-performance, r=indirect

Improve resolver performance

Some not insignificant improvements found while developing https://github.com/CocoaPods/Molinillo/pull/40, which I absolutely cannot wait to 🚢

\c @indirect

12 files changed, 71 insertions, 87 deletions

diff --git a/lib/bundler/definition.rb b/lib/bundler/definition.rb
index 366b51b4a7..02f8ee0957 100644
--- a/lib/bundler/definition.rb
+++ b/lib/bundler/definition.rb
@@ -224,7 +224,7 @@ module Bundler
           source.dependency_names = dependency_names.dup
           idx.add_source source.specs
           dependency_names -= pinned_spec_names(source.specs)
-          dependency_names.push(*source.unmet_deps).uniq!
+          dependency_names.concat(source.unmet_deps).uniq!
         end
       end
     end
diff --git a/lib/bundler/endpoint_specification.rb b/lib/bundler/endpoint_specification.rb
index b26fdaf9cc..69d05167e8 100644
--- a/lib/bundler/endpoint_specification.rb
+++ b/lib/bundler/endpoint_specification.rb
@@ -115,8 +115,8 @@ module Bundler
       end
     end
 
-    def build_dependency(name, *requirements)
-      Gem::Dependency.new(name, *requirements)
+    def build_dependency(name, requirements)
+      Gem::Dependency.new(name, requirements)
     rescue ArgumentError => e
       raise unless e.message.include?(ILLFORMED_MESSAGE)
       puts # we shouldn't print the error message on the "fetching info" status line
diff --git a/lib/bundler/fetcher.rb b/lib/bundler/fetcher.rb
index 7da22f8ed1..fb9a407791 100644
--- a/lib/bundler/fetcher.rb
+++ b/lib/bundler/fetcher.rb
@@ -63,7 +63,7 @@ module Bundler
     FAIL_ERRORS = begin
       fail_errors = [AuthenticationRequiredError, BadAuthenticationError, FallbackError]
       fail_errors << Gem::Requirement::BadRequirementError if defined?(Gem::Requirement::BadRequirementError)
-      fail_errors.push(*NET_ERRORS.map {|e| SharedHelpers.const_get_safely(e, Net) }.compact)
+      fail_errors.concat(NET_ERRORS.map {|e| SharedHelpers.const_get_safely(e, Net) }.compact)
     end.freeze
 
     class << self
diff --git a/lib/bundler/fetcher/compact_index.rb b/lib/bundler/fetcher/compact_index.rb
index aa284e5fc6..c0e1b3b4cf 100644
--- a/lib/bundler/fetcher/compact_index.rb
+++ b/lib/bundler/fetcher/compact_index.rb
@@ -41,7 +41,7 @@ module Bundler
           deps = compact_index_client.dependencies(remaining_gems)
           next_gems = deps.map {|d| d[3].map(&:first).flatten(1) }.flatten(1).uniq
           deps.each {|dep| gem_info << dep }
-          complete_gems.push(*deps.map(&:first)).uniq!
+          complete_gems.concat(deps.map(&:first)).uniq!
           remaining_gems = next_gems - complete_gems
         end
 
diff --git a/lib/bundler/fetcher/dependency.rb b/lib/bundler/fetcher/dependency.rb
index 0e67375de8..a145837a88 100644
--- a/lib/bundler/fetcher/dependency.rb
+++ b/lib/bundler/fetcher/dependency.rb
@@ -54,7 +54,7 @@ module Bundler
         gem_list = []
         gem_names.each_slice(Source::Rubygems::API_REQUEST_SIZE) do |names|
           marshalled_deps = downloader.fetch(dependency_api_uri(names)).body
-          gem_list.push(*Bundler.load_marshal(marshalled_deps))
+          gem_list.concat(Bundler.load_marshal(marshalled_deps))
         end
         gem_list
       end
@@ -64,7 +64,7 @@ module Bundler
         spec_list = []
 
         gem_list.each do |s|
-          deps_list.push(*s[:dependencies].map(&:first))
+          deps_list.concat(s[:dependencies].map(&:first))
           deps = s[:dependencies].map {|n, d| [n, d.split(", ")] }
           spec_list.push([s[:name], s[:number], s[:platform], deps])
         end
diff --git a/lib/bundler/index.rb b/lib/bundler/index.rb
index a03c11d992..c28a120990 100644
--- a/lib/bundler/index.rb
+++ b/lib/bundler/index.rb
@@ -21,15 +21,14 @@ module Bundler
       @sources = []
       @cache = {}
       @specs = Hash.new {|h, k| h[k] = {} }
-      @all_specs = Hash.new {|h, k| h[k] = [] }
+      @all_specs = Hash.new {|h, k| h[k] = EMPTY_SEARCH }
     end
 
     def initialize_copy(o)
-      super
-      @sources = @sources.dup
+      @sources = o.sources.dup
       @cache = {}
       @specs = Hash.new {|h, k| h[k] = {} }
-      @all_specs = Hash.new {|h, k| h[k] = [] }
+      @all_specs = Hash.new {|h, k| h[k] = EMPTY_SEARCH }
 
       o.specs.each do |name, hash|
         @specs[name] = hash.dup
@@ -49,7 +48,7 @@ module Bundler
     end
 
     def search_all(name)
-      all_matches = @all_specs[name] + local_search(name)
+      all_matches = local_search(name) + @all_specs[name]
       @sources.each do |source|
         all_matches.concat(source.search_all(name))
       end
@@ -60,19 +59,18 @@ module Bundler
     # about, returning all of the results.
     def search(query, base = nil)
       results = local_search(query, base)
-      seen = Set.new(results.map {|spec| [spec.name, spec.version, spec.platform] })
+      seen = results.map(&:full_name).to_set
 
       @sources.each do |source|
         source.search(query, base).each do |spec|
-          lookup = [spec.name, spec.version, spec.platform]
-          unless seen.include?(lookup)
-            results << spec
-            seen << lookup
-          end
+          results << spec if seen.add?(spec.full_name)
         end
       end
 
-      results.sort_by {|s| [s.version, s.platform.to_s == RUBY ? NULL : s.platform.to_s] }
+      results.sort_by do |s|
+        platform_string = s.platform.to_s
+        [s.version, platform_string == RUBY ? NULL : platform_string]
+      end
     end
 
     def local_search(query, base = nil)
@@ -90,14 +88,15 @@ module Bundler
 
     def <<(spec)
       @specs[spec.name][spec.full_name] = spec
-
       spec
     end
 
     def each(&blk)
+      return enum_for(:each) unless blk
       specs.values.each do |spec_sets|
         spec_sets.values.each(&blk)
       end
+      sources.each {|s| s.each(&blk) }
     end
 
     # returns a list of the dependencies
@@ -109,17 +108,17 @@ module Bundler
 
     def dependency_names
       names = []
-      each {|s| names.push(*s.dependencies.map(&:name)) }
+      each {|s| names.concat(s.dependencies.map(&:name)) }
       names.uniq
     end
 
     def use(other, override_dupes = false)
       return unless other
       other.each do |s|
-        if (dupes = search_by_spec(s)) && dupes.any?
-          @all_specs[s.name] = [s] + dupes
+        if (dupes = search_by_spec(s)) && !dupes.empty?
+          # safe to << since it's a new array when it has contents
+          @all_specs[s.name] = dupes << s
           next unless override_dupes
-          self << s
         end
         self << s
       end
@@ -154,7 +153,8 @@ module Bundler
     def search_by_dependency(dependency, base = nil)
       @cache[base || false] ||= {}
       @cache[base || false][dependency] ||= begin
-        specs = specs_by_name(dependency.name) + (base || [])
+        specs = specs_by_name(dependency.name)
+        specs += base if base
         found = specs.select do |spec|
           next true if spec.source.is_a?(Source::Gemspec)
           if base # allow all platforms when searching from a lockfile
@@ -175,25 +175,11 @@ module Bundler
       end
     end
 
+    EMPTY_SEARCH = [].freeze
+
     def search_by_spec(spec)
       spec = @specs[spec.name][spec.full_name]
-      spec ? [spec] : []
-    end
-
-    if RUBY_VERSION < "1.9"
-      def same_version?(a, b)
-        regex = /^(.*?)(?:\.0)*$/
-        a.to_s[regex, 1] == b.to_s[regex, 1]
-      end
-    else
-      def same_version?(a, b)
-        a == b
-      end
-    end
-
-    def spec_satisfies_dependency?(spec, dep)
-      return false unless dep.name == spec.name
-      dep.requirement.satisfied_by?(spec.version)
+      spec ? [spec] : EMPTY_SEARCH
     end
   end
 end
diff --git a/lib/bundler/remote_specification.rb b/lib/bundler/remote_specification.rb
index 29735fc6ab..6a02897c63 100644
--- a/lib/bundler/remote_specification.rb
+++ b/lib/bundler/remote_specification.rb
@@ -66,6 +66,10 @@ module Bundler
       [@name, @version, @platform == Gem::Platform::RUBY ? -1 : 1]
     end
 
+    def to_s
+      "#<#{self.class} name=#{name} version=#{version} platform=#{platform}>"
+    end
+
   private
 
     def _remote_specification
@@ -75,11 +79,7 @@ module Bundler
     end
 
     def method_missing(method, *args, &blk)
-      if Gem::Specification.new.respond_to?(method)
-        _remote_specification.send(method, *args, &blk)
-      else
-        super
-      end
+      _remote_specification.send(method, *args, &blk)
     end
   end
 end
diff --git a/lib/bundler/resolver.rb b/lib/bundler/resolver.rb
index 8c183ba885..918b3c977b 100644
--- a/lib/bundler/resolver.rb
+++ b/lib/bundler/resolver.rb
@@ -106,14 +106,8 @@ module Bundler
         specs.values
       end
 
-      def activate_platform(platform)
-        unless @activated.include?(platform)
-          if for?(platform, nil)
-            @activated << platform
-            return __dependencies[platform] || []
-          end
-        end
-        []
+      def activate_platform!(platform)
+        @activated << platform if !@activated.include?(platform) && for?(platform, nil)
       end
 
       def name
@@ -252,28 +246,34 @@ module Bundler
       platform = dependency.__platform
       dependency = dependency.dep unless dependency.is_a? Gem::Dependency
       search = @search_for[dependency] ||= begin
-        index = @source_requirements[dependency.name] || @index
+        index = index_for(dependency)
         results = index.search(dependency, @base[dependency.name])
         if vertex = @base_dg.vertex_named(dependency.name)
           locked_requirement = vertex.payload.requirement
         end
         if results.any?
-          version = results.first.version
-          nested  = [[]]
+          nested = []
           results.each do |spec|
-            if spec.version != version
-              nested << []
-              version = spec.version
+            version, specs = nested.last
+            if version == spec.version
+              specs << spec
+            else
+              nested << [spec.version, [spec]]
             end
-            nested.last << spec
           end
-          groups = nested.map {|a| SpecGroup.new(a) }
-          !locked_requirement ? groups : groups.select {|sg| locked_requirement.satisfied_by? sg.version }
+          nested.reduce([]) do |groups, (version, specs)|
+            next groups if locked_requirement && !locked_requirement.satisfied_by?(version)
+            groups << SpecGroup.new(specs)
+          end
         else
           []
         end
       end
-      search.select {|sg| sg.for?(platform, @ruby_version) }.each {|sg| sg.activate_platform(platform) }
+      search.select {|sg| sg.for?(platform, @ruby_version) }.each {|sg| sg.activate_platform!(platform) }
+    end
+
+    def index_for(dependency)
+      @source_requirements[dependency.name] || @index
     end
 
     def name_for(dependency)
@@ -314,14 +314,12 @@ module Bundler
         if (base = @base[dependency.name]) && !base.empty?
           dependency.requirement.satisfied_by?(base.first.version) ? 0 : 1
         else
-          base_dep = Dependency.new dependency.name, ">= 0.a"
-          all = search_for(DepProxy.new base_dep, dependency.__platform).size.to_f
-          if all.zero?
-            0
-          elsif (search = search_for(dependency).size.to_f) == all && all == 1
-            0
+          all = index_for(dependency).search(dependency.name).size
+          if all <= 1
+            all
           else
-            search / all
+            search = search_for(dependency).size
+            search - all
           end
         end
       end
diff --git a/lib/bundler/rubygems_integration.rb b/lib/bundler/rubygems_integration.rb
index 8a0fdbaeeb..41ebc87c77 100644
--- a/lib/bundler/rubygems_integration.rb
+++ b/lib/bundler/rubygems_integration.rb
@@ -212,7 +212,7 @@ module Bundler
       # Fetch all specs, minus prerelease specs
       spec_list = fetch_specs(true, false)
       # Then fetch the prerelease specs
-      fetch_prerelease_specs.each {|k, v| spec_list[k].push(*v) }
+      fetch_prerelease_specs.each {|k, v| spec_list[k].concat(v) }
 
       spec_list.values.first
     ensure
@@ -605,7 +605,7 @@ module Bundler
         specs = fetch_specs(source, remote, "specs")
         pres = fetch_specs(source, remote, "prerelease_specs") || []
 
-        specs.push(*pres)
+        specs.concat(pres)
       end
 
       def download_gem(spec, uri, path)
diff --git a/spec/bundler/endpoint_specification_spec.rb b/spec/bundler/endpoint_specification_spec.rb
index fccf1842fc..cdf81cd0f7 100644
--- a/spec/bundler/endpoint_specification_spec.rb
+++ b/spec/bundler/endpoint_specification_spec.rb
@@ -16,25 +16,26 @@ describe Bundler::EndpointSpecification do
     let(:requirement2)   { ">= 1.1.7" }
 
     it "should return a Gem::Dependency" do
-      expect(subject.send(:build_dependency, name, requirement1, requirement2)).to be_instance_of(Gem::Dependency)
+      expect(subject.send(:build_dependency, name, [requirement1, requirement2])).
+        to eq(Gem::Dependency.new(name, requirement1, requirement2))
     end
 
     context "when an ArgumentError occurs" do
       before do
-        allow(Gem::Dependency).to receive(:new).with(name, requirement1, requirement2) {
+        allow(Gem::Dependency).to receive(:new).with(name, [requirement1, requirement2]) {
           raise ArgumentError.new("Some error occurred")
         }
       end
 
       it "should raise the original error" do
-        expect { subject.send(:build_dependency, name, requirement1, requirement2) }.to raise_error(
+        expect { subject.send(:build_dependency, name, [requirement1, requirement2]) }.to raise_error(
           ArgumentError, "Some error occurred")
       end
     end
 
     context "when there is an ill formed requirement" do
       before do
-        allow(Gem::Dependency).to receive(:new).with(name, requirement1, requirement2) {
+        allow(Gem::Dependency).to receive(:new).with(name, [requirement1, requirement2]) {
           raise ArgumentError.new("Ill-formed requirement [\"#<YAML::Syck::DefaultKey")
         }
         # Eliminate extra line break in rspec output due to `puts` in `#build_dependency`
@@ -42,7 +43,7 @@ describe Bundler::EndpointSpecification do
       end
 
       it "should raise a Bundler::GemspecError with invalid gemspec message" do
-        expect { subject.send(:build_dependency, name, requirement1, requirement2) }.to raise_error(
+        expect { subject.send(:build_dependency, name, [requirement1, requirement2]) }.to raise_error(
           Bundler::GemspecError, /Unfortunately, the gem foo \(1\.0\.0\) has an invalid gemspec/)
       end
     end
diff --git a/spec/bundler/remote_specification_spec.rb b/spec/bundler/remote_specification_spec.rb
index 527f48facc..6a8e9a6434 100644
--- a/spec/bundler/remote_specification_spec.rb
+++ b/spec/bundler/remote_specification_spec.rb
@@ -170,13 +170,5 @@ describe Bundler::RemoteSpecification do
         subject.missing_method_call
       end
     end
-
-    context "and is not present in Gem::Specification" do
-      before { allow_any_instance_of(Gem::Specification).to receive(:respond_to?).and_return(false) }
-
-      it "should throw method missing error" do
-        expect { subject.missing_method_call }.to raise_error(NoMethodError)
-      end
-    end
   end
 end
diff --git a/spec/install/bundler_spec.rb b/spec/install/bundler_spec.rb
index 560272e5cf..835afa0e96 100644
--- a/spec/install/bundler_spec.rb
+++ b/spec/install/bundler_spec.rb
@@ -44,8 +44,15 @@ describe "bundle install" do
           In Gemfile:
             bundler (= 0.9.2)
 
+            rails (= 3.0) was resolved to 3.0, which depends on
+              bundler (>= 0.9.0.pre)
+
           Current Bundler version:
             bundler (#{Bundler::VERSION})
+        This Gemfile requires a different version of Bundler.
+        Perhaps you need to update Bundler by running `gem install bundler`?
+
+        Could not find gem 'bundler (= 0.9.2)', which is required by gem 'rails (= 3.0)', in any of the sources.
         E
       expect(out).to include(nice_error)
     end