government / ast / tree_test.go

@ c3dee802a4878505a60909c4f533fffbdfffc936 | history


package ast

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

	"government/sexpr"
)

func mustRead(t *testing.T, src string) []sexpr.Value {
	t.Helper()
	forms, err := sexpr.ReadAll(src)
	if err != nil {
		t.Fatalf("ReadAll(%q): %v", src, err)
	}
	return forms
}

// outline prints a tree as "text#id" atoms and nested lists, so tests can
// state the expected numbering compactly.
func outline(nodes []*Node) string {
	parts := make([]string, len(nodes))
	for i, n := range nodes {
		label := n.Text + "#" + itoa(n.ID)
		if n.IsList() {
			label = "(#" + itoa(n.ID) + " " + outline(n.Children) + ")"
		}
		parts[i] = label
	}
	return strings.Join(parts, " ")
}

func itoa(n uint64) string { return strconv.FormatUint(n, 10) }

func TestToTreeNumbersInPreOrder(t *testing.T) {
	tests := []struct {
		src, want string
	}{
		// The design's worked example.
		{"(+ 1 (* 2 3))", "(#1 +#2 1#3 (#4 *#5 2#6 3#7))"},
		{"1 2", "1#1 2#2"},
		{"'(a . b)", "(#1 quote#2 (#3 a#4 .#5 b#6))"},
		{"(f () T F)", "(#1 f#2 ()#3 T#4 F#5)"},
	}
	for _, tt := range tests {
		tree, err := ToTree(mustRead(t, tt.src))
		if err != nil {
			t.Errorf("ToTree(%s): %v", tt.src, err)
			continue
		}
		if got := outline(tree.Forms); got != tt.want {
			t.Errorf("ToTree(%s) = %s, want %s", tt.src, got, tt.want)
		}
	}
}

func TestToTreeNamespaces(t *testing.T) {
	tree, err := ToTree(mustRead(t, `(define x "s") foo 1.50 -3 '+`))
	if err != nil {
		t.Fatal(err)
	}
	f := tree.Forms
	quoted := f[4].Children[1]
	checks := []struct {
		n    *Node
		ns   Namespace
		text string
	}{
		{f[0].Children[0], NSBuiltin, "define"},
		{f[0].Children[1], NSSymbol, "x"},
		{f[0].Children[2], NSString, "s"},
		{f[1], NSSymbol, "foo"},
		{f[2], NSFloat, "1.5"},
		{f[3], NSInt, "-3"},
		// Quoting does not change a name's namespace; it only changes how
		// the evaluator treats the node.
		{quoted, NSBuiltin, "+"},
	}
	for _, c := range checks {
		if c.n.NS != c.ns || c.n.Text != c.text {
			t.Errorf("node %d = %s %q, want %s %q", c.n.ID, c.n.NS, c.n.Text, c.ns, c.text)
		}
	}
}

func TestQuotedBuiltinBecomesSymbol(t *testing.T) {
	tree, err := ToTree(mustRead(t, "'+"))
	if err != nil {
		t.Fatal(err)
	}
	forms, _, err := FromTree(tree)
	if err != nil {
		t.Fatal(err)
	}
	want := sexpr.List(sexpr.Symbol("quote"), sexpr.Symbol("+"))
	if !reflect.DeepEqual(forms[0], want) {
		t.Errorf("FromTree = %s, want %s", sexpr.Print(forms[0]), sexpr.Print(want))
	}
}

func TestRoundTripTestdata(t *testing.T) {
	files, err := filepath.Glob("../testdata/*.gov.lisp")
	if err != nil || len(files) == 0 {
		t.Fatalf("no testdata: %v", err)
	}
	for _, file := range files {
		src, err := os.ReadFile(file)
		if err != nil {
			t.Fatal(err)
		}
		program := mustRead(t, string(src))
		tree, err := ToTree(program)
		if err != nil {
			t.Errorf("%s: ToTree: %v", file, err)
			continue
		}
		got, _, err := FromTree(tree)
		if err != nil {
			t.Errorf("%s: FromTree: %v", file, err)
			continue
		}
		if !reflect.DeepEqual(got, program) {
			t.Errorf("%s: FromTree(ToTree(p)) differs from p", file)
		}
	}
}

func TestRoundTripEdgeCases(t *testing.T) {
	for _, src := range []string{
		`'(1 2 . 3)`,
		`'((a . b) . (c . ()))`,
		`"" "😀" "\u{0}"`,
		`1.0e+21 -0.0 1.0e-7 0.1`,
		`-9223372036854775808`,
		`'(quote lambda T F ())`,
	} {
		program := mustRead(t, src)
		tree, err := ToTree(program)
		if err != nil {
			t.Errorf("ToTree(%s): %v", src, err)
			continue
		}
		got, _, err := FromTree(tree)
		if err != nil {
			t.Errorf("FromTree(ToTree(%s)): %v", src, err)
			continue
		}
		if !reflect.DeepEqual(got, program) {
			t.Errorf("FromTree(ToTree(%s)) = %v", src, got)
		}
	}
}

func TestEveryTreeNodeEncodes(t *testing.T) {
	tree, err := ToTree(mustRead(t, `(define (f) '(1 . "x")) 2.5 T`))
	if err != nil {
		t.Fatal(err)
	}
	var walk func([]*Node)
	walk = func(nodes []*Node) {
		for _, n := range nodes {
			if _, err := n.OID(); err != nil {
				t.Errorf("node %d: %v", n.ID, err)
			}
			walk(n.Children)
		}
	}
	walk(tree.Forms)
}

func TestOrigins(t *testing.T) {
	tree, err := ToTree(mustRead(t, "(+ 1 (* 2 3))"))
	if err != nil {
		t.Fatal(err)
	}
	forms, origins, err := FromTree(tree)
	if err != nil {
		t.Fatal(err)
	}
	outer := forms[0].(*sexpr.Pair)
	inner := outer.Cdr.(*sexpr.Pair).Cdr.(*sexpr.Pair).Car.(*sexpr.Pair)
	if origins[outer].ID != 1 || origins[inner].ID != 4 {
		t.Errorf("origins: outer #%d, inner #%d; want #1, #4", origins[outer].ID, origins[inner].ID)
	}
}

func TestFromTreeRejects(t *testing.T) {
	atom := func(id uint64, ns Namespace, text string) *Node { return &Node{ID: id, NS: ns, Text: text} }
	list := func(id uint64, children ...*Node) *Node {
		return &Node{ID: id, NS: NSBuiltin, Text: ListNode, Children: children}
	}
	tests := []struct {
		name string
		form *Node
		want string
	}{
		{"empty list node", list(1), "no elements"},
		{"atom with a child", &Node{ID: 1, NS: NSInt, Text: "1", Children: []*Node{atom(2, NSInt, "2")}}, "an atom can have none"},
		{"dot at the start", list(1, atom(2, NSBuiltin, Dot), atom(3, NSSymbol, "a")), "position 1 of 2"},
		{"dot at the end", list(1, atom(2, NSSymbol, "a"), atom(3, NSBuiltin, Dot)), "position 2 of 2"},
		{"two tails", list(1, atom(2, NSSymbol, "a"), atom(3, NSBuiltin, Dot), atom(4, NSSymbol, "b"), atom(5, NSSymbol, "c")), "position 2 of 4"},
		{"bad integer", atom(1, NSInt, "007"), "malformed"},
	}
	for _, tt := range tests {
		_, _, err := FromTree(&Tree{Forms: []*Node{tt.form}})
		if err == nil || !strings.Contains(err.Error(), tt.want) {
			t.Errorf("%s: error = %v, want %q", tt.name, err, tt.want)
		}
	}
}

func TestToTreeRejects(t *testing.T) {
	tests := []struct {
		name string
		form sexpr.Value
		want string
	}{
		// The reader never makes these; ToTree must not turn them into
		// structure if something else does.
		{"symbol named .", sexpr.Symbol(Dot), "builtin name"},
		{"symbol named (...)", sexpr.Symbol(ListNode), "builtin name"},
		{"empty symbol", sexpr.Symbol(""), "empty symbol"},
		{"non-literal value", fakeFunction{}, "cannot be in a program tree"},
	}
	for _, tt := range tests {
		_, err := ToTree([]sexpr.Value{tt.form})
		if err == nil || !strings.Contains(err.Error(), tt.want) {
			t.Errorf("%s: error = %v, want %q", tt.name, err, tt.want)
		}
	}
}

type fakeFunction struct{ sexpr.FunctionBase }

func (fakeFunction) Builtin() bool { return false }
func (fakeFunction) Name() string  { return "" }

func TestBuildCarriesNotes(t *testing.T) {
	src := "; squares\n(define sq (lambda (x)\n  ; the work\n  (* x x)))"
	datums, err := sexpr.ReadProgram(src)
	if err != nil {
		t.Fatal(err)
	}
	tree, err := Build(datums)
	if err != nil {
		t.Fatal(err)
	}
	// (#1 define#2 sq#3 (#4 lambda#5 (#6 x#7) (#8 *#9 x#10 x#11)))
	lambda := tree.Forms[0].Children[2]
	if tree.Forms[0].Note != "squares" || lambda.Children[2].Note != "the work" || lambda.Note != "" {
		t.Errorf("notes: form %q, (* x x) %q, lambda %q", tree.Forms[0].Note, lambda.Children[2].Note, lambda.Note)
	}
	if lambda.Children[2].ID != 8 {
		t.Errorf("(* x x) is node %d, want 8", lambda.Children[2].ID)
	}
}

// TestBuildMatchesToTree checks that building from source and from the
// values it reads as give the same tree, notes aside. A difference would
// mean the reader splits some list differently from DatumOf.
func TestBuildMatchesToTree(t *testing.T) {
	sources := []string{`'(1 . (2 . (3 . ())))`, `'(a . 'b)`, `'(a b . c)`, `(f () T F "s" 1.5 -2)`, `'''x`}
	files, _ := filepath.Glob("../testdata/*.gov.lisp")
	examples, _ := filepath.Glob("../examples/*.gov.lisp")
	for _, f := range append(files, examples...) {
		src, err := os.ReadFile(f)
		if err != nil {
			t.Fatal(err)
		}
		sources = append(sources, string(src))
	}
	for _, src := range sources {
		datums, err := sexpr.ReadProgram(src)
		if err != nil {
			t.Fatal(err)
		}
		fromSource, err := Build(datums)
		if err != nil {
			t.Fatal(err)
		}
		var clear func(n *Node)
		clear = func(n *Node) {
			n.Note = ""
			for _, c := range n.Children {
				clear(c)
			}
		}
		for _, f := range fromSource.Forms {
			clear(f)
		}
		fromValues, err := ToTree(mustRead(t, src))
		if err != nil {
			t.Fatal(err)
		}
		if !reflect.DeepEqual(fromSource, fromValues) {
			t.Errorf("%.40q: the tree from source differs from the tree from its values", src)
		}
	}
}