@ 21ba553f2ac9aed7435e6a7744c2a33c37c9dec8 | history
package policy
import (
"cmp"
"fmt"
"slices"
"strconv"
"strings"
"government/ast"
"government/sexpr"
)
// Draw prints the graph as a tree, one node per line, with each node's
// depth, its decoded label and its OID:
//
// depth 1 `-- (...)#1 GOV.0.1.1
// depth 2 |-- +#2 GOV.0.2.21
// depth 3 | `-- +#2' copy
//
// A trailing ' marks a copy the validator made, which carries an atom down
// to the bottom; a chain of copies is one line giving the depths it spans.
// A node with several parents is drawn in full under the first and named
// again, without its children, under the others.
func (g *Graph) Draw() string {
type line struct {
depth int
tree, where string
}
var lines []line
drawn := map[*Node]bool{}
var walk func(n *Node, parent *Node, prefix, branch string)
walk = func(n *Node, parent *Node, prefix, branch string) {
label, where := describe(n, parent)
if drawn[n] {
lines = append(lines, line{n.Depth, prefix + branch + label, where + " (shared, drawn above)"})
return
}
drawn[n] = true
if where == "copy" {
// A copy can only have more copies of itself below it, down to
// the bottom; one line says how far the chain goes.
last := n
for len(last.Children) == 1 && last.Children[0].Policy.Equal(n.Policy) {
last = last.Children[0]
}
if last != n {
where = fmt.Sprintf("copy, depths %d-%d", n.Depth, last.Depth)
}
lines = append(lines, line{n.Depth, prefix + branch + label, where})
return
}
lines = append(lines, line{n.Depth, prefix + branch + label, where})
children := slices.Clone(n.Children)
slices.SortStableFunc(children, func(a, b *Node) int { return cmp.Compare(nodeID(a), nodeID(b)) })
childPrefix := prefix
switch branch {
case "|-- ":
childPrefix += "| "
case "`-- ":
childPrefix += " "
}
for i, c := range children {
b := "|-- "
if i == len(children)-1 {
b = "`-- "
}
walk(c, n, childPrefix, b)
}
}
walk(g.Levels[0][0], nil, "", "")
width := 0
for _, l := range lines {
width = max(width, len(l.tree))
}
var b strings.Builder
for _, l := range lines {
row := fmt.Sprintf("depth %d %-*s %s", l.depth, width, l.tree, l.where)
b.WriteString(strings.TrimRight(row, " "))
b.WriteByte('\n')
}
return b.String()
}
// describe gives a node's label, e.g. +#2 or "hi"#11, and what to show
// beside it: its OID, or "copy" for a copy of its parent.
func describe(n, parent *Node) (label, where string) {
if n.Policy.Equal(AnyPolicy) {
return "anyPolicy", ""
}
ns, id, text, err := ast.DecodeOID(n.Policy)
if err != nil {
return n.Policy.String(), "(not a GOVERNMENT node)"
}
if ns == ast.NSString {
text = sexpr.Print(sexpr.String(text))
}
label = text + "#" + strconv.FormatUint(id, 10)
if parent != nil && parent.Policy.Equal(n.Policy) {
return label + "'", "copy"
}
return label, short(n.Policy)
}
func nodeID(n *Node) uint64 {
_, id, _, _ := ast.DecodeOID(n.Policy)
return id
}