test_core_graph.py
python
sha256:88ac91129873e6a496e9189515aa690eb893ae25d69c8f72af141a2be5068eb3
docs: docstring sprint contract→find-symbol — idiomatic run…
Sonnet 4.6
patch
142 days ago
| 1 | """Tests for muse/core/graph.py — canonical commit DAG traversal primitives. |
| 2 | |
| 3 | Coverage |
| 4 | -------- |
| 5 | iter_ancestors |
| 6 | - empty starts list → yields nothing |
| 7 | - single root commit (no parents) → yields just that commit |
| 8 | - linear chain, yields in BFS order (newest-first) |
| 9 | - merge commit (two parents) → both parents visited, each once |
| 10 | - first_parent_only=True → only follows parent_commit_id |
| 11 | - exclude= set → treats boundary commits as already-visited |
| 12 | - max_commits=N → stops after N commits yielded (missing commits don't count) |
| 13 | - missing commit in chain → skipped gracefully, walk continues |
| 14 | - diamond DAG (shared ancestor) → shared commit visited exactly once |
| 15 | - multi-source starts → seeds BFS from multiple tips simultaneously |
| 16 | - uses deque internally (structural check, same rationale as blame test) |
| 17 | |
| 18 | ancestor_ids |
| 19 | - returns set of commit IDs (sha256:-prefixed) |
| 20 | - empty repo → empty set |
| 21 | - respects exclude= boundaries |
| 22 | - respects max_commits cap (returns IDs of visited commits) |
| 23 | |
| 24 | find_merge_base |
| 25 | - same commit → returns itself |
| 26 | - linear chain → returns the common ancestor |
| 27 | - true merge topology → returns LCA |
| 28 | - no common ancestor (two disjoint chains) → returns None |
| 29 | - max_ancestors= exceeded → raises ValueError |
| 30 | """ |
| 31 | |
| 32 | from __future__ import annotations |
| 33 | |
| 34 | import datetime |
| 35 | import json |
| 36 | import pathlib |
| 37 | |
| 38 | import pytest |
| 39 | |
| 40 | from muse.core.graph import ancestor_ids, find_merge_base, iter_ancestors |
| 41 | from muse.core._types import long_id |
| 42 | from muse.core.snapshot import compute_commit_id, compute_snapshot_id |
| 43 | from muse.core.store import CommitRecord, SnapshotRecord, write_commit, write_snapshot |
| 44 | |
| 45 | _BASE_DT = datetime.datetime(2026, 1, 1, tzinfo=datetime.timezone.utc) |
| 46 | |
| 47 | |
| 48 | # --------------------------------------------------------------------------- |
| 49 | # Helpers |
| 50 | # --------------------------------------------------------------------------- |
| 51 | |
| 52 | |
| 53 | def _make_repo(tmp_path: pathlib.Path) -> pathlib.Path: |
| 54 | muse = tmp_path / ".muse" |
| 55 | for d in ("objects", "commits", "snapshots", "refs/heads"): |
| 56 | (muse / d).mkdir(parents=True, exist_ok=True) |
| 57 | (muse / "repo.json").write_text(json.dumps({"repo_id": "test-repo"})) |
| 58 | (muse / "HEAD").write_text("ref: refs/heads/main\n") |
| 59 | return tmp_path |
| 60 | |
| 61 | |
| 62 | def _write_commit( |
| 63 | repo: pathlib.Path, |
| 64 | message: str = "commit", |
| 65 | parent: str | None = None, |
| 66 | parent2: str | None = None, |
| 67 | author: str = "Author", |
| 68 | committed_at: datetime.datetime | None = None, |
| 69 | ) -> str: |
| 70 | """Write a commit and return its commit_id.""" |
| 71 | dt = committed_at if committed_at is not None else _BASE_DT |
| 72 | snap_id = compute_snapshot_id({}) |
| 73 | write_snapshot(repo, SnapshotRecord(snapshot_id=snap_id, manifest={})) |
| 74 | parent_ids = [p for p in (parent, parent2) if p is not None] |
| 75 | commit_id = compute_commit_id(parent_ids, snap_id, message, dt.isoformat()) |
| 76 | write_commit( |
| 77 | repo, |
| 78 | CommitRecord( |
| 79 | commit_id=commit_id, |
| 80 | repo_id="test-repo", |
| 81 | branch="main", |
| 82 | snapshot_id=snap_id, |
| 83 | message=message, |
| 84 | committed_at=dt, |
| 85 | parent_commit_id=parent, |
| 86 | author=author, |
| 87 | parent2_commit_id=parent2, |
| 88 | ), |
| 89 | ) |
| 90 | return commit_id |
| 91 | |
| 92 | |
| 93 | def _ids(commits) -> list[str]: |
| 94 | return [c.commit_id for c in commits] |
| 95 | |
| 96 | |
| 97 | # --------------------------------------------------------------------------- |
| 98 | # iter_ancestors |
| 99 | # --------------------------------------------------------------------------- |
| 100 | |
| 101 | |
| 102 | class TestIterAncestors: |
| 103 | def test_empty_starts_yields_nothing(self, tmp_path: pathlib.Path) -> None: |
| 104 | repo = _make_repo(tmp_path) |
| 105 | assert list(iter_ancestors(repo, [])) == [] |
| 106 | |
| 107 | def test_single_root_commit(self, tmp_path: pathlib.Path) -> None: |
| 108 | repo = _make_repo(tmp_path) |
| 109 | cid = _write_commit(repo, "root") |
| 110 | result = list(iter_ancestors(repo, cid)) |
| 111 | assert len(result) == 1 |
| 112 | assert result[0].commit_id == cid |
| 113 | |
| 114 | def test_linear_chain_yields_all_in_bfs_order(self, tmp_path: pathlib.Path) -> None: |
| 115 | """A→B→C chain starting from A yields A, B, C in that order.""" |
| 116 | repo = _make_repo(tmp_path) |
| 117 | c = _write_commit(repo, "root") |
| 118 | b = _write_commit(repo, "second", parent=c) |
| 119 | a = _write_commit(repo, "third", parent=b) |
| 120 | |
| 121 | result = _ids(iter_ancestors(repo, a)) |
| 122 | assert result == [a, b, c] |
| 123 | |
| 124 | def test_merge_commit_visits_both_parents(self, tmp_path: pathlib.Path) -> None: |
| 125 | """Merge commit with two parents → both parent branches visited.""" |
| 126 | repo = _make_repo(tmp_path) |
| 127 | root = _write_commit(repo, "root") |
| 128 | left = _write_commit(repo, "left", parent=root) |
| 129 | right = _write_commit(repo, "right", parent=root) |
| 130 | merge = _write_commit(repo, "merge", parent=left, parent2=right) |
| 131 | |
| 132 | visited = set(_ids(iter_ancestors(repo, merge))) |
| 133 | assert merge in visited |
| 134 | assert left in visited |
| 135 | assert right in visited |
| 136 | assert root in visited |
| 137 | |
| 138 | def test_diamond_dag_shared_ancestor_visited_once(self, tmp_path: pathlib.Path) -> None: |
| 139 | """In a diamond (A→B, A→C, B→D, C→D), D is visited exactly once.""" |
| 140 | repo = _make_repo(tmp_path) |
| 141 | d = _write_commit(repo, "D") |
| 142 | b = _write_commit(repo, "B", parent=d) |
| 143 | c = _write_commit(repo, "C", parent=d) |
| 144 | a = _write_commit(repo, "A", parent=b, parent2=c) |
| 145 | |
| 146 | result = list(iter_ancestors(repo, a)) |
| 147 | commit_ids = _ids(result) |
| 148 | # D must appear exactly once despite two paths reaching it. |
| 149 | assert commit_ids.count(d) == 1 |
| 150 | assert set(commit_ids) == {a, b, c, d} |
| 151 | |
| 152 | def test_first_parent_only_skips_second_parent(self, tmp_path: pathlib.Path) -> None: |
| 153 | repo = _make_repo(tmp_path) |
| 154 | root = _write_commit(repo, "root") |
| 155 | left = _write_commit(repo, "left", parent=root) |
| 156 | right = _write_commit(repo, "right", parent=root) |
| 157 | merge = _write_commit(repo, "merge", parent=left, parent2=right) |
| 158 | |
| 159 | result = set(_ids(iter_ancestors(repo, merge, first_parent_only=True))) |
| 160 | assert merge in result |
| 161 | assert left in result |
| 162 | assert root in result |
| 163 | assert right not in result # second parent branch skipped |
| 164 | |
| 165 | def test_exclude_stops_at_boundary(self, tmp_path: pathlib.Path) -> None: |
| 166 | """Commits in `exclude` and their ancestors are never yielded.""" |
| 167 | repo = _make_repo(tmp_path) |
| 168 | root = _write_commit(repo, "root") |
| 169 | mid = _write_commit(repo, "mid", parent=root) |
| 170 | tip = _write_commit(repo, "tip", parent=mid) |
| 171 | |
| 172 | result = _ids(iter_ancestors(repo, tip, exclude={mid})) |
| 173 | assert tip in result |
| 174 | assert mid not in result |
| 175 | assert root not in result |
| 176 | |
| 177 | def test_max_commits_caps_yield(self, tmp_path: pathlib.Path) -> None: |
| 178 | """max_commits=2 yields at most 2 commits from a longer chain.""" |
| 179 | repo = _make_repo(tmp_path) |
| 180 | c = _write_commit(repo, "root") |
| 181 | b = _write_commit(repo, "mid", parent=c) |
| 182 | a = _write_commit(repo, "tip", parent=b) |
| 183 | |
| 184 | result = list(iter_ancestors(repo, a, max_commits=2)) |
| 185 | assert len(result) == 2 |
| 186 | |
| 187 | def test_missing_commit_skipped_walk_continues(self, tmp_path: pathlib.Path) -> None: |
| 188 | """A missing commit ID in the chain is silently skipped.""" |
| 189 | repo = _make_repo(tmp_path) |
| 190 | root = _write_commit(repo, "root") |
| 191 | # Write a commit that references a nonexistent parent. |
| 192 | snap_id = compute_snapshot_id({}) |
| 193 | write_snapshot(repo, SnapshotRecord(snapshot_id=snap_id, manifest={})) |
| 194 | ghost_parent = long_id("ab" * 32) |
| 195 | cid = compute_commit_id([ghost_parent], snap_id, "orphan", _BASE_DT.isoformat()) |
| 196 | write_commit( |
| 197 | repo, |
| 198 | CommitRecord( |
| 199 | commit_id=cid, |
| 200 | repo_id="test-repo", |
| 201 | branch="main", |
| 202 | snapshot_id=snap_id, |
| 203 | message="orphan", |
| 204 | committed_at=_BASE_DT, |
| 205 | parent_commit_id=ghost_parent, |
| 206 | author="A", |
| 207 | ), |
| 208 | ) |
| 209 | |
| 210 | # Should yield the orphan commit without crashing on the ghost parent. |
| 211 | result = list(iter_ancestors(repo, cid)) |
| 212 | assert len(result) == 1 |
| 213 | assert result[0].commit_id == cid |
| 214 | |
| 215 | def test_multi_source_starts(self, tmp_path: pathlib.Path) -> None: |
| 216 | """Multi-source BFS from two tips collects ancestors of both.""" |
| 217 | repo = _make_repo(tmp_path) |
| 218 | shared = _write_commit(repo, "shared") |
| 219 | branch_a = _write_commit(repo, "branch_a", parent=shared) |
| 220 | branch_b = _write_commit(repo, "branch_b", parent=shared) |
| 221 | |
| 222 | visited = set(_ids(iter_ancestors(repo, [branch_a, branch_b]))) |
| 223 | assert branch_a in visited |
| 224 | assert branch_b in visited |
| 225 | assert shared in visited # shared ancestor visited once |
| 226 | |
| 227 | def test_multi_source_shared_ancestor_once(self, tmp_path: pathlib.Path) -> None: |
| 228 | """Shared ancestor appears exactly once in multi-source BFS.""" |
| 229 | repo = _make_repo(tmp_path) |
| 230 | shared = _write_commit(repo, "shared") |
| 231 | a = _write_commit(repo, "a", parent=shared) |
| 232 | b = _write_commit(repo, "b", parent=shared) |
| 233 | |
| 234 | all_ids = _ids(iter_ancestors(repo, [a, b])) |
| 235 | assert all_ids.count(shared) == 1 |
| 236 | |
| 237 | def test_yields_commit_records_not_ids(self, tmp_path: pathlib.Path) -> None: |
| 238 | """iter_ancestors yields CommitRecord objects (not strings).""" |
| 239 | from muse.core.store import CommitRecord as CR |
| 240 | repo = _make_repo(tmp_path) |
| 241 | cid = _write_commit(repo, "root", author="Alice") |
| 242 | result = list(iter_ancestors(repo, cid)) |
| 243 | assert len(result) == 1 |
| 244 | assert isinstance(result[0], CR) |
| 245 | assert result[0].author == "Alice" |
| 246 | |
| 247 | def test_uses_deque_not_list(self) -> None: |
| 248 | """iter_ancestors must use collections.deque for O(1) popleft.""" |
| 249 | import inspect |
| 250 | from muse.core import graph as graph_module |
| 251 | source = inspect.getsource(graph_module.iter_ancestors) |
| 252 | assert "deque" in source, "iter_ancestors must use collections.deque" |
| 253 | assert "pop(0)" not in source, "must not use list.pop(0)" |
| 254 | assert "insert(0" not in source, "must not use list.insert(0, ...)" |
| 255 | |
| 256 | |
| 257 | # --------------------------------------------------------------------------- |
| 258 | # ancestor_ids |
| 259 | # --------------------------------------------------------------------------- |
| 260 | |
| 261 | |
| 262 | class TestAncestorIds: |
| 263 | def test_returns_set_of_prefixed_ids(self, tmp_path: pathlib.Path) -> None: |
| 264 | repo = _make_repo(tmp_path) |
| 265 | c = _write_commit(repo, "root") |
| 266 | b = _write_commit(repo, "mid", parent=c) |
| 267 | a = _write_commit(repo, "tip", parent=b) |
| 268 | result = ancestor_ids(repo, a) |
| 269 | assert isinstance(result, set) |
| 270 | assert result == {a, b, c} |
| 271 | for oid in result: |
| 272 | assert oid.startswith("sha256:") |
| 273 | |
| 274 | def test_empty_starts_returns_empty_set(self, tmp_path: pathlib.Path) -> None: |
| 275 | repo = _make_repo(tmp_path) |
| 276 | assert ancestor_ids(repo, []) == set() |
| 277 | |
| 278 | def test_exclude_boundaries_respected(self, tmp_path: pathlib.Path) -> None: |
| 279 | repo = _make_repo(tmp_path) |
| 280 | root = _write_commit(repo, "root") |
| 281 | mid = _write_commit(repo, "mid", parent=root) |
| 282 | tip = _write_commit(repo, "tip", parent=mid) |
| 283 | result = ancestor_ids(repo, tip, exclude={mid}) |
| 284 | assert tip in result |
| 285 | assert mid not in result |
| 286 | assert root not in result |
| 287 | |
| 288 | def test_max_commits_respected(self, tmp_path: pathlib.Path) -> None: |
| 289 | repo = _make_repo(tmp_path) |
| 290 | ids = [] |
| 291 | prev = None |
| 292 | for i in range(10): |
| 293 | cid = _write_commit(repo, f"c{i}", parent=prev) |
| 294 | ids.append(cid) |
| 295 | prev = cid |
| 296 | tip = ids[-1] |
| 297 | result = ancestor_ids(repo, tip, max_commits=5) |
| 298 | assert len(result) <= 5 |
| 299 | |
| 300 | def test_range_exclusion_pattern(self, tmp_path: pathlib.Path) -> None: |
| 301 | """ancestor_ids(base) as exclude= produces A..B semantics.""" |
| 302 | repo = _make_repo(tmp_path) |
| 303 | shared = _write_commit(repo, "shared") |
| 304 | base = _write_commit(repo, "base", parent=shared) |
| 305 | c1 = _write_commit(repo, "c1", parent=base) |
| 306 | c2 = _write_commit(repo, "c2", parent=c1) |
| 307 | |
| 308 | base_ancestors = ancestor_ids(repo, base) |
| 309 | tip_range = ancestor_ids(repo, c2, exclude=base_ancestors) |
| 310 | assert c2 in tip_range |
| 311 | assert c1 in tip_range |
| 312 | assert base not in tip_range |
| 313 | assert shared not in tip_range |
| 314 | |
| 315 | |
| 316 | # --------------------------------------------------------------------------- |
| 317 | # find_merge_base |
| 318 | # --------------------------------------------------------------------------- |
| 319 | |
| 320 | |
| 321 | class TestFindMergeBase: |
| 322 | def test_same_commit_returns_itself(self, tmp_path: pathlib.Path) -> None: |
| 323 | repo = _make_repo(tmp_path) |
| 324 | cid = _write_commit(repo, "root") |
| 325 | assert find_merge_base(repo, cid, cid) == cid |
| 326 | |
| 327 | def test_linear_chain_returns_common_ancestor(self, tmp_path: pathlib.Path) -> None: |
| 328 | """A→B→C: merge_base(A, B) == B.""" |
| 329 | repo = _make_repo(tmp_path) |
| 330 | c = _write_commit(repo, "root") |
| 331 | b = _write_commit(repo, "mid", parent=c) |
| 332 | a = _write_commit(repo, "tip", parent=b) |
| 333 | assert find_merge_base(repo, a, b) == b |
| 334 | |
| 335 | def test_true_merge_returns_lca(self, tmp_path: pathlib.Path) -> None: |
| 336 | """root→left, root→right: merge_base(left, right) == root.""" |
| 337 | repo = _make_repo(tmp_path) |
| 338 | root = _write_commit(repo, "root") |
| 339 | left = _write_commit(repo, "left", parent=root) |
| 340 | right = _write_commit(repo, "right", parent=root) |
| 341 | assert find_merge_base(repo, left, right) == root |
| 342 | |
| 343 | def test_deeper_lca(self, tmp_path: pathlib.Path) -> None: |
| 344 | """A→B→X, A→C→X: merge_base(B, C) == X.""" |
| 345 | repo = _make_repo(tmp_path) |
| 346 | x = _write_commit(repo, "X") |
| 347 | b = _write_commit(repo, "B", parent=x) |
| 348 | c = _write_commit(repo, "C", parent=x) |
| 349 | assert find_merge_base(repo, b, c) == x |
| 350 | |
| 351 | def test_no_common_ancestor_returns_none(self, tmp_path: pathlib.Path) -> None: |
| 352 | """Two root commits with no shared history → None.""" |
| 353 | repo = _make_repo(tmp_path) |
| 354 | root_a = _write_commit(repo, "rootA") |
| 355 | root_b = _write_commit(repo, "rootB") |
| 356 | result = find_merge_base(repo, root_a, root_b) |
| 357 | assert result is None |
| 358 | |
| 359 | def test_symmetric(self, tmp_path: pathlib.Path) -> None: |
| 360 | """find_merge_base(a, b) == find_merge_base(b, a).""" |
| 361 | repo = _make_repo(tmp_path) |
| 362 | root = _write_commit(repo, "root") |
| 363 | left = _write_commit(repo, "left", parent=root) |
| 364 | right = _write_commit(repo, "right", parent=root) |
| 365 | assert find_merge_base(repo, left, right) == find_merge_base(repo, right, left) |
| 366 | |
| 367 | def test_max_ancestors_raises_on_deep_graph(self, tmp_path: pathlib.Path) -> None: |
| 368 | """When max_ancestors is exceeded, raises ValueError.""" |
| 369 | repo = _make_repo(tmp_path) |
| 370 | # Build a chain of 10 commits. |
| 371 | prev = None |
| 372 | for i in range(10): |
| 373 | prev = _write_commit(repo, f"c{i}", parent=prev) |
| 374 | a = _write_commit(repo, "a", parent=prev) |
| 375 | b_root = _write_commit(repo, "b_root") |
| 376 | b = _write_commit(repo, "b", parent=b_root) |
| 377 | # With max_ancestors=1, BFS from a and b won't find common ancestor. |
| 378 | with pytest.raises(ValueError, match="max_ancestors"): |
| 379 | find_merge_base(repo, a, b, max_ancestors=1) |
| 380 | |
| 381 | def test_ancestor_of_itself_via_chain(self, tmp_path: pathlib.Path) -> None: |
| 382 | """merge_base(tip, root) == root when root is an ancestor of tip.""" |
| 383 | repo = _make_repo(tmp_path) |
| 384 | root = _write_commit(repo, "root") |
| 385 | mid = _write_commit(repo, "mid", parent=root) |
| 386 | tip = _write_commit(repo, "tip", parent=mid) |
| 387 | result = find_merge_base(repo, tip, root) |
| 388 | assert result == root |
File History
1 commit
sha256:88ac91129873e6a496e9189515aa690eb893ae25d69c8f72af141a2be5068eb3
docs: docstring sprint contract→find-symbol — idiomatic run…
Sonnet 4.6
patch
142 days ago