diff options
Diffstat (limited to 'lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph')
9 files changed, 660 insertions, 0 deletions
diff --git a/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/action.rb b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/action.rb new file mode 100644 index 0000000000..8707ec451d --- /dev/null +++ b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/action.rb @@ -0,0 +1,36 @@ +# frozen_string_literal: true + +module Gem::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/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb new file mode 100644 index 0000000000..aa9815c5ae --- /dev/null +++ b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb @@ -0,0 +1,66 @@ +# frozen_string_literal: true + +require_relative 'action' +module Gem::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/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/add_vertex.rb b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/add_vertex.rb new file mode 100644 index 0000000000..9c7066a669 --- /dev/null +++ b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/add_vertex.rb @@ -0,0 +1,62 @@ +# frozen_string_literal: true + +require_relative 'action' +module Gem::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/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/delete_edge.rb b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/delete_edge.rb new file mode 100644 index 0000000000..1e62c0a0b6 --- /dev/null +++ b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/delete_edge.rb @@ -0,0 +1,63 @@ +# frozen_string_literal: true + +require_relative 'action' +module Gem::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/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb new file mode 100644 index 0000000000..6132f969b9 --- /dev/null +++ b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb @@ -0,0 +1,61 @@ +# frozen_string_literal: true + +require_relative 'action' +module Gem::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/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/log.rb b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/log.rb new file mode 100644 index 0000000000..6954c4b1f8 --- /dev/null +++ b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/log.rb @@ -0,0 +1,126 @@ +# 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 Gem::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/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/set_payload.rb b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/set_payload.rb new file mode 100644 index 0000000000..9bcaaae0f9 --- /dev/null +++ b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/set_payload.rb @@ -0,0 +1,46 @@ +# frozen_string_literal: true + +require_relative 'action' +module Gem::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/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/tag.rb b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/tag.rb new file mode 100644 index 0000000000..62f243a2af --- /dev/null +++ b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/tag.rb @@ -0,0 +1,36 @@ +# frozen_string_literal: true + +require_relative 'action' +module Gem::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/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/vertex.rb b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/vertex.rb new file mode 100644 index 0000000000..074de369be --- /dev/null +++ b/lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/vertex.rb @@ -0,0 +1,164 @@ +# frozen_string_literal: true + +module Gem::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 |