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