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:

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:

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

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)