prettyprinters/subgraph_printer.go
// Copyright © 2016 Asteris, LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package prettyprinters
import (
"bytes"
"errors"
"github.com/asteris-llc/converge/graph"
"github.com/asteris-llc/converge/graph/node"
"golang.org/x/net/context"
)
// Subgraph are treated as a semi-lattice with the root graph as the ⊥ (join)
// element. Subgraphs are partially ordered based on the rank of their root
// element in the graph.
// Subgraph is a type that represents a subgraph containing it's ID, it's root
// node, a list of it's terminal nodes, and any other included nodes.
type Subgraph struct {
StartNode *string
EndNodes []string
ID SubgraphID
Nodes []string
}
// SubgraphMap is a simple type alias for keeping track of SubgraphID ->
// Subgraph mappings
type SubgraphMap map[SubgraphID]Subgraph
// A SubgraphID is an opaque type that is handled by the DigraphPrettyPrinter.
// SubgraphID must adhere to the following conditions:
//
// * Unique per graph
// * Comparable
type SubgraphID interface{}
// A SubgraphMarker is a structure used to identify graph nodes that mark the
// beginning or end of a Subgraph. SubgraphMakers are returned by MarkNode().
// The SubgraphID field should be set to the name of a unique SubgraphID if
// start is true. When Start is false the SubgraphID field is ignored.
type SubgraphMarker struct {
SubgraphID SubgraphID // The ID for this subgraph (if Start is true)
Start bool // True if this is the start of a new subgraph
}
// SubgraphBottomID defines the SubgraphID for the bottom subgraph. "⊥" is a
// reserved SubgraphID and shouldn't be returned as the SubgraphID by any calls
// to MakeNode.
var SubgraphBottomID interface{}
var (
// This is the join element that contains all other subgraphs. subgraphBottom
// is the parent of all top-level subgraphs.
subgraphBottom = Subgraph{
StartNode: nil,
Nodes: make([]string, 0),
}
)
// makeSubgraphMap creates a new map to hold subgraph data and includes a ⊥
// element. Returns a tuple of the subgraph map and the identifier for the join
// element.
func makeSubgraphMap() SubgraphMap {
subgraph := make(SubgraphMap)
subgraph[SubgraphBottomID] = subgraphBottom
return subgraph
}
// loadSubgraphs takes a graph and a subgraph map and traverses the graph,
// calling MarkNode() on each node, creating and updating subgraphs as
// necessary.
func (p Printer) loadSubgraphs(ctx context.Context, g *graph.Graph, subgraphs SubgraphMap) {
printer, ok := p.pp.(SubgraphPrinter)
if !ok {
for _, node := range g.Vertices() {
addNodeToSubgraph(subgraphs, nil, node)
}
return
}
g.RootFirstWalk(ctx, func(meta *node.Node) error {
if sgMarker := printer.MarkNode(g, meta.ID); sgMarker != nil {
if sgMarker.Start {
addNodeToSubgraph(subgraphs, sgMarker.SubgraphID, meta.ID)
} else {
thisSubgraph := getSubgraphByID(subgraphs, graph.ParentID(meta.ID))
setSubgraphEndNode(subgraphs, thisSubgraph, meta.ID)
}
} else {
subgraphID := getSubgraphByID(subgraphs, graph.ParentID(meta.ID))
addNodeToSubgraph(subgraphs, subgraphID, meta.ID)
}
return nil
})
}
// getParentSubgraph will, given a SubgraphMap a SubgraphID, and a position in
// the graph, locate the parent subgraph, or return ⊥ if no other subgraph is
// found.
func getParentSubgraph(subgraphs SubgraphMap, thisSubgraph SubgraphID, id string) SubgraphID {
parent := graph.ParentID(id)
if thisSubgraph == SubgraphBottomID {
return SubgraphBottomID
}
if id == "." || parent == "." {
return SubgraphBottomID
}
for subgraphID, subgraph := range subgraphs {
for nodeIdx := range subgraph.Nodes {
if id == subgraph.Nodes[nodeIdx] {
if subgraphID == thisSubgraph {
return getParentSubgraph(subgraphs, thisSubgraph, graph.ParentID(id))
}
return subgraphID
}
}
}
return getParentSubgraph(subgraphs, thisSubgraph, graph.ParentID(id))
}
// setSubgraphEndNode appends the given node to the nodes and end nodes lists
// for the specified subgraph.
func setSubgraphEndNode(subgraphs SubgraphMap, subgraphID SubgraphID, node string) {
if subgraphID == SubgraphBottomID {
return
}
if sg, found := subgraphs[subgraphID]; found {
sg.EndNodes = append(sg.EndNodes, node)
sg.Nodes = append(sg.Nodes, node)
subgraphs[subgraphID] = sg
}
}
// isSubgraphEnd returns true if the subgraph exists and the node string is a
// member it's EndNodes list, and false otherwise.
func isSubgraphEnd(subgraphs SubgraphMap, id SubgraphID, node string) bool {
sg, found := subgraphs[id]
if !found {
return false
}
for endNodeIdx := range sg.EndNodes {
if node == sg.EndNodes[endNodeIdx] {
return true
}
}
return false
}
// getSubgraphByID returns the first subgraph that has the given node as an
// element, and ⊥ otherwise.
func getSubgraphByID(subgraphs SubgraphMap, id string) SubgraphID {
if id == "." {
return SubgraphBottomID
}
for subgraphID, subgraph := range subgraphs {
if isSubgraphEnd(subgraphs, subgraphID, id) {
return getParentSubgraph(subgraphs, subgraphID, id)
}
for nodeIdx := range subgraph.Nodes {
if id == subgraph.Nodes[nodeIdx] {
return subgraphID
}
}
}
return getSubgraphByID(subgraphs, graph.ParentID(id))
}
// addNodeToSubgraph appnds the given node to a subgraph, creating a new
// subgraph if necessary.
func addNodeToSubgraph(subgraphs SubgraphMap, subgraphID SubgraphID, vertexID string) {
oldGraph, found := subgraphs[subgraphID]
if !found {
oldGraph.StartNode = &vertexID
oldGraph.ID = subgraphID
}
oldGraph.StartNode = &vertexID
oldGraph.Nodes = append(oldGraph.Nodes, vertexID)
subgraphs[subgraphID] = oldGraph
}
// drawSubgraph call DrawNode for each element within the specified subgraph,
// calling StartSubgraph() and FinishSubgraph before and after to ensure that
// the returned string contains any prefix/postfix additions defined by the
// printer.
func (p Printer) drawSubgraph(g *graph.Graph, id SubgraphID, subgraph Subgraph) (Renderable, error) {
subgraphPrinter, spOK := p.pp.(SubgraphPrinter)
nodePrinter, npOK := p.pp.(NodePrinter)
if !spOK && !npOK {
return HiddenString(), nil
}
buffer := new(bytes.Buffer)
write := func(s Renderable) { buffer.WriteString(s.String()) }
subgraphNodes := subgraph.Nodes
if nil == subgraph.StartNode {
return nil, errors.New("Cannot draw subgraph starting at nil vertex")
}
if spOK {
if str, err := subgraphPrinter.StartSubgraph(g, *subgraph.StartNode, subgraph.ID); err == nil {
write(str)
} else {
return nil, err
}
}
if npOK {
for idx := range subgraphNodes {
if str, err := nodePrinter.DrawNode(g, subgraphNodes[idx]); err == nil {
write(str)
} else {
return nil, err
}
}
}
if spOK {
if str, err := subgraphPrinter.FinishSubgraph(g, id); err == nil {
write(str)
}
}
return buffer, nil
}