government / ast / tree.go

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

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

// ToTree turns a parsed program 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.
func ToTree(program []sexpr.Value) (*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
}

type builder struct {
	lastID uint64
}

func (b *builder) node(v sexpr.Value) (*Node, error) {
	b.lastID++
	n := &Node{ID: b.lastID}
	switch v := v.(type) {
	case *sexpr.Pair:
		n.NS, n.Text = NSBuiltin, ListNode
		return n, b.elements(n, v)
	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
}

// elements makes each element of the list p a child of n. An improper
// tail becomes a "." child followed by the tail, mirroring the source text
// (a b . c).
func (b *builder) elements(n *Node, p *sexpr.Pair) error {
	var rest sexpr.Value = p
	for {
		switch r := rest.(type) {
		case *sexpr.Pair:
			child, err := b.node(r.Car)
			if err != nil {
				return err
			}
			n.Children = append(n.Children, child)
			rest = r.Cdr
			continue
		case sexpr.Empty:
			return nil
		}
		b.lastID++
		n.Children = append(n.Children, &Node{ID: b.lastID, NS: NSBuiltin, Text: Dot})
		tail, err := b.node(rest)
		if err != nil {
			return err
		}
		n.Children = append(n.Children, tail)
		return nil
	}
}

// isReservedSymbol reports whether a source symbol names a builtin. The
// structural names never come out of the reader as symbols; if one did, it
// must stay a symbol rather than turn into structure.
func isReservedSymbol(name string) bool {
	switch name {
	case ListNode, Dot, True, False, Empty:
		return false
	}
	return IsBuiltin(name)
}

// 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)
}