test_stress_graph.py
python
| 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 | from __future__ import annotations |
| 15 | |
| 16 | import datetime |
| 17 | import pathlib |
| 18 | |
| 19 | import pytest |
| 20 | |
| 21 | from muse.core.merge_engine import find_merge_base |
| 22 | from muse.core.store import CommitRecord, write_commit |
| 23 | |
| 24 | |
| 25 | # --------------------------------------------------------------------------- |
| 26 | # Helpers |
| 27 | # --------------------------------------------------------------------------- |
| 28 | |
| 29 | |
| 30 | def _write(root: pathlib.Path, cid: str, parent: str | None = None, parent2: str | None = None) -> None: |
| 31 | write_commit(root, CommitRecord( |
| 32 | commit_id=cid, |
| 33 | repo_id="repo", |
| 34 | branch="main", |
| 35 | snapshot_id=f"snap-{cid}", |
| 36 | message=cid, |
| 37 | committed_at=datetime.datetime.now(datetime.timezone.utc), |
| 38 | parent_commit_id=parent, |
| 39 | parent2_commit_id=parent2, |
| 40 | )) |
| 41 | |
| 42 | |
| 43 | @pytest.fixture |
| 44 | def repo(tmp_path: pathlib.Path) -> pathlib.Path: |
| 45 | muse = tmp_path / ".muse" |
| 46 | (muse / "commits").mkdir(parents=True) |
| 47 | (muse / "refs" / "heads").mkdir(parents=True) |
| 48 | return tmp_path |
| 49 | |
| 50 | |
| 51 | # --------------------------------------------------------------------------- |
| 52 | # Linear chain |
| 53 | # --------------------------------------------------------------------------- |
| 54 | |
| 55 | |
| 56 | class TestLinearChain: |
| 57 | def test_chain_of_500_finds_base(self, repo: pathlib.Path) -> None: |
| 58 | """LCA of two commits on a 500-long linear chain is the shared ancestor.""" |
| 59 | prev: str | None = None |
| 60 | for i in range(500): |
| 61 | cid = f"c{i:04d}" |
| 62 | _write(repo, cid, prev) |
| 63 | prev = cid |
| 64 | |
| 65 | # Branch off at c0100 |
| 66 | _write(repo, "branch-tip", "c0100") |
| 67 | |
| 68 | base = find_merge_base(repo, "c0499", "branch-tip") |
| 69 | assert base == "c0100" |
| 70 | |
| 71 | def test_lca_of_adjacent_commits_is_parent(self, repo: pathlib.Path) -> None: |
| 72 | _write(repo, "root") |
| 73 | _write(repo, "child", "root") |
| 74 | assert find_merge_base(repo, "root", "child") == "root" |
| 75 | assert find_merge_base(repo, "child", "root") == "root" |
| 76 | |
| 77 | def test_long_chain_lca_symmetry(self, repo: pathlib.Path) -> None: |
| 78 | """find_merge_base(a, b) == find_merge_base(b, a) on a long chain.""" |
| 79 | prev: str | None = None |
| 80 | for i in range(100): |
| 81 | cid = f"n{i:03d}" |
| 82 | _write(repo, cid, prev) |
| 83 | prev = cid |
| 84 | |
| 85 | _write(repo, "left", "n050") |
| 86 | _write(repo, "right", "n050") |
| 87 | |
| 88 | assert find_merge_base(repo, "left", "right") == "n050" |
| 89 | assert find_merge_base(repo, "right", "left") == "n050" |
| 90 | |
| 91 | def test_same_commit_returns_itself(self, repo: pathlib.Path) -> None: |
| 92 | _write(repo, "solo") |
| 93 | assert find_merge_base(repo, "solo", "solo") == "solo" |
| 94 | |
| 95 | def test_one_is_ancestor_of_other(self, repo: pathlib.Path) -> None: |
| 96 | """When A is a direct ancestor of B, LCA is A.""" |
| 97 | prev: str | None = None |
| 98 | for i in range(20): |
| 99 | cid = f"x{i:02d}" |
| 100 | _write(repo, cid, prev) |
| 101 | prev = cid |
| 102 | assert find_merge_base(repo, "x00", "x19") == "x00" |
| 103 | assert find_merge_base(repo, "x19", "x00") == "x00" |
| 104 | |
| 105 | |
| 106 | # --------------------------------------------------------------------------- |
| 107 | # Diamond topology |
| 108 | # --------------------------------------------------------------------------- |
| 109 | |
| 110 | |
| 111 | class TestDiamondTopology: |
| 112 | def test_simple_diamond(self, repo: pathlib.Path) -> None: |
| 113 | """ |
| 114 | root |
| 115 | / \\ |
| 116 | L R |
| 117 | \\ / |
| 118 | M (merge commit, not relevant here — just find LCA of L and R) |
| 119 | """ |
| 120 | _write(repo, "root") |
| 121 | _write(repo, "L", "root") |
| 122 | _write(repo, "R", "root") |
| 123 | assert find_merge_base(repo, "L", "R") == "root" |
| 124 | |
| 125 | def test_double_diamond(self, repo: pathlib.Path) -> None: |
| 126 | """ |
| 127 | A |
| 128 | / \\ |
| 129 | B C |
| 130 | \\ / |
| 131 | D |
| 132 | / \\ |
| 133 | E F |
| 134 | \\ / |
| 135 | G |
| 136 | LCA(E, F) should be D. |
| 137 | """ |
| 138 | _write(repo, "A") |
| 139 | _write(repo, "B", "A") |
| 140 | _write(repo, "C", "A") |
| 141 | _write(repo, "D", "B", "C") |
| 142 | _write(repo, "E", "D") |
| 143 | _write(repo, "F", "D") |
| 144 | assert find_merge_base(repo, "E", "F") == "D" |
| 145 | |
| 146 | def test_criss_cross_merge(self, repo: pathlib.Path) -> None: |
| 147 | """ |
| 148 | Criss-cross: A and B are each other's ancestor via two different merge paths. |
| 149 | X → L1 → M1(L1,R1) |
| 150 | X → R1 → M2(R1,L1) |
| 151 | LCA of M1 and M2 should be either L1 or R1 (both are valid LCAs). |
| 152 | The algorithm must not return None or crash. |
| 153 | """ |
| 154 | _write(repo, "X") |
| 155 | _write(repo, "L1", "X") |
| 156 | _write(repo, "R1", "X") |
| 157 | _write(repo, "M1", "L1", "R1") |
| 158 | _write(repo, "M2", "R1", "L1") |
| 159 | |
| 160 | base = find_merge_base(repo, "M1", "M2") |
| 161 | # Any of X, L1, R1 is a valid common ancestor; None is not acceptable. |
| 162 | assert base is not None |
| 163 | assert base in {"X", "L1", "R1"} |
| 164 | |
| 165 | def test_octopus_three_branch_fan_in(self, repo: pathlib.Path) -> None: |
| 166 | """Three branches that all diverged from the same root.""" |
| 167 | _write(repo, "root") |
| 168 | _write(repo, "branch-a", "root") |
| 169 | _write(repo, "branch-b", "root") |
| 170 | _write(repo, "branch-c", "root") |
| 171 | |
| 172 | assert find_merge_base(repo, "branch-a", "branch-b") == "root" |
| 173 | assert find_merge_base(repo, "branch-a", "branch-c") == "root" |
| 174 | assert find_merge_base(repo, "branch-b", "branch-c") == "root" |
| 175 | |
| 176 | |
| 177 | # --------------------------------------------------------------------------- |
| 178 | # Independent histories |
| 179 | # --------------------------------------------------------------------------- |
| 180 | |
| 181 | |
| 182 | class TestDisjointHistories: |
| 183 | def test_no_common_ancestor_returns_none(self, repo: pathlib.Path) -> None: |
| 184 | _write(repo, "island-a") |
| 185 | _write(repo, "island-b") |
| 186 | assert find_merge_base(repo, "island-a", "island-b") is None |
| 187 | |
| 188 | def test_long_independent_chains_return_none(self, repo: pathlib.Path) -> None: |
| 189 | prev_a: str | None = None |
| 190 | prev_b: str | None = None |
| 191 | for i in range(20): |
| 192 | a = f"a{i:02d}" |
| 193 | b = f"b{i:02d}" |
| 194 | _write(repo, a, prev_a) |
| 195 | _write(repo, b, prev_b) |
| 196 | prev_a = a |
| 197 | prev_b = b |
| 198 | assert find_merge_base(repo, "a19", "b19") is None |
| 199 | |
| 200 | def test_missing_commit_id_graceful(self, repo: pathlib.Path) -> None: |
| 201 | """Asking for an LCA where one commit doesn't exist should return None, not raise.""" |
| 202 | _write(repo, "real") |
| 203 | result = find_merge_base(repo, "real", "ghost-commit-that-does-not-exist") |
| 204 | # The ghost has no ancestors, so no common ancestor found. |
| 205 | assert result is None |
| 206 | |
| 207 | |
| 208 | # --------------------------------------------------------------------------- |
| 209 | # Ancestor-set correctness |
| 210 | # --------------------------------------------------------------------------- |
| 211 | |
| 212 | |
| 213 | class TestAncestorCorrectness: |
| 214 | def test_merge_commit_has_both_parents_as_ancestors(self, repo: pathlib.Path) -> None: |
| 215 | _write(repo, "root") |
| 216 | _write(repo, "A", "root") |
| 217 | _write(repo, "B", "root") |
| 218 | _write(repo, "merge", "A", "B") |
| 219 | _write(repo, "feature", "A") |
| 220 | |
| 221 | # LCA of feature and merge: feature branched from A, merge contains A. |
| 222 | # So A is the common ancestor. |
| 223 | base = find_merge_base(repo, "feature", "merge") |
| 224 | assert base == "A" |
| 225 | |
| 226 | def test_wide_history_with_shared_root(self, repo: pathlib.Path) -> None: |
| 227 | """100 branches diverging from a shared root, pairwise LCA is root.""" |
| 228 | _write(repo, "root") |
| 229 | branches = [f"br{i:03d}" for i in range(50)] |
| 230 | for br in branches: |
| 231 | _write(repo, br, "root") |
| 232 | |
| 233 | # Check a sampling of pairs |
| 234 | for i in range(0, 50, 10): |
| 235 | for j in range(i + 1, 50, 10): |
| 236 | assert find_merge_base(repo, branches[i], branches[j]) == "root" |
| 237 | |
| 238 | def test_deep_branch_divergence(self, repo: pathlib.Path) -> None: |
| 239 | """Branches diverge at root, each has 50 commits. LCA is root.""" |
| 240 | _write(repo, "root") |
| 241 | prev_a: str | None = "root" |
| 242 | prev_b: str | None = "root" |
| 243 | for i in range(50): |
| 244 | a = f"da{i:02d}" |
| 245 | b = f"db{i:02d}" |
| 246 | _write(repo, a, prev_a) |
| 247 | _write(repo, b, prev_b) |
| 248 | prev_a = a |
| 249 | prev_b = b |
| 250 | |
| 251 | assert find_merge_base(repo, "da49", "db49") == "root" |
| 252 | |
| 253 | def test_multiple_merge_bases_chain(self, repo: pathlib.Path) -> None: |
| 254 | """A → B → C; branch D from B. LCA of C and D is B.""" |
| 255 | _write(repo, "A") |
| 256 | _write(repo, "B", "A") |
| 257 | _write(repo, "C", "B") |
| 258 | _write(repo, "D", "B") |
| 259 | assert find_merge_base(repo, "C", "D") == "B" |
| 260 | assert find_merge_base(repo, "D", "C") == "B" |