@ 675167640370859e58d24a1f76126760c2e61968 | history
package policy
import (
"cmp"
"fmt"
"slices"
"strconv"
"strings"
"nmyk.io/government/ast"
"nmyk.io/government/builtin"
"nmyk.io/government/sexpr"
)
// DrawOptions controls Draw.
type DrawOptions struct {
// NoCopies leaves out the copies, so only the program's own nodes are
// drawn.
NoCopies bool
}
// Draw prints the graph as a tree, one node per line, with each node's
// depth, its decoded label, its id and its OID:
//
// depth 1 `-- () 1 GOV.0.1.1
// depth 2 |-- + 2 GOV.0.2.21
// depth 3 | `-- + 2' copy
//
// A list node is drawn as (). A ' after the id 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. A note follows its node's OID after a ";", with its line breaks
// shown as " / ".
func (g *Graph) Draw(opts DrawOptions) string {
type line struct {
depth int
tree, id, where string
copy bool
}
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) {
d := describe(n, parent)
l := line{depth: n.Depth, tree: prefix + branch + d.label, id: d.id, where: d.where, copy: d.copy}
if drawn[n] {
l.where += " (shared, drawn above)"
lines = append(lines, l)
return
}
drawn[n] = true
if d.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 {
l.where = fmt.Sprintf("copy, depths %d-%d", n.Depth, last.Depth)
}
lines = append(lines, l)
return
}
if n.Note != "" {
l.where += " ; " + strings.ReplaceAll(n.Note, "\n", " / ")
}
lines = append(lines, l)
var children []*Node
for _, c := range n.Children {
if opts.NoCopies && c.Policy.Equal(n.Policy) {
continue
}
children = append(children, c)
}
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, "", "")
var depthWidth, treeWidth, idWidth int
for _, l := range lines {
depthWidth = max(depthWidth, len(strconv.Itoa(l.depth)))
treeWidth = max(treeWidth, len(l.tree))
idWidth = max(idWidth, len(l.id))
}
var b strings.Builder
for _, l := range lines {
row := fmt.Sprintf("depth %*d %s", depthWidth, l.depth, l.tree)
if l.id != "" || l.where != "" {
// The ' of a copy sits in the gap after the id, so ids stay
// aligned with and without it.
mark := " "
if l.copy {
mark = "'"
}
row = fmt.Sprintf("depth %*d %-*s %*s%s %s", depthWidth, l.depth, treeWidth, l.tree, idWidth, l.id, mark, l.where)
}
b.WriteString(strings.TrimRight(row, " "))
b.WriteByte('\n')
}
return b.String()
}
type description struct {
label, id, where string
copy bool
}
// describe gives a node's label, e.g. + or "hi", its id, and what to show
// beside it: its OID, or "copy" for a copy of its parent.
func describe(n, parent *Node) description {
if n.Policy.Equal(AnyPolicy) {
return description{label: "anyPolicy"}
}
ns, id, text, err := ast.DecodeOID(n.Policy)
if err != nil {
return description{label: n.Policy.String(), where: "(not a GOVERNMENT node)"}
}
switch {
case ns == ast.NSString:
text = sexpr.Print(sexpr.String(text))
case ns == ast.NSBuiltin && text == builtin.ListNode:
text = "()"
}
d := description{label: text, id: strconv.FormatUint(id, 10), where: short(n.Policy)}
if parent != nil && parent.Policy.Equal(n.Policy) {
d.copy, d.where = true, "copy"
}
return d
}
func nodeID(n *Node) uint64 {
_, id, _, _ := ast.DecodeOID(n.Policy)
return id
}