diff options
Diffstat (limited to 'vendor/github.com/hashicorp/terraform/dag/dag.go')
-rw-r--r-- | vendor/github.com/hashicorp/terraform/dag/dag.go | 21 |
1 files changed, 17 insertions, 4 deletions
diff --git a/vendor/github.com/hashicorp/terraform/dag/dag.go b/vendor/github.com/hashicorp/terraform/dag/dag.go index f8776bc..b7eb10c 100644 --- a/vendor/github.com/hashicorp/terraform/dag/dag.go +++ b/vendor/github.com/hashicorp/terraform/dag/dag.go | |||
@@ -106,7 +106,7 @@ func (g *AcyclicGraph) TransitiveReduction() { | |||
106 | uTargets := g.DownEdges(u) | 106 | uTargets := g.DownEdges(u) |
107 | vs := AsVertexList(g.DownEdges(u)) | 107 | vs := AsVertexList(g.DownEdges(u)) |
108 | 108 | ||
109 | g.DepthFirstWalk(vs, func(v Vertex, d int) error { | 109 | g.depthFirstWalk(vs, false, func(v Vertex, d int) error { |
110 | shared := uTargets.Intersection(g.DownEdges(v)) | 110 | shared := uTargets.Intersection(g.DownEdges(v)) |
111 | for _, vPrime := range AsVertexList(shared) { | 111 | for _, vPrime := range AsVertexList(shared) { |
112 | g.RemoveEdge(BasicEdge(u, vPrime)) | 112 | g.RemoveEdge(BasicEdge(u, vPrime)) |
@@ -187,9 +187,18 @@ type vertexAtDepth struct { | |||
187 | } | 187 | } |
188 | 188 | ||
189 | // depthFirstWalk does a depth-first walk of the graph starting from | 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 | 190 | // the vertices in start. |
191 | // to export this publicly at some point. | ||
192 | func (g *AcyclicGraph) DepthFirstWalk(start []Vertex, f DepthWalkFunc) error { | 191 | func (g *AcyclicGraph) DepthFirstWalk(start []Vertex, f DepthWalkFunc) error { |
192 | return g.depthFirstWalk(start, true, f) | ||
193 | } | ||
194 | |||
195 | // This internal method provides the option of not sorting the vertices during | ||
196 | // the walk, which we use for the Transitive reduction. | ||
197 | // Some configurations can lead to fully-connected subgraphs, which makes our | ||
198 | // transitive reduction algorithm O(n^3). This is still passable for the size | ||
199 | // of our graphs, but the additional n^2 sort operations would make this | ||
200 | // uncomputable in a reasonable amount of time. | ||
201 | func (g *AcyclicGraph) depthFirstWalk(start []Vertex, sorted bool, f DepthWalkFunc) error { | ||
193 | defer g.debug.BeginOperation(typeDepthFirstWalk, "").End("") | 202 | defer g.debug.BeginOperation(typeDepthFirstWalk, "").End("") |
194 | 203 | ||
195 | seen := make(map[Vertex]struct{}) | 204 | seen := make(map[Vertex]struct{}) |
@@ -219,7 +228,11 @@ func (g *AcyclicGraph) DepthFirstWalk(start []Vertex, f DepthWalkFunc) error { | |||
219 | 228 | ||
220 | // Visit targets of this in a consistent order. | 229 | // Visit targets of this in a consistent order. |
221 | targets := AsVertexList(g.DownEdges(current.Vertex)) | 230 | targets := AsVertexList(g.DownEdges(current.Vertex)) |
222 | sort.Sort(byVertexName(targets)) | 231 | |
232 | if sorted { | ||
233 | sort.Sort(byVertexName(targets)) | ||
234 | } | ||
235 | |||
223 | for _, t := range targets { | 236 | for _, t := range targets { |
224 | frontier = append(frontier, &vertexAtDepth{ | 237 | frontier = append(frontier, &vertexAtDepth{ |
225 | Vertex: t, | 238 | Vertex: t, |