# Design: DAG-parallel run-plan + parallelism-aware planning

audience: AI coding agents first. PLAN_SLUG: `run-plan-dag-parallel`. Date: 2026-06-27.

## Context

`run-plan` executes a session-state/v1 plan wave-by-wave. Today it is **sequential within a wave** (`run-plan.js:346-347`) — independent tasks serialize even when their dependency graph permits concurrency. phase3 (`2026-06-27-multideal-commerce-phase3.jsonl`) is the canonical loss: its DAG is `t1→{t2,t3}→t4→{t5,t6}→t7`; `t5` (checkout) and `t6` (redemption) are explicitly "different files, parallel OK" yet run one after the other.

Planning (`brainstorm`/`plan`) likewise does not deliberately expose parallelism — waves are authored as coarse ordering, not as parallel-eligibility groups, so the structure run-plan needs is often absent.

## Goal

1. `run-plan` runs every dependency-ready task in a wave **concurrently** (bounded by the Workflow concurrency cap), merging results into integration **serially** and fail-closed.
2. `brainstorm`/`plan` author waves as **parallelism groups**: same-wave tasks are mutually independent + file-disjoint; dependencies cross wave boundaries only.
3. **Two co-equal execution strategies over ONE shared primitive; the planner picks per plan by plan shape.** Both are permanent and first-class — neither is a deprecated version of the other:
   - **`sequential`** — one task at a time, in order. Correct for linear/simple plans where DAG machinery (per-round leasing, parallel worktrees, per-round integration build) is overkill.
   - **`dag-parallel`** — dependency-DAG run in parallel rounds. Correct for plans with independent branches, where sequential leaves real parallelism on the table.

   `meta.scheduler` carries the choice; the enum is OPEN (future strategies can be added). Absent ⇒ `sequential` (so every pre-existing plan runs unchanged — in-flight safety, regression-locked by test). Extract the per-task ladder as a shared primitive (`runTaskLadder`) both strategies compose — one ladder, no duplication, no drift. `plan` selects the strategy from the wave/dep structure it authored (rule in Component 2) and stamps it.

Explicitly OUT of scope (decided 2026-06-27, user): a separate-plan "program/run-program" layer. One plan, one integration branch, one PR. The program-of-plans design (`docs/design/run-program-dag.md`) is SUPERSEDED for this need — revive it only if separate PRs / separate repos per module are ever required.

## Scheduling semantics (the contract that makes parallel safe)

Scheduling is driven by the task **dependency DAG** (`deps`), not by wave index. Waves remain ONLY as integration-review barriers. This is backward compatible: existing plans carry both intra- and cross-wave deps (the old sequential engine tolerated them), so the engine must too — it schedules by deps, not by forbidding edges.

- **Within a wave, tasks run in dependency-respecting parallel ROUNDS (topological layers).** Round = the set of not-done tasks in the wave whose deps are ALL `done()`; run that set in parallel, merge, then recompute the next round until the wave is empty.
- **Same-round tasks MUST write disjoint file sets.** A round is what runs without seeing each other's changes; the serial merge conflicts if two same-round tasks touch the same file. Disjointness is the planner's assertion (tasks meant to run together → same wave, no dep edge, disjoint files); the engine's serial-merge-with-conflict-HALT is the safety net. Tasks in LATER rounds re-base off the post-merge integration head (same mechanism cross-wave deps already use via `lease`), so they correctly build on earlier rounds.
- **Stuck round = HALT:** pending tasks remain but no task is ready (unmet/cyclic deps) → fail-closed.
- **Wave barrier unchanged:** after all rounds in a wave merge, the cumulative-diff integration review (`P.integrate`, opus) runs before the next wave.

Authoring target (planner): put genuinely independent + file-disjoint work in the SAME wave with NO dep edge so it lands in ONE round (max parallelism). Intra-wave deps are tolerated (they just push a task to a later round) but indicate the work probably wanted separate waves — prefer cross-wave deps for clarity.

## Components

### 1. `run-plan.js` — shared ladder primitive + two strategies selected per-plan

Refactor, do NOT replace. Extract the per-task ladder into a shared primitive both strategies call; express each strategy as a composition of it. Select at the `phase('Execute')` site:

```
const scheduler = (m.meta && m.meta.scheduler) || 'sequential'   // absent ⇒ sequential (pre-existing plans)
if (scheduler === 'dag-parallel') await runDagParallel(waves, m, branch, intWt, route)
else if (scheduler === 'sequential') await runSequential(waves, m, branch, intWt, route)
else return halt('Execute', `unknown meta.scheduler "${scheduler}"`)   // fail-closed on a typo, never silent-default
```

- **`runSequential`** = today's `for (const w of waves) { for (const t of waveTasks) {...} }` (`run-plan.js:341-453`) re-expressed as: per wave, per task → `lease` → `runTaskLadder` → `P.commit` → integration review. Behavior identical to current; **a regression test locks ladder-via-primitive == prior inline behavior** (pre-existing plans depend on this).
- **`runDagParallel`** = the round loop (PHASE A1 serial lease / A2 parallel `runTaskLadder` / B serial merge / C integration gate0), then integration review. Detailed below.
- Both compose the SAME `runTaskLadder` primitive → one ladder, no drift. `meta.scheduler` is the only switch; an unknown value HALTs (no silent fallback that would mask a planner typo).

The ladder (lease → implement → gate0 → risk → finance → review → metagate) is unchanged in CONTENT — lifted verbatim into the primitive.

Seam — split the existing ladder so lease (worktree creation, git-lock contended) is serial and implement→metagate is parallel:

```
async function runTaskLadder(t, leased, route, m) -> {
  t, ok: boolean, base, head, wt, halt?: {stage, why, ctx}
}
// leased = {wt, base, head, resumed} from the serial lease pre-pass.
// Body = current lines 363-438 (implement through metagate), verbatim — NO lease, NO merge.
// On any current `return halt(...)` inside: return {ok:false, halt:{...}} instead
// (a halt inside parallel() must not abort siblings mid-flight — collect, then HALT).
```

Wave executor (replaces the inner loop) — round loop with serial lease + parallel build + serial merge + post-merge integration gate:

```
// pending = waveTasks not done()
// BLOCKED task with a blocker among pending -> halt('Execute', BLOCKED) (pre-check, serial)
// while (pending not empty):
//   ready = pending.filter(t => (t.deps||[]).every(d => done(dep d)))   // deps any wave
//   if (ready empty) -> halt('Execute', `stuck: unmet/cyclic deps ${pending ids}`)  // fail-closed
//   PHASE A1 — lease, SERIAL (git .git/worktrees lock — never parallelize worktree add):
//     const leased = []; for (const t of ready) { const ls = await sub(P.lease(m,t,branch),...)
//       if (!ls||!ls.ok) return halt('Execute', `lease failed ${t.id}`, ls); leased.push({t, ...ls}) }
//   PHASE A2 — implement+verify, PARALLEL over `ready`:
//     const results = await parallel(leased.map(L => () => runTaskLadder(L.t, L, route, m)))
//     if (results.some(r => !r || !r.ok)) -> halt('Execute', first r.halt)   // no partial merge
//   PHASE B — bless, SERIAL (deterministic order = ready order):
//     for (const r of results) {
//       const cm = await sub(P.commit(m, r.t, intWt, branch), ...)
//       if (!cm || !cm.committed) -> halt('Execute', merge/commit failed — conflict => HALT, never auto-resolve)
//       r.t.status = 'COMMITTED'; remove r.t from pending
//     }
//   PHASE C — CUMULATIVE BUILD GATE, SERIAL (restores the property sequential mode gave for free):
//     const ig = await sub(P.gate0(intWt, <wave base>, <integration head>), {schema:S_GATE0, label:`int-gate0:w${w}#round`})
//     if (!ig || !ig.green) -> halt('Execute', `integration gate0 red after round (cross-task break): ${ig&&ig.output}`)
//     // HALT, NOT a fixer loop — a cross-task break can't be attributed to one task;
//     // matches the "no LLM-improvised integration recovery" decision in [[run-plan-det-extraction]].
// (next round's lease cuts off the now-updated integration head — later rounds see earlier merges)
```

**Why PHASE C is mandatory, not optional.** In the old sequential loop each task leased off `branch` *with all prior tasks already merged* (line 357), so the last task's `gate0` was implicitly a full cumulative build of the wave. Parallel rounds break that: every task in a round cuts from the same integration head and `gate0`s only its own diff — nothing typechecks `integration + all merged tasks`. The wave-barrier `P.integrate` is an opus diff review, NOT a build. Without PHASE C a wave whose tasks each compile alone but break in combination (a type/symbol/import coupling the planner's file-disjoint judgment missed — plausible for phase3 `t2` fulfillment-platform.ts referencing `t3`'s `orderLineVoucherExt` schema) reaches the PR unbuilt. PHASE C is the real enforcement of correctness across parallel tasks; "file-disjoint" is only a proxy and they diverge exactly when this bites.

Constraints:
- Concurrency is auto-capped by the Workflow runtime (`min(16, cores-2)`); do not add a manual cap.
- **Invariant (preserve): `run-plan.js` MUST NEVER call `workflow()`.** Unrelated to this change directly, but the file stays a leaf Workflow; keep the existing comment/guard.
- Resume path (`ls.resumed`, lines 360-364) lives inside `runTaskLadder` unchanged — a parallel re-run still preserves committed task-branch work per task.

### 2. `plan` skill — parallelism pass

Add a step after wave/phase assignment: **express independent work as same-wave parallel tasks; never serialize for convenience.**
- Decision rule: tasks A,B go in the SAME wave with NO dep edge ⟺ neither is in the other's transitive dep closure AND they write disjoint files (→ they run in one parallel round). A real dependency → the dependent task goes in a LATER wave with a `deps` edge.
- Assertion the plan SHOULD satisfy: tasks that will share a round (same wave, no edge between them) are file-disjoint (verify by the files each is scoped to touch). Intra-wave deps are tolerated by the engine (scheduled in a later round) but are a smell — prefer cross-wave deps so the wave map reads as "these run together."
- Anti-pattern to reject: chaining independent tasks into separate sequential waves "to be safe" — that forfeits the parallelism this feature exists for.
- **Strategy selection (plan owns the wave structure, so it picks the execution strategy and stamps `meta.scheduler`):**
  - **`dag-parallel`** ⟺ the authored DAG has REAL parallelism to exploit: ≥1 wave containing ≥2 mutually-independent (no dep edge between them), file-disjoint tasks.
  - **`sequential`** otherwise — a linear dependency chain or all single-task waves, where the round machinery adds overhead/risk for no concurrency gain.
  - Decision rule (apply, don't derive): "any wave with ≥2 independent file-disjoint tasks → `dag-parallel`; else `sequential`." Stamp the chosen value verbatim in the `meta` line.

### 3. `brainstorm` skill — parallelism in session-file task authoring

Where brainstorm populates section 9 (`task` records) from the plan's wave table, add the same wave-purity contract (same-wave = independent + disjoint; deps cross waves). One-source-of-truth: reference the rule in `plan`, do not restate the derivation. **At that same point (wave structure now known), apply the strategy-selection rule and set `meta.scheduler`** — the choice depends on the wave/dep shape, so it is set when section 9 is populated, NOT guessed in the initial skeleton.

### 4. session-state/v1 schema — additive fields

Update the schema block in `brainstorm/SKILL.md` (canonical) + mirror note in `fix-rot`. Two additive changes, both backward compatible (absent ⇒ old behavior):
- `meta.scheduler: "sequential" | "dag-parallel"` — execution-strategy selector (open enum; unknown value HALTs at the engine). Absent ⇒ `sequential` (pre-existing plans). New plans get whichever the selection rule picks.
- OPTIONAL `files: [<path-or-glob>...]` on `task` records — the file set the task is scoped to write. Lets `plan` verify same-round disjointness mechanically and a future engine pre-flight conflicts. NOT required — absence falls back to the serial-merge-conflict-HALT safety net.

### 5. `fix-rot` — no new mechanism

fix-rot already emits the same schema. Only addition: when reconstructing tasks, keep the wave-purity contract (don't collapse genuinely-parallel work into one wave, don't invent intra-wave deps). One line referencing the `plan` rule.

## Data flow

```
/run-plan <slug>  → Workflow(run-plan.js)
  Load → Reconcile (vs git) → Setup integration worktree
  per wave (sequential barrier):
    round loop until wave empty:
      ready = pending whose deps all done; empty+pending ⇒ HALT (stuck)
      PHASE A1 lease × ready                     (serial — git worktree lock)
      PHASE A2 runTaskLadder × ready             (parallel, per-task worktrees)
      PHASE B  P.commit × passing                (serial merge → integration; conflict ⇒ HALT)
      PHASE C  gate0 on integration              (serial — cumulative build; red ⇒ HALT)
    integration review (opus, cumulative)        (barrier)
  converge (all COMMITTED) → open PR
```

## Error handling — fail-closed (unchanged philosophy)

- Any task ladder returns `ok:false` → whole wave HALTs; NO passing sibling is merged (no partial-wave landing). Resolve + re-run; resume preserves each task branch's committed work.
- Serial-merge conflict → HALT with the conflicting paths; never auto-resolve (matches existing `reset --hard` caution in [[run-plan-det-extraction]]).
- Post-merge integration gate0 (PHASE C) red → HALT (cross-task build break); no fixer loop — unattributable to one task.
- Stuck round (pending tasks, none ready: cyclic/unmet deps) → HALT, fail-closed.
- Intra-wave dep is NOT an error — it pushes the task to a later round. Only same-round file overlap surfaces (as a merge conflict → HALT).

## Testing

- **Regression guard (in-flight safety): `runSequential` over the extracted `runTaskLadder` == prior inline behavior** on a representative multi-wave plan (same lease/ladder/commit order, same HALT points). This is the test that lets us refactor the sequential path into the shared primitive without breaking draining plans.
- Engine: extend `~/.claude/workflows/lib/` test harness — unit `runTaskLadder` extraction (behavior identical to current sequential per-task path on a single task); `runDagParallel` with (a) 2 independent tasks → one round, both run parallel, merged in order; (b) one task fails → wave HALTs, no merge; (c) intra-wave dep A→B → two rounds (A then B), B leases off A's merge; (d) cyclic/unmet deps → stuck-round HALT; (e) merge conflict → HALT. Test both branches of every fail-closed line + a negative proof (per [[run-plan-det-extraction]] discipline).
- Empirical: run the real phase3 plan; confirm `t2∥t3` and `t5∥t6` run concurrently in `/workflows` and land one PR.
- Resume-cache: confirm `resumeFromRunId` keys cached `agent()`/`sub()` results on (prompt, opts) NOT call-order — a resumed parallel round must replay each task's result correctly regardless of completion order. Verify before relying on resume across a parallel wave.

## Architecture Decisions

- **Rejected: program-of-plans (`run-program`) layer.** With one-PR integration it is redundant with intra-plan DAG parallelism; pays off only for separate PRs/repos (not wanted). Design preserved, deferred: `docs/design/run-program-dag.md`.
- **Chosen: wave = parallelism group, serial merge.** Minimal change (per-task worktrees already exist), preserves the gate/review/metagate ladder, per-wave integration review, resume, and fail-closed semantics. The run-plan author pre-flagged it (`run-plan.js:346`).
- **Merge serialized, not parallel.** Merges are cheap; serial merge removes integration-branch races and gives deterministic conflict detection. Parallelism is spent where the cost is (implement+review), not on git plumbing.
- **Two co-equal strategies over one shared primitive, NOT old-vs-new and NOT a forked `run-plan-v2.js`.** `sequential` and `dag-parallel` are both permanent; the planner picks the minimal-sufficient one per plan (simple→sequential, branchy→dag-parallel). Per-plan `meta.scheduler` (open enum) gives in-flight safety (pre-existing plans default to the unchanged sequential path) without duplicating ~360 lines of plumbing. The extracted `runTaskLadder` primitive is the single ladder both compose → no drift. Decided 2026-06-27 (user: "2 separate ways of running workflows, we may need both … create primitives and reuse … to avoid the drift").

## Files changed

- `~/.claude/workflows/run-plan.js` — extract `runTaskLadder` primitive (implement→metagate, no lease/merge); add `runSequential` (legacy path over the primitive) + `runDagParallel` (round loop A1/A2/B/C); select by `meta.scheduler` (default sequential).
- `~/.claude/workflows/lib/` + test file — scheduler unit tests (new or extended).
- `~/.claude/skills/plan/SKILL.md` — parallelism pass + wave-purity contract.
- `~/.claude/skills/brainstorm/SKILL.md` — schema `files` field; wave-purity note in task authoring.
- `~/.claude/skills/fix-rot/SKILL.md` — wave-purity note on reconstruction.
- `~/.claude/docs/design/run-program-dag.md` — mark SUPERSEDED/deferred, point here.
```