government / src / policy / draw.go

@ 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
}