government / src / ast / share_test.go

@ 52e34195229c6f9cac00b26701541ddac8a02b66 | history


package ast

import (
	"os"
	"path/filepath"
	"reflect"
	"strings"
	"testing"

	"nmyk.io/government/internal/lisptest"
	"nmyk.io/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")
}