test_commit_graph_phase2.py
file-level
1
files
1
commits
0
hotspots
0
🧊 dead
0
💥 blast risk
| 1 | """TDD — Phase 2: commit graph for O(1) BFS-frontier DAG walks (issue #63). |
| 2 | |
| 3 | CG-1 After process_mpack_index_job, every commit in the mpack has a row |
| 4 | in musehub_commit_graph with correct parent_ids. |
| 5 | CG-2 Generation numbers are monotonically correct: |
| 6 | - root commit → generation 0 |
| 7 | - each commit → generation = max(parent generations) + 1 |
| 8 | CG-3 _walk_commit_delta for 1000 commits completes in under 50ms |
| 9 | (proves bulk-query path, not one-per-commit path). |
| 10 | CG-4 _walk_commit_delta correctness: returns exactly the right delta |
| 11 | when the receiver already has some commits (partial clone / incremental fetch). |
| 12 | """ |
| 13 | from __future__ import annotations |
| 14 | |
| 15 | import datetime |
| 16 | import hashlib |
| 17 | import time |
| 18 | |
| 19 | import msgpack |
| 20 | import pytest |
| 21 | from sqlalchemy import select |
| 22 | from sqlalchemy.ext.asyncio import AsyncSession |
| 23 | |
| 24 | from muse.core.types import blob_id |
| 25 | from musehub.db import musehub_repo_models as db |
| 26 | from musehub.core.genesis import compute_identity_id |
| 27 | from musehub.services.musehub_repository import create_repo |
| 28 | |
| 29 | from musehub.services.musehub_wire import process_mpack_index_job |
| 30 | |
| 31 | |
| 32 | # --------------------------------------------------------------------------- |
| 33 | # Helpers |
| 34 | # --------------------------------------------------------------------------- |
| 35 | |
| 36 | def _make_linear_chain(n: int, seed: str = "cg") -> tuple[list[dict], str]: |
| 37 | """Build a linear commit chain of length n. |
| 38 | |
| 39 | Returns (commits_list, tip_commit_id). |
| 40 | Each commit dict has: commit_id, parent_commit_id, snapshot_id, branch, message. |
| 41 | """ |
| 42 | commits = [] |
| 43 | parent_id: str | None = None |
| 44 | for i in range(n): |
| 45 | snap_id = blob_id(f"{seed}-snap-{i}".encode()) |
| 46 | msg_bytes = f"{seed}-commit-{i}-parent={parent_id}".encode() |
| 47 | cid = blob_id(msg_bytes) |
| 48 | commits.append({ |
| 49 | "commit_id": cid, |
| 50 | "branch": "main", |
| 51 | "message": f"commit {i}", |
| 52 | "author": "gabriel", |
| 53 | "committed_at": datetime.datetime(2025, 1, 1, tzinfo=datetime.timezone.utc).isoformat(), |
| 54 | "parent_commit_id": parent_id, |
| 55 | "parent2_commit_id": None, |
| 56 | "snapshot_id": snap_id, |
| 57 | "agent_id": "", |
| 58 | "model_id": "", |
| 59 | "toolchain_id": "", |
| 60 | "sem_ver_bump": "none", |
| 61 | "breaking_changes": [], |
| 62 | "signature": "", |
| 63 | "signer_key_id": "", |
| 64 | "signer_public_key": "", |
| 65 | "prompt_hash": "", |
| 66 | }) |
| 67 | parent_id = cid |
| 68 | return commits, parent_id # type: ignore[return-value] |
| 69 | |
| 70 | |
| 71 | def _make_mpack_from_commits(commits: list[dict]) -> tuple[bytes, str]: |
| 72 | mpack = { |
| 73 | "commits": commits, |
| 74 | "snapshots": [], |
| 75 | "objects": [], |
| 76 | "branch_heads": {"main": commits[-1]["commit_id"]}, |
| 77 | } |
| 78 | wire_bytes = msgpack.packb(mpack, use_bin_type=True) |
| 79 | mpack_key = "sha256:" + hashlib.sha256(wire_bytes).hexdigest() |
| 80 | return wire_bytes, mpack_key |
| 81 | |
| 82 | |
| 83 | async def _store_mpack(wire_bytes: bytes, mpack_key: str) -> None: |
| 84 | import musehub.storage.backends as _backends_mod |
| 85 | backend = _backends_mod.get_backend() |
| 86 | await backend.put_mpack(mpack_key, wire_bytes) |
| 87 | |
| 88 | |
| 89 | async def _enqueue_and_process( |
| 90 | session: AsyncSession, |
| 91 | repo_id: str, |
| 92 | mpack_key: str, |
| 93 | commits: list[dict], |
| 94 | ) -> str: |
| 95 | from musehub.core.genesis import compute_job_id |
| 96 | from musehub.db.musehub_jobs_models import MusehubBackgroundJob |
| 97 | |
| 98 | now = datetime.datetime.now(datetime.timezone.utc) |
| 99 | job_id = compute_job_id(repo_id, "mpack.index", now.isoformat()) |
| 100 | session.add(MusehubBackgroundJob( |
| 101 | job_id=job_id, |
| 102 | repo_id=repo_id, |
| 103 | job_type="mpack.index", |
| 104 | payload={ |
| 105 | "mpack_key": mpack_key, |
| 106 | "branch": "main", |
| 107 | "head": commits[-1]["commit_id"], |
| 108 | "pusher_id": "", |
| 109 | "declared_objects_count": 0, |
| 110 | "declared_commits_count": len(commits), |
| 111 | }, |
| 112 | status="pending", |
| 113 | created_at=now, |
| 114 | attempt=0, |
| 115 | )) |
| 116 | await session.commit() |
| 117 | await process_mpack_index_job(session, job_id) |
| 118 | await session.commit() |
| 119 | return job_id |
| 120 | |
| 121 | |
| 122 | # --------------------------------------------------------------------------- |
| 123 | # CG-1 |
| 124 | # --------------------------------------------------------------------------- |
| 125 | |
| 126 | @pytest.mark.asyncio |
| 127 | async def test_cg1_commit_graph_written_for_every_commit(db_session: AsyncSession) -> None: |
| 128 | """Every commit in the mpack must have a row in musehub_commit_graph.""" |
| 129 | repo = await create_repo( |
| 130 | db_session, |
| 131 | name="cg-test-1", |
| 132 | owner="gabriel", |
| 133 | owner_user_id=compute_identity_id(b"gabriel"), |
| 134 | visibility="public", |
| 135 | initialize=False, |
| 136 | ) |
| 137 | |
| 138 | n = 20 |
| 139 | commits, tip = _make_linear_chain(n, seed="cg1") |
| 140 | wire_bytes, mpack_key = _make_mpack_from_commits(commits) |
| 141 | await _store_mpack(wire_bytes, mpack_key) |
| 142 | await _enqueue_and_process(db_session, repo.repo_id, mpack_key, commits) |
| 143 | |
| 144 | expected_cids = {c["commit_id"] for c in commits} |
| 145 | rows_q = await db_session.execute( |
| 146 | select(db.MusehubCommitGraph).where( |
| 147 | db.MusehubCommitGraph.commit_id.in_(expected_cids) |
| 148 | ) |
| 149 | ) |
| 150 | rows = rows_q.scalars().all() |
| 151 | indexed_cids = {r.commit_id for r in rows} |
| 152 | |
| 153 | assert indexed_cids == expected_cids, ( |
| 154 | f"expected {n} commit graph rows, got {len(rows)}\n" |
| 155 | f"missing: {expected_cids - indexed_cids}" |
| 156 | ) |
| 157 | |
| 158 | |
| 159 | # --------------------------------------------------------------------------- |
| 160 | # CG-2 |
| 161 | # --------------------------------------------------------------------------- |
| 162 | |
| 163 | @pytest.mark.asyncio |
| 164 | async def test_cg2_generation_numbers_correct(db_session: AsyncSession) -> None: |
| 165 | """Root commit → generation 0; each subsequent commit → parent_generation + 1.""" |
| 166 | repo = await create_repo( |
| 167 | db_session, |
| 168 | name="cg-test-2", |
| 169 | owner="gabriel", |
| 170 | owner_user_id=compute_identity_id(b"gabriel"), |
| 171 | visibility="public", |
| 172 | initialize=False, |
| 173 | ) |
| 174 | |
| 175 | n = 10 |
| 176 | commits, tip = _make_linear_chain(n, seed="cg2") |
| 177 | wire_bytes, mpack_key = _make_mpack_from_commits(commits) |
| 178 | await _store_mpack(wire_bytes, mpack_key) |
| 179 | await _enqueue_and_process(db_session, repo.repo_id, mpack_key, commits) |
| 180 | |
| 181 | expected_cids_cg2 = {c["commit_id"] for c in commits} |
| 182 | rows_q = await db_session.execute( |
| 183 | select(db.MusehubCommitGraph).where( |
| 184 | db.MusehubCommitGraph.commit_id.in_(expected_cids_cg2) |
| 185 | ) |
| 186 | ) |
| 187 | rows = {r.commit_id: r for r in rows_q.scalars().all()} |
| 188 | |
| 189 | for i, commit in enumerate(commits): |
| 190 | cid = commit["commit_id"] |
| 191 | row = rows.get(cid) |
| 192 | assert row is not None, f"commit {i} missing from graph" |
| 193 | assert row.generation == i, ( |
| 194 | f"commit {i}: expected generation={i}, got {row.generation}" |
| 195 | ) |
| 196 | |
| 197 | |
| 198 | # --------------------------------------------------------------------------- |
| 199 | # CG-3 |
| 200 | # --------------------------------------------------------------------------- |
| 201 | |
| 202 | @pytest.mark.asyncio |
| 203 | async def test_cg3_walk_commit_delta_1000_commits_under_50ms(db_session: AsyncSession) -> None: |
| 204 | """_walk_commit_delta for 1000 commits must complete in under 50ms.""" |
| 205 | repo = await create_repo( |
| 206 | db_session, |
| 207 | name="cg-test-3", |
| 208 | owner="gabriel", |
| 209 | owner_user_id=compute_identity_id(b"gabriel"), |
| 210 | visibility="public", |
| 211 | initialize=False, |
| 212 | ) |
| 213 | |
| 214 | n = 1000 |
| 215 | commits, tip = _make_linear_chain(n, seed="cg3") |
| 216 | wire_bytes, mpack_key = _make_mpack_from_commits(commits) |
| 217 | await _store_mpack(wire_bytes, mpack_key) |
| 218 | await _enqueue_and_process(db_session, repo.repo_id, mpack_key, commits) |
| 219 | |
| 220 | from musehub.services.musehub_wire import _walk_commit_delta |
| 221 | |
| 222 | t0 = time.perf_counter() |
| 223 | delta = await _walk_commit_delta(db_session, [tip], have=[]) |
| 224 | elapsed_ms = (time.perf_counter() - t0) * 1000 |
| 225 | |
| 226 | assert len(delta) == n, f"expected {n} commits in delta, got {len(delta)}" |
| 227 | assert elapsed_ms < 50, ( |
| 228 | f"_walk_commit_delta took {elapsed_ms:.1f}ms for {n} commits — must be < 50ms" |
| 229 | ) |
| 230 | |
| 231 | |
| 232 | # --------------------------------------------------------------------------- |
| 233 | # CG-4 |
| 234 | # --------------------------------------------------------------------------- |
| 235 | |
| 236 | @pytest.mark.asyncio |
| 237 | async def test_cg4_walk_commit_delta_correctness_with_have(db_session: AsyncSession) -> None: |
| 238 | """Delta walk with a non-empty 'have' set returns only the commits the receiver lacks.""" |
| 239 | repo = await create_repo( |
| 240 | db_session, |
| 241 | name="cg-test-4", |
| 242 | owner="gabriel", |
| 243 | owner_user_id=compute_identity_id(b"gabriel"), |
| 244 | visibility="public", |
| 245 | initialize=False, |
| 246 | ) |
| 247 | |
| 248 | n = 50 |
| 249 | commits, tip = _make_linear_chain(n, seed="cg4") |
| 250 | wire_bytes, mpack_key = _make_mpack_from_commits(commits) |
| 251 | await _store_mpack(wire_bytes, mpack_key) |
| 252 | await _enqueue_and_process(db_session, repo.repo_id, mpack_key, commits) |
| 253 | |
| 254 | # Receiver already has the first 20 commits. |
| 255 | have_idx = 20 |
| 256 | have_commit_id = commits[have_idx]["commit_id"] |
| 257 | have = {c["commit_id"] for c in commits[: have_idx + 1]} |
| 258 | |
| 259 | from musehub.services.musehub_wire import _walk_commit_delta |
| 260 | |
| 261 | delta = await _walk_commit_delta(db_session, [tip], have=list(have), ) |
| 262 | |
| 263 | expected = {c["commit_id"] for c in commits[have_idx + 1:]} |
| 264 | assert set(delta.keys()) == expected, ( |
| 265 | f"delta wrong: expected {len(expected)} commits, got {len(delta)}\n" |
| 266 | f"extra: {set(delta.keys()) - expected}\n" |
| 267 | f"missing: {expected - set(delta.keys())}" |
| 268 | ) |