diff options
Diffstat (limited to 'vendor/github.com/hashicorp/terraform/dag/dag.go')
-rw-r--r-- | vendor/github.com/hashicorp/terraform/dag/dag.go | 286 |
1 files changed, 286 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 | } | ||