diff options
author | Jake Champlin <jake.champlin.27@gmail.com> | 2017-06-06 12:40:07 -0400 |
---|---|---|
committer | Jake Champlin <jake.champlin.27@gmail.com> | 2017-06-06 12:40:07 -0400 |
commit | bae9f6d2fd5eb5bc80929bd393932b23f14d7c93 (patch) | |
tree | ca9ab12a7d78b1fc27a8f734729081357ce6d252 /vendor/github.com/hashicorp/terraform/dag | |
parent | 254c495b6bebab3fb72a243c4bce858d79e6ee99 (diff) | |
download | terraform-provider-statuscake-bae9f6d2fd5eb5bc80929bd393932b23f14d7c93.tar.gz terraform-provider-statuscake-bae9f6d2fd5eb5bc80929bd393932b23f14d7c93.tar.zst terraform-provider-statuscake-bae9f6d2fd5eb5bc80929bd393932b23f14d7c93.zip |
Initial transfer of provider code
Diffstat (limited to 'vendor/github.com/hashicorp/terraform/dag')
-rw-r--r-- | vendor/github.com/hashicorp/terraform/dag/dag.go | 286 | ||||
-rw-r--r-- | vendor/github.com/hashicorp/terraform/dag/dot.go | 282 | ||||
-rw-r--r-- | vendor/github.com/hashicorp/terraform/dag/edge.go | 37 | ||||
-rw-r--r-- | vendor/github.com/hashicorp/terraform/dag/graph.go | 391 | ||||
-rw-r--r-- | vendor/github.com/hashicorp/terraform/dag/marshal.go | 462 | ||||
-rw-r--r-- | vendor/github.com/hashicorp/terraform/dag/set.go | 109 | ||||
-rw-r--r-- | vendor/github.com/hashicorp/terraform/dag/tarjan.go | 107 | ||||
-rw-r--r-- | vendor/github.com/hashicorp/terraform/dag/walk.go | 445 |
8 files changed, 2119 insertions, 0 deletions
diff --git a/vendor/github.com/hashicorp/terraform/dag/dag.go b/vendor/github.com/hashicorp/terraform/dag/dag.go new file mode 100644 index 0000000..f8776bc --- /dev/null +++ b/vendor/github.com/hashicorp/terraform/dag/dag.go | |||
@@ -0,0 +1,286 @@ | |||
1 | package dag | ||
2 | |||
3 | import ( | ||
4 | "fmt" | ||
5 | "sort" | ||
6 | "strings" | ||
7 | |||
8 | "github.com/hashicorp/go-multierror" | ||
9 | ) | ||
10 | |||
11 | // AcyclicGraph is a specialization of Graph that cannot have cycles. With | ||
12 | // this property, we get the property of sane graph traversal. | ||
13 | type AcyclicGraph struct { | ||
14 | Graph | ||
15 | } | ||
16 | |||
17 | // WalkFunc is the callback used for walking the graph. | ||
18 | type WalkFunc func(Vertex) error | ||
19 | |||
20 | // DepthWalkFunc is a walk function that also receives the current depth of the | ||
21 | // walk as an argument | ||
22 | type DepthWalkFunc func(Vertex, int) error | ||
23 | |||
24 | func (g *AcyclicGraph) DirectedGraph() Grapher { | ||
25 | return g | ||
26 | } | ||
27 | |||
28 | // Returns a Set that includes every Vertex yielded by walking down from the | ||
29 | // provided starting Vertex v. | ||
30 | func (g *AcyclicGraph) Ancestors(v Vertex) (*Set, error) { | ||
31 | s := new(Set) | ||
32 | start := AsVertexList(g.DownEdges(v)) | ||
33 | memoFunc := func(v Vertex, d int) error { | ||
34 | s.Add(v) | ||
35 | return nil | ||
36 | } | ||
37 | |||
38 | if err := g.DepthFirstWalk(start, memoFunc); err != nil { | ||
39 | return nil, err | ||
40 | } | ||
41 | |||
42 | return s, nil | ||
43 | } | ||
44 | |||
45 | // Returns a Set that includes every Vertex yielded by walking up from the | ||
46 | // provided starting Vertex v. | ||
47 | func (g *AcyclicGraph) Descendents(v Vertex) (*Set, error) { | ||
48 | s := new(Set) | ||
49 | start := AsVertexList(g.UpEdges(v)) | ||
50 | memoFunc := func(v Vertex, d int) error { | ||
51 | s.Add(v) | ||
52 | return nil | ||
53 | } | ||
54 | |||
55 | if err := g.ReverseDepthFirstWalk(start, memoFunc); err != nil { | ||
56 | return nil, err | ||
57 | } | ||
58 | |||
59 | return s, nil | ||
60 | } | ||
61 | |||
62 | // Root returns the root of the DAG, or an error. | ||
63 | // | ||
64 | // Complexity: O(V) | ||
65 | func (g *AcyclicGraph) Root() (Vertex, error) { | ||
66 | roots := make([]Vertex, 0, 1) | ||
67 | for _, v := range g.Vertices() { | ||
68 | if g.UpEdges(v).Len() == 0 { | ||
69 | roots = append(roots, v) | ||
70 | } | ||
71 | } | ||
72 | |||
73 | if len(roots) > 1 { | ||
74 | // TODO(mitchellh): make this error message a lot better | ||
75 | return nil, fmt.Errorf("multiple roots: %#v", roots) | ||
76 | } | ||
77 | |||
78 | if len(roots) == 0 { | ||
79 | return nil, fmt.Errorf("no roots found") | ||
80 | } | ||
81 | |||
82 | return roots[0], nil | ||
83 | } | ||
84 | |||
85 | // TransitiveReduction performs the transitive reduction of graph g in place. | ||
86 | // The transitive reduction of a graph is a graph with as few edges as | ||
87 | // possible with the same reachability as the original graph. This means | ||
88 | // that if there are three nodes A => B => C, and A connects to both | ||
89 | // B and C, and B connects to C, then the transitive reduction is the | ||
90 | // same graph with only a single edge between A and B, and a single edge | ||
91 | // between B and C. | ||
92 | // | ||
93 | // The graph must be valid for this operation to behave properly. If | ||
94 | // Validate() returns an error, the behavior is undefined and the results | ||
95 | // will likely be unexpected. | ||
96 | // | ||
97 | // Complexity: O(V(V+E)), or asymptotically O(VE) | ||
98 | func (g *AcyclicGraph) TransitiveReduction() { | ||
99 | // For each vertex u in graph g, do a DFS starting from each vertex | ||
100 | // v such that the edge (u,v) exists (v is a direct descendant of u). | ||
101 | // | ||
102 | // For each v-prime reachable from v, remove the edge (u, v-prime). | ||
103 | defer g.debug.BeginOperation("TransitiveReduction", "").End("") | ||
104 | |||
105 | for _, u := range g.Vertices() { | ||
106 | uTargets := g.DownEdges(u) | ||
107 | vs := AsVertexList(g.DownEdges(u)) | ||
108 | |||
109 | g.DepthFirstWalk(vs, func(v Vertex, d int) error { | ||
110 | shared := uTargets.Intersection(g.DownEdges(v)) | ||
111 | for _, vPrime := range AsVertexList(shared) { | ||
112 | g.RemoveEdge(BasicEdge(u, vPrime)) | ||
113 | } | ||
114 | |||
115 | return nil | ||
116 | }) | ||
117 | } | ||
118 | } | ||
119 | |||
120 | // Validate validates the DAG. A DAG is valid if it has a single root | ||
121 | // with no cycles. | ||
122 | func (g *AcyclicGraph) Validate() error { | ||
123 | if _, err := g.Root(); err != nil { | ||
124 | return err | ||
125 | } | ||
126 | |||
127 | // Look for cycles of more than 1 component | ||
128 | var err error | ||
129 | cycles := g.Cycles() | ||
130 | if len(cycles) > 0 { | ||
131 | for _, cycle := range cycles { | ||
132 | cycleStr := make([]string, len(cycle)) | ||
133 | for j, vertex := range cycle { | ||
134 | cycleStr[j] = VertexName(vertex) | ||
135 | } | ||
136 | |||
137 | err = multierror.Append(err, fmt.Errorf( | ||
138 | "Cycle: %s", strings.Join(cycleStr, ", "))) | ||
139 | } | ||
140 | } | ||
141 | |||
142 | // Look for cycles to self | ||
143 | for _, e := range g.Edges() { | ||
144 | if e.Source() == e.Target() { | ||
145 | err = multierror.Append(err, fmt.Errorf( | ||
146 | "Self reference: %s", VertexName(e.Source()))) | ||
147 | } | ||
148 | } | ||
149 | |||
150 | return err | ||
151 | } | ||
152 | |||
153 | func (g *AcyclicGraph) Cycles() [][]Vertex { | ||
154 | var cycles [][]Vertex | ||
155 | for _, cycle := range StronglyConnected(&g.Graph) { | ||
156 | if len(cycle) > 1 { | ||
157 | cycles = append(cycles, cycle) | ||
158 | } | ||
159 | } | ||
160 | return cycles | ||
161 | } | ||
162 | |||
163 | // Walk walks the graph, calling your callback as each node is visited. | ||
164 | // This will walk nodes in parallel if it can. Because the walk is done | ||
165 | // in parallel, the error returned will be a multierror. | ||
166 | func (g *AcyclicGraph) Walk(cb WalkFunc) error { | ||
167 | defer g.debug.BeginOperation(typeWalk, "").End("") | ||
168 | |||
169 | w := &Walker{Callback: cb, Reverse: true} | ||
170 | w.Update(g) | ||
171 | return w.Wait() | ||
172 | } | ||
173 | |||
174 | // simple convenience helper for converting a dag.Set to a []Vertex | ||
175 | func AsVertexList(s *Set) []Vertex { | ||
176 | rawList := s.List() | ||
177 | vertexList := make([]Vertex, len(rawList)) | ||
178 | for i, raw := range rawList { | ||
179 | vertexList[i] = raw.(Vertex) | ||
180 | } | ||
181 | return vertexList | ||
182 | } | ||
183 | |||
184 | type vertexAtDepth struct { | ||
185 | Vertex Vertex | ||
186 | Depth int | ||
187 | } | ||
188 | |||
189 | // depthFirstWalk does a depth-first walk of the graph starting from | ||
190 | // the vertices in start. This is not exported now but it would make sense | ||
191 | // to export this publicly at some point. | ||
192 | func (g *AcyclicGraph) DepthFirstWalk(start []Vertex, f DepthWalkFunc) error { | ||
193 | defer g.debug.BeginOperation(typeDepthFirstWalk, "").End("") | ||
194 | |||
195 | seen := make(map[Vertex]struct{}) | ||
196 | frontier := make([]*vertexAtDepth, len(start)) | ||
197 | for i, v := range start { | ||
198 | frontier[i] = &vertexAtDepth{ | ||
199 | Vertex: v, | ||
200 | Depth: 0, | ||
201 | } | ||
202 | } | ||
203 | for len(frontier) > 0 { | ||
204 | // Pop the current vertex | ||
205 | n := len(frontier) | ||
206 | current := frontier[n-1] | ||
207 | frontier = frontier[:n-1] | ||
208 | |||
209 | // Check if we've seen this already and return... | ||
210 | if _, ok := seen[current.Vertex]; ok { | ||
211 | continue | ||
212 | } | ||
213 | seen[current.Vertex] = struct{}{} | ||
214 | |||
215 | // Visit the current node | ||
216 | if err := f(current.Vertex, current.Depth); err != nil { | ||
217 | return err | ||
218 | } | ||
219 | |||
220 | // Visit targets of this in a consistent order. | ||
221 | targets := AsVertexList(g.DownEdges(current.Vertex)) | ||
222 | sort.Sort(byVertexName(targets)) | ||
223 | for _, t := range targets { | ||
224 | frontier = append(frontier, &vertexAtDepth{ | ||
225 | Vertex: t, | ||
226 | Depth: current.Depth + 1, | ||
227 | }) | ||
228 | } | ||
229 | } | ||
230 | |||
231 | return nil | ||
232 | } | ||
233 | |||
234 | // reverseDepthFirstWalk does a depth-first walk _up_ the graph starting from | ||
235 | // the vertices in start. | ||
236 | func (g *AcyclicGraph) ReverseDepthFirstWalk(start []Vertex, f DepthWalkFunc) error { | ||
237 | defer g.debug.BeginOperation(typeReverseDepthFirstWalk, "").End("") | ||
238 | |||
239 | seen := make(map[Vertex]struct{}) | ||
240 | frontier := make([]*vertexAtDepth, len(start)) | ||
241 | for i, v := range start { | ||
242 | frontier[i] = &vertexAtDepth{ | ||
243 | Vertex: v, | ||
244 | Depth: 0, | ||
245 | } | ||
246 | } | ||
247 | for len(frontier) > 0 { | ||
248 | // Pop the current vertex | ||
249 | n := len(frontier) | ||
250 | current := frontier[n-1] | ||
251 | frontier = frontier[:n-1] | ||
252 | |||
253 | // Check if we've seen this already and return... | ||
254 | if _, ok := seen[current.Vertex]; ok { | ||
255 | continue | ||
256 | } | ||
257 | seen[current.Vertex] = struct{}{} | ||
258 | |||
259 | // Add next set of targets in a consistent order. | ||
260 | targets := AsVertexList(g.UpEdges(current.Vertex)) | ||
261 | sort.Sort(byVertexName(targets)) | ||
262 | for _, t := range targets { | ||
263 | frontier = append(frontier, &vertexAtDepth{ | ||
264 | Vertex: t, | ||
265 | Depth: current.Depth + 1, | ||
266 | }) | ||
267 | } | ||
268 | |||
269 | // Visit the current node | ||
270 | if err := f(current.Vertex, current.Depth); err != nil { | ||
271 | return err | ||
272 | } | ||
273 | } | ||
274 | |||
275 | return nil | ||
276 | } | ||
277 | |||
278 | // byVertexName implements sort.Interface so a list of Vertices can be sorted | ||
279 | // consistently by their VertexName | ||
280 | type byVertexName []Vertex | ||
281 | |||
282 | func (b byVertexName) Len() int { return len(b) } | ||
283 | func (b byVertexName) Swap(i, j int) { b[i], b[j] = b[j], b[i] } | ||
284 | func (b byVertexName) Less(i, j int) bool { | ||
285 | return VertexName(b[i]) < VertexName(b[j]) | ||
286 | } | ||
diff --git a/vendor/github.com/hashicorp/terraform/dag/dot.go b/vendor/github.com/hashicorp/terraform/dag/dot.go new file mode 100644 index 0000000..7e6d2af --- /dev/null +++ b/vendor/github.com/hashicorp/terraform/dag/dot.go | |||
@@ -0,0 +1,282 @@ | |||
1 | package dag | ||
2 | |||
3 | import ( | ||
4 | "bytes" | ||
5 | "fmt" | ||
6 | "sort" | ||
7 | "strings" | ||
8 | ) | ||
9 | |||
10 | // DotOpts are the options for generating a dot formatted Graph. | ||
11 | type DotOpts struct { | ||
12 | // Allows some nodes to decide to only show themselves when the user has | ||
13 | // requested the "verbose" graph. | ||
14 | Verbose bool | ||
15 | |||
16 | // Highlight Cycles | ||
17 | DrawCycles bool | ||
18 | |||
19 | // How many levels to expand modules as we draw | ||
20 | MaxDepth int | ||
21 | |||
22 | // use this to keep the cluster_ naming convention from the previous dot writer | ||
23 | cluster bool | ||
24 | } | ||
25 | |||
26 | // GraphNodeDotter can be implemented by a node to cause it to be included | ||
27 | // in the dot graph. The Dot method will be called which is expected to | ||
28 | // return a representation of this node. | ||
29 | type GraphNodeDotter interface { | ||
30 | // Dot is called to return the dot formatting for the node. | ||
31 | // The first parameter is the title of the node. | ||
32 | // The second parameter includes user-specified options that affect the dot | ||
33 | // graph. See GraphDotOpts below for details. | ||
34 | DotNode(string, *DotOpts) *DotNode | ||
35 | } | ||
36 | |||
37 | // DotNode provides a structure for Vertices to return in order to specify their | ||
38 | // dot format. | ||
39 | type DotNode struct { | ||
40 | Name string | ||
41 | Attrs map[string]string | ||
42 | } | ||
43 | |||
44 | // Returns the DOT representation of this Graph. | ||
45 | func (g *marshalGraph) Dot(opts *DotOpts) []byte { | ||
46 | if opts == nil { | ||
47 | opts = &DotOpts{ | ||
48 | DrawCycles: true, | ||
49 | MaxDepth: -1, | ||
50 | Verbose: true, | ||
51 | } | ||
52 | } | ||
53 | |||
54 | var w indentWriter | ||
55 | w.WriteString("digraph {\n") | ||
56 | w.Indent() | ||
57 | |||
58 | // some dot defaults | ||
59 | w.WriteString(`compound = "true"` + "\n") | ||
60 | w.WriteString(`newrank = "true"` + "\n") | ||
61 | |||
62 | // the top level graph is written as the first subgraph | ||
63 | w.WriteString(`subgraph "root" {` + "\n") | ||
64 | g.writeBody(opts, &w) | ||
65 | |||
66 | // cluster isn't really used other than for naming purposes in some graphs | ||
67 | opts.cluster = opts.MaxDepth != 0 | ||
68 | maxDepth := opts.MaxDepth | ||
69 | if maxDepth == 0 { | ||
70 | maxDepth = -1 | ||
71 | } | ||
72 | |||
73 | for _, s := range g.Subgraphs { | ||
74 | g.writeSubgraph(s, opts, maxDepth, &w) | ||
75 | } | ||
76 | |||
77 | w.Unindent() | ||
78 | w.WriteString("}\n") | ||
79 | return w.Bytes() | ||
80 | } | ||
81 | |||
82 | func (v *marshalVertex) dot(g *marshalGraph, opts *DotOpts) []byte { | ||
83 | var buf bytes.Buffer | ||
84 | graphName := g.Name | ||
85 | if graphName == "" { | ||
86 | graphName = "root" | ||
87 | } | ||
88 | |||
89 | name := v.Name | ||
90 | attrs := v.Attrs | ||
91 | if v.graphNodeDotter != nil { | ||
92 | node := v.graphNodeDotter.DotNode(name, opts) | ||
93 | if node == nil { | ||
94 | return []byte{} | ||
95 | } | ||
96 | |||
97 | newAttrs := make(map[string]string) | ||
98 | for k, v := range attrs { | ||
99 | newAttrs[k] = v | ||
100 | } | ||
101 | for k, v := range node.Attrs { | ||
102 | newAttrs[k] = v | ||
103 | } | ||
104 | |||
105 | name = node.Name | ||
106 | attrs = newAttrs | ||
107 | } | ||
108 | |||
109 | buf.WriteString(fmt.Sprintf(`"[%s] %s"`, graphName, name)) | ||
110 | writeAttrs(&buf, attrs) | ||
111 | buf.WriteByte('\n') | ||
112 | |||
113 | return buf.Bytes() | ||
114 | } | ||
115 | |||
116 | func (e *marshalEdge) dot(g *marshalGraph) string { | ||
117 | var buf bytes.Buffer | ||
118 | graphName := g.Name | ||
119 | if graphName == "" { | ||
120 | graphName = "root" | ||
121 | } | ||
122 | |||
123 | sourceName := g.vertexByID(e.Source).Name | ||
124 | targetName := g.vertexByID(e.Target).Name | ||
125 | s := fmt.Sprintf(`"[%s] %s" -> "[%s] %s"`, graphName, sourceName, graphName, targetName) | ||
126 | buf.WriteString(s) | ||
127 | writeAttrs(&buf, e.Attrs) | ||
128 | |||
129 | return buf.String() | ||
130 | } | ||
131 | |||
132 | func cycleDot(e *marshalEdge, g *marshalGraph) string { | ||
133 | return e.dot(g) + ` [color = "red", penwidth = "2.0"]` | ||
134 | } | ||
135 | |||
136 | // Write the subgraph body. The is recursive, and the depth argument is used to | ||
137 | // record the current depth of iteration. | ||
138 | func (g *marshalGraph) writeSubgraph(sg *marshalGraph, opts *DotOpts, depth int, w *indentWriter) { | ||
139 | if depth == 0 { | ||
140 | return | ||
141 | } | ||
142 | depth-- | ||
143 | |||
144 | name := sg.Name | ||
145 | if opts.cluster { | ||
146 | // we prefix with cluster_ to match the old dot output | ||
147 | name = "cluster_" + name | ||
148 | sg.Attrs["label"] = sg.Name | ||
149 | } | ||
150 | w.WriteString(fmt.Sprintf("subgraph %q {\n", name)) | ||
151 | sg.writeBody(opts, w) | ||
152 | |||
153 | for _, sg := range sg.Subgraphs { | ||
154 | g.writeSubgraph(sg, opts, depth, w) | ||
155 | } | ||
156 | } | ||
157 | |||
158 | func (g *marshalGraph) writeBody(opts *DotOpts, w *indentWriter) { | ||
159 | w.Indent() | ||
160 | |||
161 | for _, as := range attrStrings(g.Attrs) { | ||
162 | w.WriteString(as + "\n") | ||
163 | } | ||
164 | |||
165 | // list of Vertices that aren't to be included in the dot output | ||
166 | skip := map[string]bool{} | ||
167 | |||
168 | for _, v := range g.Vertices { | ||
169 | if v.graphNodeDotter == nil { | ||
170 | skip[v.ID] = true | ||
171 | continue | ||
172 | } | ||
173 | |||
174 | w.Write(v.dot(g, opts)) | ||
175 | } | ||
176 | |||
177 | var dotEdges []string | ||
178 | |||
179 | if opts.DrawCycles { | ||
180 | for _, c := range g.Cycles { | ||
181 | if len(c) < 2 { | ||
182 | continue | ||
183 | } | ||
184 | |||
185 | for i, j := 0, 1; i < len(c); i, j = i+1, j+1 { | ||
186 | if j >= len(c) { | ||
187 | j = 0 | ||
188 | } | ||
189 | src := c[i] | ||
190 | tgt := c[j] | ||
191 | |||
192 | if skip[src.ID] || skip[tgt.ID] { | ||
193 | continue | ||
194 | } | ||
195 | |||
196 | e := &marshalEdge{ | ||
197 | Name: fmt.Sprintf("%s|%s", src.Name, tgt.Name), | ||
198 | Source: src.ID, | ||
199 | Target: tgt.ID, | ||
200 | Attrs: make(map[string]string), | ||
201 | } | ||
202 | |||
203 | dotEdges = append(dotEdges, cycleDot(e, g)) | ||
204 | src = tgt | ||
205 | } | ||
206 | } | ||
207 | } | ||
208 | |||
209 | for _, e := range g.Edges { | ||
210 | dotEdges = append(dotEdges, e.dot(g)) | ||
211 | } | ||
212 | |||
213 | // srot these again to match the old output | ||
214 | sort.Strings(dotEdges) | ||
215 | |||
216 | for _, e := range dotEdges { | ||
217 | w.WriteString(e + "\n") | ||
218 | } | ||
219 | |||
220 | w.Unindent() | ||
221 | w.WriteString("}\n") | ||
222 | } | ||
223 | |||
224 | func writeAttrs(buf *bytes.Buffer, attrs map[string]string) { | ||
225 | if len(attrs) > 0 { | ||
226 | buf.WriteString(" [") | ||
227 | buf.WriteString(strings.Join(attrStrings(attrs), ", ")) | ||
228 | buf.WriteString("]") | ||
229 | } | ||
230 | } | ||
231 | |||
232 | func attrStrings(attrs map[string]string) []string { | ||
233 | strings := make([]string, 0, len(attrs)) | ||
234 | for k, v := range attrs { | ||
235 | strings = append(strings, fmt.Sprintf("%s = %q", k, v)) | ||
236 | } | ||
237 | sort.Strings(strings) | ||
238 | return strings | ||
239 | } | ||
240 | |||
241 | // Provide a bytes.Buffer like structure, which will indent when starting a | ||
242 | // newline. | ||
243 | type indentWriter struct { | ||
244 | bytes.Buffer | ||
245 | level int | ||
246 | } | ||
247 | |||
248 | func (w *indentWriter) indent() { | ||
249 | newline := []byte("\n") | ||
250 | if !bytes.HasSuffix(w.Bytes(), newline) { | ||
251 | return | ||
252 | } | ||
253 | for i := 0; i < w.level; i++ { | ||
254 | w.Buffer.WriteString("\t") | ||
255 | } | ||
256 | } | ||
257 | |||
258 | // Indent increases indentation by 1 | ||
259 | func (w *indentWriter) Indent() { w.level++ } | ||
260 | |||
261 | // Unindent decreases indentation by 1 | ||
262 | func (w *indentWriter) Unindent() { w.level-- } | ||
263 | |||
264 | // the following methods intercecpt the byte.Buffer writes and insert the | ||
265 | // indentation when starting a new line. | ||
266 | func (w *indentWriter) Write(b []byte) (int, error) { | ||
267 | w.indent() | ||
268 | return w.Buffer.Write(b) | ||
269 | } | ||
270 | |||
271 | func (w *indentWriter) WriteString(s string) (int, error) { | ||
272 | w.indent() | ||
273 | return w.Buffer.WriteString(s) | ||
274 | } | ||
275 | func (w *indentWriter) WriteByte(b byte) error { | ||
276 | w.indent() | ||
277 | return w.Buffer.WriteByte(b) | ||
278 | } | ||
279 | func (w *indentWriter) WriteRune(r rune) (int, error) { | ||
280 | w.indent() | ||
281 | return w.Buffer.WriteRune(r) | ||
282 | } | ||
diff --git a/vendor/github.com/hashicorp/terraform/dag/edge.go b/vendor/github.com/hashicorp/terraform/dag/edge.go new file mode 100644 index 0000000..f0d99ee --- /dev/null +++ b/vendor/github.com/hashicorp/terraform/dag/edge.go | |||
@@ -0,0 +1,37 @@ | |||
1 | package dag | ||
2 | |||
3 | import ( | ||
4 | "fmt" | ||
5 | ) | ||
6 | |||
7 | // Edge represents an edge in the graph, with a source and target vertex. | ||
8 | type Edge interface { | ||
9 | Source() Vertex | ||
10 | Target() Vertex | ||
11 | |||
12 | Hashable | ||
13 | } | ||
14 | |||
15 | // BasicEdge returns an Edge implementation that simply tracks the source | ||
16 | // and target given as-is. | ||
17 | func BasicEdge(source, target Vertex) Edge { | ||
18 | return &basicEdge{S: source, T: target} | ||
19 | } | ||
20 | |||
21 | // basicEdge is a basic implementation of Edge that has the source and | ||
22 | // target vertex. | ||
23 | type basicEdge struct { | ||
24 | S, T Vertex | ||
25 | } | ||
26 | |||
27 | func (e *basicEdge) Hashcode() interface{} { | ||
28 | return fmt.Sprintf("%p-%p", e.S, e.T) | ||
29 | } | ||
30 | |||
31 | func (e *basicEdge) Source() Vertex { | ||
32 | return e.S | ||
33 | } | ||
34 | |||
35 | func (e *basicEdge) Target() Vertex { | ||
36 | return e.T | ||
37 | } | ||
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 | } | ||
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 | } | ||
diff --git a/vendor/github.com/hashicorp/terraform/dag/set.go b/vendor/github.com/hashicorp/terraform/dag/set.go new file mode 100644 index 0000000..3929c9d --- /dev/null +++ b/vendor/github.com/hashicorp/terraform/dag/set.go | |||
@@ -0,0 +1,109 @@ | |||
1 | package dag | ||
2 | |||
3 | import ( | ||
4 | "sync" | ||
5 | ) | ||
6 | |||
7 | // Set is a set data structure. | ||
8 | type Set struct { | ||
9 | m map[interface{}]interface{} | ||
10 | once sync.Once | ||
11 | } | ||
12 | |||
13 | // Hashable is the interface used by set to get the hash code of a value. | ||
14 | // If this isn't given, then the value of the item being added to the set | ||
15 | // itself is used as the comparison value. | ||
16 | type Hashable interface { | ||
17 | Hashcode() interface{} | ||
18 | } | ||
19 | |||
20 | // hashcode returns the hashcode used for set elements. | ||
21 | func hashcode(v interface{}) interface{} { | ||
22 | if h, ok := v.(Hashable); ok { | ||
23 | return h.Hashcode() | ||
24 | } | ||
25 | |||
26 | return v | ||
27 | } | ||
28 | |||
29 | // Add adds an item to the set | ||
30 | func (s *Set) Add(v interface{}) { | ||
31 | s.once.Do(s.init) | ||
32 | s.m[hashcode(v)] = v | ||
33 | } | ||
34 | |||
35 | // Delete removes an item from the set. | ||
36 | func (s *Set) Delete(v interface{}) { | ||
37 | s.once.Do(s.init) | ||
38 | delete(s.m, hashcode(v)) | ||
39 | } | ||
40 | |||
41 | // Include returns true/false of whether a value is in the set. | ||
42 | func (s *Set) Include(v interface{}) bool { | ||
43 | s.once.Do(s.init) | ||
44 | _, ok := s.m[hashcode(v)] | ||
45 | return ok | ||
46 | } | ||
47 | |||
48 | // Intersection computes the set intersection with other. | ||
49 | func (s *Set) Intersection(other *Set) *Set { | ||
50 | result := new(Set) | ||
51 | if s == nil { | ||
52 | return result | ||
53 | } | ||
54 | if other != nil { | ||
55 | for _, v := range s.m { | ||
56 | if other.Include(v) { | ||
57 | result.Add(v) | ||
58 | } | ||
59 | } | ||
60 | } | ||
61 | |||
62 | return result | ||
63 | } | ||
64 | |||
65 | // Difference returns a set with the elements that s has but | ||
66 | // other doesn't. | ||
67 | func (s *Set) Difference(other *Set) *Set { | ||
68 | result := new(Set) | ||
69 | if s != nil { | ||
70 | for k, v := range s.m { | ||
71 | var ok bool | ||
72 | if other != nil { | ||
73 | _, ok = other.m[k] | ||
74 | } | ||
75 | if !ok { | ||
76 | result.Add(v) | ||
77 | } | ||
78 | } | ||
79 | } | ||
80 | |||
81 | return result | ||
82 | } | ||
83 | |||
84 | // Len is the number of items in the set. | ||
85 | func (s *Set) Len() int { | ||
86 | if s == nil { | ||
87 | return 0 | ||
88 | } | ||
89 | |||
90 | return len(s.m) | ||
91 | } | ||
92 | |||
93 | // List returns the list of set elements. | ||
94 | func (s *Set) List() []interface{} { | ||
95 | if s == nil { | ||
96 | return nil | ||
97 | } | ||
98 | |||
99 | r := make([]interface{}, 0, len(s.m)) | ||
100 | for _, v := range s.m { | ||
101 | r = append(r, v) | ||
102 | } | ||
103 | |||
104 | return r | ||
105 | } | ||
106 | |||
107 | func (s *Set) init() { | ||
108 | s.m = make(map[interface{}]interface{}) | ||
109 | } | ||
diff --git a/vendor/github.com/hashicorp/terraform/dag/tarjan.go b/vendor/github.com/hashicorp/terraform/dag/tarjan.go new file mode 100644 index 0000000..9d8b25c --- /dev/null +++ b/vendor/github.com/hashicorp/terraform/dag/tarjan.go | |||
@@ -0,0 +1,107 @@ | |||
1 | package dag | ||
2 | |||
3 | // StronglyConnected returns the list of strongly connected components | ||
4 | // within the Graph g. This information is primarily used by this package | ||
5 | // for cycle detection, but strongly connected components have widespread | ||
6 | // use. | ||
7 | func StronglyConnected(g *Graph) [][]Vertex { | ||
8 | vs := g.Vertices() | ||
9 | acct := sccAcct{ | ||
10 | NextIndex: 1, | ||
11 | VertexIndex: make(map[Vertex]int, len(vs)), | ||
12 | } | ||
13 | for _, v := range vs { | ||
14 | // Recurse on any non-visited nodes | ||
15 | if acct.VertexIndex[v] == 0 { | ||
16 | stronglyConnected(&acct, g, v) | ||
17 | } | ||
18 | } | ||
19 | return acct.SCC | ||
20 | } | ||
21 | |||
22 | func stronglyConnected(acct *sccAcct, g *Graph, v Vertex) int { | ||
23 | // Initial vertex visit | ||
24 | index := acct.visit(v) | ||
25 | minIdx := index | ||
26 | |||
27 | for _, raw := range g.DownEdges(v).List() { | ||
28 | target := raw.(Vertex) | ||
29 | targetIdx := acct.VertexIndex[target] | ||
30 | |||
31 | // Recurse on successor if not yet visited | ||
32 | if targetIdx == 0 { | ||
33 | minIdx = min(minIdx, stronglyConnected(acct, g, target)) | ||
34 | } else if acct.inStack(target) { | ||
35 | // Check if the vertex is in the stack | ||
36 | minIdx = min(minIdx, targetIdx) | ||
37 | } | ||
38 | } | ||
39 | |||
40 | // Pop the strongly connected components off the stack if | ||
41 | // this is a root vertex | ||
42 | if index == minIdx { | ||
43 | var scc []Vertex | ||
44 | for { | ||
45 | v2 := acct.pop() | ||
46 | scc = append(scc, v2) | ||
47 | if v2 == v { | ||
48 | break | ||
49 | } | ||
50 | } | ||
51 | |||
52 | acct.SCC = append(acct.SCC, scc) | ||
53 | } | ||
54 | |||
55 | return minIdx | ||
56 | } | ||
57 | |||
58 | func min(a, b int) int { | ||
59 | if a <= b { | ||
60 | return a | ||
61 | } | ||
62 | return b | ||
63 | } | ||
64 | |||
65 | // sccAcct is used ot pass around accounting information for | ||
66 | // the StronglyConnectedComponents algorithm | ||
67 | type sccAcct struct { | ||
68 | NextIndex int | ||
69 | VertexIndex map[Vertex]int | ||
70 | Stack []Vertex | ||
71 | SCC [][]Vertex | ||
72 | } | ||
73 | |||
74 | // visit assigns an index and pushes a vertex onto the stack | ||
75 | func (s *sccAcct) visit(v Vertex) int { | ||
76 | idx := s.NextIndex | ||
77 | s.VertexIndex[v] = idx | ||
78 | s.NextIndex++ | ||
79 | s.push(v) | ||
80 | return idx | ||
81 | } | ||
82 | |||
83 | // push adds a vertex to the stack | ||
84 | func (s *sccAcct) push(n Vertex) { | ||
85 | s.Stack = append(s.Stack, n) | ||
86 | } | ||
87 | |||
88 | // pop removes a vertex from the stack | ||
89 | func (s *sccAcct) pop() Vertex { | ||
90 | n := len(s.Stack) | ||
91 | if n == 0 { | ||
92 | return nil | ||
93 | } | ||
94 | vertex := s.Stack[n-1] | ||
95 | s.Stack = s.Stack[:n-1] | ||
96 | return vertex | ||
97 | } | ||
98 | |||
99 | // inStack checks if a vertex is in the stack | ||
100 | func (s *sccAcct) inStack(needle Vertex) bool { | ||
101 | for _, n := range s.Stack { | ||
102 | if n == needle { | ||
103 | return true | ||
104 | } | ||
105 | } | ||
106 | return false | ||
107 | } | ||
diff --git a/vendor/github.com/hashicorp/terraform/dag/walk.go b/vendor/github.com/hashicorp/terraform/dag/walk.go new file mode 100644 index 0000000..23c87ad --- /dev/null +++ b/vendor/github.com/hashicorp/terraform/dag/walk.go | |||
@@ -0,0 +1,445 @@ | |||
1 | package dag | ||
2 | |||
3 | import ( | ||
4 | "errors" | ||
5 | "fmt" | ||
6 | "log" | ||
7 | "sync" | ||
8 | "time" | ||
9 | |||
10 | "github.com/hashicorp/go-multierror" | ||
11 | ) | ||
12 | |||
13 | // Walker is used to walk every vertex of a graph in parallel. | ||
14 | // | ||
15 | // A vertex will only be walked when the dependencies of that vertex have | ||
16 | // been walked. If two vertices can be walked at the same time, they will be. | ||
17 | // | ||
18 | // Update can be called to update the graph. This can be called even during | ||
19 | // a walk, cahnging vertices/edges mid-walk. This should be done carefully. | ||
20 | // If a vertex is removed but has already been executed, the result of that | ||
21 | // execution (any error) is still returned by Wait. Changing or re-adding | ||
22 | // a vertex that has already executed has no effect. Changing edges of | ||
23 | // a vertex that has already executed has no effect. | ||
24 | // | ||
25 | // Non-parallelism can be enforced by introducing a lock in your callback | ||
26 | // function. However, the goroutine overhead of a walk will remain. | ||
27 | // Walker will create V*2 goroutines (one for each vertex, and dependency | ||
28 | // waiter for each vertex). In general this should be of no concern unless | ||
29 | // there are a huge number of vertices. | ||
30 | // | ||
31 | // The walk is depth first by default. This can be changed with the Reverse | ||
32 | // option. | ||
33 | // | ||
34 | // A single walker is only valid for one graph walk. After the walk is complete | ||
35 | // you must construct a new walker to walk again. State for the walk is never | ||
36 | // deleted in case vertices or edges are changed. | ||
37 | type Walker struct { | ||
38 | // Callback is what is called for each vertex | ||
39 | Callback WalkFunc | ||
40 | |||
41 | // Reverse, if true, causes the source of an edge to depend on a target. | ||
42 | // When false (default), the target depends on the source. | ||
43 | Reverse bool | ||
44 | |||
45 | // changeLock must be held to modify any of the fields below. Only Update | ||
46 | // should modify these fields. Modifying them outside of Update can cause | ||
47 | // serious problems. | ||
48 | changeLock sync.Mutex | ||
49 | vertices Set | ||
50 | edges Set | ||
51 | vertexMap map[Vertex]*walkerVertex | ||
52 | |||
53 | // wait is done when all vertices have executed. It may become "undone" | ||
54 | // if new vertices are added. | ||
55 | wait sync.WaitGroup | ||
56 | |||
57 | // errMap contains the errors recorded so far for execution. Reading | ||
58 | // and writing should hold errLock. | ||
59 | errMap map[Vertex]error | ||
60 | errLock sync.Mutex | ||
61 | } | ||
62 | |||
63 | type walkerVertex struct { | ||
64 | // These should only be set once on initialization and never written again. | ||
65 | // They are not protected by a lock since they don't need to be since | ||
66 | // they are write-once. | ||
67 | |||
68 | // DoneCh is closed when this vertex has completed execution, regardless | ||
69 | // of success. | ||
70 | // | ||
71 | // CancelCh is closed when the vertex should cancel execution. If execution | ||
72 | // is already complete (DoneCh is closed), this has no effect. Otherwise, | ||
73 | // execution is cancelled as quickly as possible. | ||
74 | DoneCh chan struct{} | ||
75 | CancelCh chan struct{} | ||
76 | |||
77 | // Dependency information. Any changes to any of these fields requires | ||
78 | // holding DepsLock. | ||
79 | // | ||
80 | // DepsCh is sent a single value that denotes whether the upstream deps | ||
81 | // were successful (no errors). Any value sent means that the upstream | ||
82 | // dependencies are complete. No other values will ever be sent again. | ||
83 | // | ||
84 | // DepsUpdateCh is closed when there is a new DepsCh set. | ||
85 | DepsCh chan bool | ||
86 | DepsUpdateCh chan struct{} | ||
87 | DepsLock sync.Mutex | ||
88 | |||
89 | // Below is not safe to read/write in parallel. This behavior is | ||
90 | // enforced by changes only happening in Update. Nothing else should | ||
91 | // ever modify these. | ||
92 | deps map[Vertex]chan struct{} | ||
93 | depsCancelCh chan struct{} | ||
94 | } | ||
95 | |||
96 | // errWalkUpstream is used in the errMap of a walk to note that an upstream | ||
97 | // dependency failed so this vertex wasn't run. This is not shown in the final | ||
98 | // user-returned error. | ||
99 | var errWalkUpstream = errors.New("upstream dependency failed") | ||
100 | |||
101 | // Wait waits for the completion of the walk and returns any errors ( | ||
102 | // in the form of a multierror) that occurred. Update should be called | ||
103 | // to populate the walk with vertices and edges prior to calling this. | ||
104 | // | ||
105 | // Wait will return as soon as all currently known vertices are complete. | ||
106 | // If you plan on calling Update with more vertices in the future, you | ||
107 | // should not call Wait until after this is done. | ||
108 | func (w *Walker) Wait() error { | ||
109 | // Wait for completion | ||
110 | w.wait.Wait() | ||
111 | |||
112 | // Grab the error lock | ||
113 | w.errLock.Lock() | ||
114 | defer w.errLock.Unlock() | ||
115 | |||
116 | // Build the error | ||
117 | var result error | ||
118 | for v, err := range w.errMap { | ||
119 | if err != nil && err != errWalkUpstream { | ||
120 | result = multierror.Append(result, fmt.Errorf( | ||
121 | "%s: %s", VertexName(v), err)) | ||
122 | } | ||
123 | } | ||
124 | |||
125 | return result | ||
126 | } | ||
127 | |||
128 | // Update updates the currently executing walk with the given graph. | ||
129 | // This will perform a diff of the vertices and edges and update the walker. | ||
130 | // Already completed vertices remain completed (including any errors during | ||
131 | // their execution). | ||
132 | // | ||
133 | // This returns immediately once the walker is updated; it does not wait | ||
134 | // for completion of the walk. | ||
135 | // | ||
136 | // Multiple Updates can be called in parallel. Update can be called at any | ||
137 | // time during a walk. | ||
138 | func (w *Walker) Update(g *AcyclicGraph) { | ||
139 | var v, e *Set | ||
140 | if g != nil { | ||
141 | v, e = g.vertices, g.edges | ||
142 | } | ||
143 | |||
144 | // Grab the change lock so no more updates happen but also so that | ||
145 | // no new vertices are executed during this time since we may be | ||
146 | // removing them. | ||
147 | w.changeLock.Lock() | ||
148 | defer w.changeLock.Unlock() | ||
149 | |||
150 | // Initialize fields | ||
151 | if w.vertexMap == nil { | ||
152 | w.vertexMap = make(map[Vertex]*walkerVertex) | ||
153 | } | ||
154 | |||
155 | // Calculate all our sets | ||
156 | newEdges := e.Difference(&w.edges) | ||
157 | oldEdges := w.edges.Difference(e) | ||
158 | newVerts := v.Difference(&w.vertices) | ||
159 | oldVerts := w.vertices.Difference(v) | ||
160 | |||
161 | // Add the new vertices | ||
162 | for _, raw := range newVerts.List() { | ||
163 | v := raw.(Vertex) | ||
164 | |||
165 | // Add to the waitgroup so our walk is not done until everything finishes | ||
166 | w.wait.Add(1) | ||
167 | |||
168 | // Add to our own set so we know about it already | ||
169 | log.Printf("[DEBUG] dag/walk: added new vertex: %q", VertexName(v)) | ||
170 | w.vertices.Add(raw) | ||
171 | |||
172 | // Initialize the vertex info | ||
173 | info := &walkerVertex{ | ||
174 | DoneCh: make(chan struct{}), | ||
175 | CancelCh: make(chan struct{}), | ||
176 | deps: make(map[Vertex]chan struct{}), | ||
177 | } | ||
178 | |||
179 | // Add it to the map and kick off the walk | ||
180 | w.vertexMap[v] = info | ||
181 | } | ||
182 | |||
183 | // Remove the old vertices | ||
184 | for _, raw := range oldVerts.List() { | ||
185 | v := raw.(Vertex) | ||
186 | |||
187 | // Get the vertex info so we can cancel it | ||
188 | info, ok := w.vertexMap[v] | ||
189 | if !ok { | ||
190 | // This vertex for some reason was never in our map. This | ||
191 | // shouldn't be possible. | ||
192 | continue | ||
193 | } | ||
194 | |||
195 | // Cancel the vertex | ||
196 | close(info.CancelCh) | ||
197 | |||
198 | // Delete it out of the map | ||
199 | delete(w.vertexMap, v) | ||
200 | |||
201 | log.Printf("[DEBUG] dag/walk: removed vertex: %q", VertexName(v)) | ||
202 | w.vertices.Delete(raw) | ||
203 | } | ||
204 | |||
205 | // Add the new edges | ||
206 | var changedDeps Set | ||
207 | for _, raw := range newEdges.List() { | ||
208 | edge := raw.(Edge) | ||
209 | waiter, dep := w.edgeParts(edge) | ||
210 | |||
211 | // Get the info for the waiter | ||
212 | waiterInfo, ok := w.vertexMap[waiter] | ||
213 | if !ok { | ||
214 | // Vertex doesn't exist... shouldn't be possible but ignore. | ||
215 | continue | ||
216 | } | ||
217 | |||
218 | // Get the info for the dep | ||
219 | depInfo, ok := w.vertexMap[dep] | ||
220 | if !ok { | ||
221 | // Vertex doesn't exist... shouldn't be possible but ignore. | ||
222 | continue | ||
223 | } | ||
224 | |||
225 | // Add the dependency to our waiter | ||
226 | waiterInfo.deps[dep] = depInfo.DoneCh | ||
227 | |||
228 | // Record that the deps changed for this waiter | ||
229 | changedDeps.Add(waiter) | ||
230 | |||
231 | log.Printf( | ||
232 | "[DEBUG] dag/walk: added edge: %q waiting on %q", | ||
233 | VertexName(waiter), VertexName(dep)) | ||
234 | w.edges.Add(raw) | ||
235 | } | ||
236 | |||
237 | // Process reoved edges | ||
238 | for _, raw := range oldEdges.List() { | ||
239 | edge := raw.(Edge) | ||
240 | waiter, dep := w.edgeParts(edge) | ||
241 | |||
242 | // Get the info for the waiter | ||
243 | waiterInfo, ok := w.vertexMap[waiter] | ||
244 | if !ok { | ||
245 | // Vertex doesn't exist... shouldn't be possible but ignore. | ||
246 | continue | ||
247 | } | ||
248 | |||
249 | // Delete the dependency from the waiter | ||
250 | delete(waiterInfo.deps, dep) | ||
251 | |||
252 | // Record that the deps changed for this waiter | ||
253 | changedDeps.Add(waiter) | ||
254 | |||
255 | log.Printf( | ||
256 | "[DEBUG] dag/walk: removed edge: %q waiting on %q", | ||
257 | VertexName(waiter), VertexName(dep)) | ||
258 | w.edges.Delete(raw) | ||
259 | } | ||
260 | |||
261 | // For each vertex with changed dependencies, we need to kick off | ||
262 | // a new waiter and notify the vertex of the changes. | ||
263 | for _, raw := range changedDeps.List() { | ||
264 | v := raw.(Vertex) | ||
265 | info, ok := w.vertexMap[v] | ||
266 | if !ok { | ||
267 | // Vertex doesn't exist... shouldn't be possible but ignore. | ||
268 | continue | ||
269 | } | ||
270 | |||
271 | // Create a new done channel | ||
272 | doneCh := make(chan bool, 1) | ||
273 | |||
274 | // Create the channel we close for cancellation | ||
275 | cancelCh := make(chan struct{}) | ||
276 | |||
277 | // Build a new deps copy | ||
278 | deps := make(map[Vertex]<-chan struct{}) | ||
279 | for k, v := range info.deps { | ||
280 | deps[k] = v | ||
281 | } | ||
282 | |||
283 | // Update the update channel | ||
284 | info.DepsLock.Lock() | ||
285 | if info.DepsUpdateCh != nil { | ||
286 | close(info.DepsUpdateCh) | ||
287 | } | ||
288 | info.DepsCh = doneCh | ||
289 | info.DepsUpdateCh = make(chan struct{}) | ||
290 | info.DepsLock.Unlock() | ||
291 | |||
292 | // Cancel the older waiter | ||
293 | if info.depsCancelCh != nil { | ||
294 | close(info.depsCancelCh) | ||
295 | } | ||
296 | info.depsCancelCh = cancelCh | ||
297 | |||
298 | log.Printf( | ||
299 | "[DEBUG] dag/walk: dependencies changed for %q, sending new deps", | ||
300 | VertexName(v)) | ||
301 | |||
302 | // Start the waiter | ||
303 | go w.waitDeps(v, deps, doneCh, cancelCh) | ||
304 | } | ||
305 | |||
306 | // Start all the new vertices. We do this at the end so that all | ||
307 | // the edge waiters and changes are setup above. | ||
308 | for _, raw := range newVerts.List() { | ||
309 | v := raw.(Vertex) | ||
310 | go w.walkVertex(v, w.vertexMap[v]) | ||
311 | } | ||
312 | } | ||
313 | |||
314 | // edgeParts returns the waiter and the dependency, in that order. | ||
315 | // The waiter is waiting on the dependency. | ||
316 | func (w *Walker) edgeParts(e Edge) (Vertex, Vertex) { | ||
317 | if w.Reverse { | ||
318 | return e.Source(), e.Target() | ||
319 | } | ||
320 | |||
321 | return e.Target(), e.Source() | ||
322 | } | ||
323 | |||
324 | // walkVertex walks a single vertex, waiting for any dependencies before | ||
325 | // executing the callback. | ||
326 | func (w *Walker) walkVertex(v Vertex, info *walkerVertex) { | ||
327 | // When we're done executing, lower the waitgroup count | ||
328 | defer w.wait.Done() | ||
329 | |||
330 | // When we're done, always close our done channel | ||
331 | defer close(info.DoneCh) | ||
332 | |||
333 | // Wait for our dependencies. We create a [closed] deps channel so | ||
334 | // that we can immediately fall through to load our actual DepsCh. | ||
335 | var depsSuccess bool | ||
336 | var depsUpdateCh chan struct{} | ||
337 | depsCh := make(chan bool, 1) | ||
338 | depsCh <- true | ||
339 | close(depsCh) | ||
340 | for { | ||
341 | select { | ||
342 | case <-info.CancelCh: | ||
343 | // Cancel | ||
344 | return | ||
345 | |||
346 | case depsSuccess = <-depsCh: | ||
347 | // Deps complete! Mark as nil to trigger completion handling. | ||
348 | depsCh = nil | ||
349 | |||
350 | case <-depsUpdateCh: | ||
351 | // New deps, reloop | ||
352 | } | ||
353 | |||
354 | // Check if we have updated dependencies. This can happen if the | ||
355 | // dependencies were satisfied exactly prior to an Update occurring. | ||
356 | // In that case, we'd like to take into account new dependencies | ||
357 | // if possible. | ||
358 | info.DepsLock.Lock() | ||
359 | if info.DepsCh != nil { | ||
360 | depsCh = info.DepsCh | ||
361 | info.DepsCh = nil | ||
362 | } | ||
363 | if info.DepsUpdateCh != nil { | ||
364 | depsUpdateCh = info.DepsUpdateCh | ||
365 | } | ||
366 | info.DepsLock.Unlock() | ||
367 | |||
368 | // If we still have no deps channel set, then we're done! | ||
369 | if depsCh == nil { | ||
370 | break | ||
371 | } | ||
372 | } | ||
373 | |||
374 | // If we passed dependencies, we just want to check once more that | ||
375 | // we're not cancelled, since this can happen just as dependencies pass. | ||
376 | select { | ||
377 | case <-info.CancelCh: | ||
378 | // Cancelled during an update while dependencies completed. | ||
379 | return | ||
380 | default: | ||
381 | } | ||
382 | |||
383 | // Run our callback or note that our upstream failed | ||
384 | var err error | ||
385 | if depsSuccess { | ||
386 | log.Printf("[DEBUG] dag/walk: walking %q", VertexName(v)) | ||
387 | err = w.Callback(v) | ||
388 | } else { | ||
389 | log.Printf("[DEBUG] dag/walk: upstream errored, not walking %q", VertexName(v)) | ||
390 | err = errWalkUpstream | ||
391 | } | ||
392 | |||
393 | // Record the error | ||
394 | if err != nil { | ||
395 | w.errLock.Lock() | ||
396 | defer w.errLock.Unlock() | ||
397 | |||
398 | if w.errMap == nil { | ||
399 | w.errMap = make(map[Vertex]error) | ||
400 | } | ||
401 | w.errMap[v] = err | ||
402 | } | ||
403 | } | ||
404 | |||
405 | func (w *Walker) waitDeps( | ||
406 | v Vertex, | ||
407 | deps map[Vertex]<-chan struct{}, | ||
408 | doneCh chan<- bool, | ||
409 | cancelCh <-chan struct{}) { | ||
410 | // For each dependency given to us, wait for it to complete | ||
411 | for dep, depCh := range deps { | ||
412 | DepSatisfied: | ||
413 | for { | ||
414 | select { | ||
415 | case <-depCh: | ||
416 | // Dependency satisfied! | ||
417 | break DepSatisfied | ||
418 | |||
419 | case <-cancelCh: | ||
420 | // Wait cancelled. Note that we didn't satisfy dependencies | ||
421 | // so that anything waiting on us also doesn't run. | ||
422 | doneCh <- false | ||
423 | return | ||
424 | |||
425 | case <-time.After(time.Second * 5): | ||
426 | log.Printf("[DEBUG] dag/walk: vertex %q, waiting for: %q", | ||
427 | VertexName(v), VertexName(dep)) | ||
428 | } | ||
429 | } | ||
430 | } | ||
431 | |||
432 | // Dependencies satisfied! We need to check if any errored | ||
433 | w.errLock.Lock() | ||
434 | defer w.errLock.Unlock() | ||
435 | for dep, _ := range deps { | ||
436 | if w.errMap[dep] != nil { | ||
437 | // One of our dependencies failed, so return false | ||
438 | doneCh <- false | ||
439 | return | ||
440 | } | ||
441 | } | ||
442 | |||
443 | // All dependencies satisfied and successful | ||
444 | doneCh <- true | ||
445 | } | ||