# MWP-2 — Correctness fallback for `_walk_commit_delta` (fixes RC-2)

> Sub-ticket of the MWP MVP master tracker:
> **muse#58** — https://staging.musehub.ai/gabriel/muse/issues/58
> Predecessor: **musehub#106** (MWP-1, generation authority) — closed.
> (Formal cross-issue links are not available yet; this issue and #58 cross-reference by URL.)

## Background

`muse clone` has no dedicated endpoint — it is a full `POST /fetch/mpack` with
`have=[]`, served from the prebuilt-mpack cache. The fetch path discovers which
commits to ship by calling `_walk_commit_delta`
(`musehub/services/musehub_wire_fetch.py::_walk_commit_delta`). That function has
**two** internal walks:

1. **Graph fast-path** (lines 66–157) — a *generation-bounded range scan* of
   `musehub_commit_graph` followed by a BFS over the parent pointers found in
   that scan. This is the only live path: line 66 pins `if True:` so the path
   below it never runs.
2. **Legacy DAG walk** (lines 159–184) — a `walk_dag_async`
   (`musehub/graph/walk.py::walk_dag_async`) over `MusehubCommit.parent_ids`,
   the *authoritative* DAG. It is currently **dead code** behind that `if True:`.

### The bug (RC-2)

The graph fast-path is correct **only if every generation in
`musehub_commit_graph` is correct**. MWP-1 (musehub#106) made generations
authoritative *at write time* and added a repair routine, but the fetch walk
still has **no safety net** when a generation is wrong or a graph row is missing
for any reason the write-path didn't cover (a pre-MWP-1 artefact, a backfill gap,
a partial/failed prior push that wrote `musehub_commits` but not the graph row,
or a future regression).

Concretely, the graph fast-path truncates silently in two ways:

- **Range-scan exclusion.** The scan is
  `generation > min_have_gen AND generation <= max_want_gen`
  (`_walk_commit_delta` lines 109–110). `max_want_gen` is the max generation of
  the `want` tips. If any *ancestor* of a tip has a generation **greater** than
  the tip's (impossible when correct, but exactly what a corrupt low tip
  generation produces relative to its true ancestors) or a tip's generation is
  understated, real ancestors fall outside `(min_have_gen, max_want_gen]` and are
  never loaded into `graph_map`.
- **BFS dead-end on missing rows.** The BFS (lines 122–136) reads parents from
  `graph_map.get(cid, ([], None, 0))`. Any commit absent from `graph_map` —
  whether because the range scan excluded it or because it has no graph row at
  all — yields the empty-parent default, so the BFS **stops** there and every
  ancestor beyond it is dropped from the returned set.

A truncated return set means the assembled mpack is missing commits and their
blobs. The tip-snapshot resolver (`wire_fetch_mpack` lines 485–491,
`ORDER BY generation DESC LIMIT 1`) then picks the wrong (older) snapshot, the
mpack is cached against the new tip id, and **clone returns HTTP 200 with a
working tree missing the latest commits** — the original clone-after-push
symptom, now caused at the *read* side rather than the write side.

### Why MWP-1 is necessary but not sufficient

MWP-1 added a fetch-side guard (`[MWP1_13]`, `wire_fetch_mpack` lines 512–540):
when `want_tip_snap_id` (graph max-gen) disagrees with the authoritative
`MusehubCommit.snapshot_id`, it calls
`musehub/services/musehub_wire_push.py::repair_corrupt_commit_generations` and
re-queries the tip snapshot. That **repairs the persisted graph** so the *next*
clone is fast and correct.

It does **not** make the *current* `_walk_commit_delta` return set complete:
the walk already returned a truncated `needed_rows` *before* the guard runs
(`needed_rows = await _walk_commit_delta(...)` at line 414; the guard is at 512).
Repair fixes generations, but the commit set handed to mpack assembly this
request was computed from the pre-repair graph. MWP-1 masks the symptom for the
tip-snapshot case after a self-heal; MWP-2 makes the walk itself self-correcting
so the **current response is always complete**, for every detection signal, at
all three call sites, even if repair never runs.

MWP-1 and MWP-2 are complementary and both stay:
- **MWP-1 repair** — heals the persisted graph (keeps future clones on the fast path).
- **MWP-2 fallback** — guarantees the *current* walk result is complete, now.

## Goal

- `_walk_commit_delta` **never returns a truncated commit set**. When the graph
  fast-path cannot be trusted, it falls back to the authoritative
  `MusehubCommit.parent_ids` DAG walk and returns the complete ancestor closure
  of `want` minus `have`.
- The `if True:` dead-code guard (line 66) is removed; the legacy DAG walk
  becomes the live, tested fallback — not dead code.
- The fallback is **cheap to decide** (no extra query in the common case) and
  **bounded** when it runs, so steady-state clone latency is unchanged.
- All three call sites (`wire_fetch_presign`, `wire_fetch_mpack`, `wire_fetch`)
  benefit from the single seam, with no per-call-site changes required.
- A non-skipped regression test proves a clone served entirely by the fallback
  (graph deliberately corrupted, repair patched out) returns every commit and blob.

## Design

### Detection — free in the common case

The fast-path BFS already knows whether it touched a commit it could not find in
`graph_map`. Track one boolean during the existing BFS:

```python
graph_incomplete = bool(_missing_from_graph)   # any start tip missing a graph row
...
for cid in frontier_mem:
    ...
    entry = graph_map.get(cid)
    if entry is None:
        graph_incomplete = True            # reachable commit not in the range scan
        pids_for_cid, _, _gen = [], None, 0
    else:
        pids_for_cid, _, _gen = entry
    ...
```

`graph_incomplete` becomes true exactly when the BFS would dead-end: a `want`
tip with no graph row, or any reachable commit excluded from the range scan
(the corrupt-generation case). No extra query — it is derived from data the
fast-path already loads.

When `graph_incomplete` is `False`, the fast-path result is provably the full
closure (every reachable commit had its true parents in `graph_map`), so we
return it unchanged — **zero added cost on the steady-state happy path.**

### Fallback — authoritative DAG walk

When `graph_incomplete` is `True`, log loudly and re-walk from `starts` over the
authoritative parent pointers:

```python
logger.error(
    "[MWP2] graph walk incomplete (missing_starts=%s, dead_end during BFS) — "
    "falling back to authoritative MusehubCommit DAG walk; want=%d have=%d",
    _missing_from_graph, len(starts), len(have_set),
)
return await _walk_commit_delta_dag(session, starts, have_set)
```

`_walk_commit_delta_dag` is the current lines 159–184 promoted to a named helper,
with two fixes:

1. **Topological ordering (parents-first).** `walk_dag_async` yields tips→roots
   (children before parents). The client applies commits sequentially and skips
   any whose parent is not yet applied, so a children-first dict is correct but
   wasteful. Re-order the collected commits parents-first using Kahn's algorithm
   over the reachable subgraph of `MusehubCommit.parent_ids` — mirror the
   topo-sort already proven in
   `musehub/services/musehub_wire_push.py::_resolve_generation_with_backfill`.
2. **Bounded walk.** Pass `max_nodes` to `walk_dag_async` (a generous cap, e.g.
   the count of `musehub_commits` rows, or a fixed ceiling such as 100_000) so a
   pathological corrupt graph cannot drive an unbounded scan. Log if the cap is hit.

The helper returns the same `_CommitDeltaMap` shape the fast-path returns
(`dict[commit_id -> SimpleNamespace(commit_id, snapshot_id, parent_ids)]`), so
downstream code in all three callers is unchanged. `snapshot_id` and
`parent_ids` come from the `MusehubCommit` rows the walk already loads into
`_row_cache`.

### Why detection lives inside `_walk_commit_delta`, not in `wire_fetch_mpack`

The tip-snapshot mismatch (`[BLOB-DEBUG]` / `[MWP1_13]`) is computed in
`wire_fetch_mpack` only, *after* the walk, and only for that one caller.
`wire_fetch_presign` (line 224) and `wire_fetch` (line 1127) have no such guard.
Putting detection + fallback inside `_walk_commit_delta` fixes all three with one
change and guarantees a complete set *before* any snapshot resolution runs.

### Interaction with MWP-1's `[MWP1_13]` guard

Leave the `[MWP1_13]` repair in place — it keeps the persisted graph healthy.
After MWP-2, the sequence for a corrupt graph is:
1. `_walk_commit_delta` detects incompleteness → returns the **complete** set via
   the DAG fallback (current response correct).
2. `wire_fetch_mpack`'s `[MWP1_13]` guard still notices the stale tip snapshot →
   repairs generations (future responses back on the fast path).

No change to `[MWP1_13]` is required; add an assertion in the E2E test that with
repair patched **out**, the fallback alone still yields a complete mpack.

## Phases (load-bearing; each green before the next)

### Phase 0 — Reproduce (red) ✅ COMPLETE
- [x] `MWP2_01` Unit: missing interior graph row for C3 in C1←C2←C3←C4 chain;
  graph has C1(gen=0), C2(gen=1), C4(gen=3) — C3 absent. BFS dead-ends at C3
  (empty-parents default), C2/C1 never added to reachable set. **RED** confirmed
  (`reachable=2`, missing C2 and C1).
- [x] `MWP2_02` Unit: want tip C3 absent from graph in C1←C2←C3 chain.
  max_want_gen=0 (C3→None→default 0); range scan returns only C1(gen=0); BFS
  from C3 finds no parents in graph_map. Result: {C3} only. **RED** confirmed.
- [x] `MWP2_03` Unit (guard against over-fallback): fully consistent graph —
  C1(gen=0), C2(gen=1), C3(gen=2); walk_dag_async never called. **GREEN**.

> **Phase 0 complete** (commit `sha256:4dd2a937f66f8`):
> Both reproduction tests are RED for the right reason — BFS dead-end at missing
> graph rows, logging `reachable=1` and `reachable=2` respectively. MWP2_03 pins
> the happy-path contract. No production code changed.

### Phase 1 — Promote the DAG walk to a tested helper ✅ COMPLETE
- [x] `MWP2_04` Promoted the dead legacy walk (old lines 159–184) to
  `_walk_commit_delta_dag(session, starts, have_set) -> _CommitDeltaMap`.
  Removed the `if True:` dead-code guard; the fast-path body is now the
  direct body of `_walk_commit_delta`. The helper adds Kahn's topo-sort
  (parents-first) and `max_nodes=100_000` bound with a WARNING log if hit.
  Returns `MusehubCommit` rows directly (avoids the downstream bulk re-fetch).
- [x] `MWP2_05` `_walk_commit_delta_dag` over C1←C2←C3 returns {C1,C2,C3}
  with correct `snapshot_id` and `parent_ids` on every row. **GREEN**.
- [x] `MWP2_06` Kahn's sort produces parents-first dict order: `idx[C1] <
  idx[C2] < idx[C3]` in a linear chain. **GREEN**.

> **Phase 1 complete** (commit `sha256:d984bd63c5abb`):
> `_walk_commit_delta_dag` is a tested, callable top-level helper. The
> `if True:` dead-code guard is gone. MWP2_01 and MWP2_02 remain RED —
> the helper is not yet wired into the fast-path BFS (Phase 2).

### Phase 2 — Wire detection + automatic fallback ✅ COMPLETE
- [x] `MWP2_07` Added `graph_incomplete: bool` to the fast-path BFS:
  initialized to `any(s not in graph_map for s in starts)` (missing start tips),
  then set to `True` during BFS whenever `graph_map.get(cid) is None`
  (dead-end interior node). After the BFS, `if graph_incomplete:` logs `[MWP2]`
  at ERROR and returns `_walk_commit_delta_dag(session, starts, have_set)`.
  **Makes MWP2_01 and MWP2_02 GREEN.**
- [x] `MWP2_08` MWP2_03 updated to patch `_walk_commit_delta_dag` directly
  (was: `walk_dag_async`). Consistent graph never triggers the fallback. **GREEN**.
- [x] `MWP2_09` `have` boundary honored under fallback: C1←C2←C3←C4, C3
  absent from graph (triggers fallback), `want=[C4] have=[C2]` → result is
  {C3, C4}; C1 and C2 absent. **GREEN**.

> **Phase 2 complete** (commit `sha256:984cdb57998d2`):
> All 6 Phase 0+1+2 tests GREEN. MWP2_01 and MWP2_02 (the Phase 0 RED gates)
> are now GREEN — the fallback returns the complete ancestor closure for both
> truncation scenarios. MWP-1's 13 tests unaffected (19 total GREEN).

### Phase 3 — Bounded fallback + stress ✅ COMPLETE
- [x] `MWP2_10` Pass `max_nodes` to `walk_dag_async` inside
  `_walk_commit_delta_dag`; log a `[MWP2]` warning if the cap is reached. Choose
  the cap as `count(musehub_commits)` for the repo, or a fixed ceiling.
  Implemented: `max_nodes=100_000` fixed ceiling (Phase 1); Phase 3 adds two
  assertions — kwarg wired (`max_nodes=100_000` captured via
  `patch.object(_walk_mod, "walk_dag_async")`) and warning fires when
  `walk_dag_async` yields exactly 100,000 items. Kahn's sort switched to
  `collections.deque.popleft()` so O(n) holds even for bushy graphs. **GREEN**.
- [x] `MWP2_11` Stress: a 5,000-commit linear history with no graph rows (forces
  full DAG fallback) completes, returns all 5,000 commits in parents-first topo
  order, and stays within the bound. Single `flush()` (no commit) keeps
  SQLAlchemy identity map warm — `session.get()` is O(1) per adjacency call.
  Topo-order verified: every parent in result appears before its child. **GREEN**.

> **Phase 3 complete**:
> Production fix: `from collections import deque`; Kahn's queue now uses
> `deque.popleft()` instead of `list.pop(0)` — O(n) guaranteed for all graph
> shapes. Two new tests GREEN: MWP2_10 (max_nodes kwarg wired + cap warning)
> and MWP2_11 (5,000-commit stress, full fallback, topo order verified).
> MWP-1's 13 tests unaffected (21 total GREEN).

### Phase 4 — End-to-end regression (the acceptance gate) ✅ COMPLETE
- [x] `MWP2_12` E2E via `wire_fetch_mpack(..., force_build=True)`: push C1→C2→C3
  (in-memory backend, mirror `test_mwp1_generation_authority.py::_InMemBackend`),
  then **corrupt the graph** so the fast path truncates (delete/wrong-gen a
  middle row), then **patch out** `repair_corrupt_commit_generations` so MWP-1's
  guard cannot self-heal. Clone with `want=[C3], have=[]`. Assert the assembled
  mpack contains C1, C2, C3 and C3's blob — proving the **fallback alone** ships
  a complete clone. **This is the acceptance gate.**
- [x] `MWP2_13` E2E: same setup **with** repair enabled — assert the response is
  complete *and* a follow-up `_walk_commit_delta` runs on the fast path (graph
  healed, `graph_incomplete == False`). Proves MWP-1 + MWP-2 compose.
  Implemented: first clone fires fallback (complete); INSERT C2's graph row back
  (simulating repair/re-push); second `_walk_commit_delta` with dag patched to
  raise → no raise → fast path confirmed. **GREEN**.

> **Phase 4 complete**:
> Two new E2E tests GREEN. `_InMemBackend` + `_e2e_push` helper mirror the
> MWP1_14 pattern. MWP2_12 asserts the fallback alone (repair patched out)
> returns {C1, C2, C3} and C3's blob — the acceptance gate. MWP2_13 proves
> composition: first clone completes via fallback; after graph is healed (C2
> reinserted), second `_walk_commit_delta` uses the fast path (dag helper
> patched to raise, no exception → fast path confirmed). MWP-1 guard assertion:
> `mock_repair.assert_not_called()` verifies the missing-row corruption does not
> trigger MWP-1's snapshot-mismatch guard (RC-2 ≠ RC-1). 23 total GREEN
> (10 MWP2 + 13 MWP1).

## Acceptance criteria

- [x] `_walk_commit_delta` returns the complete ancestor closure of `want` minus
      `have` even when `musehub_commit_graph` has a wrong or missing generation
      (`MWP2_01`, `MWP2_02`, `MWP2_12`).
- [x] A fully consistent graph never pays for the fallback — zero extra queries,
      DAG helper not invoked (`MWP2_03`, `MWP2_08`).
- [x] The fallback result is in parents-first topological order (`MWP2_06`).
- [x] The fallback is bounded and survives a full-history corruption without
      blowing up (`MWP2_10`, `MWP2_11`).
- [x] A clone served *entirely* by the fallback (repair patched out) returns
      every commit and blob (`MWP2_12`). Codified as a non-skipped regression test.
- [x] The `if True:` dead-code guard is gone; the legacy walk is live and tested.

## Testing tiers

| Tier | Coverage |
|------|----------|
| Unit | detection flag, DAG helper closure, topo ordering, have-boundary |
| Integration | DB-backed corrupt/missing graph rows; fast-path vs fallback selection |
| End-to-end | push → corrupt graph → clone via fallback returns complete mpack |
| Stress | full-history fallback over a 5,000-commit chain, bounded |
| Data integrity | no truncated commit set under any graph corruption |

## Out of scope

- Repairing the persisted graph — that is MWP-1's `repair_corrupt_commit_generations`
  and the `[MWP1_13]` guard, which remain unchanged.
- Job enqueue dedup on back-to-back pushes — **MWP-3**.
- Prebuild/index ordering — **MWP-4**.
- Client 503 retry — **MWP-5**.
- Broad re-enable of the skipped wire suite — **MWP-6**.

## Anchors

- `musehub/services/musehub_wire_fetch.py::_walk_commit_delta` (detection seam; remove `if True:` at line 66; promote legacy walk lines 159–184)
- `musehub/services/musehub_wire_fetch.py::wire_fetch_mpack` (main caller, line 414; `[MWP1_13]` guard lines 512–540 — leave intact)
- `musehub/services/musehub_wire_fetch.py::wire_fetch_presign` (caller, line 224)

---

## ✅ Closed — 2026-06-28

All 4 phases delivered, 23 tests GREEN (10 MWP2 + 13 MWP1), all 6 acceptance
criteria met. Summary:

- **RC-2 fixed**: `if True:` dead-code guard removed. Fallback is live.
- **MWP-2 correctness**: `_walk_commit_delta` now detects graph incompleteness at
  both entry points (missing start tip; interior dead-end) and falls back to the
  authoritative `MusehubCommit` DAG walk.
- **O(n) Kahn's sort**: `collections.deque.popleft()` replaces `list.pop(0)` —
  guaranteed O(n) for all graph shapes including bushy ones.
- **Bounded**: `max_nodes=100_000` hard ceiling wired into `walk_dag_async`; warning
  logged if the cap fires.
- **E2E acceptance gate** (MWP2_12): push C1→C2→C3, delete C2's graph row, patch
  out MWP-1 repair, clone — mpack contains all 3 commits and C3's blob. Non-skipped
  regression test. `mock_repair.assert_not_called()` proves MWP-1 snapshot-mismatch
  guard does NOT fire for missing-row corruption (RC-2 ≠ RC-1).
- **Composition proven** (MWP2_13): after graph is healed, `_walk_commit_delta` uses
  the fast path — dag helper patched to raise, no exception raised.
- `musehub/services/musehub_wire_fetch.py::wire_fetch` (caller, line 1127)
- `musehub/graph/walk.py::walk_dag_async` (authoritative DAG walk; accepts `exclude=have_set`, `max_nodes`)
- `musehub/services/musehub_wire_push.py::_resolve_generation_with_backfill` (Kahn topo-sort pattern to mirror for parents-first ordering)
- `musehub/services/musehub_wire_push.py::repair_corrupt_commit_generations` (MWP-1 repair; patched out in `MWP2_12`)
- New test file: `musehub/tests/test_mwp2_walk_fallback.py` (test IDs `MWP2_01`–`MWP2_13`)