Module stack_graphs::cycles

Detect and avoid cycles in our path-finding algorithm.

Cycles in a stack graph can indicate many things. Your language might allow mutually recursive imports. If you are modeling dataflow through function calls, then any recursion in your function calls will lead to cycles in your stack graph. And if you have any control-flow paths that lead to infinite loops at runtime, we’ll probably discover those as stack graph paths during the path-finding algorithm.

(Note that we’re only considering cycles in well-formed paths. For instance, pop symbol nodes are “guards” that don’t allow you to progress into a node if the top of the symbol stack doesn’t match. We don’t consider that a valid path, and so we don’t have to worry about whether it contains any cycles.)

This module implements a cycle detector that lets us detect these situations and “cut off” these paths, not trying to extend them any further. Note that any cycle detection logic we implement will be a heuristic. In particular, since our path-finding algorithm will mimic any runtime recursion, a “complete” cycle detection logic would be equivalent to the Halting Problem.

Right now, we implement a simple heuristic where we limit the number of distinct paths that we process that have the same start and end nodes. We do not make any guarantees that we will always use this particular heuristic, however! We reserve the right to change the heuristic at any time.

Structs

CycleDetector

Helps detect cycles in the path-finding algorithm.