government / src / ast / unlayer.go

@ c491ab51ca7fcb046a61286346455e3aaca25ae3 | history


package ast

import (
	"cmp"
	"fmt"
	"slices"
)

// Unlayer rebuilds a tree from its layers. It is how a validated policy
// graph becomes a program, so its input is untrusted: it reads only each
// node's ID, NS and Text, takes structure from the edges alone, and checks
// every decoding rule in DESIGN.md before returning.
//
// A node may have several parents. The result then shares that node rather
// than duplicating it, which is how shared subexpressions survive decoding.
func Unlayer(l Layers) (*Tree, error) {
	u := &unlayerer{
		depth:    map[*Node]int{},
		children: map[*Node][]*Node{},
		built:    map[*Node]*Node{},
		byID:     map[uint64]*Node{},
	}
	if err := u.index(l); err != nil {
		return nil, err
	}
	if len(l.Nodes) == 0 || len(l.Nodes[0]) == 0 {
		return nil, fmt.Errorf("no top-level forms")
	}

	forms := slices.Clone(l.Nodes[0])
	sortByID(forms)
	t := &Tree{}
	for _, f := range forms {
		if isDot(f) {
			return nil, fmt.Errorf("depth 1: %s is outside a list; . belongs second-to-last in one", f)
		}
		n, err := u.build(f)
		if err != nil {
			return nil, err
		}
		t.Forms = append(t.Forms, n)
	}
	return t, nil
}

type unlayerer struct {
	depth    map[*Node]int
	children map[*Node][]*Node
	built    map[*Node]*Node // input node -> output node, so shared nodes stay shared
	byID     map[uint64]*Node
}

// index records each node's depth and children, and checks that every
// edge goes down exactly one level and every node below depth 1 has a
// parent.
func (u *unlayerer) index(l Layers) error {
	for d, nodes := range l.Nodes {
		for _, n := range nodes {
			if prev, ok := u.depth[n]; ok {
				return fmt.Errorf("%s is listed at depths %d and %d", n, prev, d+1)
			}
			u.depth[n] = d + 1
		}
	}
	hasParent := map[*Node]bool{}
	for d, edges := range l.Edges {
		for _, e := range edges {
			if u.depth[e.Parent] != d+1 || u.depth[e.Child] != d+2 {
				return fmt.Errorf("cert %d: mapping %s -> %s does not go from depth %d to %d", d+1, e.Parent, e.Child, d+1, d+2)
			}
			u.children[e.Parent] = append(u.children[e.Parent], e.Child)
			hasParent[e.Child] = true
		}
	}
	for d := 1; d < len(l.Nodes); d++ {
		for _, n := range l.Nodes[d] {
			if !hasParent[n] {
				return fmt.Errorf("depth %d: %s has no parent", d+1, n)
			}
		}
	}
	return nil
}

func (u *unlayerer) build(in *Node) (*Node, error) {
	if out, ok := u.built[in]; ok {
		return out, nil
	}
	d := u.depth[in]
	out := &Node{ID: in.ID, NS: in.NS, Text: in.Text, Note: in.Note}
	// Ids are unique across the program, so two real nodes with one id
	// means two different OIDs claim the same place in argument order.
	if other, ok := u.byID[in.ID]; ok {
		return nil, fmt.Errorf("depth %d: %s and %s share node id %d", d, other, out, in.ID)
	}
	u.byID[in.ID] = out
	u.built[in] = out

	for _, c := range u.children[in] {
		if sameOID(c, in) {
			if err := u.checkCopy(c); err != nil {
				return nil, err
			}
			continue
		}
		child, err := u.build(c)
		if err != nil {
			return nil, err
		}
		out.Children = append(out.Children, child)
	}
	sortByID(out.Children)
	if err := checkShape(out); err != nil {
		return nil, fmt.Errorf("depth %d: %w", d, err)
	}
	return out, nil
}

// checkCopy accepts a copy the validator made and everything below it,
// which may only be further copies of the same atom. A real node under a
// copy would mean an edge from an OID the program never mapped from at
// that depth.
func (u *unlayerer) checkCopy(c *Node) error {
	for _, below := range u.children[c] {
		if !sameOID(below, c) {
			return fmt.Errorf("depth %d: copy %s has real child %s; a copy may only have copies below it", u.depth[c], c, below)
		}
		if err := u.checkCopy(below); err != nil {
			return err
		}
	}
	return nil
}

// sameOID is how the decoder recognizes the validator's copies: an atom
// with no mapping expects only its own OID, so anyPolicy in the next cert
// gives it a child with that same OID.
func sameOID(a, b *Node) bool {
	return a.ID == b.ID && a.NS == b.NS && a.Text == b.Text
}

func sortByID(nodes []*Node) {
	slices.SortFunc(nodes, func(a, b *Node) int { return cmp.Compare(a.ID, b.ID) })
}