// mcpp.graph — Kahn's algorithm, dependency levels and closure, over

// index-addressed directed graphs.

//

// THE SHAPE EVERY CALLER ALREADY HAS

//

// A module-import graph, a package-dependency graph and a build-rule graph

// are unrelated domains, but by the time any of them asks "what order", "what

// depth" or "what does this reach", the caller has already reduced its own

// nodes to a dense index range 0..n-1 and its edges to an adjacency list.

// This package is that reduced question's one answer, factored out after

// `src/modgraph/graph.cppm`, `src/build/prepare/features.cpp` (twice),

// `src/build/dep_graph.cppm` and `src/build/prepare/plan.cpp` had each

// hand-written a variant of Kahn's algorithm or a DFS cycle check, with four

// different tie-break rules and three different cycle-reporting shapes.

//

// EDGE ORIENTATION

//

// `deps[u]` lists the nodes `u` depends on: an edge `u -> v` means "u depends

// on v", so a leaf with no dependencies is a node with an empty adjacency

// list. This is the direction every migrated call site already used for its

// own hand-rolled adjacency (a consumer's edge list, an importer's imports,

// a package's `[dependencies]`), so no call site has to invert its data to

// call in.

//

// THREE ORDERS, AND WHY A CALLER KEEPS THE ONE IT HAD

//

// An order among nodes that do not constrain each other is still observable

// when the order becomes a link order: Mach-O runs initializers in link order,

// and the module graph's unit order is the order of the objects on the link

// line. Changing it changed a program's initialization (measured 2026-09-29:

// openkal's `same-source` example, linked for aarch64-macos, crashed at start

// when its units moved to the stable order below). A caller whose order

// reaches an artifact therefore keeps its order, and this module offers each

// order the engine uses:

//

// topological_order Kahn, lowest ready index first (stable)

// stack_topological_order Kahn, most recently readied first, over edges in

// the order given (the module graph's unit order)

// depth_first_order dependencies first, depth first, from roots in

// the order given (the host-module orders)

//

// STABILITY

//

// `topological_order` and `levels` are Kahn's algorithm with the ready set

// kept as an ordered set rather than an arbitrary queue: whenever more than

// one node has no unmet dependency, the LOWEST INDEX is emitted next. Two

// graphs that differ only in an unconstrained sibling order therefore

// disagree nowhere it can be observed by anything downstream, and the answer

// for a fully-ordered chain (0 depends on nothing, 1 depends on 0, ...) is

// always the identity permutation.

//

// CYCLES

//

// `topological_order` and `levels` report a cycle as the ordered PATH that

// walks it — `cycle = {a, b, c, a}`, read "a depends on b depends on c

// depends on a" — not merely the set of nodes that Kahn's algorithm could not

// retire. A path names the actionable edges; a set makes the reader

// reconstruct them. `closure` asks a different question (reachability, not

// order) and is defined to tolerate a cycle rather than reject it: a visited

// set already terminates the walk, and rejecting would turn every caller that

// does not care about order into one that has to.

export module mcpp.graph;

import std;

export namespace mcpp::graph {

// `deps[u]` = the node ids `u` depends on, `u` and each entry of `deps[u]`

// being indices into `deps` itself (0..deps.size()-1). Duplicate entries

// within one node's list are tolerated (treated as one edge).

using AdjacencyList = std::vector<std::vector<std::size_t>>;

// A cycle, reported as the ring it walks: `cycle.front() == cycle.back()`,

// and consecutive entries are a real edge (`cycle[i]` depends on

// `cycle[i + 1]`). Never empty when returned as an error — a ring has at

// least the two entries closing a self-loop (`{a, a}`).

struct CycleError {

std::vector<std::size_t> cycle;

};

// Dependency-first order: every node comes after every node it (transitively)

// depends on. See the module header for the stability and cycle contract.

std::expected<std::vector<std::size_t>, CycleError>

topological_order(const AdjacencyList& deps);

// `result[u]` = 0 when `u` has no dependencies, otherwise

// `1 + max(result[v] for v in deps[u])`. Same stability and cycle contract as

// `topological_order`, computed by walking that order once — every node's

// dependencies are already leveled by the time the node itself is reached.

std::expected<std::vector<std::size_t>, CycleError>

levels(const AdjacencyList& deps);

// Every node reachable from `roots` by following dependency edges

// transitively, returned sorted and deduplicated. `include_roots` selects

// whether the roots themselves are in the result (default: excluded, i.e. the

// STRICT closure — what the roots depend on, not the roots' own identity).

//

// Tolerant of cycles: a visited set already terminates the walk, so a cycle

// reachable from a root is silently absorbed into the answer rather than

// rejected. Closure is a reachability question; a caller that also needs to

// know a cycle is not well-formed asks `topological_order` or `levels`

// instead — that is exactly the caller (`plan.cpp`'s cache-key fold) that

// must reject one.

std::vector<std::size_t>

closure(const AdjacencyList& deps, std::span<const std::size_t> roots,

bool include_roots = false);

// Kahn's algorithm with the ready nodes on a stack: the node readied most

// recently is emitted next. `edges` holds (dependent, dependency) pairs over

// nodes 0..n-1, in the order that decides the ties. This is the order of the

// module graph's units, and so of the objects on a link line (see the header).

std::expected<std::vector<std::size_t>, CycleError>

stack_topological_order(std::size_t n,

std::span<const std::pair<std::size_t, std::size_t>> edges);

// What a dependency on a node still on the depth-first path means.

enum class Cycles {

Error, // a cycle: the order is refused with the ring

Skip, // the edge is ignored; the node is emitted where it stands

};

// Dependencies first, depth first: from each root in the order given, a node

// is emitted after every node it depends on, its dependencies visited in the

// order of `deps[u]`. Only nodes reachable from `roots` are emitted.

std::expected<std::vector<std::size_t>, CycleError>

depth_first_order(const AdjacencyList& deps, std::span<const std::size_t> roots,

Cycles cycles = Cycles::Error);

} // namespace mcpp::graph

namespace mcpp::graph {

namespace {

// Shared Kahn's-algorithm walk. Returns the dependency-first order, or (when

// a cycle remains) the CycleError both public functions report verbatim.

std::expected<std::vector<std::size_t>, CycleError>

kahn_order(const AdjacencyList& deps) {

const std::size_t n = deps.size();

std::vector<std::vector<std::size_t>> dependents(n); // reverse edges

std::vector<std::size_t> remaining(n, 0); // unmet deps left

for (std::size_t u = 0; u < n; ++u) {

for (auto v : deps[u]) {

remaining[u]++;

dependents[v].push_back(u);

}

}

std::set<std::size_t> ready; // ordered: smallest index served first

for (std::size_t u = 0; u < n; ++u)

if (remaining[u] == 0) ready.insert(u);

std::vector<std::size_t> order;

order.reserve(n);

while (!ready.empty()) {

auto it = ready.begin();

std::size_t u = *it;

ready.erase(it);

order.push_back(u);

for (auto w : dependents[u])

if (--remaining[w] == 0) ready.insert(w);

}

if (order.size() == n) return order;

// A cycle remains among the nodes Kahn's algorithm could not retire

// (`remaining[u] > 0`). Walk it with an explicit-stack DFS restricted to

// those nodes to recover the actual ring, rather than reporting the

// leftover set: the set says something is wrong, the ring says what.

std::vector<bool> stuck(n);

for (std::size_t u = 0; u < n; ++u) stuck[u] = remaining[u] > 0;

std::vector<char> state(n, 0); // 0 unseen, 1 on the current path, 2 done

std::vector<std::size_t> path;

for (std::size_t start = 0; start < n; ++start) {

if (!stuck[start] || state[start] != 0) continue;

std::vector<std::pair<std::size_t, std::size_t>> frame{{start, 0}};

while (!frame.empty()) {

auto& [u, k] = frame.back();

if (k == 0) {

state[u] = 1;

path.push_back(u);

}

bool descended = false;

while (k < deps[u].size()) {

auto v = deps[u][k++];

if (!stuck[v]) continue;

if (state[v] == 1) {

auto ring_start = std::ranges::find(path, v);

CycleError err;

err.cycle.assign(ring_start, path.end());

err.cycle.push_back(v);

return std::unexpected(std::move(err));

}

if (state[v] == 0) {

frame.push_back({v, 0});

descended = true;

break;

}

}

if (descended) continue;

state[u] = 2;

path.pop_back();

frame.pop_back();

}

}

// Unreachable in theory: Kahn's algorithm left at least one stuck node,

// and every stuck node's dependencies are themselves stuck (otherwise

// Kahn's algorithm would have retired it), so the DFS above always

// closes a ring before running out of stuck, unseen starting points.

// Reported defensively rather than assumed, as an unclosed path rather

// than a valid ring, so a defect here is legible instead of undefined.

CycleError err;

err.cycle = path;

return std::unexpected(std::move(err));

}

} // namespace

std::expected<std::vector<std::size_t>, CycleError>

topological_order(const AdjacencyList& deps) {

return kahn_order(deps);

}

std::expected<std::vector<std::size_t>, CycleError>

stack_topological_order(std::size_t n,

std::span<const std::pair<std::size_t, std::size_t>> edges) {

std::vector<std::size_t> remaining(n, 0);

std::vector<std::vector<std::size_t>> dependents(n);

for (auto [dependent, dependency] : edges) {

remaining[dependent]++;

dependents[dependency].push_back(dependent);

}

std::vector<std::size_t> order;

order.reserve(n);

std::vector<std::size_t> ready;

for (std::size_t u = 0; u < n; ++u)

if (remaining[u] == 0) ready.push_back(u);

while (!ready.empty()) {

const std::size_t u = ready.back();

ready.pop_back();

order.push_back(u);

for (auto w : dependents[u])

if (--remaining[w] == 0) ready.push_back(w);

}

if (order.size() == n) return order;

// The ring, found the way `topological_order` finds one.

AdjacencyList deps(n);

for (auto [dependent, dependency] : edges) deps[dependent].push_back(dependency);

auto ring = kahn_order(deps);

if (!ring) return std::unexpected(ring.error());

return std::unexpected(CycleError{});

}

std::expected<std::vector<std::size_t>, CycleError>

depth_first_order(const AdjacencyList& deps, std::span<const std::size_t> roots,

Cycles cycles) {

const std::size_t n = deps.size();

std::vector<char> state(n, 0); // 0 unseen, 1 on the current path, 2 done

std::vector<std::size_t> order;

std::vector<std::size_t> path;

for (auto root : roots) {

if (root >= n || state[root] != 0) continue;

std::vector<std::pair<std::size_t, std::size_t>> frame{{root, 0}};

state[root] = 1;

path.push_back(root);

while (!frame.empty()) {

auto& [u, k] = frame.back();

if (k < deps[u].size()) {

const auto v = deps[u][k++];

if (v >= n || state[v] == 2) continue;

if (state[v] == 1) {

if (cycles == Cycles::Skip) continue;

CycleError err;

err.cycle.assign(std::ranges::find(path, v), path.end());

err.cycle.push_back(v);

return std::unexpected(std::move(err));

}

state[v] = 1;

path.push_back(v);

frame.push_back({v, 0});

continue;

}

state[u] = 2;

order.push_back(u);

path.pop_back();

frame.pop_back();

}

}

return order;

}

std::expected<std::vector<std::size_t>, CycleError>

levels(const AdjacencyList& deps) {

auto order = kahn_order(deps);

if (!order) return std::unexpected(order.error());

std::vector<std::size_t> level(deps.size(), 0);

for (auto u : *order) {

std::size_t lv = 0;

for (auto v : deps[u]) lv = std::max(lv, level[v] + 1);

level[u] = lv;

}

return level;

}

std::vector<std::size_t>

closure(const AdjacencyList& deps, std::span<const std::size_t> roots,

bool include_roots) {

std::set<std::size_t> seen;

std::vector<std::size_t> stack(roots.begin(), roots.end());

for (auto r : roots) seen.insert(r);

while (!stack.empty()) {

auto u = stack.back();

stack.pop_back();

if (u >= deps.size()) continue;

for (auto v : deps[u])

if (seen.insert(v).second) stack.push_back(v);

}

if (!include_roots)

for (auto r : roots) seen.erase(r);

return {seen.begin(), seen.end()};

}

} // namespace mcpp::graph