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/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 }