diff options
Diffstat (limited to 'vendor/github.com/hashicorp/terraform/dag/marshal.go')
-rw-r--r-- | vendor/github.com/hashicorp/terraform/dag/marshal.go | 462 |
1 files changed, 462 insertions, 0 deletions
diff --git a/vendor/github.com/hashicorp/terraform/dag/marshal.go b/vendor/github.com/hashicorp/terraform/dag/marshal.go new file mode 100644 index 0000000..16d5dd6 --- /dev/null +++ b/vendor/github.com/hashicorp/terraform/dag/marshal.go | |||
@@ -0,0 +1,462 @@ | |||
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 | } | ||