diff options
Diffstat (limited to 'vendor/github.com/hashicorp/terraform/dag/graph.go')
-rw-r--r-- | vendor/github.com/hashicorp/terraform/dag/graph.go | 391 |
1 files changed, 391 insertions, 0 deletions
diff --git a/vendor/github.com/hashicorp/terraform/dag/graph.go b/vendor/github.com/hashicorp/terraform/dag/graph.go new file mode 100644 index 0000000..e7517a2 --- /dev/null +++ b/vendor/github.com/hashicorp/terraform/dag/graph.go | |||
@@ -0,0 +1,391 @@ | |||
1 | package dag | ||
2 | |||
3 | import ( | ||
4 | "bytes" | ||
5 | "encoding/json" | ||
6 | "fmt" | ||
7 | "io" | ||
8 | "sort" | ||
9 | ) | ||
10 | |||
11 | // Graph is used to represent a dependency graph. | ||
12 | type Graph struct { | ||
13 | vertices *Set | ||
14 | edges *Set | ||
15 | downEdges map[interface{}]*Set | ||
16 | upEdges map[interface{}]*Set | ||
17 | |||
18 | // JSON encoder for recording debug information | ||
19 | debug *encoder | ||
20 | } | ||
21 | |||
22 | // Subgrapher allows a Vertex to be a Graph itself, by returning a Grapher. | ||
23 | type Subgrapher interface { | ||
24 | Subgraph() Grapher | ||
25 | } | ||
26 | |||
27 | // A Grapher is any type that returns a Grapher, mainly used to identify | ||
28 | // dag.Graph and dag.AcyclicGraph. In the case of Graph and AcyclicGraph, they | ||
29 | // return themselves. | ||
30 | type Grapher interface { | ||
31 | DirectedGraph() Grapher | ||
32 | } | ||
33 | |||
34 | // Vertex of the graph. | ||
35 | type Vertex interface{} | ||
36 | |||
37 | // NamedVertex is an optional interface that can be implemented by Vertex | ||
38 | // to give it a human-friendly name that is used for outputting the graph. | ||
39 | type NamedVertex interface { | ||
40 | Vertex | ||
41 | Name() string | ||
42 | } | ||
43 | |||
44 | func (g *Graph) DirectedGraph() Grapher { | ||
45 | return g | ||
46 | } | ||
47 | |||
48 | // Vertices returns the list of all the vertices in the graph. | ||
49 | func (g *Graph) Vertices() []Vertex { | ||
50 | list := g.vertices.List() | ||
51 | result := make([]Vertex, len(list)) | ||
52 | for i, v := range list { | ||
53 | result[i] = v.(Vertex) | ||
54 | } | ||
55 | |||
56 | return result | ||
57 | } | ||
58 | |||
59 | // Edges returns the list of all the edges in the graph. | ||
60 | func (g *Graph) Edges() []Edge { | ||
61 | list := g.edges.List() | ||
62 | result := make([]Edge, len(list)) | ||
63 | for i, v := range list { | ||
64 | result[i] = v.(Edge) | ||
65 | } | ||
66 | |||
67 | return result | ||
68 | } | ||
69 | |||
70 | // EdgesFrom returns the list of edges from the given source. | ||
71 | func (g *Graph) EdgesFrom(v Vertex) []Edge { | ||
72 | var result []Edge | ||
73 | from := hashcode(v) | ||
74 | for _, e := range g.Edges() { | ||
75 | if hashcode(e.Source()) == from { | ||
76 | result = append(result, e) | ||
77 | } | ||
78 | } | ||
79 | |||
80 | return result | ||
81 | } | ||
82 | |||
83 | // EdgesTo returns the list of edges to the given target. | ||
84 | func (g *Graph) EdgesTo(v Vertex) []Edge { | ||
85 | var result []Edge | ||
86 | search := hashcode(v) | ||
87 | for _, e := range g.Edges() { | ||
88 | if hashcode(e.Target()) == search { | ||
89 | result = append(result, e) | ||
90 | } | ||
91 | } | ||
92 | |||
93 | return result | ||
94 | } | ||
95 | |||
96 | // HasVertex checks if the given Vertex is present in the graph. | ||
97 | func (g *Graph) HasVertex(v Vertex) bool { | ||
98 | return g.vertices.Include(v) | ||
99 | } | ||
100 | |||
101 | // HasEdge checks if the given Edge is present in the graph. | ||
102 | func (g *Graph) HasEdge(e Edge) bool { | ||
103 | return g.edges.Include(e) | ||
104 | } | ||
105 | |||
106 | // Add adds a vertex to the graph. This is safe to call multiple time with | ||
107 | // the same Vertex. | ||
108 | func (g *Graph) Add(v Vertex) Vertex { | ||
109 | g.init() | ||
110 | g.vertices.Add(v) | ||
111 | g.debug.Add(v) | ||
112 | return v | ||
113 | } | ||
114 | |||
115 | // Remove removes a vertex from the graph. This will also remove any | ||
116 | // edges with this vertex as a source or target. | ||
117 | func (g *Graph) Remove(v Vertex) Vertex { | ||
118 | // Delete the vertex itself | ||
119 | g.vertices.Delete(v) | ||
120 | g.debug.Remove(v) | ||
121 | |||
122 | // Delete the edges to non-existent things | ||
123 | for _, target := range g.DownEdges(v).List() { | ||
124 | g.RemoveEdge(BasicEdge(v, target)) | ||
125 | } | ||
126 | for _, source := range g.UpEdges(v).List() { | ||
127 | g.RemoveEdge(BasicEdge(source, v)) | ||
128 | } | ||
129 | |||
130 | return nil | ||
131 | } | ||
132 | |||
133 | // Replace replaces the original Vertex with replacement. If the original | ||
134 | // does not exist within the graph, then false is returned. Otherwise, true | ||
135 | // is returned. | ||
136 | func (g *Graph) Replace(original, replacement Vertex) bool { | ||
137 | // If we don't have the original, we can't do anything | ||
138 | if !g.vertices.Include(original) { | ||
139 | return false | ||
140 | } | ||
141 | |||
142 | defer g.debug.BeginOperation("Replace", "").End("") | ||
143 | |||
144 | // If they're the same, then don't do anything | ||
145 | if original == replacement { | ||
146 | return true | ||
147 | } | ||
148 | |||
149 | // Add our new vertex, then copy all the edges | ||
150 | g.Add(replacement) | ||
151 | for _, target := range g.DownEdges(original).List() { | ||
152 | g.Connect(BasicEdge(replacement, target)) | ||
153 | } | ||
154 | for _, source := range g.UpEdges(original).List() { | ||
155 | g.Connect(BasicEdge(source, replacement)) | ||
156 | } | ||
157 | |||
158 | // Remove our old vertex, which will also remove all the edges | ||
159 | g.Remove(original) | ||
160 | |||
161 | return true | ||
162 | } | ||
163 | |||
164 | // RemoveEdge removes an edge from the graph. | ||
165 | func (g *Graph) RemoveEdge(edge Edge) { | ||
166 | g.init() | ||
167 | g.debug.RemoveEdge(edge) | ||
168 | |||
169 | // Delete the edge from the set | ||
170 | g.edges.Delete(edge) | ||
171 | |||
172 | // Delete the up/down edges | ||
173 | if s, ok := g.downEdges[hashcode(edge.Source())]; ok { | ||
174 | s.Delete(edge.Target()) | ||
175 | } | ||
176 | if s, ok := g.upEdges[hashcode(edge.Target())]; ok { | ||
177 | s.Delete(edge.Source()) | ||
178 | } | ||
179 | } | ||
180 | |||
181 | // DownEdges returns the outward edges from the source Vertex v. | ||
182 | func (g *Graph) DownEdges(v Vertex) *Set { | ||
183 | g.init() | ||
184 | return g.downEdges[hashcode(v)] | ||
185 | } | ||
186 | |||
187 | // UpEdges returns the inward edges to the destination Vertex v. | ||
188 | func (g *Graph) UpEdges(v Vertex) *Set { | ||
189 | g.init() | ||
190 | return g.upEdges[hashcode(v)] | ||
191 | } | ||
192 | |||
193 | // Connect adds an edge with the given source and target. This is safe to | ||
194 | // call multiple times with the same value. Note that the same value is | ||
195 | // verified through pointer equality of the vertices, not through the | ||
196 | // value of the edge itself. | ||
197 | func (g *Graph) Connect(edge Edge) { | ||
198 | g.init() | ||
199 | g.debug.Connect(edge) | ||
200 | |||
201 | source := edge.Source() | ||
202 | target := edge.Target() | ||
203 | sourceCode := hashcode(source) | ||
204 | targetCode := hashcode(target) | ||
205 | |||
206 | // Do we have this already? If so, don't add it again. | ||
207 | if s, ok := g.downEdges[sourceCode]; ok && s.Include(target) { | ||
208 | return | ||
209 | } | ||
210 | |||
211 | // Add the edge to the set | ||
212 | g.edges.Add(edge) | ||
213 | |||
214 | // Add the down edge | ||
215 | s, ok := g.downEdges[sourceCode] | ||
216 | if !ok { | ||
217 | s = new(Set) | ||
218 | g.downEdges[sourceCode] = s | ||
219 | } | ||
220 | s.Add(target) | ||
221 | |||
222 | // Add the up edge | ||
223 | s, ok = g.upEdges[targetCode] | ||
224 | if !ok { | ||
225 | s = new(Set) | ||
226 | g.upEdges[targetCode] = s | ||
227 | } | ||
228 | s.Add(source) | ||
229 | } | ||
230 | |||
231 | // String outputs some human-friendly output for the graph structure. | ||
232 | func (g *Graph) StringWithNodeTypes() string { | ||
233 | var buf bytes.Buffer | ||
234 | |||
235 | // Build the list of node names and a mapping so that we can more | ||
236 | // easily alphabetize the output to remain deterministic. | ||
237 | vertices := g.Vertices() | ||
238 | names := make([]string, 0, len(vertices)) | ||
239 | mapping := make(map[string]Vertex, len(vertices)) | ||
240 | for _, v := range vertices { | ||
241 | name := VertexName(v) | ||
242 | names = append(names, name) | ||
243 | mapping[name] = v | ||
244 | } | ||
245 | sort.Strings(names) | ||
246 | |||
247 | // Write each node in order... | ||
248 | for _, name := range names { | ||
249 | v := mapping[name] | ||
250 | targets := g.downEdges[hashcode(v)] | ||
251 | |||
252 | buf.WriteString(fmt.Sprintf("%s - %T\n", name, v)) | ||
253 | |||
254 | // Alphabetize dependencies | ||
255 | deps := make([]string, 0, targets.Len()) | ||
256 | targetNodes := make(map[string]Vertex) | ||
257 | for _, target := range targets.List() { | ||
258 | dep := VertexName(target) | ||
259 | deps = append(deps, dep) | ||
260 | targetNodes[dep] = target | ||
261 | } | ||
262 | sort.Strings(deps) | ||
263 | |||
264 | // Write dependencies | ||
265 | for _, d := range deps { | ||
266 | buf.WriteString(fmt.Sprintf(" %s - %T\n", d, targetNodes[d])) | ||
267 | } | ||
268 | } | ||
269 | |||
270 | return buf.String() | ||
271 | } | ||
272 | |||
273 | // String outputs some human-friendly output for the graph structure. | ||
274 | func (g *Graph) String() string { | ||
275 | var buf bytes.Buffer | ||
276 | |||
277 | // Build the list of node names and a mapping so that we can more | ||
278 | // easily alphabetize the output to remain deterministic. | ||
279 | vertices := g.Vertices() | ||
280 | names := make([]string, 0, len(vertices)) | ||
281 | mapping := make(map[string]Vertex, len(vertices)) | ||
282 | for _, v := range vertices { | ||
283 | name := VertexName(v) | ||
284 | names = append(names, name) | ||
285 | mapping[name] = v | ||
286 | } | ||
287 | sort.Strings(names) | ||
288 | |||
289 | // Write each node in order... | ||
290 | for _, name := range names { | ||
291 | v := mapping[name] | ||
292 | targets := g.downEdges[hashcode(v)] | ||
293 | |||
294 | buf.WriteString(fmt.Sprintf("%s\n", name)) | ||
295 | |||
296 | // Alphabetize dependencies | ||
297 | deps := make([]string, 0, targets.Len()) | ||
298 | for _, target := range targets.List() { | ||
299 | deps = append(deps, VertexName(target)) | ||
300 | } | ||
301 | sort.Strings(deps) | ||
302 | |||
303 | // Write dependencies | ||
304 | for _, d := range deps { | ||
305 | buf.WriteString(fmt.Sprintf(" %s\n", d)) | ||
306 | } | ||
307 | } | ||
308 | |||
309 | return buf.String() | ||
310 | } | ||
311 | |||
312 | func (g *Graph) init() { | ||
313 | if g.vertices == nil { | ||
314 | g.vertices = new(Set) | ||
315 | } | ||
316 | if g.edges == nil { | ||
317 | g.edges = new(Set) | ||
318 | } | ||
319 | if g.downEdges == nil { | ||
320 | g.downEdges = make(map[interface{}]*Set) | ||
321 | } | ||
322 | if g.upEdges == nil { | ||
323 | g.upEdges = make(map[interface{}]*Set) | ||
324 | } | ||
325 | } | ||
326 | |||
327 | // Dot returns a dot-formatted representation of the Graph. | ||
328 | func (g *Graph) Dot(opts *DotOpts) []byte { | ||
329 | return newMarshalGraph("", g).Dot(opts) | ||
330 | } | ||
331 | |||
332 | // MarshalJSON returns a JSON representation of the entire Graph. | ||
333 | func (g *Graph) MarshalJSON() ([]byte, error) { | ||
334 | dg := newMarshalGraph("root", g) | ||
335 | return json.MarshalIndent(dg, "", " ") | ||
336 | } | ||
337 | |||
338 | // SetDebugWriter sets the io.Writer where the Graph will record debug | ||
339 | // information. After this is set, the graph will immediately encode itself to | ||
340 | // the stream, and continue to record all subsequent operations. | ||
341 | func (g *Graph) SetDebugWriter(w io.Writer) { | ||
342 | g.debug = &encoder{w: w} | ||
343 | g.debug.Encode(newMarshalGraph("root", g)) | ||
344 | } | ||
345 | |||
346 | // DebugVertexInfo encodes arbitrary information about a vertex in the graph | ||
347 | // debug logs. | ||
348 | func (g *Graph) DebugVertexInfo(v Vertex, info string) { | ||
349 | va := newVertexInfo(typeVertexInfo, v, info) | ||
350 | g.debug.Encode(va) | ||
351 | } | ||
352 | |||
353 | // DebugEdgeInfo encodes arbitrary information about an edge in the graph debug | ||
354 | // logs. | ||
355 | func (g *Graph) DebugEdgeInfo(e Edge, info string) { | ||
356 | ea := newEdgeInfo(typeEdgeInfo, e, info) | ||
357 | g.debug.Encode(ea) | ||
358 | } | ||
359 | |||
360 | // DebugVisitInfo records a visit to a Vertex during a walk operation. | ||
361 | func (g *Graph) DebugVisitInfo(v Vertex, info string) { | ||
362 | vi := newVertexInfo(typeVisitInfo, v, info) | ||
363 | g.debug.Encode(vi) | ||
364 | } | ||
365 | |||
366 | // DebugOperation marks the start of a set of graph transformations in | ||
367 | // the debug log, and returns a DebugOperationEnd func, which marks the end of | ||
368 | // the operation in the log. Additional information can be added to the log via | ||
369 | // the info parameter. | ||
370 | // | ||
371 | // The returned func's End method allows this method to be called from a single | ||
372 | // defer statement: | ||
373 | // defer g.DebugOperationBegin("OpName", "operating").End("") | ||
374 | // | ||
375 | // The returned function must be called to properly close the logical operation | ||
376 | // in the logs. | ||
377 | func (g *Graph) DebugOperation(operation string, info string) DebugOperationEnd { | ||
378 | return g.debug.BeginOperation(operation, info) | ||
379 | } | ||
380 | |||
381 | // VertexName returns the name of a vertex. | ||
382 | func VertexName(raw Vertex) string { | ||
383 | switch v := raw.(type) { | ||
384 | case NamedVertex: | ||
385 | return v.Name() | ||
386 | case fmt.Stringer: | ||
387 | return fmt.Sprintf("%s", v) | ||
388 | default: | ||
389 | return fmt.Sprintf("%v", v) | ||
390 | } | ||
391 | } | ||