Mojom frontend: Detect Ill-founded Types

mojom/mojom_tool/utils/wellfounded_graphs_test.go

 package utils
 
 import (
         "bytes"
         "fmt"
         "strings"
         "testing"
 )
 
 ////////////////////////////////////////////////////
 // SimpleNode type
 ////////////////////////////////////////////////////
 
 // SimpleNode is a simple implementation of the |Node| interface used
 // for testing.
 type SimpleNode struct {
         // The value of this node
         value int
 
         // Is this node a square node?
         isSquare bool
 
-        // The list of out-edges. The elements will be *SimpleNodes.
-        edges []Node
+        // The list of out-edges.
+        edges []OutEdge
 
         // Cache the fact that |SetKnownWellFounded| has been invoked.
         knownWellFounded bool
 }
 
-func (node *SimpleNode) DebugName() string {
+func (node *SimpleNode) Name() string {
         return fmt.Sprintf("Node%d", node.value)
 }
 
-func (node *SimpleNode) OutEdges() []Node {
+func (node *SimpleNode) OutEdges() []OutEdge {
         return node.edges
 }
 
 func (node *SimpleNode) IsSquare() bool {
         return node.isSquare
 }
 
 func (node *SimpleNode) KnownWellFounded() bool {
         return node.knownWellFounded
 }
 
 func (node *SimpleNode) SetKnownWellFounded() {
         if node.knownWellFounded {
-                panic(fmt.Sprintf("SetKnownWellFounded invoked twice on %s", node.DebugName()))
+                panic(fmt.Sprintf("SetKnownWellFounded invoked twice on %s", node.Name()))
         }
         node.knownWellFounded = true
 }
 
 //Creates a new SimpleNode.
 func NewNode(value, numEdges int, isSquare bool) *SimpleNode {
         node := new(SimpleNode)
         node.value = value
-        node.edges = make([]Node, numEdges)
+        node.edges = make([]OutEdge, numEdges)
         node.isSquare = isSquare
         return node
 }
 
 ////////////////////////////////////////////////////
 // Test Utilities
 ////////////////////////////////////////////////////
 
 // Builds a test graph containing only circle nodes.
 // The connection matrix should have the following form:
@@ skipping 14 matching lines @@
                         squareMap[n] = true
                 }
         }
         nodes = make([]*SimpleNode, len(connectionMatrix))
         for index, connectionList := range connectionMatrix {
                 _, isSquare := squareMap[index]
                 nodes[index] = NewNode(index, len(connectionList), isSquare)
         }
         for index, connectionList := range connectionMatrix {
                 for i, target := range connectionList {
-                        nodes[index].edges[i] = nodes[target]
+                        nodes[index].edges[i] = OutEdge{"", nodes[target]}
                 }
         }
         return
 }
 
 // expectedDebugData is used to store an expectation for the value of the |debugData| populated
 // by the ethod |checkWellFounded|. This data captures the result of phase 1 of the algorithm.
 type expectedDebugData struct {
         initialPendingSet    []string
         initialFoundationSet []string
@@ skipping 10 matching lines @@
         return compareNodeSlice(expected.initialFoundationSet, actual.initialFoundationSet, "initialFoundationSet")
 }
 
 func compareNodeSlice(expected []string, actual []Node, name string) error {
         expectedMap := make(map[string]bool)
         actualMap := make(map[string]bool)
         for _, n := range expected {
                 expectedMap[n] = true
         }
         for _, n := range actual {
-                actualMap[n.DebugName()] = true
+                actualMap[n.Name()] = true
         }
         for _, n := range expected {
                 if _, ok := actualMap[n]; !ok {
                         return fmt.Errorf("%s: missing %s, actual: %s", name, n, NodeSliceToString(actual))
                 }
         }
         for _, n := range actual {
-                if _, ok := expectedMap[n.DebugName()]; !ok {
-                        return fmt.Errorf("%s: unexpected: %s, expected: %v, actual: %s", name, n.DebugName(), expected, NodeSliceToString(actual))
+                if _, ok := expectedMap[n.Name()]; !ok {
+                        return fmt.Errorf("%s: unexpected: %s, expected: %v, actual: %s", name, n.Name(), expected, NodeSliceToString(actual))
                 }
         }
         return nil
 }
 
 func NodeSliceToString(nodeSlice []Node) string {
         var buffer bytes.Buffer
         fmt.Fprintf(&buffer, "[")
         first := true
         for _, n := range nodeSlice {
                 if !first {
                         fmt.Fprintf(&buffer, ", ")
                 }
-                fmt.Fprintf(&buffer, "%s", n.DebugName())
+                fmt.Fprintf(&buffer, "%s", n.Name())
                 first = false
         }
         fmt.Fprintln(&buffer, "]")
         return buffer.String()
 }
 
 ////////////////////////////////////////////////////
 // Tests
 ////////////////////////////////////////////////////
 
@@ skipping 294 matching lines @@
                 }
                 if len(c.expectedPathA) == 0 {
                         if cycleDescription != nil {
                                 t.Fatalf("Case %dA: Detected a cycle: %s", i, cycleDescription)
                         }
                 } else {
                         if cycleDescription == nil {
                                 t.Fatalf("Case %d: Expected a cycle.", i)
                         }
                         if !strings.Contains(cycleDescription.String(), fmt.Sprintf("first:%s", c.expectedFirstA)) {
-                                t.Fatalf("Case %d: got=%s expectedFirst=%q", i, cycleDescription.String(), c.expectedFirstA)
+                                t.Fatalf("Case %d: got=%s expectedFirstA=%q", i, cycleDescription.String(), c.expectedFirstA)
                         }
                         if !strings.Contains(cycleDescription.String(), fmt.Sprintf("last:%s", c.expectedLastA)) {
-                                t.Fatalf("Case %d: got=%s expectedLast=%q", i, cycleDescription.String(), c.expectedLastA)
+                                t.Fatalf("Case %d: got=%s expectedLastA=%q", i, cycleDescription.String(), c.expectedLastA)
                         }
                         if !strings.Contains(cycleDescription.String(), fmt.Sprintf("{%s}", c.expectedPathA)) {
-                                t.Fatalf("Case %d: got=%s expectedPath=%q", i, cycleDescription.String(), c.expectedPathA)
+                                t.Fatalf("Case %d: got=%s expectedPathA=%q", i, cycleDescription.String(), c.expectedPathA)
                         }
                 }
 
                 // Test from root=Node1
                 if len(graph) > 1 {
                         dbgData := debugData{}
                         cycleDescription := checkWellFounded(graph[1], &dbgData)
                         if err := compareDebugData(&c.expectedDebugDataB, &dbgData); err != nil {
                                 t.Fatalf("Case %dB: %s", i, err.Error())
                         }
                         if len(c.expectedPathB) == 0 {
                                 if cycleDescription != nil {
                                         t.Fatalf("Case %dB: Detected a cycle: %s", i, cycleDescription)
                                 }
                         } else {
                                 if cycleDescription == nil {
                                         t.Fatalf("Case %dB: Expected a cycle.", i)
                                 }
                                 if !strings.Contains(cycleDescription.String(), fmt.Sprintf("first:%s", c.expectedFirstB)) {
-                                        t.Fatalf("Case %dB: got=%s expectedFirst=%q", i, cycleDescription.String(), c.expectedFirstB)
+                                        t.Fatalf("Case %dB: got=%s expectedFirstB=%q", i, cycleDescription.String(), c.expectedFirstB)
                                 }
                                 if !strings.Contains(cycleDescription.String(), fmt.Sprintf("last:%s", c.expectedLastB)) {
-                                        t.Fatalf("Case %dB: got=%s expectedLast=%q", i, cycleDescription.String(), c.expectedLastB)
+                                        t.Fatalf("Case %dB: got=%s expectedLastB=%q", i, cycleDescription.String(), c.expectedLastB)
                                 }
                                 if !strings.Contains(cycleDescription.String(), fmt.Sprintf("{%s}", c.expectedPathB)) {
-                                        t.Fatalf("Case %dB: got=%s expectedPath=%q", i, cycleDescription.String(), c.expectedPathB)
+                                        t.Fatalf("Case %dB: got=%s expectedPathB=%q", i, cycleDescription.String(), c.expectedPathB)
                                 }
                         }
                 }
         }
 }
 
 // TestWellFoundedIsWellFounded tests the function |checkWellFounded| on graphs
 // that contain both circles and squares and are well-founded.
 func TestWellFoundedIsWellFounded(t *testing.T) {
         cases := []WellFoundedGraphTestCase{
@@ skipping 836 matching lines @@
                                 if !strings.Contains(cycleDescription.String(), fmt.Sprintf("last:%s", c.expectedLastB)) {
                                         t.Fatalf("Case %dB: got=%s expectedLast=%q", i, cycleDescription.String(), c.expectedLastB)
                                 }
                                 if !strings.Contains(cycleDescription.String(), fmt.Sprintf("{%s}", c.expectedPathB)) {
                                         t.Fatalf("Case %dB: got=%s expectedPath=%q", i, cycleDescription.String(), c.expectedPathB)
                                 }
                         }
                 }
         }
 }