government / src / ast / unlayer_test.go

@ 27e33aecf4976d7646339e35c5fff6755a29497c | history


package ast

import (
	"os"
	"reflect"
	"strings"
	"testing"

	"government/internal/lisptest"
)

// withCopies adds what policy processing adds on top of Layer's output: a
// copy of every node that has no children, one level down at each depth
// until the bottom. This is the shape Unlayer sees in the real pipeline.
func withCopies(l Layers) Layers {
	n := l.Depth()
	out := Layers{Nodes: make([][]*Node, n), Edges: make([][]Edge, n)}
	for d := range l.Nodes {
		out.Nodes[d] = append(out.Nodes[d], l.Nodes[d]...)
		out.Edges[d] = append(out.Edges[d], l.Edges[d]...)
	}
	for d := 0; d < n-1; d++ {
		for _, node := range out.Nodes[d] {
			if len(childrenIn(out.Edges[d], node)) > 0 {
				continue
			}
			c := &Node{ID: node.ID, NS: node.NS, Text: node.Text}
			out.Nodes[d+1] = append(out.Nodes[d+1], c)
			out.Edges[d] = append(out.Edges[d], Edge{node, c})
		}
	}
	return out
}

func childrenIn(edges []Edge, parent *Node) []*Node {
	var kids []*Node
	for _, e := range edges {
		if e.Parent == parent {
			kids = append(kids, e.Child)
		}
	}
	return kids
}

func roundTrip(t *testing.T, name, src string) {
	t.Helper()
	tree, err := ToTree(mustRead(t, src))
	if err != nil {
		t.Fatalf("%s: ToTree: %v", name, err)
	}
	l, err := Layer(tree)
	if err != nil {
		t.Fatalf("%s: Layer: %v", name, err)
	}
	for _, input := range []struct {
		label  string
		layers Layers
	}{{"layers", l}, {"layers with copies", withCopies(l)}} {
		got, err := Unlayer(input.layers)
		if err != nil {
			t.Errorf("%s: Unlayer(%s): %v", name, input.label, err)
			continue
		}
		if !reflect.DeepEqual(got, tree) {
			t.Errorf("%s: Unlayer(%s) differs from the tree", name, input.label)
		}
	}
}

func TestUnlayerRoundTripTestdata(t *testing.T) {
	files, err := lisptest.Files()
	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)
		}
		roundTrip(t, file, string(src))
	}
}

func TestUnlayerRoundTripShapes(t *testing.T) {
	for _, src := range []string{
		"(+ 1 (* 2 3))",
		"1 (a (b (c)))",
		"'(1 2 . 3)",
		"'((a . b) . c)",
		"(f () T F)",
	} {
		roundTrip(t, src, src)
	}
}

func TestUnlayerCopiesAreSkipped(t *testing.T) {
	l := withCopies(mustLayer(t, "(+ 1 (* 2 3))"))
	// The validator's graph has the design's two copies, +#2' and 1#3'.
	if got := len(l.Nodes[2]); got != 5 {
		t.Fatalf("depth 3 has %d nodes, want 5", got)
	}
	tree, err := Unlayer(l)
	if err != nil {
		t.Fatal(err)
	}
	if got := outline(tree.Forms); got != "(#1 +#2 1#3 (#4 *#5 2#6 3#7))" {
		t.Errorf("Unlayer = %s", got)
	}
}

func TestUnlayerKeepsSharedNodes(t *testing.T) {
	x := &Node{ID: 3, NS: NSSymbol, Text: "x"}
	f := &Node{ID: 2, NS: NSSymbol, Text: "f"}
	g := &Node{ID: 5, NS: NSSymbol, Text: "g"}
	a := &Node{ID: 1, NS: NSBuiltin, Text: ListNode}
	b := &Node{ID: 4, NS: NSBuiltin, Text: ListNode}
	l := Layers{
		Nodes: [][]*Node{{a, b}, {f, x, g}},
		Edges: [][]Edge{{{a, f}, {a, x}, {b, g}, {b, x}}, nil},
	}
	tree, err := Unlayer(l)
	if err != nil {
		t.Fatal(err)
	}
	if tree.Forms[0].Children[1] != tree.Forms[1].Children[0] {
		t.Error("x was duplicated instead of shared")
	}
}

func TestUnlayerRejects(t *testing.T) {
	node := func(id uint64, ns Namespace, text string) *Node { return &Node{ID: id, NS: ns, Text: text} }
	list := func(id uint64) *Node { return node(id, NSBuiltin, ListNode) }
	copyOf := func(n *Node) *Node { return node(n.ID, n.NS, n.Text) }

	one := node(2, NSInt, "1")
	oneCopy := copyOf(one)
	stray := node(3, NSInt, "2")
	root := list(1)

	tests := []struct {
		name   string
		layers Layers
		want   string
	}{
		{
			"copy with a real child",
			Layers{
				Nodes: [][]*Node{{root}, {one}, {oneCopy}, {stray}},
				Edges: [][]Edge{{{root, one}}, {{one, oneCopy}}, {{oneCopy, stray}}, nil},
			},
			"copy GOV.2.2.49 has real child GOV.2.3.50",
		},
		{
			"atom with a real child",
			Layers{
				Nodes: [][]*Node{{root}, {one}, {stray}},
				Edges: [][]Edge{{{root, one}}, {{one, stray}}, nil},
			},
			"atom GOV.2.2.49 has child GOV.2.3.50",
		},
		{
			"list node with no elements",
			Layers{Nodes: [][]*Node{{root}}, Edges: [][]Edge{nil}},
			"list GOV.0.1.1 has no elements",
		},
		{
			"list node whose only child is a copy",
			func() Layers {
				r, c := list(1), list(1)
				return Layers{Nodes: [][]*Node{{r}, {c}}, Edges: [][]Edge{{{r, c}}, nil}}
			}(),
			"list GOV.0.1.1 has no elements",
		},
		{
			". first in a list",
			func() Layers {
				r, dot, a := list(1), node(2, NSBuiltin, Dot), node(3, NSSymbol, "a")
				return Layers{Nodes: [][]*Node{{r}, {dot, a}}, Edges: [][]Edge{{{r, dot}, {r, a}}, nil}}
			}(),
			". at position 1 of 2",
		},
		{
			". as a top-level form",
			Layers{Nodes: [][]*Node{{node(1, NSBuiltin, Dot)}}, Edges: [][]Edge{nil}},
			"depth 1: GOV.0.1.2 is outside a list",
		},
		{
			"node with no parent",
			Layers{
				Nodes: [][]*Node{{root}, {one, stray}},
				Edges: [][]Edge{{{root, one}}, nil},
			},
			"depth 2: GOV.2.3.50 has no parent",
		},
		{
			"mapping that skips a depth",
			Layers{
				Nodes: [][]*Node{{root}, {one}, {stray}},
				Edges: [][]Edge{{{root, one}, {root, stray}}, nil, nil},
			},
			"cert 1: mapping GOV.0.1.1 -> GOV.2.3.50 does not go from depth 1 to 2",
		},
		{
			"two nodes with one id",
			func() Layers {
				r, a, b := list(1), node(2, NSSymbol, "a"), node(2, NSSymbol, "b")
				return Layers{Nodes: [][]*Node{{r}, {a, b}}, Edges: [][]Edge{{{r, a}, {r, b}}, nil}}
			}(),
			"share node id 2",
		},
		{
			"no forms",
			Layers{},
			"no top-level forms",
		},
	}
	seen := map[string]string{}
	for _, tt := range tests {
		_, err := Unlayer(tt.layers)
		if err == nil || !strings.Contains(err.Error(), tt.want) {
			t.Errorf("%s: error = %v, want %q", tt.name, err, tt.want)
			continue
		}
		// Cases that expect the same message are the same mistake; any other
		// pair must be told apart.
		if prev, dup := seen[err.Error()]; dup && prev != tt.want {
			t.Errorf("%s gives the same error as a different case: %v", tt.name, err)
		}
		seen[err.Error()] = tt.want
	}
}