gabriel / muse public
test_phase3_noncmt_bfs_migration.py python
150 lines 5.7 KB
Raw
sha256:51ce277f663e01a43eaffbe77509b1de7ac2d4251b55d23306304bcdeb92c90d feat(pack): delta-encode snapshots in MPackBundle wire format Sonnet 4.6 minor ⚠ breaking 120 days ago
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
21
22 # ---------------------------------------------------------------------------
23 # shard._connected_components
24 # ---------------------------------------------------------------------------
25
26 class TestShardConnectedComponents:
27 def _fn(self):
28 from muse.cli.commands import shard as shard_module
29 return shard_module._connected_components
30
31 def test_structural_no_inline_dfs(self) -> None:
32 """_connected_components must not use an inline stack-based DFS after migration."""
33 src = inspect.getsource(self._fn())
34 assert "while stack:" not in src and "stack.pop()" not in src, (
35 "shard._connected_components still uses an inline DFS stack — "
36 "migrate to walk_dag(order='dfs')"
37 )
38
39 def test_single_node_single_component(self) -> None:
40 result = self._fn()(["a"], [])
41 assert len(result) == 1
42 assert result[0] == frozenset({"a"})
43
44 def test_two_connected_nodes_one_component(self) -> None:
45 result = self._fn()(["a", "b"], [("a", "b")])
46 assert len(result) == 1
47 assert result[0] == frozenset({"a", "b"})
48
49 def test_two_disconnected_nodes_two_components(self) -> None:
50 result = self._fn()(["a", "b"], [])
51 assert len(result) == 2
52 components = {frozenset(c) for c in result}
53 assert frozenset({"a"}) in components
54 assert frozenset({"b"}) in components
55
56 def test_triangle_one_component(self) -> None:
57 result = self._fn()(["a", "b", "c"], [("a", "b"), ("b", "c"), ("a", "c")])
58 assert len(result) == 1
59 assert result[0] == frozenset({"a", "b", "c"})
60
61 def test_two_disconnected_pairs(self) -> None:
62 result = self._fn()(["a", "b", "c", "d"], [("a", "b"), ("c", "d")])
63 assert len(result) == 2
64 components = {frozenset(c) for c in result}
65 assert frozenset({"a", "b"}) in components
66 assert frozenset({"c", "d"}) in components
67
68 def test_edges_are_undirected(self) -> None:
69 """Edge (a, b) means both a→b and b→a for connectivity."""
70 result = self._fn()(["a", "b"], [("a", "b")])
71 assert len(result) == 1
72 assert "a" in result[0] and "b" in result[0]
73
74 def test_empty_input(self) -> None:
75 assert self._fn()([], []) == []
76
77 def test_no_node_duplicated_across_components(self) -> None:
78 """Every node appears in exactly one component."""
79 files = ["a", "b", "c", "d", "e"]
80 edges = [("a", "b"), ("c", "d")]
81 result = self._fn()(files, edges)
82 all_nodes = [n for comp in result for n in comp]
83 assert len(all_nodes) == len(set(all_nodes))
84 assert set(all_nodes) == set(files)
85
86
87 # ---------------------------------------------------------------------------
88 # identity/dag._DAG.would_cycle
89 # ---------------------------------------------------------------------------
90
91 class TestDagWouldCycle:
92 def _cls(self):
93 from muse.plugins.identity import dag as dag_module
94 return dag_module._DAG
95
96 def test_structural_no_inline_dfs(self) -> None:
97 """_DAG.would_cycle must not use an inline DFS stack after migration."""
98 src = inspect.getsource(self._cls().would_cycle)
99 assert "while stack:" not in src and "stack.pop()" not in src, (
100 "identity/_DAG.would_cycle still uses an inline DFS stack — "
101 "migrate to walk_dag(order='dfs')"
102 )
103
104 def test_self_loop_is_cycle(self) -> None:
105 dag = self._cls()()
106 assert dag.would_cycle("a", "a") is True
107
108 def test_no_edges_no_cycle(self) -> None:
109 dag = self._cls()()
110 assert dag.would_cycle("a", "b") is False
111
112 def test_direct_forward_edge_no_cycle(self) -> None:
113 """a→b exists; adding a→b again is fine — no back-edge to a."""
114 dag = self._cls()()
115 dag.add_edge("a", "b")
116 assert dag.would_cycle("a", "b") is False
117
118 def test_back_edge_is_cycle(self) -> None:
119 """a→b exists; b→a would create a cycle."""
120 dag = self._cls()()
121 dag.add_edge("a", "b")
122 assert dag.would_cycle("b", "a") is True
123
124 def test_transitive_cycle(self) -> None:
125 """a→b→c exists; c→a would create a transitive cycle."""
126 dag = self._cls()()
127 dag.add_edge("a", "b")
128 dag.add_edge("b", "c")
129 assert dag.would_cycle("c", "a") is True
130
131 def test_no_transitive_cycle(self) -> None:
132 """a→b→c exists; d→a is fine (d is not reachable from a)."""
133 dag = self._cls()()
134 dag.add_edge("a", "b")
135 dag.add_edge("b", "c")
136 assert dag.would_cycle("d", "a") is False
137
138 def test_diamond_cycle_detection(self) -> None:
139 """a→b, a→c, b→d, c→d; d→a would cycle."""
140 dag = self._cls()()
141 dag.add_edge("a", "b")
142 dag.add_edge("a", "c")
143 dag.add_edge("b", "d")
144 dag.add_edge("c", "d")
145 assert dag.would_cycle("d", "a") is True
146
147 def test_unrelated_nodes_no_cycle(self) -> None:
148 dag = self._cls()()
149 dag.add_edge("x", "y")
150 assert dag.would_cycle("a", "b") is False
File History 1 commit
sha256:51ce277f663e01a43eaffbe77509b1de7ac2d4251b55d23306304bcdeb92c90d feat(pack): delta-encode snapshots in MPackBundle wire format Sonnet 4.6 minor ⚠ 120 days ago