Migrate our resolver engine to PubGrub

  https://github.com/rubygems/rubygems/pull/5960

  Co-authored-by: David Rodríguez <deivid.rodriguez@riseup.net>

5 files changed, 217 insertions, 47 deletions

diff --git a/lib/bundler/resolver/base.rb b/lib/bundler/resolver/base.rb
index a8f42dc994..78b798f4ec 100644
--- a/lib/bundler/resolver/base.rb
+++ b/lib/bundler/resolver/base.rb
@@ -20,15 +20,11 @@ module Bundler
         @base_requirements ||= build_base_requirements
       end
 
-      def unlock_deps(deps)
-        exact, lower_bound = deps.partition(&:specific?)
+      def unlock_names(names)
+        names.each do |name|
+          @base.delete_by_name(name)
 
-        exact.each do |exact_dep|
-          @base.delete_by_name_and_version(exact_dep.name, exact_dep.requirement.requirements.first.last)
-        end
-
-        lower_bound.each do |lower_bound_dep|
-          @additional_base_requirements.delete(lower_bound_dep)
+          @additional_base_requirements.reject! {|dep| dep.name == name }
         end
 
         @base_requirements = nil
@@ -39,10 +35,10 @@ module Bundler
       def build_base_requirements
         base_requirements = {}
         @base.each do |ls|
-          dep = Dependency.new(ls.name, ls.version)
-          base_requirements[ls.name] = dep
+          req = Gem::Requirement.new(ls.version)
+          base_requirements[ls.name] = req
         end
-        @additional_base_requirements.each {|d| base_requirements[d.name] = d }
+        @additional_base_requirements.each {|d| base_requirements[d.name] = d.requirement }
         base_requirements
       end
     end
diff --git a/lib/bundler/resolver/candidate.rb b/lib/bundler/resolver/candidate.rb
new file mode 100644
index 0000000000..cf5691ccc7
--- /dev/null
+++ b/lib/bundler/resolver/candidate.rb
@@ -0,0 +1,92 @@
+# frozen_string_literal: true
+
+require_relative "spec_group"
+
+module Bundler
+  class Resolver
+    #
+    # This class is a PubGrub compatible "Version" class that takes Bundler
+    # resolution complexities into account.
+    #
+    # Each Resolver::Candidate has a underlying `Gem::Version` plus a set of
+    # platforms. For example, 1.1.0-x86_64-linux is a different resolution candidate
+    # from 1.1.0 (generic). This is because different platform variants of the
+    # same gem version can bring different dependencies, so they need to be
+    # considered separately.
+    #
+    # Some candidates may also keep some information explicitly about the
+    # package the refer to. These candidates are referred to as "canonical" and
+    # are used when materializing resolution results back into RubyGems
+    # specifications that can be installed, written to lock files, and so on.
+    #
+    class Candidate
+      include Comparable
+
+      attr_reader :version
+
+      def initialize(version, specs: [])
+        @spec_group = Resolver::SpecGroup.new(specs)
+        @platforms = specs.map(&:platform).sort_by(&:to_s).uniq
+        @version = Gem::Version.new(version)
+        @ruby_only = @platforms == [Gem::Platform::RUBY]
+      end
+
+      def dependencies
+        @spec_group.dependencies
+      end
+
+      def to_specs(package)
+        return [] if package.meta?
+
+        @spec_group.to_specs(package.force_ruby_platform?)
+      end
+
+      def prerelease?
+        @version.prerelease?
+      end
+
+      def segments
+        @version.segments
+      end
+
+      def sort_obj
+        [@version, @ruby_only ? -1 : 1]
+      end
+
+      def canonical?
+        !@spec_group.empty?
+      end
+
+      def <=>(other)
+        return unless other.is_a?(self.class)
+        return @version <=> other.version unless canonical? && other.canonical?
+
+        sort_obj <=> other.sort_obj
+      end
+
+      def ==(other)
+        return unless other.is_a?(self.class)
+        return @version == other.version unless canonical? && other.canonical?
+
+        sort_obj == other.sort_obj
+      end
+
+      def eql?(other)
+        return unless other.is_a?(self.class)
+        return @version.eql?(other.version) unless canonical? || other.canonical?
+
+        sort_obj.eql?(other.sort_obj)
+      end
+
+      def hash
+        sort_obj.hash
+      end
+
+      def to_s
+        return @version.to_s if @platforms.empty? || @ruby_only
+
+        "#{@version} (#{@platforms.join(", ")})"
+      end
+    end
+  end
+end
diff --git a/lib/bundler/resolver/package.rb b/lib/bundler/resolver/package.rb
new file mode 100644
index 0000000000..fa283baca8
--- /dev/null
+++ b/lib/bundler/resolver/package.rb
@@ -0,0 +1,67 @@
+# frozen_string_literal: true
+
+module Bundler
+  class Resolver
+    #
+    # Represents a gem being resolved, in a format PubGrub likes.
+    #
+    # The class holds the following information:
+    #
+    # * Platforms this gem will be resolved on.
+    # * The locked version of this gem resolution should favor (if any).
+    # * Whether the gem should be unlocked to its latest version.
+    # * The dependency explicit set in the Gemfile for this gem (if any).
+    #
+    class Package
+      attr_reader :name, :platforms, :dependency
+
+      def initialize(name, platforms, locked_specs, unlock, dependency: nil)
+        @name = name
+        @platforms = platforms
+        @locked_specs = locked_specs
+        @unlock = unlock
+        @dependency = dependency
+      end
+
+      def to_s
+        @name.delete("\0")
+      end
+
+      def root?
+        false
+      end
+
+      def meta?
+        @name.end_with?("\0")
+      end
+
+      def ==(other)
+        self.class == other.class && @name == other.name
+      end
+
+      def hash
+        @name.hash
+      end
+
+      def locked_version
+        @locked_specs[name].first&.version
+      end
+
+      def unlock?
+        @unlock.empty? || @unlock.include?(name)
+      end
+
+      def prerelease_specified?
+        @dependency&.prerelease?
+      end
+
+      def force_ruby_platform?
+        @dependency&.force_ruby_platform
+      end
+
+      def current_platform?
+        @dependency&.current_platform?
+      end
+    end
+  end
+end
diff --git a/lib/bundler/resolver/root.rb b/lib/bundler/resolver/root.rb
new file mode 100644
index 0000000000..e5eb634fb8
--- /dev/null
+++ b/lib/bundler/resolver/root.rb
@@ -0,0 +1,25 @@
+# frozen_string_literal: true
+
+require_relative "package"
+
+module Bundler
+  class Resolver
+    #
+    # Represents the Gemfile from the resolver's perspective. It's the root
+    # package and Gemfile entries depend on it.
+    #
+    class Root < Package
+      def initialize(name)
+        @name = name
+      end
+
+      def meta?
+        true
+      end
+
+      def root?
+        true
+      end
+    end
+  end
+end
diff --git a/lib/bundler/resolver/spec_group.rb b/lib/bundler/resolver/spec_group.rb
index ac32c3c119..b44c19a73f 100644
--- a/lib/bundler/resolver/spec_group.rb
+++ b/lib/bundler/resolver/spec_group.rb
@@ -3,20 +3,27 @@
 module Bundler
   class Resolver
     class SpecGroup
-      attr_accessor :name, :version, :source
-      attr_accessor :activated_platforms, :force_ruby_platform
+      def initialize(specs)
+        @specs = specs
+      end
 
-      def initialize(specs, relevant_platforms)
-        @exemplary_spec = specs.first
-        @name = @exemplary_spec.name
-        @version = @exemplary_spec.version
-        @source = @exemplary_spec.source
+      def empty?
+        @specs.empty?
+      end
 
-        @activated_platforms = relevant_platforms
-        @specs = specs
+      def name
+        @name ||= exemplary_spec.name
+      end
+
+      def version
+        @version ||= exemplary_spec.version
+      end
+
+      def source
+        @source ||= exemplary_spec.source
       end
 
-      def to_specs
+      def to_specs(force_ruby_platform)
         @specs.map do |s|
           lazy_spec = LazySpecification.new(name, version, s.platform, source)
           lazy_spec.force_ruby_platform = force_ruby_platform
@@ -26,44 +33,27 @@ module Bundler
       end
 
       def to_s
-        activated_platforms_string = sorted_activated_platforms.join(", ")
-        "#{name} (#{version}) (#{activated_platforms_string})"
+        sorted_spec_names.join(", ")
       end
 
-      def dependencies_for_activated_platforms
-        @dependencies_for_activated_platforms ||= @specs.map do |spec|
+      def dependencies
+        @dependencies ||= @specs.map do |spec|
           __dependencies(spec) + metadata_dependencies(spec)
         end.flatten.uniq
       end
 
-      def ==(other)
-        return unless other.is_a?(SpecGroup)
-        name == other.name &&
-          version == other.version &&
-          sorted_activated_platforms == other.sorted_activated_platforms &&
-          source == other.source
-      end
-
-      def eql?(other)
-        return unless other.is_a?(SpecGroup)
-        name.eql?(other.name) &&
-          version.eql?(other.version) &&
-          sorted_activated_platforms.eql?(other.sorted_activated_platforms) &&
-          source.eql?(other.source)
-      end
-
-      def hash
-        name.hash ^ version.hash ^ sorted_activated_platforms.hash ^ source.hash
-      end
-
       protected
 
-      def sorted_activated_platforms
-        activated_platforms.sort_by(&:to_s)
+      def sorted_spec_names
+        @sorted_spec_names ||= @specs.map(&:full_name).sort
       end
 
       private
 
+      def exemplary_spec
+        @specs.first
+      end
+
       def __dependencies(spec)
         dependencies = []
         spec.dependencies.each do |dep|