]>
Commit | Line | Data |
---|---|---|
bae9f6d2 JC |
1 | package dag |
2 | ||
3 | import ( | |
4 | "encoding/json" | |
5 | "fmt" | |
6 | "io" | |
7 | "log" | |
8 | "reflect" | |
9 | "sort" | |
10 | "strconv" | |
11 | "sync" | |
12 | ) | |
13 | ||
14 | const ( | |
15 | typeOperation = "Operation" | |
16 | typeTransform = "Transform" | |
17 | typeWalk = "Walk" | |
18 | typeDepthFirstWalk = "DepthFirstWalk" | |
19 | typeReverseDepthFirstWalk = "ReverseDepthFirstWalk" | |
20 | typeTransitiveReduction = "TransitiveReduction" | |
21 | typeEdgeInfo = "EdgeInfo" | |
22 | typeVertexInfo = "VertexInfo" | |
23 | typeVisitInfo = "VisitInfo" | |
24 | ) | |
25 | ||
26 | // the marshal* structs are for serialization of the graph data. | |
27 | type marshalGraph struct { | |
28 | // Type is always "Graph", for identification as a top level object in the | |
29 | // JSON stream. | |
30 | Type string | |
31 | ||
32 | // Each marshal structure requires a unique ID so that it can be referenced | |
33 | // by other structures. | |
34 | ID string `json:",omitempty"` | |
35 | ||
36 | // Human readable name for this graph. | |
37 | Name string `json:",omitempty"` | |
38 | ||
39 | // Arbitrary attributes that can be added to the output. | |
40 | Attrs map[string]string `json:",omitempty"` | |
41 | ||
42 | // List of graph vertices, sorted by ID. | |
43 | Vertices []*marshalVertex `json:",omitempty"` | |
44 | ||
45 | // List of edges, sorted by Source ID. | |
46 | Edges []*marshalEdge `json:",omitempty"` | |
47 | ||
48 | // Any number of subgraphs. A subgraph itself is considered a vertex, and | |
49 | // may be referenced by either end of an edge. | |
50 | Subgraphs []*marshalGraph `json:",omitempty"` | |
51 | ||
52 | // Any lists of vertices that are included in cycles. | |
53 | Cycles [][]*marshalVertex `json:",omitempty"` | |
54 | } | |
55 | ||
56 | // The add, remove, connect, removeEdge methods mirror the basic Graph | |
57 | // manipulations to reconstruct a marshalGraph from a debug log. | |
58 | func (g *marshalGraph) add(v *marshalVertex) { | |
59 | g.Vertices = append(g.Vertices, v) | |
60 | sort.Sort(vertices(g.Vertices)) | |
61 | } | |
62 | ||
63 | func (g *marshalGraph) remove(v *marshalVertex) { | |
64 | for i, existing := range g.Vertices { | |
65 | if v.ID == existing.ID { | |
66 | g.Vertices = append(g.Vertices[:i], g.Vertices[i+1:]...) | |
67 | return | |
68 | } | |
69 | } | |
70 | } | |
71 | ||
72 | func (g *marshalGraph) connect(e *marshalEdge) { | |
73 | g.Edges = append(g.Edges, e) | |
74 | sort.Sort(edges(g.Edges)) | |
75 | } | |
76 | ||
77 | func (g *marshalGraph) removeEdge(e *marshalEdge) { | |
78 | for i, existing := range g.Edges { | |
79 | if e.Source == existing.Source && e.Target == existing.Target { | |
80 | g.Edges = append(g.Edges[:i], g.Edges[i+1:]...) | |
81 | return | |
82 | } | |
83 | } | |
84 | } | |
85 | ||
86 | func (g *marshalGraph) vertexByID(id string) *marshalVertex { | |
87 | for _, v := range g.Vertices { | |
88 | if id == v.ID { | |
89 | return v | |
90 | } | |
91 | } | |
92 | return nil | |
93 | } | |
94 | ||
95 | type marshalVertex struct { | |
96 | // Unique ID, used to reference this vertex from other structures. | |
97 | ID string | |
98 | ||
99 | // Human readable name | |
100 | Name string `json:",omitempty"` | |
101 | ||
102 | Attrs map[string]string `json:",omitempty"` | |
103 | ||
104 | // This is to help transition from the old Dot interfaces. We record if the | |
105 | // node was a GraphNodeDotter here, so we can call it to get attributes. | |
106 | graphNodeDotter GraphNodeDotter | |
107 | } | |
108 | ||
109 | func newMarshalVertex(v Vertex) *marshalVertex { | |
110 | dn, ok := v.(GraphNodeDotter) | |
111 | if !ok { | |
112 | dn = nil | |
113 | } | |
114 | ||
115 | return &marshalVertex{ | |
116 | ID: marshalVertexID(v), | |
117 | Name: VertexName(v), | |
118 | Attrs: make(map[string]string), | |
119 | graphNodeDotter: dn, | |
120 | } | |
121 | } | |
122 | ||
123 | // vertices is a sort.Interface implementation for sorting vertices by ID | |
124 | type vertices []*marshalVertex | |
125 | ||
126 | func (v vertices) Less(i, j int) bool { return v[i].Name < v[j].Name } | |
127 | func (v vertices) Len() int { return len(v) } | |
128 | func (v vertices) Swap(i, j int) { v[i], v[j] = v[j], v[i] } | |
129 | ||
130 | type marshalEdge struct { | |
131 | // Human readable name | |
132 | Name string | |
133 | ||
134 | // Source and Target Vertices by ID | |
135 | Source string | |
136 | Target string | |
137 | ||
138 | Attrs map[string]string `json:",omitempty"` | |
139 | } | |
140 | ||
141 | func newMarshalEdge(e Edge) *marshalEdge { | |
142 | return &marshalEdge{ | |
143 | Name: fmt.Sprintf("%s|%s", VertexName(e.Source()), VertexName(e.Target())), | |
144 | Source: marshalVertexID(e.Source()), | |
145 | Target: marshalVertexID(e.Target()), | |
146 | Attrs: make(map[string]string), | |
147 | } | |
148 | } | |
149 | ||
150 | // edges is a sort.Interface implementation for sorting edges by Source ID | |
151 | type edges []*marshalEdge | |
152 | ||
153 | func (e edges) Less(i, j int) bool { return e[i].Name < e[j].Name } | |
154 | func (e edges) Len() int { return len(e) } | |
155 | func (e edges) Swap(i, j int) { e[i], e[j] = e[j], e[i] } | |
156 | ||
157 | // build a marshalGraph structure from a *Graph | |
158 | func newMarshalGraph(name string, g *Graph) *marshalGraph { | |
159 | mg := &marshalGraph{ | |
160 | Type: "Graph", | |
161 | Name: name, | |
162 | Attrs: make(map[string]string), | |
163 | } | |
164 | ||
165 | for _, v := range g.Vertices() { | |
166 | id := marshalVertexID(v) | |
167 | if sg, ok := marshalSubgrapher(v); ok { | |
168 | smg := newMarshalGraph(VertexName(v), sg) | |
169 | smg.ID = id | |
170 | mg.Subgraphs = append(mg.Subgraphs, smg) | |
171 | } | |
172 | ||
173 | mv := newMarshalVertex(v) | |
174 | mg.Vertices = append(mg.Vertices, mv) | |
175 | } | |
176 | ||
177 | sort.Sort(vertices(mg.Vertices)) | |
178 | ||
179 | for _, e := range g.Edges() { | |
180 | mg.Edges = append(mg.Edges, newMarshalEdge(e)) | |
181 | } | |
182 | ||
183 | sort.Sort(edges(mg.Edges)) | |
184 | ||
185 | for _, c := range (&AcyclicGraph{*g}).Cycles() { | |
186 | var cycle []*marshalVertex | |
187 | for _, v := range c { | |
188 | mv := newMarshalVertex(v) | |
189 | cycle = append(cycle, mv) | |
190 | } | |
191 | mg.Cycles = append(mg.Cycles, cycle) | |
192 | } | |
193 | ||
194 | return mg | |
195 | } | |
196 | ||
197 | // Attempt to return a unique ID for any vertex. | |
198 | func marshalVertexID(v Vertex) string { | |
199 | val := reflect.ValueOf(v) | |
200 | switch val.Kind() { | |
201 | case reflect.Chan, reflect.Func, reflect.Map, reflect.Ptr, reflect.Slice, reflect.UnsafePointer: | |
202 | return strconv.Itoa(int(val.Pointer())) | |
203 | case reflect.Interface: | |
204 | return strconv.Itoa(int(val.InterfaceData()[1])) | |
205 | } | |
206 | ||
207 | if v, ok := v.(Hashable); ok { | |
208 | h := v.Hashcode() | |
209 | if h, ok := h.(string); ok { | |
210 | return h | |
211 | } | |
212 | } | |
213 | ||
214 | // fallback to a name, which we hope is unique. | |
215 | return VertexName(v) | |
216 | ||
217 | // we could try harder by attempting to read the arbitrary value from the | |
218 | // interface, but we shouldn't get here from terraform right now. | |
219 | } | |
220 | ||
221 | // check for a Subgrapher, and return the underlying *Graph. | |
222 | func marshalSubgrapher(v Vertex) (*Graph, bool) { | |
223 | sg, ok := v.(Subgrapher) | |
224 | if !ok { | |
225 | return nil, false | |
226 | } | |
227 | ||
228 | switch g := sg.Subgraph().DirectedGraph().(type) { | |
229 | case *Graph: | |
230 | return g, true | |
231 | case *AcyclicGraph: | |
232 | return &g.Graph, true | |
233 | } | |
234 | ||
235 | return nil, false | |
236 | } | |
237 | ||
238 | // The DebugOperationEnd func type provides a way to call an End function via a | |
239 | // method call, allowing for the chaining of methods in a defer statement. | |
240 | type DebugOperationEnd func(string) | |
241 | ||
242 | // End calls function e with the info parameter, marking the end of this | |
243 | // operation in the logs. | |
244 | func (e DebugOperationEnd) End(info string) { e(info) } | |
245 | ||
246 | // encoder provides methods to write debug data to an io.Writer, and is a noop | |
247 | // when no writer is present | |
248 | type encoder struct { | |
249 | sync.Mutex | |
250 | w io.Writer | |
251 | } | |
252 | ||
253 | // Encode is analogous to json.Encoder.Encode | |
254 | func (e *encoder) Encode(i interface{}) { | |
255 | if e == nil || e.w == nil { | |
256 | return | |
257 | } | |
258 | e.Lock() | |
259 | defer e.Unlock() | |
260 | ||
261 | js, err := json.Marshal(i) | |
262 | if err != nil { | |
263 | log.Println("[ERROR] dag:", err) | |
264 | return | |
265 | } | |
266 | js = append(js, '\n') | |
267 | ||
268 | _, err = e.w.Write(js) | |
269 | if err != nil { | |
270 | log.Println("[ERROR] dag:", err) | |
271 | return | |
272 | } | |
273 | } | |
274 | ||
275 | func (e *encoder) Add(v Vertex) { | |
276 | e.Encode(marshalTransform{ | |
277 | Type: typeTransform, | |
278 | AddVertex: newMarshalVertex(v), | |
279 | }) | |
280 | } | |
281 | ||
282 | // Remove records the removal of Vertex v. | |
283 | func (e *encoder) Remove(v Vertex) { | |
284 | e.Encode(marshalTransform{ | |
285 | Type: typeTransform, | |
286 | RemoveVertex: newMarshalVertex(v), | |
287 | }) | |
288 | } | |
289 | ||
290 | func (e *encoder) Connect(edge Edge) { | |
291 | e.Encode(marshalTransform{ | |
292 | Type: typeTransform, | |
293 | AddEdge: newMarshalEdge(edge), | |
294 | }) | |
295 | } | |
296 | ||
297 | func (e *encoder) RemoveEdge(edge Edge) { | |
298 | e.Encode(marshalTransform{ | |
299 | Type: typeTransform, | |
300 | RemoveEdge: newMarshalEdge(edge), | |
301 | }) | |
302 | } | |
303 | ||
304 | // BeginOperation marks the start of set of graph transformations, and returns | |
305 | // an EndDebugOperation func to be called once the opration is complete. | |
306 | func (e *encoder) BeginOperation(op string, info string) DebugOperationEnd { | |
307 | if e == nil { | |
308 | return func(string) {} | |
309 | } | |
310 | ||
311 | e.Encode(marshalOperation{ | |
312 | Type: typeOperation, | |
313 | Begin: op, | |
314 | Info: info, | |
315 | }) | |
316 | ||
317 | return func(info string) { | |
318 | e.Encode(marshalOperation{ | |
319 | Type: typeOperation, | |
320 | End: op, | |
321 | Info: info, | |
322 | }) | |
323 | } | |
324 | } | |
325 | ||
326 | // structure for recording graph transformations | |
327 | type marshalTransform struct { | |
328 | // Type: "Transform" | |
329 | Type string | |
330 | AddEdge *marshalEdge `json:",omitempty"` | |
331 | RemoveEdge *marshalEdge `json:",omitempty"` | |
332 | AddVertex *marshalVertex `json:",omitempty"` | |
333 | RemoveVertex *marshalVertex `json:",omitempty"` | |
334 | } | |
335 | ||
336 | func (t marshalTransform) Transform(g *marshalGraph) { | |
337 | switch { | |
338 | case t.AddEdge != nil: | |
339 | g.connect(t.AddEdge) | |
340 | case t.RemoveEdge != nil: | |
341 | g.removeEdge(t.RemoveEdge) | |
342 | case t.AddVertex != nil: | |
343 | g.add(t.AddVertex) | |
344 | case t.RemoveVertex != nil: | |
345 | g.remove(t.RemoveVertex) | |
346 | } | |
347 | } | |
348 | ||
349 | // this structure allows us to decode any object in the json stream for | |
350 | // inspection, then re-decode it into a proper struct if needed. | |
351 | type streamDecode struct { | |
352 | Type string | |
353 | Map map[string]interface{} | |
354 | JSON []byte | |
355 | } | |
356 | ||
357 | func (s *streamDecode) UnmarshalJSON(d []byte) error { | |
358 | s.JSON = d | |
359 | err := json.Unmarshal(d, &s.Map) | |
360 | if err != nil { | |
361 | return err | |
362 | } | |
363 | ||
364 | if t, ok := s.Map["Type"]; ok { | |
365 | s.Type, _ = t.(string) | |
366 | } | |
367 | return nil | |
368 | } | |
369 | ||
370 | // structure for recording the beginning and end of any multi-step | |
371 | // transformations. These are informational, and not required to reproduce the | |
372 | // graph state. | |
373 | type marshalOperation struct { | |
374 | Type string | |
375 | Begin string `json:",omitempty"` | |
376 | End string `json:",omitempty"` | |
377 | Info string `json:",omitempty"` | |
378 | } | |
379 | ||
380 | // decodeGraph decodes a marshalGraph from an encoded graph stream. | |
381 | func decodeGraph(r io.Reader) (*marshalGraph, error) { | |
382 | dec := json.NewDecoder(r) | |
383 | ||
384 | // a stream should always start with a graph | |
385 | g := &marshalGraph{} | |
386 | ||
387 | err := dec.Decode(g) | |
388 | if err != nil { | |
389 | return nil, err | |
390 | } | |
391 | ||
392 | // now replay any operations that occurred on the original graph | |
393 | for dec.More() { | |
394 | s := &streamDecode{} | |
395 | err := dec.Decode(s) | |
396 | if err != nil { | |
397 | return g, err | |
398 | } | |
399 | ||
400 | // the only Type we're concerned with here is Transform to complete the | |
401 | // Graph | |
402 | if s.Type != typeTransform { | |
403 | continue | |
404 | } | |
405 | ||
406 | t := &marshalTransform{} | |
407 | err = json.Unmarshal(s.JSON, t) | |
408 | if err != nil { | |
409 | return g, err | |
410 | } | |
411 | t.Transform(g) | |
412 | } | |
413 | return g, nil | |
414 | } | |
415 | ||
416 | // marshalVertexInfo allows encoding arbitrary information about the a single | |
417 | // Vertex in the logs. These are accumulated for informational display while | |
418 | // rebuilding the graph. | |
419 | type marshalVertexInfo struct { | |
420 | Type string | |
421 | Vertex *marshalVertex | |
422 | Info string | |
423 | } | |
424 | ||
425 | func newVertexInfo(infoType string, v Vertex, info string) *marshalVertexInfo { | |
426 | return &marshalVertexInfo{ | |
427 | Type: infoType, | |
428 | Vertex: newMarshalVertex(v), | |
429 | Info: info, | |
430 | } | |
431 | } | |
432 | ||
433 | // marshalEdgeInfo allows encoding arbitrary information about the a single | |
434 | // Edge in the logs. These are accumulated for informational display while | |
435 | // rebuilding the graph. | |
436 | type marshalEdgeInfo struct { | |
437 | Type string | |
438 | Edge *marshalEdge | |
439 | Info string | |
440 | } | |
441 | ||
442 | func newEdgeInfo(infoType string, e Edge, info string) *marshalEdgeInfo { | |
443 | return &marshalEdgeInfo{ | |
444 | Type: infoType, | |
445 | Edge: newMarshalEdge(e), | |
446 | Info: info, | |
447 | } | |
448 | } | |
449 | ||
450 | // JSON2Dot reads a Graph debug log from and io.Reader, and converts the final | |
451 | // graph dot format. | |
452 | // | |
453 | // TODO: Allow returning the output at a certain point during decode. | |
454 | // Encode extra information from the json log into the Dot. | |
455 | func JSON2Dot(r io.Reader) ([]byte, error) { | |
456 | g, err := decodeGraph(r) | |
457 | if err != nil { | |
458 | return nil, err | |
459 | } | |
460 | ||
461 | return g.Dot(nil), nil | |
462 | } |