diff options
Diffstat (limited to 'lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb')
| -rw-r--r-- | lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb | 202 |
1 files changed, 57 insertions, 145 deletions
diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb index 42563664d6..6189a717cd 100644 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb +++ b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb @@ -2,6 +2,9 @@ require 'set' require 'tsort' +require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/log' +require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/vertex' + module Gem::Resolver::Molinillo # A directed acyclic graph that is tuned to hold named dependencies class DependencyGraph @@ -10,15 +13,16 @@ module Gem::Resolver::Molinillo # 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_method :tsort_each_node, :each + # @!visibility private + alias tsort_each_node each - # @visibility private + # @!visibility private def tsort_each_child(vertex, &block) vertex.successors.each(&block) end @@ -44,9 +48,27 @@ module Gem::Resolver::Molinillo # 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} @@ -55,6 +77,7 @@ module Gem::Resolver::Molinillo 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| @@ -75,6 +98,22 @@ module Gem::Resolver::Molinillo "#{self.class}:#{vertices.values.inspect}" end + # @return [String] Returns a dot format representation of the graph + def to_dot + dot_vertices = [] + dot_edges = [] + vertices.each do |n, v| + dot_vertices << " #{n} [label=\"{#{n}|#{v.payload}}\"]" + v.outgoing_edges.each do |e| + dot_edges << " #{e.origin.name} -> #{e.destination.name} [label=\"#{e.requirement}\"]" + end + end + dot_vertices.sort! + 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} @@ -93,12 +132,9 @@ module Gem::Resolver::Molinillo # @param [Object] requirement the requirement that is requiring the child # @return [void] def add_child_vertex(name, payload, parent_names, requirement) - vertex = add_vertex(name, payload) + root = !parent_names.delete(nil) { true } + vertex = add_vertex(name, payload, root) parent_names.each do |parent_name| - unless parent_name - vertex.root = true - next - end parent_node = vertex_named(parent_name) add_edge(parent_node, vertex, requirement) end @@ -110,10 +146,7 @@ module Gem::Resolver::Molinillo # @param [Object] payload # @return [Vertex] the vertex that was added to `self` def add_vertex(name, payload, root = false) - vertex = vertices[name] ||= Vertex.new(name, payload) - vertex.payload ||= payload - vertex.root ||= root - vertex + log.add_vertex(self, name, payload, root) end # Detaches the {#vertex_named} `name` {Vertex} from the graph, recursively @@ -121,16 +154,7 @@ module Gem::Resolver::Molinillo # @param [String] name # @return [void] def detach_vertex_named(name) - return unless vertex = vertices.delete(name) - vertex.outgoing_edges.each do |e| - v = e.destination - v.incoming_edges.delete(e) - detach_vertex_named(v.name) unless v.root? || v.predecessors.any? - end - vertex.incoming_edges.each do |e| - v = e.origin - v.outgoing_edges.delete(e) - end + log.detach_vertex_named(self, name) end # @param [String] name @@ -158,134 +182,22 @@ module Gem::Resolver::Molinillo add_edge_no_circular(origin, destination, 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) - edge = Edge.new(origin, destination, requirement) - origin.outgoing_edges << edge - destination.incoming_edges << edge - edge - end - - # 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 [Arrary<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_method :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 - @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) - 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) - other && - name == other.name && - payload == other.payload - end - - alias_method :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_method :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_method :is_reachable_from?, :ancestor? + log.add_edge_no_circular(self, origin.name, destination.name, requirement) end end end |