Module graph 

The dependency graph — what the program is made of and what depends on what.

Why the compiler owns this

.NET Aspire’s dashboard shows a resource list and a dependency graph, and it can, because you write an AppHost: a second program that declares AddPostgres("db"), WithReference(db), and so on. The topology is described twice — once as the application, once as the AppHost — and the two drift.

Beck has no AppHost, because the program is the AppHost. crate::place assigns every definition a tier, crate::split slices the signal graph, and beck-infra derives the resource set from the effect rows, each resource carrying the effect that implies it. Nothing about the topology is written down a second time, so nothing about it can disagree. The graph below is not collected; it is read off what the compiler already knows.

The structure, and why

A compressed sparse row adjacency: offsets[v]..offsets[v + 1] indexes a contiguous run of edges. That is 4 bytes per edge and one cache line per neighbourhood, against the pointer per edge and one allocation per vertex of a Vec<Vec<_>>. Both directions are stored, because the two questions a dashboard asks are opposite: what does this need (forward) and what breaks if I change it (reverse).

operation	time	space
build, including SCCs	O(V + E)	O(V + E)
dependencies, dependents	O(1) to the slice	0
cycle_of, scc_index, id	O(1), O(log V) for id	0
impacted_by (transitive dependents)	O(V' + E') reached	O(V')
topological	O(1), precomputed	0

Building is linear and cannot be better: the program has to be read once. Everything the dashboard asks afterwards is a slice index or a bounded traversal, so “almost instant” is not a performance target to chase — it is what the representation makes unavoidable.

Cycles are not errors here

docs/19-phase-1-report.md §19.4 item 4: the signal graph is legitimately cyclic — events is decided from todos, todos is folded from events — and §3.7 makes the cycle sound. So this does not topologically sort the vertices, which would be impossible. It computes strongly connected components with Tarjan’s algorithm and topologically sorts the condensation, which always exists. A cycle becomes one box in the dashboard rather than a failure to render.

Tarjan rather than Kosaraju because it is one pass rather than two, and it emits components in reverse topological order for free — the layout order the dashboard wants. It is written iteratively: recursion depth would be the longest path in the program, and a compiler should not have a program size at which it overflows the stack.

Structs

DepGraph

A dependency graph over one program and the infrastructure its effects imply.

Edge

GraphBuilder

Accumulates vertices and edges before they are frozen into CSR form.

GraphNode

NodeId

An index into DepGraph::nodes.

Enums

EdgeKind

NodeKind

Functions

from_program

Read the vertices and edges of a checked program.