diff options
Diffstat (limited to 'lib/bundler/vendor/molinillo/lib/molinillo')
19 files changed, 1803 insertions, 0 deletions
diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/delegates/resolution_state.rb b/lib/bundler/vendor/molinillo/lib/molinillo/delegates/resolution_state.rb new file mode 100644 index 0000000000..253c18764f --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/delegates/resolution_state.rb @@ -0,0 +1,50 @@ +# 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 + 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 new file mode 100644 index 0000000000..29f48d5b3c --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/delegates/specification_provider.rb @@ -0,0 +1,80 @@ +# 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#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 new file mode 100644 index 0000000000..76e84ab7e6 --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb @@ -0,0 +1,222 @@ +# frozen_string_literal: true +require 'set' +require 'tsort' + +require 'bundler/vendor/molinillo/lib/molinillo/dependency_graph/log' +require 'bundler/vendor/molinillo/lib/molinillo/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 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) + 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 + + # @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_node = vertex_named(parent_name) + add_edge(parent_node, 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([origin, destination]) + 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 + 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 new file mode 100644 index 0000000000..e0dfe6cbbd --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/action.rb @@ -0,0 +1,35 @@ +# 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 new file mode 100644 index 0000000000..9092e4d546 --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb @@ -0,0 +1,65 @@ +# frozen_string_literal: true +require 'bundler/vendor/molinillo/lib/molinillo/dependency_graph/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 new file mode 100644 index 0000000000..eda4251801 --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_vertex.rb @@ -0,0 +1,61 @@ +# frozen_string_literal: true +require 'bundler/vendor/molinillo/lib/molinillo/dependency_graph/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 new file mode 100644 index 0000000000..e9125a59c6 --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/delete_edge.rb @@ -0,0 +1,62 @@ +# frozen_string_literal: true +require 'bundler/vendor/molinillo/lib/molinillo/dependency_graph/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 new file mode 100644 index 0000000000..d20b2cb0e0 --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb @@ -0,0 +1,60 @@ +# frozen_string_literal: true +require 'bundler/vendor/molinillo/lib/molinillo/dependency_graph/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 new file mode 100644 index 0000000000..72a705e023 --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/log.rb @@ -0,0 +1,125 @@ +# frozen_string_literal: true +require 'bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular' +require 'bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_vertex' +require 'bundler/vendor/molinillo/lib/molinillo/dependency_graph/delete_edge' +require 'bundler/vendor/molinillo/lib/molinillo/dependency_graph/detach_vertex_named' +require 'bundler/vendor/molinillo/lib/molinillo/dependency_graph/set_payload' +require 'bundler/vendor/molinillo/lib/molinillo/dependency_graph/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 new file mode 100644 index 0000000000..8d8e10fedf --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/set_payload.rb @@ -0,0 +1,45 @@ +# frozen_string_literal: true +require 'bundler/vendor/molinillo/lib/molinillo/dependency_graph/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 new file mode 100644 index 0000000000..53524d36ad --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/tag.rb @@ -0,0 +1,35 @@ +# frozen_string_literal: true +require 'bundler/vendor/molinillo/lib/molinillo/dependency_graph/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 new file mode 100644 index 0000000000..eab989e7bc --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/vertex.rb @@ -0,0 +1,125 @@ +# 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 + 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 [Array<Vertex>] the vertices of {#graph} where `self` is a + # {#descendent?} + def recursive_predecessors + vertices = predecessors + vertices += vertices.map(&:recursive_predecessors).flatten(1) + vertices.uniq! + vertices + end + + # @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 [Array<Vertex>] the vertices of {#graph} where `self` is an + # {#ancestor?} + def recursive_successors + vertices = successors + vertices += vertices.map(&:recursive_successors).flatten(1) + vertices.uniq! + vertices + end + + # @return [String] a string suitable for debugging + def inspect + "#{self.class}:#{name}(#{payload.inspect})" + end + + # @return [Boolean] whether the two vertices are equal, determined + # by a recursive traversal of each {Vertex#successors} + def ==(other) + 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 true iff there is a path following edges within this {#graph} + def path_to?(other) + equal?(other) || successors.any? { |v| v.path_to?(other) } + end + + alias descendent? path_to? + + # Is there a path from `other` to `self` following edges in the + # dependency graph? + # @return true iff there is a path following edges within this {#graph} + def ancestor?(other) + other.path_to?(self) + end + + alias is_reachable_from? ancestor? + end + end +end diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/errors.rb b/lib/bundler/vendor/molinillo/lib/molinillo/errors.rb new file mode 100644 index 0000000000..f904bd0814 --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/errors.rb @@ -0,0 +1,75 @@ +# 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 + 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 iff a {Vertex} is added to a + # {DependencyGraph} that has a {DependencyGraph::Vertex#path_to?} an + # existing {DependencyGraph::Vertex} + class CircularDependencyError < ResolverError + # [Set<Object>] the dependencies responsible for causing the error + attr_reader :dependencies + + # Initializes a new error with the given circular vertices. + # @param [Array<DependencyGraph::Vertex>] nodes the nodes in the dependency + # that caused the error + def initialize(nodes) + super "There is a circular dependency between #{nodes.map(&:name).join(' and ')}" + @dependencies = nodes.map(&:payload).to_set + end + end + + # An error caused by conflicts in version + class VersionConflict < ResolverError + # @return [{String => Resolution::Conflict}] the conflicts that caused + # resolution to fail + attr_reader :conflicts + + # Initializes a new error with the given version conflicts. + # @param [{String => Resolution::Conflict}] conflicts see {#conflicts} + def initialize(conflicts) + pairs = [] + conflicts.values.flatten.map(&:requirements).flatten.each do |conflicting| + conflicting.each do |source, conflict_requirements| + conflict_requirements.each do |c| + pairs << [c, source] + end + end + end + + super "Unable to satisfy the following requirements:\n\n" \ + "#{pairs.map { |r, d| "- `#{r}` required by `#{d}`" }.join("\n")}" + @conflicts = conflicts + end + end +end diff --git a/lib/bundler/vendor/molinillo/lib/molinillo/gem_metadata.rb b/lib/bundler/vendor/molinillo/lib/molinillo/gem_metadata.rb new file mode 100644 index 0000000000..a4fb6dd68e --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/gem_metadata.rb @@ -0,0 +1,5 @@ +# frozen_string_literal: true +module Bundler::Molinillo + # The version of Bundler::Molinillo. + VERSION = '0.5.7'.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 new file mode 100644 index 0000000000..0f1ad195f2 --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/modules/specification_provider.rb @@ -0,0 +1,100 @@ +# frozen_string_literal: true +module Bundler::Molinillo + # Provides information about specifcations and dependencies to the resolver, + # allowing the {Resolver} class to remain generic while still providing power + # and flexibility. + # + # This module contains the methods that users of Bundler::Molinillo must to implement, + # using knowledge of their own model classes. + module SpecificationProvider + # Search for the specifications that match the given dependency. + # The specifications in the returned array will be considered in reverse + # order, so the latest version ought to be last. + # @note This method should be 'pure', i.e. the return value should depend + # only on the `dependency` parameter. + # + # @param [Object] dependency + # @return [Array<Object>] the specifications that satisfy the given + # `dependency`. + def search_for(dependency) + [] + end + + # Returns the dependencies of `specification`. + # @note This method should be 'pure', i.e. the return value should depend + # only on the `specification` parameter. + # + # @param [Object] specification + # @return [Array<Object>] the dependencies that are required by the given + # `specification`. + def dependencies_for(specification) + [] + end + + # Determines whether the given `requirement` is satisfied by the given + # `spec`, in the context of the current `activated` dependency graph. + # + # @param [Object] requirement + # @param [DependencyGraph] activated the current dependency graph in the + # resolution process. + # @param [Object] spec + # @return [Boolean] whether `requirement` is satisfied by `spec` in the + # context of the current `activated` dependency graph. + def requirement_satisfied_by?(requirement, activated, spec) + true + end + + # Returns the name for the given `dependency`. + # @note This method should be 'pure', i.e. the return value should depend + # only on the `dependency` parameter. + # + # @param [Object] dependency + # @return [String] the name for the given `dependency`. + def name_for(dependency) + dependency.to_s + end + + # @return [String] the name of the source of explicit dependencies, i.e. + # those passed to {Resolver#resolve} directly. + def name_for_explicit_dependency_source + 'user-specified dependency' + end + + # @return [String] the name of the source of 'locked' dependencies, i.e. + # those passed to {Resolver#resolve} directly as the `base` + def name_for_locking_dependency_source + 'Lockfile' + end + + # Sort dependencies so that the ones that are easiest to resolve are first. + # Easiest to resolve is (usually) defined by: + # 1) Is this dependency already activated? + # 2) How relaxed are the requirements? + # 3) Are there any conflicts for this dependency? + # 4) How many possibilities are there to satisfy this dependency? + # + # @param [Array<Object>] dependencies + # @param [DependencyGraph] activated the current dependency graph in the + # resolution process. + # @param [{String => Array<Conflict>}] conflicts + # @return [Array<Object>] a sorted copy of `dependencies`. + def sort_dependencies(dependencies, activated, conflicts) + dependencies.sort_by do |dependency| + name = name_for(dependency) + [ + activated.vertex_named(name).payload ? 0 : 1, + conflicts[name] ? 0 : 1, + ] + end + end + + # 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 new file mode 100644 index 0000000000..d47cfa2928 --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/modules/ui.rb @@ -0,0 +1,65 @@ +# 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) + output.puts debug_info.split("\n").map { |s| ' ' * depth + s } + end + end + + # Whether or not debug messages should be printed. + # By default, whether or not the `MOLINILLO_DEBUG` environment variable is + # set. + # + # @return [Boolean] + def debug? + 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 new file mode 100644 index 0000000000..1845966a75 --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/resolution.rb @@ -0,0 +1,494 @@ +# 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 the spec that was unable to be activated due + # to a conflict + # @attr [Object] locked_requirement the relevant locking requirement. + # @attr [Array<Array<Object>>] requirement_trees the different requirement + # trees that led to every requirement for the conflicting name. + # @attr [{String=>Object}] activated_by_name the already-activated specs. + Conflict = Struct.new( + :requirement, + :requirements, + :existing, + :possibility, + :locked_requirement, + :requirement_trees, + :activated_by_name + ) + + # @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 unless state.requirements.any? || state.requirement + indicate_progress + if state.respond_to?(:pop_possibility_state) # DependencyState + debug(depth) { "Creating possibility state for #{requirement} (#{possibilities.count} remaining)" } + state.pop_possibility_state.tap do |s| + if s + states.push(s) + activated.tag(s) + end + end + end + process_topmost_state + end + + activated.freeze + ensure + end_resolution + end + + # @return [Integer] the number of resolver iterations in between calls to + # {#resolver_ui}'s {UI#indicate_progress} method + attr_accessor :iteration_rate + private :iteration_rate + + # @return [Time] the time at which resolution began + attr_accessor :started_at + private :started_at + + # @return [Array<ResolutionState>] the stack of states for the resolution + attr_accessor :states + private :states + + private + + # Sets up the resolution process + # @return [void] + def start_resolution + @started_at = Time.now + + handle_missing_or_push_dependency_state(initial_state) + + debug { "Starting resolution (#{@started_at})\nUser-requested dependencies: #{original_requested}" } + resolver_ui.before_resolution + end + + # Ends the resolution process + # @return [void] + def end_resolution + resolver_ui.after_resolution + debug do + "Finished resolution (#{@iteration_counter} steps) " \ + "(Took #{(ended_at = Time.now) - @started_at} seconds) (#{ended_at})" + end + debug { 'Unactivated: ' + Hash[activated.vertices.reject { |_n, v| v.payload }].keys.join(', ') } if state + debug { 'Activated: ' + Hash[activated.vertices.select { |_n, v| v.payload }].keys.join(', ') } if state + end + + require 'bundler/vendor/molinillo/lib/molinillo/state' + require 'bundler/vendor/molinillo/lib/molinillo/modules/specification_provider' + + require 'bundler/vendor/molinillo/lib/molinillo/delegates/resolution_state' + require 'bundler/vendor/molinillo/lib/molinillo/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 if state.is_a? PossibilityState + unwind_for_conflict until possibility && state.is_a?(DependencyState) + end + end + + # @return [Object] the current possibility that the resolution is trying + # to activate + def possibility + possibilities.last + end + + # @return [RequirementState] the current state the resolution is + # operating upon + def state + states.last + end + + # Creates the initial state for the resolution, based upon the + # {#requested} dependencies + # @return [DependencyState] the initial state for the resolution + def initial_state + graph = DependencyGraph.new.tap do |dg| + original_requested.each { |r| dg.add_vertex(name_for(r), nil, true).tap { |v| v.explicit_requirements << r } } + dg.tag(:initial_state) + end + + requirements = sort_dependencies(original_requested, graph, {}) + initial_requirement = requirements.shift + DependencyState.new( + initial_requirement && name_for(initial_requirement), + requirements, + graph, + initial_requirement, + initial_requirement && search_for(initial_requirement), + 0, + {} + ) + end + + # Unwinds the states stack because a conflict has been encountered + # @return [void] + def unwind_for_conflict + debug(depth) { "Unwinding for conflict: #{requirement} to #{state_index_for_unwind / 2}" } + conflicts.tap do |c| + sliced_states = states.slice!((state_index_for_unwind + 1)..-1) + raise VersionConflict.new(c) unless state + activated.rewind_to(sliced_states.first || :initial_state) if sliced_states + state.conflicts = c + index = states.size - 1 + @parents_of.each { |_, a| a.reject! { |i| i >= index } } + end + end + + # @return [Integer] The index to which the resolution should unwind in the + # case of conflict. + def state_index_for_unwind + current_requirement = requirement + existing_requirement = requirement_for_existing_name(name) + index = -1 + [current_requirement, existing_requirement].each do |r| + until r.nil? + current_state = find_state_for(r) + if state_any?(current_state) + current_index = states.index(current_state) + index = current_index if current_index > index + break + end + r = parent_of(r) + end + end + + index + end + + # @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 + + # @return [Object] the requirement that led to a version of a possibility + # with the given name being activated. + def requirement_for_existing_name(name) + return nil unless activated.vertex_named(name).payload + states.find { |s| s.name == name }.requirement + end + + # @return [ResolutionState] the state whose `requirement` is the given + # `requirement`. + def find_state_for(requirement) + return nil unless requirement + states.reverse_each.find { |i| requirement == i.requirement && i.is_a?(DependencyState) } + end + + # @return [Boolean] whether or not the given state has any possibilities + # left. + def state_any?(state) + state && state.possibilities.any? + end + + # @return [Conflict] a {Conflict} that reflects the failure to activate + # the {#possibility} in conjunction with the current {#state} + def create_conflict + vertex = activated.vertex_named(name) + 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 { |edge| (requirements[edge.origin.payload] ||= []).unshift(edge.requirement) } + + activated_by_name = {} + activated.each { |v| activated_by_name[v.name] = v.payload if v.payload } + conflicts[name] = Conflict.new( + requirement, + requirements, + vertex.payload, + possibility, + locked_requirement, + requirement_trees, + activated_by_name + ) + 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 + + # @return [Array<Object>] the list of requirements that led to + # `requirement` being required. + def requirement_tree_for(requirement) + tree = [] + while requirement + tree.unshift(requirement) + requirement = parent_of(requirement) + end + tree + end + + # Indicates progress roughly once every second + # @return [void] + def indicate_progress + @iteration_counter += 1 + @progress_rate ||= resolver_ui.progress_rate + if iteration_rate.nil? + if Time.now - started_at >= @progress_rate + self.iteration_rate = @iteration_counter + end + end + + if iteration_rate && (@iteration_counter % iteration_rate) == 0 + resolver_ui.indicate_progress + end + end + + # Calls the {#resolver_ui}'s {UI#debug} method + # @param [Integer] depth the depth of the {#states} stack + # @param [Proc] block a block that yields a {#to_s} + # @return [void] + def debug(depth = 0, &block) + resolver_ui.debug(depth, &block) + end + + # Attempts to activate the current {#possibility} + # @return [void] + def attempt_to_activate + debug(depth) { 'Attempting to activate ' + possibility.to_s } + existing_node = activated.vertex_named(name) + if existing_node.payload + debug(depth) { "Found existing spec (#{existing_node.payload})" } + attempt_to_activate_existing_spec(existing_node) + else + attempt_to_activate_new_spec + end + end + + # Attempts to activate the current {#possibility} (given that it has + # already been activated) + # @return [void] + def attempt_to_activate_existing_spec(existing_node) + existing_spec = existing_node.payload + if requirement_satisfied_by?(requirement, activated, existing_spec) + new_requirements = requirements.dup + push_state_for_requirements(new_requirements, false) + else + return if attempt_to_swap_possibility + create_conflict + debug(depth) { "Unsatisfied by existing spec (#{existing_node.payload})" } + unwind_for_conflict + end + end + + # Attempts to swp the current {#possibility} with the already-activated + # spec with the given name + # @return [Boolean] Whether the possibility was swapped into {#activated} + def attempt_to_swap_possibility + activated.tag(:swap) + vertex = activated.vertex_named(name) + activated.set_payload(name, possibility) + if !vertex.requirements. + all? { |r| requirement_satisfied_by?(r, activated, possibility) } || + !new_spec_satisfied? + activated.rewind_to(:swap) + return + end + fixup_swapped_children(vertex) + activate_spec + end + + # Ensures there are no orphaned successors to the given {vertex}. + # @param [DependencyGraph::Vertex] vertex the vertex to fix up. + # @return [void] + def fixup_swapped_children(vertex) # rubocop:disable Metrics/CyclomaticComplexity + payload = vertex.payload + deps = dependencies_for(payload).group_by(&method(:name_for)) + vertex.outgoing_edges.each do |outgoing_edge| + requirement = outgoing_edge.requirement + parent_index = @parents_of[requirement].last + succ = outgoing_edge.destination + matching_deps = Array(deps[succ.name]) + dep_matched = matching_deps.include?(requirement) + + # only push the current index when it was originally required by the + # same named spec + if parent_index && states[parent_index].name == name + @parents_of[requirement].push(states.size - 1) + end + + if matching_deps.empty? && !succ.root? && succ.predecessors.to_a == [vertex] + debug(depth) { "Removing orphaned spec #{succ.name} after swapping #{name}" } + succ.requirements.each { |r| @parents_of.delete(r) } + + removed_names = activated.detach_vertex_named(succ.name).map(&:name) + requirements.delete_if do |r| + # the only removed vertices are those with no other requirements, + # so it's safe to delete only based upon name here + removed_names.include?(name_for(r)) + end + elsif !dep_matched + debug(depth) { "Removing orphaned dependency #{requirement} after swapping #{name}" } + # also reset if we're removing the edge, but only if its parent has + # already been fixed up + @parents_of[requirement].push(states.size - 1) if @parents_of[requirement].empty? + + activated.delete_edge(outgoing_edge) + requirements.delete(requirement) + end + end + end + + # Attempts to activate the current {#possibility} (given that it hasn't + # already been activated) + # @return [void] + def attempt_to_activate_new_spec + if new_spec_satisfied? + activate_spec + else + create_conflict + unwind_for_conflict + end + end + + # @return [Boolean] whether the current spec is satisfied as a new + # possibility. + def new_spec_satisfied? + unless requirement_satisfied_by?(requirement, activated, possibility) + debug(depth) { 'Unsatisfied by requested spec' } + return false + end + + locked_requirement = locked_requirement_named(name) + + locked_spec_satisfied = !locked_requirement || + requirement_satisfied_by?(locked_requirement, activated, possibility) + debug(depth) { 'Unsatisfied by locked spec' } unless locked_spec_satisfied + + locked_spec_satisfied + end + + # @param [String] requirement_name the spec name to search for + # @return [Object] the locked spec named `requirement_name`, if one + # is found on {#base} + def locked_requirement_named(requirement_name) + vertex = base.vertex_named(requirement_name) + vertex && vertex.payload + end + + # Add the current {#possibility} to the dependency graph of the current + # {#state} + # @return [void] + def activate_spec + conflicts.delete(name) + debug(depth) { "Activated #{name} at #{possibility}" } + activated.set_payload(name, possibility) + require_nested_dependencies_for(possibility) + end + + # Requires the dependencies that the recently activated spec has + # @param [Object] activated_spec the specification that has just been + # activated + # @return [void] + def require_nested_dependencies_for(activated_spec) + nested_dependencies = dependencies_for(activated_spec) + debug(depth) { "Requiring nested dependencies (#{nested_dependencies.join(', ')})" } + nested_dependencies.each do |d| + activated.add_child_vertex(name_for(d), nil, [name_for(activated_spec)], 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 + # @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 = new_requirements.shift + new_name = new_requirement ? name_for(new_requirement) : ''.freeze + possibilities = new_requirement ? search_for(new_requirement) : [] + handle_missing_or_push_dependency_state DependencyState.new( + new_name, new_requirements, new_activated, + new_requirement, possibilities, depth, conflicts.dup + ) + end + + # Pushes a new {DependencyState}. + # If the {#specification_provider} says to + # {SpecificationProvider#allow_missing?} that particular requirement, and + # there are no possibilities for that requirement, then `state` is not + # pushed, and the node in {#activated} is removed, and we continue + # resolving the remaining requirements. + # @param [DependencyState] state + # @return [void] + def handle_missing_or_push_dependency_state(state) + if state.requirement && state.possibilities.empty? && allow_missing?(state.requirement) + state.activated.detach_vertex_named(state.name) + push_state_for_requirements(state.requirements.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 new file mode 100644 index 0000000000..50d853b146 --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/resolver.rb @@ -0,0 +1,45 @@ +# frozen_string_literal: true +require 'bundler/vendor/molinillo/lib/molinillo/dependency_graph' + +module Bundler::Molinillo + # This class encapsulates a dependency resolver. + # The resolver is responsible for determining which set of dependencies to + # activate, with feedback from the {#specification_provider} + # + # + class Resolver + require 'bundler/vendor/molinillo/lib/molinillo/resolution' + + # @return [SpecificationProvider] the specification provider used + # in the resolution process + attr_reader :specification_provider + + # @return [UI] the UI module used to communicate back to the user + # during the resolution process + attr_reader :resolver_ui + + # 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 new file mode 100644 index 0000000000..3a8107cf1a --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/state.rb @@ -0,0 +1,54 @@ +# 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 [Set<Object>] conflicts unresolved conflicts + ResolutionState = Struct.new( + :name, + :requirements, + :activated, + :requirement, + :possibilities, + :depth, + :conflicts + ) + + class ResolutionState + # Returns an empty resolution state + # @return [ResolutionState] an empty state + def self.empty + new(nil, [], DependencyGraph.new, nil, nil, 0, Set.new) + end + end + + # A state that encapsulates a set of {#requirements} with an {Array} of + # possibilities + class DependencyState < ResolutionState + # Removes a possibility from `self` + # @return [PossibilityState] a state with a single possibility, + # the possibility that was removed from `self` + def pop_possibility_state + PossibilityState.new( + name, + requirements.dup, + activated, + requirement, + [possibilities.pop], + depth + 1, + conflicts.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 |