Module graph 

The graph walks behind §6.5’s prelude helpers (ADR-060).

§6.5 asks for “closure-based algorithms that do not require materializing a graph object”: the caller supplies a start state and a function from a state to its neighbours, and the helper walks whatever that function describes. There is no graph value, no adjacency table and no node type — the graph is the closure.

Why the walks do not call the closures themselves

Calling a Praxis closure means transmuting a JIT’d function pointer and passing it a live RuntimeContext, which no unit test can supply. So the walks below never touch a closure: they ask a GraphOracle, and praxis_runtime::abi supplies the one implementation that calls closures. A test supplies one backed by an adjacency table, which is what makes “dijkstra relaxes an edge it has already settled” a question that can be asked without a compiler in the room.

States are values, and the walks hold them

A state is a GcRef and the walks keep every state they have seen — in a visited set, in a queue, in a cost table, in a parent table. Those are Rust structures the collector cannot see, so the caller must root every state it hands in and every state an oracle hands back before the next call that may allocate. GraphOracle::retain is where that happens: the walks call it once per newly discovered state, immediately, and the ABI implementation roots it in its NativeScope.

Identity

Two states are the same state when DynamicKey says so — the same descriptor and a structural equals — which is exactly the rule a Set element and a Map key follow. That is why inference requires CapKind::HashStable of the state type at every call site: a state that can change after the walk has stored it cannot be found again, and the walk would revisit it forever.

Structs

Aborted

A walk stopped before it had an answer, because a fault is pending.

Route

What a goal-directed search found: the route from the start to the goal it stopped at, and what that route cost.

Traits

GraphOracle

What a walk asks about the graph it is walking.

Functions

a_star_route

a_star_distance/a_star_path’s one walk: the cheapest route from start to a goal, or None when no goal is reachable.

bfs_order

bfs(start, neighbours) — every reachable state, in breadth-first order.

bfs_route

bfs_distance/bfs_path’s one walk: the shortest route from start to a state satisfying is_goal, or None when no such state is reachable.

dfs_order

dfs(start, neighbours) — every reachable state, in depth-first pre-order.

dfs_route

dfs_distance/dfs_path’s one walk: the route depth-first search found to a state satisfying is_goal, or None when no such state is reachable.

dijkstra_costs

dijkstra(start, neighbours, weight) — the least cost from start to every reachable state, as (state, cost) pairs.

dijkstra_route

dijkstra_distance/dijkstra_path’s one walk: the cheapest route from start to a goal, or None when no goal is reachable.

reachable

flood_fill(start, neighbours) — every reachable state.