1 files changed, 164 insertions, 0 deletions
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