@ ce159ec40272fb3caed2436702b1426f1550e47d | history
package ast
import (
"os"
"path/filepath"
"reflect"
"strings"
"testing"
)
// 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 := 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)
}
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
}
}