government / ast / layer.go

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