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