gabriel / muse public
test_property_merge_invariants.py python
711 lines 29.8 KB
Raw
sha256:660fcac1df3ab28f61862e961890bd2ca8b754fa0242079d93ca1e25037ec8a6 chore(tests): add docstring to tests/__init__.py so rc14 tr… Human 26 days ago
1 """Property-based tests for the three-way merge engine invariants.
2
3 These tests use Hypothesis to generate random manifests and DAG shapes and
4 verify mathematical invariants that must hold for ANY input — not just the
5 specific inputs we thought to write as unit tests.
6
7 Why these tests?
8 ----------------
9 The silent-drop bug (fixed in 73427a30) survived all existing tests because
10 the existing tests only exercised SPECIFIC manifests. A property test with
11 the invariant "theirs-only files must survive merge" would have caught it
12 immediately: Hypothesis would have generated a manifest where theirs added
13 a file that ours didn't touch, run apply_merge, and found the file absent.
14
15 Invariants tested
16 -----------------
17 M1 Theirs-only additions survive in merged manifest.
18 M2 Ours-only additions survive in merged manifest.
19 M3 Theirs-only deletions are applied in merged manifest.
20 M4 Ours-only deletions are applied in merged manifest.
21 M5 Conflict paths are exactly the intersection of ours_changed and theirs_changed.
22 M6 Conflict paths are absent from apply_merge output (caller resolves them).
23 M7 Non-conflicting paths from both sides are correct in output.
24 M8 Identical content on both sides is never a conflict in diff_snapshots.
25 M9 apply_merge is idempotent when ours == theirs (convergence).
26 M10 merged result contains no paths from conflict_paths when they exist.
27
28 LCA invariants
29 --------------
30 L1 LCA(A, A) == A.
31 L2 LCA(A, B) is an ancestor of A (reachable from A).
32 L3 LCA(A, B) is an ancestor of B (reachable from B).
33 L4 LCA(A, B) == LCA(B, A) — commutativity.
34 L5 If A is ancestor of B, LCA(A, B) == A.
35
36 Snapshot integrity invariant
37 ----------------------------
38 SI1 Every object_id referenced in a merged manifest exists in the object store.
39 """
40 from __future__ import annotations
41
42 import datetime
43 import hashlib
44 import json
45 import pathlib
46 import uuid
47
48 import pytest
49 from hypothesis import HealthCheck, given, settings
50 from hypothesis import strategies as st
51
52 from muse.core.merge_engine import (
53 apply_merge,
54 detect_conflicts,
55 diff_snapshots,
56 find_merge_base,
57 )
58 from muse.core._types import Manifest
59
60
61 # ---------------------------------------------------------------------------
62 # Strategies — building blocks for random manifests and DAGs
63 # ---------------------------------------------------------------------------
64
65
66 def _h(label: str) -> str:
67 return hashlib.sha256(label.encode()).hexdigest()
68
69
70 # A path looks like "src/module_3.py" or "README.md".
71 _path_strategy = st.text(
72 alphabet=st.characters(whitelist_categories=("Ll", "Lu", "Nd"), whitelist_characters="/_-."),
73 min_size=1,
74 max_size=32,
75 ).filter(lambda s: "/" not in s or not s.startswith("/"))
76
77 # A content hash is a 64-char hex string (we use sha256 of a label for uniqueness).
78 _hash_strategy = st.text(
79 alphabet="0123456789abcdef",
80 min_size=64,
81 max_size=64,
82 )
83
84 # A manifest is a dict of path → hash with at most 40 entries.
85 _manifest_strategy = st.dictionaries(
86 keys=_path_strategy,
87 values=_hash_strategy,
88 min_size=0,
89 max_size=40,
90 )
91
92
93 # ---------------------------------------------------------------------------
94 # Helpers
95 # ---------------------------------------------------------------------------
96
97
98 def _linear_repo(
99 tmp_path: pathlib.Path,
100 ) -> tuple[pathlib.Path, str]:
101 """Create a minimal code-domain Muse repo for LCA tests."""
102 from muse.core.snapshot import compute_commit_id, compute_snapshot_id
103 from muse.core.store import CommitRecord, SnapshotRecord, write_commit, write_snapshot
104
105 muse_dir = tmp_path / ".muse"
106 muse_dir.mkdir(exist_ok=True)
107 repo_id = str(uuid.uuid4())
108 (muse_dir / "repo.json").write_text(
109 json.dumps({"repo_id": repo_id, "domain": "code", "default_branch": "main"}),
110 encoding="utf-8",
111 )
112 (muse_dir / "refs" / "heads").mkdir(parents=True, exist_ok=True)
113 (muse_dir / "snapshots").mkdir(exist_ok=True)
114 (muse_dir / "commits").mkdir(exist_ok=True)
115 (muse_dir / "objects").mkdir(exist_ok=True)
116 return tmp_path, repo_id
117
118
119 def _make_commit_lca(
120 root: pathlib.Path,
121 repo_id: str,
122 manifest: Manifest,
123 message: str = "c",
124 parent_id: str | None = None,
125 parent2_id: str | None = None,
126 ) -> str:
127 from muse.core.snapshot import compute_commit_id, compute_snapshot_id
128 from muse.core.store import CommitRecord, SnapshotRecord, write_commit, write_snapshot
129
130 snap_id = compute_snapshot_id(manifest)
131 committed_at = datetime.datetime.now(datetime.timezone.utc)
132 parent_ids: list[str] = []
133 if parent_id:
134 parent_ids.append(parent_id)
135 if parent2_id:
136 parent_ids.append(parent2_id)
137 commit_id = compute_commit_id(
138 parent_ids=parent_ids,
139 snapshot_id=snap_id,
140 message=message,
141 committed_at_iso=committed_at.isoformat(),
142 )
143 write_snapshot(root, SnapshotRecord(snapshot_id=snap_id, manifest=manifest))
144 write_commit(root, CommitRecord(
145 commit_id=commit_id,
146 repo_id=repo_id,
147 branch="main",
148 snapshot_id=snap_id,
149 message=message,
150 committed_at=committed_at,
151 parent_commit_id=parent_id,
152 parent2_commit_id=parent2_id,
153 ))
154 return commit_id
155
156
157 # ===========================================================================
158 # M — apply_merge / diff_snapshots / detect_conflicts invariants
159 # ===========================================================================
160
161
162 class TestMergeEngineInvariantsM:
163 """Property-based invariants for the pure merge functions."""
164
165 @given(
166 base=_manifest_strategy,
167 extra_theirs=_manifest_strategy,
168 )
169 @settings(max_examples=200, suppress_health_check=[HealthCheck.too_slow])
170 def test_M1_theirs_only_additions_survive(
171 self, base: Manifest, extra_theirs: Manifest
172 ) -> None:
173 """M1: every file theirs adds (not in base, not touched by ours) is in merged."""
174 # ours: no changes from base
175 ours = dict(base)
176 # theirs: base + extra_theirs (disjoint new keys only)
177 theirs = dict(base)
178 new_keys = {k: v for k, v in extra_theirs.items() if k not in base}
179 theirs.update(new_keys)
180
181 ours_changed = diff_snapshots(base, ours)
182 theirs_changed = diff_snapshots(base, theirs)
183 conflicts = detect_conflicts(ours_changed, theirs_changed, ours, theirs)
184
185 merged = apply_merge(base, ours, theirs, ours_changed, theirs_changed, conflicts)
186
187 for path, obj_id in new_keys.items():
188 assert path in merged, (
189 f"M1 VIOLATED: theirs-only addition '{path}' absent from merged.\n"
190 f"base keys: {set(base)}\n"
191 f"extra_theirs keys: {set(new_keys)}\n"
192 f"merged keys: {set(merged)}"
193 )
194 assert merged[path] == obj_id, (
195 f"M1 VIOLATED: theirs-only addition '{path}' has wrong hash in merged."
196 )
197
198 @given(
199 base=_manifest_strategy,
200 extra_ours=_manifest_strategy,
201 )
202 @settings(max_examples=200, suppress_health_check=[HealthCheck.too_slow])
203 def test_M2_ours_only_additions_survive(
204 self, base: Manifest, extra_ours: Manifest
205 ) -> None:
206 """M2: every file ours adds (not in base, not touched by theirs) is in merged."""
207 ours = dict(base)
208 new_keys = {k: v for k, v in extra_ours.items() if k not in base}
209 ours.update(new_keys)
210 theirs = dict(base)
211
212 ours_changed = diff_snapshots(base, ours)
213 theirs_changed = diff_snapshots(base, theirs)
214 conflicts = detect_conflicts(ours_changed, theirs_changed, ours, theirs)
215
216 merged = apply_merge(base, ours, theirs, ours_changed, theirs_changed, conflicts)
217
218 for path, obj_id in new_keys.items():
219 assert path in merged, f"M2 VIOLATED: ours-only addition '{path}' absent from merged."
220 assert merged[path] == obj_id
221
222 @given(base=_manifest_strategy, del_keys=st.frozensets(st.text(min_size=1, max_size=20)))
223 @settings(max_examples=200, suppress_health_check=[HealthCheck.too_slow])
224 def test_M3_theirs_only_deletions_applied(
225 self, base: Manifest, del_keys: frozenset[str]
226 ) -> None:
227 """M3: files theirs deletes (and ours does not touch) are absent from merged."""
228 to_delete = {k for k in del_keys if k in base}
229 if not to_delete:
230 return # no relevant keys to test
231
232 ours = dict(base)
233 theirs = {k: v for k, v in base.items() if k not in to_delete}
234
235 ours_changed = diff_snapshots(base, ours)
236 theirs_changed = diff_snapshots(base, theirs)
237 conflicts = detect_conflicts(ours_changed, theirs_changed, ours, theirs)
238
239 merged = apply_merge(base, ours, theirs, ours_changed, theirs_changed, conflicts)
240
241 for path in to_delete:
242 assert path not in merged, (
243 f"M3 VIOLATED: theirs-only deletion '{path}' still present in merged."
244 )
245
246 @given(base=_manifest_strategy, del_keys=st.frozensets(st.text(min_size=1, max_size=20)))
247 @settings(max_examples=200, suppress_health_check=[HealthCheck.too_slow])
248 def test_M4_ours_only_deletions_applied(
249 self, base: Manifest, del_keys: frozenset[str]
250 ) -> None:
251 """M4: files ours deletes (and theirs does not touch) are absent from merged."""
252 to_delete = {k for k in del_keys if k in base}
253 if not to_delete:
254 return
255
256 theirs = dict(base)
257 ours = {k: v for k, v in base.items() if k not in to_delete}
258
259 ours_changed = diff_snapshots(base, ours)
260 theirs_changed = diff_snapshots(base, theirs)
261 conflicts = detect_conflicts(ours_changed, theirs_changed, ours, theirs)
262
263 merged = apply_merge(base, ours, theirs, ours_changed, theirs_changed, conflicts)
264
265 for path in to_delete:
266 assert path not in merged, (
267 f"M4 VIOLATED: ours-only deletion '{path}' still present in merged."
268 )
269
270 @given(base=_manifest_strategy, ours=_manifest_strategy, theirs=_manifest_strategy)
271 @settings(max_examples=300, suppress_health_check=[HealthCheck.too_slow])
272 def test_M5_conflicts_are_divergent_intersection(
273 self,
274 base: Manifest,
275 ours: Manifest,
276 theirs: Manifest,
277 ) -> None:
278 """M5: detect_conflicts returns exactly paths where both changed AND disagree.
279
280 Formally: conflicts = {p ∈ ours_changed ∩ theirs_changed | ours.get(p) ≠ theirs.get(p)}.
281
282 Convergent changes — both deleted the same file (both .get(p) == None), or
283 both added/modified to the same hash — are NOT conflicts. The old invariant
284 that conflicts == ours_changed ∩ theirs_changed was incorrect for these cases.
285 """
286 ours_changed = diff_snapshots(base, ours)
287 theirs_changed = diff_snapshots(base, theirs)
288 conflicts = detect_conflicts(ours_changed, theirs_changed, ours, theirs)
289
290 expected = {
291 p for p in ours_changed & theirs_changed
292 if ours.get(p) != theirs.get(p)
293 }
294 assert conflicts == expected, (
295 f"M5 VIOLATED: conflict set {conflicts!r} != expected {expected!r}.\n"
296 f" ours_changed={ours_changed!r}\n"
297 f" theirs_changed={theirs_changed!r}"
298 )
299
300 @given(base=_manifest_strategy, ours=_manifest_strategy, theirs=_manifest_strategy)
301 @settings(max_examples=200, suppress_health_check=[HealthCheck.too_slow])
302 def test_M6_conflict_paths_absent_from_apply_merge(
303 self,
304 base: Manifest,
305 ours: Manifest,
306 theirs: Manifest,
307 ) -> None:
308 """M6: apply_merge never writes conflict paths — callers resolve them."""
309 ours_changed = diff_snapshots(base, ours)
310 theirs_changed = diff_snapshots(base, theirs)
311 conflicts = detect_conflicts(ours_changed, theirs_changed, ours, theirs)
312
313 merged = apply_merge(base, ours, theirs, ours_changed, theirs_changed, conflicts)
314
315 # Conflict paths must not be in merged at a value taken from ours or theirs
316 # (they stay at base or absent). The strict invariant: a conflict path
317 # must have been either absent from base (so it should be absent in merged)
318 # or present at base's value.
319 for path in conflicts:
320 if path in merged:
321 # If present, it must be at base's value (not ours or theirs override).
322 assert merged[path] == base.get(path), (
323 f"M6 VIOLATED: conflict path '{path}' in merged at non-base value."
324 )
325
326 @given(base=_manifest_strategy, ours=_manifest_strategy, theirs=_manifest_strategy)
327 @settings(max_examples=200, suppress_health_check=[HealthCheck.too_slow])
328 def test_M7_non_conflicting_paths_correct_in_output(
329 self,
330 base: Manifest,
331 ours: Manifest,
332 theirs: Manifest,
333 ) -> None:
334 """M7: non-conflicting ours-only changes are at ours value; theirs-only at theirs value."""
335 ours_changed = diff_snapshots(base, ours)
336 theirs_changed = diff_snapshots(base, theirs)
337 conflicts = detect_conflicts(ours_changed, theirs_changed, ours, theirs)
338 merged = apply_merge(base, ours, theirs, ours_changed, theirs_changed, conflicts)
339
340 for path in ours_changed - conflicts:
341 if path in ours:
342 assert merged.get(path) == ours[path], (
343 f"M7 VIOLATED: ours-only change '{path}' not at ours value in merged."
344 )
345 else:
346 assert path not in merged, (
347 f"M7 VIOLATED: ours-only deletion '{path}' still present in merged."
348 )
349
350 for path in theirs_changed - conflicts:
351 if path in theirs:
352 assert merged.get(path) == theirs[path], (
353 f"M7 VIOLATED: theirs-only change '{path}' not at theirs value in merged."
354 )
355 else:
356 assert path not in merged, (
357 f"M7 VIOLATED: theirs-only deletion '{path}' still present in merged."
358 )
359
360 @given(base=_manifest_strategy, common_changes=_manifest_strategy)
361 @settings(max_examples=200, suppress_health_check=[HealthCheck.too_slow])
362 def test_M8_convergent_modify_auto_resolves(
363 self, base: Manifest, common_changes: Manifest
364 ) -> None:
365 """M8: when both branches independently arrive at the same hash, no conflict fires
366 and the merged manifest contains the path at the agreed hash.
367
368 This is the canonical convergent-change invariant: identical outcomes are not
369 conflicts regardless of whether both sides changed the path.
370 """
371 shared_hash = _h("shared-content")
372 path = "shared.py"
373 base_with = dict(base)
374 base_with[path] = _h("original")
375 ours = dict(base_with)
376 ours[path] = shared_hash
377 theirs = dict(base_with)
378 theirs[path] = shared_hash
379
380 ours_changed = diff_snapshots(base_with, ours)
381 theirs_changed = diff_snapshots(base_with, theirs)
382
383 conflicts = detect_conflicts(ours_changed, theirs_changed, ours, theirs)
384 merged = apply_merge(base_with, ours, theirs, ours_changed, theirs_changed, conflicts)
385
386 # Convergent change: detect_conflicts must NOT flag 'path'.
387 assert path not in conflicts, (
388 f"M8 VIOLATED: convergent path '{path}' (same hash on both sides) "
389 f"wrongly reported as conflict."
390 )
391 # apply_merge must include 'path' at the agreed hash.
392 assert merged.get(path) == shared_hash, (
393 f"M8 VIOLATED: merged['{path}'] = {merged.get(path)!r}, "
394 f"expected {shared_hash!r}."
395 )
396
397 @given(base=_manifest_strategy, changes=_manifest_strategy)
398 @settings(max_examples=200, suppress_health_check=[HealthCheck.too_slow])
399 def test_M9_merge_ours_equals_theirs_is_convergent(
400 self, base: Manifest, changes: Manifest
401 ) -> None:
402 """M9: when ours == theirs, apply_merge produces ours exactly (no-conflict convergence)."""
403 ours = dict(changes)
404 theirs = dict(changes)
405
406 ours_changed = diff_snapshots(base, ours)
407 theirs_changed = diff_snapshots(base, theirs)
408 conflicts = detect_conflicts(ours_changed, theirs_changed, ours, theirs)
409
410 merged = apply_merge(base, ours, theirs, ours_changed, theirs_changed, conflicts)
411
412 # Every non-conflicting path must be at ours (== theirs) value.
413 for path in set(ours) | set(theirs):
414 if path in conflicts:
415 continue
416 expected = ours.get(path)
417 if expected is not None:
418 assert merged.get(path) == expected, (
419 f"M9 VIOLATED: ours == theirs but merged[{path!r}] != ours[{path!r}]."
420 )
421
422 @given(base=_manifest_strategy, ours=_manifest_strategy, theirs=_manifest_strategy)
423 @settings(max_examples=200, suppress_health_check=[HealthCheck.too_slow])
424 def test_M10_untouched_base_paths_preserved(
425 self, base: Manifest, ours: Manifest, theirs: Manifest
426 ) -> None:
427 """M10: files neither branch touched remain in merged at base value."""
428 ours_changed = diff_snapshots(base, ours)
429 theirs_changed = diff_snapshots(base, theirs)
430 conflicts = detect_conflicts(ours_changed, theirs_changed, ours, theirs)
431 merged = apply_merge(base, ours, theirs, ours_changed, theirs_changed, conflicts)
432
433 untouched = set(base) - ours_changed - theirs_changed
434 for path in untouched:
435 assert merged.get(path) == base[path], (
436 f"M10 VIOLATED: untouched path '{path}' changed value in merged."
437 )
438
439
440 # ===========================================================================
441 # L — LCA / find_merge_base invariants
442 # ===========================================================================
443
444
445 class TestLCAInvariantsL:
446 """Property-based invariants for find_merge_base (Lowest Common Ancestor)."""
447
448 @pytest.fixture
449 def repo(self, tmp_path: pathlib.Path) -> tuple[pathlib.Path, str]:
450 return _linear_repo(tmp_path)
451
452 def test_L1_lca_of_same_commit_is_itself(
453 self, tmp_path: pathlib.Path
454 ) -> None:
455 """L1: LCA(X, X) == X for any commit X."""
456 root, repo_id = _linear_repo(tmp_path)
457 c = _make_commit_lca(root, repo_id, {}, "root")
458 lca = find_merge_base(root, c, c)
459 assert lca == c, f"L1: LCA({c[:8]}, {c[:8]}) should be {c[:8]}, got {lca}"
460
461 def test_L2_L3_lca_is_ancestor_of_both(self, tmp_path: pathlib.Path) -> None:
462 """L2+L3: LCA(A,B) must be in the ancestry of both A and B."""
463 root, repo_id = _linear_repo(tmp_path)
464 c0 = _make_commit_lca(root, repo_id, {}, "base")
465 c1 = _make_commit_lca(root, repo_id, {"a.py": _h("a1")}, "ours", parent_id=c0)
466 c2 = _make_commit_lca(root, repo_id, {"b.py": _h("b1")}, "theirs", parent_id=c0)
467
468 lca = find_merge_base(root, c1, c2)
469 assert lca is not None, "LCA of two commits with common ancestor must exist"
470
471 from muse.core.store import read_commit
472
473 def _ancestors(start: str) -> set[str]:
474 visited: set[str] = set()
475 q = [start]
476 while q:
477 cid = q.pop()
478 if cid in visited:
479 continue
480 visited.add(cid)
481 commit = read_commit(root, cid)
482 if commit is None:
483 continue
484 if commit.parent_commit_id:
485 q.append(commit.parent_commit_id)
486 if commit.parent2_commit_id:
487 q.append(commit.parent2_commit_id)
488 return visited
489
490 assert lca in _ancestors(c1), f"L2: LCA {lca[:8]} not in ancestry of A {c1[:8]}"
491 assert lca in _ancestors(c2), f"L3: LCA {lca[:8]} not in ancestry of B {c2[:8]}"
492
493 def test_L4_lca_commutativity(self, tmp_path: pathlib.Path) -> None:
494 """L4: LCA(A, B) == LCA(B, A)."""
495 root, repo_id = _linear_repo(tmp_path)
496 c0 = _make_commit_lca(root, repo_id, {}, "base")
497 c1 = _make_commit_lca(root, repo_id, {"a.py": _h("a1")}, "c1", parent_id=c0)
498 c2 = _make_commit_lca(root, repo_id, {"b.py": _h("b1")}, "c2", parent_id=c0)
499
500 lca_ab = find_merge_base(root, c1, c2)
501 lca_ba = find_merge_base(root, c2, c1)
502 assert lca_ab == lca_ba, (
503 f"L4: LCA({c1[:8]}, {c2[:8]}) = {lca_ab}, "
504 f"LCA({c2[:8]}, {c1[:8]}) = {lca_ba} — not commutative"
505 )
506
507 def test_L5_if_a_is_ancestor_of_b_lca_is_a(self, tmp_path: pathlib.Path) -> None:
508 """L5: if A is ancestor of B, LCA(A, B) == A."""
509 root, repo_id = _linear_repo(tmp_path)
510 c0 = _make_commit_lca(root, repo_id, {}, "base")
511 c1 = _make_commit_lca(root, repo_id, {"a.py": _h("a1")}, "c1", parent_id=c0)
512 c2 = _make_commit_lca(root, repo_id, {"b.py": _h("b1")}, "c2", parent_id=c1)
513
514 lca = find_merge_base(root, c0, c2)
515 assert lca == c0, f"L5: c0 is ancestor of c2 so LCA should be c0, got {lca}"
516
517 lca2 = find_merge_base(root, c1, c2)
518 assert lca2 == c1, f"L5: c1 is ancestor of c2 so LCA should be c1, got {lca2}"
519
520 def test_L6_lca_for_merge_commit_topology(self, tmp_path: pathlib.Path) -> None:
521 """L6: diamond topology — LCA of the two branches is the fork point, not deeper."""
522 root, repo_id = _linear_repo(tmp_path)
523 base = _make_commit_lca(root, repo_id, {}, "base")
524 a = _make_commit_lca(root, repo_id, {"a.py": _h("a")}, "a", parent_id=base)
525 b = _make_commit_lca(root, repo_id, {"b.py": _h("b")}, "b", parent_id=base)
526 # Merge commit of a and b
527 m = _make_commit_lca(
528 root, repo_id, {"a.py": _h("a"), "b.py": _h("b")}, "merge",
529 parent_id=a, parent2_id=b
530 )
531
532 # LCA of a and m should be a (m is a descendant of a).
533 assert find_merge_base(root, a, m) == a, "L6a"
534 # LCA of b and m should be b.
535 assert find_merge_base(root, b, m) == b, "L6b"
536 # LCA of base and m should be base.
537 assert find_merge_base(root, base, m) == base, "L6c"
538
539
540 # ===========================================================================
541 # SI — Snapshot integrity invariants
542 # ===========================================================================
543
544
545 class TestSnapshotIntegritySI:
546 """After every merge, every object_id in the snapshot must be in the store."""
547
548 def _object_exists(self, root: pathlib.Path, obj_id: str) -> bool:
549 """Return True if obj_id is readable from the object store."""
550 from muse.core.object_store import read_object
551 return read_object(root, obj_id) is not None
552
553 def test_SI1_fast_forward_snapshot_objects_all_present(
554 self, tmp_path: pathlib.Path
555 ) -> None:
556 """SI1: after fast-forward, every object in the new snapshot is in the store."""
557 from muse.core.object_store import write_object
558 from muse.core.store import read_commit, read_snapshot
559
560 root, repo_id = _linear_repo(tmp_path)
561 (root / ".muse" / "HEAD").write_text("ref: refs/heads/main", encoding="utf-8")
562
563 # Write real objects to the store.
564 contents = {f"file_{i}.py": f"x = {i}\n".encode() for i in range(10)}
565 manifest: Manifest = {}
566 for path, data in contents.items():
567 obj_id = hashlib.sha256(data).hexdigest()
568 write_object(root, obj_id, data)
569 manifest[path] = obj_id
570
571 base_c = _make_commit_lca(root, repo_id, {}, "base")
572 # Write feat branch with the manifest.
573 (root / ".muse" / "refs" / "heads" / "main").write_text(base_c, encoding="utf-8")
574 feat_c = _make_commit_lca(root, repo_id, manifest, "feat", parent_id=base_c)
575 (root / ".muse" / "refs" / "heads" / "feat").write_text(feat_c, encoding="utf-8")
576
577 # Run merge (fast-forward).
578 from tests.cli_test_helper import CliRunner
579 runner = CliRunner()
580 env = {"MUSE_REPO_ROOT": str(root)}
581 runner.invoke(None, ["merge", "--force", "feat"], env=env, catch_exceptions=False)
582
583 # Verify every object in main's snapshot is in the store.
584 main_head = (root / ".muse" / "refs" / "heads" / "main").read_text().strip()
585 commit = read_commit(root, main_head)
586 assert commit is not None
587 snap = read_snapshot(root, commit.snapshot_id)
588 assert snap is not None
589
590 for path, obj_id in snap.manifest.items():
591 assert self._object_exists(root, obj_id), (
592 f"SI1 VIOLATED: blob {obj_id[:8]} for '{path}' missing from store "
593 f"after fast-forward merge."
594 )
595
596 def test_SI2_apply_merge_output_all_hashes_from_inputs(
597 self, tmp_path: pathlib.Path
598 ) -> None:
599 """SI2: every hash in apply_merge output came from base, ours, or theirs.
600
601 This ensures apply_merge never invents a hash. Any invented hash would
602 reference a non-existent object and corrupt the repo on checkout.
603 """
604 base = {"a.py": _h("a-base"), "b.py": _h("b-base"), "c.py": _h("c-base")}
605 ours = {"a.py": _h("a-ours"), "b.py": _h("b-base"), "d.py": _h("d-ours")}
606 theirs = {"a.py": _h("a-theirs"), "c.py": _h("c-theirs"), "e.py": _h("e-theirs")}
607
608 all_known_hashes = (
609 set(base.values()) | set(ours.values()) | set(theirs.values())
610 )
611
612 ours_changed = diff_snapshots(base, ours)
613 theirs_changed = diff_snapshots(base, theirs)
614 conflicts = detect_conflicts(ours_changed, theirs_changed, ours, theirs)
615 merged = apply_merge(base, ours, theirs, ours_changed, theirs_changed, conflicts)
616
617 for path, obj_id in merged.items():
618 assert obj_id in all_known_hashes, (
619 f"SI2 VIOLATED: apply_merge produced unknown hash {obj_id[:8]} for '{path}'. "
620 f"Invented hashes corrupt the object store."
621 )
622
623 @given(base=_manifest_strategy, ours=_manifest_strategy, theirs=_manifest_strategy)
624 @settings(max_examples=300, suppress_health_check=[HealthCheck.too_slow])
625 def test_SI3_all_merged_hashes_come_from_known_inputs(
626 self, base: Manifest, ours: Manifest, theirs: Manifest
627 ) -> None:
628 """SI3: property version of SI2 — apply_merge never generates new hashes."""
629 all_known = set(base.values()) | set(ours.values()) | set(theirs.values())
630
631 ours_changed = diff_snapshots(base, ours)
632 theirs_changed = diff_snapshots(base, theirs)
633 conflicts = detect_conflicts(ours_changed, theirs_changed, ours, theirs)
634 merged = apply_merge(base, ours, theirs, ours_changed, theirs_changed, conflicts)
635
636 for path, obj_id in merged.items():
637 assert obj_id in all_known, (
638 f"SI3 VIOLATED: merged[{path!r}] = {obj_id[:8]} was not in any input manifest."
639 )
640
641
642 # ===========================================================================
643 # DT — Determinism tests
644 # ===========================================================================
645
646
647 class TestDeterminismDT:
648 """Snapshot IDs and commit IDs must be deterministic across calls and dict orderings."""
649
650 def test_DT1_snapshot_id_independent_of_dict_insertion_order(self) -> None:
651 """DT1: compute_snapshot_id produces the same ID regardless of dict key order."""
652 from muse.core.snapshot import compute_snapshot_id
653
654 manifest = {f"file_{i:03d}.py": _h(f"content-{i}") for i in range(50)}
655
656 # Build the same dict in reverse insertion order.
657 manifest_reversed: Manifest = {}
658 for k in reversed(list(manifest.keys())):
659 manifest_reversed[k] = manifest[k]
660
661 id_forward = compute_snapshot_id(manifest)
662 id_reversed = compute_snapshot_id(manifest_reversed)
663 assert id_forward == id_reversed, (
664 "DT1 VIOLATED: compute_snapshot_id is sensitive to dict insertion order. "
665 "Two repos with the same content would get different snapshot IDs."
666 )
667
668 def test_DT2_snapshot_id_is_stable_across_calls(self) -> None:
669 """DT2: the same manifest always produces the same snapshot_id."""
670 from muse.core.snapshot import compute_snapshot_id
671
672 manifest = {"app.py": _h("app"), "README.md": _h("readme")}
673 ids = {compute_snapshot_id(manifest) for _ in range(100)}
674 assert len(ids) == 1, "DT2 VIOLATED: compute_snapshot_id is not deterministic."
675
676 def test_DT3_empty_manifest_has_stable_id(self) -> None:
677 """DT3: the empty manifest always has the same snapshot_id."""
678 from muse.core.snapshot import compute_snapshot_id
679 ids = {compute_snapshot_id({}) for _ in range(50)}
680 assert len(ids) == 1, "DT3: empty manifest snapshot_id is not stable."
681
682 def test_DT4_commit_id_stable_for_same_inputs(self) -> None:
683 """DT4: compute_commit_id with the same inputs always returns the same ID."""
684 from muse.core.snapshot import compute_commit_id
685 kwargs = dict(
686 parent_ids=["abc" * 21 + "a"],
687 snapshot_id=_h("snap"),
688 message="test commit",
689 committed_at_iso="2026-01-01T00:00:00+00:00",
690 )
691 ids = {compute_commit_id(**kwargs) for _ in range(50)}
692 assert len(ids) == 1, "DT4: compute_commit_id is not deterministic."
693
694 @given(manifest=_manifest_strategy)
695 @settings(max_examples=200)
696 def test_DT5_snapshot_id_property_stable(self, manifest: Manifest) -> None:
697 """DT5: for any random manifest, snapshot_id is the same when called twice."""
698 from muse.core.snapshot import compute_snapshot_id
699 assert compute_snapshot_id(manifest) == compute_snapshot_id(manifest)
700
701 @given(manifest=_manifest_strategy)
702 @settings(max_examples=200)
703 def test_DT6_snapshot_id_order_independent_property(self, manifest: Manifest) -> None:
704 """DT6: for any manifest, shuffling key insertion order doesn't change the ID."""
705 from muse.core.snapshot import compute_snapshot_id
706 keys = list(manifest.keys())
707 # Build a copy with reversed key order
708 shuffled = {k: manifest[k] for k in reversed(keys)}
709 assert compute_snapshot_id(manifest) == compute_snapshot_id(shuffled), (
710 "DT6 VIOLATED: snapshot_id changed when dict key order changed."
711 )
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