aboutsummaryrefslogtreecommitdiffhomepage
path: root/vendor/github.com/hashicorp/terraform/dag
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/hashicorp/terraform/dag')
-rw-r--r--vendor/github.com/hashicorp/terraform/dag/dag.go286
-rw-r--r--vendor/github.com/hashicorp/terraform/dag/dot.go282
-rw-r--r--vendor/github.com/hashicorp/terraform/dag/edge.go37
-rw-r--r--vendor/github.com/hashicorp/terraform/dag/graph.go391
-rw-r--r--vendor/github.com/hashicorp/terraform/dag/marshal.go462
-rw-r--r--vendor/github.com/hashicorp/terraform/dag/set.go109
-rw-r--r--vendor/github.com/hashicorp/terraform/dag/tarjan.go107
-rw-r--r--vendor/github.com/hashicorp/terraform/dag/walk.go445
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 @@
1package dag
2
3import (
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.
13type AcyclicGraph struct {
14 Graph
15}
16
17// WalkFunc is the callback used for walking the graph.
18type WalkFunc func(Vertex) error
19
20// DepthWalkFunc is a walk function that also receives the current depth of the
21// walk as an argument
22type DepthWalkFunc func(Vertex, int) error
23
24func (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.
30func (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.
47func (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)
65func (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)
98func (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.
122func (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
153func (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.
166func (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
175func 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
184type 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.
192func (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.
236func (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
280type byVertexName []Vertex
281
282func (b byVertexName) Len() int { return len(b) }
283func (b byVertexName) Swap(i, j int) { b[i], b[j] = b[j], b[i] }
284func (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 @@
1package dag
2
3import (
4 "bytes"
5 "fmt"
6 "sort"
7 "strings"
8)
9
10// DotOpts are the options for generating a dot formatted Graph.
11type 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.
29type 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.
39type DotNode struct {
40 Name string
41 Attrs map[string]string
42}
43
44// Returns the DOT representation of this Graph.
45func (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
82func (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
116func (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
132func 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.
138func (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
158func (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
224func 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
232func 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.
243type indentWriter struct {
244 bytes.Buffer
245 level int
246}
247
248func (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
259func (w *indentWriter) Indent() { w.level++ }
260
261// Unindent decreases indentation by 1
262func (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.
266func (w *indentWriter) Write(b []byte) (int, error) {
267 w.indent()
268 return w.Buffer.Write(b)
269}
270
271func (w *indentWriter) WriteString(s string) (int, error) {
272 w.indent()
273 return w.Buffer.WriteString(s)
274}
275func (w *indentWriter) WriteByte(b byte) error {
276 w.indent()
277 return w.Buffer.WriteByte(b)
278}
279func (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 @@
1package dag
2
3import (
4 "fmt"
5)
6
7// Edge represents an edge in the graph, with a source and target vertex.
8type 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.
17func 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.
23type basicEdge struct {
24 S, T Vertex
25}
26
27func (e *basicEdge) Hashcode() interface{} {
28 return fmt.Sprintf("%p-%p", e.S, e.T)
29}
30
31func (e *basicEdge) Source() Vertex {
32 return e.S
33}
34
35func (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 @@
1package dag
2
3import (
4 "bytes"
5 "encoding/json"
6 "fmt"
7 "io"
8 "sort"
9)
10
11// Graph is used to represent a dependency graph.
12type 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.
23type 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.
30type Grapher interface {
31 DirectedGraph() Grapher
32}
33
34// Vertex of the graph.
35type 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.
39type NamedVertex interface {
40 Vertex
41 Name() string
42}
43
44func (g *Graph) DirectedGraph() Grapher {
45 return g
46}
47
48// Vertices returns the list of all the vertices in the graph.
49func (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.
60func (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.
71func (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.
84func (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.
97func (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.
102func (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.
108func (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.
117func (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.
136func (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.
165func (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.
182func (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.
188func (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.
197func (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.
232func (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.
274func (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
312func (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.
328func (g *Graph) Dot(opts *DotOpts) []byte {
329 return newMarshalGraph("", g).Dot(opts)
330}
331
332// MarshalJSON returns a JSON representation of the entire Graph.
333func (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.
341func (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.
348func (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.
355func (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.
361func (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.
377func (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.
382func 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 @@
1package dag
2
3import (
4 "encoding/json"
5 "fmt"
6 "io"
7 "log"
8 "reflect"
9 "sort"
10 "strconv"
11 "sync"
12)
13
14const (
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.
27type 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.
58func (g *marshalGraph) add(v *marshalVertex) {
59 g.Vertices = append(g.Vertices, v)
60 sort.Sort(vertices(g.Vertices))
61}
62
63func (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
72func (g *marshalGraph) connect(e *marshalEdge) {
73 g.Edges = append(g.Edges, e)
74 sort.Sort(edges(g.Edges))
75}
76
77func (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
86func (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
95type 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
109func 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
124type vertices []*marshalVertex
125
126func (v vertices) Less(i, j int) bool { return v[i].Name < v[j].Name }
127func (v vertices) Len() int { return len(v) }
128func (v vertices) Swap(i, j int) { v[i], v[j] = v[j], v[i] }
129
130type 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
141func 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
151type edges []*marshalEdge
152
153func (e edges) Less(i, j int) bool { return e[i].Name < e[j].Name }
154func (e edges) Len() int { return len(e) }
155func (e edges) Swap(i, j int) { e[i], e[j] = e[j], e[i] }
156
157// build a marshalGraph structure from a *Graph
158func 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.
198func 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.
222func 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.
240type DebugOperationEnd func(string)
241
242// End calls function e with the info parameter, marking the end of this
243// operation in the logs.
244func (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
248type encoder struct {
249 sync.Mutex
250 w io.Writer
251}
252
253// Encode is analogous to json.Encoder.Encode
254func (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
275func (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.
283func (e *encoder) Remove(v Vertex) {
284 e.Encode(marshalTransform{
285 Type: typeTransform,
286 RemoveVertex: newMarshalVertex(v),
287 })
288}
289
290func (e *encoder) Connect(edge Edge) {
291 e.Encode(marshalTransform{
292 Type: typeTransform,
293 AddEdge: newMarshalEdge(edge),
294 })
295}
296
297func (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.
306func (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
327type 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
336func (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.
351type streamDecode struct {
352 Type string
353 Map map[string]interface{}
354 JSON []byte
355}
356
357func (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.
373type 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.
381func 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.
419type marshalVertexInfo struct {
420 Type string
421 Vertex *marshalVertex
422 Info string
423}
424
425func 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.
436type marshalEdgeInfo struct {
437 Type string
438 Edge *marshalEdge
439 Info string
440}
441
442func 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.
455func 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 @@
1package dag
2
3import (
4 "sync"
5)
6
7// Set is a set data structure.
8type 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.
16type Hashable interface {
17 Hashcode() interface{}
18}
19
20// hashcode returns the hashcode used for set elements.
21func 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
30func (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.
36func (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.
42func (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.
49func (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.
67func (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.
85func (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.
94func (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
107func (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 @@
1package 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.
7func 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
22func 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
58func 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
67type 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
75func (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
84func (s *sccAcct) push(n Vertex) {
85 s.Stack = append(s.Stack, n)
86}
87
88// pop removes a vertex from the stack
89func (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
100func (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 @@
1package dag
2
3import (
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.
37type 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
63type 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.
99var 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.
108func (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.
138func (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.
316func (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.
326func (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
405func (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}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-18 14:41:13 +0000