Mojom frontend: Detect Ill-founded Types

mojom/mojom_tool/utils/wellfounded_graphs.go

 // Copyright 2016 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 package utils
 
 import (
         "bytes"
         "fmt"
 )
@@ skipping 10 matching lines @@
 // (ii) A circle node is well-founded iff all of its children are well-founded
 // (iii) A non-leaf square node is well-founded iff at least one of its children is well-founded.
 // (See the paper for a more logically correct definition.)
 //
 // See the comments on the main function |CheckWellFounded| below for a description
 // of the algorithm.
 
 ///////////////////////////////////////////////////
 // Node type
 //
-// A |Node| is a node in a directed graph.
+// A |Node| is a node in a directed graph. A user of this library is responsible
+// for implementing this interface. This library will use the Go equality operator
+// to compare instances of |Node| and it is the responsibility of the user
+// to ensure that x == y iff x and y represent the same logical node.
 ///////////////////////////////////////////////////
 
 type Node interface {
         // Returns the list of children of this node.
-        OutEdges() []Node
+        OutEdges() []OutEdge
 
         // Returns whether or not this node is a square node.
         IsSquare() bool
 
         // SetKnownWellFounded is invoked by the algorithm in order to set the
         // fact that the algorithm has determined that this node is well-founded.
         // An implementation of |Node| should cache this--even between different
         // invocations of the algorithm on different starting nodes--and return
         // |true| from the method |KnownWellFounded| just in case this method has
         // ever been invoked.  In this way any nodes verified to be well-founded during
         // one run of the algorithm do not need to be checked during a later run of the
         // algorithm on a different starting node.
         SetKnownWellFounded()
 
         // Returns whether or not the function |SetKnownWellFounded| has ever
         // been invoked on this node, during the lifetime of a program using
         // this library.
         KnownWellFounded() bool
 
-        // Returns the name of this node, appropriate for debugging.
-        DebugName() string
+        // Returns a human-readable name for this node. Not used by the algorithm
+        // but used for generating debugging and error messages.
+        Name() string
+}
+
+type OutEdge struct {
+        // The Label on an edge is opaque data that may be used by the client however it wishes.
+        // The algorithm never inspects this data.
+        Label interface{}
+
+        // The target node of the out edge.
+        Target Node
 }
 
 ///////////////////////////////////////////////////
 // CheckWellFounded function
 //
 // This is the main public function.
 ///////////////////////////////////////////////////
 
 // CheckWellFounded checks whether the sub-graph rooted at |root| contains any ill-founded nodes.
 // If any ill-founded nodes are detected then a non-nil |CycleDescription| is returned containing
@@ skipping 59 matching lines @@
         return finder.checkWellFounded(holder)
 }
 
 ///////////////////////////////////////////////////
 /// cycleFinder type
 ///
 /// A cycleFinder is an object that holds state during the execution of the algorithm.
 ///////////////////////////////////////////////////
 type cycleFinder struct {
 
-        // Maps each node seen by the computation to its holder.
+        // Maps each node seen by the computation to its holder. Note that this assumes
+        // that the implementation of Node uses values that are comparable and
+        // obey identity semantics.
         nodeToHolder map[Node]*nodeHolder
 
         foundationSet, pendingSet NodeSet
 
         visitationIndex int
-        currentPath     nodeStack
 
         debugDataRequest *debugData
 }
 
 type debugData struct {
         initialPendingSet    []Node
         initialFoundationSet []Node
 }
 
 func makeCycleFinder() cycleFinder {
         finder := cycleFinder{}
         finder.nodeToHolder = make(map[Node]*nodeHolder)
         finder.foundationSet = MakeNodeSet()
         finder.pendingSet = MakeNodeSet()
-        finder.currentPath = nodeStack{}
         return finder
 }
 
 // checkWellFounded contains the top-level implementation of the algorithm.
 func (finder *cycleFinder) checkWellFounded(nodeHolder *nodeHolder) *CycleDescription {
         if nodeHolder.node.KnownWellFounded() {
                 // This node is already known to be well-founded because of an earlier
                 // execution of the algorithm.
                 return nil
         }
@@ skipping 30 matching lines @@
                 if minIllfoundedNode == nil || n.visitationOrder < minVisitationOrder {
                         minVisitationOrder = n.visitationOrder
                         minIllfoundedNode = n.node
                 }
         }
 
         // Starting from the ill-founded node with the least visitation order,
         // build a canonical cycle.
         freshCycleFinder := makeCycleFinder()
         holder := freshCycleFinder.holderForNode(minIllfoundedNode)
-        return freshCycleFinder.findKnownIllFoundedCycle(holder)
+        return freshCycleFinder.findKnownIllFoundedCycle(holder, nil)
 }
 
 // checkWellFoundedPhase1 is a recursive helper function that does a depth-first traversal
 // of the graph rooted at |nodeHolder|. The goal of phase 1 is to mark as many
 // of the nodes as possible as |KnownWellFounded| and to set up the |pendingSet|,
 // the |foundationSet|, and the |parentsToBeNotified| sets so that the remaining
 // well-founded nodes will be marked as |KnownWellFounded| in phase 2.
 //
 // In more detail the following steps are performed for each node x:
 // (a1) If it can be verified during the traversal that x is well-founded then
@@ skipping 19 matching lines @@
                 // of the algorithm and so we treat this node as a leaf node.
                 nodeHolder.state = vsVisitEnded
                 return
         }
 
         // Mark the visit as started.
         nodeHolder.state = vsVisitStarted
 
         // Next we examine each of the children and recurse into the unvisited ones.
         sawUnverifiedChild := false
-        for _, child := range nodeHolder.node.OutEdges() {
-                childHolder := finder.holderForNode(child)
+        for _, edge := range nodeHolder.node.OutEdges() {
+                childHolder := finder.holderForNode(edge.Target)
                 if childHolder.state == vsUnvisited {
                         // Recursively visit this child.
                         finder.checkWellFoundedPhase1(childHolder)
                 }
 
                 // After having visited a child we use the results to update the status of this node.
                 // We could express the logic here more concisely, but  the logic is easier
                 // to understand if we treat circles and squares seperately,
                 if nodeHolder.node.IsSquare() {
                         if nodeHolder.node.KnownWellFounded() {
@@ skipping 55 matching lines @@
 // to be well-founded during phase 1, pruned to nodes that have parents that
 // are in the |pendingSet|.) We iteratively remove a node n from the foundation set and
 // for each of its parents p for which p is in the pending set and for which we can now verify
 // well-foundedness, we remove p from the pending set and add it to the foundation set.
 func (finder *cycleFinder) checkWellFoundedPhase2() {
         for n := finder.foundationSet.removeRandomElement(); n != nil; n = finder.foundationSet.removeRandomElement() {
                 for p, _ := range n.parentsToBeNotified.elements {
                         if finder.pendingSet.Contains(p) {
                                 knownWellFounded := true
                                 if !p.node.IsSquare() {
-                                        for _, child := range p.node.OutEdges() {
+                                        for _, edge := range p.node.OutEdges() {
+                                                child := edge.Target
                                                 if child != p.node && !child.KnownWellFounded() {
                                                         knownWellFounded = false
                                                         break
                                                 }
                                         }
                                 }
                                 if knownWellFounded {
                                         p.node.SetKnownWellFounded()
                                         finder.foundationSet.Add(p)
                                         finder.pendingSet.Remove(p)
                                 }
                         }
                 }
         }
 }
 
+// A pathElement is a node and one of its out-edges.
+type pathElement struct {
+        node Node
+        edge OutEdge
+}
+
+type nodePath []pathElement
+
 // findKnownIllFoundedCycle finds and returns a |CycleDescription| starting from a node that is known
 // to be ill-founded. This proceeds by following edges from an ill-founded node to
 // an ill-founded child node until a cycle is formed. We return a *canonical* cycle,
 // meaning we start from the node with the least possible visit index and follow edges to
 // the child node with the least possible visit index. This is done in order to make testing of the algorithm easier.
 // We are not concerned with optimizing the performance of phase 3 because in the intended application
 // phase 3 can occur at most once in the lifetime of a program: Once an ill-founded node is detected the
 // program exits with a cycle description allowing the user to fix the ill-foundedness.
-func (finder *cycleFinder) findKnownIllFoundedCycle(nodeHolder *nodeHolder) *CycleDescription {
+//
+// This method is recursive. To initiate the recursion |nodeHolder| should be set to the starting node and
+// |path| should be nil. In subsequent recursive calls |nodeHolder| is the current node of the walk and
+// |path| is the path from the starting node to the current node.
+func (finder *cycleFinder) findKnownIllFoundedCycle(nodeHolder *nodeHolder, path nodePath) *CycleDescription {
+        // If this is the start of the recursion initialize the path.
+        if path == nil {
+                path = make(nodePath, 0)
+        }
+
         // Mark the current node as started
         nodeHolder.state = vsVisitStarted
-        finder.currentPath.Push(nodeHolder)
-        for _, child := range nodeHolder.node.OutEdges() {
-                childHolder := finder.holderForNode(child)
+        for _, edge := range nodeHolder.node.OutEdges() {
+                childHolder := finder.holderForNode(edge.Target)
                 if childHolder.state == vsVisitStarted {
                         // If the child has been started but not finished then we have found a cycle
                         // from the child to the current node back to the child.
-                        return newCycleDescription(finder.currentPath.elements, childHolder, nodeHolder)
+                        path = append(path, pathElement{nodeHolder.node, edge})
+                        return newCycleDescription(path, childHolder.node, nodeHolder.node)
                 } else if !childHolder.node.KnownWellFounded() {
-                        return finder.findKnownIllFoundedCycle(childHolder)
+                        path = append(path, pathElement{nodeHolder.node, edge})
+                        return finder.findKnownIllFoundedCycle(childHolder, path)
                 }
         }
         panic("Program logic error: Could not find a known ill-founded cycle.")
 }
 
 // Returns the nodeHolder for the given node.
 func (finder *cycleFinder) holderForNode(node Node) *nodeHolder {
         if holder, found := finder.nodeToHolder[node]; found {
                 return holder
         }
@@ skipping 33 matching lines @@
 
 func newNodeHolder(node Node, visitationOrder int) *nodeHolder {
         nodeHolder := new(nodeHolder)
         nodeHolder.node = node
         nodeHolder.parentsToBeNotified = MakeNodeSet()
         nodeHolder.state = vsUnvisited
         nodeHolder.visitationOrder = visitationOrder
         return nodeHolder
 }
 
-//////////////////////////////////////////////
-///  nodeStack type
-//////////////////////////////////////////////
-
-// A nodeStack is a stack of *nodeHolders
-type nodeStack struct {
-        elements []*nodeHolder
-}
-
-func (stack *nodeStack) Push(n *nodeHolder) {
-        stack.elements = append(stack.elements, n)
-}
-
-func (stack *nodeStack) Size() int {
-        return len(stack.elements)
-}
-
-func (stack *nodeStack) Pop() (n *nodeHolder) {
-        lastIndex := stack.Size() - 1
-        n = stack.elements[lastIndex]
-        stack.elements = stack.elements[:lastIndex]
-        return
-}
-
-func (stack *nodeStack) Peek() (n *nodeHolder) {
-        return stack.elements[stack.Size()-1]
-}
-
-func (stack *nodeStack) String() string {
-        var buffer bytes.Buffer
-        fmt.Fprintf(&buffer, "[")
-        first := true
-        for _, e := range stack.elements {
-                if !first {
-                        fmt.Fprintf(&buffer, ", ")
-                }
-                fmt.Fprintf(&buffer, "%s", e.node.DebugName())
-                first = false
-        }
-        fmt.Fprintln(&buffer, "]")
-        return buffer.String()
-}
-
 ///////////////////////////////////////////////////
 /// NodeSet type
 ///////////////////////////////////////////////////
 
 // A NodeSet is a set of nodeHolders.
 type NodeSet struct {
         elements map[*nodeHolder]bool
 }
 
 // MakeNodeSet makes a new empty NodeSet.
@@ skipping 66 matching lines @@
 
 func (set *NodeSet) Size() int {
         return len(set.elements)
 }
 
 // compareNodeSets is a package-private method used in our tests. It returns
 // a non-nil error in case expected is not equal to actual.
 func compareNodeSets(expected, actual *NodeSet) error {
         for n, _ := range expected.elements {
                 if !actual.Contains(n) {
-                        return fmt.Errorf("%s is in expected but not actual", n.node.DebugName())
+                        return fmt.Errorf("%s is in expected but not actual", n.node.Name())
                 }
         }
         for n, _ := range actual.elements {
                 if !expected.Contains(n) {
-                        return fmt.Errorf("%s is in actual but not expected", n.node.DebugName())
+                        return fmt.Errorf("%s is in actual but not expected", n.node.Name())
                 }
         }
         return nil
 }
 
 // String returns a human readable string representation of |set|.
 func (set *NodeSet) String() string {
         var buffer bytes.Buffer
         fmt.Fprintf(&buffer, "{")
         first := true
         for e, _ := range set.elements {
                 if !first {
                         fmt.Fprintf(&buffer, ", ")
                 }
-                fmt.Fprintf(&buffer, "%s", e.node.DebugName())
+                fmt.Fprintf(&buffer, "%s", e.node.Name())
                 first = false
         }
         fmt.Fprintln(&buffer, "}")
         return buffer.String()
 }
 
 ///////////////////////////////////////////////////
 // CycleDescription type
 //
 // A |CycleDescription| describes a cycle in a directed graph.
 ///////////////////////////////////////////////////
 
 type CycleDescription struct {
-        first, last Node
-        path        []Node
+        First, Last Node
+        Path        []OutEdge
 }
 
 func (c *CycleDescription) String() string {
         var buffer bytes.Buffer
-        fmt.Fprintf(&buffer, "first:%s", c.first.DebugName())
-        fmt.Fprintf(&buffer, ", last:%s", c.last.DebugName())
+        fmt.Fprintf(&buffer, "first:%s", c.First.Name())
+        fmt.Fprintf(&buffer, ", last:%s", c.Last.Name())
         fmt.Fprintf(&buffer, ", path:{")
-        first := true
-        for _, n := range c.path {
-                if !first {
+        fmt.Fprintf(&buffer, "%s", c.First.Name())
+        for _, edge := range c.Path {
+                if edge.Target != c.First {
                         fmt.Fprintf(&buffer, ", ")
+                        fmt.Fprintf(&buffer, "%s", edge.Target.Name())
                 }
-                fmt.Fprintf(&buffer, "%s", n.DebugName())
-                first = false
         }
         fmt.Fprintln(&buffer, "}")
         return buffer.String()
 }
 
-func newCycleDescription(path []*nodeHolder, first, last *nodeHolder) *CycleDescription {
+// newCycleDescription builds a CycleDescription based on the given data.
+// |path| should be a nodePath that ends with a cycle. That is it should look like
+//  {x1, ->x2}, {x2, ->x3}, {x3, ->x4}, {x4, ->x5}, {x5, ->x2}
+//
+// |cycleStart| should be the first node of |path| included in the cycle. In
+// the above example it would be x2.
+//
+// |end| should be the last node of the path. In the above example it would be x5.
+//
+// The return value using our example would be:
+// {First: x2, Last: x5, Path:[{x2, x2->x3}, {x3, x3->x4}, {x4, x4->x5}, {x5, x5->x2}]}
+func newCycleDescription(path nodePath, cycleStart, end Node) *CycleDescription {
+        lastNode := path[len(path)-1].node
+        if lastNode != end {
+                panic(fmt.Sprintf("%s != %s", lastNode.Name(), end.Name()))
+        }
+        lastTarget := path[len(path)-1].edge.Target
+        if lastTarget != cycleStart {
+                panic(fmt.Sprintf("(%T)%s != (%T)%s", lastTarget, lastTarget.Name(), cycleStart, cycleStart.Name()))
+        }
         description := CycleDescription{}
-        description.first = first.node
-        description.last = last.node
-        description.path = make([]Node, 0, len(path))
-        for _, n := range path {
-                if len(description.path) > 0 || n.node == first.node {
-                        description.path = append(description.path, n.node)
+        description.First = cycleStart
+        description.Last = end
+        description.Path = make([]OutEdge, 0, len(path))
+        for _, element := range path {
+                if len(description.Path) > 0 || element.node == cycleStart {
+                        description.Path = append(description.Path, element.edge)
                 }
         }
-        if description.path[len(description.path)-1] != last.node {
-                panic(fmt.Sprintf("%s != %s", description.path[len(description.path)-1], last.node))
+        if description.Path[len(description.Path)-1].Target != cycleStart {
+                panic(fmt.Sprintf("%s != %s", description.Path[len(description.Path)-1].Target.Name(), cycleStart.Name()))
         }
         return &description
 }