@ 5907b855a9838ebf99230949b5fc2a535b09f3ad | history
package ast
import (
"cmp"
"errors"
"fmt"
"slices"
)
// Edge is a parent->child link in the tree. In the certificates it is a
// policy mapping, issuerDomainPolicy -> subjectDomainPolicy, in the cert at
// the parent's depth.
type Edge struct {
Parent, Child *Node
}
// Layers is the tree cut into one slice per certificate. Cert d (counting
// from 1) holds the nodes at depth d and the edges leaving them, so it is
// index d-1 here. Cert 1 lists its nodes as policies; the nodes below are
// created by the validator from cert d-1's mappings, because certs 2..n
// assert only anyPolicy.
//
// Nodes are not padded down to depth n. An atom above the bottom has no
// mapping, so it expects only its own OID, and anyPolicy in each later cert
// makes the validator copy it down one level at a time. That keeps it from
// being pruned without writing anything for it.
type Layers struct {
Nodes [][]*Node
Edges [][]Edge
}
// Depth is the number of certificates the program needs.
func (l Layers) Depth() int {
return len(l.Nodes)
}
// Layer puts top-level forms at depth 1 and each list's elements one
// deeper than the list. A node shared by several parents must sit at a
// single depth, because a policy node exists at exactly one depth of the
// graph.
func Layer(t *Tree) (Layers, error) {
if len(t.Forms) == 0 {
// An empty policy tree fails validation, so there is no empty
// program to encode.
return Layers{}, errors.New("a program needs at least one form")
}
depth := map[*Node]int{}
var l Layers
var visit func(n *Node, d int) error
visit = func(n *Node, d int) error {
if prev, seen := depth[n]; seen {
if prev != d {
return fmt.Errorf("node %d is reached at depths %d and %d", n.ID, prev, d)
}
return nil
}
depth[n] = d
for len(l.Nodes) < d {
l.Nodes = append(l.Nodes, nil)
l.Edges = append(l.Edges, nil)
}
l.Nodes[d-1] = append(l.Nodes[d-1], n)
for _, c := range n.Children {
l.Edges[d-1] = append(l.Edges[d-1], Edge{n, c})
if err := visit(c, d+1); err != nil {
return err
}
}
return nil
}
for _, f := range t.Forms {
if err := visit(f, 1); err != nil {
return Layers{}, err
}
}
// Certificates list policies and mappings in id order, so the same
// program always produces the same bytes.
for d := range l.Nodes {
sortByID(l.Nodes[d])
slices.SortFunc(l.Edges[d], func(a, b Edge) int {
return cmp.Or(cmp.Compare(a.Parent.ID, b.Parent.ID), cmp.Compare(a.Child.ID, b.Child.ID))
})
}
return l, nil
}