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
11 def initialize(prioritizer)
12   super()
13 
14   @prioritizer = prioritizer
15 
16   @ready = Puppet::Graph::RbTreeMap.new
17   @generated = {}
18   @done = {}
19   @blockers = {}
20   @providerless_types = []
21 end

Public Instance Methods

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

Calls superclass method Puppet::Graph::SimpleGraph#add_relationship

   # File lib/puppet/graph/relationship_graph.rb
45 def add_relationship(f, t, label=nil)
46   super(f, t, label)
47   @ready.delete(@prioritizer.priority_of(t))
48 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
35 def add_vertex(vertex, priority = nil)
36   super(vertex)
37 
38   if priority
39     @prioritizer.record_priority_for(vertex, priority)
40   else
41     @prioritizer.generate_priority_for(vertex)
42   end
43 end

clear_blockers() click to toggle source

   # File lib/puppet/graph/relationship_graph.rb
79 def clear_blockers
80   @blockers.clear
81 end

enqueue(*resources) click to toggle source

   # File lib/puppet/graph/relationship_graph.rb
83 def enqueue(*resources)
84   resources.each do |resource|
85     @ready[@prioritizer.priority_of(resource)] = resource
86   end
87 end

enqueue_roots() click to toggle source

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

   # File lib/puppet/graph/relationship_graph.rb
60 def enqueue_roots
61   vertices.each do |v|
62     @blockers[v] = direct_dependencies_of(v).length
63     enqueue(v) if @blockers[v] == 0
64   end
65 end

finish(resource) click to toggle source

   # File lib/puppet/graph/relationship_graph.rb
89 def finish(resource)
90   direct_dependents_of(resource).each do |v|
91     enqueue(v) if unblock(v)
92   end
93   @done[resource] = true
94 end

next_resource() click to toggle source

   # File lib/puppet/graph/relationship_graph.rb
96 def next_resource
97   @ready.delete_min
98 end

populate_from(catalog) click to toggle source

   # File lib/puppet/graph/relationship_graph.rb
23 def populate_from(catalog)
24   add_all_resources_as_vertices(catalog)
25   build_manual_dependencies
26   build_autorelation_dependencies(catalog)
27 
28   write_graph(:relationships) if catalog.host_config?
29 
30   replace_containers_with_anchors(catalog)
31 
32   write_graph(:expanded_relationships) if catalog.host_config?
33 end

remove_vertex!(vertex) click to toggle source

Calls superclass method Puppet::Graph::SimpleGraph#remove_vertex!

   # File lib/puppet/graph/relationship_graph.rb
50 def remove_vertex!(vertex)
51   super
52   @prioritizer.forget(vertex)
53 end

resource_priority(resource) click to toggle source

   # File lib/puppet/graph/relationship_graph.rb
55 def resource_priority(resource)
56   @prioritizer.priority_of(resource)
57 end

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

    # File lib/puppet/graph/relationship_graph.rb
100 def traverse(options = {}, &block)
101   continue_while = options[:while] || lambda { true }
102   pre_process = options[:pre_process] || lambda { |resource| }
103   overly_deferred_resource_handler = options[:overly_deferred_resource_handler] || lambda { |resource| }
104   canceled_resource_handler = options[:canceled_resource_handler] || lambda { |resource| }
105   teardown = options[:teardown] || lambda {}
106   graph_cycle_handler = options[:graph_cycle_handler] || lambda { [] }
107 
108   cycles = report_cycles_in_graph
109   if cycles
110     graph_cycle_handler.call(cycles)
111   end
112 
113   enqueue_roots
114 
115   deferred_resources = []
116 
117   while continue_while.call() && (resource = next_resource)
118     if resource.suitable?
119       made_progress = true
120 
121       pre_process.call(resource)
122 
123       yield resource
124 
125       finish(resource)
126     else
127       deferred_resources << resource
128     end
129 
130     if @ready.empty? and deferred_resources.any?
131       if made_progress
132         enqueue(*deferred_resources)
133       else
134         deferred_resources.each do |res|
135           overly_deferred_resource_handler.call(res)
136           finish(res)
137         end
138       end
139 
140       made_progress = false
141       deferred_resources = []
142     end
143   end
144 
145   if !continue_while.call()
146     while (resource = next_resource)
147       canceled_resource_handler.call(resource)
148       finish(resource)
149     end
150   end
151 
152   teardown.call()
153 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
69 def unblock(resource)
70   @blockers[resource] ||= direct_dependencies_of(resource).select { |r2| !@done[r2] }.length
71   if @blockers[resource] > 0
72     @blockers[resource] -= 1
73   else
74     resource.warning _("appears to have a negative number of dependencies")
75   end
76   @blockers[resource] <= 0
77 end

Private Instance Methods

add_all_resources_as_vertices(catalog) click to toggle source

    # File lib/puppet/graph/relationship_graph.rb
157 def add_all_resources_as_vertices(catalog)
158   catalog.resources.each do |vertex|
159     add_vertex(vertex)
160   end
161 end

build_autorelation_dependencies(catalog) click to toggle source

    # File lib/puppet/graph/relationship_graph.rb
171 def build_autorelation_dependencies(catalog)
172   vertices.each do |vertex|
173     [:require,:subscribe].each do |rel_type|
174       vertex.send("auto#{rel_type}".to_sym, catalog).each do |edge|
175         # don't let automatic relationships conflict with manual ones.
176         next if edge?(edge.source, edge.target)
177 
178         if edge?(edge.target, edge.source)
179           vertex.debug "Skipping automatic relationship with #{edge.source}"
180         else
181           vertex.debug "Adding auto#{rel_type} relationship with #{edge.source}"
182           if rel_type == :require
183             edge.event = :NONE
184           else
185             edge.callback = :refresh
186             edge.event = :ALL_EVENTS
187           end
188           add_edge(edge)
189         end
190       end
191     end
192 
193     [:before,:notify].each do |rel_type|
194       vertex.send("auto#{rel_type}".to_sym, catalog).each do |edge|
195         # don't let automatic relationships conflict with manual ones.
196         next if edge?(edge.target, edge.source)
197 
198         if edge?(edge.source, edge.target)
199           vertex.debug "Skipping automatic relationship with #{edge.target}"
200         else
201           vertex.debug "Adding auto#{rel_type} relationship with #{edge.target}"
202           if rel_type == :before
203             edge.event = :NONE
204           else
205             edge.callback = :refresh
206             edge.event = :ALL_EVENTS
207           end
208           add_edge(edge)
209         end
210       end
211     end
212   end
213 end

build_manual_dependencies() click to toggle source

    # File lib/puppet/graph/relationship_graph.rb
163 def build_manual_dependencies
164   vertices.each do |vertex|
165     vertex.builddepends.each do |edge|
166       add_edge(edge)
167     end
168   end
169 end

replace_containers_with_anchors(catalog) click to toggle source

    # File lib/puppet/graph/relationship_graph.rb
235 def replace_containers_with_anchors(catalog)
236   stage_class      = Puppet::Type.type(:stage)
237   whit_class       = Puppet::Type.type(:whit)
238   component_class  = Puppet::Type.type(:component)
239   containers = catalog.resources.find_all { |v| (v.is_a?(component_class) or v.is_a?(stage_class)) and vertex?(v) }
240   #
241   # These two hashes comprise the aforementioned attention to the possible
242   #   case of containers that contain / depend on other containers; they map
243   #   containers to their sentinels but pass other vertices through.  Thus we
244   #   can "do the right thing" for references to other vertices that may or
245   #   may not be containers.
246   #
247   admissible = Hash.new { |h,k| k }
248   completed  = Hash.new { |h,k| k }
249   containers.each { |x|
250     admissible[x] = whit_class.new(:name => "admissible_#{x.ref}", :catalog => catalog)
251     completed[x]  = whit_class.new(:name => "completed_#{x.ref}",  :catalog => catalog)
252 
253     # This copies the original container's tags over to the two anchor whits.
254     # Without this, tags are not propagated to the container's resources.
255     admissible[x].set_tags(x)
256     completed[x].set_tags(x)
257 
258     priority = @prioritizer.priority_of(x)
259     add_vertex(admissible[x], priority)
260     add_vertex(completed[x], priority)
261   }
262   #
263   # Implement the six requirements listed above
264   #
265   containers.each { |x|
266     contents = catalog.adjacent(x, :direction => :out)
267     add_edge(admissible[x],completed[x]) if contents.empty? # (0)
268     contents.each { |v|
269       add_edge(admissible[x],admissible[v],Default_label) # (1)
270       add_edge(completed[v], completed[x], Default_label) # (2)
271     }
272     # (3) & (5)
273     adjacent(x,:direction => :in,:type => :edges).each { |e|
274       add_edge(completed[e.source],admissible[x],e.label)
275       remove_edge! e
276     }
277     # (4) & (5)
278     adjacent(x,:direction => :out,:type => :edges).each { |e|
279       add_edge(completed[x],admissible[e.target],e.label)
280       remove_edge! e
281     }
282   }
283   containers.each { |x| remove_vertex! x } # (5)
284 end