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