government / program / program.go

@ c3dee802a4878505a60909c4f533fffbdfffc936 | history


// Package program is the whole path from a .gov file to something the
// evaluator can run: ratify the chain, rebuild the policy graph, decode it
// into a tree, and turn the tree into values.
//
// It is also the trust boundary. Everything before Load returns is checking
// untrusted bytes; everything after it runs code that passed every check.
package program

import (
	"crypto/x509"
	"fmt"
	"io"
	"strings"
	"time"

	"government/ast"
	"government/eval"
	"government/policy"
	"government/ratify"
	"government/sexpr"
)

// ErrDecode: the policy graph is valid but does not decode to a program,
// e.g. a list node with no elements.
const ErrDecode = "E-DECODE"

type Error struct {
	Code string
	Msg  string
}

func (e *Error) Error() string { return e.Code + ": " + e.Msg }

type Options struct {
	At       time.Time
	Pin      ratify.Pin
	CRLs     [][]byte
	MaxNodes int
}

// Program is a ratified, decoded program.
type Program struct {
	Forms []sexpr.Value
	// Certs is the chain in depth order, anchor first.
	Certs []*x509.Certificate
	// Tree is the decoded program, with its notes.
	Tree *ast.Tree
	// Nodes is how many AST nodes the program has. A node shared by
	// several parents counts once; the validator's copies do not count.
	Nodes   int
	origins ast.Origins
	depth   map[*ast.Node]int
	parent  map[*ast.Node]*ast.Node
}

// Depth is how many certificates hold the program, not counting the
// anchor: the depth of its tree.
func (p *Program) Depth() int { return len(p.Certs) - 1 }

// Load runs every check on a .gov file and decodes it. Any error it returns
// means the program may not run: a ratify, policy or decode error.
func Load(data []byte, opts Options) (*Program, error) {
	certs, err := ratify.Ratify(data, ratify.Options{At: opts.At, Pin: opts.Pin, CRLs: opts.CRLs})
	if err != nil {
		return nil, err
	}
	g, err := policy.Program(certs, policy.Options{MaxNodes: opts.MaxNodes})
	if err != nil {
		return nil, err
	}
	layers, err := g.Layers()
	if err != nil {
		return nil, &Error{ErrDecode, err.Error()}
	}
	tree, err := ast.Unlayer(layers)
	if err != nil {
		return nil, &Error{ErrDecode, err.Error()}
	}
	forms, origins, err := ast.FromTree(tree)
	if err != nil {
		return nil, &Error{ErrDecode, err.Error()}
	}
	p := &Program{Forms: forms, Certs: certs, Tree: tree, origins: origins,
		depth: map[*ast.Node]int{}, parent: map[*ast.Node]*ast.Node{}}
	var walk func(n, parent *ast.Node, d int)
	walk = func(n, parent *ast.Node, d int) {
		if _, seen := p.depth[n]; seen {
			return
		}
		p.depth[n] = d
		if parent != nil {
			p.parent[n] = parent
		}
		for _, c := range n.Children {
			walk(c, n, d+1)
		}
	}
	for _, f := range tree.Forms {
		walk(f, nil, 1)
	}
	p.Nodes = len(p.depth)
	return p, nil
}

// Locate names where an evaluation error happened: the OID of the
// innermost list being evaluated and its depth, which is the cert that
// holds it, plus the note of the innermost noted node around it. A .gov
// program has no line numbers; this is its equivalent.
func (p *Program) Locate(err error) string {
	n := p.node(err)
	if n == nil {
		return ""
	}
	where := fmt.Sprintf("%s (depth %d)", n, p.depth[n])
	for m := n; m != nil; m = p.parent[m] {
		if m.Note != "" {
			where += fmt.Sprintf(" (note: %q)", strings.ReplaceAll(m.Note, "\n", " "))
			break
		}
	}
	return where
}

func (p *Program) node(err error) *ast.Node {
	e, ok := err.(*eval.Error)
	if !ok {
		return nil
	}
	pair, ok := e.Expr.(*sexpr.Pair)
	if !ok {
		return nil
	}
	return p.origins[pair]
}

// Run evaluates the forms in order, printing the value of each one that is
// not a define, and stops at the first error.
func (p *Program) Run(out io.Writer) error {
	top := eval.NewTopLevel()
	for _, form := range p.Forms {
		v, err := top.Eval(form)
		if err != nil {
			return err
		}
		if !IsDefine(form) {
			fmt.Fprintln(out, sexpr.Print(v))
		}
	}
	return nil
}

// Describe formats an evaluation error with its location, as `government
// run` prints it.
func (p *Program) Describe(err error) string {
	if where := p.Locate(err); where != "" {
		return err.Error() + " at " + where
	}
	return err.Error()
}

func IsDefine(form sexpr.Value) bool {
	pair, ok := form.(*sexpr.Pair)
	return ok && pair.Car == sexpr.Value(sexpr.Symbol("define"))
}