@ 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)
}
}
}