Class: Upkeep::DAG::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/upkeep/dag.rb

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



14
15
16
17
18
19
 
# File 'lib/upkeep/dag.rb', line 14

def initialize
  @nodes = {}
  @edges = []
  @version = 0
  reset_indexes!
end

Instance Attribute Details

#edges ⇒ Object (readonly)

Returns the value of attribute edges.



12
13
14
 
# File 'lib/upkeep/dag.rb', line 12

def edges
  @edges
end

#nodes ⇒ Object (readonly)

Returns the value of attribute nodes.



12
13
14
 
# File 'lib/upkeep/dag.rb', line 12

def nodes
  @nodes
end

#version ⇒ Object (readonly)

Returns the value of attribute version.



12
13
14
 
# File 'lib/upkeep/dag.rb', line 12

def version
  @version
end

Class Method Details

.deserialize_frame_payload(payload) ⇒ Object 



409
410
411
412
413
 
# File 'lib/upkeep/dag.rb', line 409

def deserialize_frame_payload(payload)
  payload.each_with_object({}) do |(key, value), frame_payload|
    frame_payload[key] = key == :recipe && value ? Replay::Recipe.from_h(value) : value
  end
end

.deserialize_payload(kind, payload) ⇒ Object 



396
397
398
399
400
401
402
403
404
405
406
407
 
# File 'lib/upkeep/dag.rb', line 396

def deserialize_payload(kind, payload)
  payload = symbolize_keys(payload)

  case kind
  when :dependency
    Dependencies.from_h(payload)
  when :frame
    deserialize_frame_payload(payload)
  else
    payload
  end
end

.from_h(snapshot) ⇒ Object 



275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
 
# File 'lib/upkeep/dag.rb', line 275

def self.from_h(snapshot)
  snapshot = symbolize_keys(snapshot)
  graph = new
  graph.nodes.clear
  graph.edges.clear
  graph.send(:reset_indexes!)

  snapshot.fetch(:nodes).each do |node_snapshot|
    node_snapshot = symbolize_keys(node_snapshot)
    kind = node_snapshot.fetch(:kind).to_sym
    graph.nodes[node_snapshot.fetch(:id)] = Node.new(
      node_snapshot.fetch(:id),
      kind,
      deserialize_payload(kind, node_snapshot.fetch(:payload))
    )
  end

  snapshot.fetch(:edges).each do |edge_snapshot|
    edge_snapshot = symbolize_keys(edge_snapshot)
    graph.add_edge(
      edge_snapshot.fetch(:from),
      edge_snapshot.fetch(:to),
      reason: edge_snapshot.fetch(:reason).to_sym
    )
  end

  graph.send(:rebuild_dependency_index)
  graph
end

.symbolize_keys(value) ⇒ Object 



415
416
417
418
419
420
421
422
423
424
425
426
427
 
# File 'lib/upkeep/dag.rb', line 415

def symbolize_keys(value)
  case value
  when Hash
    value.each_with_object({}) do |(key, nested_value), result|
      normalized_key = key.respond_to?(:to_sym) ? key.to_sym : key
      result[normalized_key] = symbolize_keys(nested_value)
    end
  when Array
    value.map { |nested_value| symbolize_keys(nested_value) }
  else
    value
  end
end

Instance Method Details

#add_dependency(owner_id, dependency) ⇒ Object 



42
43
44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/upkeep/dag.rb', line 42

def add_dependency(owner_id, dependency)
  dependency_cache_key = dependency.cache_key
  dependency_cache_keys = @dependency_cache_keys_by_node[owner_id]
  return false if dependency_cache_keys.key?(dependency_cache_key)

  add_node(owner_id, kind: :unknown) unless nodes.key?(owner_id)
  add_node(dependency_cache_key, kind: :dependency, payload: dependency)
  add_edge(owner_id, dependency_cache_key, reason: :depends_on)

  dependency_cache_keys[dependency_cache_key] = true
  @dependencies_by_node[owner_id] << dependency
  true
end

#add_edge(from, to, reason:) ⇒ Object 



28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/upkeep/dag.rb', line 28

def add_edge(from, to, reason:)
  key = edge_key(from, to, reason)
  return false if @edge_keys[key]

  @edge_keys[key] = true
  @version += 1
  edge = Edge.new(from, to, reason)
  edges << edge
  @outgoing_edges_by_from[from] << edge
  @incoming_edges_by_to[to] << edge
  @dependency_owner_ids_by_node[to] << from if reason == :depends_on
  true
end

#add_node(id, kind:, payload: {}) ⇒ Object 



21
22
23
24
25
26
 
# File 'lib/upkeep/dag.rb', line 21

def add_node(id, kind:, payload: {})
  return nodes.fetch(id) if nodes.key?(id)

  @version += 1
  nodes[id] = Node.new(id, kind, payload)
end

#ancestor_node_ids(node_id) ⇒ Object 



116
117
118
119
120
121
122
123
124
125
126
 
# File 'lib/upkeep/dag.rb', line 116

def ancestor_node_ids(node_id)
  ancestors = []
  current = node_id

  while (edge = incoming_edges(current, reason: :contains).first)
    ancestors << edge.from
    current = edge.from
  end

  ancestors
end

#attach_subgraph(scope_id, replacement_graph, parent_id:, replacement_scope_id: scope_id) ⇒ Object

Raises:

  • (KeyError) 


190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
 
# File 'lib/upkeep/dag.rb', line 190

def attach_subgraph(scope_id, replacement_graph, parent_id:, replacement_scope_id: scope_id)
  raise KeyError, scope_id if node?(scope_id)
  raise KeyError, replacement_scope_id unless replacement_graph.node?(replacement_scope_id)
  raise KeyError, parent_id unless node?(parent_id)

  replacement_ids = replacement_graph.contained_node_ids(replacement_scope_id).to_h { |id| [id, true] }
  composed = self.class.new

  nodes.each_value do |node|
    next if node.kind == :dependency

    composed.add_node(node.id, kind: node.kind, payload: node.payload)
  end
  edges.each do |edge|
    next unless edge.reason == :contains

    composed.add_edge(edge.from, edge.to, reason: :contains)
  end
  composed.nodes.keys.each do |owner_id|
    dependencies_for(owner_id).each { |dependency| composed.add_dependency(owner_id, dependency) }
  end

  replacement_graph.nodes.each_value do |node|
    next if node.kind == :dependency || !replacement_ids[node.id]

    composed.add_node(node.id, kind: node.kind, payload: node.payload)
  end
  replacement_graph.edges.each do |edge|
    next unless edge.reason == :contains
    next unless replacement_ids[edge.from] && replacement_ids[edge.to]

    composed.add_edge(edge.from, edge.to, reason: :contains)
  end
  composed.add_edge(parent_id, replacement_scope_id, reason: :contains)
  replacement_ids.each_key do |owner_id|
    replacement_graph.dependencies_for(owner_id).each do |dependency|
      composed.add_dependency(owner_id, dependency)
    end
  end

  composed
end

#contained_by?(descendant_id, ancestor_id) ⇒ Boolean

Returns:

  • (Boolean) 


128
129
130
 
# File 'lib/upkeep/dag.rb', line 128

def contained_by?(descendant_id, ancestor_id)
  ancestor_node_ids(descendant_id).include?(ancestor_id)
end

#contained_node_ids(node_id) ⇒ Object 



132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
 
# File 'lib/upkeep/dag.rb', line 132

def contained_node_ids(node_id)
  ids = []
  queue = [node_id]
  visited = {}

  until queue.empty?
    id = queue.shift
    next if visited[id]

    visited[id] = true
    ids << id
    queue.concat(outgoing_edges(id, reason: :contains).map(&:to))
  end

  ids
end

#dependencies_for(node_id) ⇒ Object 



56
57
58
 
# File 'lib/upkeep/dag.rb', line 56

def dependencies_for(node_id)
  @dependencies_by_node[node_id]
end

#dependency_node_ids_matching(changes) ⇒ Object 



86
87
88
89
90
 
# File 'lib/upkeep/dag.rb', line 86

def dependency_node_ids_matching(changes)
  dependency_nodes.filter_map do |node|
    node.id if changes.any? { |change| node.payload.matches_change?(change) }
  end
end

#dependency_nodes ⇒ Object 



237
238
239
 
# File 'lib/upkeep/dag.rb', line 237

def dependency_nodes
  nodes.values.select { |node| node.kind == :dependency }
end

#dependency_owner_ids(dependency_node_id) ⇒ Object 



82
83
84
 
# File 'lib/upkeep/dag.rb', line 82

def dependency_owner_ids(dependency_node_id)
  @dependency_owner_ids_by_node.fetch(dependency_node_id, []).dup
end

#dependency_reports ⇒ Object 



343
344
345
346
347
348
349
350
351
 
# File 'lib/upkeep/dag.rb', line 343

def dependency_reports
  dependency_nodes.map do |node|
    {
      id: node.id,
      dependency: node.payload.to_h,
      owners: dependency_owner_ids(node.id)
    }
  end
end

#frame_nodes ⇒ Object 



233
234
235
 
# File 'lib/upkeep/dag.rb', line 233

def frame_nodes
  nodes.values.select { |node| node.kind == :frame }
end

#frame_reports ⇒ Object 



305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
 
# File 'lib/upkeep/dag.rb', line 305

def frame_reports
  frame_nodes.map do |node|
    {
      id: node.id,
      kind: node.payload.fetch(:kind),
      template: node.payload[:template],
      site_id: node.payload[:site_id],
      manifest_path: node.payload[:manifest_path],
      manifest_fingerprint: node.payload[:manifest_fingerprint],
      locals: node.payload[:locals],
      contains: outgoing_edges(node.id, reason: :contains).map(&:to),
      dependencies: dependencies_for(node.id).map(&:to_h),
      replay_recipe: recipe_report(node.payload[:recipe])
    }.compact
  end
end

#incoming_edges(to, reason: nil) ⇒ Object 



75
76
77
78
79
80
 
# File 'lib/upkeep/dag.rb', line 75

def incoming_edges(to, reason: nil)
  indexed_edges = @incoming_edges_by_to.fetch(to, [])
  return indexed_edges.dup unless reason

  indexed_edges.select { |edge| edge.reason == reason }
end

#nearest_frame_nodes_from(node_id) ⇒ Object 



92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
# File 'lib/upkeep/dag.rb', line 92

def nearest_frame_nodes_from(node_id)
  current = node(node_id)
  return [current] if current.kind == :frame

  queue = outgoing_edges(node_id, reason: :contains).map(&:to)
  visited = {}
  frames = []

  until queue.empty?
    id = queue.shift
    next if visited[id]

    visited[id] = true
    current = node(id)
    if current.kind == :frame
      frames << current
    else
      queue.concat(outgoing_edges(id, reason: :contains).map(&:to))
    end
  end

  frames
end

#node(id) ⇒ Object 



60
61
62
 
# File 'lib/upkeep/dag.rb', line 60

def node(id)
  nodes.fetch(id)
end

#node?(id) ⇒ Boolean

Returns:

  • (Boolean) 


64
65
66
 
# File 'lib/upkeep/dag.rb', line 64

def node?(id)
  nodes.key?(id)
end

#outgoing_edges(from, reason: nil) ⇒ Object 



68
69
70
71
72
73
 
# File 'lib/upkeep/dag.rb', line 68

def outgoing_edges(from, reason: nil)
  indexed_edges = @outgoing_edges_by_from.fetch(from, [])
  return indexed_edges.dup unless reason

  indexed_edges.select { |edge| edge.reason == reason }
end

#recipe_report(recipe) ⇒ Object 



322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
 
# File 'lib/upkeep/dag.rb', line 322

def recipe_report(recipe)
  return unless recipe

  snapshot = recipe.to_h
  replay = snapshot[:replay] || snapshot["replay"] || {}
  replay_json = JSON.generate(replay)
  {
    kind: recipe.kind.to_s,
    target_kind: recipe.target_kind,
    target_id: recipe.target_id,
    runtime: recipe.runtime,
    template: recipe.template,
    replay: {
      type: recipe.replay.respond_to?(:type) ? recipe.replay.type : nil,
      keys: replay.keys.map(&:to_s).sort,
      bytes: replay_json.bytesize,
      digest: Digest::SHA256.hexdigest(replay_json)
    }.compact
  }.compact
end

#replace_subgraph(scope_id, replacement_graph, replacement_scope_id: scope_id) ⇒ Object

Raises:

  • (KeyError) 


149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
 
# File 'lib/upkeep/dag.rb', line 149

def replace_subgraph(scope_id, replacement_graph, replacement_scope_id: scope_id)
  raise KeyError, scope_id unless node?(scope_id)
  raise KeyError, replacement_scope_id unless replacement_graph.node?(replacement_scope_id)

  removed_ids = contained_node_ids(scope_id).to_h { |id| [id, true] }
  replacement_ids = replacement_graph.contained_node_ids(replacement_scope_id).to_h { |id| [id, true] }
  composed = self.class.new

  nodes.each_value do |node|
    next if node.kind == :dependency || removed_ids[node.id]

    composed.add_node(node.id, kind: node.kind, payload: node.payload)
  end
  replacement_graph.nodes.each_value do |node|
    next if node.kind == :dependency || !replacement_ids[node.id]

    composed.add_node(node.id, kind: node.kind, payload: node.payload)
  end

  edges.each do |edge|
    next unless edge.reason == :contains
    next unless composed.node?(edge.from) && composed.node?(edge.to)
    next if removed_ids[edge.from] || edge.to != scope_id && removed_ids[edge.to]

    composed.add_edge(edge.from, edge.to, reason: :contains)
  end
  replacement_graph.edges.each do |edge|
    next unless edge.reason == :contains
    next unless replacement_ids[edge.from] && replacement_ids[edge.to]

    composed.add_edge(edge.from, edge.to, reason: :contains)
  end

  composed.nodes.keys.each do |owner_id|
    source = replacement_ids[owner_id] ? replacement_graph : self
    source.dependencies_for(owner_id).each { |dependency| composed.add_dependency(owner_id, dependency) }
  end

  composed
end

#report ⇒ Object 



256
257
258
259
260
261
262
263
 
# File 'lib/upkeep/dag.rb', line 256

def report
  {
    summary: summary,
    frames: frame_reports,
    dependencies: dependency_reports,
    edges: edges.map(&:to_h)
  }
end

#summary ⇒ Object 



241
242
243
244
245
246
247
248
249
250
251
252
253
254
 
# File 'lib/upkeep/dag.rb', line 241

def summary
  {
    nodes: nodes.size,
    edges: edges.size,
    frames: frame_nodes.size,
    manifest_attached_frames: frame_nodes.count { |node| node.payload[:manifest_path] },
    dependencies: dependency_nodes.size,
    containment_edges: edges.count { |edge| edge.reason == :contains },
    dependency_edges: edges.count { |edge| edge.reason == :depends_on },
    replay_recipes: frame_nodes.count { |node| node.payload[:recipe] },
    replay_recipe_kinds: frame_nodes.filter_map { |node| node.payload[:recipe]&.kind }.map(&:to_s).uniq.sort,
    dependency_sources: dependency_nodes.map { |node| node.payload.source.to_s }.uniq.sort
  }
end

#to_h(dependencies: :all) ⇒ Object 



265
266
267
268
269
270
271
272
273
 
# File 'lib/upkeep/dag.rb', line 265

def to_h(dependencies: :all)
  serialized_nodes = serializable_nodes(dependencies: dependencies)
  node_ids = serialized_nodes.to_h { |node| [node.id, true] }

  {
    nodes: serialized_nodes.map { |node| serialize_node(node) },
    edges: edges.select { |edge| node_ids[edge.from] && node_ids[edge.to] }.map(&:to_h)
  }
end