gabriel / musehub public
test_mwp2_walk_fallback.py python
964 lines 36.9 KB Cold
Raw
sha256:383b9b15b1a7c18348bf797dbec252b8842199567b4b04371578fedd5f7891d4 merge: integrate push-ingest commit verification into dev Opus 5.5 minor ⚠ breaking 11 days ago
1 """MWP-2 Phase 0 (RED) — _walk_commit_delta correctness fallback.
2
3 Sub-ticket: musehub#107 — https://staging.musehub.ai/gabriel/musehub/issues/107
4 Master: muse#58 — https://staging.musehub.ai/gabriel/muse/issues/58
5 Predecessor: musehub#106 (MWP-1, generation authority) — closed.
6
7 Root cause (RC-2): ``_walk_commit_delta`` (musehub_wire_fetch.py:49) pins
8 ``if True:`` at line 66, making the authoritative MusehubCommit DAG walk (lines
9 159–184) dead code. The live path is a generation-bounded range scan:
10
11 generation > min_have_gen AND generation <= max_want_gen
12
13 This is correct only when every generation in ``musehub_commit_graph`` is
14 correct. When a generation is wrong or a graph row is missing, the range scan
15 either excludes real ancestors (corrupt low generation causes max_want_gen to
16 understate the range) or the BFS dead-ends (missing graph row yields empty
17 parents from ``graph_map.get(cid, ([], None, 0))``). Either way
18 ``_walk_commit_delta`` silently returns a truncated commit set, the assembled
19 mpack is missing commits and blobs, and clone exits 0 with a stale working tree.
20
21 MWP-1 (musehub#106) fixed the write side: no new commit is ever written with a
22 wrong generation, and ``repair_corrupt_commit_generations`` heals pre-existing
23 artefacts. MWP-2 fixes the read side: ``_walk_commit_delta`` must detect that
24 its BFS is incomplete and fall back to the authoritative parent-pointer walk,
25 so the *current* response is always complete regardless of graph state.
26
27 Expected Phase 0 status:
28 - MWP2_01 RED — corrupt generation excludes ancestors; truncated result
29 - MWP2_02 RED — missing graph row dead-ends BFS; missing commits in result
30 - MWP2_03 GREEN — fully consistent graph uses fast path; no fallback triggered
31
32 The fix (Phases 1–2) adds a ``graph_incomplete`` flag to the BFS and calls a
33 promoted ``_walk_commit_delta_dag`` helper when the flag is set.
34 """
35 from __future__ import annotations
36
37 import datetime
38 import logging
39 from unittest.mock import AsyncMock, MagicMock, patch
40
41 import pytest
42 from sqlalchemy import delete as _sa_delete, insert as _sa_insert, select
43 from sqlalchemy.ext.asyncio import AsyncSession
44
45 from muse.core.ids import hash_commit, hash_snapshot
46 from muse.core.mpack import build_wire_mpack, parse_wire_mpack
47 from muse.core.types import blob_id
48 from musehub.core.genesis import compute_identity_id
49 from musehub.db.musehub_repo_models import (
50 MusehubCommit,
51 MusehubCommitGraph,
52 )
53 from musehub.services.musehub_repository import create_repo
54 from musehub.services.musehub_wire_fetch import (
55 _walk_commit_delta,
56 _walk_commit_delta_dag,
57 wire_fetch_mpack,
58 )
59 from musehub.services.musehub_wire_push import wire_push_unpack_mpack
60
61 _OWNER = "gabriel"
62 _IDENTITY_ID = compute_identity_id(b"gabriel")
63
64
65 # ---------------------------------------------------------------------------
66 # Helpers — mirrors test_mwp1_generation_authority.py conventions
67 # ---------------------------------------------------------------------------
68
69
70 def _cid(seed: str) -> str:
71 """Deterministic sha256: commit id from a seed string, for rows seeded directly."""
72 return blob_id(f"mwp2-commit-{seed}".encode())
73
74
75 _SEEDS: dict[str, str] = {}
76
77
78 def _pushed_cid(seed: str, parent: str | None, snap_id: str) -> str:
79 """The id of the commit _raw_commit builds for *seed*; push ingest verifies it."""
80 cid = hash_commit(parent_ids=[parent] if parent else [], snapshot_id=snap_id, message=f"commit {seed}",
81 committed_at_iso=_now().isoformat(), author=_OWNER, signer_public_key="")
82 _SEEDS[cid] = seed
83 return cid
84
85
86 def _sid(seed: str) -> str:
87 """Deterministic snapshot id."""
88 return hash_snapshot({f"{seed}.txt": blob_id(seed.encode())})
89
90
91 def _now() -> datetime.datetime:
92 return datetime.datetime(2026, 1, 1, tzinfo=datetime.timezone.utc)
93
94
95 async def _seed_commit(
96 session: AsyncSession,
97 cid: str,
98 parent_ids: list[str],
99 snap_id: str,
100 ) -> None:
101 """Insert a musehub_commits row (authoritative DAG) with no graph row."""
102 session.add(MusehubCommit(
103 commit_id=cid,
104 branch="main",
105 message=f"commit {cid[:12]}",
106 author=_OWNER,
107 timestamp=_now(),
108 parent_ids=parent_ids,
109 snapshot_id=snap_id,
110 ))
111 await session.flush()
112
113
114 async def _seed_graph(
115 session: AsyncSession,
116 cid: str,
117 parent_ids: list[str],
118 generation: int,
119 snap_id: str,
120 ) -> None:
121 """Insert a musehub_commit_graph row with an explicit (possibly corrupt) generation."""
122 session.add(MusehubCommitGraph(
123 commit_id=cid,
124 parent_ids=parent_ids,
125 generation=generation,
126 snapshot_id=snap_id,
127 created_at=_now(),
128 ))
129 await session.flush()
130
131
132 class _InMemBackend:
133 """In-memory storage backend for E2E push→fetch tests.
134
135 Pre-seed push mpacks in ``backend._mpacks[mpack_key] = mpack_bytes``
136 BEFORE calling ``wire_push_unpack_mpack``. The fetch path assembles and
137 stores its mpack via ``put_mpack``; the test reads it back directly.
138 """
139
140 def __init__(self) -> None:
141 self._mpacks: dict[str, bytes] = {}
142
143 async def put_mpack(self, mpack_id: str, data: bytes) -> None:
144 self._mpacks[mpack_id] = data
145
146 async def get_mpack(self, mpack_id: str) -> bytes | None:
147 return self._mpacks.get(mpack_id)
148
149 async def presign_mpack_get(self, mpack_id: str, ttl: int = 3600) -> str:
150 return f"inmem://{mpack_id}"
151
152 async def put(self, oid: str, data: bytes) -> str:
153 return oid
154
155 async def get(self, oid: str) -> bytes | None:
156 return None
157
158 async def presign_get(self, oid: str, ttl: int = 3600) -> str:
159 return f"inmem://{oid}"
160
161 async def quarantine_mpack(self, *args: object, **kwargs: object) -> None:
162 pass
163
164
165 def _raw_commit(
166 cid: str,
167 parent: str | None,
168 snap_id: str,
169 *,
170 branch: str = "main",
171 ) -> dict:
172 """Raw commit wire dict in the shape wire_push_unpack_mpack consumes."""
173 return {
174 "commit_id": cid,
175 "branch": branch,
176 "message": f"commit {_SEEDS.get(cid, cid[:12])}",
177 "author": _OWNER,
178 "committed_at": _now().isoformat(),
179 "parent_commit_id": parent,
180 "parent2_commit_id": None,
181 "snapshot_id": snap_id,
182 "agent_id": "",
183 "model_id": "",
184 "toolchain_id": "",
185 "sem_ver_bump": "none",
186 "breaking_changes": [],
187 "signature": "",
188 "signer_key_id": "",
189 "signer_public_key": "",
190 "prompt_hash": "",
191 }
192
193
194 # ---------------------------------------------------------------------------
195 # MWP2_01 — corrupt generation excludes ancestors from range scan (RED)
196 # ---------------------------------------------------------------------------
197
198
199 @pytest.mark.asyncio
200 async def test_mwp2_01_corrupt_generation_truncates_walk(
201 db_session: AsyncSession,
202 ) -> None:
203 """RED: a missing interior graph row dead-ends the BFS, dropping ancestors.
204
205 Chain: C1 <- C2 <- C3 <- C4 (all in musehub_commits, authoritative).
206 Graph: C1(gen=0), C2(gen=1), C4(gen=3) — C3 has NO graph row.
207 want=[C4], have=[].
208
209 BFS: C4 is in graph_map (gen=3, parents=[C3]). C3 → graph_map.get(C3)
210 returns default ([], None, 0) → BFS treats C3 as a leaf and stops.
211 C2 and C1 are never added to the reachable set.
212
213 Result without fix: {C4, C3} — C2 and C1 missing.
214 Result with fix: {C4, C3, C2, C1}.
215
216 This is the canonical post-MWP-1 RC-2 scenario: the tip has a correct high
217 generation, but an interior ancestor's graph row was never written (a push
218 that wrote musehub_commits but not the graph row, or a pre-backfill gap).
219 MWP2_02 covers the case where the *start tip itself* is absent from the graph.
220 """
221 c1 = _cid("01-c1")
222 c2 = _cid("01-c2")
223 c3 = _cid("01-c3")
224 c4 = _cid("01-c4")
225 s1, s2, s3, s4 = _sid("01-s1"), _sid("01-s2"), _sid("01-s3"), _sid("01-s4")
226
227 # Authoritative DAG — all four commits exist in musehub_commits.
228 await _seed_commit(db_session, c1, [], s1)
229 await _seed_commit(db_session, c2, [c1], s2)
230 await _seed_commit(db_session, c3, [c2], s3)
231 await _seed_commit(db_session, c4, [c3], s4)
232
233 # Graph: C1, C2 present with correct generations; C3 absent (the backfill
234 # gap that produces the BFS dead-end); C4 present with correct generation
235 # relative to the true chain (gen=3).
236 await _seed_graph(db_session, c1, [], 0, s1)
237 await _seed_graph(db_session, c2, [c1], 1, s2)
238 # C3 deliberately NOT seeded in graph.
239 await _seed_graph(db_session, c4, [c3], 3, s4)
240 await db_session.commit()
241
242 result = await _walk_commit_delta(db_session, want=[c4], have=[])
243
244 assert c4 in result, "C4 (want tip) must always be in result"
245 assert c3 in result, (
246 f"C3 must be in result — it is a direct parent of C4. "
247 f"It is missing because graph_map.get(C3) returned empty parents "
248 f"(C3 has no graph row), so the BFS dead-ended at C3. "
249 f"Got result keys: {sorted(result.keys())}"
250 )
251 assert c2 in result, (
252 f"C2 must be in result — ancestor of C4 reachable via C3. "
253 f"Got result keys: {sorted(result.keys())}"
254 )
255 assert c1 in result, (
256 f"C1 must be in result — root ancestor of C4. "
257 f"Got result keys: {sorted(result.keys())}"
258 )
259
260
261 # ---------------------------------------------------------------------------
262 # MWP2_02 — missing graph row for the start tip dead-ends BFS (RED)
263 # ---------------------------------------------------------------------------
264
265
266 @pytest.mark.asyncio
267 async def test_mwp2_02_missing_start_tip_graph_row(
268 db_session: AsyncSession,
269 ) -> None:
270 """RED: when the start tip (a want commit) has no graph row at all, the
271 BFS dead-ends immediately and returns an empty or incomplete set.
272
273 Setup:
274 musehub_commits: C1(root) <- C2 <- C3
275 musehub_commit_graph: C1(gen=0), C2(gen=1) — C3 has NO graph row.
276 want=[C3], have=[].
277
278 max_want_gen: C3 not in graph → query returns None → max_want_gen = 0.
279 Range scan: gen > -1 AND gen <= 0 → only C1 (gen=0) returned in graph_map.
280 BFS: starts from C3; C3 not in graph_map → treated as having empty parents;
281 BFS adds C3 to reachable but never follows its parents (C2, C1).
282 Result without fix: {C3} only. Missing: C2, C1.
283 Result with fix: {C3, C2, C1}.
284 """
285 c1 = _cid("02-c1")
286 c2 = _cid("02-c2")
287 c3 = _cid("02-c3")
288 s1, s2, s3 = _sid("02-s1"), _sid("02-s2"), _sid("02-s3")
289
290 # Authoritative DAG.
291 await _seed_commit(db_session, c1, [], s1)
292 await _seed_commit(db_session, c2, [c1], s2)
293 await _seed_commit(db_session, c3, [c2], s3)
294
295 # Graph: C1 and C2 present; C3 (the want tip) absent.
296 await _seed_graph(db_session, c1, [], 0, s1)
297 await _seed_graph(db_session, c2, [c1], 1, s2)
298 await db_session.commit()
299
300 result = await _walk_commit_delta(db_session, want=[c3], have=[])
301
302 assert c3 in result, "C3 (want tip) must be in result"
303 assert c2 in result, (
304 f"C2 must be in result — parent of C3 (the want tip). "
305 f"C3 had no graph row, so max_want_gen=0 and the range scan only "
306 f"returned C1. BFS from C3 found no parents in graph_map. "
307 f"Got result keys: {sorted(result.keys())}"
308 )
309 assert c1 in result, (
310 f"C1 must be in result — root ancestor reachable from C3. "
311 f"Got result keys: {sorted(result.keys())}"
312 )
313
314
315 # ---------------------------------------------------------------------------
316 # MWP2_03 — consistent graph uses fast path, no fallback invoked (GREEN)
317 # ---------------------------------------------------------------------------
318
319
320 @pytest.mark.asyncio
321 async def test_mwp2_03_consistent_graph_uses_fast_path(
322 db_session: AsyncSession,
323 ) -> None:
324 """GREEN guard: a fully consistent graph must return the complete ancestor
325 closure via the fast path, and ``_walk_commit_delta_dag`` must NOT be called.
326
327 This test pins the happy-path contract so later phases cannot accidentally
328 make the fast path degrade into always calling the fallback (which would be
329 correct but slow).
330
331 After Phase 2 the ``_walk_commit_delta_dag`` helper will exist; this test
332 patches it to detect if it is invoked. Before Phase 1 it doesn't exist, so
333 we patch ``musehub.graph.walk.walk_dag_async`` (the underlying function the
334 legacy walk calls) as a proxy — if the fast path is truly live and exclusive,
335 walk_dag_async should never be called during _walk_commit_delta.
336
337 Note: after Phase 1 promotes _walk_commit_delta_dag to a real named function,
338 this test should be updated to patch that directly. For Phase 0 we patch
339 walk_dag_async as the canary.
340
341 Setup:
342 musehub_commits: C1(root) <- C2 <- C3
343 musehub_commit_graph: C1(gen=0), C2(gen=1), C3(gen=2) — fully consistent.
344 want=[C3], have=[].
345
346 Expected: result contains C1, C2, C3 and walk_dag_async is not called.
347 """
348 c1 = _cid("03-c1")
349 c2 = _cid("03-c2")
350 c3 = _cid("03-c3")
351 s1, s2, s3 = _sid("03-s1"), _sid("03-s2"), _sid("03-s3")
352
353 await _seed_commit(db_session, c1, [], s1)
354 await _seed_commit(db_session, c2, [c1], s2)
355 await _seed_commit(db_session, c3, [c2], s3)
356
357 await _seed_graph(db_session, c1, [], 0, s1)
358 await _seed_graph(db_session, c2, [c1], 1, s2)
359 await _seed_graph(db_session, c3, [c2], 2, s3)
360 await db_session.commit()
361
362 with patch(
363 "musehub.services.musehub_wire_fetch._walk_commit_delta_dag",
364 new_callable=AsyncMock,
365 ) as mock_dag:
366 mock_dag.side_effect = AssertionError(
367 "_walk_commit_delta invoked the DAG fallback (_walk_commit_delta_dag) "
368 "on a fully consistent graph — the fast path must be used exclusively."
369 )
370
371 result = await _walk_commit_delta(db_session, want=[c3], have=[])
372
373 assert c3 in result, f"C3 must be in result; got {sorted(result.keys())}"
374 assert c2 in result, f"C2 must be in result; got {sorted(result.keys())}"
375 assert c1 in result, f"C1 must be in result; got {sorted(result.keys())}"
376
377
378 # ---------------------------------------------------------------------------
379 # MWP2_05 — _walk_commit_delta_dag returns full closure with populated fields
380 # ---------------------------------------------------------------------------
381
382
383 @pytest.mark.asyncio
384 async def test_mwp2_05_dag_helper_returns_full_closure(
385 db_session: AsyncSession,
386 ) -> None:
387 """GREEN: _walk_commit_delta_dag over a musehub_commits chain returns the
388 complete ancestor closure of want minus have, with snapshot_id and
389 parent_ids populated on every returned row.
390
391 No graph rows are seeded — the helper walks musehub_commits.parent_ids
392 directly (the authoritative DAG), so a missing/corrupt graph is irrelevant.
393
394 Chain: C1(root) <- C2 <- C3
395 Call: _walk_commit_delta_dag(session, starts=[C3], have_set=frozenset())
396 Expect: {C3, C2, C1}, each with correct snapshot_id and parent_ids.
397 """
398 c1 = _cid("05-c1")
399 c2 = _cid("05-c2")
400 c3 = _cid("05-c3")
401 s1, s2, s3 = _sid("05-s1"), _sid("05-s2"), _sid("05-s3")
402
403 await _seed_commit(db_session, c1, [], s1)
404 await _seed_commit(db_session, c2, [c1], s2)
405 await _seed_commit(db_session, c3, [c2], s3)
406 await db_session.commit()
407
408 result = await _walk_commit_delta_dag(db_session, starts=[c3], have_set=frozenset())
409
410 assert set(result.keys()) == {c1, c2, c3}, (
411 f"Must return all three commits; got {sorted(result.keys())}"
412 )
413
414 # Every row must have snapshot_id and parent_ids populated.
415 r1, r2, r3 = result[c1], result[c2], result[c3]
416
417 assert r1.snapshot_id == s1, f"C1 snapshot_id wrong: {r1.snapshot_id}"
418 assert r2.snapshot_id == s2, f"C2 snapshot_id wrong: {r2.snapshot_id}"
419 assert r3.snapshot_id == s3, f"C3 snapshot_id wrong: {r3.snapshot_id}"
420
421 assert r1.parent_ids == [], f"C1 parent_ids wrong: {r1.parent_ids}"
422 assert r2.parent_ids == [c1], f"C2 parent_ids wrong: {r2.parent_ids}"
423 assert r3.parent_ids == [c2], f"C3 parent_ids wrong: {r3.parent_ids}"
424
425
426 # ---------------------------------------------------------------------------
427 # MWP2_06 — _walk_commit_delta_dag returns commits in parents-first topo order
428 # ---------------------------------------------------------------------------
429
430
431 @pytest.mark.asyncio
432 async def test_mwp2_06_dag_helper_parents_first_order(
433 db_session: AsyncSession,
434 ) -> None:
435 """GREEN: the dict returned by _walk_commit_delta_dag is in parents-first
436 topological order — every commit appears after all of its in-set parents.
437
438 walk_dag_async BFS order is children-before-parents (C3, C2, C1 for a
439 linear chain starting at C3). After Kahn's topo-sort the result must be
440 C1, C2, C3 — each parent strictly before its child.
441
442 Chain: C1(root) <- C2 <- C3
443 Expected key order: [C1, C2, C3]
444 """
445 c1 = _cid("06-c1")
446 c2 = _cid("06-c2")
447 c3 = _cid("06-c3")
448 s1, s2, s3 = _sid("06-s1"), _sid("06-s2"), _sid("06-s3")
449
450 await _seed_commit(db_session, c1, [], s1)
451 await _seed_commit(db_session, c2, [c1], s2)
452 await _seed_commit(db_session, c3, [c2], s3)
453 await db_session.commit()
454
455 result = await _walk_commit_delta_dag(db_session, starts=[c3], have_set=frozenset())
456
457 keys = list(result.keys())
458 assert len(keys) == 3, f"Expected 3 commits, got {len(keys)}: {keys}"
459
460 idx = {cid: i for i, cid in enumerate(keys)}
461 assert idx[c1] < idx[c2], (
462 f"C1 (root) must appear before C2 in the result. "
463 f"Got order: C1={idx[c1]}, C2={idx[c2]}, C3={idx[c3]}"
464 )
465 assert idx[c2] < idx[c3], (
466 f"C2 must appear before C3 in the result. "
467 f"Got order: C1={idx[c1]}, C2={idx[c2]}, C3={idx[c3]}"
468 )
469
470
471 # ---------------------------------------------------------------------------
472 # MWP2_09 — have boundary is honored under the DAG fallback (GREEN)
473 # ---------------------------------------------------------------------------
474
475
476 @pytest.mark.asyncio
477 async def test_mwp2_09_have_boundary_honored_under_fallback(
478 db_session: AsyncSession,
479 ) -> None:
480 """GREEN: when the fallback fires, the have set is respected — commits in
481 have and their ancestors are excluded from the result, same as the fast path.
482
483 Chain: C1(root) <- C2 <- C3 <- C4
484 Graph: C1(gen=0), C2(gen=1), C4(gen=3) — C3 absent (triggers fallback).
485 want=[C4], have=[C2].
486
487 Fast-path sequence (pre-fallback):
488 max_want_gen=3, min_have_gen=1 (gen of C2).
489 Range scan gen=(1,3] → only C4(gen=3). C3 absent → graph_incomplete=True.
490 Dispatches to _walk_commit_delta_dag(session, starts=[C4], have_set={C2}).
491
492 DAG walk: BFS from C4 with exclude={C2}.
493 C4 visited → adj=[C3] → C3 visited → adj=[C2] (excluded, already in seen).
494 C2 never yielded. C1 never queued.
495 Kahn's sort: {C3, C4} in parents-first order.
496
497 Assert: {C3, C4} in result; C1 and C2 absent.
498 """
499 c1 = _cid("09-c1")
500 c2 = _cid("09-c2")
501 c3 = _cid("09-c3")
502 c4 = _cid("09-c4")
503 s1, s2, s3, s4 = _sid("09-s1"), _sid("09-s2"), _sid("09-s3"), _sid("09-s4")
504
505 # Authoritative DAG — all four commits.
506 await _seed_commit(db_session, c1, [], s1)
507 await _seed_commit(db_session, c2, [c1], s2)
508 await _seed_commit(db_session, c3, [c2], s3)
509 await _seed_commit(db_session, c4, [c3], s4)
510
511 # Graph: C1, C2, C4 present; C3 absent → triggers fallback.
512 await _seed_graph(db_session, c1, [], 0, s1)
513 await _seed_graph(db_session, c2, [c1], 1, s2)
514 await _seed_graph(db_session, c4, [c3], 3, s4)
515 await db_session.commit()
516
517 result = await _walk_commit_delta(db_session, want=[c4], have=[c2])
518
519 assert c4 in result, f"C4 (want tip) must be in result; got {sorted(result.keys())}"
520 assert c3 in result, f"C3 must be in result (it is between the tip and the have boundary)"
521 assert c2 not in result, (
522 f"C2 is in have — it must be excluded from the result; "
523 f"got {sorted(result.keys())}"
524 )
525 assert c1 not in result, (
526 f"C1 is an ancestor of have — it must be excluded from the result; "
527 f"got {sorted(result.keys())}"
528 )
529
530
531 # ---------------------------------------------------------------------------
532 # MWP2_10 — max_nodes bound is wired into walk_dag_async + warning fires (GREEN)
533 # ---------------------------------------------------------------------------
534
535
536 @pytest.mark.asyncio
537 async def test_mwp2_10_max_nodes_bound_is_wired(
538 db_session: AsyncSession,
539 caplog: pytest.LogCaptureFixture,
540 ) -> None:
541 """GREEN (Phase 3): two assertions about the max_nodes cap in _walk_commit_delta_dag.
542
543 Part A — kwarg wired: walk_dag_async is called with max_nodes=100_000.
544 Setup: a 2-commit chain with no graph rows → triggers _walk_commit_delta_dag.
545 A wrapper around walk_dag_async captures the kwargs.
546
547 Part B — warning fires: when walk_dag_async yields exactly 100_000 commits,
548 the `[MWP2] ... max_nodes cap hit` warning is emitted.
549 A mock replaces walk_dag_async to yield 100_000 fake cid strings (not in DB).
550 Kahn's sort runs over them (all in_degree=0, empty result dict).
551 The deque-based Kahn's queue keeps this O(n), not O(n²).
552 """
553 import logging as _logging
554 from unittest.mock import patch as _patch
555
556 # ---- Part A: max_nodes=100_000 kwarg reaches walk_dag_async ----
557 c1 = _cid("10a-c1")
558 c2 = _cid("10a-c2")
559 s1, s2 = _sid("10a-s1"), _sid("10a-s2")
560
561 await _seed_commit(db_session, c1, [], s1)
562 await _seed_commit(db_session, c2, [c1], s2)
563 # No graph rows — forces _walk_commit_delta_dag.
564
565 received: dict[str, object] = {}
566
567 from musehub.graph import walk as _walk_mod
568
569 _original_walk = _walk_mod.walk_dag_async
570
571 async def _capturing_walk(starts, adj_fn, *, exclude=None, max_nodes=None):
572 received["max_nodes"] = max_nodes
573 async for item in _original_walk(starts, adj_fn, exclude=exclude, max_nodes=max_nodes):
574 yield item
575
576 with _patch.object(_walk_mod, "walk_dag_async", new=_capturing_walk):
577 result_a = await _walk_commit_delta(db_session, want=[c2], have=[])
578
579 assert received.get("max_nodes") == 100_000, (
580 f"_walk_commit_delta_dag must pass max_nodes=100_000 to walk_dag_async; "
581 f"got max_nodes={received.get('max_nodes')!r}"
582 )
583 assert c1 in result_a and c2 in result_a, (
584 f"Full result still expected even with wrapping; got {sorted(result_a.keys())}"
585 )
586
587 # ---- Part B: WARNING fires when reachable count hits the cap ----
588 # Mock walk_dag_async to yield exactly 100_000 fake cids (not in DB).
589 # Kahn's sort sees all in_degree=0 (no _row_cache entries → no parent edges).
590 # With deque.popleft() this is O(n); with list.pop(0) it would be O(n²).
591 async def _capped_walk(starts, adj_fn, *, exclude=None, max_nodes=None):
592 for i in range(100_000):
593 yield f"sha256:{'a' * 60}{i:04d}"
594
595 with _patch.object(_walk_mod, "walk_dag_async", new=_capped_walk):
596 with caplog.at_level(_logging.WARNING, logger="musehub.services.musehub_wire_fetch"):
597 await _walk_commit_delta_dag(
598 db_session,
599 starts=[c2],
600 have_set=frozenset(),
601 )
602
603 assert any("max_nodes cap hit" in r.message for r in caplog.records), (
604 "WARNING must be logged when reachable count reaches max_nodes=100_000. "
605 f"Log records captured: {[r.message for r in caplog.records]}"
606 )
607
608
609 # ---------------------------------------------------------------------------
610 # MWP2_11 — 5,000-commit stress: full fallback, correct topo order, O(n) (GREEN)
611 # ---------------------------------------------------------------------------
612
613
614 @pytest.mark.asyncio
615 async def test_mwp2_11_stress_5000_commit_linear_chain(
616 db_session: AsyncSession,
617 ) -> None:
618 """GREEN (Phase 3): a 5,000-commit linear chain with no graph rows triggers
619 the DAG fallback and returns all 5,000 commits in parents-first topo order.
620
621 No graph rows are seeded → fast-path BFS detects graph_incomplete=True at
622 the very first start (want tip absent from graph_map → max_want_gen=0).
623 Fallback walks musehub_commits.parent_ids over the entire chain.
624
625 Performance note: commits are seeded with a single flush (no commit), so
626 SQLAlchemy's identity map stays warm — session.get() hits the map for each
627 adjacency call (O(1) per call) rather than issuing 5,000 DB round trips.
628 Kahn's topo-sort uses collections.deque to guarantee O(n), not O(n²).
629
630 Assertions:
631 - result contains exactly 5,000 commits
632 - every parent appears before its child in dict iteration order
633 - result is bounded well below max_nodes=100_000
634 """
635 N = 5_000
636
637 # Build linear chain C0 ← C1 ← ... ← C4999.
638 chain_cids = [_cid(f"11-c{i:04d}") for i in range(N)]
639 chain_sids = [_sid(f"11-s{i:04d}") for i in range(N)]
640
641 for i in range(N):
642 parent_ids = [] if i == 0 else [chain_cids[i - 1]]
643 db_session.add(MusehubCommit(
644 commit_id=chain_cids[i],
645 branch="main",
646 message=f"commit {chain_cids[i][:12]}",
647 author=_OWNER,
648 timestamp=_now(),
649 parent_ids=parent_ids,
650 snapshot_id=chain_sids[i],
651 ))
652 # Single flush — keeps identity map warm so session.get() is O(1) per call.
653 # No graph rows seeded → forces full DAG fallback.
654 await db_session.flush()
655
656 tip = chain_cids[-1]
657 result = await _walk_commit_delta(db_session, want=[tip], have=[])
658
659 assert len(result) == N, (
660 f"Fallback must return all {N} commits; got {len(result)}"
661 )
662
663 # Verify parents-first topological order: every parent in the result set must
664 # appear strictly before its child in dict iteration order.
665 keys = list(result.keys())
666 idx = {cid: pos for pos, cid in enumerate(keys)}
667 violations = []
668 for cid in keys:
669 row = result[cid]
670 for pid in (row.parent_ids or []):
671 if pid in idx and idx[pid] >= idx[cid]:
672 violations.append((pid[:12], cid[:12]))
673 assert not violations, (
674 f"Topo-order violation: parent appears after child in {len(violations)} "
675 f"case(s); first few: {violations[:5]}"
676 )
677
678
679 # ---------------------------------------------------------------------------
680 # Shared E2E helpers (MWP2_12 / MWP2_13)
681 # ---------------------------------------------------------------------------
682
683
684 def _e2e_backend_patch(backend: _InMemBackend) -> tuple:
685 """Return the three backend patches needed for push + fetch E2E tests."""
686 return (
687 patch("musehub.services.musehub_wire.get_backend", return_value=backend),
688 patch("musehub.services.musehub_wire_push.get_backend", return_value=backend),
689 patch("musehub.services.musehub_wire_fetch.get_backend", return_value=backend),
690 patch("musehub.storage.backends.get_backend", return_value=backend),
691 )
692
693
694 async def _e2e_push(
695 session: AsyncSession,
696 repo_id: str,
697 backend: _InMemBackend,
698 cid: str,
699 parent: str | None,
700 snap_id: str,
701 fpath: str,
702 oid: str,
703 data: bytes,
704 ) -> None:
705 """Build a single-commit mpack, store in backend, and push via wire_push_unpack_mpack."""
706 mpack_bytes = build_wire_mpack({
707 "commits": [_raw_commit(cid, parent, snap_id)],
708 "snapshots": [{
709 "snapshot_id": snap_id,
710 "parent_snapshot_id": None,
711 "delta_upsert": {fpath: oid},
712 "delta_remove": [],
713 "directories": [],
714 }],
715 "blobs": [{"object_id": oid, "content": data}],
716 "tags": [],
717 })
718 mpack_key = blob_id(mpack_bytes)
719 backend._mpacks[mpack_key] = mpack_bytes
720
721 push_patches = _e2e_backend_patch(backend)
722 with push_patches[0], push_patches[1], push_patches[2], push_patches[3]:
723 await wire_push_unpack_mpack(
724 session,
725 repo_id,
726 mpack_key,
727 pusher_id=_OWNER,
728 branch="main",
729 head_commit_id=cid,
730 commits_count=1,
731 blobs_count=1,
732 force=True,
733 )
734 await session.flush()
735
736
737 # ---------------------------------------------------------------------------
738 # MWP2_12 — E2E acceptance gate: fallback alone ships a complete clone (GREEN)
739 # ---------------------------------------------------------------------------
740
741
742 @pytest.mark.asyncio
743 async def test_mwp2_12_e2e_fallback_alone_ships_complete_clone(
744 db_session: AsyncSession,
745 ) -> None:
746 """GREEN (Phase 4 — acceptance gate): MWP-2 fallback alone delivers a
747 complete clone even when the commit graph has a missing interior row.
748
749 Setup:
750 1. Create a repo and push C1 → C2 → C3 individually.
751 CommitGraph after pushes: C1(gen=0), C2(gen=1), C3(gen=2).
752 2. Delete C2's CommitGraph row — interior node missing.
753 3. Patch out repair_corrupt_commit_generations (MWP-1 cannot self-heal).
754 4. Clone via wire_fetch_mpack(want=[C3], have=[], force_build=True).
755
756 Without MWP-2 (the bug):
757 max_want_gen = 2 (C3 in graph). Range scan: gen=(−1,2] → C1(0), C3(2).
758 BFS: C3 → C2 (C2 not in graph_map, parents=[]) → BFS dead-end.
759 Reachable = {C3, C2}. C1 ABSENT from assembled mpack.
760
761 With MWP-2 (the fix):
762 BFS detects C2 absent from graph_map → graph_incomplete=True → fallback.
763 _walk_commit_delta_dag returns {C1, C2, C3}. All three commits in mpack.
764
765 Note: MWP-1's guard does NOT fire here because C3's graph snapshot still
766 matches C3's commit snapshot — the corruption is only a missing graph row,
767 not a wrong generation. repair_corrupt_commit_generations is patched as a
768 safety rail to prove MWP-2 is self-sufficient.
769 """
770 repo = await create_repo(
771 db_session,
772 name="mwp2-12",
773 owner=_OWNER,
774 owner_user_id=_IDENTITY_ID,
775 visibility="public",
776 initialize=False,
777 )
778 await db_session.commit()
779
780 c1, c2, c3 = _cid("12-c1"), _cid("12-c2"), _cid("12-c3")
781 oid1 = blob_id(b"12-c1-blob")
782 oid2 = blob_id(b"12-c2-blob")
783 oid3 = blob_id(b"12-c3-blob")
784 s1 = hash_snapshot({"f1.txt": oid1})
785 s2 = hash_snapshot({"f2.txt": oid2})
786 s3 = hash_snapshot({"f3.txt": oid3})
787 c1 = _pushed_cid("12-c1", None, s1)
788 c2 = _pushed_cid("12-c2", c1, s2)
789 c3 = _pushed_cid("12-c3", c2, s3)
790
791 backend = _InMemBackend()
792
793 # Push C1, C2, C3 — each push writes correct CommitGraph generations.
794 await _e2e_push(db_session, repo.repo_id, backend, c1, None, s1, "f1.txt", oid1, b"12-c1-blob")
795 await _e2e_push(db_session, repo.repo_id, backend, c2, c1, s2, "f2.txt", oid2, b"12-c2-blob")
796 await _e2e_push(db_session, repo.repo_id, backend, c3, c2, s3, "f3.txt", oid3, b"12-c3-blob")
797
798 # Corrupt: delete C2's CommitGraph row (missing interior node).
799 await db_session.execute(
800 _sa_delete(MusehubCommitGraph).where(MusehubCommitGraph.commit_id == c2)
801 )
802 await db_session.flush()
803
804 # Patch out MWP-1's repair guard to prove MWP-2 handles this alone.
805 fetch_patches = _e2e_backend_patch(backend)
806 with patch(
807 "musehub.services.musehub_wire_fetch.repair_corrupt_commit_generations",
808 new_callable=AsyncMock,
809 ) as mock_repair, \
810 fetch_patches[0], fetch_patches[2], fetch_patches[3]:
811
812 mock_repair.return_value = {"total_corrupt": 0, "repaired": 0}
813
814 fetch_result = await wire_fetch_mpack(
815 db_session,
816 repo.repo_id,
817 want=[c3],
818 have=[],
819 force_build=True,
820 )
821
822 # MWP-1 guard should NOT fire: C3's graph snapshot still matches its commit
823 # snapshot — only the missing C2 row caused truncation (RC-2, not RC-1).
824 mock_repair.assert_not_called()
825
826 assert fetch_result["mpack_id"] is not None, "wire_fetch_mpack must return a mpack_id"
827 assembled_bytes = backend._mpacks[fetch_result["mpack_id"]]
828 parsed = parse_wire_mpack(assembled_bytes)
829
830 commit_ids = {c["commit_id"] for c in parsed.get("commits", [])}
831 blob_oids = {b["object_id"] for b in parsed.get("blobs", [])}
832
833 assert c1 in commit_ids, (
834 f"C1 must be in assembled mpack — WITHOUT MWP-2 the BFS dead-ends at C2 "
835 f"(C2 absent from graph_map → parents=[]) and C1 is never reachable. "
836 f"commits present: {[cid[:16] for cid in commit_ids]}"
837 )
838 assert c2 in commit_ids, (
839 f"C2 must be in assembled mpack; got {[cid[:16] for cid in commit_ids]}"
840 )
841 assert c3 in commit_ids, (
842 f"C3 (want tip) must be in assembled mpack; got {[cid[:16] for cid in commit_ids]}"
843 )
844 assert oid3 in blob_oids, (
845 f"C3's blob (oid3) must be in assembled mpack; got {[o[:16] for o in blob_oids]}"
846 )
847
848
849 # ---------------------------------------------------------------------------
850 # MWP2_13 — E2E: fallback + graph healing → fast path on second call (GREEN)
851 # ---------------------------------------------------------------------------
852
853
854 @pytest.mark.asyncio
855 async def test_mwp2_13_e2e_fast_path_after_graph_healed(
856 db_session: AsyncSession,
857 ) -> None:
858 """GREEN (Phase 4): MWP-2 handles the corrupt state; once the graph is healed
859 by any mechanism, a follow-up _walk_commit_delta uses the fast path.
860
861 Proves MWP-1 + MWP-2 compose: the fallback is the safety net for the
862 *current* response; the fast path is restored once the graph is intact.
863
864 Setup (same as MWP2_12):
865 Push C1 → C2 → C3. Delete C2's CommitGraph row. repair NOT patched.
866
867 First clone: MWP-2 fallback fires. Result: {C1, C2, C3} — complete.
868 MWP-1 guard does NOT fire (no snapshot mismatch for this corruption type).
869
870 Graph heal: INSERT C2's CommitGraph row back (gen=1) — simulating what a
871 subsequent push or an explicit repair would do once the graph gap is noticed.
872
873 Second call (_walk_commit_delta, not full wire_fetch_mpack):
874 _walk_commit_delta_dag is patched to raise AssertionError if called.
875 With the healed graph (C1=0, C2=1, C3=2 all present), the fast-path BFS
876 completes without any missing nodes → graph_incomplete=False → no fallback.
877 The patched dag helper is never invoked — no AssertionError.
878 """
879 repo = await create_repo(
880 db_session,
881 name="mwp2-13",
882 owner=_OWNER,
883 owner_user_id=_IDENTITY_ID,
884 visibility="public",
885 initialize=False,
886 )
887 await db_session.commit()
888
889 c1, c2, c3 = _cid("13-c1"), _cid("13-c2"), _cid("13-c3")
890 oid1 = blob_id(b"13-c1-blob")
891 oid2 = blob_id(b"13-c2-blob")
892 oid3 = blob_id(b"13-c3-blob")
893 s1 = hash_snapshot({"f1.txt": oid1})
894 s2 = hash_snapshot({"f2.txt": oid2})
895 s3 = hash_snapshot({"f3.txt": oid3})
896 c1 = _pushed_cid("13-c1", None, s1)
897 c2 = _pushed_cid("13-c2", c1, s2)
898 c3 = _pushed_cid("13-c3", c2, s3)
899
900 backend = _InMemBackend()
901
902 # Push C1, C2, C3.
903 await _e2e_push(db_session, repo.repo_id, backend, c1, None, s1, "f1.txt", oid1, b"13-c1-blob")
904 await _e2e_push(db_session, repo.repo_id, backend, c2, c1, s2, "f2.txt", oid2, b"13-c2-blob")
905 await _e2e_push(db_session, repo.repo_id, backend, c3, c2, s3, "f3.txt", oid3, b"13-c3-blob")
906
907 # Corrupt: delete C2's CommitGraph row (same as MWP2_12).
908 await db_session.execute(
909 _sa_delete(MusehubCommitGraph).where(MusehubCommitGraph.commit_id == c2)
910 )
911 await db_session.flush()
912
913 # First clone — MWP-2 fallback fires; repair is NOT patched (it won't run
914 # for this corruption type, but we leave it live to prove composition).
915 fetch_patches = _e2e_backend_patch(backend)
916 with fetch_patches[0], fetch_patches[2], fetch_patches[3]:
917 fetch_result = await wire_fetch_mpack(
918 db_session,
919 repo.repo_id,
920 want=[c3],
921 have=[],
922 force_build=True,
923 )
924
925 assert fetch_result["mpack_id"] is not None
926 assembled_bytes = backend._mpacks[fetch_result["mpack_id"]]
927 parsed_first = parse_wire_mpack(assembled_bytes)
928 commit_ids_first = {c["commit_id"] for c in parsed_first.get("commits", [])}
929
930 assert {c1, c2, c3} == commit_ids_first, (
931 f"First clone must contain all 3 commits; got {[cid[:16] for cid in commit_ids_first]}"
932 )
933
934 # Heal the graph: re-insert C2's CommitGraph row with the correct generation.
935 # This simulates what a follow-up push or repair routine would do once it
936 # detects the gap. The INSERT is safe because the DELETE was already flushed.
937 await db_session.execute(
938 _sa_insert(MusehubCommitGraph).values(
939 commit_id=c2,
940 parent_ids=[c1],
941 generation=1,
942 snapshot_id=s2,
943 created_at=_now(),
944 )
945 )
946 await db_session.flush()
947
948 # Second call: _walk_commit_delta must use the fast path now.
949 # Patch _walk_commit_delta_dag to raise if called — any invocation = regression.
950 with patch(
951 "musehub.services.musehub_wire_fetch._walk_commit_delta_dag",
952 new_callable=AsyncMock,
953 ) as mock_dag:
954 mock_dag.side_effect = AssertionError(
955 "MWP2_13: _walk_commit_delta invoked the DAG fallback after the graph "
956 "was healed — the fast path must be used exclusively when graph is intact."
957 )
958 result2 = await _walk_commit_delta(db_session, want=[c3], have=[])
959
960 # Fast path returned — verify completeness (now as SimpleNamespace proxies).
961 assert {c1, c2, c3} == set(result2.keys()), (
962 f"Second _walk_commit_delta must return all 3 commits via fast path; "
963 f"got {[cid[:16] for cid in result2.keys()]}"
964 )
File History 7 commits
sha256:383b9b15b1a7c18348bf797dbec252b8842199567b4b04371578fedd5f7891d4 merge: integrate push-ingest commit verification into dev Opus 5.5 minor ⚠ 11 days ago
sha256:39b90cebf3ab4c72ef67a29fe9d451ba1394084edf4053dff98878651f5d2378 test: build reproducible commit ids in push fixtures Opus 5.5 11 days ago
sha256:d939d288f2939676bf4c4d018c87b6b88322146f0e574e068839868be17e67b9 test(mwp-2): phase 4 E2E acceptance gate (MWP2_12, MWP2_13) Sonnet 4.6 141 days ago
sha256:1280ec7c64fed820c8a862f23e64707df980b19e5a63ca0fee14acf7ee1b86d9 test(mwp-2): phase 3 bounded fallback + 5k stress (MWP2_10,… Sonnet 4.6 patch 141 days ago
sha256:984cdb57998d247e791f54d58a3595951dc990f09cbe6132d7b3675dab07de20 feat(mwp2): Phase 2 — wire graph_incomplete detection + DAG… Sonnet 4.6 141 days ago
sha256:d984bd63c5abb64309fc91547bb884fe8a7e08820bae6f2b13957cee07584221 feat(mwp2): Phase 1 — extract _walk_commit_delta_dag, remov… Sonnet 4.6 141 days ago
sha256:4dd2a937f66f8e36d9aa59bd1bf3cb880ca1d503fef67300a0cba3b482784081 test(mwp2): Phase 0 RED — reproduction tests for _walk_comm… Sonnet 4.6 141 days ago