Spec: Fork–Join Work Graph (F3 Top-3) #308

Problem Statement

Library consumers need an in-process async DAG of work steps that share one TContext, where edges mean readiness dependencies only (not typed payload channels), with compile-time proof of graph legality (cycle / unknown dependency / duplicate id / self-dependency / contract mismatch) and runtime dual-path assembly (WorkGraphBuilder / IWorkGraph plus attribute-driven generation). Existing surfaces do not cover this:

• Composite parallel traversal (ADR-006) parallels tree depth, not multi-predecessor DAG waves.
• Step Builder proves construction step completeness, not async execution readiness.
• Command Router is 1:1 dispatch, not a fork–join graph.
• Watch-list Channel Pipeline and BCL TPL Dataflow are typed message networks — out of this domain's edge model.

This work is F3 admission Top-3 from Wayfinder map #244 / ROADMAP F3. Wayfinder map for this Spec: #300. Domain vocabulary lives in CONTEXT.md; API stub for reaction: docs/.Local/prototypes/work-graph-mvp-api-stub.md on branch prototype/work-graph-api-stub (#306).

Solution

Ship Fork–Join Work Graph (API prefix Work*):

• Holder marker type with [WorkGraph<TContext>] names the graph and fixes TContext (prefer static class).
• Step types implement IWorkStep<TContext> with ValueTask ExecuteAsync(TContext, CancellationToken) and [WorkStep(typeof(Holder), Id = "…", DependsOn = …)] (explicit holder membership).
• Manual path: WorkGraphBuilder<TContext>.Add(id, step, params dependsOn).Build() → IWorkGraph<TContext>.RunAsync(ctx, ct) returning ValueTask (no trace in MVP).
• Generated path: {Name}WorkStepKeys (public const string ids) + {Name}WorkGraph.Create(resolver | dictionary) filling the builder.
• Execution: async-only; topological waves; same-wave steps may run concurrently; fail-fast (cancel in-flight peers; throw). Document that overlapping unsynchronized writes to TContext are forbidden; library does not isolate/merge context.
• Diagnostics (MVP matrix): see Implementation Decisions — IDs allocated in first Diagnostics PR from DP087+ (Spec does not pre-reserve numbers).
• MVP Sample sketch (sibling Samples, not in this Spec's implementation): request-prep graph Auth ∥ LoadConfig → BuildPrincipal → Authorize.
• Namespace sketch (validated): DesignPatterns.Behavioral.

User Stories

1. As an application developer, I want a [WorkGraph<TContext>] holder separate from step classes, so that graph name and context type have a single generation anchor.
2. As an application developer, I want each step to be a type implementing IWorkStep<TContext>, so that steps are independently unit-testable.
3. As an application developer, I want [WorkStep(typeof(Holder), Id, DependsOn)] to declare membership and edges, so that multiple graphs may share the same TContext without silent aggregation.
4. As an application developer, I want ExecuteAsync to mutate shared TContext and return ValueTask, so that outputs do not require typed payload edges.
5. As an application developer, I want WorkGraphBuilder to register steps and Build() to validate the DAG at runtime, so that tests and dynamic scenarios work without the generator.
6. As an application developer, I want IWorkGraph.RunAsync to execute topological waves with fail-fast cancellation, so that fork–join semantics match the domain card.
7. As an application developer, I want generated {Name}WorkStepKeys, so that call sites and diagnostics share stable string ids (Strategy/Factory Keys precedent).
8. As an application developer, I want {Name}WorkGraph.Create(resolver|map) to materialize IWorkGraph from the attribute catalog, so that attribute and manual paths share execution semantics.
9. As an application developer, I want cycle, unknown DependsOn, duplicate id, and self-dependency to be Errors, so that illegal graphs cannot ship.
10. As an application developer, I want unreachable steps to be Warnings while multi-root graphs remain valid, so that Sample-style Auth ∥ LoadConfig works and dead steps are still visible.
11. As an application developer, I want [WorkStep] / IWorkStep / TContext mismatches to be Errors, so that attribute catalogs stay consistent with holder context.
12. As an application developer, I want empty graphs rejected and single-node / diamond graphs accepted, so that edge cases are unambiguous in Spec and tests.
13. As an application developer, I want MVP without Dop options, trace types, DI, or sync Execute, so that the first ship stays thin.
14. As an application developer, I do not want typed TIn/TOut edges or Channel<T> stage wiring in this domain, so that Channel Pipeline stays a watch-list boundary.
15. As an application developer, I do not want this domain to extend Composite TraverseParallel* or impersonate TPL Dataflow, so that Non-goals stay crisp.
16. As a library consumer on netstandard2.0 and net8.0, I want Core + generated code on both TFMs, so that the dual-TFM baseline holds.
17. As a developer, I want generation without AppDomain reflection scanning, so that AOT/trim goals stay aligned with AGENTS.md.
18. As a developer, I want actionable diagnostic messages (which ids / which edge), so that AGENTS.md messageFormat guidance holds.
19. As a developer, I want Design Doc WorkGraph.md (or agreed name) plus design index entry, so that API/diagnostics/trade-offs are recorded like other domains.
20. As a documentation reader, I want CHANGELOG and ROADMAP F3 Top-3 status updates when milestones land, so that backlog state stays truthful.
21. As a maintainer, I want DP### IDs allocated from the next free ID (DP087+) in the first Diagnostics PR without Spec pre-reservation, so that unused numbers are not burned.
22. As a maintainer, I want DiagnosticIds / descriptors / AnalyzerReleases / AGENTS.md updated in the same PRs that introduce rules, so that AGENTS.md process holds.
23. As a maintainer, I want each solution module in its own PR, so that AGENTS.md module boundaries hold.
24. As a maintainer, I want Runtime unit tests for builder validation + wave/fail-fast behavior and generator Verify for attribute emission/diagnostics, so that both dual-path seams stay locked.
25. As a sample author, I want a request-prep Sample in DesignPatterns.Samples after APIs exist, so that ROADMAP admission criterion Allow multiple HandlerOrder attributes on a single handler class #3 is satisfied.
26. As a contributor, I want XML docs on public APIs, file-scoped namespaces, and nullable enable, so that repo coding standards apply.
27. As a release manager, I want no version bump/tag/publish as part of feature PRs unless explicitly requested, so that AGENTS.md release policy holds.
28. As a future implementer, I want MVP not to forbid later Dop, trace/observer, sync path, aggregate failure, DI, or unregistered-step Analyzer, so that Phase 2+ stays additive.
29. As an application developer, I do not want an unregistered-IWorkStep Analyzer in MVP, so that the manual builder path is not forced through attributes.

Implementation Decisions

Scope and phasing

• Domain name: Fork–Join Work Graph; API prefix Work*.
• MVP (must): Runtime IWorkStep / IWorkGraph / WorkGraphBuilder + attributes [WorkGraph<T>] / [WorkStep]; generator Keys + Create facade; diagnostic matrix below; Design Doc + ROADMAP/AGENTS/CHANGELOG; Runtime tests + generator Verify; dual TFM.
• Phase 2+ (same domain): MaxDegreeOfParallelism / run options; RunAsync trace/observer; sync path; aggregate/continue failure; DI/Autofac registration; unregistered-step Analyzer.
• Samples: sibling repo after APIs usable.

Locked surface (grill + prototype)

From #303 / #306:

[WorkGraph<TContext>] static class Holder { }

[WorkStep(typeof(Holder), Id = "…", DependsOn = new[] { "…" })]
sealed class Step : IWorkStep<TContext> {
  ValueTask ExecuteAsync(TContext context, CancellationToken cancellationToken);
}

new WorkGraphBuilder<TContext>().Add(id, step, dependsOn…).Build();
await graph.RunAsync(ctx, ct); // ValueTask

HolderWorkStepKeys.*;
HolderWorkGraph.Create(resolveById | dictionary);

Diagnostic matrix (MVP)

From #304:

DP###: not reserved in this Spec; first Diagnostics PR assigns from DP087+.

Edge-case acceptance (Spec-required)

From #305:

• Empty graph → illegal (Build / Create Error).
• Single-node → legal; RunAsync executes it.
• Diamond (A→C, B→C) → legal; C after both predecessors.

Boundary vs siblings

From #302 / #301:

• vs Channel Pipeline (watch list): no typed payload edges / Channel<T> wiring — name in Out of Scope; do not admit/specify that domain.
• vs Composite parallel (ADR-006): tree-level traversal ≠ DAG readiness waves; do not extend CompositeTraverser.
• vs TPL Dataflow: not a message-block network / actor mailbox; may consume Task/ValueTask/WhenAll.
• vs Step Builder: construction completeness ≠ execution DAG.
• Compile-time analogues to cite: Composite DP011/012 (+ schema), State DP056–059, Step Builder DP082/084.
• Runtime wave analogue to cite (ideas only): Composite ADR-006 BFS same-level parallel.

Modules (one PR each)

• Runtime: attributes, IWorkStep, IWorkGraph, WorkGraphBuilder, execution/fail-fast.
• Diagnostics: allocate DP087+ for MVP generator diagnostics; descriptors + AnalyzerReleases + AGENTS table.
• SourceGenerators: Work Graph generator + Verify (Keys, facade, diagnostic cases).
• Docs: Design Doc, ROADMAP F3 Top-3, AGENTS summary row, CHANGELOG; update CONTEXT.md if needed.
• Samples (sibling): request-prep — separate Issue/PR in DesignPatterns.Samples.
• Analyzers / CodeFixes / DI / Autofac / Package: not MVP (Package only if packing requires).

Architectural constraints (AGENTS.md)

• Primitives over frameworks; Core without MSDI; dual TFM; Roslyn 4.8.0; nullable; TreatWarningsAsErrors; English for issues/PRs/commits.
• No AppDomain reflection registration scans.
• Diagnostic help links via existing DiagnosticHelpLinks pattern.
• Single-module PRs.

Testing Decisions (seams — confirmed)

What makes a good test here: assert observable behavior — Runtime: Build validation exceptions, wave ordering, fail-fast cancellation; Generator: Verify public sources + diagnostic IDs/severities/messages — not private helpers.

Primary seams:

1. DesignPatterns.Tests — builder/RunAsync behavior (empty/single/diamond; cycle/dup/self/unknown at Build; fail-fast).
2. DesignPatterns.SourceGenerators.Tests — Verify Keys/facade emission + diagnostic matrix cases.

Secondary: Docs module; Samples sibling after API exists.

Modules under test: Runtime + SourceGenerators (both MVP); then Docs; Samples later.

Out of Scope

• Implementing Channel Pipeline, Resilience Pipeline, Specification, Proxy, or other watch/rejection-list domains.
• Typed payload edges; Channel<T> stage wiring.
• Extending Composite TraverseParallel* as Work Graph.
• TPL Dataflow alternative/wrapper/actor mailbox.
• MVP Dop / run options; MVP trace/observer; MVP sync Execute; MVP aggregate/continue failure; MVP DI/Autofac; MVP unregistered-step Analyzer.
• TContext isolate/merge framework.
• Spec-time DP### number reservation.
• API freeze, stable SemVer policy change, or NuGet publish as part of this feature work.
• Changing ADR-008 Singleton diagnostic ID assignments (DP067–DP071).
• VSIX CompletionProvider / Rider plugins.
• Step Builder Phase 2 / Command Router housekeeping in this Spec's delivery.

Further Notes

• Wayfinder map: #300; child resolutions Research: in-repo DAG validation and wave-orchestration analogues #301–Prototype: stub Work* API outline for Spec reaction #306.
• Peer Spec structure: #256 Command Router; #287 Step Builder.
• API stub: prototype/work-graph-api-stub / docs/.Local/prototypes/work-graph-mvp-api-stub.md.
• Research notes (local branches): research/work-graph-dag-analogues, research/work-graph-nongoals-boundaries.
• After this Spec: /to-tickets should split Runtime → Diagnostics → SourceGenerators+Verify → Docs → Samples (sibling) with blocking edges; each /implement in a fresh session.
• Destination of map Wayfinder: Fork–Join Work Graph MVP Spec #300 is this Spec issue; map closes when this issue exists (no implementation in the map).