test_proposal_reimagination_phase2.py
file-level
1
files
1
commits
0
hotspots
0
🧊 dead
0
💥 blast risk
| 1 | """Phase 2 — Dependency DAG Engine tests (issue #37). |
| 2 | |
| 3 | Tier 1 — Unit (pure, no DB) |
| 4 | - build_dag: adjacency, merged_ids, number_by_id |
| 5 | - topological_sort: linear chain, branching diamond, multi-root, isolated nodes |
| 6 | - topological_sort: raises CycleError on cycles; cycle_ids populated correctly |
| 7 | - detect_cycle: True/False without side effects |
| 8 | - blocked_by_numbers: live deps only (merged dependencies excluded) |
| 9 | - blocks_numbers: reverse direction |
| 10 | - is_blocked: True/False contract |
| 11 | |
| 12 | Tier 5 — Integration (DB) |
| 13 | - create_proposal wires depends_on → MusehubProposalDependency rows |
| 14 | - create_proposal rejects unknown dependency IDs |
| 15 | - create_proposal detects and rejects cycles via CycleError |
| 16 | - enrich_proposal_list_batch populates blocked_by / blocks / is_blocked |
| 17 | - all_merge_conditions_met is False while hard dep is unmerged |
| 18 | - all_merge_conditions_met is True once dep is merged |
| 19 | - merge_proposal gates on unmerged dependencies (raises RuntimeError) |
| 20 | - merge_proposal succeeds once all deps are merged |
| 21 | - Merging dep A unblocks dep B in subsequent enrichment |
| 22 | """ |
| 23 | |
| 24 | from __future__ import annotations |
| 25 | |
| 26 | import uuid |
| 27 | from datetime import datetime, timezone |
| 28 | |
| 29 | import pytest |
| 30 | from sqlalchemy.ext.asyncio import AsyncSession |
| 31 | |
| 32 | from musehub.services.proposal_dag import ( |
| 33 | CycleError, |
| 34 | ProposalDag, |
| 35 | blocked_by_numbers, |
| 36 | blocks_numbers, |
| 37 | build_dag, |
| 38 | detect_cycle, |
| 39 | is_blocked, |
| 40 | topological_sort, |
| 41 | ) |
| 42 | |
| 43 | |
| 44 | # ───────────────────────────────────────────────────────────────────────────── |
| 45 | # Helpers |
| 46 | # ───────────────────────────────────────────────────────────────────────────── |
| 47 | |
| 48 | |
| 49 | def _now() -> datetime: |
| 50 | return datetime.now(tz=timezone.utc) |
| 51 | |
| 52 | |
| 53 | def _uid() -> str: |
| 54 | return uuid.uuid4().hex[:12] |
| 55 | |
| 56 | |
| 57 | def _ids(n: int) -> list[str]: |
| 58 | return [f"sha256:{'%064x' % i}" for i in range(1, n + 1)] |
| 59 | |
| 60 | |
| 61 | async def _make_repo(session: AsyncSession) -> str: |
| 62 | from musehub.core.genesis import compute_identity_id, compute_repo_id |
| 63 | from musehub.db.musehub_repo_models import MusehubBranch, MusehubRepo |
| 64 | from musehub.db.musehub_social_models import MusehubProposal, MusehubProposalDependency |
| 65 | |
| 66 | owner = "dagtest" |
| 67 | slug = f"repo-{_uid()}" |
| 68 | owner_id = compute_identity_id(owner.encode()) |
| 69 | created_at = _now() |
| 70 | repo = MusehubRepo( |
| 71 | repo_id=compute_repo_id(owner_id, slug, "code", created_at.isoformat()), |
| 72 | name=slug, |
| 73 | owner=owner, |
| 74 | slug=slug, |
| 75 | visibility="public", |
| 76 | owner_user_id=owner_id, |
| 77 | description="", |
| 78 | tags=[], |
| 79 | created_at=created_at, |
| 80 | ) |
| 81 | session.add(repo) |
| 82 | await session.flush() |
| 83 | return repo.repo_id |
| 84 | |
| 85 | |
| 86 | async def _make_branch(session: AsyncSession, repo_id: str, name: str) -> None: |
| 87 | from musehub.core.genesis import compute_branch_id |
| 88 | from musehub.db.musehub_repo_models import MusehubBranch, MusehubRepo |
| 89 | from musehub.db.musehub_social_models import MusehubProposal, MusehubProposalDependency |
| 90 | |
| 91 | branch = MusehubBranch( |
| 92 | branch_id=compute_branch_id(repo_id, name), |
| 93 | repo_id=repo_id, |
| 94 | name=name, |
| 95 | ) |
| 96 | session.add(branch) |
| 97 | await session.flush() |
| 98 | |
| 99 | |
| 100 | async def _create_proposal( |
| 101 | session: AsyncSession, |
| 102 | repo_id: str, |
| 103 | *, |
| 104 | from_branch: str, |
| 105 | number: int = 1, |
| 106 | depends_on: list[str] | None = None, |
| 107 | ) -> "MusehubProposal": |
| 108 | from musehub.services.musehub_proposals import create_proposal |
| 109 | |
| 110 | return await create_proposal( |
| 111 | session, |
| 112 | repo_id=repo_id, |
| 113 | title=f"proposal {number}", |
| 114 | from_branch=from_branch, |
| 115 | to_branch="dev", |
| 116 | author="dagtest", |
| 117 | depends_on=depends_on or [], |
| 118 | ) |
| 119 | |
| 120 | |
| 121 | # ───────────────────────────────────────────────────────────────────────────── |
| 122 | # Tier 1 — Unit: build_dag |
| 123 | # ───────────────────────────────────────────────────────────────────────────── |
| 124 | |
| 125 | |
| 126 | class TestBuildDag: |
| 127 | def test_empty_edges(self) -> None: |
| 128 | dag = build_dag([]) |
| 129 | assert dag.nodes == set() |
| 130 | assert len(dag.depends_on) == 0 |
| 131 | |
| 132 | def test_single_edge(self) -> None: |
| 133 | a, b = _ids(2) |
| 134 | dag = build_dag([(b, a)]) # B depends on A |
| 135 | assert a in dag.nodes |
| 136 | assert b in dag.nodes |
| 137 | assert a in dag.depends_on[b] |
| 138 | assert b in dag.required_by[a] |
| 139 | |
| 140 | def test_merged_ids_populated(self) -> None: |
| 141 | a, b = _ids(2) |
| 142 | dag = build_dag([(b, a)], merged_ids=[a]) |
| 143 | assert a in dag.merged_ids |
| 144 | assert b not in dag.merged_ids |
| 145 | |
| 146 | def test_number_by_id_populated(self) -> None: |
| 147 | a, b = _ids(2) |
| 148 | dag = build_dag([(b, a)], number_by_id={a: 1, b: 2}) |
| 149 | assert dag.number_by_id[a] == 1 |
| 150 | assert dag.number_by_id[b] == 2 |
| 151 | |
| 152 | |
| 153 | # ───────────────────────────────────────────────────────────────────────────── |
| 154 | # Tier 1 — Unit: topological_sort |
| 155 | # ───────────────────────────────────────────────────────────────────────────── |
| 156 | |
| 157 | |
| 158 | class TestTopologicalSort: |
| 159 | def test_empty_dag(self) -> None: |
| 160 | dag = build_dag([]) |
| 161 | assert topological_sort(dag) == [] |
| 162 | |
| 163 | def test_linear_chain_abc(self) -> None: |
| 164 | a, b, c = _ids(3) |
| 165 | dag = build_dag([(b, a), (c, b)], number_by_id={a: 1, b: 2, c: 3}) |
| 166 | order = topological_sort(dag) |
| 167 | assert order.index(a) < order.index(b) < order.index(c) |
| 168 | |
| 169 | def test_diamond_shape(self) -> None: |
| 170 | # A → B, A → C, B → D, C → D (D depends on B and C, which both depend on A) |
| 171 | a, b, c, d = _ids(4) |
| 172 | dag = build_dag([(b, a), (c, a), (d, b), (d, c)]) |
| 173 | order = topological_sort(dag) |
| 174 | assert order.index(a) < order.index(b) |
| 175 | assert order.index(a) < order.index(c) |
| 176 | assert order.index(b) < order.index(d) |
| 177 | assert order.index(c) < order.index(d) |
| 178 | |
| 179 | def test_multi_root(self) -> None: |
| 180 | a, b, c = _ids(3) |
| 181 | # A and B are independent roots; C depends on both |
| 182 | dag = build_dag([(c, a), (c, b)]) |
| 183 | order = topological_sort(dag) |
| 184 | assert order.index(a) < order.index(c) |
| 185 | assert order.index(b) < order.index(c) |
| 186 | |
| 187 | def test_merged_nodes_excluded_from_output(self) -> None: |
| 188 | a, b = _ids(2) |
| 189 | dag = build_dag([(b, a)], merged_ids=[a]) |
| 190 | order = topological_sort(dag) |
| 191 | assert a not in order |
| 192 | assert b in order |
| 193 | |
| 194 | def test_cycle_two_nodes_raises(self) -> None: |
| 195 | a, b = _ids(2) |
| 196 | dag = build_dag([(a, b), (b, a)]) |
| 197 | with pytest.raises(CycleError) as exc_info: |
| 198 | topological_sort(dag) |
| 199 | assert a in exc_info.value.cycle_ids or b in exc_info.value.cycle_ids |
| 200 | |
| 201 | def test_cycle_three_nodes_raises(self) -> None: |
| 202 | a, b, c = _ids(3) |
| 203 | dag = build_dag([(b, a), (c, b), (a, c)]) # A←B←C←A |
| 204 | with pytest.raises(CycleError) as exc_info: |
| 205 | topological_sort(dag) |
| 206 | assert len(exc_info.value.cycle_ids) >= 2 |
| 207 | |
| 208 | def test_cycle_error_message_contains_ids(self) -> None: |
| 209 | a, b = _ids(2) |
| 210 | dag = build_dag([(a, b), (b, a)]) |
| 211 | with pytest.raises(CycleError) as exc_info: |
| 212 | topological_sort(dag) |
| 213 | msg = str(exc_info.value) |
| 214 | assert "cycle" in msg.lower() |
| 215 | |
| 216 | def test_merged_breaks_cycle(self) -> None: |
| 217 | a, b = _ids(2) |
| 218 | # A depends on B, B depends on A — but A is merged, so B is free |
| 219 | dag = build_dag([(a, b), (b, a)], merged_ids=[a]) |
| 220 | order = topological_sort(dag) |
| 221 | assert b in order |
| 222 | assert a not in order |
| 223 | |
| 224 | |
| 225 | # ───────────────────────────────────────────────────────────────────────────── |
| 226 | # Tier 1 — Unit: detect_cycle |
| 227 | # ───────────────────────────────────────────────────────────────────────────── |
| 228 | |
| 229 | |
| 230 | class TestDetectCycle: |
| 231 | def test_no_cycle_returns_false(self) -> None: |
| 232 | a, b = _ids(2) |
| 233 | dag = build_dag([(b, a)]) |
| 234 | assert detect_cycle(dag) is False |
| 235 | |
| 236 | def test_cycle_returns_true(self) -> None: |
| 237 | a, b = _ids(2) |
| 238 | dag = build_dag([(a, b), (b, a)]) |
| 239 | assert detect_cycle(dag) is True |
| 240 | |
| 241 | def test_no_side_effects_on_dag(self) -> None: |
| 242 | a, b, c = _ids(3) |
| 243 | dag = build_dag([(b, a), (c, b)]) |
| 244 | detect_cycle(dag) |
| 245 | assert c in dag.depends_on |
| 246 | |
| 247 | |
| 248 | # ───────────────────────────────────────────────────────────────────────────── |
| 249 | # Tier 1 — Unit: blocked_by_numbers / blocks_numbers / is_blocked |
| 250 | # ───────────────────────────────────────────────────────────────────────────── |
| 251 | |
| 252 | |
| 253 | class TestBlockedByAndBlocks: |
| 254 | def test_no_dependencies_not_blocked(self) -> None: |
| 255 | a = _ids(1)[0] |
| 256 | dag = build_dag([], number_by_id={a: 1}) |
| 257 | assert blocked_by_numbers(dag, a) == [] |
| 258 | assert is_blocked(dag, a) is False |
| 259 | |
| 260 | def test_live_dependency_blocks(self) -> None: |
| 261 | a, b = _ids(2) |
| 262 | dag = build_dag([(b, a)], number_by_id={a: 1, b: 2}) |
| 263 | assert blocked_by_numbers(dag, b) == [1] |
| 264 | assert is_blocked(dag, b) is True |
| 265 | |
| 266 | def test_merged_dependency_not_blocking(self) -> None: |
| 267 | a, b = _ids(2) |
| 268 | dag = build_dag([(b, a)], merged_ids=[a], number_by_id={a: 1, b: 2}) |
| 269 | assert blocked_by_numbers(dag, b) == [] |
| 270 | assert is_blocked(dag, b) is False |
| 271 | |
| 272 | def test_partial_merge_still_blocked(self) -> None: |
| 273 | a, b, c = _ids(3) |
| 274 | # C depends on both A and B; only A merged |
| 275 | dag = build_dag([(c, a), (c, b)], merged_ids=[a], number_by_id={a: 1, b: 2, c: 3}) |
| 276 | assert blocked_by_numbers(dag, c) == [2] # B still unmerged |
| 277 | assert is_blocked(dag, c) is True |
| 278 | |
| 279 | def test_blocks_numbers(self) -> None: |
| 280 | a, b, c = _ids(3) |
| 281 | # B and C both depend on A |
| 282 | dag = build_dag([(b, a), (c, a)], number_by_id={a: 1, b: 2, c: 3}) |
| 283 | assert blocks_numbers(dag, a) == [2, 3] |
| 284 | |
| 285 | def test_blocks_excludes_merged_waiters(self) -> None: |
| 286 | a, b = _ids(2) |
| 287 | dag = build_dag([(b, a)], merged_ids=[b], number_by_id={a: 1, b: 2}) |
| 288 | assert blocks_numbers(dag, a) == [] |
| 289 | |
| 290 | def test_blocked_by_sorted_ascending(self) -> None: |
| 291 | a, b, c, d = _ids(4) |
| 292 | dag = build_dag([(d, c), (d, b), (d, a)], number_by_id={a: 1, b: 2, c: 3, d: 4}) |
| 293 | result = blocked_by_numbers(dag, d) |
| 294 | assert result == sorted(result) |
| 295 | |
| 296 | |
| 297 | # ───────────────────────────────────────────────────────────────────────────── |
| 298 | # Tier 5 — Integration: DB-backed DAG operations |
| 299 | # ───────────────────────────────────────────────────────────────────────────── |
| 300 | |
| 301 | |
| 302 | class TestDagIntegration: |
| 303 | @pytest.mark.asyncio |
| 304 | async def test_create_proposal_persists_dependency_edges( |
| 305 | self, db_session: AsyncSession |
| 306 | ) -> None: |
| 307 | from sqlalchemy import select |
| 308 | from musehub.db.musehub_repo_models import MusehubBranch, MusehubRepo |
| 309 | from musehub.db.musehub_social_models import MusehubProposal, MusehubProposalDependency |
| 310 | |
| 311 | repo_id = await _make_repo(db_session) |
| 312 | await _make_branch(db_session, repo_id, "feat/p1") |
| 313 | await _make_branch(db_session, repo_id, "feat/p2") |
| 314 | await _make_branch(db_session, repo_id, "dev") |
| 315 | |
| 316 | p1 = await _create_proposal(db_session, repo_id, from_branch="feat/p1", number=1) |
| 317 | p2 = await _create_proposal( |
| 318 | db_session, repo_id, from_branch="feat/p2", number=2, depends_on=[p1.proposal_id] |
| 319 | ) |
| 320 | |
| 321 | edge_rows = list( |
| 322 | ( |
| 323 | await db_session.execute( |
| 324 | select(MusehubProposalDependency).where( |
| 325 | MusehubProposalDependency.dependent_proposal_id == p2.proposal_id |
| 326 | ) |
| 327 | ) |
| 328 | ).scalars() |
| 329 | ) |
| 330 | assert len(edge_rows) == 1 |
| 331 | assert edge_rows[0].dependency_proposal_id == p1.proposal_id |
| 332 | |
| 333 | @pytest.mark.asyncio |
| 334 | async def test_create_proposal_rejects_unknown_dependency( |
| 335 | self, db_session: AsyncSession |
| 336 | ) -> None: |
| 337 | repo_id = await _make_repo(db_session) |
| 338 | await _make_branch(db_session, repo_id, "feat/p1") |
| 339 | await _make_branch(db_session, repo_id, "dev") |
| 340 | |
| 341 | fake_id = "sha256:" + "f" * 64 |
| 342 | with pytest.raises(ValueError, match="unknown proposal IDs"): |
| 343 | await _create_proposal( |
| 344 | db_session, repo_id, from_branch="feat/p1", depends_on=[fake_id] |
| 345 | ) |
| 346 | |
| 347 | @pytest.mark.asyncio |
| 348 | async def test_create_proposal_rejects_cycle( |
| 349 | self, db_session: AsyncSession |
| 350 | ) -> None: |
| 351 | from musehub.services.proposal_dag import create_dependency_edges |
| 352 | |
| 353 | repo_id = await _make_repo(db_session) |
| 354 | await _make_branch(db_session, repo_id, "feat/p1") |
| 355 | await _make_branch(db_session, repo_id, "feat/p2") |
| 356 | await _make_branch(db_session, repo_id, "dev") |
| 357 | |
| 358 | p1 = await _create_proposal(db_session, repo_id, from_branch="feat/p1", number=1) |
| 359 | p2 = await _create_proposal( |
| 360 | db_session, repo_id, from_branch="feat/p2", number=2, depends_on=[p1.proposal_id] |
| 361 | ) |
| 362 | # p2 depends on p1. Adding p1 depends-on p2 would create a cycle. |
| 363 | with pytest.raises(CycleError): |
| 364 | await create_dependency_edges( |
| 365 | db_session, p1.proposal_id, [p2.proposal_id] |
| 366 | ) |
| 367 | |
| 368 | @pytest.mark.asyncio |
| 369 | async def test_enrich_batch_populates_blocked_by( |
| 370 | self, db_session: AsyncSession |
| 371 | ) -> None: |
| 372 | from musehub.services.musehub_proposals import enrich_proposal_list_batch |
| 373 | |
| 374 | repo_id = await _make_repo(db_session) |
| 375 | await _make_branch(db_session, repo_id, "feat/p1") |
| 376 | await _make_branch(db_session, repo_id, "feat/p2") |
| 377 | await _make_branch(db_session, repo_id, "dev") |
| 378 | |
| 379 | p1_resp = await _create_proposal(db_session, repo_id, from_branch="feat/p1", number=1) |
| 380 | p2_resp = await _create_proposal( |
| 381 | db_session, repo_id, from_branch="feat/p2", number=2, depends_on=[p1_resp.proposal_id] |
| 382 | ) |
| 383 | |
| 384 | from musehub.db.musehub_repo_models import MusehubBranch, MusehubRepo |
| 385 | from musehub.db.musehub_social_models import MusehubProposal, MusehubProposalDependency |
| 386 | from sqlalchemy import select |
| 387 | p1_orm = (await db_session.execute( |
| 388 | select(MusehubProposal).where(MusehubProposal.proposal_id == p1_resp.proposal_id) |
| 389 | )).scalar_one() |
| 390 | p2_orm = (await db_session.execute( |
| 391 | select(MusehubProposal).where(MusehubProposal.proposal_id == p2_resp.proposal_id) |
| 392 | )).scalar_one() |
| 393 | |
| 394 | entries = await enrich_proposal_list_batch([p1_orm, p2_orm], db_session) |
| 395 | by_id = {e.proposal_id: e for e in entries} |
| 396 | |
| 397 | # p2 is blocked by p1 |
| 398 | p2_entry = by_id[p2_orm.proposal_id] |
| 399 | assert p2_entry.is_blocked is True |
| 400 | assert p1_orm.proposal_number in p2_entry.blocked_by |
| 401 | |
| 402 | # p1 blocks p2 |
| 403 | p1_entry = by_id[p1_orm.proposal_id] |
| 404 | assert p2_orm.proposal_number in p1_entry.blocks |
| 405 | assert p1_entry.is_blocked is False |
| 406 | |
| 407 | |
| 408 | @pytest.mark.asyncio |
| 409 | async def test_all_merge_conditions_false_while_dep_unmerged( |
| 410 | self, db_session: AsyncSession |
| 411 | ) -> None: |
| 412 | from musehub.services.musehub_proposals import enrich_proposal_list_batch |
| 413 | from musehub.db.musehub_repo_models import MusehubBranch, MusehubRepo |
| 414 | from musehub.db.musehub_social_models import MusehubProposal, MusehubProposalDependency |
| 415 | from sqlalchemy import select |
| 416 | |
| 417 | repo_id = await _make_repo(db_session) |
| 418 | await _make_branch(db_session, repo_id, "feat/p1") |
| 419 | await _make_branch(db_session, repo_id, "feat/p2") |
| 420 | await _make_branch(db_session, repo_id, "dev") |
| 421 | |
| 422 | p1 = await _create_proposal(db_session, repo_id, from_branch="feat/p1", number=1) |
| 423 | p2_orm = await _create_proposal( |
| 424 | db_session, repo_id, from_branch="feat/p2", number=2, depends_on=[p1.proposal_id] |
| 425 | ) |
| 426 | |
| 427 | p2_fresh = (await db_session.execute( |
| 428 | select(MusehubProposal).where(MusehubProposal.proposal_id == p2_orm.proposal_id) |
| 429 | )).scalar_one() |
| 430 | |
| 431 | entries = await enrich_proposal_list_batch([p2_fresh], db_session) |
| 432 | assert entries[0].all_merge_conditions_met is False |
| 433 | |
| 434 | @pytest.mark.asyncio |
| 435 | async def test_merge_proposal_gated_by_unmerged_dep( |
| 436 | self, db_session: AsyncSession |
| 437 | ) -> None: |
| 438 | from musehub.services.musehub_proposals import merge_proposal |
| 439 | |
| 440 | repo_id = await _make_repo(db_session) |
| 441 | await _make_branch(db_session, repo_id, "feat/p1") |
| 442 | await _make_branch(db_session, repo_id, "feat/p2") |
| 443 | await _make_branch(db_session, repo_id, "dev") |
| 444 | |
| 445 | p1 = await _create_proposal(db_session, repo_id, from_branch="feat/p1", number=1) |
| 446 | p2_orm = await _create_proposal( |
| 447 | db_session, repo_id, from_branch="feat/p2", number=2, depends_on=[p1.proposal_id] |
| 448 | ) |
| 449 | |
| 450 | with pytest.raises(RuntimeError, match="unmerged dependencies"): |
| 451 | await merge_proposal(db_session, repo_id, p2_orm.proposal_id) |