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

• Appendables
  An arena used by AppendingCycleDetector to store the path component lists. The arena is shared between all cycle detectors in a path stitching run, so that the cycle detectors themselves can be small and cheaply cloned.
• AppendingCycleDetector
  A cycle detector that builds up paths by appending elements to it. Path elements are stored in a shared arena that must be provided when calling methods, so that cloning the cycle detector itself is cheap.
• SimilarPathDetector
  Helps detect similar paths in the path-finding algorithm.
• SimilarPathStats