government / ast / layer_test.go

@ cdf2d0cb24bc5f0af81926cf5d0b2a709fd84abc | history


package ast

import (
	"strings"
	"testing"
)

func mustLayer(t *testing.T, src string) Layers {
	t.Helper()
	tree, err := ToTree(mustRead(t, src))
	if err != nil {
		t.Fatal(err)
	}
	l, err := Layer(tree)
	if err != nil {
		t.Fatal(err)
	}
	return l
}

func oidString(t *testing.T, n *Node) string {
	t.Helper()
	oid, err := n.OID()
	if err != nil {
		t.Fatal(err)
	}
	return strings.Replace(oid.String(), Root, "GOV", 1)
}

// TestWorkedExample checks Layer against the table in DESIGN.md's worked
// example, written in the same OID notation.
func TestWorkedExample(t *testing.T) {
	l := mustLayer(t, "(+ 1 (* 2 3))")
	wantNodes := [][]string{
		{"GOV.0.1.1"},
		{"GOV.0.2.21", "GOV.2.3.49", "GOV.0.4.1"},
		{"GOV.0.5.23", "GOV.2.6.50", "GOV.2.7.51"},
	}
	wantEdges := [][]string{
		{"GOV.0.1.1 -> GOV.0.2.21", "GOV.0.1.1 -> GOV.2.3.49", "GOV.0.1.1 -> GOV.0.4.1"},
		{"GOV.0.4.1 -> GOV.0.5.23", "GOV.0.4.1 -> GOV.2.6.50", "GOV.0.4.1 -> GOV.2.7.51"},
		nil,
	}
	if l.Depth() != 3 {
		t.Fatalf("Depth = %d, want 3", l.Depth())
	}
	for d := range wantNodes {
		var nodes []string
		for _, n := range l.Nodes[d] {
			nodes = append(nodes, oidString(t, n))
		}
		if got, want := strings.Join(nodes, ", "), strings.Join(wantNodes[d], ", "); got != want {
			t.Errorf("depth %d nodes = %s, want %s", d+1, got, want)
		}
		var edges []string
		for _, e := range l.Edges[d] {
			edges = append(edges, oidString(t, e.Parent)+" -> "+oidString(t, e.Child))
		}
		if got, want := strings.Join(edges, ", "), strings.Join(wantEdges[d], ", "); got != want {
			t.Errorf("cert %d mappings = %s, want %s", d+1, got, want)
		}
	}
}

func TestLayerShapes(t *testing.T) {
	tests := []struct {
		src   string
		depth int
		nodes []int // node count per depth
		edges []int // mapping count per cert
	}{
		{"42", 1, []int{1}, []int{0}},
		{"1 2 3", 1, []int{3}, []int{0}},
		{"(f)", 2, []int{1, 1}, []int{1, 0}},
		// The shallow 1 is not padded: depth 2 has only the list's three
		// elements, and nothing at depth 3 or 4 is written for the 1.
		{"1 (a (b (c)))", 4, []int{2, 2, 2, 1}, []int{2, 2, 1, 0}},
		{"'(a . b)", 3, []int{1, 2, 3}, []int{2, 3, 0}},
	}
	for _, tt := range tests {
		l := mustLayer(t, tt.src)
		if l.Depth() != tt.depth {
			t.Errorf("%s: Depth = %d, want %d", tt.src, l.Depth(), tt.depth)
			continue
		}
		for d := 0; d < tt.depth; d++ {
			if len(l.Nodes[d]) != tt.nodes[d] || len(l.Edges[d]) != tt.edges[d] {
				t.Errorf("%s: depth %d has %d nodes and %d edges, want %d and %d",
					tt.src, d+1, len(l.Nodes[d]), len(l.Edges[d]), tt.nodes[d], tt.edges[d])
			}
		}
	}
}

func TestLayerSortsById(t *testing.T) {
	// Children listed out of id order.
	a := &Node{ID: 3, NS: NSInt, Text: "1"}
	b := &Node{ID: 2, NS: NSInt, Text: "2"}
	list := &Node{ID: 1, NS: NSBuiltin, Text: ListNode, Children: []*Node{a, b}}
	l, err := Layer(&Tree{Forms: []*Node{list}})
	if err != nil {
		t.Fatal(err)
	}
	if l.Nodes[1][0] != b || l.Edges[0][0].Child != b {
		t.Error("depth 2 is not in id order")
	}
}

func TestLayerSharedNode(t *testing.T) {
	x := &Node{ID: 4, NS: NSSymbol, Text: "x"}
	f := &Node{ID: 2, NS: NSSymbol, Text: "f"}
	g := &Node{ID: 6, NS: NSSymbol, Text: "g"}
	inner := &Node{ID: 5, NS: NSBuiltin, Text: ListNode, Children: []*Node{g, x}}

	sameDepth := &Node{ID: 1, NS: NSBuiltin, Text: ListNode, Children: []*Node{f, x}}
	other := &Node{ID: 3, NS: NSBuiltin, Text: ListNode, Children: []*Node{g, x}}
	l, err := Layer(&Tree{Forms: []*Node{sameDepth, other}})
	if err != nil {
		t.Fatalf("shared node at one depth: %v", err)
	}
	if len(l.Nodes[1]) != 3 || len(l.Edges[0]) != 4 {
		t.Errorf("depth 2: %d nodes, %d edges; want 3 and 4", len(l.Nodes[1]), len(l.Edges[0]))
	}

	twoDepths := &Node{ID: 1, NS: NSBuiltin, Text: ListNode, Children: []*Node{f, x, inner}}
	if _, err := Layer(&Tree{Forms: []*Node{twoDepths}}); err == nil || !strings.Contains(err.Error(), "depths 2 and 3") {
		t.Errorf("shared node at two depths: error = %v", err)
	}
}

func TestLayerEmptyProgram(t *testing.T) {
	if _, err := Layer(&Tree{}); err == nil {
		t.Error("empty program layered without error")
	}
}