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 



325
326
327
328
329
 
# File 'lib/upkeep/dag.rb', line 325

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 



312
313
314
315
316
317
318
319
320
321
322
323
 
# File 'lib/upkeep/dag.rb', line 312

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 



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
 
# File 'lib/upkeep/dag.rb', line 191

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 



331
332
333
334
335
336
337
338
339
340
341
342
343
 
# File 'lib/upkeep/dag.rb', line 331

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

#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 



153
154
155
 
# File 'lib/upkeep/dag.rb', line 153

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 



259
260
261
262
263
264
265
266
267
 
# File 'lib/upkeep/dag.rb', line 259

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 



149
150
151
 
# File 'lib/upkeep/dag.rb', line 149

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

#frame_reports ⇒ Object 



221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
 
# File 'lib/upkeep/dag.rb', line 221

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 



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

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

#report ⇒ Object 



172
173
174
175
176
177
178
179
 
# File 'lib/upkeep/dag.rb', line 172

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

#summary ⇒ Object 



157
158
159
160
161
162
163
164
165
166
167
168
169
170
 
# File 'lib/upkeep/dag.rb', line 157

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 



181
182
183
184
185
186
187
188
189
 
# File 'lib/upkeep/dag.rb', line 181

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