government / policy / draw.go

@ af60bd0141acb3f5ffa6ea8e93d9b351b41c9420 | 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. A note follows its node's
// OID after a ";", with its line breaks shown as " / ".
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
		}
		if n.Note != "" {
			where += "  ; " + strings.ReplaceAll(n.Note, "\n", " / ")
		}
		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
}