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
Public Class Methods
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
Puppet::Graph::SimpleGraph#add_relationship
# 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
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
# File lib/puppet/graph/relationship_graph.rb 78 def clear_blockers 79 @blockers.clear 80 end
# 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 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
# 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
# File lib/puppet/graph/relationship_graph.rb 95 def next_resource 96 @ready.delete_min 97 end
# 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
Puppet::Graph::SimpleGraph#remove_vertex!
# File lib/puppet/graph/relationship_graph.rb 49 def remove_vertex!(vertex) 50 super 51 @prioritizer.forget(vertex) 52 end
# File lib/puppet/graph/relationship_graph.rb 54 def resource_priority(resource) 55 @prioritizer.priority_of(resource) 56 end
# 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
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
# 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
# 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
# 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
# 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