gabriel / muse public
test_perf_merge_scale.py python
760 lines 32.5 KB
Raw
sha256:51ce277f663e01a43eaffbe77509b1de7ac2d4251b55d23306304bcdeb92c90d feat(pack): delta-encode snapshots in MPackBundle wire format Sonnet 4.6 minor ⚠ breaking 120 days ago
1 """Phase 3.6 — ``muse merge`` at scale.
2
3 Targets
4 -------
5 - ``muse merge --dry-run <branch>`` on two branches each with 5 000 modified
6 files from a 75 000-file base: < 30 s.
7 - ``detect_conflicts`` on 1 000 files modified by both branches: < 5 s
8 (actual measurement: < 1 ms — target is trivially exceeded; the test
9 documents the asymptotic behaviour).
10 - ``find_merge_base`` on 50-commit-deep chains completes correctly;
11 > ``max_ancestors`` cap raises ``MuseCLIError`` cleanly.
12
13 Additional coverage discovered during reconnaissance
14 ----------------------------------------------------
15 - Convergent both-delete: NOT a conflict, absent from merged manifest.
16 - Convergent same-add same-hash: NOT a conflict, present in merged manifest.
17 - Delete-vs-modify: IS a conflict.
18 - Criss-cross DAG: ``find_merge_base`` returns a valid (though non-unique) LCA.
19 - Disjoint histories (no common ancestor): returns ``None``.
20 - Fast-forward merge semantics at 75 000-file scale.
21 - Memory: three 75 000-file manifests stay under 64 MB peak.
22 - Snapshot I/O round-trip at 75 000 files: write < 500 ms, read < 500 ms.
23 - Full three-way pipeline (diff → detect → apply) at 75 000 files: < 5 s.
24 """
25
26 from __future__ import annotations
27 from collections.abc import Mapping
28
29 import datetime
30 import hashlib
31 import pathlib
32 import shutil
33 import tempfile
34 import time
35 import tracemalloc
36
37 import pytest
38
39 from muse.core.merge_engine import (
40 apply_merge,
41 detect_conflicts,
42 diff_snapshots,
43 find_merge_base,
44 )
45 from muse.core.snapshot import compute_commit_id, compute_snapshot_id
46 from muse.core.store import (
47 CommitRecord,
48 SnapshotRecord,
49 commit_path,
50 write_commit,
51 write_snapshot,
52 )
53 from muse.core.types import Manifest, blob_id
54 from muse.core.paths import muse_dir
55
56 # ---------------------------------------------------------------------------
57 # Helpers
58 # ---------------------------------------------------------------------------
59
60 _NOW = datetime.datetime(2024, 1, 1, tzinfo=datetime.timezone.utc)
61 _REPO_ID = "bench"
62
63
64 def _s256(data: bytes) -> str:
65 return blob_id(data)
66
67
68 def _fresh_repo(path: pathlib.Path, max_ancestors: int = 200_000) -> pathlib.Path:
69 dot_muse = muse_dir(path)
70 dot_muse.mkdir(parents=True)
71 (dot_muse / "repo.json").write_text('{"repo_id":"bench","owner":"bench"}')
72 (dot_muse / "config.toml").write_text(f"[limits]\nmax_ancestors = {max_ancestors}\n")
73 for d in ("commits", "snapshots", "objects"):
74 (dot_muse / d).mkdir()
75 (dot_muse / "refs" / "heads").mkdir(parents=True)
76 (dot_muse / "HEAD").write_text("ref: refs/heads/main\n")
77 return path
78
79
80 def _make_commit(
81 root: pathlib.Path,
82 parent_id: str | None,
83 snap_id: str,
84 msg: str,
85 offset_secs: int = 0,
86 ) -> str:
87 parent_ids = [parent_id] if parent_id else []
88 ts = _NOW + datetime.timedelta(seconds=offset_secs)
89 cid = compute_commit_id(
90 parent_ids=parent_ids,
91 snapshot_id=snap_id,
92 message=msg,
93 committed_at_iso=ts.isoformat(),
94 author="bench",
95 )
96 write_commit(
97 root,
98 CommitRecord(
99 repo_id="bench",
100 commit_id=cid,
101 branch="br",
102 message=msg,
103 author="bench",
104 committed_at=ts,
105 parent_commit_id=parent_id,
106 parent2_commit_id=None,
107 snapshot_id=snap_id,
108 metadata={},
109 sem_ver_bump="PATCH",
110 ),
111 )
112 return cid
113
114
115 def _write_chain(root: pathlib.Path, depth: int, prefix: str, parent_id: str) -> str:
116 """Write a linear chain of *depth* commits on top of *parent_id*. Returns tip."""
117 snap = SnapshotRecord(
118 snapshot_id=compute_snapshot_id({}), manifest={}, created_at=_NOW
119 )
120 write_snapshot(root, snap)
121 prev = parent_id
122 for i in range(depth):
123 prev = _make_commit(root, prev, snap.snapshot_id, f"{prefix}-{i}", i)
124 return prev
125
126
127 def _build_manifests(
128 n_base: int,
129 n_ours: int,
130 n_theirs: int,
131 n_conflict: int,
132 ) -> tuple[Mapping[str, str], Mapping[str, str], Mapping[str, str]]:
133 """Return (base, ours, theirs) manifests for a scale scenario."""
134 base = {f"f{i:06d}.py": _s256(bytes([i % 256] * 64)) for i in range(n_base)}
135 ours = dict(base)
136 theirs = dict(base)
137 for i in range(n_ours):
138 ours[f"f{i:06d}.py"] = _s256(b"ours" + bytes([i % 256] * 60))
139 for i in range(n_ours, n_ours + n_theirs):
140 theirs[f"f{i:06d}.py"] = _s256(b"theirs" + bytes([i % 256] * 60))
141 conflict_start = n_ours + n_theirs
142 for i in range(conflict_start, conflict_start + n_conflict):
143 ours[f"f{i:06d}.py"] = _s256(b"ours_c" + bytes([i % 256] * 56))
144 theirs[f"f{i:06d}.py"] = _s256(b"theirs_c" + bytes([i % 256] * 56))
145 return base, ours, theirs
146
147
148 # ---------------------------------------------------------------------------
149 # TestDiffSnapshotsAtScale — the pure set-arithmetic hot path
150 # ---------------------------------------------------------------------------
151
152
153 class TestDiffSnapshotsAtScale:
154 """diff_snapshots is pure Python set arithmetic — verifies correctness at 75k."""
155
156 def test_diff_empty_manifests(self) -> None:
157 assert diff_snapshots({}, {}) == set()
158
159 def test_diff_no_changes(self) -> None:
160 m = {f"f{i}.py": _s256(bytes([i % 256])) for i in range(1000)}
161 assert diff_snapshots(m, m) == set()
162
163 def test_diff_all_added(self) -> None:
164 other = {f"f{i}.py": _s256(bytes([i % 256])) for i in range(500)}
165 result = diff_snapshots({}, other)
166 assert result == set(other)
167
168 def test_diff_all_deleted(self) -> None:
169 base = {f"f{i}.py": _s256(bytes([i % 256])) for i in range(500)}
170 assert diff_snapshots(base, {}) == set(base)
171
172 def test_diff_partial_modify(self) -> None:
173 base = {f"f{i}.py": _s256(bytes([i % 256])) for i in range(1000)}
174 other = dict(base)
175 for i in range(0, 100):
176 other[f"f{i}.py"] = _s256(b"new" + bytes([i % 256]))
177 result = diff_snapshots(base, other)
178 assert len(result) == 100
179 assert all(f"f{i}.py" in result for i in range(100))
180
181 def test_diff_symmetry_add_delete(self) -> None:
182 """diff_snapshots(a, b) == diff_snapshots(b, a) for add/delete (same paths, different meaning)."""
183 base = {"x.py": "h1"}
184 other = {"y.py": "h2"}
185 assert diff_snapshots(base, other) == diff_snapshots(other, base)
186
187 def test_diff_75k_under_500ms(self) -> None:
188 """diff_snapshots on 75k-file manifests completes in < 500 ms."""
189 base, ours, _ = _build_manifests(75_000, 5_000, 0, 0)
190 t0 = time.perf_counter()
191 result = diff_snapshots(base, ours)
192 duration_ms = (time.perf_counter() - t0) * 1000
193 assert len(result) == 5_000
194 assert duration_ms < 500, f"diff_snapshots took {duration_ms:.1f}ms (limit: 500ms)"
195
196
197 # ---------------------------------------------------------------------------
198 # TestDetectConflictsSemantics — correctness of the new convergence semantics
199 # ---------------------------------------------------------------------------
200
201
202 class TestDetectConflictsSemantics:
203 """Verifies the fixed convergence semantics of detect_conflicts."""
204
205 def test_disjoint_changes_no_conflict(self) -> None:
206 ours_m = {"a.py": "h_a"}
207 theirs_m = {"b.py": "h_b"}
208 assert detect_conflicts({"a.py"}, {"b.py"}, ours_m, theirs_m) == set()
209
210 def test_divergent_change_is_conflict(self) -> None:
211 ours_m = {"x.py": "hash_ours"}
212 theirs_m = {"x.py": "hash_theirs"}
213 assert detect_conflicts({"x.py"}, {"x.py"}, ours_m, theirs_m) == {"x.py"}
214
215 def test_both_delete_is_convergent(self) -> None:
216 """Both branches deleted the same file — convergent, NOT a conflict."""
217 assert detect_conflicts({"gone.py"}, {"gone.py"}, {}, {}) == set()
218
219 def test_both_delete_absent_from_merged(self) -> None:
220 """Both-delete: convergent → apply_merge correctly omits the file."""
221 base = {"gone.py": "h_old", "keep.py": "h_k"}
222 ours = {"keep.py": "h_k"}
223 theirs = {"keep.py": "h_k"}
224 oc = diff_snapshots(base, ours)
225 tc = diff_snapshots(base, theirs)
226 conflicts = detect_conflicts(oc, tc, ours, theirs)
227 merged = apply_merge(base, ours, theirs, oc, tc, conflicts)
228 assert "gone.py" not in merged, "Both-delete must remove file from merged"
229 assert "keep.py" in merged
230
231 def test_same_add_same_hash_convergent(self) -> None:
232 """Both branches independently added the same file with identical content."""
233 ours_m = {"new.py": "hash42"}
234 theirs_m = {"new.py": "hash42"}
235 assert detect_conflicts({"new.py"}, {"new.py"}, ours_m, theirs_m) == set()
236
237 def test_same_add_present_in_merged(self) -> None:
238 """Same-add convergent → apply_merge includes the file at the agreed hash."""
239 base: Manifest = {}
240 h = _s256(b"shared-content")
241 ours = {"new.py": h}
242 theirs = {"new.py": h}
243 oc = diff_snapshots(base, ours)
244 tc = diff_snapshots(base, theirs)
245 conflicts = detect_conflicts(oc, tc, ours, theirs)
246 merged = apply_merge(base, ours, theirs, oc, tc, conflicts)
247 assert "new.py" not in conflicts
248 assert merged.get("new.py") == h
249
250 def test_delete_vs_modify_is_conflict(self) -> None:
251 """One side deleted, other modified — genuinely divergent."""
252 ours_m: Manifest = {}
253 theirs_m = {"a.py": "hash_new"}
254 assert detect_conflicts({"a.py"}, {"a.py"}, ours_m, theirs_m) == {"a.py"}
255
256 def test_same_add_different_hash_is_conflict(self) -> None:
257 """Both added same path with DIFFERENT content — real conflict."""
258 ours_m = {"new.py": "h_v1"}
259 theirs_m = {"new.py": "h_v2"}
260 assert detect_conflicts({"new.py"}, {"new.py"}, ours_m, theirs_m) == {"new.py"}
261
262 def test_commutativity(self) -> None:
263 """detect_conflicts(a, b, ma, mb) == detect_conflicts(b, a, mb, ma)."""
264 ours_m = {f"f{i}.py": f"h_ours_{i}" for i in range(50)}
265 theirs_m = {f"f{i}.py": f"h_theirs_{i}" for i in range(30, 80)}
266 oc = set(ours_m)
267 tc = set(theirs_m)
268 assert detect_conflicts(oc, tc, ours_m, theirs_m) == detect_conflicts(
269 tc, oc, theirs_m, ours_m
270 )
271
272 def test_detect_conflicts_1k_under_5s(self) -> None:
273 """1 000 conflicting paths detected in well under 5 s (actually < 1 ms)."""
274 paths = {f"conflict-{i:04d}.py" for i in range(1_000)}
275 ours_m = {p: f"ours-{p}" for p in paths}
276 theirs_m = {p: f"theirs-{p}" for p in paths}
277 t0 = time.perf_counter()
278 result = detect_conflicts(paths, paths, ours_m, theirs_m)
279 duration_ms = (time.perf_counter() - t0) * 1000
280 assert result == paths
281 assert duration_ms < 5_000, f"detect_conflicts 1k took {duration_ms:.1f}ms (limit: 5000ms)"
282
283 def test_detect_conflicts_75k_under_500ms(self) -> None:
284 """detect_conflicts on 75k-path intersection completes in < 500 ms."""
285 n = 75_000
286 paths = {f"f{i:06d}.py" for i in range(n)}
287 ours_m = {p: f"ours-{p}" for p in paths}
288 theirs_m = {p: f"theirs-{p}" for p in paths}
289 t0 = time.perf_counter()
290 result = detect_conflicts(paths, paths, ours_m, theirs_m)
291 duration_ms = (time.perf_counter() - t0) * 1000
292 assert len(result) == n
293 assert duration_ms < 500, f"detect_conflicts 75k took {duration_ms:.1f}ms (limit: 500ms)"
294
295
296 # ---------------------------------------------------------------------------
297 # TestApplyMergeAtScale — correctness and timing of apply_merge
298 # ---------------------------------------------------------------------------
299
300
301 class TestApplyMergeAtScale:
302 """apply_merge correctness and performance at 75k files."""
303
304 def test_apply_no_changes(self) -> None:
305 base = {"a.py": "h1", "b.py": "h2"}
306 merged = apply_merge(base, base, base, set(), set(), set())
307 assert merged == base
308
309 def test_apply_ours_only_addition(self) -> None:
310 base: Manifest = {}
311 ours = {"new.py": "h_new"}
312 merged = apply_merge(base, ours, {}, {"new.py"}, set(), set())
313 assert merged["new.py"] == "h_new"
314
315 def test_apply_theirs_only_deletion(self) -> None:
316 base = {"del.py": "h_old", "keep.py": "h_k"}
317 ours = dict(base)
318 theirs = {"keep.py": "h_k"}
319 merged = apply_merge(base, ours, theirs, set(), {"del.py"}, set())
320 assert "del.py" not in merged
321 assert "keep.py" in merged
322
323 def test_apply_conflict_stays_at_base(self) -> None:
324 base = {"c.py": "h_base"}
325 ours = {"c.py": "h_ours"}
326 theirs = {"c.py": "h_theirs"}
327 merged = apply_merge(base, ours, theirs, {"c.py"}, {"c.py"}, {"c.py"})
328 assert merged["c.py"] == "h_base"
329
330 def test_apply_all_conflict_returns_base(self) -> None:
331 """When every path is a conflict, apply_merge returns a copy of base."""
332 base = {f"f{i}.py": f"h{i}" for i in range(100)}
333 ours = {p: f"ours-{v}" for p, v in base.items()}
334 theirs = {p: f"theirs-{v}" for p, v in base.items()}
335 oc = set(base)
336 tc = set(base)
337 merged = apply_merge(base, ours, theirs, oc, tc, oc)
338 assert merged == base
339
340 def test_apply_75k_5k_5k_under_500ms(self) -> None:
341 """apply_merge on 75k files with 5k ours + 5k theirs changes: < 500 ms."""
342 base, ours, theirs = _build_manifests(75_000, 5_000, 5_000, 0)
343 oc = diff_snapshots(base, ours)
344 tc = diff_snapshots(base, theirs)
345 conflicts = detect_conflicts(oc, tc, ours, theirs)
346 t0 = time.perf_counter()
347 merged = apply_merge(base, ours, theirs, oc, tc, conflicts)
348 duration_ms = (time.perf_counter() - t0) * 1000
349 assert len(conflicts) == 0
350 assert len(merged) == 75_000
351 assert duration_ms < 500, f"apply_merge 75k took {duration_ms:.1f}ms (limit: 500ms)"
352
353 def test_apply_75k_with_1k_conflicts_under_500ms(self) -> None:
354 """apply_merge with 1k conflict paths at 75k scale: < 500 ms."""
355 base, ours, theirs = _build_manifests(75_000, 5_000, 5_000, 1_000)
356 oc = diff_snapshots(base, ours)
357 tc = diff_snapshots(base, theirs)
358 conflicts = detect_conflicts(oc, tc, ours, theirs)
359 t0 = time.perf_counter()
360 merged = apply_merge(base, ours, theirs, oc, tc, conflicts)
361 duration_ms = (time.perf_counter() - t0) * 1000
362 assert len(conflicts) == 1_000
363 assert duration_ms < 500, f"apply_merge 75k+conflicts took {duration_ms:.1f}ms (limit: 500ms)"
364
365
366 # ---------------------------------------------------------------------------
367 # TestFullMergePipeline — diff → detect → apply at scale
368 # ---------------------------------------------------------------------------
369
370
371 class TestFullMergePipeline:
372 """End-to-end pure-function pipeline timing and correctness."""
373
374 def test_pipeline_correctness_small(self) -> None:
375 base = {"a.py": "base_a", "b.py": "base_b", "c.py": "base_c"}
376 # ours: modifies a.py, leaves b.py and c.py unchanged
377 ours = {"a.py": "ours_a", "b.py": "base_b", "c.py": "base_c"}
378 # theirs: leaves a.py unchanged, modifies b.py, leaves c.py, adds d.py
379 theirs = {"a.py": "base_a", "b.py": "theirs_b", "c.py": "base_c", "d.py": "new_d"}
380 oc = diff_snapshots(base, ours)
381 tc = diff_snapshots(base, theirs)
382 conflicts = detect_conflicts(oc, tc, ours, theirs)
383 merged = apply_merge(base, ours, theirs, oc, tc, conflicts)
384 assert merged["a.py"] == "ours_a" # ours-only modification
385 assert merged["b.py"] == "theirs_b" # theirs-only modification
386 assert merged["d.py"] == "new_d" # theirs-only addition
387 assert merged["c.py"] == "base_c" # untouched by both
388
389 def test_pipeline_both_delete_resolved(self) -> None:
390 """Pipeline: both-delete produces no conflict and absent file in merged."""
391 base = {"rm.py": "old", "keep.py": "k"}
392 ours = {"keep.py": "k"}
393 theirs = {"keep.py": "k"}
394 oc = diff_snapshots(base, ours)
395 tc = diff_snapshots(base, theirs)
396 conflicts = detect_conflicts(oc, tc, ours, theirs)
397 merged = apply_merge(base, ours, theirs, oc, tc, conflicts)
398 assert "rm.py" not in conflicts
399 assert "rm.py" not in merged
400
401 def test_pipeline_same_add_resolved(self) -> None:
402 """Pipeline: same-add same-hash produces no conflict and file in merged."""
403 base: Manifest = {}
404 h = _s256(b"shared")
405 ours = {"new.py": h}
406 theirs = {"new.py": h}
407 oc = diff_snapshots(base, ours)
408 tc = diff_snapshots(base, theirs)
409 conflicts = detect_conflicts(oc, tc, ours, theirs)
410 merged = apply_merge(base, ours, theirs, oc, tc, conflicts)
411 assert "new.py" not in conflicts
412 assert merged.get("new.py") == h
413
414 def test_pipeline_75k_5k_5k_under_5s(self) -> None:
415 """Full pipeline (diff×2 + detect + apply) at 75k files, 5k+5k changes: < 5 s."""
416 base, ours, theirs = _build_manifests(75_000, 5_000, 5_000, 0)
417 t0 = time.perf_counter()
418 oc = diff_snapshots(base, ours)
419 tc = diff_snapshots(base, theirs)
420 conflicts = detect_conflicts(oc, tc, ours, theirs)
421 merged = apply_merge(base, ours, theirs, oc, tc, conflicts)
422 elapsed = time.perf_counter() - t0
423 assert len(conflicts) == 0
424 assert len(merged) == 75_000
425 assert elapsed < 5, f"Full pipeline 75k took {elapsed:.2f}s (limit: 5s)"
426
427 def test_pipeline_75k_with_1k_conflicts_under_5s(self) -> None:
428 """Full pipeline with 1k conflict paths at 75k scale: < 5 s."""
429 base, ours, theirs = _build_manifests(75_000, 5_000, 5_000, 1_000)
430 t0 = time.perf_counter()
431 oc = diff_snapshots(base, ours)
432 tc = diff_snapshots(base, theirs)
433 conflicts = detect_conflicts(oc, tc, ours, theirs)
434 merged = apply_merge(base, ours, theirs, oc, tc, conflicts)
435 elapsed = time.perf_counter() - t0
436 assert len(conflicts) == 1_000
437 assert elapsed < 5, f"Full pipeline 75k+conflicts took {elapsed:.2f}s (limit: 5s)"
438
439 def test_pipeline_memory_3_manifests_under_64mb(self) -> None:
440 """Three 75k-file manifests (base + ours + theirs) peak < 64 MB."""
441 tracemalloc.start()
442 base, ours, theirs = _build_manifests(75_000, 5_000, 5_000, 1_000)
443 _, peak = tracemalloc.get_traced_memory()
444 tracemalloc.stop()
445 peak_mb = peak / 1024 / 1024
446 assert peak_mb < 64, f"3 manifests at 75k peak {peak_mb:.1f}MB (limit: 64MB)"
447
448
449 # ---------------------------------------------------------------------------
450 # TestSnapshotIOAtScale — read_snapshot / write_snapshot at 75k files
451 # ---------------------------------------------------------------------------
452
453
454 class TestSnapshotIOAtScale:
455 """Snapshot serialisation/deserialisation timing at 75k-file scale."""
456
457 def test_write_snapshot_75k_under_500ms(self, tmp_path: pathlib.Path) -> None:
458 root = _fresh_repo(tmp_path)
459 manifest = {f"f{i:06d}.py": _s256(bytes([i % 256] * 64)) for i in range(75_000)}
460 snap_id = compute_snapshot_id(manifest)
461 snap = SnapshotRecord(snapshot_id=snap_id, manifest=manifest, created_at=_NOW)
462 t0 = time.perf_counter()
463 write_snapshot(root, snap)
464 duration_ms = (time.perf_counter() - t0) * 1000
465 assert duration_ms < 500, f"write_snapshot 75k took {duration_ms:.1f}ms (limit: 500ms)"
466
467 def test_read_snapshot_75k_under_500ms(self, tmp_path: pathlib.Path) -> None:
468 from muse.core.store import read_snapshot
469
470 root = _fresh_repo(tmp_path)
471 manifest = {f"f{i:06d}.py": _s256(bytes([i % 256] * 64)) for i in range(75_000)}
472 snap_id = compute_snapshot_id(manifest)
473 write_snapshot(root, SnapshotRecord(snapshot_id=snap_id, manifest=manifest, created_at=_NOW))
474 t0 = time.perf_counter()
475 loaded = read_snapshot(root, snap_id)
476 duration_ms = (time.perf_counter() - t0) * 1000
477 assert loaded is not None
478 assert len(loaded.manifest) == 75_000
479 assert duration_ms < 500, f"read_snapshot 75k took {duration_ms:.1f}ms (limit: 500ms)"
480
481 def test_snapshot_roundtrip_integrity(self, tmp_path: pathlib.Path) -> None:
482 """write + read produces bit-identical manifest."""
483 from muse.core.store import read_snapshot
484
485 root = _fresh_repo(tmp_path)
486 manifest = {f"f{i:04d}.py": _s256(bytes([i % 256])) for i in range(10_000)}
487 snap_id = compute_snapshot_id(manifest)
488 write_snapshot(root, SnapshotRecord(snapshot_id=snap_id, manifest=manifest, created_at=_NOW))
489 loaded = read_snapshot(root, snap_id)
490 assert loaded is not None
491 assert loaded.manifest == manifest
492
493
494 # ---------------------------------------------------------------------------
495 # TestFindMergeBaseCorrectness — DAG edge cases
496 # ---------------------------------------------------------------------------
497
498
499 class TestFindMergeBaseCorrectness:
500 """find_merge_base correctness across edge cases."""
501
502 def _repo_with_base(
503 self, tmp_path: pathlib.Path, max_ancestors: int = 200_000
504 ) -> tuple[pathlib.Path, str, str]:
505 """Return (root, base_commit_id, snap_id)."""
506 root = _fresh_repo(tmp_path, max_ancestors=max_ancestors)
507 snap_id = compute_snapshot_id({})
508 write_snapshot(root, SnapshotRecord(snapshot_id=snap_id, manifest={}, created_at=_NOW))
509 base_id = _make_commit(root, None, snap_id, "base", 0)
510 return root, base_id, snap_id
511
512 def test_lca_simple_diverging_chains(self, tmp_path: pathlib.Path) -> None:
513 root, base_id, snap_id = self._repo_with_base(tmp_path)
514 tip_a = _write_chain(root, 10, "a", base_id)
515 tip_b = _write_chain(root, 10, "b", base_id)
516 result = find_merge_base(root, tip_a, tip_b)
517 assert result == base_id
518
519 def test_lca_identical_tips(self, tmp_path: pathlib.Path) -> None:
520 """find_merge_base(tip, tip) == tip."""
521 root, base_id, snap_id = self._repo_with_base(tmp_path)
522 tip = _write_chain(root, 5, "a", base_id)
523 assert find_merge_base(root, tip, tip) == tip
524
525 def test_lca_a_is_ancestor_of_b(self, tmp_path: pathlib.Path) -> None:
526 """When a is a direct ancestor of b, LCA is a."""
527 root, base_id, snap_id = self._repo_with_base(tmp_path)
528 mid = _write_chain(root, 3, "chain", base_id)
529 tip = _write_chain(root, 3, "ext", mid)
530 result = find_merge_base(root, mid, tip)
531 assert result == mid
532
533 def test_lca_disjoint_histories_returns_none(self, tmp_path: pathlib.Path) -> None:
534 root = _fresh_repo(tmp_path)
535 snap_id = compute_snapshot_id({})
536 write_snapshot(root, SnapshotRecord(snapshot_id=snap_id, manifest={}, created_at=_NOW))
537 a = _make_commit(root, None, snap_id, "a", 0)
538 b = _make_commit(root, None, snap_id, "b", 1)
539 assert find_merge_base(root, a, b) is None
540
541 def test_lca_criss_cross_dag_valid_lca(self, tmp_path: pathlib.Path) -> None:
542 """Criss-cross DAG (merge_1 has parents a+b, merge_2 has parents b+a).
543 Both a and b are valid LCAs; BFS must return one of them.
544 """
545 root, base_id, snap_id = self._repo_with_base(tmp_path)
546 a = _make_commit(root, base_id, snap_id, "a", 1)
547 b = _make_commit(root, base_id, snap_id, "b", 2)
548
549 # m1: a merges b
550 ts = _NOW + datetime.timedelta(seconds=3)
551 m1_id = compute_commit_id( parent_ids=[a, b],
552 snapshot_id=snap_id,
553 message="merge1",
554 committed_at_iso=ts.isoformat(),
555 author="b",)
556 write_commit(
557 root,
558 CommitRecord(
559 commit_id=m1_id, repo_id=_REPO_ID, branch="a",
560 message="merge1", author="b", committed_at=ts,
561 parent_commit_id=a, parent2_commit_id=b,
562 snapshot_id=snap_id, metadata={}, sem_ver_bump="PATCH",
563 ),
564 )
565
566 # m2: b merges a
567 ts2 = _NOW + datetime.timedelta(seconds=4)
568 m2_id = compute_commit_id( parent_ids=[b, a],
569 snapshot_id=snap_id,
570 message="merge2",
571 committed_at_iso=ts2.isoformat(),
572 author="b",)
573 write_commit(
574 root,
575 CommitRecord(
576 commit_id=m2_id, repo_id=_REPO_ID, branch="b",
577 message="merge2", author="b", committed_at=ts2,
578 parent_commit_id=b, parent2_commit_id=a,
579 snapshot_id=snap_id, metadata={}, sem_ver_bump="PATCH",
580 ),
581 )
582
583 result = find_merge_base(root, m1_id, m2_id)
584 assert result in {a, b}, f"Expected a or b as LCA, got {result}"
585
586 def test_lca_cap_raises_clean_error(self, tmp_path: pathlib.Path) -> None:
587 """Ancestor graph > max_ancestors raises MuseCLIError, not a silent None."""
588 from muse.core.errors import MuseCLIError
589
590 root = _fresh_repo(tmp_path, max_ancestors=20)
591 snap_id = compute_snapshot_id({})
592 write_snapshot(root, SnapshotRecord(snapshot_id=snap_id, manifest={}, created_at=_NOW))
593 # 25-long chains share no ancestor — A side will hit cap
594 prev_a: str | None = None
595 for i in range(25):
596 prev_a = _make_commit(root, prev_a, snap_id, f"a-{i}", i)
597 prev_b: str | None = None
598 for i in range(25):
599 prev_b = _make_commit(root, prev_b, snap_id, f"b-{i}", i + 25)
600 assert prev_a is not None
601 assert prev_b is not None
602 with pytest.raises(MuseCLIError, match="Ancestor graph exceeds"):
603 find_merge_base(root, prev_a, prev_b)
604
605 def test_lca_missing_commit_handled(self, tmp_path: pathlib.Path) -> None:
606 """BFS continues gracefully when a commit file is missing (None from read_commit)."""
607 root, base_id, snap_id = self._repo_with_base(tmp_path)
608 # Chain a: base → real commit
609 tip_a = _write_chain(root, 5, "a", base_id)
610 # Chain b: points to a non-existent commit ID (ghost)
611 ghost_id = _s256(b"ghost-commit-does-not-exist")
612 # Stub the ghost so write_commit's parent-existence guard passes;
613 # find_merge_base will encounter the unreadable stub and stop.
614 _p = commit_path(root, ghost_id)
615 _p.parent.mkdir(parents=True, exist_ok=True)
616 _p.write_bytes(b"")
617 # wrap the ghost in a real commit so find_merge_base walks into it
618 ts = _NOW + datetime.timedelta(seconds=100)
619 wrap_id = compute_commit_id( parent_ids=[ghost_id],
620 snapshot_id=snap_id,
621 message="wrap",
622 committed_at_iso=ts.isoformat(),
623 author="b",)
624 write_commit(
625 root,
626 CommitRecord(
627 commit_id=wrap_id, repo_id=_REPO_ID, branch="b",
628 message="wrap", author="b", committed_at=ts,
629 parent_commit_id=ghost_id, parent2_commit_id=None,
630 snapshot_id=snap_id, metadata={}, sem_ver_bump="PATCH",
631 ),
632 )
633 # Should not raise — returns None because the ghost branch has no real ancestors
634 result = find_merge_base(root, tip_a, wrap_id)
635 assert result is None # ghost side has no ancestors in common with a
636
637
638 # ---------------------------------------------------------------------------
639 # TestFindMergeBasePerformance — timing at real-world commit depths
640 # ---------------------------------------------------------------------------
641
642
643 class TestFindMergeBasePerformance:
644 """find_merge_base timing. Each test builds fresh chains in a temp dir."""
645
646 @pytest.mark.parametrize("depth", [100, 500])
647 def test_find_merge_base_depth_under_2s(
648 self, depth: int, tmp_path: pathlib.Path
649 ) -> None:
650 """find_merge_base on two diverging {depth}-commit chains: < 2 s."""
651 root = _fresh_repo(tmp_path)
652 snap_id = compute_snapshot_id({})
653 write_snapshot(root, SnapshotRecord(snapshot_id=snap_id, manifest={}, created_at=_NOW))
654 base_id = _make_commit(root, None, snap_id, "base", 0)
655 tip_a = _write_chain(root, depth, "a", base_id)
656 tip_b = _write_chain(root, depth, "b", base_id)
657 t0 = time.perf_counter()
658 result = find_merge_base(root, tip_a, tip_b)
659 elapsed = time.perf_counter() - t0
660 assert result == base_id, f"Wrong LCA at depth={depth}"
661 assert elapsed < 2, f"find_merge_base depth={depth} took {elapsed:.2f}s (limit: 2s)"
662
663 @pytest.mark.slow
664 def test_find_merge_base_1k_depth_under_5s(self, tmp_path: pathlib.Path) -> None:
665 """find_merge_base on 1k-commit diverging chains: < 5 s."""
666 root = _fresh_repo(tmp_path)
667 snap_id = compute_snapshot_id({})
668 write_snapshot(root, SnapshotRecord(snapshot_id=snap_id, manifest={}, created_at=_NOW))
669 base_id = _make_commit(root, None, snap_id, "base", 0)
670 tip_a = _write_chain(root, 1_000, "a", base_id)
671 tip_b = _write_chain(root, 1_000, "b", base_id)
672 t0 = time.perf_counter()
673 result = find_merge_base(root, tip_a, tip_b)
674 elapsed = time.perf_counter() - t0
675 assert result == base_id
676 assert elapsed < 5, f"find_merge_base 1k took {elapsed:.2f}s (limit: 5s)"
677
678 @pytest.mark.slow
679 def test_find_merge_base_5k_depth_under_30s(self, tmp_path: pathlib.Path) -> None:
680 """find_merge_base on 5k-commit diverging chains: < 30 s (the merge target)."""
681 root = _fresh_repo(tmp_path)
682 snap_id = compute_snapshot_id({})
683 write_snapshot(root, SnapshotRecord(snapshot_id=snap_id, manifest={}, created_at=_NOW))
684 base_id = _make_commit(root, None, snap_id, "base", 0)
685 tip_a = _write_chain(root, 5_000, "a", base_id)
686 tip_b = _write_chain(root, 5_000, "b", base_id)
687 t0 = time.perf_counter()
688 result = find_merge_base(root, tip_a, tip_b)
689 elapsed = time.perf_counter() - t0
690 assert result == base_id
691 assert elapsed < 30, f"find_merge_base 5k took {elapsed:.2f}s (limit: 30s)"
692
693
694 # ---------------------------------------------------------------------------
695 # TestFullMergeScaleSlow — the 30-second overall target (@slow)
696 # ---------------------------------------------------------------------------
697
698
699 @pytest.mark.slow
700 class TestFullMergeScaleSlow:
701 """End-to-end scale targets that require @slow to keep CI fast."""
702
703 def test_full_pipeline_75k_5k_5k_1k_conflicts_under_30s(self) -> None:
704 """Full pipeline: 75k files, 5k ours, 5k theirs, 1k conflicts — < 30 s."""
705 base, ours, theirs = _build_manifests(75_000, 5_000, 5_000, 1_000)
706 t0 = time.perf_counter()
707 oc = diff_snapshots(base, ours)
708 tc = diff_snapshots(base, theirs)
709 conflicts = detect_conflicts(oc, tc, ours, theirs)
710 merged = apply_merge(base, ours, theirs, oc, tc, conflicts)
711 elapsed = time.perf_counter() - t0
712 assert len(conflicts) == 1_000
713 assert len(merged) == 75_000
714 assert elapsed < 30, f"Full pipeline 75k+1k conflicts took {elapsed:.2f}s (limit: 30s)"
715
716 def test_snapshot_io_75k_three_reads_plus_write_under_30s(
717 self, tmp_path: pathlib.Path
718 ) -> None:
719 """3 reads + 1 write of a 75k-file snapshot (realistic merge I/O) < 30 s."""
720 from muse.core.store import read_snapshot
721
722 root = _fresh_repo(tmp_path)
723 manifest = {f"f{i:06d}.py": _s256(bytes([i % 256] * 64)) for i in range(75_000)}
724 snap_id = compute_snapshot_id(manifest)
725 write_snapshot(root, SnapshotRecord(snapshot_id=snap_id, manifest=manifest, created_at=_NOW))
726
727 t0 = time.perf_counter()
728 for _ in range(3):
729 snap = read_snapshot(root, snap_id)
730 assert snap is not None and len(snap.manifest) == 75_000
731 # write the merged result
732 merged_snap_id = compute_snapshot_id(manifest)
733 write_snapshot(root, SnapshotRecord(snapshot_id=merged_snap_id, manifest=manifest, created_at=_NOW))
734 elapsed = time.perf_counter() - t0
735 assert elapsed < 30, f"3 reads + 1 write 75k took {elapsed:.2f}s (limit: 30s)"
736
737 def test_write_merge_state_1k_conflicts_roundtrip(
738 self, tmp_path: pathlib.Path
739 ) -> None:
740 """write_merge_state + read_merge_state with 1 000 conflict paths round-trips cleanly."""
741 from muse.core.merge_engine import read_merge_state, write_merge_state
742
743 root = _fresh_repo(tmp_path)
744 conflict_paths = [f"conflict/f{i:04d}.py" for i in range(1_000)]
745
746 write_merge_state(
747 root,
748 base_commit="a" * 64,
749 ours_commit="b" * 64,
750 theirs_commit="c" * 64,
751 conflict_paths=conflict_paths,
752 other_branch="feat/big-change",
753 )
754
755 state = read_merge_state(root)
756 assert state is not None
757 assert len(state.conflict_paths) == 1_000
758 assert state.other_branch == "feat/big-change"
759 # Paths must round-trip correctly
760 assert sorted(state.conflict_paths) == sorted(conflict_paths)
File History 1 commit
sha256:51ce277f663e01a43eaffbe77509b1de7ac2d4251b55d23306304bcdeb92c90d feat(pack): delta-encode snapshots in MPackBundle wire format Sonnet 4.6 minor ⚠ 120 days ago