@ 594cab6ae95854c36078bb56c8f0f51ffc68b05e | 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.
//
// A node shared by several parents becomes one value shared by several
// lists, so a shared subexpression is never unfolded: the program in memory
// is as small as the one in the certificates. Values are immutable, so
// nothing can tell the sharing apart from copies.
func FromTree(t *Tree) ([]sexpr.Value, Origins, error) {
c := &converter{origins: Origins{}, done: map[*Node]sexpr.Value{}}
forms := make([]sexpr.Value, len(t.Forms))
for i, n := range t.Forms {
v, err := c.value(n)
if err != nil {
return nil, nil, err
}
forms[i] = v
}
return forms, c.origins, nil
}
type converter struct {
origins Origins
done map[*Node]sexpr.Value
}
func (c *converter) value(n *Node) (sexpr.Value, error) {
if v, ok := c.done[n]; ok {
return v, nil
}
v, err := c.convert(n)
if err == nil {
c.done[n] = v
}
return v, err
}
func (c *converter) convert(n *Node) (sexpr.Value, error) {
if err := checkShape(n); err != nil {
return nil, err
}
if n.IsList() {
return c.listValue(n)
}
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 (c *converter) listValue(n *Node) (sexpr.Value, error) {
children := n.Children
var tail sexpr.Value = sexpr.Nil
if k := len(children); k >= 3 && isDot(children[k-2]) {
t, err := c.value(children[k-1])
if err != nil {
return nil, err
}
tail, children = t, children[:k-2]
}
items := make([]sexpr.Value, len(children))
for i, child := range children {
v, err := c.value(child)
if err != nil {
return nil, err
}
items[i] = v
}
list := sexpr.ListWithTail(tail, items...).(*sexpr.Pair)
c.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)
}