Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1593)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: mojom/mojom_parser/utils/wellfounded_graphs_test.go

Issue 1908273003: Mojom frontend: An algorithm for detecting ill-founded nodes in a graph. (Closed) Base URL: https://github.com/domokit/mojo.git@master
Patch Set: Responding to code review. Created 4 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « mojom/mojom_parser/utils/wellfounded_graphs.go ('k') | no next file » | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: mojom/mojom_parser/utils/wellfounded_graphs_test.go
diff --git a/mojom/mojom_parser/utils/wellfounded_graphs_test.go b/mojom/mojom_parser/utils/wellfounded_graphs_test.go
new file mode 100644
index 0000000000000000000000000000000000000000..958fa9a5882c7f2897b8f85b12c92a98a60508da
--- /dev/null
+++ b/mojom/mojom_parser/utils/wellfounded_graphs_test.go
@@ -0,0 +1,1349 @@
+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
+
+ // Cache the fact that |SetKnownWellFounded| has been invoked.
+ knownWellFounded bool
+}
+
+func (node *SimpleNode) DebugName() string {
+ return fmt.Sprintf("Node%d", node.value)
+}
+
+func (node *SimpleNode) OutEdges() []Node {
+ 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()))
+ }
+ 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.isSquare = isSquare
+ return node
+}
+
+////////////////////////////////////////////////////
+// Test Utilities
+////////////////////////////////////////////////////
+
+// Builds a test graph containing only circle nodes.
+// The connection matrix should have the following form:
+// connectionMatrix[i][j] = k indicates that there is an edge in the graph
+// from Node i to Node K. k must be less than len(connectionMatrix).
+func buildCircleTestGraph(connectionMatrix [][]int) (nodes []*SimpleNode) {
+ return buildTestGraph(connectionMatrix, nil)
+}
+
+// Builds a test graph. The connection matrix should have the following form:
+// connectionMatrix[i][j] = k indicates that there is an edge in the graph
+// from Node i to Node K. k must be less than len(connectionMatrix).
+// If |squares| is not nil then it must contain the list of indices of the nodes that are squares.
+func buildTestGraph(connectionMatrix [][]int, squares []int) (nodes []*SimpleNode) {
+ squareMap := make(map[int]bool)
+ if squares != nil {
+ for _, n := range squares {
+ 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]
+ }
+ }
+ 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
+}
+
+func compareDebugData(expected *expectedDebugData, actual *debugData) error {
+ if expected == nil {
+ panic("expected cannot be nil")
+ return nil
+ }
+ if err := compareNodeSlice(expected.initialPendingSet, actual.initialPendingSet, "initialPendingSet"); err != nil {
+ return err
+ }
+ 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
+ }
+ 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))
+ }
+ }
+ 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())
+ first = false
+ }
+ fmt.Fprintln(&buffer, "]")
+ return buffer.String()
+}
+
+////////////////////////////////////////////////////
+// Tests
+////////////////////////////////////////////////////
+
+type WellFoundedGraphTestCase struct {
+ // The connection matrix describing the digraph for this case.
+ connectionMatrix [][]int
+
+ // If this is non-nil it should be the list of indices of the square nodes.
+ squares []int
+
+ // The expected result when searching from Node0
+ expectedFirstA, expectedLastA, expectedPathA string
+
+ // The expected result when searching from Node1
+ expectedFirstB, expectedLastB, expectedPathB string
+
+ expectedDebugDataA, expectedDebugDataB expectedDebugData
+}
+
+// TestWellFoundedIsWellFoundedCirclesOnly tests the function |checkWellFounded|
+// on graphs that are well-founded and that contain only circles. For
+// graphs that contain only circles being well-founded is equivalent to
+// being acyclic.
+func TestWellFoundedIsWellFoundedCirclesOnly(t *testing.T) {
+ cases := []WellFoundedGraphTestCase{
+
+ // Case: Single node, no self-loop
+ {
+ connectionMatrix: [][]int{
+ {},
+ },
+ },
+
+ // Case: Linear chain of length 4
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0 -> 1
+ {2}, // 1 -> 2
+ {3}, // 2 -> 3
+ {}, // 3 -> ||
+ },
+ },
+
+ // Case: Diamond
+ //
+ // 0
+ // 1 2
+ // 3
+ {
+ connectionMatrix: [][]int{
+ {1, 2}, // 0
+ {3}, // 1
+ {3}, // 2
+ {}, // 3
+ },
+ },
+
+ // Case: Complex, double diamond with a tail
+ //
+ // 0
+ // 1 2
+ // 6 3 4
+ // 5
+ {
+ connectionMatrix: [][]int{
+ {1, 2}, // 0
+ {3, 6}, // 1
+ {3, 4}, // 2
+ {5}, // 3
+ {5}, // 4
+ {}, // 5
+ {}, // 6
+ },
+ },
+
+ // Case: 0 and 1 are independent roots
+ //
+ // 0 1
+ // 7 2 |
+ // 6 3 4
+ // 5
+ {
+ connectionMatrix: [][]int{
+ {7, 2}, // 0
+ {4}, // 1
+ {3, 4}, // 2
+ {5}, // 3
+ {5}, // 4
+ {}, // 5
+ {}, // 6
+ {3, 6}, // 7
+ },
+ },
+ }
+
+ for i, c := range cases {
+ graph := buildCircleTestGraph(c.connectionMatrix)
+ dbgData := debugData{}
+ cycleDescription := checkWellFounded(graph[0], &dbgData)
+ if cycleDescription != nil {
+ t.Fatalf("Case %dA: Detected a cycle: %s", i, cycleDescription)
+ }
+ if err := compareDebugData(&c.expectedDebugDataA, &dbgData); err != nil {
+ t.Fatalf("Case %dA: %s", i, err.Error())
+ }
+ if len(graph) > 1 {
+ dbgData := debugData{}
+ cycleDescription = checkWellFounded(graph[1], &dbgData)
+ if cycleDescription != nil {
+ t.Fatalf("Case %dB: Detected a cycle: %s", i, cycleDescription)
+ }
+ if err := compareDebugData(&c.expectedDebugDataB, &dbgData); err != nil {
+ t.Fatalf("Case %dB: %s", i, err.Error())
+ }
+ }
+ }
+}
+
+// TestWellFoundedNotWellFoundedCirclesOnly tests the function |checkWellFounded|
+// on graphs that are not well-founded and that contain only circles. For
+// graphs that contain only circles being well-founded is equivalent to
+// being acyclic.
+func TestWellFoundedNotWellFoundedCirclesOnly(t *testing.T) {
+
+ cases := []WellFoundedGraphTestCase{
+
+ // Case: Single node with self-loop
+ {
+ connectionMatrix: [][]int{
+ {0},
+ },
+
+ expectedFirstA: "Node0",
+ expectedLastA: "Node0",
+ expectedPathA: "Node0",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0"},
+ },
+ },
+
+ // Case: Loop of length 4
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0 -> 1
+ {2}, // 1 -> 2
+ {3}, // 2 -> 3
+ {0}, // 3 -> 0
+ },
+
+ expectedFirstA: "Node0",
+ expectedLastA: "Node3",
+ expectedPathA: "Node0, Node1, Node2, Node3",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3"},
+ },
+
+ expectedFirstB: "Node1",
+ expectedLastB: "Node0",
+ expectedPathB: "Node1, Node2, Node3, Node0",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3"},
+ },
+ },
+
+ // Case: Diamond with a loop-back from bottom to top
+ //
+ // 0 <--
+ // 1 2 |
+ // 3 ---|
+ {
+ connectionMatrix: [][]int{
+ {1, 2}, // 0
+ {3}, // 1
+ {3}, // 2
+ {0}, // 3
+ },
+ expectedFirstA: "Node0",
+ expectedLastA: "Node3",
+ expectedPathA: "Node0, Node1, Node3",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3"},
+ },
+
+ expectedFirstB: "Node1",
+ expectedLastB: "Node0",
+ expectedPathB: "Node1, Node3, Node0",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3"},
+ },
+ },
+
+ // Case: Complex, double diamond with a tail and a bridge and
+ // a loop back to the top
+ //
+ // 0
+ // 1 2 <----
+ // 6 3 4 |
+ // 5 ------|
+ {
+ connectionMatrix: [][]int{
+ {1, 2}, // 0
+ {3, 6}, // 1
+ {3, 4}, // 2
+ {5}, // 3
+ {5}, // 4
+ {2}, // 5
+ {}, // 6
+ },
+ expectedFirstA: "Node3",
+ expectedLastA: "Node2",
+ expectedPathA: "Node3, Node5, Node2",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3", "Node4", "Node5"},
+ },
+
+ expectedFirstB: "Node3",
+ expectedLastB: "Node2",
+ expectedPathB: "Node3, Node5, Node2",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node1", "Node2", "Node3", "Node4", "Node5"},
+ },
+ },
+
+ // Case: More complex
+ //
+ //
+ // 0
+ // 1 2 3 <------
+ // 4 5 |
+ // 6 8 7 |
+ // 11 9 -------|
+ // 12 10
+ {
+ connectionMatrix: [][]int{
+ {1, 2, 3}, // 0
+ {4}, // 1
+ {4, 5}, // 2
+ {5}, // 3
+ {6}, // 4
+ {6, 7, 8}, // 5
+ {11}, // 6
+ {}, // 7
+ {9}, // 8
+ {10, 3}, // 9
+ {}, // 10
+ {12}, // 11
+ {}, // 12
+ },
+ expectedFirstA: "Node5",
+ expectedLastA: "Node3",
+ expectedPathA: "Node5, Node8, Node9, Node3",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node2", "Node3", "Node5", "Node8", "Node9"},
+ },
+ },
+
+ // Case: No loop from 0 but loop from 1
+ //
+ //
+ // 1
+ // 0 2 3 <----
+ // 4 5 |
+ // 6 8 7 |
+ // 11 9 ------|
+ // 12 10
+ {
+ connectionMatrix: [][]int{
+ {4}, // 0
+ {0, 2, 3}, // 1
+ {4, 5}, // 2
+ {5}, // 3
+ {6}, // 4
+ {6, 7, 8}, // 5
+ {11}, // 6
+ {}, // 7
+ {9}, // 8
+ {10, 3}, // 9
+ {}, // 10
+ {12}, // 11
+ {}, // 12
+ },
+ expectedFirstB: "Node5",
+ expectedLastB: "Node3",
+ expectedPathB: "Node5, Node8, Node9, Node3",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node1", "Node2", "Node3", "Node5", "Node8", "Node9"},
+ },
+ },
+ }
+
+ for i, c := range cases {
+ graph := buildCircleTestGraph(c.connectionMatrix)
+ // Test from root=Node0
+ dbgData := debugData{}
+ cycleDescription := checkWellFounded(graph[0], &dbgData)
+ if err := compareDebugData(&c.expectedDebugDataA, &dbgData); err != nil {
+ t.Fatalf("Case %dA: %s", i, err.Error())
+ }
+ 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)
+ }
+ if !strings.Contains(cycleDescription.String(), fmt.Sprintf("last:%s", c.expectedLastA)) {
+ t.Fatalf("Case %d: got=%s expectedLast=%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)
+ }
+ }
+
+ // 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)
+ }
+ 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)
+ }
+ }
+ }
+ }
+}
+
+// TestWellFoundedIsWellFounded tests the function |checkWellFounded| on graphs
+// that contain both circles and squares and are well-founded.
+func TestWellFoundedIsWellFounded(t *testing.T) {
+ cases := []WellFoundedGraphTestCase{
+
+ // Case: Single square node, no self-loop
+ {
+ connectionMatrix: [][]int{
+ {},
+ },
+ squares: []int{0},
+ },
+
+ // Case: Loop through right branch but not through left branch.
+ //
+ // [0] <--|
+ // 1 2--|
+ {
+ connectionMatrix: [][]int{
+ {1, 2}, // 0
+ {}, // 1
+ {0}, // 2
+ },
+ squares: []int{0},
+ },
+
+ // Case: Loop through left branch but not through rigt branch.
+ //
+ // [0] <--|
+ // 2 1--|
+ {
+ connectionMatrix: [][]int{
+ {1, 2}, // 0
+ {0}, // 1
+ {}, // 2
+ },
+ squares: []int{0},
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node1"},
+ initialFoundationSet: []string{"Node0"},
+ },
+ },
+
+ // Case: Loop through right branch below the root
+ //
+ // 0 <---|
+ // [1] |
+ // 2 3--|
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0
+ {2, 3}, // 1
+ {}, // 2
+ {0}, // 3
+ },
+ squares: []int{1},
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node3"},
+ initialFoundationSet: []string{"Node0"},
+ },
+ },
+
+ // Case: Loop through left branch below the root
+ //
+ // 0 <---|
+ // [1] |
+ // 3 2--|
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0
+ {2, 3}, // 1
+ {0}, // 2
+ {}, // 3
+ },
+ squares: []int{1},
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node2"},
+ initialFoundationSet: []string{"Node0"},
+ },
+ },
+
+ // Case: We know 0 is well-founded before we see the loop from 4 to 0
+ //
+ //
+ // 1 <-- [0] <--|
+ // [2] |
+ // 3 4--|
+ {
+ connectionMatrix: [][]int{
+ {1, 2}, // 0
+ {}, // 1
+ {3, 4}, // 2
+ {}, // 3
+ {0}, // 4
+ },
+ squares: []int{0, 2},
+ },
+
+ // Case: Well-founded becuase of 8
+ // 0
+ // 1
+ // 2 <--
+ // 3 |
+ // 8 <-- [4] |
+ // 5 |
+ // 6---|
+ // 7
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0
+ {2}, // 1
+ {3}, // 2
+ {4}, // 3
+ {5, 8}, // 4
+ {6}, // 5
+ {2, 7}, // 6
+ {}, // 7
+ {}, // 8
+ },
+ squares: []int{4},
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node5", "Node6"},
+ initialFoundationSet: []string{"Node2"},
+ },
+ },
+
+ // Case: Double loops through right branches
+ //
+ // 0 <---|
+ // [1]<---|-----
+ // 2 3--| |
+ // [4] |
+ // 5 6 7 --|
+ // 8 9 10
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0
+ {2, 3}, // 1
+ {}, // 2
+ {0, 4}, // 3
+ {5, 6, 7}, // 4
+ {8}, // 5
+ {9}, // 6
+ {1, 10}, // 7
+ {}, // 8
+ {}, // 9
+ {}, // 10
+ },
+ squares: []int{1, 4},
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node3"},
+ initialFoundationSet: []string{"Node0"},
+ },
+ },
+
+ // Case: Double loops through left branches
+ //
+ // 0 <---|
+ // [1]<---|-----
+ // 3 2--| |
+ // [4] |
+ // 7 6 5 --|
+ // 8 9 10
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0
+ {2, 3}, // 1
+ {0, 4}, // 2
+ {}, // 3
+ {5, 6, 7}, // 4
+ {1, 10}, // 5
+ {9}, // 6
+ {8}, // 7
+ {}, // 8
+ {}, // 9
+ {}, // 10
+ },
+ squares: []int{1, 4},
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node2", "Node5"},
+ initialFoundationSet: []string{"Node0", "Node1"},
+ },
+ },
+
+ // Case: Crossing up and down on right
+ //
+ // 0 -----|
+ // 1 |
+ // [2] <---|-----
+ // 3 4 <-| |
+ // 5 |
+ // 6 |
+ // 7 -------|
+ //
+ {
+ connectionMatrix: [][]int{
+ {1, 4}, // 0
+ {2}, // 1
+ {3, 4}, // 2
+ {}, // 3
+ {5}, // 4
+ {6}, // 5
+ {7}, // 6
+ {2}, // 7
+ },
+ squares: []int{2},
+ },
+
+ // Case: Crossing up and down on left
+ //
+ // 0 -----|
+ // 1 |
+ // [2] <---|-----
+ // 4 3 <-| |
+ // 5 |
+ // 6 |
+ // 7 -------|
+ //
+ {
+ connectionMatrix: [][]int{
+ {1, 3}, // 0
+ {2}, // 1
+ {3, 4}, // 2
+ {5}, // 3
+ {}, // 4
+ {6}, // 5
+ {7}, // 6
+ {2}, // 7
+ },
+ squares: []int{2},
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node3", "Node5", "Node6", "Node7"},
+ initialFoundationSet: []string{"Node2"},
+ },
+ },
+
+ // Case:
+ //
+ // [0] <------|
+ // |---->1 2 |
+ // |<---[3]-------------|
+ //
+ //
+ //
+ {
+ connectionMatrix: [][]int{
+ {1, 2}, // 0
+ {3}, // 1
+ {}, // 2
+ {0, 1}, // 3
+ },
+ squares: []int{0, 3},
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node1", "Node3"},
+ initialFoundationSet: []string{"Node0"},
+ },
+ },
+
+ // Case:
+ //
+ // |-----> 0 <------\
+ // | [1] --> [2]---|--> 4
+ // | ^ \
+ // |----|-------3
+ //
+ //
+ {
+ connectionMatrix: [][]int{
+ {1, 2}, // 0
+ {2}, // 1
+ {0, 3, 4}, // 2
+ {0, 1}, // 3
+ {}, // 4
+ },
+ squares: []int{1, 2},
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node3"},
+ initialFoundationSet: []string{"Node0", "Node1"},
+ },
+ },
+
+ // Case:
+ //
+ // |-->[1]
+ // [2]< -| 0
+ // ^ |
+ // |----|
+ //
+ //
+ {
+ connectionMatrix: [][]int{
+ {}, // 0
+ {0, 2}, // 1
+ {1, 2}, // 2
+ },
+ squares: []int{1, 2},
+ },
+
+ // Case: Double loops through left branches
+ //
+ // 0 <---|
+ // [1]<---|-----
+ // 3 2--| |
+ // [4] |
+ // 7 6 5 --|
+ // 8 9 10
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0
+ {2, 3}, // 1
+ {0, 4}, // 2
+ {}, // 3
+ {5, 6, 7}, // 4
+ {1, 10}, // 5
+ {9}, // 6
+ {8}, // 7
+ {}, // 8
+ {}, // 9
+ {}, // 10
+ },
+ squares: []int{1, 4},
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node2", "Node5"},
+ initialFoundationSet: []string{"Node0", "Node1"},
+ },
+ },
+ }
+
+ for i, c := range cases {
+ graph := buildTestGraph(c.connectionMatrix, c.squares)
+ dbgData := debugData{}
+ cycleDescription := checkWellFounded(graph[0], &dbgData)
+ if err := compareDebugData(&c.expectedDebugDataA, &dbgData); err != nil {
+ t.Fatalf("Case %dA: %s", i, err.Error())
+ }
+ if cycleDescription != nil {
+ t.Fatalf("Case %dA: Detected a cycle: %s", i, cycleDescription)
+ }
+ 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 cycleDescription != nil {
+ t.Fatalf("Case %dB: Detected a cycle: %s", i, cycleDescription)
+ }
+ }
+ }
+}
+
+// TestWellFoundedNotWellFounded tests the function |checkWellFounded| on graphs
+// that contain both circles and squares and are not well-founded.
+func TestWellFoundedNotWellFounded(t *testing.T) {
+
+ cases := []WellFoundedGraphTestCase{
+
+ // Case: Single square node with self-loop
+ {
+ connectionMatrix: [][]int{
+ {0},
+ },
+
+ squares: []int{0},
+
+ expectedFirstA: "Node0",
+ expectedLastA: "Node0",
+ expectedPathA: "Node0",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0"},
+ initialFoundationSet: []string{},
+ },
+ },
+
+ // Case: Loop of length 4 with 1 square at the root
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0 -> 1
+ {2}, // 1 -> 2
+ {3}, // 2 -> 3
+ {0}, // 3 -> 0
+ },
+
+ squares: []int{0},
+
+ expectedFirstA: "Node0",
+ expectedLastA: "Node3",
+ expectedPathA: "Node0, Node1, Node2, Node3",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3"},
+ initialFoundationSet: []string{},
+ },
+
+ expectedFirstB: "Node1",
+ expectedLastB: "Node0",
+ expectedPathB: "Node1, Node2, Node3, Node0",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3"},
+ initialFoundationSet: []string{},
+ },
+ },
+
+ // Case: Loop of length 4 with 2 squares
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0 -> 1
+ {2}, // 1 -> 2
+ {3}, // 2 -> 3
+ {0}, // 3 -> 0
+ },
+
+ squares: []int{1, 2},
+
+ expectedFirstA: "Node0",
+ expectedLastA: "Node3",
+ expectedPathA: "Node0, Node1, Node2, Node3",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3"},
+ initialFoundationSet: []string{},
+ },
+
+ expectedFirstB: "Node1",
+ expectedLastB: "Node0",
+ expectedPathB: "Node1, Node2, Node3, Node0",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3"},
+ initialFoundationSet: []string{},
+ },
+ },
+
+ // Case: Loop through left and right branches
+ //
+ // |--> [0] <--|
+ // |--1 2--|
+ {
+ connectionMatrix: [][]int{
+ {1, 2}, // 0
+ {0}, // 1
+ {0}, // 2
+ },
+ squares: []int{0},
+
+ expectedFirstA: "Node0",
+ expectedLastA: "Node1",
+ expectedPathA: "Node0, Node1",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2"},
+ initialFoundationSet: []string{},
+ },
+
+ expectedFirstB: "Node1",
+ expectedLastB: "Node0",
+ expectedPathB: "Node1, Node0",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2"},
+ initialFoundationSet: []string{},
+ },
+ },
+
+ // Case: Loop through left and right branches below the root
+ //
+ // |----> 0 <---|
+ // | [1] |
+ // |-- 2 3--|
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0
+ {2, 3}, // 1
+ {0}, // 2
+ {0}, // 3
+ },
+ squares: []int{1},
+
+ expectedFirstA: "Node0",
+ expectedLastA: "Node2",
+ expectedPathA: "Node0, Node1, Node2",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3"},
+ initialFoundationSet: []string{},
+ },
+
+ expectedFirstB: "Node1",
+ expectedLastB: "Node0",
+ expectedPathB: "Node1, Node2, Node0",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3"},
+ initialFoundationSet: []string{},
+ },
+ },
+
+ // Case: Self loop at one node below a square
+ //
+ // [0]
+ // 1 2--|
+ // ^ |
+ // | |
+ // ----
+ {
+ connectionMatrix: [][]int{
+ {1, 2}, // 0
+ {}, // 1
+ {2}, // 2
+ },
+ squares: []int{0},
+
+ expectedFirstA: "Node2",
+ expectedLastA: "Node2",
+ expectedPathA: "Node2",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node2"},
+ initialFoundationSet: []string{},
+ },
+ },
+
+ // Case: Self loop at one node below a square, other side
+ //
+ // [0]
+ // 2 1--|
+ // ^ |
+ // | |
+ // ----
+ {
+ connectionMatrix: [][]int{
+ {1, 2}, // 0
+ {1}, // 1
+ {}, // 2
+ },
+ squares: []int{0},
+
+ expectedFirstA: "Node1",
+ expectedLastA: "Node1",
+ expectedPathA: "Node1",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node1"},
+ initialFoundationSet: []string{},
+ },
+
+ expectedFirstB: "Node1",
+ expectedLastB: "Node1",
+ expectedPathB: "Node1",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node1"},
+ initialFoundationSet: []string{},
+ },
+ },
+
+ // Case: Self loop off of one branch of a square.
+ //
+ // [0]
+ // 1 2
+ // 3 -|
+ // ^ |
+ // |---
+ {
+ connectionMatrix: [][]int{
+ {1, 2}, // 0
+ {3}, // 1
+ {}, // 2
+ {3}, // 3
+ },
+ squares: []int{0},
+
+ expectedFirstA: "Node3",
+ expectedLastA: "Node3",
+ expectedPathA: "Node3",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node1", "Node3"},
+ initialFoundationSet: []string{},
+ },
+
+ expectedFirstB: "Node3",
+ expectedLastB: "Node3",
+ expectedPathB: "Node3",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node1", "Node3"},
+ initialFoundationSet: []string{},
+ },
+ },
+
+ // Case: Hard loop off of one branch of a square.
+ //
+ // [0]
+ // --> 1 2
+ // | 3
+ // |---4
+ {
+ connectionMatrix: [][]int{
+ {1, 2}, // 0
+ {3}, // 1
+ {}, // 2
+ {4}, // 3
+ {1}, // 4
+ },
+ squares: []int{0},
+
+ expectedFirstA: "Node1",
+ expectedLastA: "Node4",
+ expectedPathA: "Node1, Node3, Node4",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node1", "Node3", "Node4"},
+ initialFoundationSet: []string{},
+ },
+
+ expectedFirstB: "Node1",
+ expectedLastB: "Node4",
+ expectedPathB: "Node1, Node3, Node4",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node1", "Node3", "Node4"},
+ initialFoundationSet: []string{},
+ },
+ },
+
+ // Case: Graph below 0 is well-founded and 1 is well-founded but not the graph below 1.
+ //
+ // [1]
+ // 2 -| 0
+ // ^ |
+ // |--|
+ //
+ //
+ {
+ connectionMatrix: [][]int{
+ {}, // 0
+ {0, 2}, // 1
+ {2}, // 2
+ },
+ squares: []int{1},
+
+ expectedFirstB: "Node2",
+ expectedLastB: "Node2",
+ expectedPathB: "Node2",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node2"},
+ initialFoundationSet: []string{},
+ },
+ },
+
+ // Case: Different loops through both branches sharing nodes.
+ //
+ // 0 <------|
+ // 1 |
+ // [2] |
+ // 3 4 |
+ // \ 5 |
+ // \----> 6 |
+ // 7 --|
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0
+ {2}, // 1
+ {3, 4}, // 2
+ {6}, // 3
+ {5}, // 4
+ {6}, // 5
+ {7}, // 6
+ {0}, // 7
+ },
+ squares: []int{2},
+
+ expectedFirstA: "Node0",
+ expectedLastA: "Node7",
+ expectedPathA: "Node0, Node1, Node2, Node3, Node6, Node7",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3", "Node4", "Node5", "Node6", "Node7"},
+ initialFoundationSet: []string{},
+ },
+
+ expectedFirstB: "Node1",
+ expectedLastB: "Node0",
+ expectedPathB: "Node1, Node2, Node3, Node6, Node7, Node0",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3", "Node4", "Node5", "Node6", "Node7"},
+ initialFoundationSet: []string{},
+ },
+ },
+
+ // Case: Different loops through both branches sharing nodes--switch sides.
+ //
+ // 0 <------|
+ // 1 |
+ // [2] |
+ // 4 3 |
+ // \ 5 |
+ // \----> 6 |
+ // 7 --|
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0
+ {2}, // 1
+ {3, 4}, // 2
+ {5}, // 3
+ {6}, // 4
+ {6}, // 5
+ {7}, // 6
+ {0}, // 7
+ },
+ squares: []int{2},
+
+ expectedFirstA: "Node0",
+ expectedLastA: "Node7",
+ expectedPathA: "Node0, Node1, Node2, Node3, Node5, Node6, Node7",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3", "Node4", "Node5", "Node6", "Node7"},
+ initialFoundationSet: []string{},
+ },
+
+ expectedFirstB: "Node1",
+ expectedLastB: "Node0",
+ expectedPathB: "Node1, Node2, Node3, Node5, Node6, Node7, Node0",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3", "Node4", "Node5", "Node6", "Node7"},
+ initialFoundationSet: []string{},
+ },
+ },
+
+ // Case: Not Well-founded becuase of 8 becuase 4 is a circle
+ // 0
+ // 1
+ // 2 <--
+ // 3 |
+ // 8 <-- 4 |
+ // 5 |
+ // 6---|
+ // 7
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0
+ {2}, // 1
+ {3}, // 2
+ {4}, // 3
+ {5, 8}, // 4
+ {6}, // 5
+ {2, 7}, // 6
+ {}, // 7
+ {}, // 8
+ },
+ squares: []int{},
+
+ expectedFirstA: "Node2",
+ expectedLastA: "Node6",
+ expectedPathA: "Node2, Node3, Node4, Node5, Node6",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3", "Node4", "Node5", "Node6"},
+ initialFoundationSet: []string{},
+ },
+
+ expectedFirstB: "Node2",
+ expectedLastB: "Node6",
+ expectedPathB: "Node2, Node3, Node4, Node5, Node6",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node1", "Node2", "Node3", "Node4", "Node5", "Node6"},
+ initialFoundationSet: []string{},
+ },
+ },
+
+ // Case: Not Well-founded becuase of 8 becuase there is no 8
+ // 0
+ // 1
+ // 2 <--
+ // 3 |
+ // [4] |
+ // 5 |
+ // 6---|
+ // 7
+ {
+ connectionMatrix: [][]int{
+ {1}, // 0
+ {2}, // 1
+ {3}, // 2
+ {4}, // 3
+ {5}, // 4
+ {6}, // 5
+ {2, 7}, // 6
+ {}, // 7
+ },
+ squares: []int{4},
+
+ expectedFirstA: "Node2",
+ expectedLastA: "Node6",
+ expectedPathA: "Node2, Node3, Node4, Node5, Node6",
+ expectedDebugDataA: expectedDebugData{
+ initialPendingSet: []string{"Node0", "Node1", "Node2", "Node3", "Node4", "Node5", "Node6"},
+ initialFoundationSet: []string{},
+ },
+
+ expectedFirstB: "Node2",
+ expectedLastB: "Node6",
+ expectedPathB: "Node2, Node3, Node4, Node5, Node6",
+ expectedDebugDataB: expectedDebugData{
+ initialPendingSet: []string{"Node1", "Node2", "Node3", "Node4", "Node5", "Node6"},
+ initialFoundationSet: []string{},
+ },
+ },
+ }
+
+ for i, c := range cases {
+ graph := buildTestGraph(c.connectionMatrix, c.squares)
+ // Test from root=Node0
+ dbgData := debugData{}
+ cycleDescription := checkWellFounded(graph[0], &dbgData)
+ if err := compareDebugData(&c.expectedDebugDataA, &dbgData); err != nil {
+ t.Fatalf("Case %dA: %s", i, err.Error())
+ }
+ 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)
+ }
+ if !strings.Contains(cycleDescription.String(), fmt.Sprintf("last:%s", c.expectedLastA)) {
+ t.Fatalf("Case %d: got=%s expectedLast=%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)
+ }
+ }
+
+ // 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)
+ }
+ 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)
+ }
+ }
+ }
+ }
+}
« no previous file with comments | « mojom/mojom_parser/utils/wellfounded_graphs.go ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698