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

   1 package dag
   2
   3 import (
   4         "encoding/json"
   5         "fmt"
   6         "io"
   7         "log"
   8         "reflect"
   9         "sort"
  10         "strconv"
  11         "sync"
  12 )
  13
  14 const (
  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.
  27 type 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.
  58 func (g *marshalGraph) add(v *marshalVertex) {
  59         g.Vertices = append(g.Vertices, v)
  60         sort.Sort(vertices(g.Vertices))
  61 }
  62
  63 func (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
  72 func (g *marshalGraph) connect(e *marshalEdge) {
  73         g.Edges = append(g.Edges, e)
  74         sort.Sort(edges(g.Edges))
  75 }
  76
  77 func (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
  86 func (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
  95 type 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
 109 func 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
 124 type vertices []*marshalVertex
 125
 126 func (v vertices) Less(i, j int) bool { return v[i].Name < v[j].Name }
 127 func (v vertices) Len() int           { return len(v) }
 128 func (v vertices) Swap(i, j int)      { v[i], v[j] = v[j], v[i] }
 129
 130 type 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
 141 func 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
 151 type edges []*marshalEdge
 152
 153 func (e edges) Less(i, j int) bool { return e[i].Name < e[j].Name }
 154 func (e edges) Len() int           { return len(e) }
 155 func (e edges) Swap(i, j int)      { e[i], e[j] = e[j], e[i] }
 156
 157 // build a marshalGraph structure from a *Graph
 158 func 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.
 198 func 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.
 222 func 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.
 240 type DebugOperationEnd func(string)
 241
 242 // End calls function e with the info parameter, marking the end of this
 243 // operation in the logs.
 244 func (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
 248 type encoder struct {
 249         sync.Mutex
 250         w io.Writer
 251 }
 252
 253 // Encode is analogous to json.Encoder.Encode
 254 func (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
 275 func (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.
 283 func (e *encoder) Remove(v Vertex) {
 284         e.Encode(marshalTransform{
 285                 Type:         typeTransform,
 286                 RemoveVertex: newMarshalVertex(v),
 287         })
 288 }
 289
 290 func (e *encoder) Connect(edge Edge) {
 291         e.Encode(marshalTransform{
 292                 Type:    typeTransform,
 293                 AddEdge: newMarshalEdge(edge),
 294         })
 295 }
 296
 297 func (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.
 306 func (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
 327 type 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
 336 func (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.
 351 type streamDecode struct {
 352         Type string
 353         Map  map[string]interface{}
 354         JSON []byte
 355 }
 356
 357 func (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.
 373 type 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.
 381 func 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.
 419 type marshalVertexInfo struct {
 420         Type   string
 421         Vertex *marshalVertex
 422         Info   string
 423 }
 424
 425 func 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.
 436 type marshalEdgeInfo struct {
 437         Type string
 438         Edge *marshalEdge
 439         Info string
 440 }
 441
 442 func 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.
 455 func 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 }