government / ast / tree.go

@ 26a72779eff9f25b53bae86607e9e4f6cd54934d | history


package ast

import (
	"crypto/x509"
	"fmt"
	"strconv"
	"strings"

	"government/sexpr"
)

// Node is one node of the program tree, and one policy OID in the
// certificates. Only list nodes have children; an atom's payload is all
// there is to it.
type Node struct {
	ID       uint64
	NS       Namespace
	Text     string
	Children []*Node
	// Note is the source comment describing this node, if any. It travels
	// in the certs as a policy qualifier and never affects evaluation.
	Note string
}

// Tree is a whole program. Its forms are the children of the policy tree's
// anyPolicy root.
type Tree struct {
	Forms []*Node
}

func (n *Node) OID() (x509.OID, error) {
	return EncodeOID(n.NS, n.ID, n.Text)
}

func (n *Node) IsList() bool {
	return n.NS == NSBuiltin && n.Text == ListNode
}

// Build turns a program, as datums from sexpr.ReadProgram, into a tree,
// numbering nodes 1, 2, 3, ... in pre-order (a list before its elements,
// elements left to right). Because ids are given in reading order, sorting
// siblings by id recovers argument order, which certificates do not
// preserve. Each datum becomes exactly one node and passes its note on.
func Build(program []*sexpr.Datum) (*Tree, error) {
	b := &builder{}
	t := &Tree{}
	for _, form := range program {
		n, err := b.node(form)
		if err != nil {
			return nil, err
		}
		t.Forms = append(t.Forms, n)
	}
	return t, nil
}

// ToTree is Build for a program that exists only as values, with no source
// and so no notes.
func ToTree(program []sexpr.Value) (*Tree, error) {
	return Build(sexpr.DatumsOf(program))
}

type builder struct {
	lastID uint64
}

func (b *builder) node(d *sexpr.Datum) (*Node, error) {
	b.lastID++
	n := &Node{ID: b.lastID, Note: d.Note}
	if d.Dot {
		n.NS, n.Text = NSBuiltin, Dot
		return n, nil
	}
	if d.IsList() {
		n.NS, n.Text = NSBuiltin, ListNode
		for _, e := range d.Elems {
			child, err := b.node(e)
			if err != nil {
				return nil, err
			}
			n.Children = append(n.Children, child)
		}
		return n, nil
	}
	switch v := d.Value.(type) {
	case sexpr.Symbol:
		n.NS, n.Text = NSSymbol, string(v)
		if isReservedSymbol(n.Text) {
			n.NS = NSBuiltin
		}
	case sexpr.Int:
		n.NS, n.Text = NSInt, strconv.FormatInt(int64(v), 10)
	case sexpr.Float:
		// The reader keeps values, not spellings, so 3.10 is stored as 3.1.
		// Print gives the shortest text that reads back as the same float.
		n.NS, n.Text = NSFloat, sexpr.Print(v)
	case sexpr.String:
		n.NS, n.Text = NSString, string(v)
	case sexpr.Bool:
		n.NS, n.Text = NSBuiltin, False
		if v {
			n.Text = True
		}
	case sexpr.Empty:
		n.NS, n.Text = NSBuiltin, Empty
	default:
		return nil, fmt.Errorf("%s cannot be in a program tree", sexpr.Print(v))
	}
	if n.NS != NSBuiltin {
		if err := checkPayload(n.NS, n.Text); err != nil {
			return nil, err
		}
	}
	return n, nil
}

// Origins maps each list FromTree produced back to its node, so an evaluation
// error inside a .gov program can name the OID it came from, the way the
// reader's positions name a line and column.
type Origins map[*sexpr.Pair]*Node

// FromTree is ToTree's inverse. A builtin name becomes the plain symbol, so
// '+ quotes the symbol +, exactly as in source.
func FromTree(t *Tree) ([]sexpr.Value, Origins, error) {
	origins := Origins{}
	forms := make([]sexpr.Value, len(t.Forms))
	for i, n := range t.Forms {
		v, err := value(n, origins)
		if err != nil {
			return nil, nil, err
		}
		forms[i] = v
	}
	return forms, origins, nil
}

func value(n *Node, origins Origins) (sexpr.Value, error) {
	if err := checkShape(n); err != nil {
		return nil, err
	}
	if n.IsList() {
		return listValue(n, origins)
	}
	switch n.NS {
	case NSBuiltin:
		switch n.Text {
		case True:
			return sexpr.T, nil
		case False:
			return sexpr.F, nil
		case Empty:
			return sexpr.Nil, nil
		case Dot:
			return nil, fmt.Errorf("%s is outside a list; . belongs second-to-last in one", n)
		}
		return sexpr.Symbol(n.Text), nil
	case NSSymbol:
		return sexpr.Symbol(n.Text), nil
	case NSInt, NSFloat:
		v, _, err := sexpr.ParseNumber(n.Text)
		if err != nil {
			return nil, fmt.Errorf("%s: %w", n, err)
		}
		return v, nil
	case NSString:
		return sexpr.String(n.Text), nil
	}
	return nil, fmt.Errorf("%s: unknown %s", n, n.NS)
}

func listValue(n *Node, origins Origins) (sexpr.Value, error) {
	children := n.Children
	var tail sexpr.Value = sexpr.Nil
	if k := len(children); k >= 3 && isDot(children[k-2]) {
		t, err := value(children[k-1], origins)
		if err != nil {
			return nil, err
		}
		tail, children = t, children[:k-2]
	}
	items := make([]sexpr.Value, len(children))
	for i, c := range children {
		v, err := value(c, origins)
		if err != nil {
			return nil, err
		}
		items[i] = v
	}
	list := sexpr.ListWithTail(tail, items...).(*sexpr.Pair)
	origins[list] = n
	return list, nil
}

func isDot(n *Node) bool {
	return n.NS == NSBuiltin && n.Text == Dot
}

// checkShape enforces the decoding rules that concern a node and its own
// children: a list has at least one element, an atom has none, and "."
// sits second-to-last with at least one element before it.
func checkShape(n *Node) error {
	if !n.IsList() {
		if len(n.Children) > 0 {
			return fmt.Errorf("atom %s has child %s; an atom can have none", n, n.Children[0])
		}
		return nil
	}
	k := len(n.Children)
	if k == 0 {
		return fmt.Errorf("list %s has no elements; the empty list is the () builtin", n)
	}
	for i, c := range n.Children {
		if isDot(c) && (i != k-2 || k < 3) {
			return fmt.Errorf("list %s has . at position %d of %d; it belongs second-to-last, after at least one element", n, i+1, k)
		}
	}
	return nil
}

// String names a node the way tools print OIDs, with GOV for Root, so an
// error points at something visible in a certificate dump.
func (n *Node) String() string {
	oid, err := n.OID()
	if err != nil {
		return fmt.Sprintf("#%d (%s %q)", n.ID, n.NS, n.Text)
	}
	return strings.Replace(oid.String(), Root, "GOV", 1)
}