government / src / lisp2gov / share_test.go

@ 761f3b207460ae5814dd76a326ce14777e29e659 | history


package lisp2gov_test

import (
	"bytes"
	"fmt"
	"strings"
	"testing"
	"time"

	"government/lisp2gov"
	"government/program"
	"government/sexpr"
)

// doubling nests k copies deep: each level uses the one below twice, so
// written out as a tree the program has about 2^k leaves, and its value
// is 2^k.
func doubling(k int) string {
	e := "1"
	for range k {
		e = "(+ (* 1 " + e + ") (- " + e + " 0))"
	}
	return e
}

// distinctPairs counts the cons cells reachable from the forms, each once,
// which is how much memory the decoded program really holds.
func distinctPairs(forms []sexpr.Value) int {
	seen := map[*sexpr.Pair]bool{}
	var walk func(v sexpr.Value)
	walk = func(v sexpr.Value) {
		p, ok := v.(*sexpr.Pair)
		if !ok || seen[p] {
			return
		}
		seen[p] = true
		walk(p.Car)
		walk(p.Cdr)
	}
	for _, f := range forms {
		walk(f)
	}
	return len(seen)
}

func load(t *testing.T, src string, opts lisp2gov.Options) ([]byte, *program.Program) {
	t.Helper()
	data, err := lisp2gov.Compile(src, opts)
	if err != nil {
		t.Fatal(err)
	}
	p, err := program.Load(data, program.Options{At: time.Now()})
	if err != nil {
		t.Fatal(err)
	}
	return data, p
}

func run(t *testing.T, p *program.Program) string {
	t.Helper()
	var out bytes.Buffer
	if err := p.Run(&out); err != nil {
		t.Fatal(err)
	}
	return strings.TrimSpace(out.String())
}

// TestNestedCopiesStaySmall: shared, a program that is a million nodes as
// a tree compiles to a couple of hundred, decodes to as many lists in
// memory, and still evaluates to the right answer.
//
// At 20 levels the source alone is 18 MB, the 2^20 copies written out, and
// reading it takes several seconds; -short stops at 12.
func TestNestedCopiesStaySmall(t *testing.T) {
	for _, k := range []int{12, 20} {
		if k > 12 && testing.Short() {
			t.Skip("20 levels is an 18 MB source")
		}
		data, p := load(t, doubling(k), lisp2gov.Options{})
		if p.Nodes > 8*k+2 {
			t.Errorf("%d levels: %d nodes; sharing should keep it near 8 per level", k, p.Nodes)
		}
		if len(data) > 5000*k {
			t.Errorf("%d levels: %d bytes", k, len(data))
		}
		// Three lists of three elements per level: nine cons cells.
		if n := distinctPairs(p.Forms); n > 9*k+3 {
			t.Errorf("%d levels: decoded program holds %d cons cells; the DAG was unfolded", k, n)
		}
		if got, want := run(t, p), fmt.Sprint(1<<k); got != want {
			t.Errorf("%d levels: value %s, want %s", k, got, want)
		}
	}
}

// TestSharingOnlyEverShrinks compares the two modes on the same programs:
// identical results, and the shared one never bigger.
func TestSharingOnlyEverShrinks(t *testing.T) {
	for _, src := range []string{
		"(+ 1 (* 2 3))",
		doubling(6),
		"(define f (lambda (x) (cons (car x) (car x))))\n(f '(1 2))\n(cons (car '(1 2)) (cdr '(1 2)))",
	} {
		shared, sp := load(t, src, lisp2gov.Options{})
		full, fp := load(t, src, lisp2gov.Options{NoShare: true})
		if a, b := run(t, sp), run(t, fp); a != b {
			t.Errorf("%s: %q shared, %q not", src, a, b)
		}
		if len(shared) > len(full) || sp.Nodes > fp.Nodes {
			t.Errorf("%s: shared is %d bytes and %d nodes, unshared %d bytes and %d nodes",
				src, len(shared), sp.Nodes, len(full), fp.Nodes)
		}
	}
	_, sp := load(t, doubling(6), lisp2gov.Options{})
	_, fp := load(t, doubling(6), lisp2gov.Options{NoShare: true})
	t.Logf("doubling(6): %d nodes shared, %d not", sp.Nodes, fp.Nodes)
	if sp.Nodes*4 > fp.Nodes {
		t.Errorf("doubling(6) shared %d nodes of %d; expected far fewer", sp.Nodes, fp.Nodes)
	}
}