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