@ 27e33aecf4976d7646339e35c5fff6755a29497c | history
package ast
import (
"os"
"path/filepath"
"reflect"
"strings"
"testing"
"government/internal/lisptest"
"government/sexpr"
)
func shareSource(t *testing.T, src string) (built, shared *Tree) {
t.Helper()
datums, err := sexpr.ReadProgram(src)
if err != nil {
t.Fatal(err)
}
built, err = Build(datums)
if err != nil {
t.Fatal(err)
}
again, _ := Build(datums)
return built, Share(again)
}
// checkShared checks everything the certificates need from a shared tree,
// and that it still means src.
func checkShared(t *testing.T, src string, tree *Tree) {
t.Helper()
seen := map[*Node]bool{}
var ids []uint64
var walk func(n *Node)
walk = func(n *Node) {
if seen[n] {
return
}
seen[n] = true
ids = append(ids, n.ID)
parentOf := map[*Node]bool{}
for i, c := range n.Children {
if parentOf[c] {
t.Errorf("%s has %s as a child twice", n, c)
}
parentOf[c] = true
if i > 0 && n.Children[i-1].ID >= c.ID {
t.Errorf("%s: children out of id order: %s before %s", n, n.Children[i-1], c)
}
walk(c)
}
}
for i, f := range tree.Forms {
if i > 0 && tree.Forms[i-1].ID >= f.ID {
t.Errorf("forms out of id order: %s before %s", tree.Forms[i-1], f)
}
walk(f)
}
want := make([]bool, len(ids)+1)
for _, id := range ids {
if id < 1 || int(id) > len(ids) || want[id] {
t.Fatalf("ids are not exactly 1..%d: %v", len(ids), ids)
}
want[id] = true
}
// Through the certificates' representation and back.
layers, err := Layer(tree)
if err != nil {
t.Fatal(err)
}
decoded, err := Unlayer(layers)
if err != nil {
t.Fatal(err)
}
forms, _, err := FromTree(decoded)
if err != nil {
t.Fatal(err)
}
orig, err := sexpr.ReadAll(src)
if err != nil {
t.Fatal(err)
}
if !reflect.DeepEqual(forms, orig) {
t.Errorf("shared program reads back as\n%v\nwant\n%v", printAll(forms), printAll(orig))
}
}
func countNodes(tree *Tree) int {
seen := map[*Node]bool{}
var walk func(n *Node)
walk = func(n *Node) {
if !seen[n] {
seen[n] = true
for _, c := range n.Children {
walk(c)
}
}
}
for _, f := range tree.Forms {
walk(f)
}
return len(seen)
}
func TestShare(t *testing.T) {
tests := []struct {
name, src string
saved int // nodes the shared tree has fewer of
}{
{"nothing repeated", "(+ 1 (* 2 3))", 0},
{"atoms are never shared", "(+ x x) (- x x)", 0},
{"one list, two parents", "(g (f 1)) (h (f 1))", 3},
{"equal siblings stay apart", "(+ (f 1) (f 1))", 0},
{"k-th copies share with k-th copies", "(+ (f 1) (f 1)) (- (f 1) (f 1))", 6},
{"different depths stay apart", "(g (f 1)) (f 1)", 0},
{"different notes stay apart", "(g\n (f 1) ; one\n)\n(h\n (f 1) ; two\n)\n", 0},
{"equal notes share", "(g\n (f 1) ; same\n)\n(h\n (f 1) ; same\n)\n", 3},
{"a shared list brings its subtree", "(a (b (c (d 1)))) (e (b (c (d 1))))", 7},
{"argument orders that disagree", "(a (g) (h)) (b (h) (g))", 2},
{"dotted tails", "(a (f . g)) (b (f . g))", 4},
{"top-level forms never merge", "(f 1) (f 1)", 0},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
built, shared := shareSource(t, tt.src)
checkShared(t, tt.src, shared)
if got := countNodes(built) - countNodes(shared); got != tt.saved {
t.Errorf("saved %d nodes, want %d", got, tt.saved)
}
})
}
}
// TestShareChangesNothingWithoutRepeats: with nothing to share, Share must
// keep Build's ids, so such programs compile to the same bytes as before.
func TestShareChangesNothingWithoutRepeats(t *testing.T) {
src := "(define sq (lambda (n) (* n n)))\n(sq (+ 1 2))\n'(a . b)\n"
built, shared := shareSource(t, src)
if !reflect.DeepEqual(built, shared) {
t.Error("Share changed a program with nothing to share")
}
}
func TestShareKeepsNodesShared(t *testing.T) {
_, shared := shareSource(t, "(g (f 1)) (h (f 1))")
if shared.Forms[0].Children[1] != shared.Forms[1].Children[1] {
t.Fatal("(f 1) was not shared")
}
layers, _ := Layer(shared)
decoded, err := Unlayer(layers)
if err != nil {
t.Fatal(err)
}
if decoded.Forms[0].Children[1] != decoded.Forms[1].Children[1] {
t.Error("Unlayer unfolded the shared node")
}
forms, _, err := FromTree(decoded)
if err != nil {
t.Fatal(err)
}
a := forms[0].(*sexpr.Pair).Cdr.(*sexpr.Pair).Car
b := forms[1].(*sexpr.Pair).Cdr.(*sexpr.Pair).Car
if a != b {
t.Error("FromTree unfolded the shared node into two lists")
}
}
// TestShareTestdata runs Share over every test program, which between them
// repeat plenty of subexpressions.
func TestShareTestdata(t *testing.T) {
paths, _ := lisptest.Files()
examples, _ := lisptest.Examples()
for _, path := range append(paths, examples...) {
src, err := os.ReadFile(path)
if err != nil {
t.Fatal(err)
}
t.Run(strings.TrimSuffix(filepath.Base(path), ".gov.lisp"), func(t *testing.T) {
_, shared := shareSource(t, string(src))
checkShared(t, string(src), shared)
})
}
}
func printAll(forms []sexpr.Value) string {
var lines []string
for _, f := range forms {
lines = append(lines, sexpr.Print(f))
}
return strings.Join(lines, "\n")
}