gabriel / muse public
test_phase2_bfs_migration.py python
445 lines 17.7 KB
Raw
sha256:51ce277f663e01a43eaffbe77509b1de7ac2d4251b55d23306304bcdeb92c90d feat(pack): delta-encode snapshots in MPackBundle wire format Sonnet 4.6 minor ⚠ breaking 121 days ago
1 """TDD Phase 2 — migrate inline BFS/DFS implementations to walk_dag / iter_ancestors.
2
3 Structural tests FAIL now (inline patterns still present); PASS after migration.
4 Behavioral tests PASS before and after (pin the public contract).
5
6 Target sites
7 ------------
8 bisect._ancestors — DFS list[str] oldest-first
9 bisect._reachable_from_good — DFS set[str]
10 branch._commit_ancestors — DFS set[str]
11 pack.build_mpack BFS block — BFS with have-set exclusion
12 pack.collect_object_ids BFS block — BFS with have-set exclusion
13 _query.walk_commits_bfs — BFS with stop_at_commit_id
14 midi/_query.walk_commits_for_track — linear first-parent walk
15 """
16
17 from __future__ import annotations
18
19 import datetime
20 import inspect
21 import json
22 import pathlib
23
24 import pytest
25
26 from muse.core.store import CommitRecord, SnapshotRecord, write_commit, write_snapshot
27 from muse.core.snapshot import compute_commit_id, compute_snapshot_id
28 from muse.core.paths import muse_dir
29
30 _BASE_DT = datetime.datetime(2026, 1, 1, tzinfo=datetime.timezone.utc)
31
32
33 # ---------------------------------------------------------------------------
34 # Shared helpers (same pattern as test_core_graph.py)
35 # ---------------------------------------------------------------------------
36
37 def _make_repo(tmp_path: pathlib.Path) -> pathlib.Path:
38 dot_muse = muse_dir(tmp_path)
39 for d in ("objects", "commits", "snapshots", "refs/heads"):
40 (dot_muse / d).mkdir(parents=True, exist_ok=True)
41 (dot_muse / "repo.json").write_text(json.dumps({"repo_id": "test-repo"}))
42 (dot_muse / "HEAD").write_text("ref: refs/heads/main\n")
43 return tmp_path
44
45
46 def _write_commit(
47 repo: pathlib.Path,
48 message: str = "commit",
49 parent: str | None = None,
50 parent2: str | None = None,
51 author: str = "Author",
52 dt: datetime.datetime = _BASE_DT,
53 ) -> str:
54 snap_id = compute_snapshot_id({})
55 write_snapshot(repo, SnapshotRecord(snapshot_id=snap_id, manifest={}))
56 parent_ids = [p for p in (parent, parent2) if p is not None]
57 commit_id = compute_commit_id(
58 parent_ids=parent_ids,
59 snapshot_id=snap_id,
60 message=message,
61 committed_at_iso=dt.isoformat(),
62 author=author,
63 )
64 write_commit(
65 repo,
66 CommitRecord(
67 repo_id="test-repo",
68 commit_id=commit_id,
69 branch="main",
70 snapshot_id=snap_id,
71 message=message,
72 committed_at=dt,
73 parent_commit_id=parent,
74 author=author,
75 parent2_commit_id=parent2,
76 ),
77 )
78 return commit_id
79
80
81 def _no_inline_bfs(source: str) -> bool:
82 """True when source has no standalone BFS queue patterns."""
83 return "while queue:" not in source and "queue.popleft()" not in source and "queue.pop()" not in source
84
85
86 # ---------------------------------------------------------------------------
87 # bisect._ancestors
88 # ---------------------------------------------------------------------------
89
90 class TestBisectAncestors:
91 def _fn(self):
92 from muse.core import bisect
93 return bisect._ancestors
94
95 def test_structural_no_inline_bfs(self) -> None:
96 """_ancestors must not use an inline BFS/DFS queue after migration."""
97 src = inspect.getsource(self._fn())
98 assert _no_inline_bfs(src), (
99 "bisect._ancestors still uses an inline queue — migrate to ancestor_ids"
100 )
101
102 def test_linear_chain_all_ancestors_returned(self, tmp_path: pathlib.Path) -> None:
103 repo = _make_repo(tmp_path)
104 root = _write_commit(repo, "root")
105 mid = _write_commit(repo, "mid", parent=root)
106 tip = _write_commit(repo, "tip", parent=mid)
107 result = self._fn()(repo, tip)
108 assert set(result) == {root, mid, tip}
109
110 def test_returns_oldest_first(self, tmp_path: pathlib.Path) -> None:
111 repo = _make_repo(tmp_path)
112 root = _write_commit(repo, "root")
113 mid = _write_commit(repo, "mid", parent=root)
114 tip = _write_commit(repo, "tip", parent=mid)
115 result = self._fn()(repo, tip)
116 # oldest-first: root then mid then tip
117 assert result.index(root) < result.index(mid) < result.index(tip)
118
119 def test_single_commit(self, tmp_path: pathlib.Path) -> None:
120 repo = _make_repo(tmp_path)
121 cid = _write_commit(repo, "solo")
122 assert self._fn()(repo, cid) == [cid]
123
124 def test_diamond_no_duplicates(self, tmp_path: pathlib.Path) -> None:
125 repo = _make_repo(tmp_path)
126 d = _write_commit(repo, "D")
127 b = _write_commit(repo, "B", parent=d)
128 c = _write_commit(repo, "C", parent=d)
129 a = _write_commit(repo, "A", parent=b, parent2=c)
130 result = self._fn()(repo, a)
131 assert result.count(d) == 1
132 assert set(result) == {a, b, c, d}
133
134
135 # ---------------------------------------------------------------------------
136 # bisect._reachable_from_good
137 # ---------------------------------------------------------------------------
138
139 class TestBisectReachableFromGood:
140 def _fn(self):
141 from muse.core import bisect
142 return bisect._reachable_from_good
143
144 def test_structural_no_inline_bfs(self) -> None:
145 """_reachable_from_good must not use an inline BFS/DFS queue."""
146 src = inspect.getsource(self._fn())
147 assert _no_inline_bfs(src), (
148 "bisect._reachable_from_good still uses an inline queue — migrate to ancestor_ids"
149 )
150
151 def test_single_good_includes_ancestors(self, tmp_path: pathlib.Path) -> None:
152 repo = _make_repo(tmp_path)
153 root = _write_commit(repo, "root")
154 mid = _write_commit(repo, "mid", parent=root)
155 tip = _write_commit(repo, "tip", parent=mid)
156 result = self._fn()(repo, [tip])
157 assert result == {tip, mid, root}
158
159 def test_multi_source_union(self, tmp_path: pathlib.Path) -> None:
160 repo = _make_repo(tmp_path)
161 shared = _write_commit(repo, "shared")
162 a = _write_commit(repo, "a", parent=shared)
163 b = _write_commit(repo, "b", parent=shared)
164 result = self._fn()(repo, [a, b])
165 assert result == {a, b, shared}
166
167 def test_shared_ancestor_once(self, tmp_path: pathlib.Path) -> None:
168 repo = _make_repo(tmp_path)
169 shared = _write_commit(repo, "shared")
170 a = _write_commit(repo, "a", parent=shared)
171 b = _write_commit(repo, "b", parent=shared)
172 result = self._fn()(repo, [a, b])
173 assert shared in result
174
175 def test_empty_good_ids(self, tmp_path: pathlib.Path) -> None:
176 repo = _make_repo(tmp_path)
177 result = self._fn()(repo, [])
178 assert result == set()
179
180
181 # ---------------------------------------------------------------------------
182 # branch._commit_ancestors
183 # ---------------------------------------------------------------------------
184
185 class TestBranchCommitAncestors:
186 def _fn(self):
187 from muse.cli.commands import branch as branch_module
188 return branch_module._commit_ancestors
189
190 def test_structural_no_inline_bfs(self) -> None:
191 """_commit_ancestors must not use an inline BFS/DFS queue."""
192 src = inspect.getsource(self._fn())
193 assert _no_inline_bfs(src), (
194 "branch._commit_ancestors still uses an inline queue — migrate to ancestor_ids"
195 )
196
197 def test_returns_set_including_self(self, tmp_path: pathlib.Path) -> None:
198 repo = _make_repo(tmp_path)
199 root = _write_commit(repo, "root")
200 tip = _write_commit(repo, "tip", parent=root)
201 result = self._fn()(repo, tip)
202 assert tip in result
203 assert root in result
204 assert isinstance(result, set)
205
206 def test_diamond_no_duplicates(self, tmp_path: pathlib.Path) -> None:
207 repo = _make_repo(tmp_path)
208 d = _write_commit(repo, "D")
209 b = _write_commit(repo, "B", parent=d)
210 c = _write_commit(repo, "C", parent=d)
211 a = _write_commit(repo, "A", parent=b, parent2=c)
212 result = self._fn()(repo, a)
213 assert result == {a, b, c, d}
214
215 def test_single_commit(self, tmp_path: pathlib.Path) -> None:
216 repo = _make_repo(tmp_path)
217 cid = _write_commit(repo, "solo")
218 assert self._fn()(repo, cid) == {cid}
219
220
221 # ---------------------------------------------------------------------------
222 # pack.build_mpack BFS block
223 # ---------------------------------------------------------------------------
224
225 class TestPackBuildMpackBFS:
226 def test_structural_no_inline_bfs(self) -> None:
227 """build_mpack must not contain its own inline BFS queue."""
228 from muse.core import pack as pack_module
229 src = inspect.getsource(pack_module.build_mpack)
230 assert _no_inline_bfs(src), (
231 "pack.build_mpack still has an inline BFS queue — migrate to iter_ancestors"
232 )
233
234 def test_have_set_excludes_old_commits(self, tmp_path: pathlib.Path) -> None:
235 """build_mpack with have=[old] must not include old commit in bundle."""
236 from muse.core.pack import build_mpack
237 from muse.core.object_store import write_object
238
239 repo = _make_repo(tmp_path)
240 old_content = b"old-object"
241 old_oid = "sha256:" + __import__("hashlib").sha256(old_content).hexdigest()
242 write_object(repo, old_oid, old_content)
243
244 old_snap_id = compute_snapshot_id({"f.txt": old_oid})
245 write_snapshot(repo, SnapshotRecord(snapshot_id=old_snap_id, manifest={"f.txt": old_oid}))
246
247 old_cid = compute_commit_id(
248 parent_ids=[],
249 snapshot_id=old_snap_id,
250 message="old",
251 committed_at_iso=_BASE_DT.isoformat(),
252 author="A",
253 )
254 write_commit(repo, CommitRecord(
255 repo_id="test-repo", commit_id=old_cid, branch="main",
256 snapshot_id=old_snap_id, message="old",
257 committed_at=_BASE_DT, author="A",
258 ))
259
260 new_content = b"new-object"
261 new_oid = "sha256:" + __import__("hashlib").sha256(new_content).hexdigest()
262 write_object(repo, new_oid, new_content)
263
264 new_snap_id = compute_snapshot_id({"g.txt": new_oid})
265 write_snapshot(repo, SnapshotRecord(snapshot_id=new_snap_id, manifest={"g.txt": new_oid}))
266
267 new_cid = compute_commit_id(
268 parent_ids=[old_cid],
269 snapshot_id=new_snap_id,
270 message="new",
271 committed_at_iso=_BASE_DT.isoformat(),
272 author="A",
273 )
274 write_commit(repo, CommitRecord(
275 repo_id="test-repo", commit_id=new_cid, branch="main",
276 snapshot_id=new_snap_id, message="new",
277 committed_at=_BASE_DT, parent_commit_id=old_cid, author="A",
278 ))
279
280 bundle = build_mpack(repo, [new_cid], have=[old_cid])
281 sent_ids = {c["commit_id"] for c in bundle["commits"]}
282 assert new_cid in sent_ids
283 assert old_cid not in sent_ids
284
285
286 # ---------------------------------------------------------------------------
287 # pack.collect_object_ids BFS block
288 # ---------------------------------------------------------------------------
289
290 class TestPackCollectObjectIds:
291 def test_structural_no_inline_bfs(self) -> None:
292 """collect_object_ids must not contain its own inline BFS queue."""
293 from muse.core import pack as pack_module
294 src = inspect.getsource(pack_module.collect_object_ids)
295 assert _no_inline_bfs(src), (
296 "pack.collect_object_ids still has an inline BFS queue — migrate to iter_ancestors"
297 )
298
299 def test_have_excludes_known_objects(self, tmp_path: pathlib.Path) -> None:
300 """Objects reachable only via have-commits are excluded from result."""
301 from muse.core.pack import collect_object_ids
302 from muse.core.object_store import write_object
303
304 repo = _make_repo(tmp_path)
305
306 old_content = b"old"
307 old_oid = "sha256:" + __import__("hashlib").sha256(old_content).hexdigest()
308 write_object(repo, old_oid, old_content)
309 old_snap_id = compute_snapshot_id({"a.txt": old_oid})
310 write_snapshot(repo, SnapshotRecord(snapshot_id=old_snap_id, manifest={"a.txt": old_oid}))
311 old_cid = compute_commit_id(
312 parent_ids=[], snapshot_id=old_snap_id,
313 message="old", committed_at_iso=_BASE_DT.isoformat(), author="A",
314 )
315 write_commit(repo, CommitRecord(
316 repo_id="test-repo", commit_id=old_cid, branch="main",
317 snapshot_id=old_snap_id, message="old",
318 committed_at=_BASE_DT, author="A",
319 ))
320
321 new_content = b"new"
322 new_oid = "sha256:" + __import__("hashlib").sha256(new_content).hexdigest()
323 write_object(repo, new_oid, new_content)
324 new_snap_id = compute_snapshot_id({"b.txt": new_oid})
325 write_snapshot(repo, SnapshotRecord(snapshot_id=new_snap_id, manifest={"b.txt": new_oid}))
326 new_cid = compute_commit_id(
327 parent_ids=[old_cid], snapshot_id=new_snap_id,
328 message="new", committed_at_iso=_BASE_DT.isoformat(), author="A",
329 )
330 write_commit(repo, CommitRecord(
331 repo_id="test-repo", commit_id=new_cid, branch="main",
332 snapshot_id=new_snap_id, message="new",
333 committed_at=_BASE_DT, parent_commit_id=old_cid, author="A",
334 ))
335
336 result = collect_object_ids(repo, [new_cid], have=[old_cid])
337 assert new_oid in result
338 assert old_oid not in result
339
340
341 # ---------------------------------------------------------------------------
342 # code._query.walk_commits_bfs
343 # ---------------------------------------------------------------------------
344
345 class TestWalkCommitsBfs:
346 def _fn(self):
347 from muse.plugins.code import _query
348 return _query.walk_commits_bfs
349
350 def test_structural_no_inline_bfs(self) -> None:
351 """walk_commits_bfs must not use an inline BFS queue after migration."""
352 src = inspect.getsource(self._fn())
353 assert _no_inline_bfs(src), (
354 "code._query.walk_commits_bfs still has an inline queue — migrate to iter_ancestors"
355 )
356
357 def test_returns_all_commits_no_stop(self, tmp_path: pathlib.Path) -> None:
358 repo = _make_repo(tmp_path)
359 root = _write_commit(repo, "root")
360 mid = _write_commit(repo, "mid", parent=root)
361 tip = _write_commit(repo, "tip", parent=mid)
362 commits, truncated = self._fn()(repo, tip)
363 assert {c.commit_id for c in commits} == {root, mid, tip}
364 assert truncated is False
365
366 def test_stop_at_commit_id_excludes_boundary(self, tmp_path: pathlib.Path) -> None:
367 repo = _make_repo(tmp_path)
368 root = _write_commit(repo, "root")
369 mid = _write_commit(repo, "mid", parent=root)
370 tip = _write_commit(repo, "tip", parent=mid)
371 commits, truncated = self._fn()(repo, tip, stop_at_commit_id=mid)
372 ids = {c.commit_id for c in commits}
373 assert tip in ids
374 assert mid not in ids
375 assert root not in ids
376
377 def test_max_commits_returns_truncated_true(self, tmp_path: pathlib.Path) -> None:
378 repo = _make_repo(tmp_path)
379 prev = None
380 for i in range(5):
381 prev = _write_commit(repo, f"c{i}", parent=prev)
382 tip = prev
383 commits, truncated = self._fn()(repo, tip, max_commits=3)
384 assert len(commits) <= 3
385 assert truncated is True
386
387 def test_merge_commit_visits_both_parents(self, tmp_path: pathlib.Path) -> None:
388 repo = _make_repo(tmp_path)
389 root = _write_commit(repo, "root")
390 left = _write_commit(repo, "left", parent=root)
391 right = _write_commit(repo, "right", parent=root)
392 merge = _write_commit(repo, "merge", parent=left, parent2=right)
393 commits, _ = self._fn()(repo, merge)
394 ids = {c.commit_id for c in commits}
395 assert ids == {merge, left, right, root}
396
397
398 # ---------------------------------------------------------------------------
399 # midi._query.walk_commits_for_track (first-parent walk)
400 # ---------------------------------------------------------------------------
401
402 class TestWalkCommitsForTrack:
403 def _fn(self):
404 from muse.plugins.midi import _query
405 return _query.walk_commits_for_track
406
407 def test_structural_no_inline_while(self) -> None:
408 """walk_commits_for_track must not use an inline while-loop walk."""
409 src = inspect.getsource(self._fn())
410 assert "while current_id" not in src and "while commit_id" not in src, (
411 "midi._query.walk_commits_for_track still uses an inline while-loop — "
412 "migrate to iter_ancestors(first_parent_only=True)"
413 )
414
415 def test_linear_chain_all_returned(self, tmp_path: pathlib.Path) -> None:
416 repo = _make_repo(tmp_path)
417 root = _write_commit(repo, "root")
418 mid = _write_commit(repo, "mid", parent=root)
419 tip = _write_commit(repo, "tip", parent=mid)
420 result = self._fn()(repo, tip, track_path="song.mid")
421 commit_ids = {r[0].commit_id for r in result}
422 assert commit_ids == {root, mid, tip}
423
424 def test_first_parent_only_skips_second_parent(self, tmp_path: pathlib.Path) -> None:
425 """walk_commits_for_track must follow only first-parent at merge commits."""
426 repo = _make_repo(tmp_path)
427 root = _write_commit(repo, "root")
428 branch = _write_commit(repo, "branch", parent=root)
429 main_tip = _write_commit(repo, "main_tip", parent=root)
430 merge = _write_commit(repo, "merge", parent=main_tip, parent2=branch)
431 result = self._fn()(repo, merge, track_path="song.mid")
432 commit_ids = {r[0].commit_id for r in result}
433 assert merge in commit_ids
434 assert main_tip in commit_ids
435 assert root in commit_ids
436 assert branch not in commit_ids # second-parent branch skipped
437
438 def test_max_commits_cap(self, tmp_path: pathlib.Path) -> None:
439 repo = _make_repo(tmp_path)
440 prev = None
441 for i in range(10):
442 prev = _write_commit(repo, f"c{i}", parent=prev)
443 tip = prev
444 result = self._fn()(repo, tip, track_path="song.mid", max_commits=3)
445 assert len(result) <= 3
File History 1 commit
sha256:51ce277f663e01a43eaffbe77509b1de7ac2d4251b55d23306304bcdeb92c90d feat(pack): delta-encode snapshots in MPackBundle wire format Sonnet 4.6 minor ⚠ 121 days ago