gabriel / muse public
test_stress_graph.py python
277 lines 10.1 KB
Raw
sha256:1900655993c83c4107067375548a7be823e471d2515830842f1a12cba4bd3cdf fix: unified object store migration — idempotent writes, JS… Sonnet 4.6 minor ⚠ breaking 29 days ago
1 """Stress tests for the commit DAG and merge-base algorithm.
2
3 Exercises:
4 - Linear chains of 500 commits.
5 - Wide fan-out / fan-in (octopus merge shapes).
6 - Criss-cross merge (ambiguous LCA — should still find *some* ancestor).
7 - Independent histories (no common ancestor → None).
8 - find_merge_base symmetry: find_merge_base(a, b) == find_merge_base(b, a).
9 - Missing commit handles gracefully (None parent pointers in corrupt graphs).
10 - Diamond topology: four-node diamond always finds the root.
11 - Double diamond: two diamonds chained together.
12 - Long parallel branches that converge at a single point.
13 """
14
15 import datetime
16 import pathlib
17
18 import pytest
19
20 from muse.core.types import fake_id
21 from muse.core.paths import muse_dir
22 from muse.core.merge_engine import find_merge_base
23 from muse.core.ids import hash_commit as compute_commit_id, hash_snapshot as compute_snapshot_id
24 from muse.core.store import CommitRecord, write_commit
25
26
27 # ---------------------------------------------------------------------------
28 # Helpers
29 # ---------------------------------------------------------------------------
30
31 _SNAP_ID: str = compute_snapshot_id({})
32 _BASE_TS: datetime.datetime = datetime.datetime(2026, 1, 1, tzinfo=datetime.timezone.utc)
33
34
35 def _write(
36 root: pathlib.Path,
37 label: str,
38 parent: str | None = None,
39 parent2: str | None = None,
40 ) -> str:
41 """Write a commit with a real content-addressed ID. Returns the commit_id."""
42 parent_ids = [p for p in (parent, parent2) if p is not None]
43 cid = compute_commit_id(
44 parent_ids=parent_ids,
45 snapshot_id=_SNAP_ID,
46 message=label,
47 committed_at_iso=_BASE_TS.isoformat(),
48 )
49 write_commit(root, CommitRecord(
50 commit_id=cid,
51 branch="main",
52 snapshot_id=_SNAP_ID,
53 message=label,
54 committed_at=_BASE_TS,
55 parent_commit_id=parent,
56 parent2_commit_id=parent2,
57 ))
58 return cid
59
60
61 @pytest.fixture
62 def repo(tmp_path: pathlib.Path) -> pathlib.Path:
63 dot_muse = muse_dir(tmp_path)
64 (dot_muse / "commits").mkdir(parents=True)
65 (dot_muse / "refs" / "heads").mkdir(parents=True)
66 return tmp_path
67
68
69 # ---------------------------------------------------------------------------
70 # Linear chain
71 # ---------------------------------------------------------------------------
72
73
74 class TestLinearChain:
75 def test_chain_of_500_finds_base(self, repo: pathlib.Path) -> None:
76 """LCA of two commits on a 500-long linear chain is the shared ancestor."""
77 prev: str | None = None
78 ids: list[str] = []
79 for i in range(500):
80 cid = _write(repo, f"c{i:04d}", prev)
81 ids.append(cid)
82 prev = cid
83
84 # Branch off at the commit at index 100
85 branch_tip_id = _write(repo, "branch-tip", ids[100])
86
87 base = find_merge_base(repo, ids[499], branch_tip_id)
88 assert base == ids[100]
89
90 def test_lca_of_adjacent_commits_is_parent(self, repo: pathlib.Path) -> None:
91 root_id = _write(repo, "root")
92 child_id = _write(repo, "child", root_id)
93 assert find_merge_base(repo, root_id, child_id) == root_id
94 assert find_merge_base(repo, child_id, root_id) == root_id
95
96 def test_long_chain_lca_symmetry(self, repo: pathlib.Path) -> None:
97 """find_merge_base(a, b) == find_merge_base(b, a) on a long chain."""
98 prev: str | None = None
99 ids: list[str] = []
100 for i in range(100):
101 cid = _write(repo, f"n{i:03d}", prev)
102 ids.append(cid)
103 prev = cid
104
105 left_id = _write(repo, "left", ids[50])
106 right_id = _write(repo, "right", ids[50])
107
108 assert find_merge_base(repo, left_id, right_id) == ids[50]
109 assert find_merge_base(repo, right_id, left_id) == ids[50]
110
111 def test_same_commit_returns_itself(self, repo: pathlib.Path) -> None:
112 solo_id = _write(repo, "solo")
113 assert find_merge_base(repo, solo_id, solo_id) == solo_id
114
115 def test_one_is_ancestor_of_other(self, repo: pathlib.Path) -> None:
116 """When A is a direct ancestor of B, LCA is A."""
117 prev: str | None = None
118 ids: list[str] = []
119 for i in range(20):
120 cid = _write(repo, f"x{i:02d}", prev)
121 ids.append(cid)
122 prev = cid
123 assert find_merge_base(repo, ids[0], ids[19]) == ids[0]
124 assert find_merge_base(repo, ids[19], ids[0]) == ids[0]
125
126
127 # ---------------------------------------------------------------------------
128 # Diamond topology
129 # ---------------------------------------------------------------------------
130
131
132 class TestDiamondTopology:
133 def test_simple_diamond(self, repo: pathlib.Path) -> None:
134 """
135 root
136 / \\
137 L R
138 \\ /
139 M (merge commit, not relevant here — just find LCA of L and R)
140 """
141 root_id = _write(repo, "root")
142 l_id = _write(repo, "L", root_id)
143 r_id = _write(repo, "R", root_id)
144 assert find_merge_base(repo, l_id, r_id) == root_id
145
146 def test_double_diamond(self, repo: pathlib.Path) -> None:
147 """
148 A
149 / \\
150 B C
151 \\ /
152 D
153 / \\
154 E F
155 \\ /
156 G
157 LCA(E, F) should be D.
158 """
159 a_id = _write(repo, "A")
160 b_id = _write(repo, "B", a_id)
161 c_id = _write(repo, "C", a_id)
162 d_id = _write(repo, "D", b_id, c_id)
163 e_id = _write(repo, "E", d_id)
164 f_id = _write(repo, "F", d_id)
165 assert find_merge_base(repo, e_id, f_id) == d_id
166
167 def test_criss_cross_merge(self, repo: pathlib.Path) -> None:
168 """
169 Criss-cross: A and B are each other's ancestor via two different merge paths.
170 X → L1 → M1(L1,R1)
171 X → R1 → M2(R1,L1)
172 LCA of M1 and M2 should be either L1 or R1 (both are valid LCAs).
173 The algorithm must not return None or crash.
174 """
175 x_id = _write(repo, "X")
176 l1_id = _write(repo, "L1", x_id)
177 r1_id = _write(repo, "R1", x_id)
178 m1_id = _write(repo, "M1", l1_id, r1_id)
179 m2_id = _write(repo, "M2", r1_id, l1_id)
180
181 base = find_merge_base(repo, m1_id, m2_id)
182 # Any of X, L1, R1 is a valid common ancestor; None is not acceptable.
183 assert base is not None
184 assert base in {x_id, l1_id, r1_id}
185
186 def test_octopus_three_branch_fan_in(self, repo: pathlib.Path) -> None:
187 """Three branches that all diverged from the same root."""
188 root_id = _write(repo, "root")
189 ba_id = _write(repo, "branch-a", root_id)
190 bb_id = _write(repo, "branch-b", root_id)
191 bc_id = _write(repo, "branch-c", root_id)
192
193 assert find_merge_base(repo, ba_id, bb_id) == root_id
194 assert find_merge_base(repo, ba_id, bc_id) == root_id
195 assert find_merge_base(repo, bb_id, bc_id) == root_id
196
197
198 # ---------------------------------------------------------------------------
199 # Independent histories
200 # ---------------------------------------------------------------------------
201
202
203 class TestDisjointHistories:
204 def test_no_common_ancestor_returns_none(self, repo: pathlib.Path) -> None:
205 island_a_id = _write(repo, "island-a")
206 island_b_id = _write(repo, "island-b")
207 assert find_merge_base(repo, island_a_id, island_b_id) is None
208
209 def test_long_independent_chains_return_none(self, repo: pathlib.Path) -> None:
210 prev_a: str | None = None
211 prev_b: str | None = None
212 last_a = last_b = ""
213 for i in range(20):
214 last_a = _write(repo, f"a{i:02d}", prev_a)
215 last_b = _write(repo, f"b{i:02d}", prev_b)
216 prev_a = last_a
217 prev_b = last_b
218 assert find_merge_base(repo, last_a, last_b) is None
219
220 def test_missing_commit_id_graceful(self, repo: pathlib.Path) -> None:
221 """Asking for an LCA where one commit doesn't exist should return None, not raise."""
222 real_id = _write(repo, "real")
223 result = find_merge_base(repo, real_id, fake_id("ghost-commit-that-does-not-exist"))
224 # The ghost has no ancestors, so no common ancestor found.
225 assert result is None
226
227
228 # ---------------------------------------------------------------------------
229 # Ancestor-set correctness
230 # ---------------------------------------------------------------------------
231
232
233 class TestAncestorCorrectness:
234 def test_merge_commit_has_both_parents_as_ancestors(self, repo: pathlib.Path) -> None:
235 root_id = _write(repo, "root")
236 a_id = _write(repo, "A", root_id)
237 b_id = _write(repo, "B", root_id)
238 merge_id = _write(repo, "merge", a_id, b_id)
239 feature_id = _write(repo, "feature", a_id)
240
241 # LCA of feature and merge: feature branched from A, merge contains A.
242 # So A is the common ancestor.
243 base = find_merge_base(repo, feature_id, merge_id)
244 assert base == a_id
245
246 def test_wide_history_with_shared_root(self, repo: pathlib.Path) -> None:
247 """100 branches diverging from a shared root, pairwise LCA is root."""
248 root_id = _write(repo, "root")
249 branch_ids = [_write(repo, f"br{i:03d}", root_id) for i in range(50)]
250
251 # Check a sampling of pairs
252 for i in range(0, 50, 10):
253 for j in range(i + 1, 50, 10):
254 assert find_merge_base(repo, branch_ids[i], branch_ids[j]) == root_id
255
256 def test_deep_branch_divergence(self, repo: pathlib.Path) -> None:
257 """Branches diverge at root, each has 50 commits. LCA is root."""
258 root_id = _write(repo, "root")
259 prev_a: str | None = root_id
260 prev_b: str | None = root_id
261 last_a = last_b = root_id
262 for i in range(50):
263 last_a = _write(repo, f"da{i:02d}", prev_a)
264 last_b = _write(repo, f"db{i:02d}", prev_b)
265 prev_a = last_a
266 prev_b = last_b
267
268 assert find_merge_base(repo, last_a, last_b) == root_id
269
270 def test_multiple_merge_bases_chain(self, repo: pathlib.Path) -> None:
271 """A → B → C; branch D from B. LCA of C and D is B."""
272 a_id = _write(repo, "A")
273 b_id = _write(repo, "B", a_id)
274 c_id = _write(repo, "C", b_id)
275 d_id = _write(repo, "D", b_id)
276 assert find_merge_base(repo, c_id, d_id) == b_id
277 assert find_merge_base(repo, d_id, c_id) == b_id
File History 1 commit
sha256:1900655993c83c4107067375548a7be823e471d2515830842f1a12cba4bd3cdf fix: unified object store migration — idempotent writes, JS… Sonnet 4.6 minor ⚠ 29 days ago