Syntax.Flow

Call-graph flow over a resolved document: occurrence analysis and liveness as one fixpoint.

The questions a compiler asks about a call graph (what does this function transitively reach, which functions are reachable from the entry points, which ones recurse) are one program with three settings of the same three knobs: a per-node contribution, a join, and a dependency relation. Data.Fixpoint solves that program; this module supplies the three knobs from the prism-resolved-syntax-v1 document, so the analysis runs over a real resolved tree rather than a hand-built graph. Transitive reach propagates along the calls relation; liveness is the identical solve with the relation reversed and a Boolean carrier.

The edges come from the same seam Syntax.Rename queries, with the same limit. A var node’s span covers exactly its identifier, so every reference is readable, but no reference carries the identity of the binder it resolved to. A local binder spelled like a top-level function is therefore read as a call to that function, which adds edges that are not there. Every answer here is that over-approximation: fl_dead names only functions that really are unreachable, and fl_transitive may list a callee a run never makes. When the seam grows a binder-identity fact the approximation tightens without an interface change. Opt-in: not in Base.

Functions and Values

fl_defined

fl_defined : forall a. (Syntax.Resolved.ResolvedDoc) -> Map(String, Unit, a)

The names the document defines, as a set.

fl_references

fl_references : (Syntax.Source.SourceFile, Syntax.Resolved.RFunction) -> List(String)

Every identifier one function’s body references, in source order, sliced from the embedded source. A reference the source cannot address is dropped, which Syntax.Rename’s rn_unaddressed is how to detect before trusting any answer here.

fl_calls

fl_calls : forall a. (Syntax.Resolved.ResolvedDoc) -> Map(String, List(String), a)

The call graph: an edge from each function to every function of this document it references. Every defined function is a node, so one that calls nothing still gets an answer, and successor lists are ascending and duplicate-free, so the iteration order below is a function of the document alone.

fl_direct

fl_direct : forall a b c d. (Map(d, List(d), a)) -> Map(d, Map(d, Unit, b), c)

The immediate successors of a graph as a set per node: the per-node contribution a propagation starts from.

map(\(p) -> (fst(p), set_to_list(snd(p))), map_to_list(fl_direct(graph_from_edges([("f", "g")]))))

[(f, [g])]

fl_transitive

fl_transitive : forall a b. (Syntax.Resolved.ResolvedDoc) -> Map(String, Map(String, Unit, a), b) ! {Fail}

Every function each function transitively calls: the least assignment with x[f] the union of direct[f] and every x[g] for g in direct[f]. The members of one cycle share one answer, and a function on a cycle lists itself.

fl_live

fl_live : forall a. (Syntax.Resolved.ResolvedDoc, List(String)) -> Map(String, Unit, a) ! {Fail}

The functions reachable from roots: the same solve with the calls relation reversed, so reachability flows from a caller to its callees, over the Boolean lattice. A root the document does not define contributes nothing.

fl_dead

fl_dead : (Syntax.Resolved.ResolvedDoc, List(String)) -> List(String) ! {Fail}

The functions no root reaches, ascending: what a dead-code report is, once the document’s entry points are named.

fl_recursive

fl_recursive : (Syntax.Resolved.ResolvedDoc) -> List(String) ! {Fail}

The functions that call themselves, directly or through a cycle, ascending. This is the question a plain traversal answers wrongly and the fixpoint answers by construction: mutual recursion is a cycle, not a self-edge.