test_phase3_noncmt_bfs_migration.py
file-level
1
files
1
commits
0
hotspots
0
🧊 dead
0
💥 blast risk
| 1 | """TDD Phase 3 — migrate non-commit graph BFS/DFS to walk_dag. |
| 2 | |
| 3 | Target sites |
| 4 | ------------ |
| 5 | shard._connected_components — DFS connected-components over file coupling graph |
| 6 | identity/dag._DAG.would_cycle — DFS cycle detection for identity relationship DAG |
| 7 | |
| 8 | Intentionally NOT migrated |
| 9 | -------------------------- |
| 10 | callgraph.transitive_callers / transitive_callees: output format is |
| 11 | {depth: [name, ...]}, which requires tracking BFS depth alongside nodes. |
| 12 | walk_dag yields a flat node stream — encoding depth into the node type |
| 13 | (e.g. (name, depth) tuples) would make the code harder to read. These |
| 14 | functions have a genuinely different shape and are a sanctioned exception. |
| 15 | """ |
| 16 | |
| 17 | from __future__ import annotations |
| 18 | |
| 19 | import inspect |
| 20 | import types |
| 21 | |
| 22 | |
| 23 | # --------------------------------------------------------------------------- |
| 24 | # shard._connected_components |
| 25 | # --------------------------------------------------------------------------- |
| 26 | |
| 27 | class TestShardConnectedComponents: |
| 28 | def _fn(self) -> types.FunctionType: |
| 29 | from muse.cli.commands import shard as shard_module |
| 30 | return shard_module._connected_components |
| 31 | |
| 32 | def test_structural_no_inline_dfs(self) -> None: |
| 33 | """_connected_components must not use an inline stack-based DFS after migration.""" |
| 34 | src = inspect.getsource(self._fn()) |
| 35 | assert "while stack:" not in src and "stack.pop()" not in src, ( |
| 36 | "shard._connected_components still uses an inline DFS stack — " |
| 37 | "migrate to walk_dag(order='dfs')" |
| 38 | ) |
| 39 | |
| 40 | def test_single_node_single_component(self) -> None: |
| 41 | result = self._fn()(["a"], []) |
| 42 | assert len(result) == 1 |
| 43 | assert result[0] == frozenset({"a"}) |
| 44 | |
| 45 | def test_two_connected_nodes_one_component(self) -> None: |
| 46 | result = self._fn()(["a", "b"], [("a", "b")]) |
| 47 | assert len(result) == 1 |
| 48 | assert result[0] == frozenset({"a", "b"}) |
| 49 | |
| 50 | def test_two_disconnected_nodes_two_components(self) -> None: |
| 51 | result = self._fn()(["a", "b"], []) |
| 52 | assert len(result) == 2 |
| 53 | components = {frozenset(c) for c in result} |
| 54 | assert frozenset({"a"}) in components |
| 55 | assert frozenset({"b"}) in components |
| 56 | |
| 57 | def test_triangle_one_component(self) -> None: |
| 58 | result = self._fn()(["a", "b", "c"], [("a", "b"), ("b", "c"), ("a", "c")]) |
| 59 | assert len(result) == 1 |
| 60 | assert result[0] == frozenset({"a", "b", "c"}) |
| 61 | |
| 62 | def test_two_disconnected_pairs(self) -> None: |
| 63 | result = self._fn()(["a", "b", "c", "d"], [("a", "b"), ("c", "d")]) |
| 64 | assert len(result) == 2 |
| 65 | components = {frozenset(c) for c in result} |
| 66 | assert frozenset({"a", "b"}) in components |
| 67 | assert frozenset({"c", "d"}) in components |
| 68 | |
| 69 | def test_edges_are_undirected(self) -> None: |
| 70 | """Edge (a, b) means both a→b and b→a for connectivity.""" |
| 71 | result = self._fn()(["a", "b"], [("a", "b")]) |
| 72 | assert len(result) == 1 |
| 73 | assert "a" in result[0] and "b" in result[0] |
| 74 | |
| 75 | def test_empty_input(self) -> None: |
| 76 | assert self._fn()([], []) == [] |
| 77 | |
| 78 | def test_no_node_duplicated_across_components(self) -> None: |
| 79 | """Every node appears in exactly one component.""" |
| 80 | files = ["a", "b", "c", "d", "e"] |
| 81 | edges = [("a", "b"), ("c", "d")] |
| 82 | result = self._fn()(files, edges) |
| 83 | all_nodes = [n for comp in result for n in comp] |
| 84 | assert len(all_nodes) == len(set(all_nodes)) |
| 85 | assert set(all_nodes) == set(files) |
| 86 | |
| 87 | |
| 88 | # --------------------------------------------------------------------------- |
| 89 | # identity/dag._DAG.would_cycle |
| 90 | # --------------------------------------------------------------------------- |
| 91 | |
| 92 | class TestDagWouldCycle: |
| 93 | def _cls(self) -> type: |
| 94 | from muse.plugins.identity import dag as dag_module |
| 95 | return dag_module._DAG |
| 96 | |
| 97 | def test_structural_no_inline_dfs(self) -> None: |
| 98 | """_DAG.would_cycle must not use an inline DFS stack after migration.""" |
| 99 | src = inspect.getsource(self._cls().would_cycle) |
| 100 | assert "while stack:" not in src and "stack.pop()" not in src, ( |
| 101 | "identity/_DAG.would_cycle still uses an inline DFS stack — " |
| 102 | "migrate to walk_dag(order='dfs')" |
| 103 | ) |
| 104 | |
| 105 | def test_self_loop_is_cycle(self) -> None: |
| 106 | dag = self._cls()() |
| 107 | assert dag.would_cycle("a", "a") is True |
| 108 | |
| 109 | def test_no_edges_no_cycle(self) -> None: |
| 110 | dag = self._cls()() |
| 111 | assert dag.would_cycle("a", "b") is False |
| 112 | |
| 113 | def test_direct_forward_edge_no_cycle(self) -> None: |
| 114 | """a→b exists; adding a→b again is fine — no back-edge to a.""" |
| 115 | dag = self._cls()() |
| 116 | dag.add_edge("a", "b") |
| 117 | assert dag.would_cycle("a", "b") is False |
| 118 | |
| 119 | def test_back_edge_is_cycle(self) -> None: |
| 120 | """a→b exists; b→a would create a cycle.""" |
| 121 | dag = self._cls()() |
| 122 | dag.add_edge("a", "b") |
| 123 | assert dag.would_cycle("b", "a") is True |
| 124 | |
| 125 | def test_transitive_cycle(self) -> None: |
| 126 | """a→b→c exists; c→a would create a transitive cycle.""" |
| 127 | dag = self._cls()() |
| 128 | dag.add_edge("a", "b") |
| 129 | dag.add_edge("b", "c") |
| 130 | assert dag.would_cycle("c", "a") is True |
| 131 | |
| 132 | def test_no_transitive_cycle(self) -> None: |
| 133 | """a→b→c exists; d→a is fine (d is not reachable from a).""" |
| 134 | dag = self._cls()() |
| 135 | dag.add_edge("a", "b") |
| 136 | dag.add_edge("b", "c") |
| 137 | assert dag.would_cycle("d", "a") is False |
| 138 | |
| 139 | def test_diamond_cycle_detection(self) -> None: |
| 140 | """a→b, a→c, b→d, c→d; d→a would cycle.""" |
| 141 | dag = self._cls()() |
| 142 | dag.add_edge("a", "b") |
| 143 | dag.add_edge("a", "c") |
| 144 | dag.add_edge("b", "d") |
| 145 | dag.add_edge("c", "d") |
| 146 | assert dag.would_cycle("d", "a") is True |
| 147 | |
| 148 | def test_unrelated_nodes_no_cycle(self) -> None: |
| 149 | dag = self._cls()() |
| 150 | dag.add_edge("x", "y") |
| 151 | assert dag.would_cycle("a", "b") is False |