T-JVXC-gs-dag-core

Status: open/ready · Impact: high · Complexity: medium

Goal

Implement the immutable DAG core as the graph_scheduler::graph module (L0): the foundation every other layer reads. On the v0.1 critical path.

Today

Location	Role today
packages/rust/graph-scheduler/	Does not exist. The crate is scaffolded by T-ROJC-gs-test-corpus-and-disabled-suites
solutions/ontological/lib/model/corpus/graph.ts	sdlc task next’s hand-rolled edge builder and cycle finder — the behaviour this module generalizes
packages/rust/intersect/	The layout precedent for a pure Rust crate in this repo

Proposed

An immutable Graph in src/graph.rs. Builder methods return a new Graph (structural sharing is fine), so a graph is safe to share across readers without a lock.

Item	Signature
NodeId	Newtype over String — an opaque id from the caller’s store
NodeAttrs	category: Option<String>, weight: Option<i64>, trigger: Option<TriggerRule>, plus an opaque extra: BTreeMap<String, serde_json::Value> passthrough
Graph::new()	An empty graph
Graph::add_node(id, attrs)	Returns a new Graph
Graph::depends_on(node, dependency)	Records “node depends on dependency”; returns a new Graph
Graph::attrs(&id)	Option<&NodeAttrs>
Graph::dependencies(&id) / dependents(&id)	Direct parents / children, in insertion order
Graph::ancestors(&id) / descendants(&id)	Transitive closures
Graph::topo_sort()	Result<Vec<NodeId>, CycleError>
Graph::has_cycle()	bool
Graph::cycles()	Vec<Vec<NodeId>> — the member sets, not just a flag

Three translation points where Rust does not follow the TypeScript sketch in layered-api.md:

• topo_sort returns Result<_, CycleError> rather than throwing. The D-BPD8 wording “throws on cycle” is the TypeScript spelling of the same contract.
• cycles() returns member sets, satisfying D-BPD8 first-consumer requirement B (task next emits CYCLE basenames=…). corpus/graph.ts’s findCycles already returns member sets and seeds the algorithm.
• NodeAttrs has no open index signature, because Rust has none. The three fields the built-in frontier and sorters read are named; anything else the caller carries goes in extra. NodeAttrs is not reachable from foreman’s src/api/v1 signatures, so the E1 emitter constraints (no generics, no serde(flatten)) do not bind it.

Cycle handling is lazy, per T-ROJC ratified default R-2: depends_on never fails, has_cycle/cycles report, topo_sort returns Err.

Approach

1. Implement src/graph.rs with the table above; keep every builder method non-mutating.
2. Implement topo_sort and cycle detection with Kahn’s algorithm over an insertion-ordered adjacency structure, so ties resolve by add_node order (T-ROJC ratified default R-1).
3. Un-ignore the Layer 1 suite in tests/graph.rs and make it green.
4. Keep the crate’s dependency set unchanged — serde and serde_json only.

Files to touch

Location	Kind	Change
packages/rust/graph-scheduler/src/graph.rs	modify	Replace the todo!() stubs with the immutable DAG core
packages/rust/graph-scheduler/src/lib.rs	modify	Re-export Graph, NodeId, NodeAttrs, CycleError
packages/rust/graph-scheduler/tests/graph.rs	modify	Remove #[ignore] from the Layer 1 suite

Acceptance criteria

• AC-1: Graph is immutable — add_node and depends_on return a new graph and leave the receiver unchanged.
• AC-2: dependencies, dependents, ancestors, descendants, topo_sort, has_cycle and cycles all behave as the Layer 1 fixture table specifies.
• AC-3: topo_sort returns Err(CycleError) naming a node on the cycle; depends_on never fails when it closes a cycle.
• AC-4: cycles() returns cycle member sets (first-consumer requirement B).
• AC-5: Every #[ignore] on the Layer 1 suite in tests/graph.rs is removed and cargo test -p graph-scheduler is green. Exception, found at implementation time: f_cycle_get_ready exercises get_ready (Layer 3, still a todo!()), so its #[ignore] is re-tagged to T-I3QP-gs-push-readiness-frontier rather than removed.
• AC-6: cargo clippy -p graph-scheduler --all-targets -- -D warnings is clean and the crate’s [dependencies] are still serde + serde_json.

Out of scope

• Status, trigger rules, readiness, filters, sorters — later tasks in the chain.
• Any change to packages/rust/foreman.

Dependencies

• T-ROJC-gs-test-corpus-and-disabled-suites — scaffolds the crate and lands the ignored Layer 1 suite this task enables.

Depends on

T-ROJC-gs-test-corpus-and-disabled-suites

---

← Back to Tasks