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