diff options
author | hsbt <hsbt@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2018-11-02 23:07:56 +0000 |
---|---|---|
committer | hsbt <hsbt@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2018-11-02 23:07:56 +0000 |
commit | 59c8d50653480bef3f24517296e6ddf937fdf6bc (patch) | |
tree | df10aaf4f3307837fe3d1d129d66f6c0c7586bc5 /lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph | |
parent | 7deb37777a230837e865e0a11fb8d7c1dc6d03ce (diff) |
Added bundler as default gems. Revisit [Feature #12733]
* bin/*, lib/bundler/*, lib/bundler.rb, spec/bundler, man/*:
Merge from latest stable branch of bundler/bundler repository and
added workaround patches. I will backport them into upstream.
* common.mk, defs/gmake.mk: Added `test-bundler` task for test suite
of bundler.
* tool/sync_default_gems.rb: Added sync task for bundler.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@65509 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph')
9 files changed, 632 insertions, 0 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 new file mode 100644 index 0000000000..c04c7eec9c --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/action.rb @@ -0,0 +1,36 @@ +# 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..9849aea2fe --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb @@ -0,0 +1,66 @@ +# 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..0a1e08255b --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_vertex.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#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..1d9f4b327d --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/delete_edge.rb @@ -0,0 +1,63 @@ +# 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..385dcbdd06 --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.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#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..8582dd19c1 --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/log.rb @@ -0,0 +1,126 @@ +# 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..37286d104a --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/set_payload.rb @@ -0,0 +1,46 @@ +# 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..d6ad16e07a --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/tag.rb @@ -0,0 +1,36 @@ +# 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..7ecdc4b65a --- /dev/null +++ b/lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/vertex.rb @@ -0,0 +1,136 @@ +# 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 [Array<Vertex>] the vertices of {#graph} where `self` is a + # {#descendent?} + def recursive_predecessors + vertices = predecessors + vertices += Compatibility.flat_map(vertices, &:recursive_predecessors) + 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 += Compatibility.flat_map(vertices, &:recursive_successors) + 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) + _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 = Set.new) + 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 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 |