@ 9691322d33532d2feea494209d4df63e32ee99be | history
package lisp2gov_test
import (
"bytes"
"fmt"
"strings"
"testing"
"time"
"nmyk.io/government/lisp2gov"
"nmyk.io/government/program"
"nmyk.io/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)
}
}