3 files changed, 37 insertions, 12 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() {
                 uTargets := g.DownEdges(u)
                 vs := AsVertexList(g.DownEdges(u))
 
-                g.DepthFirstWalk(vs, func(v Vertex, d int) error {
+                g.depthFirstWalk(vs, false, func(v Vertex, d int) error {
                         shared := uTargets.Intersection(g.DownEdges(v))
                         for _, vPrime := range AsVertexList(shared) {
                                 g.RemoveEdge(BasicEdge(u, vPrime))
@@ -187,9 +187,18 @@ type vertexAtDepth struct {
 }
 
 // depthFirstWalk does a depth-first walk of the graph starting from
-// the vertices in start. This is not exported now but it would make sense
-// to export this publicly at some point.
+// the vertices in start.
 func (g *AcyclicGraph) DepthFirstWalk(start []Vertex, f DepthWalkFunc) error {
+        return g.depthFirstWalk(start, true, f)
+}
+
+// This internal method provides the option of not sorting the vertices during
+// the walk, which we use for the Transitive reduction.
+// Some configurations can lead to fully-connected subgraphs, which makes our
+// transitive reduction algorithm O(n^3). This is still passable for the size
+// of our graphs, but the additional n^2 sort operations would make this
+// uncomputable in a reasonable amount of time.
+func (g *AcyclicGraph) depthFirstWalk(start []Vertex, sorted bool, f DepthWalkFunc) error {
         defer g.debug.BeginOperation(typeDepthFirstWalk, "").End("")
 
         seen := make(map[Vertex]struct{})
@@ -219,7 +228,11 @@ func (g *AcyclicGraph) DepthFirstWalk(start []Vertex, f DepthWalkFunc) error {
 
                 // Visit targets of this in a consistent order.
                 targets := AsVertexList(g.DownEdges(current.Vertex))
-                sort.Sort(byVertexName(targets))
+
+                if sorted {
+                        sort.Sort(byVertexName(targets))
+                }
+
                 for _, t := range targets {
                         frontier = append(frontier, &vertexAtDepth{
                                 Vertex: t,
diff --git a/vendor/github.com/hashicorp/terraform/dag/marshal.go b/vendor/github.com/hashicorp/terraform/dag/marshal.go
index 16d5dd6..c567d27 100644
--- a/vendor/github.com/hashicorp/terraform/dag/marshal.go
+++ b/vendor/github.com/hashicorp/terraform/dag/marshal.go
@@ -273,6 +273,9 @@ func (e *encoder) Encode(i interface{}) {
 }
 
 func (e *encoder) Add(v Vertex) {
+        if e == nil {
+                return
+        }
         e.Encode(marshalTransform{
                 Type:      typeTransform,
                 AddVertex: newMarshalVertex(v),
@@ -281,6 +284,9 @@ func (e *encoder) Add(v Vertex) {
 
 // Remove records the removal of Vertex v.
 func (e *encoder) Remove(v Vertex) {
+        if e == nil {
+                return
+        }
         e.Encode(marshalTransform{
                 Type:         typeTransform,
                 RemoveVertex: newMarshalVertex(v),
@@ -288,6 +294,9 @@ func (e *encoder) Remove(v Vertex) {
 }
 
 func (e *encoder) Connect(edge Edge) {
+        if e == nil {
+                return
+        }
         e.Encode(marshalTransform{
                 Type:    typeTransform,
                 AddEdge: newMarshalEdge(edge),
@@ -295,6 +304,9 @@ func (e *encoder) Connect(edge Edge) {
 }
 
 func (e *encoder) RemoveEdge(edge Edge) {
+        if e == nil {
+                return
+        }
         e.Encode(marshalTransform{
                 Type:       typeTransform,
                 RemoveEdge: newMarshalEdge(edge),
diff --git a/vendor/github.com/hashicorp/terraform/dag/walk.go b/vendor/github.com/hashicorp/terraform/dag/walk.go
index 23c87ad..f03b100 100644
--- a/vendor/github.com/hashicorp/terraform/dag/walk.go
+++ b/vendor/github.com/hashicorp/terraform/dag/walk.go
@@ -166,7 +166,7 @@ func (w *Walker) Update(g *AcyclicGraph) {
                 w.wait.Add(1)
 
                 // Add to our own set so we know about it already
-                log.Printf("[DEBUG] dag/walk: added new vertex: %q", VertexName(v))
+                log.Printf("[TRACE] dag/walk: added new vertex: %q", VertexName(v))
                 w.vertices.Add(raw)
 
                 // Initialize the vertex info
@@ -198,7 +198,7 @@ func (w *Walker) Update(g *AcyclicGraph) {
                 // Delete it out of the map
                 delete(w.vertexMap, v)
 
-                log.Printf("[DEBUG] dag/walk: removed vertex: %q", VertexName(v))
+                log.Printf("[TRACE] dag/walk: removed vertex: %q", VertexName(v))
                 w.vertices.Delete(raw)
         }
 
@@ -229,7 +229,7 @@ func (w *Walker) Update(g *AcyclicGraph) {
                 changedDeps.Add(waiter)
 
                 log.Printf(
-                        "[DEBUG] dag/walk: added edge: %q waiting on %q",
+                        "[TRACE] dag/walk: added edge: %q waiting on %q",
                         VertexName(waiter), VertexName(dep))
                 w.edges.Add(raw)
         }
@@ -253,7 +253,7 @@ func (w *Walker) Update(g *AcyclicGraph) {
                 changedDeps.Add(waiter)
 
                 log.Printf(
-                        "[DEBUG] dag/walk: removed edge: %q waiting on %q",
+                        "[TRACE] dag/walk: removed edge: %q waiting on %q",
                         VertexName(waiter), VertexName(dep))
                 w.edges.Delete(raw)
         }
@@ -296,7 +296,7 @@ func (w *Walker) Update(g *AcyclicGraph) {
                 info.depsCancelCh = cancelCh
 
                 log.Printf(
-                        "[DEBUG] dag/walk: dependencies changed for %q, sending new deps",
+                        "[TRACE] dag/walk: dependencies changed for %q, sending new deps",
                         VertexName(v))
 
                 // Start the waiter
@@ -383,10 +383,10 @@ func (w *Walker) walkVertex(v Vertex, info *walkerVertex) {
         // Run our callback or note that our upstream failed
         var err error
         if depsSuccess {
-                log.Printf("[DEBUG] dag/walk: walking %q", VertexName(v))
+                log.Printf("[TRACE] dag/walk: walking %q", VertexName(v))
                 err = w.Callback(v)
         } else {
-                log.Printf("[DEBUG] dag/walk: upstream errored, not walking %q", VertexName(v))
+                log.Printf("[TRACE] dag/walk: upstream errored, not walking %q", VertexName(v))
                 err = errWalkUpstream
         }
 
@@ -423,7 +423,7 @@ func (w *Walker) waitDeps(
                                 return
 
                         case <-time.After(time.Second * 5):
-                                log.Printf("[DEBUG] dag/walk: vertex %q, waiting for: %q",
+                                log.Printf("[TRACE] dag/walk: vertex %q, waiting for: %q",
                                         VertexName(v), VertexName(dep))
                         }
                 }