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 Class Methods

new(prioritizer) click to toggle source
Calls superclass method Puppet::Graph::SimpleGraph::new
   # File lib/puppet/graph/relationship_graph.rb
10 def initialize(prioritizer)
11   super()
12 
13   @prioritizer = prioritizer
14 
15   @ready = Puppet::Graph::RbTreeMap.new
16   @generated = {}
17   @done = {}
18   @blockers = {}
19   @providerless_types = []
20 end

Public Instance Methods

add_relationship(f, t, label=nil) click to toggle source
   # File lib/puppet/graph/relationship_graph.rb
44 def add_relationship(f, t, label=nil)
45   super(f, t, label)
46   @ready.delete(@prioritizer.priority_of(t))
47 end
add_vertex(vertex, priority = nil) click to toggle source
Calls superclass method Puppet::Graph::SimpleGraph#add_vertex
   # File lib/puppet/graph/relationship_graph.rb
34 def add_vertex(vertex, priority = nil)
35   super(vertex)
36 
37   if priority
38     @prioritizer.record_priority_for(vertex, priority)
39   else
40     @prioritizer.generate_priority_for(vertex)
41   end
42 end
clear_blockers() click to toggle source
   # File lib/puppet/graph/relationship_graph.rb
78 def clear_blockers
79   @blockers.clear
80 end
enqueue(*resources) click to toggle source
   # File lib/puppet/graph/relationship_graph.rb
82 def enqueue(*resources)
83   resources.each do |resource|
84     @ready[@prioritizer.priority_of(resource)] = resource
85   end
86 end
enqueue_roots() click to toggle source

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

   # File lib/puppet/graph/relationship_graph.rb
59 def enqueue_roots
60   vertices.each do |v|
61     @blockers[v] = direct_dependencies_of(v).length
62     enqueue(v) if @blockers[v] == 0
63   end
64 end
finish(resource) click to toggle source
   # File lib/puppet/graph/relationship_graph.rb
88 def finish(resource)
89   direct_dependents_of(resource).each do |v|
90     enqueue(v) if unblock(v)
91   end
92   @done[resource] = true
93 end
next_resource() click to toggle source
   # File lib/puppet/graph/relationship_graph.rb
95 def next_resource
96   @ready.delete_min
97 end
populate_from(catalog) click to toggle source
   # File lib/puppet/graph/relationship_graph.rb
22 def populate_from(catalog)
23   add_all_resources_as_vertices(catalog)
24   build_manual_dependencies
25   build_autorelation_dependencies(catalog)
26 
27   write_graph(:relationships) if catalog.host_config?
28 
29   replace_containers_with_anchors(catalog)
30 
31   write_graph(:expanded_relationships) if catalog.host_config?
32 end
remove_vertex!(vertex) click to toggle source
   # File lib/puppet/graph/relationship_graph.rb
49 def remove_vertex!(vertex)
50   super
51   @prioritizer.forget(vertex)
52 end
resource_priority(resource) click to toggle source
   # File lib/puppet/graph/relationship_graph.rb
54 def resource_priority(resource)
55   @prioritizer.priority_of(resource)
56 end
traverse(options = {}) { |resource| ... } click to toggle source
    # File lib/puppet/graph/relationship_graph.rb
 99 def traverse(options = {}, &block)
100   continue_while = options[:while] || lambda { true }
101   pre_process = options[:pre_process] || lambda { |resource| }
102   overly_deferred_resource_handler = options[:overly_deferred_resource_handler] || lambda { |resource| }
103   canceled_resource_handler = options[:canceled_resource_handler] || lambda { |resource| }
104   teardown = options[:teardown] || lambda {}
105   graph_cycle_handler = options[:graph_cycle_handler] || lambda { [] }
106 
107   cycles = report_cycles_in_graph
108   if cycles
109     graph_cycle_handler.call(cycles)
110   end
111 
112   enqueue_roots
113 
114   deferred_resources = []
115 
116   while continue_while.call() && (resource = next_resource)
117     if resource.suitable?
118       made_progress = true
119 
120       pre_process.call(resource)
121 
122       yield resource
123 
124       finish(resource)
125     else
126       deferred_resources << resource
127     end
128 
129     if @ready.empty? and deferred_resources.any?
130       if made_progress
131         enqueue(*deferred_resources)
132       else
133         deferred_resources.each do |res|
134           overly_deferred_resource_handler.call(res)
135           finish(res)
136         end
137       end
138 
139       made_progress = false
140       deferred_resources = []
141     end
142   end
143 
144   if !continue_while.call()
145     while (resource = next_resource)
146       canceled_resource_handler.call(resource)
147       finish(resource)
148     end
149   end
150 
151   teardown.call()
152 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
68 def unblock(resource)
69   @blockers[resource] ||= direct_dependencies_of(resource).select { |r2| !@done[r2] }.length
70   if @blockers[resource] > 0
71     @blockers[resource] -= 1
72   else
73     resource.warning _("appears to have a negative number of dependencies")
74   end
75   @blockers[resource] <= 0
76 end

Private Instance Methods

add_all_resources_as_vertices(catalog) click to toggle source
    # File lib/puppet/graph/relationship_graph.rb
156 def add_all_resources_as_vertices(catalog)
157   catalog.resources.each do |vertex|
158     add_vertex(vertex)
159   end
160 end
build_autorelation_dependencies(catalog) click to toggle source
    # File lib/puppet/graph/relationship_graph.rb
170 def build_autorelation_dependencies(catalog)
171   vertices.each do |vertex|
172     [:require,:subscribe].each do |rel_type|
173       vertex.send("auto#{rel_type}".to_sym, catalog).each do |edge|
174         # don't let automatic relationships conflict with manual ones.
175         next if edge?(edge.source, edge.target)
176 
177         if edge?(edge.target, edge.source)
178           vertex.debug "Skipping automatic relationship with #{edge.source}"
179         else
180           vertex.debug "Adding auto#{rel_type} relationship with #{edge.source}"
181           if rel_type == :require
182             edge.event = :NONE
183           else
184             edge.callback = :refresh
185             edge.event = :ALL_EVENTS
186           end
187           add_edge(edge)
188         end
189       end
190     end
191 
192     [:before,:notify].each do |rel_type|
193       vertex.send("auto#{rel_type}".to_sym, catalog).each do |edge|
194         # don't let automatic relationships conflict with manual ones.
195         next if edge?(edge.target, edge.source)
196 
197         if edge?(edge.source, edge.target)
198           vertex.debug "Skipping automatic relationship with #{edge.target}"
199         else
200           vertex.debug "Adding auto#{rel_type} relationship with #{edge.target}"
201           if rel_type == :before
202             edge.event = :NONE
203           else
204             edge.callback = :refresh
205             edge.event = :ALL_EVENTS
206           end
207           add_edge(edge)
208         end
209       end
210     end
211   end
212 end
build_manual_dependencies() click to toggle source
    # File lib/puppet/graph/relationship_graph.rb
162 def build_manual_dependencies
163   vertices.each do |vertex|
164     vertex.builddepends.each do |edge|
165       add_edge(edge)
166     end
167   end
168 end
replace_containers_with_anchors(catalog) click to toggle source
    # File lib/puppet/graph/relationship_graph.rb
234 def replace_containers_with_anchors(catalog)
235   stage_class      = Puppet::Type.type(:stage)
236   whit_class       = Puppet::Type.type(:whit)
237   component_class  = Puppet::Type.type(:component)
238   containers = catalog.resources.find_all { |v| (v.is_a?(component_class) or v.is_a?(stage_class)) and vertex?(v) }
239   #
240   # These two hashes comprise the aforementioned attention to the possible
241   #   case of containers that contain / depend on other containers; they map
242   #   containers to their sentinels but pass other vertices through.  Thus we
243   #   can "do the right thing" for references to other vertices that may or
244   #   may not be containers.
245   #
246   admissible = Hash.new { |h,k| k }
247   completed  = Hash.new { |h,k| k }
248   containers.each { |x|
249     admissible[x] = whit_class.new(:name => "admissible_#{x.ref}", :catalog => catalog)
250     completed[x]  = whit_class.new(:name => "completed_#{x.ref}",  :catalog => catalog)
251 
252     # This copies the original container's tags over to the two anchor whits.
253     # Without this, tags are not propagated to the container's resources.
254     admissible[x].set_tags(x)
255     completed[x].set_tags(x)
256 
257     priority = @prioritizer.priority_of(x)
258     add_vertex(admissible[x], priority)
259     add_vertex(completed[x], priority)
260   }
261   #
262   # Implement the six requirements listed above
263   #
264   containers.each { |x|
265     contents = catalog.adjacent(x, :direction => :out)
266     add_edge(admissible[x],completed[x]) if contents.empty? # (0)
267     contents.each { |v|
268       add_edge(admissible[x],admissible[v],Default_label) # (1)
269       add_edge(completed[v], completed[x], Default_label) # (2)
270     }
271     # (3) & (5)
272     adjacent(x,:direction => :in,:type => :edges).each { |e|
273       add_edge(completed[e.source],admissible[x],e.label)
274       remove_edge! e
275     }
276     # (4) & (5)
277     adjacent(x,:direction => :out,:type => :edges).each { |e|
278       add_edge(completed[x],admissible[e.target],e.label)
279       remove_edge! e
280     }
281   }
282   containers.each { |x| remove_vertex! x } # (5)
283 end