government / src / ast / share.go

@ d87504922ed319f2e3fd703dca40b7219eeeada1 | history


package ast

import (
	"cmp"
	"container/heap"
	"encoding/binary"
)

// Share merges identical subtrees at the same depth into one node with
// several parents, which RFC 9618's policy graph represents directly: a
// shared node costs one mapping per parent, and its own subtree is
// written once. Nothing is shared that would change the program, so the
// result evaluates exactly as t does.
//
// Only lists are shared. An atom costs one mapping per parent either way,
// so sharing one saves nothing, and sharing atoms would make argument
// order impossible to keep far more often (see below).
//
// Three rules keep the meaning intact:
//
//   - A subtree is identical only with its notes, so no comment is lost.
//
//   - Two equal children of one parent stay two nodes: a cert's policies
//     are a set, so (+ (f) (f)) sharing one (f) would lose an argument.
//     The k-th copy among siblings is shared only with other k-th copies.
//
//   - Ids still have to give argument order: within every parent, children
//     sort by id. Sharing adds a node to several parents, and their orders
//     can disagree: (f (g) (h)) and (k (h) (g)) at one depth would need
//     (g) both before and after (h). Before sharing, Share checks the
//     node can follow the sibling before it without such a contradiction,
//     and keeps a separate copy when it cannot.
//
// Ids are then renumbered 1..N in an order every parent agrees with,
// breaking ties by original id, so a program with nothing to share keeps
// exactly the ids Build gave it.
//
// t must be as Build made it: ids 1..N, each node in one place.
func Share(t *Tree) *Tree {
	s := &sharer{
		interned: map[string]int{},
		canon:    map[shareKey]*Node{},
		orig:     map[*Node]uint64{},
		after:    map[*Node][]*Node{},
	}
	out := &Tree{Forms: s.children(t.Forms, 1)}
	s.renumber()
	return out
}

type shareKey struct {
	depth, rank, structure int
}

type sharer struct {
	structure []int          // input node id -> its structure's number + 1
	interned  map[string]int // a structure's description -> its number
	key       []byte
	canon     map[shareKey]*Node // the first output node for each key
	orig      map[*Node]uint64   // output node -> id of the input node it came from
	after     map[*Node][]*Node  // order constraints: a must come before each of after[a]
	nodes     []*Node
}

// structureOf numbers each distinct subtree shape, notes included, so two
// subtrees are identical exactly when their numbers match.
func (s *sharer) structureOf(n *Node) int {
	if int(n.ID) < len(s.structure) && s.structure[n.ID] > 0 {
		return s.structure[n.ID] - 1
	}
	children := make([]int, len(n.Children))
	for i, c := range n.Children {
		children[i] = s.structureOf(c)
	}
	k := append(s.key[:0], byte(n.NS))
	k = binary.AppendUvarint(k, uint64(len(n.Text)))
	k = append(k, n.Text...)
	k = binary.AppendUvarint(k, uint64(len(n.Note)))
	k = append(k, n.Note...)
	for _, c := range children {
		k = binary.AppendUvarint(k, uint64(c))
	}
	s.key = k
	id, ok := s.interned[string(k)]
	if !ok {
		id = len(s.interned)
		s.interned[string(k)] = id
	}
	for int(n.ID) >= len(s.structure) {
		s.structure = append(s.structure, 0)
	}
	s.structure[n.ID] = id + 1
	return id
}

// children places the elements of one list (or the top-level forms) at
// depth, sharing where the rules allow, and records that each must come
// after the one before it.
func (s *sharer) children(in []*Node, depth int) []*Node {
	var out []*Node
	rank := map[int]int{}
	var prev *Node
	for _, c := range in {
		st := s.structureOf(c)
		key := shareKey{depth, rank[st], st}
		rank[st]++

		n := s.canon[key]
		if n == nil || (prev != nil && s.reaches(n, prev)) {
			n = s.copy(c, depth)
			if c.IsList() && s.canon[key] == nil {
				s.canon[key] = n
			}
		}
		if prev != nil {
			s.after[prev] = append(s.after[prev], n)
		}
		out = append(out, n)
		prev = n
	}
	return out
}

func (s *sharer) copy(in *Node, depth int) *Node {
	n := &Node{NS: in.NS, Text: in.Text, Note: in.Note}
	s.orig[n] = in.ID
	s.nodes = append(s.nodes, n)
	n.Children = s.children(in.Children, depth+1)
	return n
}

// reaches reports whether from must already come before to. Ordering to
// before from as well would then be a contradiction.
func (s *sharer) reaches(from, to *Node) bool {
	seen := map[*Node]bool{}
	stack := []*Node{from}
	for len(stack) > 0 {
		n := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if n == to {
			return true
		}
		if seen[n] {
			continue
		}
		seen[n] = true
		stack = append(stack, s.after[n]...)
	}
	return false
}

// renumber gives the nodes ids 1..N in an order that puts every list's
// elements in argument order. Among the nodes free to go next it picks
// the one with the smallest original id.
func (s *sharer) renumber() {
	waiting := map[*Node]int{}
	for _, n := range s.nodes {
		for _, m := range s.after[n] {
			waiting[m]++
		}
	}
	ready := &byOrig{orig: s.orig}
	for _, n := range s.nodes {
		if waiting[n] == 0 {
			heap.Push(ready, n)
		}
	}
	var next uint64
	for ready.Len() > 0 {
		n := heap.Pop(ready).(*Node)
		next++
		n.ID = next
		for _, m := range s.after[n] {
			if waiting[m]--; waiting[m] == 0 {
				heap.Push(ready, m)
			}
		}
	}
	if int(next) != len(s.nodes) {
		// children never adds an order that closes a cycle, so every node
		// is numbered.
		panic("ast.Share: argument orders contradict each other")
	}
}

type byOrig struct {
	nodes []*Node
	orig  map[*Node]uint64
}

func (h *byOrig) Len() int           { return len(h.nodes) }
func (h *byOrig) Less(i, j int) bool { return cmp.Less(h.orig[h.nodes[i]], h.orig[h.nodes[j]]) }
func (h *byOrig) Swap(i, j int)      { h.nodes[i], h.nodes[j] = h.nodes[j], h.nodes[i] }
func (h *byOrig) Push(x any)         { h.nodes = append(h.nodes, x.(*Node)) }
func (h *byOrig) Pop() any {
	n := h.nodes[len(h.nodes)-1]
	h.nodes = h.nodes[:len(h.nodes)-1]
	return n
}