1package dag 2 3import ( 4 "encoding/json" 5 "fmt" 6 "io" 7 "log" 8 "reflect" 9 "sort" 10 "strconv" 11 "sync" 12) 13 14const ( 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. 27type 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. 58func (g *marshalGraph) add(v *marshalVertex) { 59 g.Vertices = append(g.Vertices, v) 60 sort.Sort(vertices(g.Vertices)) 61} 62 63func (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 72func (g *marshalGraph) connect(e *marshalEdge) { 73 g.Edges = append(g.Edges, e) 74 sort.Sort(edges(g.Edges)) 75} 76 77func (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 86func (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 95type 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 109func 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 124type vertices []*marshalVertex 125 126func (v vertices) Less(i, j int) bool { return v[i].Name < v[j].Name } 127func (v vertices) Len() int { return len(v) } 128func (v vertices) Swap(i, j int) { v[i], v[j] = v[j], v[i] } 129 130type 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 141func 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 151type edges []*marshalEdge 152 153func (e edges) Less(i, j int) bool { return e[i].Name < e[j].Name } 154func (e edges) Len() int { return len(e) } 155func (e edges) Swap(i, j int) { e[i], e[j] = e[j], e[i] } 156 157// build a marshalGraph structure from a *Graph 158func 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. 198func 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. 222func 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. 240type DebugOperationEnd func(string) 241 242// End calls function e with the info parameter, marking the end of this 243// operation in the logs. 244func (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 248type encoder struct { 249 sync.Mutex 250 w io.Writer 251} 252 253// Encode is analogous to json.Encoder.Encode 254func (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 275func (e *encoder) Add(v Vertex) { 276 if e == nil { 277 return 278 } 279 e.Encode(marshalTransform{ 280 Type: typeTransform, 281 AddVertex: newMarshalVertex(v), 282 }) 283} 284 285// Remove records the removal of Vertex v. 286func (e *encoder) Remove(v Vertex) { 287 if e == nil { 288 return 289 } 290 e.Encode(marshalTransform{ 291 Type: typeTransform, 292 RemoveVertex: newMarshalVertex(v), 293 }) 294} 295 296func (e *encoder) Connect(edge Edge) { 297 if e == nil { 298 return 299 } 300 e.Encode(marshalTransform{ 301 Type: typeTransform, 302 AddEdge: newMarshalEdge(edge), 303 }) 304} 305 306func (e *encoder) RemoveEdge(edge Edge) { 307 if e == nil { 308 return 309 } 310 e.Encode(marshalTransform{ 311 Type: typeTransform, 312 RemoveEdge: newMarshalEdge(edge), 313 }) 314} 315 316// BeginOperation marks the start of set of graph transformations, and returns 317// an EndDebugOperation func to be called once the opration is complete. 318func (e *encoder) BeginOperation(op string, info string) DebugOperationEnd { 319 if e == nil { 320 return func(string) {} 321 } 322 323 e.Encode(marshalOperation{ 324 Type: typeOperation, 325 Begin: op, 326 Info: info, 327 }) 328 329 return func(info string) { 330 e.Encode(marshalOperation{ 331 Type: typeOperation, 332 End: op, 333 Info: info, 334 }) 335 } 336} 337 338// structure for recording graph transformations 339type marshalTransform struct { 340 // Type: "Transform" 341 Type string 342 AddEdge *marshalEdge `json:",omitempty"` 343 RemoveEdge *marshalEdge `json:",omitempty"` 344 AddVertex *marshalVertex `json:",omitempty"` 345 RemoveVertex *marshalVertex `json:",omitempty"` 346} 347 348func (t marshalTransform) Transform(g *marshalGraph) { 349 switch { 350 case t.AddEdge != nil: 351 g.connect(t.AddEdge) 352 case t.RemoveEdge != nil: 353 g.removeEdge(t.RemoveEdge) 354 case t.AddVertex != nil: 355 g.add(t.AddVertex) 356 case t.RemoveVertex != nil: 357 g.remove(t.RemoveVertex) 358 } 359} 360 361// this structure allows us to decode any object in the json stream for 362// inspection, then re-decode it into a proper struct if needed. 363type streamDecode struct { 364 Type string 365 Map map[string]interface{} 366 JSON []byte 367} 368 369func (s *streamDecode) UnmarshalJSON(d []byte) error { 370 s.JSON = d 371 err := json.Unmarshal(d, &s.Map) 372 if err != nil { 373 return err 374 } 375 376 if t, ok := s.Map["Type"]; ok { 377 s.Type, _ = t.(string) 378 } 379 return nil 380} 381 382// structure for recording the beginning and end of any multi-step 383// transformations. These are informational, and not required to reproduce the 384// graph state. 385type marshalOperation struct { 386 Type string 387 Begin string `json:",omitempty"` 388 End string `json:",omitempty"` 389 Info string `json:",omitempty"` 390} 391 392// decodeGraph decodes a marshalGraph from an encoded graph stream. 393func decodeGraph(r io.Reader) (*marshalGraph, error) { 394 dec := json.NewDecoder(r) 395 396 // a stream should always start with a graph 397 g := &marshalGraph{} 398 399 err := dec.Decode(g) 400 if err != nil { 401 return nil, err 402 } 403 404 // now replay any operations that occurred on the original graph 405 for dec.More() { 406 s := &streamDecode{} 407 err := dec.Decode(s) 408 if err != nil { 409 return g, err 410 } 411 412 // the only Type we're concerned with here is Transform to complete the 413 // Graph 414 if s.Type != typeTransform { 415 continue 416 } 417 418 t := &marshalTransform{} 419 err = json.Unmarshal(s.JSON, t) 420 if err != nil { 421 return g, err 422 } 423 t.Transform(g) 424 } 425 return g, nil 426} 427 428// marshalVertexInfo allows encoding arbitrary information about the a single 429// Vertex in the logs. These are accumulated for informational display while 430// rebuilding the graph. 431type marshalVertexInfo struct { 432 Type string 433 Vertex *marshalVertex 434 Info string 435} 436 437func newVertexInfo(infoType string, v Vertex, info string) *marshalVertexInfo { 438 return &marshalVertexInfo{ 439 Type: infoType, 440 Vertex: newMarshalVertex(v), 441 Info: info, 442 } 443} 444 445// marshalEdgeInfo allows encoding arbitrary information about the a single 446// Edge in the logs. These are accumulated for informational display while 447// rebuilding the graph. 448type marshalEdgeInfo struct { 449 Type string 450 Edge *marshalEdge 451 Info string 452} 453 454func newEdgeInfo(infoType string, e Edge, info string) *marshalEdgeInfo { 455 return &marshalEdgeInfo{ 456 Type: infoType, 457 Edge: newMarshalEdge(e), 458 Info: info, 459 } 460} 461 462// JSON2Dot reads a Graph debug log from and io.Reader, and converts the final 463// graph dot format. 464// 465// TODO: Allow returning the output at a certain point during decode. 466// Encode extra information from the json log into the Dot. 467func JSON2Dot(r io.Reader) ([]byte, error) { 468 g, err := decodeGraph(r) 469 if err != nil { 470 return nil, err 471 } 472 473 return g.Dot(nil), nil 474} 475