Migrate our resolver engine to PubGrub

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

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

37 files changed, 1929 insertions, 2348 deletions

diff --git a/lib/bundler/vendor/molinillo/lib/molinillo.rb b/lib/bundler/vendor/molinillo/lib/molinillo.rb
deleted file mode 100644
index a52b96deaf..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo.rb
+++ /dev/null
@@ -1,11 +0,0 @@
-# frozen_string_literal: true
-
-require_relative 'molinillo/gem_metadata'
-require_relative 'molinillo/errors'
-require_relative 'molinillo/resolver'
-require_relative 'molinillo/modules/ui'
-require_relative 'molinillo/modules/specification_provider'
-
-# Bundler::Molinillo is a generic dependency resolution algorithm.
-module Bundler::Molinillo
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/delegates/resolution_state.rb b/lib/bundler/vendor/molinillo/lib/molinillo/delegates/resolution_state.rb
deleted file mode 100644
index bcacf35243..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/delegates/resolution_state.rb
+++ /dev/null
@@ -1,57 +0,0 @@
-# frozen_string_literal: true
-
-module Bundler::Molinillo
-  # @!visibility private
-  module Delegates
-    # Delegates all {Bundler::Molinillo::ResolutionState} methods to a `#state` property.
-    module ResolutionState
-      # (see Bundler::Molinillo::ResolutionState#name)
-      def name
-        current_state = state || Bundler::Molinillo::ResolutionState.empty
-        current_state.name
-      end
-
-      # (see Bundler::Molinillo::ResolutionState#requirements)
-      def requirements
-        current_state = state || Bundler::Molinillo::ResolutionState.empty
-        current_state.requirements
-      end
-
-      # (see Bundler::Molinillo::ResolutionState#activated)
-      def activated
-        current_state = state || Bundler::Molinillo::ResolutionState.empty
-        current_state.activated
-      end
-
-      # (see Bundler::Molinillo::ResolutionState#requirement)
-      def requirement
-        current_state = state || Bundler::Molinillo::ResolutionState.empty
-        current_state.requirement
-      end
-
-      # (see Bundler::Molinillo::ResolutionState#possibilities)
-      def possibilities
-        current_state = state || Bundler::Molinillo::ResolutionState.empty
-        current_state.possibilities
-      end
-
-      # (see Bundler::Molinillo::ResolutionState#depth)
-      def depth
-        current_state = state || Bundler::Molinillo::ResolutionState.empty
-        current_state.depth
-      end
-
-      # (see Bundler::Molinillo::ResolutionState#conflicts)
-      def conflicts
-        current_state = state || Bundler::Molinillo::ResolutionState.empty
-        current_state.conflicts
-      end
-
-      # (see Bundler::Molinillo::ResolutionState#unused_unwind_options)
-      def unused_unwind_options
-        current_state = state || Bundler::Molinillo::ResolutionState.empty
-        current_state.unused_unwind_options
-      end
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/delegates/specification_provider.rb b/lib/bundler/vendor/molinillo/lib/molinillo/delegates/specification_provider.rb
deleted file mode 100644
index f8c695c1ed..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/delegates/specification_provider.rb
+++ /dev/null
@@ -1,88 +0,0 @@
-# frozen_string_literal: true
-
-module Bundler::Molinillo
-  module Delegates
-    # Delegates all {Bundler::Molinillo::SpecificationProvider} methods to a
-    # `#specification_provider` property.
-    module SpecificationProvider
-      # (see Bundler::Molinillo::SpecificationProvider#search_for)
-      def search_for(dependency)
-        with_no_such_dependency_error_handling do
-          specification_provider.search_for(dependency)
-        end
-      end
-
-      # (see Bundler::Molinillo::SpecificationProvider#dependencies_for)
-      def dependencies_for(specification)
-        with_no_such_dependency_error_handling do
-          specification_provider.dependencies_for(specification)
-        end
-      end
-
-      # (see Bundler::Molinillo::SpecificationProvider#requirement_satisfied_by?)
-      def requirement_satisfied_by?(requirement, activated, spec)
-        with_no_such_dependency_error_handling do
-          specification_provider.requirement_satisfied_by?(requirement, activated, spec)
-        end
-      end
-
-      # (see Bundler::Molinillo::SpecificationProvider#dependencies_equal?)
-      def dependencies_equal?(dependencies, other_dependencies)
-        with_no_such_dependency_error_handling do
-          specification_provider.dependencies_equal?(dependencies, other_dependencies)
-        end
-      end
-
-      # (see Bundler::Molinillo::SpecificationProvider#name_for)
-      def name_for(dependency)
-        with_no_such_dependency_error_handling do
-          specification_provider.name_for(dependency)
-        end
-      end
-
-      # (see Bundler::Molinillo::SpecificationProvider#name_for_explicit_dependency_source)
-      def name_for_explicit_dependency_source
-        with_no_such_dependency_error_handling do
-          specification_provider.name_for_explicit_dependency_source
-        end
-      end
-
-      # (see Bundler::Molinillo::SpecificationProvider#name_for_locking_dependency_source)
-      def name_for_locking_dependency_source
-        with_no_such_dependency_error_handling do
-          specification_provider.name_for_locking_dependency_source
-        end
-      end
-
-      # (see Bundler::Molinillo::SpecificationProvider#sort_dependencies)
-      def sort_dependencies(dependencies, activated, conflicts)
-        with_no_such_dependency_error_handling do
-          specification_provider.sort_dependencies(dependencies, activated, conflicts)
-        end
-      end
-
-      # (see Bundler::Molinillo::SpecificationProvider#allow_missing?)
-      def allow_missing?(dependency)
-        with_no_such_dependency_error_handling do
-          specification_provider.allow_missing?(dependency)
-        end
-      end
-
-      private
-
-      # Ensures any raised {NoSuchDependencyError} has its
-      # {NoSuchDependencyError#required_by} set.
-      # @yield
-      def with_no_such_dependency_error_handling
-        yield
-      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
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb
deleted file mode 100644
index 4d577213b9..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb
+++ /dev/null
@@ -1,255 +0,0 @@
-# frozen_string_literal: true
-
-require_relative '../../../../vendored_tsort'
-
-require_relative 'dependency_graph/log'
-require_relative 'dependency_graph/vertex'
-
-module Bundler::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
-      return vertices.values.each unless block_given?
-      vertices.values.each { |v| yield v }
-    end
-
-    include Bundler::TSort
-
-    # @!visibility private
-    alias tsort_each_node each
-
-    # @!visibility private
-    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)
-      Bundler::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 [Object] requirement The requirement the directed edge represents
-    Edge = Struct.new(:origin, :destination, :requirement)
-
-    # @return [{String => Vertex}] the vertices of the dependency graph, keyed
-    #   by {Vertex#name}
-    attr_reader :vertices
-
-    # @return [Log] the op log for this graph
-    attr_reader :log
-
-    # Initializes an empty dependency graph
-    def initialize
-      @vertices = {}
-      @log = Log.new
-    end
-
-    # Tags the current state of the dependency as the given tag
-    # @param  [Object] tag an opaque tag for the current state of the graph
-    # @return [Void]
-    def tag(tag)
-      log.tag(self, tag)
-    end
-
-    # Rewinds the graph to the state tagged as `tag`
-    # @param  [Object] tag the tag to rewind to
-    # @return [Void]
-    def rewind_to(tag)
-      log.rewind_to(self, tag)
-    end
-
-    # Initializes a copy of a {DependencyGraph}, ensuring that all {#vertices}
-    # are properly copied.
-    # @param [DependencyGraph] other the graph to copy.
-    def initialize_copy(other)
-      super
-      @vertices = {}
-      @log = other.log.dup
-      traverse = lambda do |new_v, old_v|
-        return if new_v.outgoing_edges.size == old_v.outgoing_edges.size
-        old_v.outgoing_edges.each do |edge|
-          destination = add_vertex(edge.destination.name, edge.destination.payload)
-          add_edge_no_circular(new_v, destination, edge.requirement)
-          traverse.call(destination, edge.destination)
-        end
-      end
-      other.vertices.each do |name, vertex|
-        new_vertex = add_vertex(name, vertex.payload, vertex.root?)
-        new_vertex.explicit_requirements.replace(vertex.explicit_requirements)
-        traverse.call(new_vertex, vertex)
-      end
-    end
-
-    # @return [String] a string suitable for debugging
-    def inspect
-      "#{self.class}:#{vertices.values.inspect}"
-    end
-
-    # @param [Hash] options options for dot output.
-    # @return [String] Returns a dot format representation of the graph
-    def to_dot(options = {})
-      edge_label = options.delete(:edge_label)
-      raise ArgumentError, "Unknown options: #{options.keys}" unless options.empty?
-
-      dot_vertices = []
-      dot_edges = []
-      vertices.each do |n, v|
-        dot_vertices << "  #{n} [label=\"{#{n}|#{v.payload}}\"]"
-        v.outgoing_edges.each do |e|
-          label = edge_label ? edge_label.call(e) : e.requirement
-          dot_edges << "  #{e.origin.name} -> #{e.destination.name} [label=#{label.to_s.dump}]"
-        end
-      end
-
-      dot_vertices.uniq!
-      dot_vertices.sort!
-      dot_edges.uniq!
-      dot_edges.sort!
-
-      dot = dot_vertices.unshift('digraph G {').push('') + dot_edges.push('}')
-      dot.join("\n")
-    end
-
-    # @param [DependencyGraph] other
-    # @return [Boolean] whether the two dependency graphs are equal, determined
-    #   by a recursive traversal of each {#root_vertices} and its
-    #   {Vertex#successors}
-    def ==(other)
-      return false unless other
-      return true if equal?(other)
-      vertices.each do |name, vertex|
-        other_vertex = other.vertex_named(name)
-        return false unless other_vertex
-        return false unless vertex.payload == other_vertex.payload
-        return false unless other_vertex.successors.to_set == vertex.successors.to_set
-      end
-    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)
-      root = !parent_names.delete(nil) { true }
-      vertex = add_vertex(name, payload, root)
-      vertex.explicit_requirements << requirement if root
-      parent_names.each do |parent_name|
-        parent_vertex = vertex_named(parent_name)
-        add_edge(parent_vertex, vertex, requirement)
-      end
-      vertex
-    end
-
-    # Adds a vertex with the given name, or updates the existing one.
-    # @param [String] name
-    # @param [Object] payload
-    # @return [Vertex] the vertex that was added to `self`
-    def add_vertex(name, payload, root = false)
-      log.add_vertex(self, name, payload, root)
-    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 [Array<Vertex>] the vertices which have been detached
-    def detach_vertex_named(name)
-      log.detach_vertex_named(self, name)
-    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)
-      vertex = vertex_named(name)
-      vertex if vertex && vertex.root?
-    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 destination.path_to?(origin)
-        raise CircularDependencyError.new(path(destination, origin))
-      end
-      add_edge_no_circular(origin, destination, requirement)
-    end
-
-    # Deletes an {Edge} from the dependency graph
-    # @param [Edge] edge
-    # @return [Void]
-    def delete_edge(edge)
-      log.delete_edge(self, edge.origin.name, edge.destination.name, edge.requirement)
-    end
-
-    # Sets the payload of the vertex with the given name
-    # @param [String] name the name of the vertex
-    # @param [Object] payload the payload
-    # @return [Void]
-    def set_payload(name, payload)
-      log.set_payload(self, name, payload)
-    end
-
-    private
-
-    # Adds a new {Edge} to the dependency graph without checking for
-    # circularity.
-    # @param (see #add_edge)
-    # @return (see #add_edge)
-    def add_edge_no_circular(origin, destination, requirement)
-      log.add_edge_no_circular(self, origin.name, destination.name, requirement)
-    end
-
-    # Returns the path between two vertices
-    # @raise [ArgumentError] if there is no path between the vertices
-    # @param [Vertex] from
-    # @param [Vertex] to
-    # @return [Array<Vertex>] the shortest path from `from` to `to`
-    def path(from, to)
-      distances = Hash.new(vertices.size + 1)
-      distances[from.name] = 0
-      predecessors = {}
-      each do |vertex|
-        vertex.successors.each do |successor|
-          if distances[successor.name] > distances[vertex.name] + 1
-            distances[successor.name] = distances[vertex.name] + 1
-            predecessors[successor] = vertex
-          end
-        end
-      end
-
-      path = [to]
-      while before = predecessors[to]
-        path << before
-        to = before
-        break if to == from
-      end
-
-      unless path.last.equal?(from)
-        raise ArgumentError, "There is no path from #{from.name} to #{to.name}"
-      end
-
-      path.reverse
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/action.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/action.rb
deleted file mode 100644
index c04c7eec9c..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/action.rb
+++ /dev/null
@@ -1,36 +0,0 @@
-# frozen_string_literal: true
-
-module Bundler::Molinillo
-  class DependencyGraph
-    # An action that modifies a {DependencyGraph} that is reversible.
-    # @abstract
-    class Action
-      # rubocop:disable Lint/UnusedMethodArgument
-
-      # @return [Symbol] The name of the action.
-      def self.action_name
-        raise 'Abstract'
-      end
-
-      # Performs the action on the given graph.
-      # @param  [DependencyGraph] graph the graph to perform the action on.
-      # @return [Void]
-      def up(graph)
-        raise 'Abstract'
-      end
-
-      # Reverses the action on the given graph.
-      # @param  [DependencyGraph] graph the graph to reverse the action on.
-      # @return [Void]
-      def down(graph)
-        raise 'Abstract'
-      end
-
-      # @return [Action,Nil] The previous action
-      attr_accessor :previous
-
-      # @return [Action,Nil] The next action
-      attr_accessor :next
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb
deleted file mode 100644
index 946a08236e..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb
+++ /dev/null
@@ -1,66 +0,0 @@
-# frozen_string_literal: true
-
-require_relative 'action'
-module Bundler::Molinillo
-  class DependencyGraph
-    # @!visibility private
-    # (see DependencyGraph#add_edge_no_circular)
-    class AddEdgeNoCircular < Action
-      # @!group Action
-
-      # (see Action.action_name)
-      def self.action_name
-        :add_vertex
-      end
-
-      # (see Action#up)
-      def up(graph)
-        edge = make_edge(graph)
-        edge.origin.outgoing_edges << edge
-        edge.destination.incoming_edges << edge
-        edge
-      end
-
-      # (see Action#down)
-      def down(graph)
-        edge = make_edge(graph)
-        delete_first(edge.origin.outgoing_edges, edge)
-        delete_first(edge.destination.incoming_edges, edge)
-      end
-
-      # @!group AddEdgeNoCircular
-
-      # @return [String] the name of the origin of the edge
-      attr_reader :origin
-
-      # @return [String] the name of the destination of the edge
-      attr_reader :destination
-
-      # @return [Object] the requirement that the edge represents
-      attr_reader :requirement
-
-      # @param  [DependencyGraph] graph the graph to find vertices from
-      # @return [Edge] The edge this action adds
-      def make_edge(graph)
-        Edge.new(graph.vertex_named(origin), graph.vertex_named(destination), requirement)
-      end
-
-      # Initialize an action to add an edge to a dependency graph
-      # @param [String] origin the name of the origin of the edge
-      # @param [String] destination the name of the destination of the edge
-      # @param [Object] requirement the requirement that the edge represents
-      def initialize(origin, destination, requirement)
-        @origin = origin
-        @destination = destination
-        @requirement = requirement
-      end
-
-      private
-
-      def delete_first(array, item)
-        return unless index = array.index(item)
-        array.delete_at(index)
-      end
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_vertex.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_vertex.rb
deleted file mode 100644
index 483527daf8..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_vertex.rb
+++ /dev/null
@@ -1,62 +0,0 @@
-# frozen_string_literal: true
-
-require_relative 'action'
-module Bundler::Molinillo
-  class DependencyGraph
-    # @!visibility private
-    # (see DependencyGraph#add_vertex)
-    class AddVertex < Action # :nodoc:
-      # @!group Action
-
-      # (see Action.action_name)
-      def self.action_name
-        :add_vertex
-      end
-
-      # (see Action#up)
-      def up(graph)
-        if existing = graph.vertices[name]
-          @existing_payload = existing.payload
-          @existing_root = existing.root
-        end
-        vertex = existing || Vertex.new(name, payload)
-        graph.vertices[vertex.name] = vertex
-        vertex.payload ||= payload
-        vertex.root ||= root
-        vertex
-      end
-
-      # (see Action#down)
-      def down(graph)
-        if defined?(@existing_payload)
-          vertex = graph.vertices[name]
-          vertex.payload = @existing_payload
-          vertex.root = @existing_root
-        else
-          graph.vertices.delete(name)
-        end
-      end
-
-      # @!group AddVertex
-
-      # @return [String] the name of the vertex
-      attr_reader :name
-
-      # @return [Object] the payload for the vertex
-      attr_reader :payload
-
-      # @return [Boolean] whether the vertex is root or not
-      attr_reader :root
-
-      # Initialize an action to add a vertex to a dependency graph
-      # @param [String] name the name of the vertex
-      # @param [Object] payload the payload for the vertex
-      # @param [Boolean] root whether the vertex is root or not
-      def initialize(name, payload, root)
-        @name = name
-        @payload = payload
-        @root = root
-      end
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/delete_edge.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/delete_edge.rb
deleted file mode 100644
index d81940585a..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/delete_edge.rb
+++ /dev/null
@@ -1,63 +0,0 @@
-# frozen_string_literal: true
-
-require_relative 'action'
-module Bundler::Molinillo
-  class DependencyGraph
-    # @!visibility private
-    # (see DependencyGraph#delete_edge)
-    class DeleteEdge < Action
-      # @!group Action
-
-      # (see Action.action_name)
-      def self.action_name
-        :delete_edge
-      end
-
-      # (see Action#up)
-      def up(graph)
-        edge = make_edge(graph)
-        edge.origin.outgoing_edges.delete(edge)
-        edge.destination.incoming_edges.delete(edge)
-      end
-
-      # (see Action#down)
-      def down(graph)
-        edge = make_edge(graph)
-        edge.origin.outgoing_edges << edge
-        edge.destination.incoming_edges << edge
-        edge
-      end
-
-      # @!group DeleteEdge
-
-      # @return [String] the name of the origin of the edge
-      attr_reader :origin_name
-
-      # @return [String] the name of the destination of the edge
-      attr_reader :destination_name
-
-      # @return [Object] the requirement that the edge represents
-      attr_reader :requirement
-
-      # @param  [DependencyGraph] graph the graph to find vertices from
-      # @return [Edge] The edge this action adds
-      def make_edge(graph)
-        Edge.new(
-          graph.vertex_named(origin_name),
-          graph.vertex_named(destination_name),
-          requirement
-        )
-      end
-
-      # Initialize an action to add an edge to a dependency graph
-      # @param [String] origin_name the name of the origin of the edge
-      # @param [String] destination_name the name of the destination of the edge
-      # @param [Object] requirement the requirement that the edge represents
-      def initialize(origin_name, destination_name, requirement)
-        @origin_name = origin_name
-        @destination_name = destination_name
-        @requirement = requirement
-      end
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb
deleted file mode 100644
index 36fce7c526..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb
+++ /dev/null
@@ -1,61 +0,0 @@
-# frozen_string_literal: true
-
-require_relative 'action'
-module Bundler::Molinillo
-  class DependencyGraph
-    # @!visibility private
-    # @see DependencyGraph#detach_vertex_named
-    class DetachVertexNamed < Action
-      # @!group Action
-
-      # (see Action#name)
-      def self.action_name
-        :add_vertex
-      end
-
-      # (see Action#up)
-      def up(graph)
-        return [] unless @vertex = graph.vertices.delete(name)
-
-        removed_vertices = [@vertex]
-        @vertex.outgoing_edges.each do |e|
-          v = e.destination
-          v.incoming_edges.delete(e)
-          if !v.root? && v.incoming_edges.empty?
-            removed_vertices.concat graph.detach_vertex_named(v.name)
-          end
-        end
-
-        @vertex.incoming_edges.each do |e|
-          v = e.origin
-          v.outgoing_edges.delete(e)
-        end
-
-        removed_vertices
-      end
-
-      # (see Action#down)
-      def down(graph)
-        return unless @vertex
-        graph.vertices[@vertex.name] = @vertex
-        @vertex.outgoing_edges.each do |e|
-          e.destination.incoming_edges << e
-        end
-        @vertex.incoming_edges.each do |e|
-          e.origin.outgoing_edges << e
-        end
-      end
-
-      # @!group DetachVertexNamed
-
-      # @return [String] the name of the vertex to detach
-      attr_reader :name
-
-      # Initialize an action to detach a vertex from a dependency graph
-      # @param [String] name the name of the vertex to detach
-      def initialize(name)
-        @name = name
-      end
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/log.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/log.rb
deleted file mode 100644
index 6f0de19886..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/log.rb
+++ /dev/null
@@ -1,126 +0,0 @@
-# frozen_string_literal: true
-
-require_relative 'add_edge_no_circular'
-require_relative 'add_vertex'
-require_relative 'delete_edge'
-require_relative 'detach_vertex_named'
-require_relative 'set_payload'
-require_relative 'tag'
-
-module Bundler::Molinillo
-  class DependencyGraph
-    # A log for dependency graph actions
-    class Log
-      # Initializes an empty log
-      def initialize
-        @current_action = @first_action = nil
-      end
-
-      # @!macro [new] action
-      #   {include:DependencyGraph#$0}
-      #   @param [Graph] graph the graph to perform the action on
-      #   @param (see DependencyGraph#$0)
-      #   @return (see DependencyGraph#$0)
-
-      # @macro action
-      def tag(graph, tag)
-        push_action(graph, Tag.new(tag))
-      end
-
-      # @macro action
-      def add_vertex(graph, name, payload, root)
-        push_action(graph, AddVertex.new(name, payload, root))
-      end
-
-      # @macro action
-      def detach_vertex_named(graph, name)
-        push_action(graph, DetachVertexNamed.new(name))
-      end
-
-      # @macro action
-      def add_edge_no_circular(graph, origin, destination, requirement)
-        push_action(graph, AddEdgeNoCircular.new(origin, destination, requirement))
-      end
-
-      # {include:DependencyGraph#delete_edge}
-      # @param [Graph] graph the graph to perform the action on
-      # @param [String] origin_name
-      # @param [String] destination_name
-      # @param [Object] requirement
-      # @return (see DependencyGraph#delete_edge)
-      def delete_edge(graph, origin_name, destination_name, requirement)
-        push_action(graph, DeleteEdge.new(origin_name, destination_name, requirement))
-      end
-
-      # @macro action
-      def set_payload(graph, name, payload)
-        push_action(graph, SetPayload.new(name, payload))
-      end
-
-      # Pops the most recent action from the log and undoes the action
-      # @param [DependencyGraph] graph
-      # @return [Action] the action that was popped off the log
-      def pop!(graph)
-        return unless action = @current_action
-        unless @current_action = action.previous
-          @first_action = nil
-        end
-        action.down(graph)
-        action
-      end
-
-      extend Enumerable
-
-      # @!visibility private
-      # Enumerates each action in the log
-      # @yield [Action]
-      def each
-        return enum_for unless block_given?
-        action = @first_action
-        loop do
-          break unless action
-          yield action
-          action = action.next
-        end
-        self
-      end
-
-      # @!visibility private
-      # Enumerates each action in the log in reverse order
-      # @yield [Action]
-      def reverse_each
-        return enum_for(:reverse_each) unless block_given?
-        action = @current_action
-        loop do
-          break unless action
-          yield action
-          action = action.previous
-        end
-        self
-      end
-
-      # @macro action
-      def rewind_to(graph, tag)
-        loop do
-          action = pop!(graph)
-          raise "No tag #{tag.inspect} found" unless action
-          break if action.class.action_name == :tag && action.tag == tag
-        end
-      end
-
-      private
-
-      # Adds the given action to the log, running the action
-      # @param [DependencyGraph] graph
-      # @param [Action] action
-      # @return The value returned by `action.up`
-      def push_action(graph, action)
-        action.previous = @current_action
-        @current_action.next = action if @current_action
-        @current_action = action
-        @first_action ||= action
-        action.up(graph)
-      end
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/set_payload.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/set_payload.rb
deleted file mode 100644
index 2e9b90e6cd..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/set_payload.rb
+++ /dev/null
@@ -1,46 +0,0 @@
-# frozen_string_literal: true
-
-require_relative 'action'
-module Bundler::Molinillo
-  class DependencyGraph
-    # @!visibility private
-    # @see DependencyGraph#set_payload
-    class SetPayload < Action # :nodoc:
-      # @!group Action
-
-      # (see Action.action_name)
-      def self.action_name
-        :set_payload
-      end
-
-      # (see Action#up)
-      def up(graph)
-        vertex = graph.vertex_named(name)
-        @old_payload = vertex.payload
-        vertex.payload = payload
-      end
-
-      # (see Action#down)
-      def down(graph)
-        graph.vertex_named(name).payload = @old_payload
-      end
-
-      # @!group SetPayload
-
-      # @return [String] the name of the vertex
-      attr_reader :name
-
-      # @return [Object] the payload for the vertex
-      attr_reader :payload
-
-      # Initialize an action to add set the payload for a vertex in a dependency
-      # graph
-      # @param [String] name the name of the vertex
-      # @param [Object] payload the payload for the vertex
-      def initialize(name, payload)
-        @name = name
-        @payload = payload
-      end
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/tag.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/tag.rb
deleted file mode 100644
index 5b5da3e4f9..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/tag.rb
+++ /dev/null
@@ -1,36 +0,0 @@
-# frozen_string_literal: true
-
-require_relative 'action'
-module Bundler::Molinillo
-  class DependencyGraph
-    # @!visibility private
-    # @see DependencyGraph#tag
-    class Tag < Action
-      # @!group Action
-
-      # (see Action.action_name)
-      def self.action_name
-        :tag
-      end
-
-      # (see Action#up)
-      def up(graph)
-      end
-
-      # (see Action#down)
-      def down(graph)
-      end
-
-      # @!group Tag
-
-      # @return [Object] An opaque tag
-      attr_reader :tag
-
-      # Initialize an action to tag a state of a dependency graph
-      # @param [Object] tag an opaque tag
-      def initialize(tag)
-        @tag = tag
-      end
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/vertex.rb b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/vertex.rb
deleted file mode 100644
index 1185a8ab05..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/vertex.rb
+++ /dev/null
@@ -1,164 +0,0 @@
-# frozen_string_literal: true
-
-module Bundler::Molinillo
-  class DependencyGraph
-    # A vertex in a {DependencyGraph} that encapsulates a {#name} and a
-    # {#payload}
-    class Vertex
-      # @return [String] the name of the vertex
-      attr_accessor :name
-
-      # @return [Object] the payload the vertex holds
-      attr_accessor :payload
-
-      # @return [Array<Object>] the explicit requirements that required
-      #   this vertex
-      attr_reader :explicit_requirements
-
-      # @return [Boolean] whether the vertex is considered a root vertex
-      attr_accessor :root
-      alias root? root
-
-      # Initializes a vertex with the given name and payload.
-      # @param [String] name see {#name}
-      # @param [Object] payload see {#payload}
-      def initialize(name, payload)
-        @name = name.frozen? ? name : name.dup.freeze
-        @payload = payload
-        @explicit_requirements = []
-        @outgoing_edges = []
-        @incoming_edges = []
-      end
-
-      # @return [Array<Object>] all of the requirements that required
-      #   this vertex
-      def requirements
-        (incoming_edges.map(&:requirement) + explicit_requirements).uniq
-      end
-
-      # @return [Array<Edge>] the edges of {#graph} that have `self` as their
-      #   {Edge#origin}
-      attr_accessor :outgoing_edges
-
-      # @return [Array<Edge>] the edges of {#graph} that have `self` as their
-      #   {Edge#destination}
-      attr_accessor :incoming_edges
-
-      # @return [Array<Vertex>] the vertices of {#graph} that have an edge with
-      #   `self` as their {Edge#destination}
-      def predecessors
-        incoming_edges.map(&:origin)
-      end
-
-      # @return [Set<Vertex>] the vertices of {#graph} where `self` is a
-      #   {#descendent?}
-      def recursive_predecessors
-        _recursive_predecessors
-      end
-
-      # @param [Set<Vertex>] vertices the set to add the predecessors to
-      # @return [Set<Vertex>] the vertices of {#graph} where `self` is a
-      #   {#descendent?}
-      def _recursive_predecessors(vertices = new_vertex_set)
-        incoming_edges.each do |edge|
-          vertex = edge.origin
-          next unless vertices.add?(vertex)
-          vertex._recursive_predecessors(vertices)
-        end
-
-        vertices
-      end
-      protected :_recursive_predecessors
-
-      # @return [Array<Vertex>] the vertices of {#graph} that have an edge with
-      #   `self` as their {Edge#origin}
-      def successors
-        outgoing_edges.map(&:destination)
-      end
-
-      # @return [Set<Vertex>] the vertices of {#graph} where `self` is an
-      #   {#ancestor?}
-      def recursive_successors
-        _recursive_successors
-      end
-
-      # @param [Set<Vertex>] vertices the set to add the successors to
-      # @return [Set<Vertex>] the vertices of {#graph} where `self` is an
-      #   {#ancestor?}
-      def _recursive_successors(vertices = new_vertex_set)
-        outgoing_edges.each do |edge|
-          vertex = edge.destination
-          next unless vertices.add?(vertex)
-          vertex._recursive_successors(vertices)
-        end
-
-        vertices
-      end
-      protected :_recursive_successors
-
-      # @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)
-        return true if equal?(other)
-        shallow_eql?(other) &&
-          successors.to_set == other.successors.to_set
-      end
-
-      # @param  [Vertex] other the other vertex to compare to
-      # @return [Boolean] whether the two vertices are equal, determined
-      #   solely by {#name} and {#payload} equality
-      def shallow_eql?(other)
-        return true if equal?(other)
-        other &&
-          name == other.name &&
-          payload == other.payload
-      end
-
-      alias 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 whether there is a path following edges within this {#graph}
-      def path_to?(other)
-        _path_to?(other)
-      end
-
-      alias descendent? path_to?
-
-      # @param [Vertex] other the vertex to check if there's a path to
-      # @param [Set<Vertex>] visited the vertices of {#graph} that have been visited
-      # @return [Boolean] whether there is a path to `other` from `self`
-      def _path_to?(other, visited = new_vertex_set)
-        return false unless visited.add?(self)
-        return true if equal?(other)
-        successors.any? { |v| v._path_to?(other, visited) }
-      end
-      protected :_path_to?
-
-      # Is there a path from `other` to `self` following edges in the
-      # dependency graph?
-      # @return whether there is a path following edges within this {#graph}
-      def ancestor?(other)
-        other.path_to?(self)
-      end
-
-      alias is_reachable_from? ancestor?
-
-      def new_vertex_set
-        require 'set'
-        Set.new
-      end
-      private :new_vertex_set
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/errors.rb b/lib/bundler/vendor/molinillo/lib/molinillo/errors.rb
deleted file mode 100644
index 8c8cafb447..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/errors.rb
+++ /dev/null
@@ -1,149 +0,0 @@
-# frozen_string_literal: true
-
-module Bundler::Molinillo
-  # An error that occurred during the resolution process
-  class ResolverError < StandardError; end
-
-  # An error caused by searching for a dependency that is completely unknown,
-  # i.e. has no versions available whatsoever.
-  class NoSuchDependencyError < ResolverError
-    # @return [Object] the dependency that could not be found
-    attr_accessor :dependency
-
-    # @return [Array<Object>] the specifications that depended upon {#dependency}
-    attr_accessor :required_by
-
-    # Initializes a new error with the given missing dependency.
-    # @param [Object] dependency @see {#dependency}
-    # @param [Array<Object>] required_by @see {#required_by}
-    def initialize(dependency, required_by = [])
-      @dependency = dependency
-      @required_by = required_by.uniq
-      super()
-    end
-
-    # The error message for the missing dependency, including the specifications
-    # that had this dependency.
-    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 if and only if 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
-
-    # Initializes a new error with the given circular vertices.
-    # @param [Array<DependencyGraph::Vertex>] vertices the vertices in the dependency
-    #   that caused the error
-    def initialize(vertices)
-      super "There is a circular dependency between #{vertices.map(&:name).join(' and ')}"
-      @dependencies = vertices.map { |vertex| vertex.payload.possibilities.last }.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
-
-    # @return [SpecificationProvider] the specification provider used during
-    #   resolution
-    attr_reader :specification_provider
-
-    # Initializes a new error with the given version conflicts.
-    # @param [{String => Resolution::Conflict}] conflicts see {#conflicts}
-    # @param [SpecificationProvider] specification_provider see {#specification_provider}
-    def initialize(conflicts, specification_provider)
-      pairs = []
-      conflicts.values.flat_map(&:requirements).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
-      @specification_provider = specification_provider
-    end
-
-    require_relative 'delegates/specification_provider'
-    include Delegates::SpecificationProvider
-
-    # @return [String] An error message that includes requirement trees,
-    #   which is much more detailed & customizable than the default message
-    # @param [Hash] opts the options to create a message with.
-    # @option opts [String] :solver_name The user-facing name of the solver
-    # @option opts [String] :possibility_type The generic name of a possibility
-    # @option opts [Proc] :reduce_trees A proc that reduced the list of requirement trees
-    # @option opts [Proc] :printable_requirement A proc that pretty-prints requirements
-    # @option opts [Proc] :additional_message_for_conflict A proc that appends additional
-    #   messages for each conflict
-    # @option opts [Proc] :version_for_spec A proc that returns the version number for a
-    #   possibility
-    def message_with_trees(opts = {})
-      solver_name = opts.delete(:solver_name) { self.class.name.split('::').first }
-      possibility_type = opts.delete(:possibility_type) { 'possibility named' }
-      reduce_trees = opts.delete(:reduce_trees) { proc { |trees| trees.uniq.sort_by(&:to_s) } }
-      printable_requirement = opts.delete(:printable_requirement) { proc { |req| req.to_s } }
-      additional_message_for_conflict = opts.delete(:additional_message_for_conflict) { proc {} }
-      version_for_spec = opts.delete(:version_for_spec) { proc(&:to_s) }
-      incompatible_version_message_for_conflict = opts.delete(:incompatible_version_message_for_conflict) do
-        proc do |name, _conflict|
-          %(#{solver_name} could not find compatible versions for #{possibility_type} "#{name}":)
-        end
-      end
-
-      full_message_for_conflict = opts.delete(:full_message_for_conflict) do
-        proc do |name, conflict|
-          o = "\n".dup << incompatible_version_message_for_conflict.call(name, conflict) << "\n"
-          if conflict.locked_requirement
-            o << %(  In snapshot (#{name_for_locking_dependency_source}):\n)
-            o << %(    #{printable_requirement.call(conflict.locked_requirement)}\n)
-            o << %(\n)
-          end
-          o << %(  In #{name_for_explicit_dependency_source}:\n)
-          trees = reduce_trees.call(conflict.requirement_trees)
-
-          o << trees.map do |tree|
-            t = ''.dup
-            depth = 2
-            tree.each do |req|
-              t << '  ' * depth << printable_requirement.call(req)
-              unless tree.last == req
-                if spec = conflict.activated_by_name[name_for(req)]
-                  t << %( was resolved to #{version_for_spec.call(spec)}, which)
-                end
-                t << %( depends on)
-              end
-              t << %(\n)
-              depth += 1
-            end
-            t
-          end.join("\n")
-
-          additional_message_for_conflict.call(o, name, conflict)
-
-          o
-        end
-      end
-
-      conflicts.sort.reduce(''.dup) do |o, (name, conflict)|
-        o << full_message_for_conflict.call(name, conflict)
-      end.strip
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/gem_metadata.rb b/lib/bundler/vendor/molinillo/lib/molinillo/gem_metadata.rb
deleted file mode 100644
index a0cfc21672..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/gem_metadata.rb
+++ /dev/null
@@ -1,6 +0,0 @@
-# frozen_string_literal: true
-
-module Bundler::Molinillo
-  # The version of Bundler::Molinillo.
-  VERSION = '0.8.0'.freeze
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/modules/specification_provider.rb b/lib/bundler/vendor/molinillo/lib/molinillo/modules/specification_provider.rb
deleted file mode 100644
index eeae79af3c..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/modules/specification_provider.rb
+++ /dev/null
@@ -1,112 +0,0 @@
-# frozen_string_literal: true
-
-module Bundler::Molinillo
-  # Provides information about specifications and dependencies to the resolver,
-  # allowing the {Resolver} class to remain generic while still providing power
-  # and flexibility.
-  #
-  # This module contains the methods that users of Bundler::Molinillo must to implement,
-  # using knowledge of their own model classes.
-  module SpecificationProvider
-    # Search for the specifications that match the given dependency.
-    # The specifications in the returned array will be considered in reverse
-    # order, so the latest version ought to be last.
-    # @note This method should be 'pure', i.e. the return value should depend
-    #   only on the `dependency` parameter.
-    #
-    # @param [Object] dependency
-    # @return [Array<Object>] the specifications that satisfy the given
-    #   `dependency`.
-    def search_for(dependency)
-      []
-    end
-
-    # Returns the dependencies of `specification`.
-    # @note This method should be 'pure', i.e. the return value should depend
-    #   only on the `specification` parameter.
-    #
-    # @param [Object] specification
-    # @return [Array<Object>] the dependencies that are required by the given
-    #   `specification`.
-    def dependencies_for(specification)
-      []
-    end
-
-    # Determines whether the given `requirement` is satisfied by the given
-    # `spec`, in the context of the current `activated` dependency graph.
-    #
-    # @param [Object] requirement
-    # @param [DependencyGraph] activated the current dependency graph in the
-    #   resolution process.
-    # @param [Object] spec
-    # @return [Boolean] whether `requirement` is satisfied by `spec` in the
-    #   context of the current `activated` dependency graph.
-    def requirement_satisfied_by?(requirement, activated, spec)
-      true
-    end
-
-    # Determines whether two arrays of dependencies are equal, and thus can be
-    # grouped.
-    #
-    # @param [Array<Object>] dependencies
-    # @param [Array<Object>] other_dependencies
-    # @return [Boolean] whether `dependencies` and `other_dependencies` should
-    #   be considered equal.
-    def dependencies_equal?(dependencies, other_dependencies)
-      dependencies == other_dependencies
-    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/bundler/vendor/molinillo/lib/molinillo/modules/ui.rb b/lib/bundler/vendor/molinillo/lib/molinillo/modules/ui.rb
deleted file mode 100644
index a166bc6991..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/modules/ui.rb
+++ /dev/null
@@ -1,67 +0,0 @@
-# frozen_string_literal: true
-
-module Bundler::Molinillo
-  # Conveys information about the resolution process to a user.
-  module UI
-    # The {IO} object that should be used to print output. `STDOUT`, by default.
-    #
-    # @return [IO]
-    def output
-      STDOUT
-    end
-
-    # Called roughly every {#progress_rate}, this method should convey progress
-    # to the user.
-    #
-    # @return [void]
-    def indicate_progress
-      output.print '.' unless debug?
-    end
-
-    # How often progress should be conveyed to the user via
-    # {#indicate_progress}, in seconds. A third of a second, by default.
-    #
-    # @return [Float]
-    def progress_rate
-      0.33
-    end
-
-    # Called before resolution begins.
-    #
-    # @return [void]
-    def before_resolution
-      output.print 'Resolving dependencies...'
-    end
-
-    # Called after resolution ends (either successfully or with an error).
-    # By default, prints a newline.
-    #
-    # @return [void]
-    def after_resolution
-      output.puts
-    end
-
-    # Conveys debug information to the user.
-    #
-    # @param [Integer] depth the current depth of the resolution process.
-    # @return [void]
-    def debug(depth = 0)
-      if debug?
-        debug_info = yield
-        debug_info = debug_info.inspect unless debug_info.is_a?(String)
-        debug_info = debug_info.split("\n").map { |s| ":#{depth.to_s.rjust 4}: #{s}" }
-        output.puts debug_info
-      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?
-      return @debug_mode if defined?(@debug_mode)
-      @debug_mode = ENV['MOLINILLO_DEBUG']
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb b/lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb
deleted file mode 100644
index c689ca7635..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb
+++ /dev/null
@@ -1,839 +0,0 @@
-# frozen_string_literal: true
-
-module Bundler::Molinillo
-  class Resolver
-    # A specific resolution from a given {Resolver}
-    class Resolution
-      # A conflict that the resolution process encountered
-      # @attr [Object] requirement the requirement that immediately led to the conflict
-      # @attr [{String,Nil=>[Object]}] requirements the requirements that caused the conflict
-      # @attr [Object, nil] existing the existing spec that was in conflict with
-      #   the {#possibility}
-      # @attr [Object] possibility_set the set of specs 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.
-      # @attr [{String=>Object}] activated_by_name the already-activated specs.
-      # @attr [Object] underlying_error an error that has occurred during resolution, and
-      #    will be raised at the end of it if no resolution is found.
-      Conflict = Struct.new(
-        :requirement,
-        :requirements,
-        :existing,
-        :possibility_set,
-        :locked_requirement,
-        :requirement_trees,
-        :activated_by_name,
-        :underlying_error
-      )
-
-      class Conflict
-        # @return [Object] a spec that was unable to be activated due to a conflict
-        def possibility
-          possibility_set && possibility_set.latest_version
-        end
-      end
-
-      # A collection of possibility states that share the same dependencies
-      # @attr [Array] dependencies the dependencies for this set of possibilities
-      # @attr [Array] possibilities the possibilities
-      PossibilitySet = Struct.new(:dependencies, :possibilities)
-
-      class PossibilitySet
-        # String representation of the possibility set, for debugging
-        def to_s
-          "[#{possibilities.join(', ')}]"
-        end
-
-        # @return [Object] most up-to-date dependency in the possibility set
-        def latest_version
-          possibilities.last
-        end
-      end
-
-      # Details of the state to unwind to when a conflict occurs, and the cause of the unwind
-      # @attr [Integer] state_index the index of the state to unwind to
-      # @attr [Object] state_requirement the requirement of the state we're unwinding to
-      # @attr [Array] requirement_tree for the requirement we're relaxing
-      # @attr [Array] conflicting_requirements the requirements that combined to cause the conflict
-      # @attr [Array] requirement_trees for the conflict
-      # @attr [Array] requirements_unwound_to_instead array of unwind requirements that were chosen over this unwind
-      UnwindDetails = Struct.new(
-        :state_index,
-        :state_requirement,
-        :requirement_tree,
-        :conflicting_requirements,
-        :requirement_trees,
-        :requirements_unwound_to_instead
-      )
-
-      class UnwindDetails
-        include Comparable
-
-        # We compare UnwindDetails when choosing which state to unwind to. If
-        # two options have the same state_index we prefer the one most
-        # removed from a requirement that caused the conflict. Both options
-        # would unwind to the same state, but a `grandparent` option will
-        # filter out fewer of its possibilities after doing so - where a state
-        # is both a `parent` and a `grandparent` to requirements that have
-        # caused a conflict this is the correct behaviour.
-        # @param [UnwindDetail] other UnwindDetail to be compared
-        # @return [Integer] integer specifying ordering
-        def <=>(other)
-          if state_index > other.state_index
-            1
-          elsif state_index == other.state_index
-            reversed_requirement_tree_index <=> other.reversed_requirement_tree_index
-          else
-            -1
-          end
-        end
-
-        # @return [Integer] index of state requirement in reversed requirement tree
-        #    (the conflicting requirement itself will be at position 0)
-        def reversed_requirement_tree_index
-          @reversed_requirement_tree_index ||=
-            if state_requirement
-              requirement_tree.reverse.index(state_requirement)
-            else
-              999_999
-            end
-        end
-
-        # @return [Boolean] where the requirement of the state we're unwinding
-        #    to directly caused the conflict. Note: in this case, it is
-        #    impossible for the state we're unwinding to to be a parent of
-        #    any of the other conflicting requirements (or we would have
-        #    circularity)
-        def unwinding_to_primary_requirement?
-          requirement_tree.last == state_requirement
-        end
-
-        # @return [Array] array of sub-dependencies to avoid when choosing a
-        #    new possibility for the state we've unwound to. Only relevant for
-        #    non-primary unwinds
-        def sub_dependencies_to_avoid
-          @requirements_to_avoid ||=
-            requirement_trees.map do |tree|
-              index = tree.index(state_requirement)
-              tree[index + 1] if index
-            end.compact
-        end
-
-        # @return [Array] array of all the requirements that led to the need for
-        #    this unwind
-        def all_requirements
-          @all_requirements ||= requirement_trees.flatten(1)
-        end
-      end
-
-      # @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
-
-      # Initializes a new resolution.
-      # @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
-        @parents_of = Hash.new { |h, k| h[k] = [] }
-      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 if !state.requirement && state.requirements.empty?
-          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 do |s|
-              if s
-                states.push(s)
-                activated.tag(s)
-              end
-            end
-          end
-          process_topmost_state
-        end
-
-        resolve_activated_specs
-      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
-
-        push_initial_state
-
-        debug { "Starting resolution (#{@started_at})\nUser-requested dependencies: #{original_requested}" }
-        resolver_ui.before_resolution
-      end
-
-      def resolve_activated_specs
-        activated.vertices.each do |_, vertex|
-          next unless vertex.payload
-
-          latest_version = vertex.payload.possibilities.reverse_each.find do |possibility|
-            vertex.requirements.all? { |req| requirement_satisfied_by?(req, activated, possibility) }
-          end
-
-          activated.set_payload(vertex.name, latest_version)
-        end
-        activated.freeze
-      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_relative 'state'
-      require_relative 'modules/specification_provider'
-
-      require_relative 'delegates/resolution_state'
-      require_relative 'delegates/specification_provider'
-
-      include Bundler::Molinillo::Delegates::ResolutionState
-      include Bundler::Molinillo::Delegates::SpecificationProvider
-
-      # Processes the topmost available {RequirementState} on the stack
-      # @return [void]
-      def process_topmost_state
-        if possibility
-          attempt_to_activate
-        else
-          create_conflict
-          unwind_for_conflict
-        end
-      rescue CircularDependencyError => underlying_error
-        create_conflict(underlying_error)
-        unwind_for_conflict
-      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 and pushes the initial state for the resolution, based upon the
-      # {#requested} dependencies
-      # @return [void]
-      def push_initial_state
-        graph = DependencyGraph.new.tap do |dg|
-          original_requested.each do |requested|
-            vertex = dg.add_vertex(name_for(requested), nil, true)
-            vertex.explicit_requirements << requested
-          end
-          dg.tag(:initial_state)
-        end
-
-        push_state_for_requirements(original_requested, true, graph)
-      end
-
-      # Unwinds the states stack because a conflict has been encountered
-      # @return [void]
-      def unwind_for_conflict
-        details_for_unwind = build_details_for_unwind
-        unwind_options = unused_unwind_options
-        debug(depth) { "Unwinding for conflict: #{requirement} to #{details_for_unwind.state_index / 2}" }
-        conflicts.tap do |c|
-          sliced_states = states.slice!((details_for_unwind.state_index + 1)..-1)
-          raise_error_unless_state(c)
-          activated.rewind_to(sliced_states.first || :initial_state) if sliced_states
-          state.conflicts = c
-          state.unused_unwind_options = unwind_options
-          filter_possibilities_after_unwind(details_for_unwind)
-          index = states.size - 1
-          @parents_of.each { |_, a| a.reject! { |i| i >= index } }
-          state.unused_unwind_options.reject! { |uw| uw.state_index >= index }
-        end
-      end
-
-      # Raises a VersionConflict error, or any underlying error, if there is no
-      # current state
-      # @return [void]
-      def raise_error_unless_state(conflicts)
-        return if state
-
-        error = conflicts.values.map(&:underlying_error).compact.first
-        raise error || VersionConflict.new(conflicts, specification_provider)
-      end
-
-      # @return [UnwindDetails] Details of the nearest index to which we could unwind
-      def build_details_for_unwind
-        # Get the possible unwinds for the current conflict
-        current_conflict = conflicts[name]
-        binding_requirements = binding_requirements_for_conflict(current_conflict)
-        unwind_details = unwind_options_for_requirements(binding_requirements)
-
-        last_detail_for_current_unwind = unwind_details.sort.last
-        current_detail = last_detail_for_current_unwind
-
-        # Look for past conflicts that could be unwound to affect the
-        # requirement tree for the current conflict
-        all_reqs = last_detail_for_current_unwind.all_requirements
-        all_reqs_size = all_reqs.size
-        relevant_unused_unwinds = unused_unwind_options.select do |alternative|
-          diff_reqs = all_reqs - alternative.requirements_unwound_to_instead
-          next if diff_reqs.size == all_reqs_size
-          # Find the highest index unwind whilst looping through
-          current_detail = alternative if alternative > current_detail
-          alternative
-        end
-
-        # Add the current unwind options to the `unused_unwind_options` array.
-        # The "used" option will be filtered out during `unwind_for_conflict`.
-        state.unused_unwind_options += unwind_details.reject { |detail| detail.state_index == -1 }
-
-        # Update the requirements_unwound_to_instead on any relevant unused unwinds
-        relevant_unused_unwinds.each do |d|
-          (d.requirements_unwound_to_instead << current_detail.state_requirement).uniq!
-        end
-        unwind_details.each do |d|
-          (d.requirements_unwound_to_instead << current_detail.state_requirement).uniq!
-        end
-
-        current_detail
-      end
-
-      # @param [Array<Object>] binding_requirements array of requirements that combine to create a conflict
-      # @return [Array<UnwindDetails>] array of UnwindDetails that have a chance
-      #    of resolving the passed requirements
-      def unwind_options_for_requirements(binding_requirements)
-        unwind_details = []
-
-        trees = []
-        binding_requirements.reverse_each do |r|
-          partial_tree = [r]
-          trees << partial_tree
-          unwind_details << UnwindDetails.new(-1, nil, partial_tree, binding_requirements, trees, [])
-
-          # If this requirement has alternative possibilities, check if any would
-          # satisfy the other requirements that created this conflict
-          requirement_state = find_state_for(r)
-          if conflict_fixing_possibilities?(requirement_state, binding_requirements)
-            unwind_details << UnwindDetails.new(
-              states.index(requirement_state),
-              r,
-              partial_tree,
-              binding_requirements,
-              trees,
-              []
-            )
-          end
-
-          # Next, look at the parent of this requirement, and check if the requirement
-          # could have been avoided if an alternative PossibilitySet had been chosen
-          parent_r = parent_of(r)
-          next if parent_r.nil?
-          partial_tree.unshift(parent_r)
-          requirement_state = find_state_for(parent_r)
-          if requirement_state.possibilities.any? { |set| !set.dependencies.include?(r) }
-            unwind_details << UnwindDetails.new(
-              states.index(requirement_state),
-              parent_r,
-              partial_tree,
-              binding_requirements,
-              trees,
-              []
-            )
-          end
-
-          # Finally, look at the grandparent and up of this requirement, looking
-          # for any possibilities that wouldn't create their parent requirement
-          grandparent_r = parent_of(parent_r)
-          until grandparent_r.nil?
-            partial_tree.unshift(grandparent_r)
-            requirement_state = find_state_for(grandparent_r)
-            if requirement_state.possibilities.any? { |set| !set.dependencies.include?(parent_r) }
-              unwind_details << UnwindDetails.new(
-                states.index(requirement_state),
-                grandparent_r,
-                partial_tree,
-                binding_requirements,
-                trees,
-                []
-              )
-            end
-            parent_r = grandparent_r
-            grandparent_r = parent_of(parent_r)
-          end
-        end
-
-        unwind_details
-      end
-
-      # @param [DependencyState] state
-      # @param [Array] binding_requirements array of requirements
-      # @return [Boolean] whether or not the given state has any possibilities
-      #    that could satisfy the given requirements
-      def conflict_fixing_possibilities?(state, binding_requirements)
-        return false unless state
-
-        state.possibilities.any? do |possibility_set|
-          possibility_set.possibilities.any? do |poss|
-            possibility_satisfies_requirements?(poss, binding_requirements)
-          end
-        end
-      end
-
-      # Filter's a state's possibilities to remove any that would not fix the
-      # conflict we've just rewound from
-      # @param [UnwindDetails] unwind_details details of the conflict just
-      #   unwound from
-      # @return [void]
-      def filter_possibilities_after_unwind(unwind_details)
-        return unless state && !state.possibilities.empty?
-
-        if unwind_details.unwinding_to_primary_requirement?
-          filter_possibilities_for_primary_unwind(unwind_details)
-        else
-          filter_possibilities_for_parent_unwind(unwind_details)
-        end
-      end
-
-      # Filter's a state's possibilities to remove any that would not satisfy
-      # the requirements in the conflict we've just rewound from
-      # @param [UnwindDetails] unwind_details details of the conflict just unwound from
-      # @return [void]
-      def filter_possibilities_for_primary_unwind(unwind_details)
-        unwinds_to_state = unused_unwind_options.select { |uw| uw.state_index == unwind_details.state_index }
-        unwinds_to_state << unwind_details
-        unwind_requirement_sets = unwinds_to_state.map(&:conflicting_requirements)
-
-        state.possibilities.reject! do |possibility_set|
-          possibility_set.possibilities.none? do |poss|
-            unwind_requirement_sets.any? do |requirements|
-              possibility_satisfies_requirements?(poss, requirements)
-            end
-          end
-        end
-      end
-
-      # @param [Object] possibility a single possibility
-      # @param [Array] requirements an array of requirements
-      # @return [Boolean] whether the possibility satisfies all of the
-      #    given requirements
-      def possibility_satisfies_requirements?(possibility, requirements)
-        name = name_for(possibility)
-
-        activated.tag(:swap)
-        activated.set_payload(name, possibility) if activated.vertex_named(name)
-        satisfied = requirements.all? { |r| requirement_satisfied_by?(r, activated, possibility) }
-        activated.rewind_to(:swap)
-
-        satisfied
-      end
-
-      # Filter's a state's possibilities to remove any that would (eventually)
-      # create a requirement in the conflict we've just rewound from
-      # @param [UnwindDetails] unwind_details details of the conflict just unwound from
-      # @return [void]
-      def filter_possibilities_for_parent_unwind(unwind_details)
-        unwinds_to_state = unused_unwind_options.select { |uw| uw.state_index == unwind_details.state_index }
-        unwinds_to_state << unwind_details
-
-        primary_unwinds = unwinds_to_state.select(&:unwinding_to_primary_requirement?).uniq
-        parent_unwinds = unwinds_to_state.uniq - primary_unwinds
-
-        allowed_possibility_sets = primary_unwinds.flat_map do |unwind|
-          states[unwind.state_index].possibilities.select do |possibility_set|
-            possibility_set.possibilities.any? do |poss|
-              possibility_satisfies_requirements?(poss, unwind.conflicting_requirements)
-            end
-          end
-        end
-
-        requirements_to_avoid = parent_unwinds.flat_map(&:sub_dependencies_to_avoid)
-
-        state.possibilities.reject! do |possibility_set|
-          !allowed_possibility_sets.include?(possibility_set) &&
-            (requirements_to_avoid - possibility_set.dependencies).empty?
-        end
-      end
-
-      # @param [Conflict] conflict
-      # @return [Array] minimal array of requirements that would cause the passed
-      #    conflict to occur.
-      def binding_requirements_for_conflict(conflict)
-        return [conflict.requirement] if conflict.possibility.nil?
-
-        possible_binding_requirements = conflict.requirements.values.flatten(1).uniq
-
-        # When there's a `CircularDependency` error the conflicting requirement
-        # (the one causing the circular) won't be `conflict.requirement`
-        # (which won't be for the right state, because we won't have created it,
-        # because it's circular).
-        # We need to make sure we have that requirement in the conflict's list,
-        # otherwise we won't be able to unwind properly, so we just return all
-        # the requirements for the conflict.
-        return possible_binding_requirements if conflict.underlying_error
-
-        possibilities = search_for(conflict.requirement)
-
-        # If all the requirements together don't filter out all possibilities,
-        # then the only two requirements we need to consider are the initial one
-        # (where the dependency's version was first chosen) and the last
-        if binding_requirement_in_set?(nil, possible_binding_requirements, possibilities)
-          return [conflict.requirement, requirement_for_existing_name(name_for(conflict.requirement))].compact
-        end
-
-        # Loop through the possible binding requirements, removing each one
-        # that doesn't bind. Use a `reverse_each` as we want the earliest set of
-        # binding requirements, and don't use `reject!` as we wish to refine the
-        # array *on each iteration*.
-        binding_requirements = possible_binding_requirements.dup
-        possible_binding_requirements.reverse_each do |req|
-          next if req == conflict.requirement
-          unless binding_requirement_in_set?(req, binding_requirements, possibilities)
-            binding_requirements -= [req]
-          end
-        end
-
-        binding_requirements
-      end
-
-      # @param [Object] requirement we wish to check
-      # @param [Array] possible_binding_requirements array of requirements
-      # @param [Array] possibilities array of possibilities the requirements will be used to filter
-      # @return [Boolean] whether or not the given requirement is required to filter
-      #    out all elements of the array of possibilities.
-      def binding_requirement_in_set?(requirement, possible_binding_requirements, possibilities)
-        possibilities.any? do |poss|
-          possibility_satisfies_requirements?(poss, possible_binding_requirements - [requirement])
-        end
-      end
-
-      # @param [Object] requirement
-      # @return [Object] the requirement that led to `requirement` being added
-      #   to the list of requirements.
-      def parent_of(requirement)
-        return unless requirement
-        return unless index = @parents_of[requirement].last
-        return unless parent_state = @states[index]
-        parent_state.requirement
-      end
-
-      # @param [String] name
-      # @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 vertex = activated.vertex_named(name)
-        return nil unless vertex.payload
-        states.find { |s| s.name == name }.requirement
-      end
-
-      # @param [Object] requirement
-      # @return [ResolutionState] the state whose `requirement` is the given
-      #   `requirement`.
-      def find_state_for(requirement)
-        return nil unless requirement
-        states.find { |i| requirement == i.requirement }
-      end
-
-      # @param [Object] underlying_error
-      # @return [Conflict] a {Conflict} that reflects the failure to activate
-      #   the {#possibility} in conjunction with the current {#state}
-      def create_conflict(underlying_error = nil)
-        vertex = activated.vertex_named(name)
-        locked_requirement = locked_requirement_named(name)
-
-        requirements = {}
-        unless vertex.explicit_requirements.empty?
-          requirements[name_for_explicit_dependency_source] = vertex.explicit_requirements
-        end
-        requirements[name_for_locking_dependency_source] = [locked_requirement] if locked_requirement
-        vertex.incoming_edges.each do |edge|
-          (requirements[edge.origin.payload.latest_version] ||= []).unshift(edge.requirement)
-        end
-
-        activated_by_name = {}
-        activated.each { |v| activated_by_name[v.name] = v.payload.latest_version if v.payload }
-        conflicts[name] = Conflict.new(
-          requirement,
-          requirements,
-          vertex.payload && vertex.payload.latest_version,
-          possibility,
-          locked_requirement,
-          requirement_trees,
-          activated_by_name,
-          underlying_error
-        )
-      end
-
-      # @return [Array<Array<Object>>] The different requirement
-      #   trees that led to every requirement for the current spec.
-      def requirement_trees
-        vertex = activated.vertex_named(name)
-        vertex.requirements.map { |r| requirement_tree_for(r) }
-      end
-
-      # @param [Object] requirement
-      # @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_vertex = activated.vertex_named(name)
-        if existing_vertex.payload
-          debug(depth) { "Found existing spec (#{existing_vertex.payload})" }
-          attempt_to_filter_existing_spec(existing_vertex)
-        else
-          latest = possibility.latest_version
-          possibility.possibilities.select! do |possibility|
-            requirement_satisfied_by?(requirement, activated, possibility)
-          end
-          if possibility.latest_version.nil?
-            # ensure there's a possibility for better error messages
-            possibility.possibilities << latest if latest
-            create_conflict
-            unwind_for_conflict
-          else
-            activate_new_spec
-          end
-        end
-      end
-
-      # Attempts to update the existing vertex's `PossibilitySet` with a filtered version
-      # @return [void]
-      def attempt_to_filter_existing_spec(vertex)
-        filtered_set = filtered_possibility_set(vertex)
-        if !filtered_set.possibilities.empty?
-          activated.set_payload(name, filtered_set)
-          new_requirements = requirements.dup
-          push_state_for_requirements(new_requirements, false)
-        else
-          create_conflict
-          debug(depth) { "Unsatisfied by existing spec (#{vertex.payload})" }
-          unwind_for_conflict
-        end
-      end
-
-      # Generates a filtered version of the existing vertex's `PossibilitySet` using the
-      # current state's `requirement`
-      # @param [Object] vertex existing vertex
-      # @return [PossibilitySet] filtered possibility set
-      def filtered_possibility_set(vertex)
-        PossibilitySet.new(vertex.payload.dependencies, vertex.payload.possibilities & possibility.possibilities)
-      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_new_spec
-        conflicts.delete(name)
-        debug(depth) { "Activated #{name} at #{possibility}" }
-        activated.set_payload(name, possibility)
-        require_nested_dependencies_for(possibility)
-      end
-
-      # Requires the dependencies that the recently activated spec has
-      # @param [Object] possibility_set the PossibilitySet that has just been
-      #   activated
-      # @return [void]
-      def require_nested_dependencies_for(possibility_set)
-        nested_dependencies = dependencies_for(possibility_set.latest_version)
-        debug(depth) { "Requiring nested dependencies (#{nested_dependencies.join(', ')})" }
-        nested_dependencies.each do |d|
-          activated.add_child_vertex(name_for(d), nil, [name_for(possibility_set.latest_version)], d)
-          parent_index = states.size - 1
-          parents = @parents_of[d]
-          parents << parent_index if parents.empty?
-        end
-
-        push_state_for_requirements(requirements + nested_dependencies, !nested_dependencies.empty?)
-      end
-
-      # Pushes a new {DependencyState} that encapsulates both existing and new
-      # requirements
-      # @param [Array] new_requirements
-      # @param [Boolean] requires_sort
-      # @param [Object] new_activated
-      # @return [void]
-      def push_state_for_requirements(new_requirements, requires_sort = true, new_activated = activated)
-        new_requirements = sort_dependencies(new_requirements.uniq, new_activated, conflicts) if requires_sort
-        new_requirement = nil
-        loop do
-          new_requirement = new_requirements.shift
-          break if new_requirement.nil? || states.none? { |s| s.requirement == new_requirement }
-        end
-        new_name = new_requirement ? name_for(new_requirement) : ''.freeze
-        possibilities = possibilities_for_requirement(new_requirement)
-        handle_missing_or_push_dependency_state DependencyState.new(
-          new_name, new_requirements, new_activated,
-          new_requirement, possibilities, depth, conflicts.dup, unused_unwind_options.dup
-        )
-      end
-
-      # Checks a proposed requirement with any existing locked requirement
-      # before generating an array of possibilities for it.
-      # @param [Object] requirement the proposed requirement
-      # @param [Object] activated
-      # @return [Array] possibilities
-      def possibilities_for_requirement(requirement, activated = self.activated)
-        return [] unless requirement
-        if locked_requirement_named(name_for(requirement))
-          return locked_requirement_possibility_set(requirement, activated)
-        end
-
-        group_possibilities(search_for(requirement))
-      end
-
-      # @param [Object] requirement the proposed requirement
-      # @param [Object] activated
-      # @return [Array] possibility set containing only the locked requirement, if any
-      def locked_requirement_possibility_set(requirement, activated = self.activated)
-        all_possibilities = search_for(requirement)
-        locked_requirement = locked_requirement_named(name_for(requirement))
-
-        # Longwinded way to build a possibilities array with either the locked
-        # requirement or nothing in it. Required, since the API for
-        # locked_requirement isn't guaranteed.
-        locked_possibilities = all_possibilities.select do |possibility|
-          requirement_satisfied_by?(locked_requirement, activated, possibility)
-        end
-
-        group_possibilities(locked_possibilities)
-      end
-
-      # Build an array of PossibilitySets, with each element representing a group of
-      # dependency versions that all have the same sub-dependency version constraints
-      # and are contiguous.
-      # @param [Array] possibilities an array of possibilities
-      # @return [Array<PossibilitySet>] an array of possibility sets
-      def group_possibilities(possibilities)
-        possibility_sets = []
-        current_possibility_set = nil
-
-        possibilities.reverse_each do |possibility|
-          dependencies = dependencies_for(possibility)
-          if current_possibility_set && dependencies_equal?(current_possibility_set.dependencies, dependencies)
-            current_possibility_set.possibilities.unshift(possibility)
-          else
-            possibility_sets.unshift(PossibilitySet.new(dependencies, [possibility]))
-            current_possibility_set = possibility_sets.first
-          end
-        end
-
-        possibility_sets
-      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 vertex 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.dup, false, state.activated)
-        else
-          states.push(state).tap { activated.tag(state) }
-        end
-      end
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/resolver.rb b/lib/bundler/vendor/molinillo/lib/molinillo/resolver.rb
deleted file mode 100644
index 95eaab5991..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/resolver.rb
+++ /dev/null
@@ -1,46 +0,0 @@
-# frozen_string_literal: true
-
-require_relative 'dependency_graph'
-
-module Bundler::Molinillo
-  # This class encapsulates a dependency resolver.
-  # The resolver is responsible for determining which set of dependencies to
-  # activate, with feedback from the {#specification_provider}
-  #
-  #
-  class Resolver
-    require_relative '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
-
-    # Initializes a new resolver.
-    # @param  [SpecificationProvider] specification_provider
-    #   see {#specification_provider}
-    # @param  [UI] resolver_ui
-    #   see {#resolver_ui}
-    def initialize(specification_provider, resolver_ui)
-      @specification_provider = specification_provider
-      @resolver_ui = resolver_ui
-    end
-
-    # Resolves the requested dependencies into a {DependencyGraph},
-    # locking to the base dependency graph (if specified)
-    # @param [Array] requested an array of 'requested' dependencies that the
-    #   {#specification_provider} can understand
-    # @param [DependencyGraph,nil] base the base dependency graph to which
-    #   dependencies should be 'locked'
-    def resolve(requested, base = DependencyGraph.new)
-      Resolution.new(specification_provider,
-                     resolver_ui,
-                     requested,
-                     base).
-        resolve
-    end
-  end
-end
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/state.rb b/lib/bundler/vendor/molinillo/lib/molinillo/state.rb
deleted file mode 100644
index 68fa1f54e3..0000000000
--- a/lib/bundler/vendor/molinillo/lib/molinillo/state.rb
+++ /dev/null
@@ -1,58 +0,0 @@
-# frozen_string_literal: true
-
-module Bundler::Molinillo
-  # A state that a {Resolution} can be in
-  # @attr [String] name the name of the current requirement
-  # @attr [Array<Object>] requirements currently unsatisfied requirements
-  # @attr [DependencyGraph] activated the graph of activated dependencies
-  # @attr [Object] requirement the current requirement
-  # @attr [Object] possibilities the possibilities to satisfy the current requirement
-  # @attr [Integer] depth the depth of the resolution
-  # @attr [Hash] conflicts unresolved conflicts, indexed by dependency name
-  # @attr [Array<UnwindDetails>] unused_unwind_options unwinds for previous conflicts that weren't explored
-  ResolutionState = Struct.new(
-    :name,
-    :requirements,
-    :activated,
-    :requirement,
-    :possibilities,
-    :depth,
-    :conflicts,
-    :unused_unwind_options
-  )
-
-  class ResolutionState
-    # Returns an empty resolution state
-    # @return [ResolutionState] an empty state
-    def self.empty
-      new(nil, [], DependencyGraph.new, nil, nil, 0, {}, [])
-    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,
-        requirement,
-        [possibilities.pop],
-        depth + 1,
-        conflicts.dup,
-        unused_unwind_options.dup
-      ).tap do |state|
-        state.activated.tag(state)
-      end
-    end
-  end
-
-  # A state that encapsulates a single possibility to fulfill the given
-  # {#requirement}
-  class PossibilityState < ResolutionState
-  end
-end
diff --git a/lib/bundler/vendor/pub_grub/LICENSE.txt b/lib/bundler/vendor/pub_grub/LICENSE.txt
new file mode 100644
index 0000000000..411840a4a0
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/LICENSE.txt
@@ -0,0 +1,21 @@
+The MIT License (MIT)
+
+Copyright (c) 2018 John Hawthorn
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub.rb
new file mode 100644
index 0000000000..eaaba3fc98
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub.rb
@@ -0,0 +1,31 @@
+require_relative "pub_grub/package"
+require_relative "pub_grub/static_package_source"
+require_relative "pub_grub/term"
+require_relative "pub_grub/version_range"
+require_relative "pub_grub/version_constraint"
+require_relative "pub_grub/version_union"
+require_relative "pub_grub/version_solver"
+require_relative "pub_grub/incompatibility"
+require_relative 'pub_grub/solve_failure'
+require_relative 'pub_grub/failure_writer'
+require_relative 'pub_grub/version'
+
+module Bundler::PubGrub
+  class << self
+    attr_writer :logger
+
+    def logger
+      @logger || default_logger
+    end
+
+    private
+
+    def default_logger
+      require "logger"
+
+      logger = ::Logger.new(STDERR)
+      logger.level = $DEBUG ? ::Logger::DEBUG : ::Logger::WARN
+      @logger = logger
+    end
+  end
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/assignment.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/assignment.rb
new file mode 100644
index 0000000000..2236a97b5b
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/assignment.rb
@@ -0,0 +1,20 @@
+module Bundler::PubGrub
+  class Assignment
+    attr_reader :term, :cause, :decision_level, :index
+    def initialize(term, cause, decision_level, index)
+      @term = term
+      @cause = cause
+      @decision_level = decision_level
+      @index = index
+    end
+
+    def self.decision(package, version, decision_level, index)
+      term = Term.new(VersionConstraint.exact(package, version), true)
+      new(term, :decision, decision_level, index)
+    end
+
+    def decision?
+      cause == :decision
+    end
+  end
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/basic_package_source.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/basic_package_source.rb
new file mode 100644
index 0000000000..dce20d37ad
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/basic_package_source.rb
@@ -0,0 +1,189 @@
+require_relative 'version_constraint'
+require_relative 'incompatibility'
+
+module Bundler::PubGrub
+  # Types:
+  #
+  # Where possible, Bundler::PubGrub will accept user-defined types, so long as they quack.
+  #
+  # ## "Package":
+  #
+  # This class will be used to represent the various packages being solved for.
+  # .to_s will be called when displaying errors and debugging info, it should
+  # probably return the package's name.
+  # It must also have a reasonable definition of #== and #hash
+  #
+  # Example classes: String ("rails")
+  #
+  #
+  # ## "Version":
+  #
+  # This class will be used to represent a single version number.
+  #
+  # Versions don't need to store their associated package, however they will
+  # only be compared against other versions of the same package.
+  #
+  # It must be Comparible (and implement <=> reasonably)
+  #
+  # Example classes: Gem::Version, Integer
+  #
+  #
+  # ## "Dependency"
+  #
+  # This class represents the requirement one package has on another. It is
+  # returned by dependencies_for(package, version) and will be passed to
+  # parse_dependency to convert it to a format Bundler::PubGrub understands.
+  #
+  # It must also have a reasonable definition of #==
+  #
+  # Example classes: String ("~> 1.0"), Gem::Requirement
+  #
+  class BasicPackageSource
+    # Override me!
+    #
+    # This is called per package to find all possible versions of a package.
+    #
+    # It is called at most once per-package
+    #
+    # Returns: Array of versions for a package, in preferred order of selection
+    def all_versions_for(package)
+      raise NotImplementedError
+    end
+
+    # Override me!
+    #
+    # Returns: Hash in the form of { package => requirement, ... }
+    def dependencies_for(package, version)
+      raise NotImplementedError
+    end
+
+    # Override me!
+    #
+    # Convert a (user-defined) dependency into a format Bundler::PubGrub understands.
+    #
+    # Package is passed to this method but for many implementations is not
+    # needed.
+    #
+    # Returns: either a Bundler::PubGrub::VersionRange, Bundler::PubGrub::VersionUnion, or a
+    #   Bundler::PubGrub::VersionConstraint
+    def parse_dependency(package, dependency)
+      raise NotImplementedError
+    end
+
+    # Override me!
+    #
+    # If not overridden, this will call dependencies_for with the root package.
+    #
+    # Returns: Hash in the form of { package => requirement, ... } (see dependencies_for)
+    def root_dependencies
+      dependencies_for(@root_package, @root_version)
+    end
+
+    # Override me (maybe)
+    #
+    # If not overridden, the order returned by all_versions_for will be used
+    #
+    # Returns: Array of versions in preferred order
+    def sort_versions_by_preferred(package, sorted_versions)
+      indexes = @version_indexes[package]
+      sorted_versions.sort_by { |version| indexes[version] }
+    end
+
+    def initialize
+      @root_package = Package.root
+      @root_version = Package.root_version
+
+      @cached_versions = Hash.new do |h,k|
+        if k == @root_package
+          h[k] = [@root_version]
+        else
+          h[k] = all_versions_for(k)
+        end
+      end
+      @sorted_versions = Hash.new { |h,k| h[k] = @cached_versions[k].sort }
+      @version_indexes = Hash.new { |h,k| h[k] = @cached_versions[k].each.with_index.to_h }
+
+      @cached_dependencies = Hash.new do |packages, package|
+        if package == @root_package
+          packages[package] = {
+            @root_version => root_dependencies
+          }
+        else
+          packages[package] = Hash.new do |versions, version|
+            versions[version] = dependencies_for(package, version)
+          end
+        end
+      end
+    end
+
+    def versions_for(package, range=VersionRange.any)
+      versions = range.select_versions(@sorted_versions[package])
+
+      # Conditional avoids (among other things) calling
+      # sort_versions_by_preferred with the root package
+      if versions.size > 1
+        sort_versions_by_preferred(package, versions)
+      else
+        versions
+      end
+    end
+
+    def no_versions_incompatibility_for(_package, unsatisfied_term)
+      cause = Incompatibility::NoVersions.new(unsatisfied_term)
+
+      Incompatibility.new([unsatisfied_term], cause: cause)
+    end
+
+    def incompatibilities_for(package, version)
+      package_deps = @cached_dependencies[package]
+      sorted_versions = @sorted_versions[package]
+      package_deps[version].map do |dep_package, dep_constraint_name|
+        low = high = sorted_versions.index(version)
+
+        # find version low such that all >= low share the same dep
+        while low > 0 &&
+            package_deps[sorted_versions[low - 1]][dep_package] == dep_constraint_name
+          low -= 1
+        end
+        low =
+          if low == 0
+            nil
+          else
+            sorted_versions[low]
+          end
+
+        # find version high such that all < high share the same dep
+        while high < sorted_versions.length &&
+            package_deps[sorted_versions[high]][dep_package] == dep_constraint_name
+          high += 1
+        end
+        high =
+          if high == sorted_versions.length
+            nil
+          else
+            sorted_versions[high]
+          end
+
+        range = VersionRange.new(min: low, max: high, include_min: true)
+
+        self_constraint = VersionConstraint.new(package, range: range)
+
+        if !@packages.include?(dep_package)
+          # no such package -> this version is invalid
+        end
+
+        dep_constraint = parse_dependency(dep_package, dep_constraint_name)
+        if !dep_constraint
+          # falsey indicates this dependency was invalid
+          cause = Bundler::PubGrub::Incompatibility::InvalidDependency.new(dep_package, dep_constraint_name)
+          return [Incompatibility.new([Term.new(self_constraint, true)], cause: cause)]
+        elsif !dep_constraint.is_a?(VersionConstraint)
+          # Upgrade range/union to VersionConstraint
+          dep_constraint = VersionConstraint.new(dep_package, range: dep_constraint)
+        end
+
+        Incompatibility.new([Term.new(self_constraint, true), Term.new(dep_constraint, false)], cause: :dependency)
+      end
+    end
+  end
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/failure_writer.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/failure_writer.rb
new file mode 100644
index 0000000000..ee099b23f4
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/failure_writer.rb
@@ -0,0 +1,182 @@
+module Bundler::PubGrub
+  class FailureWriter
+    def initialize(root)
+      @root = root
+
+      # { Incompatibility => Integer }
+      @derivations = {}
+
+      # [ [ String, Integer or nil ] ]
+      @lines = []
+
+      # { Incompatibility => Integer }
+      @line_numbers = {}
+
+      count_derivations(root)
+    end
+
+    def write
+      return @root.to_s unless @root.conflict?
+
+      visit(@root)
+
+      padding = @line_numbers.empty? ? 0 : "(#{@line_numbers.values.last}) ".length
+
+      @lines.map do |message, number|
+        next "" if message.empty?
+
+        lead = number ? "(#{number}) " : ""
+        lead = lead.ljust(padding)
+        message = message.gsub("\n", "\n" + " " * (padding + 2))
+        "#{lead}#{message}"
+      end.join("\n")
+    end
+
+    private
+
+    def write_line(incompatibility, message, numbered:)
+      if numbered
+        number = @line_numbers.length + 1
+        @line_numbers[incompatibility] = number
+      end
+
+      @lines << [message, number]
+    end
+
+    def visit(incompatibility, conclusion: false)
+      raise unless incompatibility.conflict?
+
+      numbered = conclusion || @derivations[incompatibility] > 1;
+      conjunction = conclusion || incompatibility == @root ? "So," : "And"
+
+      cause = incompatibility.cause
+
+      if cause.conflict.conflict? && cause.other.conflict?
+        conflict_line = @line_numbers[cause.conflict]
+        other_line = @line_numbers[cause.other]
+
+        if conflict_line && other_line
+          write_line(
+            incompatibility,
+            "Because #{cause.conflict} (#{conflict_line})\nand #{cause.other} (#{other_line}),\n#{incompatibility}.",
+            numbered: numbered
+          )
+        elsif conflict_line || other_line
+          with_line    = conflict_line ? cause.conflict : cause.other
+          without_line = conflict_line ? cause.other : cause.conflict
+          line = @line_numbers[with_line]
+
+          visit(without_line);
+          write_line(
+            incompatibility,
+            "#{conjunction} because #{with_line} (#{line}),\n#{incompatibility}.",
+            numbered: numbered
+          )
+        else
+          single_line_conflict = single_line?(cause.conflict.cause)
+          single_line_other    = single_line?(cause.other.cause)
+
+          if single_line_conflict || single_line_other
+            first  = single_line_other ? cause.conflict : cause.other
+            second = single_line_other ? cause.other : cause.conflict
+            visit(first)
+            visit(second)
+            write_line(
+              incompatibility,
+              "Thus, #{incompatibility}.",
+              numbered: numbered
+            )
+          else
+            visit(cause.conflict, conclusion: true)
+            @lines << ["", nil]
+            visit(cause.other)
+
+            write_line(
+              incompatibility,
+              "#{conjunction} because #{cause.conflict} (#{@line_numbers[cause.conflict]}),\n#{incompatibility}.",
+              numbered: numbered
+            )
+          end
+        end
+      elsif cause.conflict.conflict? || cause.other.conflict?
+        derived = cause.conflict.conflict? ? cause.conflict : cause.other
+        ext     = cause.conflict.conflict? ? cause.other : cause.conflict
+
+        derived_line = @line_numbers[derived]
+        if derived_line
+          write_line(
+            incompatibility,
+            "Because #{ext}\nand #{derived} (#{derived_line}),\n#{incompatibility}.",
+            numbered: numbered
+          )
+        elsif collapsible?(derived)
+          derived_cause = derived.cause
+          if derived_cause.conflict.conflict?
+            collapsed_derived = derived_cause.conflict
+            collapsed_ext = derived_cause.other
+          else
+            collapsed_derived = derived_cause.other
+            collapsed_ext = derived_cause.conflict
+          end
+
+          visit(collapsed_derived)
+
+          write_line(
+            incompatibility,
+            "#{conjunction} because #{collapsed_ext}\nand #{ext},\n#{incompatibility}.",
+            numbered: numbered
+          )
+        else
+          visit(derived)
+          write_line(
+            incompatibility,
+            "#{conjunction} because #{ext},\n#{incompatibility}.",
+            numbered: numbered
+          )
+        end
+      else
+        write_line(
+          incompatibility,
+          "Because #{cause.conflict}\nand #{cause.other},\n#{incompatibility}.",
+          numbered: numbered
+        )
+      end
+    end
+
+    def single_line?(cause)
+      !cause.conflict.conflict? && !cause.other.conflict?
+    end
+
+    def collapsible?(incompatibility)
+      return false if @derivations[incompatibility] > 1
+
+      cause = incompatibility.cause
+      # If incompatibility is derived from two derived incompatibilities,
+      # there are too many transitive causes to display concisely.
+      return false if cause.conflict.conflict? && cause.other.conflict?
+
+      # If incompatibility is derived from two external incompatibilities, it
+      # tends to be confusing to collapse it.
+      return false unless cause.conflict.conflict? || cause.other.conflict?
+
+      # If incompatibility's internal cause is numbered, collapsing it would
+      # get too noisy.
+      complex = cause.conflict.conflict? ? cause.conflict : cause.other
+
+      !@line_numbers.has_key?(complex)
+    end
+
+    def count_derivations(incompatibility)
+      if @derivations.has_key?(incompatibility)
+        @derivations[incompatibility] += 1
+      else
+        @derivations[incompatibility] = 1
+        if incompatibility.conflict?
+          cause = incompatibility.cause
+          count_derivations(cause.conflict)
+          count_derivations(cause.other)
+        end
+      end
+    end
+  end
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/incompatibility.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/incompatibility.rb
new file mode 100644
index 0000000000..51e1fc3cdd
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/incompatibility.rb
@@ -0,0 +1,146 @@
+module Bundler::PubGrub
+  class Incompatibility
+    ConflictCause = Struct.new(:incompatibility, :satisfier) do
+      alias_method :conflict, :incompatibility
+      alias_method :other, :satisfier
+    end
+
+    InvalidDependency = Struct.new(:package, :constraint) do
+    end
+
+    NoVersions = Struct.new(:constraint) do
+    end
+
+    attr_reader :terms, :cause
+
+    def initialize(terms, cause:, custom_explanation: nil)
+      @cause = cause
+      @terms = cleanup_terms(terms)
+      @custom_explanation = custom_explanation
+
+      if cause == :dependency && @terms.length != 2
+        raise ArgumentError, "a dependency Incompatibility must have exactly two terms. Got #{@terms.inspect}"
+      end
+    end
+
+    def hash
+      cause.hash ^ terms.hash
+    end
+
+    def eql?(other)
+      cause.eql?(other.cause) &&
+        terms.eql?(other.terms)
+    end
+
+    def failure?
+      terms.empty? || (terms.length == 1 && Package.root?(terms[0].package) && terms[0].positive?)
+    end
+
+    def conflict?
+      ConflictCause === cause
+    end
+
+    # Returns all external incompatibilities in this incompatibility's
+    # derivation graph
+    def external_incompatibilities
+      if conflict?
+        [
+          cause.conflict,
+          cause.other
+        ].flat_map(&:external_incompatibilities)
+      else
+        [this]
+      end
+    end
+
+    def to_s
+      return @custom_explanation if @custom_explanation
+
+      case cause
+      when :root
+        "(root dependency)"
+      when :dependency
+        "#{terms[0].to_s(allow_every: true)} depends on #{terms[1].invert}"
+      when Bundler::PubGrub::Incompatibility::InvalidDependency
+        "#{terms[0].to_s(allow_every: true)} depends on unknown package #{cause.package}"
+      when Bundler::PubGrub::Incompatibility::NoVersions
+        "no versions satisfy #{cause.constraint}"
+      when Bundler::PubGrub::Incompatibility::ConflictCause
+        if failure?
+          "version solving has failed"
+        elsif terms.length == 1
+          term = terms[0]
+          if term.positive?
+            "#{terms[0].to_s(allow_every: true)} is forbidden"
+          else
+            "#{terms[0].invert} is required"
+          end
+        else
+          if terms.all?(&:positive?)
+            if terms.length == 2
+              "#{terms[0].to_s(allow_every: true)} is incompatible with #{terms[1]}"
+            else
+              "one of #{terms.map(&:to_s).join(" or ")} must be false"
+            end
+          elsif terms.all?(&:negative?)
+            if terms.length == 2
+              "either #{terms[0].invert} or #{terms[1].invert}"
+            else
+              "one of #{terms.map(&:invert).join(" or ")} must be true";
+            end
+          else
+            positive = terms.select(&:positive?)
+            negative = terms.select(&:negative?).map(&:invert)
+
+            if positive.length == 1
+              "#{positive[0].to_s(allow_every: true)} requires #{negative.join(" or ")}"
+            else
+              "if #{positive.join(" and ")} then #{negative.join(" or ")}"
+            end
+          end
+        end
+      else
+        raise "unhandled cause: #{cause.inspect}"
+      end
+    end
+
+    def inspect
+      "#<#{self.class} #{to_s}>"
+    end
+
+    def pretty_print(q)
+      q.group 2, "#<#{self.class}", ">" do
+        q.breakable
+        q.text to_s
+
+        q.breakable
+        q.text " caused by "
+        q.pp @cause
+      end
+    end
+
+    private
+
+    def cleanup_terms(terms)
+      terms.each do |term|
+        raise "#{term.inspect} must be a term" unless term.is_a?(Term)
+      end
+
+      if terms.length != 1 && ConflictCause === cause
+        terms = terms.reject do |term|
+          term.positive? && Package.root?(term.package)
+        end
+      end
+
+      # Optimized simple cases
+      return terms if terms.length <= 1
+      return terms if terms.length == 2 && terms[0].package != terms[1].package
+
+      terms.group_by(&:package).map do |package, common_terms|
+        common_terms.inject do |acc, term|
+          acc.intersect(term)
+        end
+      end
+    end
+  end
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/package.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/package.rb
new file mode 100644
index 0000000000..efb9d3da16
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/package.rb
@@ -0,0 +1,43 @@
+# frozen_string_literal: true
+
+module Bundler::PubGrub
+  class Package
+
+    attr_reader :name
+
+    def initialize(name)
+      @name = name
+    end
+
+    def inspect
+      "#<#{self.class} #{name.inspect}>"
+    end
+
+    def <=>(other)
+      name <=> other.name
+    end
+
+    ROOT = Package.new(:root)
+    ROOT_VERSION = 0
+
+    def self.root
+      ROOT
+    end
+
+    def self.root_version
+      ROOT_VERSION
+    end
+
+    def self.root?(package)
+      if package.respond_to?(:root?)
+        package.root?
+      else
+        package == root
+      end
+    end
+
+    def to_s
+      name.to_s
+    end
+  end
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/partial_solution.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/partial_solution.rb
new file mode 100644
index 0000000000..4c4b8ca844
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/partial_solution.rb
@@ -0,0 +1,121 @@
+require_relative 'assignment'
+
+module Bundler::PubGrub
+  class PartialSolution
+    attr_reader :assignments, :decisions
+    attr_reader :attempted_solutions
+
+    def initialize
+      reset!
+
+      @attempted_solutions = 1
+      @backtracking = false
+    end
+
+    def decision_level
+      @decisions.length
+    end
+
+    def relation(term)
+      package = term.package
+      return :overlap if !@terms.key?(package)
+
+      @relation_cache[package][term] ||=
+        @terms[package].relation(term)
+    end
+
+    def satisfies?(term)
+      relation(term) == :subset
+    end
+
+    def derive(term, cause)
+      add_assignment(Assignment.new(term, cause, decision_level, assignments.length))
+    end
+
+    def satisfier(term)
+      assignment =
+        @assignments_by[term.package].bsearch do |assignment_by|
+          @cumulative_assignments[assignment_by].satisfies?(term)
+        end
+
+      assignment || raise("#{term} unsatisfied")
+    end
+
+    # A list of unsatisfied terms
+    def unsatisfied
+      @required.keys.reject do |package|
+        @decisions.key?(package)
+      end.map do |package|
+        @terms[package]
+      end
+    end
+
+    def decide(package, version)
+      @attempted_solutions += 1 if @backtracking
+      @backtracking = false;
+
+      decisions[package] = version
+      assignment = Assignment.decision(package, version, decision_level, assignments.length)
+      add_assignment(assignment)
+    end
+
+    def backtrack(previous_level)
+      @backtracking = true
+
+      new_assignments = assignments.select do |assignment|
+        assignment.decision_level <= previous_level
+      end
+
+      new_decisions = Hash[decisions.first(previous_level)]
+
+      reset!
+
+      @decisions = new_decisions
+
+      new_assignments.each do |assignment|
+        add_assignment(assignment)
+      end
+    end
+
+    private
+
+    def reset!
+      # { Array<Assignment> }
+      @assignments = []
+
+      # { Package => Array<Assignment> }
+      @assignments_by = Hash.new { |h,k| h[k] = [] }
+      @cumulative_assignments = {}.compare_by_identity
+
+      # { Package => Package::Version }
+      @decisions = {}
+
+      # { Package => Term }
+      @terms = {}
+      @relation_cache = Hash.new { |h,k| h[k] = {} }
+
+      # { Package => Boolean }
+      @required = {}
+    end
+
+    def add_assignment(assignment)
+      term = assignment.term
+      package = term.package
+
+      @assignments << assignment
+      @assignments_by[package] << assignment
+
+      @required[package] = true if term.positive?
+
+      if @terms.key?(package)
+        old_term = @terms[package]
+        @terms[package] = old_term.intersect(term)
+      else
+        @terms[package] = term
+      end
+      @relation_cache[package].clear
+
+      @cumulative_assignments[assignment] = @terms[package]
+    end
+  end
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/rubygems.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/rubygems.rb
new file mode 100644
index 0000000000..245c23be22
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/rubygems.rb
@@ -0,0 +1,45 @@
+module Bundler::PubGrub
+  module RubyGems
+    extend self
+
+    def requirement_to_range(requirement)
+      ranges = requirement.requirements.map do |(op, ver)|
+        case op
+        when "~>"
+          name = "~> #{ver}"
+          bump = ver.class.new(ver.bump.to_s + ".A")
+          VersionRange.new(name: name, min: ver, max: bump, include_min: true)
+        when ">"
+          VersionRange.new(min: ver)
+        when ">="
+          VersionRange.new(min: ver, include_min: true)
+        when "<"
+          VersionRange.new(max: ver)
+        when "<="
+          VersionRange.new(max: ver, include_max: true)
+        when "="
+          VersionRange.new(min: ver, max: ver, include_min: true, include_max: true)
+        when "!="
+          VersionRange.new(min: ver, max: ver, include_min: true, include_max: true).invert
+        else
+          raise "bad version specifier: #{op}"
+        end
+      end
+
+      ranges.inject(&:intersect)
+    end
+
+    def requirement_to_constraint(package, requirement)
+      Bundler::PubGrub::VersionConstraint.new(package, range: requirement_to_range(requirement))
+    end
+
+    def parse_range(dep)
+      requirement_to_range(Gem::Requirement.new(dep))
+    end
+
+    def parse_constraint(package, dep)
+      range = parse_range(dep)
+      Bundler::PubGrub::VersionConstraint.new(package, range: range)
+    end
+  end
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/solve_failure.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/solve_failure.rb
new file mode 100644
index 0000000000..961a7a7c0c
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/solve_failure.rb
@@ -0,0 +1,19 @@
+require_relative 'failure_writer'
+
+module Bundler::PubGrub
+  class SolveFailure < StandardError
+    attr_reader :incompatibility
+
+    def initialize(incompatibility)
+      @incompatibility = incompatibility
+    end
+
+    def to_s
+      "Could not find compatible versions\n\n#{explanation}"
+    end
+
+    def explanation
+      @explanation ||= FailureWriter.new(@incompatibility).write
+    end
+  end
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/static_package_source.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/static_package_source.rb
new file mode 100644
index 0000000000..e895812bed
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/static_package_source.rb
@@ -0,0 +1,53 @@
+require_relative 'package'
+require_relative 'version_constraint'
+require_relative 'incompatibility'
+require_relative 'basic_package_source'
+
+module Bundler::PubGrub
+  class StaticPackageSource < BasicPackageSource
+    class DSL
+      def initialize(packages, root_deps)
+        @packages = packages
+        @root_deps = root_deps
+      end
+
+      def root(deps:)
+        @root_deps.update(deps)
+      end
+
+      def add(name, version, deps: {})
+        version = Gem::Version.new(version)
+        @packages[name] ||= {}
+        raise ArgumentError, "#{name} #{version} declared twice" if @packages[name].key?(version)
+        @packages[name][version] = deps
+      end
+    end
+
+    def initialize
+      @root_deps = {}
+      @packages = {}
+
+      yield DSL.new(@packages, @root_deps)
+
+      super()
+    end
+
+    def all_versions_for(package)
+      @packages[package].keys
+    end
+
+    def root_dependencies
+      @root_deps
+    end
+
+    def dependencies_for(package, version)
+      @packages[package][version]
+    end
+
+    def parse_dependency(package, dependency)
+      return false unless @packages.key?(package)
+
+      Bundler::PubGrub::RubyGems.parse_constraint(package, dependency)
+    end
+  end
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/term.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/term.rb
new file mode 100644
index 0000000000..1d0f763378
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/term.rb
@@ -0,0 +1,105 @@
+module Bundler::PubGrub
+  class Term
+    attr_reader :package, :constraint, :positive
+
+    def initialize(constraint, positive)
+      @constraint = constraint
+      @package = @constraint.package
+      @positive = positive
+    end
+
+    def to_s(allow_every: false)
+      if positive
+        @constraint.to_s(allow_every: allow_every)
+      else
+        "not #{@constraint}"
+      end
+    end
+
+    def hash
+      constraint.hash ^ positive.hash
+    end
+
+    def eql?(other)
+      positive == other.positive &&
+        constraint.eql?(other.constraint)
+    end
+
+    def invert
+      self.class.new(@constraint, !@positive)
+    end
+    alias_method :inverse, :invert
+
+    def intersect(other)
+      raise ArgumentError, "packages must match" if package != other.package
+
+      if positive? && other.positive?
+        self.class.new(constraint.intersect(other.constraint), true)
+      elsif negative? && other.negative?
+        self.class.new(constraint.union(other.constraint), false)
+      else
+        positive = positive? ? self : other
+        negative = negative? ? self : other
+        self.class.new(positive.constraint.intersect(negative.constraint.invert), true)
+      end
+    end
+
+    def difference(other)
+      intersect(other.invert)
+    end
+
+    def relation(other)
+      if positive? && other.positive?
+        constraint.relation(other.constraint)
+      elsif negative? && other.positive?
+        if constraint.allows_all?(other.constraint)
+          :disjoint
+        else
+          :overlap
+        end
+      elsif positive? && other.negative?
+        if !other.constraint.allows_any?(constraint)
+          :subset
+        elsif other.constraint.allows_all?(constraint)
+          :disjoint
+        else
+          :overlap
+        end
+      elsif negative? && other.negative?
+        if constraint.allows_all?(other.constraint)
+          :subset
+        else
+          :overlap
+        end
+      else
+        raise
+      end
+    end
+
+    def normalized_constraint
+      @normalized_constraint ||= positive ? constraint : constraint.invert
+    end
+
+    def satisfies?(other)
+      raise ArgumentError, "packages must match" unless package == other.package
+
+      relation(other) == :subset
+    end
+
+    def positive?
+      @positive
+    end
+
+    def negative?
+      !positive?
+    end
+
+    def empty?
+      @empty ||= normalized_constraint.empty?
+    end
+
+    def inspect
+      "#<#{self.class} #{self}>"
+    end
+  end
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/version.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/version.rb
new file mode 100644
index 0000000000..d7984b3863
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/version.rb
@@ -0,0 +1,3 @@
+module Bundler::PubGrub
+  VERSION = "0.5.0"
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/version_constraint.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_constraint.rb
new file mode 100644
index 0000000000..c222542435
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_constraint.rb
@@ -0,0 +1,124 @@
+require_relative 'version_range'
+
+module Bundler::PubGrub
+  class VersionConstraint
+    attr_reader :package, :range
+
+    # @param package [Bundler::PubGrub::Package]
+    # @param range [Bundler::PubGrub::VersionRange]
+    def initialize(package, range: nil)
+      @package = package
+      @range = range
+    end
+
+    def hash
+      package.hash ^ range.hash
+    end
+
+    def eql?(other)
+      package.eql?(other.package) &&
+        range.eql?(other.range)
+    end
+
+    class << self
+      def exact(package, version)
+        range = VersionRange.new(min: version, max: version, include_min: true, include_max: true)
+        new(package, range: range)
+      end
+
+      def any(package)
+        new(package, range: VersionRange.any)
+      end
+
+      def empty(package)
+        new(package, range: VersionRange.empty)
+      end
+    end
+
+    def intersect(other)
+      unless package == other.package
+        raise ArgumentError, "Can only intersect between VersionConstraint of the same package"
+      end
+
+      self.class.new(package, range: range.intersect(other.range))
+    end
+
+    def union(other)
+      unless package == other.package
+        raise ArgumentError, "Can only intersect between VersionConstraint of the same package"
+      end
+
+      self.class.new(package, range: range.union(other.range))
+    end
+
+    def invert
+      new_range = range.invert
+      self.class.new(package, range: new_range)
+    end
+
+    def difference(other)
+      intersect(other.invert)
+    end
+
+    def allows_all?(other)
+      range.allows_all?(other.range)
+    end
+
+    def allows_any?(other)
+      range.intersects?(other.range)
+    end
+
+    def subset?(other)
+      other.allows_all?(self)
+    end
+
+    def overlap?(other)
+      other.allows_any?(self)
+    end
+
+    def disjoint?(other)
+      !overlap?(other)
+    end
+
+    def relation(other)
+      if subset?(other)
+        :subset
+      elsif overlap?(other)
+        :overlap
+      else
+        :disjoint
+      end
+    end
+
+    def to_s(allow_every: false)
+      if Package.root?(package)
+        package.to_s
+      elsif allow_every && any?
+        "every version of #{package}"
+      else
+        "#{package} #{constraint_string}"
+      end
+    end
+
+    def constraint_string
+      if any?
+        ">= 0"
+      else
+        range.to_s
+      end
+    end
+
+    def empty?
+      range.empty?
+    end
+
+    # Does this match every version of the package
+    def any?
+      range.any?
+    end
+
+    def inspect
+      "#<#{self.class} #{self}>"
+    end
+  end
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/version_range.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_range.rb
new file mode 100644
index 0000000000..e384178973
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_range.rb
@@ -0,0 +1,409 @@
+# frozen_string_literal: true
+
+module Bundler::PubGrub
+  class VersionRange
+    attr_reader :min, :max, :include_min, :include_max
+
+    alias_method :include_min?, :include_min
+    alias_method :include_max?, :include_max
+
+    class Empty < VersionRange
+      undef_method :min, :max
+      undef_method :include_min, :include_min?
+      undef_method :include_max, :include_max?
+
+      def initialize
+      end
+
+      def empty?
+        true
+      end
+
+      def eql?
+        other.empty?
+      end
+
+      def hash
+        [].hash
+      end
+
+      def intersects?(_)
+        false
+      end
+
+      def intersect(other)
+        self
+      end
+
+      def allows_all?(other)
+        other.empty?
+      end
+
+      def include?(_)
+        false
+      end
+
+      def any?
+        false
+      end
+
+      def to_s
+        "(no versions)"
+      end
+
+      def ==(other)
+        other.class == self.class
+      end
+
+      def invert
+        VersionRange.any
+      end
+
+      def select_versions(_)
+        []
+      end
+    end
+
+    EMPTY = Empty.new
+
+    def self.empty
+      EMPTY
+    end
+
+    def self.any
+      new
+    end
+
+    def initialize(min: nil, max: nil, include_min: false, include_max: false, name: nil)
+      @min = min
+      @max = max
+      @include_min = include_min
+      @include_max = include_max
+      @name = name
+    end
+
+    def hash
+      @hash ||= min.hash ^ max.hash ^ include_min.hash ^ include_max.hash
+    end
+
+    def eql?(other)
+      if other.is_a?(VersionRange)
+        min.eql?(other.min) &&
+          max.eql?(other.max) &&
+          include_min.eql?(other.include_min) &&
+          include_max.eql?(other.include_max)
+      else
+        ranges.eql?(other.ranges)
+      end
+    end
+
+    def ranges
+      [self]
+    end
+
+    def include?(version)
+      compare_version(version) == 0
+    end
+
+    # Partitions passed versions into [lower, within, higher]
+    #
+    # versions must be sorted
+    def partition_versions(versions)
+      min_index =
+        if !min || versions.empty?
+          0
+        elsif include_min?
+          (0..versions.size).bsearch { |i| versions[i].nil? || versions[i] >= min }
+        else
+          (0..versions.size).bsearch { |i| versions[i].nil? || versions[i] > min }
+        end
+
+      lower = versions.slice(0, min_index)
+      versions = versions.slice(min_index, versions.size)
+
+      max_index =
+        if !max || versions.empty?
+          versions.size
+        elsif include_max?
+          (0..versions.size).bsearch { |i| versions[i].nil? || versions[i] > max }
+        else
+          (0..versions.size).bsearch { |i| versions[i].nil? || versions[i] >= max }
+        end
+
+      [
+        lower,
+        versions.slice(0, max_index),
+        versions.slice(max_index, versions.size)
+      ]
+    end
+
+    # Returns versions which are included by this range.
+    #
+    # versions must be sorted
+    def select_versions(versions)
+      return versions if any?
+
+      partition_versions(versions)[1]
+    end
+
+    def compare_version(version)
+      if min
+        case version <=> min
+        when -1
+          return -1
+        when 0
+          return -1 if !include_min
+        when 1
+        end
+      end
+
+      if max
+        case version <=> max
+        when -1
+        when 0
+          return 1 if !include_max
+        when 1
+          return 1
+        end
+      end
+
+      0
+    end
+
+    def strictly_lower?(other)
+      return false if !max || !other.min
+
+      case max <=> other.min
+      when 0
+        !include_max || !other.include_min
+      when -1
+        true
+      when 1
+        false
+      end
+    end
+
+    def strictly_higher?(other)
+      other.strictly_lower?(self)
+    end
+
+    def intersects?(other)
+      return false if other.empty?
+      return other.intersects?(self) if other.is_a?(VersionUnion)
+      !strictly_lower?(other) && !strictly_higher?(other)
+    end
+    alias_method :allows_any?, :intersects?
+
+    def intersect(other)
+      return other if other.empty?
+      return other.intersect(self) if other.is_a?(VersionUnion)
+
+      min_range =
+        if !min
+          other
+        elsif !other.min
+          self
+        else
+          case min <=> other.min
+          when 0
+            include_min ? other : self
+          when -1
+            other
+          when 1
+            self
+          end
+        end
+
+      max_range =
+        if !max
+          other
+        elsif !other.max
+          self
+        else
+          case max <=> other.max
+          when 0
+            include_max ? other : self
+          when -1
+            self
+          when 1
+            other
+          end
+        end
+
+      if !min_range.equal?(max_range) && min_range.min && max_range.max
+        case min_range.min <=> max_range.max
+        when -1
+        when 0
+          if !min_range.include_min || !max_range.include_max
+            return EMPTY
+          end
+        when 1
+          return EMPTY
+        end
+      end
+
+      VersionRange.new(
+        min: min_range.min,
+        include_min: min_range.include_min,
+        max: max_range.max,
+        include_max: max_range.include_max
+      )
+    end
+
+    # The span covered by two ranges
+    #
+    # If self and other are contiguous, this builds a union of the two ranges.
+    # (if they aren't you are probably calling the wrong method)
+    def span(other)
+      return self if other.empty?
+
+      min_range =
+        if !min
+          self
+        elsif !other.min
+          other
+        else
+          case min <=> other.min
+          when 0
+            include_min ? self : other
+          when -1
+            self
+          when 1
+            other
+          end
+        end
+
+      max_range =
+        if !max
+          self
+        elsif !other.max
+          other
+        else
+          case max <=> other.max
+          when 0
+            include_max ? self : other
+          when -1
+            other
+          when 1
+            self
+          end
+        end
+
+      VersionRange.new(
+        min: min_range.min,
+        include_min: min_range.include_min,
+        max: max_range.max,
+        include_max: max_range.include_max
+      )
+    end
+
+    def union(other)
+      return other.union(self) if other.is_a?(VersionUnion)
+
+      if contiguous_to?(other)
+        span(other)
+      else
+        VersionUnion.union([self, other])
+      end
+    end
+
+    def contiguous_to?(other)
+      return false if other.empty?
+
+      intersects?(other) ||
+        (min == other.max && (include_min || other.include_max)) ||
+        (max == other.min && (include_max || other.include_min))
+    end
+
+    def allows_all?(other)
+      return true if other.empty?
+
+      if other.is_a?(VersionUnion)
+        return VersionUnion.new([self]).allows_all?(other)
+      end
+
+      return false if max && !other.max
+      return false if min && !other.min
+
+      if min
+        case min <=> other.min
+        when -1
+        when 0
+          return false if !include_min && other.include_min
+        when 1
+          return false
+        end
+      end
+
+      if max
+        case max <=> other.max
+        when -1
+          return false
+        when 0
+          return false if !include_max && other.include_max
+        when 1
+        end
+      end
+
+      true
+    end
+
+    def any?
+      !min && !max
+    end
+
+    def empty?
+      false
+    end
+
+    def to_s
+      @name ||= constraints.join(", ")
+    end
+
+    def inspect
+      "#<#{self.class} #{to_s}>"
+    end
+
+    def upper_invert
+      return self.class.empty unless max
+
+      VersionRange.new(min: max, include_min: !include_max)
+    end
+
+    def invert
+      return self.class.empty if any?
+
+      low = VersionRange.new(max: min, include_max: !include_min)
+      high = VersionRange.new(min: max, include_min: !include_max)
+
+      if !min
+        high
+      elsif !max
+        low
+      else
+        low.union(high)
+      end
+    end
+
+    def ==(other)
+      self.class == other.class &&
+        min == other.min &&
+        max == other.max &&
+        include_min == other.include_min &&
+        include_max == other.include_max
+    end
+
+    private
+
+    def constraints
+      return ["any"] if any?
+      return ["= #{min}"] if min == max
+
+      c = []
+      c << "#{include_min ? ">=" : ">"} #{min}" if min
+      c << "#{include_max ? "<=" : "<"} #{max}" if max
+      c
+    end
+
+  end
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb
new file mode 100644
index 0000000000..ea5e455968
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_solver.rb
@@ -0,0 +1,240 @@
+require_relative 'partial_solution'
+require_relative 'term'
+require_relative 'incompatibility'
+require_relative 'solve_failure'
+
+module Bundler::PubGrub
+  class VersionSolver
+    attr_reader :logger
+    attr_reader :source
+    attr_reader :solution
+
+    def initialize(source:, root: Package.root, logger: Bundler::PubGrub.logger)
+      @logger = logger
+
+      @source = source
+
+      # { package => [incompatibility, ...]}
+      @incompatibilities = Hash.new do |h, k|
+        h[k] = []
+      end
+
+      @seen_incompatibilities = {}
+
+      @solution = PartialSolution.new
+
+      add_incompatibility Incompatibility.new([
+        Term.new(VersionConstraint.any(root), false)
+      ], cause: :root)
+
+      propagate(root)
+    end
+
+    def solved?
+      solution.unsatisfied.empty?
+    end
+
+    # Returns true if there is more work to be done, false otherwise
+    def work
+      return false if solved?
+
+      next_package = choose_package_version
+      propagate(next_package)
+
+      if solved?
+        logger.info { "Solution found after #{solution.attempted_solutions} attempts:" }
+        solution.decisions.each do |package, version|
+          next if Package.root?(package)
+          logger.info { "* #{package} #{version}" }
+        end
+
+        false
+      else
+        true
+      end
+    end
+
+    def solve
+      work until solved?
+
+      solution.decisions
+    end
+
+    alias_method :result, :solve
+
+    private
+
+    def propagate(initial_package)
+      changed = [initial_package]
+      while package = changed.shift
+        @incompatibilities[package].reverse_each do |incompatibility|
+          result = propagate_incompatibility(incompatibility)
+          if result == :conflict
+            root_cause = resolve_conflict(incompatibility)
+            changed.clear
+            changed << propagate_incompatibility(root_cause)
+          elsif result # should be a Package
+            changed << result
+          end
+        end
+        changed.uniq!
+      end
+    end
+
+    def propagate_incompatibility(incompatibility)
+      unsatisfied = nil
+      incompatibility.terms.each do |term|
+        relation = solution.relation(term)
+        if relation == :disjoint
+          return nil
+        elsif relation == :overlap
+          # If more than one term is inconclusive, we can't deduce anything
+          return nil if unsatisfied
+          unsatisfied = term
+        end
+      end
+
+      if !unsatisfied
+        return :conflict
+      end
+
+      logger.debug { "derived: #{unsatisfied.invert}" }
+
+      solution.derive(unsatisfied.invert, incompatibility)
+
+      unsatisfied.package
+    end
+
+    def next_package_to_try
+      solution.unsatisfied.min_by do |term|
+        package = term.package
+        range = term.constraint.range
+        matching_versions = source.versions_for(package, range)
+        higher_versions = source.versions_for(package, range.upper_invert)
+
+        [matching_versions.count <= 1 ? 0 : 1, higher_versions.count]
+      end.package
+    end
+
+    def choose_package_version
+      if solution.unsatisfied.empty?
+        logger.info "No packages unsatisfied. Solving complete!"
+        return nil
+      end
+
+      package = next_package_to_try
+      unsatisfied_term = solution.unsatisfied.find { |t| t.package == package }
+      version = source.versions_for(package, unsatisfied_term.constraint.range).first
+
+      if version.nil?
+        add_incompatibility source.no_versions_incompatibility_for(package, unsatisfied_term)
+        return package
+      end
+
+      conflict = false
+
+      source.incompatibilities_for(package, version).each do |incompatibility|
+        if @seen_incompatibilities.include?(incompatibility)
+          logger.debug { "knew: #{incompatibility}" }
+          next
+        end
+        @seen_incompatibilities[incompatibility] = true
+
+        add_incompatibility incompatibility
+
+        conflict ||= incompatibility.terms.all? do |term|
+          term.package == package || solution.satisfies?(term)
+        end
+      end
+
+      unless conflict
+        logger.info { "selecting #{package} #{version}" }
+
+        solution.decide(package, version)
+      end
+
+      package
+    end
+
+    def resolve_conflict(incompatibility)
+      logger.info { "conflict: #{incompatibility}" }
+
+      new_incompatibility = false
+
+      while !incompatibility.failure?
+        most_recent_term = nil
+        most_recent_satisfier = nil
+        difference = nil
+
+        previous_level = 1
+
+        incompatibility.terms.each do |term|
+          satisfier = solution.satisfier(term)
+
+          if most_recent_satisfier.nil?
+            most_recent_term = term
+            most_recent_satisfier = satisfier
+          elsif most_recent_satisfier.index < satisfier.index
+            previous_level = [previous_level, most_recent_satisfier.decision_level].max
+            most_recent_term = term
+            most_recent_satisfier = satisfier
+            difference = nil
+          else
+            previous_level = [previous_level, satisfier.decision_level].max
+          end
+
+          if most_recent_term == term
+            difference = most_recent_satisfier.term.difference(most_recent_term)
+            if difference.empty?
+              difference = nil
+            else
+              difference_satisfier = solution.satisfier(difference.inverse)
+              previous_level = [previous_level, difference_satisfier.decision_level].max
+            end
+          end
+        end
+
+        if previous_level < most_recent_satisfier.decision_level ||
+            most_recent_satisfier.decision?
+
+          logger.info { "backtracking to #{previous_level}" }
+          solution.backtrack(previous_level)
+
+          if new_incompatibility
+            add_incompatibility(incompatibility)
+          end
+
+          return incompatibility
+        end
+
+        new_terms = []
+        new_terms += incompatibility.terms - [most_recent_term]
+        new_terms += most_recent_satisfier.cause.terms.reject { |term|
+          term.package == most_recent_satisfier.term.package
+        }
+        if difference
+          new_terms << difference.invert
+        end
+
+        incompatibility = Incompatibility.new(new_terms, cause: Incompatibility::ConflictCause.new(incompatibility, most_recent_satisfier.cause))
+
+        new_incompatibility = true
+
+        partially = difference ? " partially" : ""
+        logger.info { "! #{most_recent_term} is#{partially} satisfied by #{most_recent_satisfier.term}" }
+        logger.info { "! which is caused by #{most_recent_satisfier.cause}" }
+        logger.info { "! thus #{incompatibility}" }
+      end
+
+      raise SolveFailure.new(incompatibility)
+    end
+
+    def add_incompatibility(incompatibility)
+      logger.debug { "fact: #{incompatibility}" }
+      incompatibility.terms.each do |term|
+        package = term.package
+        @incompatibilities[package] << incompatibility
+      end
+    end
+  end
+end
diff --git a/lib/bundler/vendor/pub_grub/lib/pub_grub/version_union.rb b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_union.rb
new file mode 100644
index 0000000000..b66c603dfd
--- /dev/null
+++ b/lib/bundler/vendor/pub_grub/lib/pub_grub/version_union.rb
@@ -0,0 +1,178 @@
+# frozen_string_literal: true
+
+module Bundler::PubGrub
+  class VersionUnion
+    attr_reader :ranges
+
+    def self.normalize_ranges(ranges)
+      ranges = ranges.flat_map do |range|
+        range.ranges
+      end
+
+      ranges.reject!(&:empty?)
+
+      return [] if ranges.empty?
+
+      mins, ranges = ranges.partition { |r| !r.min }
+      original_ranges = mins + ranges.sort_by { |r| [r.min, r.include_min ? 0 : 1] }
+      ranges = [original_ranges.shift]
+      original_ranges.each do |range|
+        if ranges.last.contiguous_to?(range)
+          ranges << ranges.pop.span(range)
+        else
+          ranges << range
+        end
+      end
+
+      ranges
+    end
+
+    def self.union(ranges, normalize: true)
+      ranges = normalize_ranges(ranges) if normalize
+
+      if ranges.size == 0
+        VersionRange.empty
+      elsif ranges.size == 1
+        ranges[0]
+      else
+        new(ranges)
+      end
+    end
+
+    def initialize(ranges)
+      raise ArgumentError unless ranges.all? { |r| r.instance_of?(VersionRange) }
+      @ranges = ranges
+    end
+
+    def hash
+      ranges.hash
+    end
+
+    def eql?(other)
+      ranges.eql?(other.ranges)
+    end
+
+    def include?(version)
+      !!ranges.bsearch {|r| r.compare_version(version) }
+    end
+
+    def select_versions(all_versions)
+      versions = []
+      ranges.inject(all_versions) do |acc, range|
+        _, matching, higher = range.partition_versions(acc)
+        versions.concat matching
+        higher
+      end
+      versions
+    end
+
+    def intersects?(other)
+      my_ranges = ranges.dup
+      other_ranges = other.ranges.dup
+
+      my_range = my_ranges.shift
+      other_range = other_ranges.shift
+      while my_range && other_range
+        if my_range.intersects?(other_range)
+          return true
+        end
+
+        if !my_range.max || (other_range.max && other_range.max < my_range.max)
+          other_range = other_ranges.shift
+        else
+          my_range = my_ranges.shift
+        end
+      end
+    end
+    alias_method :allows_any?, :intersects?
+
+    def allows_all?(other)
+      my_ranges = ranges.dup
+
+      my_range = my_ranges.shift
+
+      other.ranges.all? do |other_range|
+        while my_range
+          break if my_range.allows_all?(other_range)
+          my_range = my_ranges.shift
+        end
+
+        !!my_range
+      end
+    end
+
+    def empty?
+      false
+    end
+
+    def any?
+      false
+    end
+
+    def intersect(other)
+      my_ranges = ranges.dup
+      other_ranges = other.ranges.dup
+      new_ranges = []
+
+      my_range = my_ranges.shift
+      other_range = other_ranges.shift
+      while my_range && other_range
+        new_ranges << my_range.intersect(other_range)
+
+        if !my_range.max || (other_range.max && other_range.max < my_range.max)
+          other_range = other_ranges.shift
+        else
+          my_range = my_ranges.shift
+        end
+      end
+      new_ranges.reject!(&:empty?)
+      VersionUnion.union(new_ranges, normalize: false)
+    end
+
+    def upper_invert
+      ranges.last.upper_invert
+    end
+
+    def invert
+      ranges.map(&:invert).inject(:intersect)
+    end
+
+    def union(other)
+      VersionUnion.union([self, other])
+    end
+
+    def to_s
+      output = []
+
+      ranges = self.ranges.dup
+      while !ranges.empty?
+        ne = []
+        range = ranges.shift
+        while !ranges.empty? && ranges[0].min == range.max
+          ne << range.max
+          range = range.span(ranges.shift)
+        end
+
+        ne.map! {|x| "!= #{x}" }
+        if ne.empty?
+          output << range.to_s
+        elsif range.any?
+          output << ne.join(', ')
+        else
+          output << "#{range}, #{ne.join(', ')}"
+        end
+      end
+
+      output.join(" OR ")
+    end
+
+    def inspect
+      "#<#{self.class} #{to_s}>"
+    end
+
+    def ==(other)
+      self.class == other.class &&
+        self.ranges == other.ranges
+    end
+  end
+end