class Puppet::Graph::RelationshipGraph

The relationship graph is the final form of a puppet catalog in which all dependency edges are explicitly in the graph. This form of the catalog is used to traverse the graph in the order in which resources are managed.

@api private

Constants

Default_label

Impose our container information on another graph by using it to replace any container vertices X with a pair of vertices { admissible_X and completed_X } such that

0) completed_X depends on admissible_X
1) contents of X each depend on admissible_X
2) completed_X depends on each on the contents of X
3) everything which depended on X depends on completed_X
4) admissible_X depends on everything X depended on
5) the containers and their edges must be removed

Note that this requires attention to the possible case of containers which contain or depend on other containers, but has the advantage that the number of new edges created scales linearly with the number of contained vertices regardless of how containers are related; alternatives such as replacing container-edges with content-edges scale as the product of the number of external dependencies, which is to say geometrically in the case of nested / chained containers.

Attributes

blockers[R]

Public Instance Methods

add_relationship(f, t, label=nil) click to toggle source

# File lib/puppet/graph/relationship_graph.rb, line 44
def add_relationship(f, t, label=nil)
  super(f, t, label)
  @ready.delete(@prioritizer.priority_of(t))
end

add_vertex(vertex, priority = nil) click to toggle source

# File lib/puppet/graph/relationship_graph.rb, line 34
def add_vertex(vertex, priority = nil)
  super(vertex)

  if priority
    @prioritizer.record_priority_for(vertex, priority)
  else
    @prioritizer.generate_priority_for(vertex)
  end
end

clear_blockers() click to toggle source

# File lib/puppet/graph/relationship_graph.rb, line 78
def clear_blockers
  @blockers.clear
end

enqueue(*resources) click to toggle source

# File lib/puppet/graph/relationship_graph.rb, line 82
def enqueue(*resources)
  resources.each do |resource|
    @ready[@prioritizer.priority_of(resource)] = resource
  end
end

enqueue_roots() click to toggle source

Enqueue the initial set of resources, those with no dependencies.

# File lib/puppet/graph/relationship_graph.rb, line 59
def enqueue_roots
  vertices.each do |v|
    @blockers[v] = direct_dependencies_of(v).length
    enqueue(v) if @blockers[v] == 0
  end
end

finish(resource) click to toggle source

# File lib/puppet/graph/relationship_graph.rb, line 88
def finish(resource)
  direct_dependents_of(resource).each do |v|
    enqueue(v) if unblock(v)
  end
  @done[resource] = true
end

next_resource() click to toggle source

# File lib/puppet/graph/relationship_graph.rb, line 95
def next_resource
  @ready.delete_min
end

populate_from(catalog) click to toggle source

# File lib/puppet/graph/relationship_graph.rb, line 22
def populate_from(catalog)
  add_all_resources_as_vertices(catalog)
  build_manual_dependencies
  build_autorequire_dependencies(catalog)

  write_graph(:relationships) if catalog.host_config?

  replace_containers_with_anchors(catalog)

  write_graph(:expanded_relationships) if catalog.host_config?
end

remove_vertex!(vertex) click to toggle source

# File lib/puppet/graph/relationship_graph.rb, line 49
def remove_vertex!(vertex)
  super
  @prioritizer.forget(vertex)
end

resource_priority(resource) click to toggle source

# File lib/puppet/graph/relationship_graph.rb, line 54
def resource_priority(resource)
  @prioritizer.priority_of(resource)
end

traverse(options = {}) { |resource| ... } click to toggle source

# File lib/puppet/graph/relationship_graph.rb, line 99
def traverse(options = {}, &block)
  continue_while = options[:while] || lambda { true }
  pre_process = options[:pre_process] || lambda { |resource| }
  overly_deferred_resource_handler = options[:overly_deferred_resource_handler] || lambda { |resource| }
  canceled_resource_handler = options[:canceled_resource_handler] || lambda { |resource| }
  teardown = options[:teardown] || lambda {}

  report_cycles_in_graph

  enqueue_roots

  deferred_resources = []

  while continue_while.call() && (resource = next_resource)
    if resource.suitable?
      made_progress = true

      pre_process.call(resource)

      yield resource

      finish(resource)
    else
      deferred_resources << resource
    end

    if @ready.empty? and deferred_resources.any?
      if made_progress
        enqueue(*deferred_resources)
      else
        deferred_resources.each do |resource|
          overly_deferred_resource_handler.call(resource)
          finish(resource)
        end
      end

      made_progress = false
      deferred_resources = []
    end
  end

  if !continue_while.call()
    while (resource = next_resource)
      canceled_resource_handler.call(resource)
      finish(resource)
    end
  end

  teardown.call()
end

unblock(resource) click to toggle source

Decrement the blocker count for the resource by 1. If the number of blockers is unknown, count them and THEN decrement by 1.

# File lib/puppet/graph/relationship_graph.rb, line 68
def unblock(resource)
  @blockers[resource] ||= direct_dependencies_of(resource).select { |r2| !@done[r2] }.length
  if @blockers[resource] > 0
    @blockers[resource] -= 1
  else
    resource.warning "appears to have a negative number of dependencies"
  end
  @blockers[resource] <= 0
end

Public Class Methods

new(prioritizer) click to toggle source

# File lib/puppet/graph/relationship_graph.rb, line 10
def initialize(prioritizer)
  super()

  @prioritizer = prioritizer

  @ready = Puppet::Graph::RbTreeMap.new
  @generated = {}
  @done = {}
  @blockers = {}
  @providerless_types = []
end