vendor/github.com/hashicorp/terraform/dag/dag.go

   1 package dag
   2
   3 import (
   4         "fmt"
   5         "sort"
   6         "strings"
   7
   8         "github.com/hashicorp/terraform/tfdiags"
   9
  10         "github.com/hashicorp/go-multierror"
  11 )
  12
  13 // AcyclicGraph is a specialization of Graph that cannot have cycles. With
  14 // this property, we get the property of sane graph traversal.
  15 type AcyclicGraph struct {
  16         Graph
  17 }
  18
  19 // WalkFunc is the callback used for walking the graph.
  20 type WalkFunc func(Vertex) tfdiags.Diagnostics
  21
  22 // DepthWalkFunc is a walk function that also receives the current depth of the
  23 // walk as an argument
  24 type DepthWalkFunc func(Vertex, int) error
  25
  26 func (g *AcyclicGraph) DirectedGraph() Grapher {
  27         return g
  28 }
  29
  30 // Returns a Set that includes every Vertex yielded by walking down from the
  31 // provided starting Vertex v.
  32 func (g *AcyclicGraph) Ancestors(v Vertex) (*Set, error) {
  33         s := new(Set)
  34         start := AsVertexList(g.DownEdges(v))
  35         memoFunc := func(v Vertex, d int) error {
  36                 s.Add(v)
  37                 return nil
  38         }
  39
  40         if err := g.DepthFirstWalk(start, memoFunc); err != nil {
  41                 return nil, err
  42         }
  43
  44         return s, nil
  45 }
  46
  47 // Returns a Set that includes every Vertex yielded by walking up from the
  48 // provided starting Vertex v.
  49 func (g *AcyclicGraph) Descendents(v Vertex) (*Set, error) {
  50         s := new(Set)
  51         start := AsVertexList(g.UpEdges(v))
  52         memoFunc := func(v Vertex, d int) error {
  53                 s.Add(v)
  54                 return nil
  55         }
  56
  57         if err := g.ReverseDepthFirstWalk(start, memoFunc); err != nil {
  58                 return nil, err
  59         }
  60
  61         return s, nil
  62 }
  63
  64 // Root returns the root of the DAG, or an error.
  65 //
  66 // Complexity: O(V)
  67 func (g *AcyclicGraph) Root() (Vertex, error) {
  68         roots := make([]Vertex, 0, 1)
  69         for _, v := range g.Vertices() {
  70                 if g.UpEdges(v).Len() == 0 {
  71                         roots = append(roots, v)
  72                 }
  73         }
  74
  75         if len(roots) > 1 {
  76                 // TODO(mitchellh): make this error message a lot better
  77                 return nil, fmt.Errorf("multiple roots: %#v", roots)
  78         }
  79
  80         if len(roots) == 0 {
  81                 return nil, fmt.Errorf("no roots found")
  82         }
  83
  84         return roots[0], nil
  85 }
  86
  87 // TransitiveReduction performs the transitive reduction of graph g in place.
  88 // The transitive reduction of a graph is a graph with as few edges as
  89 // possible with the same reachability as the original graph. This means
  90 // that if there are three nodes A => B => C, and A connects to both
  91 // B and C, and B connects to C, then the transitive reduction is the
  92 // same graph with only a single edge between A and B, and a single edge
  93 // between B and C.
  94 //
  95 // The graph must be valid for this operation to behave properly. If
  96 // Validate() returns an error, the behavior is undefined and the results
  97 // will likely be unexpected.
  98 //
  99 // Complexity: O(V(V+E)), or asymptotically O(VE)
 100 func (g *AcyclicGraph) TransitiveReduction() {
 101         // For each vertex u in graph g, do a DFS starting from each vertex
 102         // v such that the edge (u,v) exists (v is a direct descendant of u).
 103         //
 104         // For each v-prime reachable from v, remove the edge (u, v-prime).
 105         defer g.debug.BeginOperation("TransitiveReduction", "").End("")
 106
 107         for _, u := range g.Vertices() {
 108                 uTargets := g.DownEdges(u)
 109                 vs := AsVertexList(g.DownEdges(u))
 110
 111                 g.depthFirstWalk(vs, false, func(v Vertex, d int) error {
 112                         shared := uTargets.Intersection(g.DownEdges(v))
 113                         for _, vPrime := range AsVertexList(shared) {
 114                                 g.RemoveEdge(BasicEdge(u, vPrime))
 115                         }
 116
 117                         return nil
 118                 })
 119         }
 120 }
 121
 122 // Validate validates the DAG. A DAG is valid if it has a single root
 123 // with no cycles.
 124 func (g *AcyclicGraph) Validate() error {
 125         if _, err := g.Root(); err != nil {
 126                 return err
 127         }
 128
 129         // Look for cycles of more than 1 component
 130         var err error
 131         cycles := g.Cycles()
 132         if len(cycles) > 0 {
 133                 for _, cycle := range cycles {
 134                         cycleStr := make([]string, len(cycle))
 135                         for j, vertex := range cycle {
 136                                 cycleStr[j] = VertexName(vertex)
 137                         }
 138
 139                         err = multierror.Append(err, fmt.Errorf(
 140                                 "Cycle: %s", strings.Join(cycleStr, ", ")))
 141                 }
 142         }
 143
 144         // Look for cycles to self
 145         for _, e := range g.Edges() {
 146                 if e.Source() == e.Target() {
 147                         err = multierror.Append(err, fmt.Errorf(
 148                                 "Self reference: %s", VertexName(e.Source())))
 149                 }
 150         }
 151
 152         return err
 153 }
 154
 155 func (g *AcyclicGraph) Cycles() [][]Vertex {
 156         var cycles [][]Vertex
 157         for _, cycle := range StronglyConnected(&g.Graph) {
 158                 if len(cycle) > 1 {
 159                         cycles = append(cycles, cycle)
 160                 }
 161         }
 162         return cycles
 163 }
 164
 165 // Walk walks the graph, calling your callback as each node is visited.
 166 // This will walk nodes in parallel if it can. The resulting diagnostics
 167 // contains problems from all graphs visited, in no particular order.
 168 func (g *AcyclicGraph) Walk(cb WalkFunc) tfdiags.Diagnostics {
 169         defer g.debug.BeginOperation(typeWalk, "").End("")
 170
 171         w := &Walker{Callback: cb, Reverse: true}
 172         w.Update(g)
 173         return w.Wait()
 174 }
 175
 176 // simple convenience helper for converting a dag.Set to a []Vertex
 177 func AsVertexList(s *Set) []Vertex {
 178         rawList := s.List()
 179         vertexList := make([]Vertex, len(rawList))
 180         for i, raw := range rawList {
 181                 vertexList[i] = raw.(Vertex)
 182         }
 183         return vertexList
 184 }
 185
 186 type vertexAtDepth struct {
 187         Vertex Vertex
 188         Depth  int
 189 }
 190
 191 // depthFirstWalk does a depth-first walk of the graph starting from
 192 // the vertices in start.
 193 func (g *AcyclicGraph) DepthFirstWalk(start []Vertex, f DepthWalkFunc) error {
 194         return g.depthFirstWalk(start, true, f)
 195 }
 196
 197 // This internal method provides the option of not sorting the vertices during
 198 // the walk, which we use for the Transitive reduction.
 199 // Some configurations can lead to fully-connected subgraphs, which makes our
 200 // transitive reduction algorithm O(n^3). This is still passable for the size
 201 // of our graphs, but the additional n^2 sort operations would make this
 202 // uncomputable in a reasonable amount of time.
 203 func (g *AcyclicGraph) depthFirstWalk(start []Vertex, sorted bool, f DepthWalkFunc) error {
 204         defer g.debug.BeginOperation(typeDepthFirstWalk, "").End("")
 205
 206         seen := make(map[Vertex]struct{})
 207         frontier := make([]*vertexAtDepth, len(start))
 208         for i, v := range start {
 209                 frontier[i] = &vertexAtDepth{
 210                         Vertex: v,
 211                         Depth:  0,
 212                 }
 213         }
 214         for len(frontier) > 0 {
 215                 // Pop the current vertex
 216                 n := len(frontier)
 217                 current := frontier[n-1]
 218                 frontier = frontier[:n-1]
 219
 220                 // Check if we've seen this already and return...
 221                 if _, ok := seen[current.Vertex]; ok {
 222                         continue
 223                 }
 224                 seen[current.Vertex] = struct{}{}
 225
 226                 // Visit the current node
 227                 if err := f(current.Vertex, current.Depth); err != nil {
 228                         return err
 229                 }
 230
 231                 // Visit targets of this in a consistent order.
 232                 targets := AsVertexList(g.DownEdges(current.Vertex))
 233
 234                 if sorted {
 235                         sort.Sort(byVertexName(targets))
 236                 }
 237
 238                 for _, t := range targets {
 239                         frontier = append(frontier, &vertexAtDepth{
 240                                 Vertex: t,
 241                                 Depth:  current.Depth + 1,
 242                         })
 243                 }
 244         }
 245
 246         return nil
 247 }
 248
 249 // reverseDepthFirstWalk does a depth-first walk _up_ the graph starting from
 250 // the vertices in start.
 251 func (g *AcyclicGraph) ReverseDepthFirstWalk(start []Vertex, f DepthWalkFunc) error {
 252         defer g.debug.BeginOperation(typeReverseDepthFirstWalk, "").End("")
 253
 254         seen := make(map[Vertex]struct{})
 255         frontier := make([]*vertexAtDepth, len(start))
 256         for i, v := range start {
 257                 frontier[i] = &vertexAtDepth{
 258                         Vertex: v,
 259                         Depth:  0,
 260                 }
 261         }
 262         for len(frontier) > 0 {
 263                 // Pop the current vertex
 264                 n := len(frontier)
 265                 current := frontier[n-1]
 266                 frontier = frontier[:n-1]
 267
 268                 // Check if we've seen this already and return...
 269                 if _, ok := seen[current.Vertex]; ok {
 270                         continue
 271                 }
 272                 seen[current.Vertex] = struct{}{}
 273
 274                 // Add next set of targets in a consistent order.
 275                 targets := AsVertexList(g.UpEdges(current.Vertex))
 276                 sort.Sort(byVertexName(targets))
 277                 for _, t := range targets {
 278                         frontier = append(frontier, &vertexAtDepth{
 279                                 Vertex: t,
 280                                 Depth:  current.Depth + 1,
 281                         })
 282                 }
 283
 284                 // Visit the current node
 285                 if err := f(current.Vertex, current.Depth); err != nil {
 286                         return err
 287                 }
 288         }
 289
 290         return nil
 291 }
 292
 293 // byVertexName implements sort.Interface so a list of Vertices can be sorted
 294 // consistently by their VertexName
 295 type byVertexName []Vertex
 296
 297 func (b byVertexName) Len() int      { return len(b) }
 298 func (b byVertexName) Swap(i, j int) { b[i], b[j] = b[j], b[i] }
 299 func (b byVertexName) Less(i, j int) bool {
 300         return VertexName(b[i]) < VertexName(b[j])
 301 }