diff options
Diffstat (limited to 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph')
9 files changed, 0 insertions, 660 deletions
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 |