]>
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) { | |
15c0b25d AP |
276 | if e == nil { |
277 | return | |
278 | } | |
bae9f6d2 JC |
279 | e.Encode(marshalTransform{ |
280 | Type: typeTransform, | |
281 | AddVertex: newMarshalVertex(v), | |
282 | }) | |
283 | } | |
284 | ||
285 | // Remove records the removal of Vertex v. | |
286 | func (e *encoder) Remove(v Vertex) { | |
15c0b25d AP |
287 | if e == nil { |
288 | return | |
289 | } | |
bae9f6d2 JC |
290 | e.Encode(marshalTransform{ |
291 | Type: typeTransform, | |
292 | RemoveVertex: newMarshalVertex(v), | |
293 | }) | |
294 | } | |
295 | ||
296 | func (e *encoder) Connect(edge Edge) { | |
15c0b25d AP |
297 | if e == nil { |
298 | return | |
299 | } | |
bae9f6d2 JC |
300 | e.Encode(marshalTransform{ |
301 | Type: typeTransform, | |
302 | AddEdge: newMarshalEdge(edge), | |
303 | }) | |
304 | } | |
305 | ||
306 | func (e *encoder) RemoveEdge(edge Edge) { | |
15c0b25d AP |
307 | if e == nil { |
308 | return | |
309 | } | |
bae9f6d2 JC |
310 | e.Encode(marshalTransform{ |
311 | Type: typeTransform, | |
312 | RemoveEdge: newMarshalEdge(edge), | |
313 | }) | |
314 | } | |
315 | ||
316 | // BeginOperation marks the start of set of graph transformations, and returns | |
317 | // an EndDebugOperation func to be called once the opration is complete. | |
318 | func (e *encoder) BeginOperation(op string, info string) DebugOperationEnd { | |
319 | if e == nil { | |
320 | return func(string) {} | |
321 | } | |
322 | ||
323 | e.Encode(marshalOperation{ | |
324 | Type: typeOperation, | |
325 | Begin: op, | |
326 | Info: info, | |
327 | }) | |
328 | ||
329 | return func(info string) { | |
330 | e.Encode(marshalOperation{ | |
331 | Type: typeOperation, | |
332 | End: op, | |
333 | Info: info, | |
334 | }) | |
335 | } | |
336 | } | |
337 | ||
338 | // structure for recording graph transformations | |
339 | type marshalTransform struct { | |
340 | // Type: "Transform" | |
341 | Type string | |
342 | AddEdge *marshalEdge `json:",omitempty"` | |
343 | RemoveEdge *marshalEdge `json:",omitempty"` | |
344 | AddVertex *marshalVertex `json:",omitempty"` | |
345 | RemoveVertex *marshalVertex `json:",omitempty"` | |
346 | } | |
347 | ||
348 | func (t marshalTransform) Transform(g *marshalGraph) { | |
349 | switch { | |
350 | case t.AddEdge != nil: | |
351 | g.connect(t.AddEdge) | |
352 | case t.RemoveEdge != nil: | |
353 | g.removeEdge(t.RemoveEdge) | |
354 | case t.AddVertex != nil: | |
355 | g.add(t.AddVertex) | |
356 | case t.RemoveVertex != nil: | |
357 | g.remove(t.RemoveVertex) | |
358 | } | |
359 | } | |
360 | ||
361 | // this structure allows us to decode any object in the json stream for | |
362 | // inspection, then re-decode it into a proper struct if needed. | |
363 | type streamDecode struct { | |
364 | Type string | |
365 | Map map[string]interface{} | |
366 | JSON []byte | |
367 | } | |
368 | ||
369 | func (s *streamDecode) UnmarshalJSON(d []byte) error { | |
370 | s.JSON = d | |
371 | err := json.Unmarshal(d, &s.Map) | |
372 | if err != nil { | |
373 | return err | |
374 | } | |
375 | ||
376 | if t, ok := s.Map["Type"]; ok { | |
377 | s.Type, _ = t.(string) | |
378 | } | |
379 | return nil | |
380 | } | |
381 | ||
382 | // structure for recording the beginning and end of any multi-step | |
383 | // transformations. These are informational, and not required to reproduce the | |
384 | // graph state. | |
385 | type marshalOperation struct { | |
386 | Type string | |
387 | Begin string `json:",omitempty"` | |
388 | End string `json:",omitempty"` | |
389 | Info string `json:",omitempty"` | |
390 | } | |
391 | ||
392 | // decodeGraph decodes a marshalGraph from an encoded graph stream. | |
393 | func decodeGraph(r io.Reader) (*marshalGraph, error) { | |
394 | dec := json.NewDecoder(r) | |
395 | ||
396 | // a stream should always start with a graph | |
397 | g := &marshalGraph{} | |
398 | ||
399 | err := dec.Decode(g) | |
400 | if err != nil { | |
401 | return nil, err | |
402 | } | |
403 | ||
404 | // now replay any operations that occurred on the original graph | |
405 | for dec.More() { | |
406 | s := &streamDecode{} | |
407 | err := dec.Decode(s) | |
408 | if err != nil { | |
409 | return g, err | |
410 | } | |
411 | ||
412 | // the only Type we're concerned with here is Transform to complete the | |
413 | // Graph | |
414 | if s.Type != typeTransform { | |
415 | continue | |
416 | } | |
417 | ||
418 | t := &marshalTransform{} | |
419 | err = json.Unmarshal(s.JSON, t) | |
420 | if err != nil { | |
421 | return g, err | |
422 | } | |
423 | t.Transform(g) | |
424 | } | |
425 | return g, nil | |
426 | } | |
427 | ||
428 | // marshalVertexInfo allows encoding arbitrary information about the a single | |
429 | // Vertex in the logs. These are accumulated for informational display while | |
430 | // rebuilding the graph. | |
431 | type marshalVertexInfo struct { | |
432 | Type string | |
433 | Vertex *marshalVertex | |
434 | Info string | |
435 | } | |
436 | ||
437 | func newVertexInfo(infoType string, v Vertex, info string) *marshalVertexInfo { | |
438 | return &marshalVertexInfo{ | |
439 | Type: infoType, | |
440 | Vertex: newMarshalVertex(v), | |
441 | Info: info, | |
442 | } | |
443 | } | |
444 | ||
445 | // marshalEdgeInfo allows encoding arbitrary information about the a single | |
446 | // Edge in the logs. These are accumulated for informational display while | |
447 | // rebuilding the graph. | |
448 | type marshalEdgeInfo struct { | |
449 | Type string | |
450 | Edge *marshalEdge | |
451 | Info string | |
452 | } | |
453 | ||
454 | func newEdgeInfo(infoType string, e Edge, info string) *marshalEdgeInfo { | |
455 | return &marshalEdgeInfo{ | |
456 | Type: infoType, | |
457 | Edge: newMarshalEdge(e), | |
458 | Info: info, | |
459 | } | |
460 | } | |
461 | ||
462 | // JSON2Dot reads a Graph debug log from and io.Reader, and converts the final | |
463 | // graph dot format. | |
464 | // | |
465 | // TODO: Allow returning the output at a certain point during decode. | |
466 | // Encode extra information from the json log into the Dot. | |
467 | func JSON2Dot(r io.Reader) ([]byte, error) { | |
468 | g, err := decodeGraph(r) | |
469 | if err != nil { | |
470 | return nil, err | |
471 | } | |
472 | ||
473 | return g.Dot(nil), nil | |
474 | } |