@ 52e34195229c6f9cac00b26701541ddac8a02b66 | 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
}