entangle.py python
623 lines 22.3 KB
Raw
sha256:cf6265cea8c21d9228d90dec13ef6ec2dab5103d466db9cc4590681832de4bf8 docs(KD-STAGING): sync governance after KD-6b DONE Human 13 days ago
1 """muse code entangle — hidden symbol-pair entanglement detector.
2
3 ``muse code coupling`` works at the file level. ``muse code entangle`` goes
4 one level deeper and works at the **symbol level**: it finds *pairs of
5 symbols* that consistently change in the same commit but have **no structural
6 import or call-graph link** between them.
7
8 These are the hidden "keep-in-sync" relationships that nobody documented —
9 the ones that cause mysterious bugs when one side is updated and the other is
10 forgotten.
11
12 Why this is impossible in Git
13 ------------------------------
14 Git sees ``billing.py`` and ``serializers.py`` changed in the same commit.
15 It has no way to say *which functions* changed, so it cannot report
16 symbol-pair co-change.
17
18 Muse stores a ``structured_delta`` with every commit. Each delta records
19 every symbol operation — insert, delete, replace — with its precise address.
20 ``entangle`` mines this history to surface the statistical signal that file
21 diffing cannot see.
22
23 Exclusions
24 ----------
25 - Import pseudo-symbols (``::import::``) are excluded.
26 - Commits touching more than ``_MAX_SYMBOLS_PER_COMMIT`` distinct symbols are
27 skipped — they are mass-refactors that produce O(N²) noise.
28 - The same-file constraint can be relaxed with ``--include-same-file``.
29 - Results where either symbol is in a test file are surfaced with a
30 ``[test]`` badge.
31
32 Structural-link check
33 ---------------------
34 Two symbols are considered **structurally linked** if the file that
35 contains *symbol A* has an import record pointing to the module/file of
36 *symbol B*, or vice versa. This check is intentionally conservative —
37 it only looks at top-level import symbols in the current snapshot. A
38 pair that is flagged as "entangled" despite an obvious import may be using
39 an indirect import chain; that is still interesting to know.
40
41 Usage::
42
43 muse code entangle
44 muse code entangle --top 20
45 muse code entangle --min-rate 0.5 # only pairs that co-changed > 50 % of the time
46 muse code entangle --symbol billing.py::Invoice.compute_total
47 muse code entangle --include-same-file # include pairs in the same file
48 muse code entangle --since HEAD~30
49 muse code entangle --json
50
51 Output::
52
53 Symbol entanglement — HEAD (47 commits · 3 entangled pairs)
54
55 # SYMBOL A ↔ SYMBOL B RATE CO-CHANGES
56 1 billing.py::Invoice.compute_total ↔ serializers.py::to_json 91% 10 / 11
57 2 auth.py::verify_identity ↔ middleware.py::check_token 80% 8 / 10
58 3 models.py::User.save ↔ events.py::emit_user_event 75% 6 / 8 [cross-file, no import link]
59
60 ⚠️ These pairs change together but have no structural import link.
61 Consider adding documentation, a shared interface, or an explicit test.
62
63 JSON output (--json)::
64
65 {
66 "ref": "HEAD",
67 "commits_analysed": 47,
68 "truncated": false,
69 "filters": { "min_rate": 0.5, "min_co_changes": 2, "symbol": null, "include_same_file": false },
70 "pairs": [
71 {
72 "symbol_a": "billing.py::Invoice.compute_total",
73 "symbol_b": "serializers.py::to_json",
74 "file_a": "billing.py",
75 "file_b": "serializers.py",
76 "same_file": false,
77 "structurally_linked": false,
78 "co_changes": 10,
79 "commits_both_active": 11,
80 "co_change_rate": 0.91,
81 "a_in_test": false,
82 "b_in_test": false
83 }
84 ]
85 }
86 """
87
88 from __future__ import annotations
89
90 import argparse
91 import ast
92 import json
93 import logging
94 import pathlib
95 import re
96 import sys
97 from typing import TypedDict
98
99 from muse.core.errors import ExitCode
100 from muse.core.repo import read_repo_id, require_repo
101 from muse.core.store import (
102 JsonValue,
103 Manifest,
104 get_commit_snapshot_manifest,
105 read_current_branch,
106 resolve_commit_ref,
107 )
108 from muse.core.symbol_cache import load_symbol_cache
109 from muse.domain import DomainOp
110
111 type _ImportMap = dict[str, set[str]]
112 type _CounterMap = dict[str, int]
113 type _JsonFilters = dict[str, JsonValue]
114 from muse.plugins.code._query import (
115 flat_symbol_ops,
116 symbols_for_snapshot,
117 walk_commits_bfs,
118 )
119 from muse.core.validation import clamp_int, sanitize_display
120
121 logger = logging.getLogger(__name__)
122
123 # ── Constants ──────────────────────────────────────────────────────────────────
124
125 _DEFAULT_TOP = 20
126 _DEFAULT_MIN_CO_CHANGES = 2
127 _DEFAULT_MIN_RATE = 0.0
128 _DEFAULT_MAX_COMMITS = 10_000
129
130 # Skip commits with too many distinct symbols — they're mass-refactors.
131 _MAX_SYMBOLS_PER_COMMIT = 200
132
133 # Test-file heuristics.
134 _TEST_RE: tuple[re.Pattern[str], ...] = (
135 re.compile(r"(^|/)test_"),
136 re.compile(r"_test\.py$"),
137 re.compile(r"(^|/)tests/"),
138 re.compile(r"(^|/)spec/"),
139 re.compile(r"(^|/)conftest\.py$"),
140 )
141
142
143 def _is_test_file(path: str) -> bool:
144 return any(p.search(path) for p in _TEST_RE)
145
146
147 # ── TypedDict ──────────────────────────────────────────────────────────────────
148
149
150 class _EntangledPair(TypedDict):
151 symbol_a: str
152 symbol_b: str
153 file_a: str
154 file_b: str
155 same_file: bool
156 structurally_linked: bool
157 co_changes: int
158 commits_both_active: int
159 co_change_rate: float
160 a_in_test: bool
161 b_in_test: bool
162
163
164 # ── Helpers ────────────────────────────────────────────────────────────────────
165
166
167
168 def _module_name_from_path(file_path: str) -> str:
169 """Convert a file path to a rough Python module name.
170
171 ``muse/core/store.py`` → ``muse.core.store``
172 ``billing.py`` → ``billing``
173 """
174 stem = file_path.removesuffix(".py").removesuffix(".pyi")
175 return stem.replace("/", ".").replace("\\", ".")
176
177
178 def _build_import_map(
179 root: pathlib.Path,
180 manifest: Manifest,
181 ) -> _ImportMap:
182 """Return ``{file_path: {imported_module_name, ...}}`` from the snapshot.
183
184 We extract import pseudo-symbols from the symbol cache / AST parser.
185 These records have ``kind == "import"`` and ``qualified_name`` set to the
186 imported module name (e.g. ``muse.core.store`` or just ``store``).
187 """
188 cache = load_symbol_cache(root)
189 all_trees = symbols_for_snapshot(root, manifest, cache=cache)
190
191 import_map: _ImportMap = {}
192 for file_path, tree in all_trees.items():
193 mods: set[str] = set()
194 for rec in tree.values():
195 if rec.get("kind") == "import":
196 qn: str = rec.get("qualified_name") or rec.get("name") or ""
197 if qn:
198 mods.add(qn)
199 # Also record the top-level package for coarse matching.
200 mods.add(qn.split(".")[0])
201 import_map[file_path] = mods
202
203 return import_map
204
205
206 def _are_structurally_linked(
207 file_a: str,
208 file_b: str,
209 import_map: _ImportMap,
210 ) -> bool:
211 """Return True if either file imports the other (even partially).
212
213 We check whether any module name in the import set of file_a resembles
214 the module path of file_b, or vice versa. We use a suffix check rather
215 than exact match to handle aliased or re-exported imports.
216 """
217 mod_a = _module_name_from_path(file_a)
218 mod_b = _module_name_from_path(file_b)
219
220 imports_of_a = import_map.get(file_a, set())
221 imports_of_b = import_map.get(file_b, set())
222
223 # file_a imports file_b?
224 for imp in imports_of_a:
225 if mod_b.endswith(imp) or imp.endswith(mod_b) or imp == mod_b.split(".")[-1]:
226 return True
227 # file_b imports file_a?
228 for imp in imports_of_b:
229 if mod_a.endswith(imp) or imp.endswith(mod_a) or imp == mod_a.split(".")[-1]:
230 return True
231 return False
232
233
234 # ── Core algorithm ─────────────────────────────────────────────────────────────
235
236
237 def _collect_symbol_pairs(
238 root: pathlib.Path,
239 head_commit_id: str,
240 stop_at: str | None,
241 max_commits: int,
242 include_same_file: bool,
243 ) -> tuple[
244 dict[tuple[str, str], int], # co-change counts
245 dict[str, int], # how many commits each symbol was active in
246 int, # commits_analysed
247 bool, # truncated
248 ]:
249 """Single BFS pass: count symbol-pair co-changes.
250
251 Returns:
252 co_changes — ``(addr_a, addr_b) → commit count`` (a < b lexicographically)
253 active — ``addr → commit count where the symbol changed``
254 commits_analysed, truncated
255 """
256 commits, truncated = walk_commits_bfs(
257 root, head_commit_id, max_commits, stop_at_commit_id=stop_at
258 )
259
260 co_changes: dict[tuple[str, str], int] = {}
261 active: _CounterMap = {}
262
263 for commit in commits:
264 if commit.structured_delta is None:
265 continue
266 ops: list[DomainOp] = commit.structured_delta["ops"]
267
268 # Collect distinct symbol addresses changed in this commit,
269 # excluding import pseudo-symbols.
270 changed: list[str] = []
271 for op in flat_symbol_ops(ops):
272 addr: str = op["address"]
273 if "::import::" not in addr:
274 changed.append(addr)
275
276 # Skip mass-refactor commits.
277 if len(changed) > _MAX_SYMBOLS_PER_COMMIT:
278 continue
279
280 # Deduplicate within this commit (a symbol may appear >1 ops).
281 unique = list(dict.fromkeys(changed))
282
283 # Track per-symbol activity count.
284 for addr in unique:
285 active[addr] = active.get(addr, 0) + 1
286
287 # Count co-changing pairs.
288 for i in range(len(unique)):
289 for j in range(i + 1, len(unique)):
290 a, b = unique[i], unique[j]
291 # Canonical ordering so we always use the same dict key.
292 pair: tuple[str, str] = (a, b) if a <= b else (b, a)
293
294 fa = a.split("::")[0]
295 fb = b.split("::")[0]
296 if not include_same_file and fa == fb:
297 continue
298
299 co_changes[pair] = co_changes.get(pair, 0) + 1
300
301 return co_changes, active, len(commits), truncated
302
303
304 # ── Scoring + filtering ────────────────────────────────────────────────────────
305
306
307 def _build_pairs(
308 co_changes: dict[tuple[str, str], int],
309 active: _CounterMap,
310 import_map: _ImportMap,
311 min_co_changes: int,
312 min_rate: float,
313 symbol_filter: str | None,
314 top: int,
315 include_same_file: bool,
316 ) -> list[_EntangledPair]:
317 """Filter, score, and sort the co-change pairs."""
318 pairs: list[_EntangledPair] = []
319
320 for (a, b), count in co_changes.items():
321 if count < min_co_changes:
322 continue
323
324 fa = a.split("::")[0]
325 fb = b.split("::")[0]
326
327 # --symbol filter: only show pairs involving the requested symbol.
328 if symbol_filter is not None and symbol_filter not in (a, b):
329 continue
330
331 # How many commits were both symbols active?
332 # Use the lower of the two active counts as the "opportunity window".
333 active_a = active.get(a, count)
334 active_b = active.get(b, count)
335 both_active = min(active_a, active_b)
336 rate = count / both_active if both_active > 0 else 0.0
337
338 if rate < min_rate:
339 continue
340
341 linked = _are_structurally_linked(fa, fb, import_map)
342 # We only surface *unlinked* pairs — that's the entanglement signal.
343 # Unless the user provides --symbol to inspect a specific pair.
344 if linked and symbol_filter is None:
345 continue
346
347 pairs.append(_EntangledPair(
348 symbol_a=a,
349 symbol_b=b,
350 file_a=fa,
351 file_b=fb,
352 same_file=(fa == fb),
353 structurally_linked=linked,
354 co_changes=count,
355 commits_both_active=both_active,
356 co_change_rate=round(rate, 4),
357 a_in_test=_is_test_file(fa),
358 b_in_test=_is_test_file(fb),
359 ))
360
361 # Sort: highest co_change_rate first, then co_changes count, then address.
362 pairs.sort(key=lambda p: (-p["co_change_rate"], -p["co_changes"], p["symbol_a"]))
363 return pairs[:top]
364
365
366 # ── Formatters ─────────────────────────────────────────────────────────────────
367
368
369 def _print_table(
370 pairs: list[_EntangledPair],
371 ref: str,
372 commits_analysed: int,
373 truncated: bool,
374 since: str | None,
375 ) -> None:
376 scope = f"{since}..{ref}" if since else ref
377 trunc = " ⚠️ truncated" if truncated else ""
378 print(
379 f"\nSymbol entanglement — {scope}"
380 f" ({commits_analysed} commits · {len(pairs)} entangled pair(s){trunc})"
381 )
382 print("")
383
384 if not pairs:
385 print(" (no entangled symbol pairs found)")
386 print(
387 "\n All co-changing symbol pairs have a structural import link "
388 "— no hidden entanglement detected."
389 )
390 return
391
392 max_a = max(len(p["symbol_a"]) for p in pairs)
393 max_b = max(len(p["symbol_b"]) for p in pairs)
394 width = len(str(len(pairs)))
395 hdr = (
396 f" {'#':>{width}} "
397 f"{'SYMBOL A':<{max_a}} ↔ {'SYMBOL B':<{max_b}} "
398 f"{'RATE':>5} {'CO-CHANGES':>10}"
399 )
400 print(hdr)
401 print(" " + "─" * (len(hdr) - 2))
402
403 for i, p in enumerate(pairs, 1):
404 rate_pct = f"{round(p['co_change_rate'] * 100)} %"
405 co_str = f"{p['co_changes']} / {p['commits_both_active']}"
406 badges: list[str] = []
407 if p["a_in_test"] or p["b_in_test"]:
408 badges.append("[test]")
409 if p["same_file"]:
410 badges.append("[same-file]")
411 badge_str = " " + " ".join(badges) if badges else ""
412 print(
413 f" {i:>{width}} "
414 f"{sanitize_display(p['symbol_a']):<{max_a}} ↔ {sanitize_display(p['symbol_b']):<{max_b}} "
415 f"{rate_pct:>5} {co_str:>10}{badge_str}"
416 )
417
418 print(
419 "\n⚠️ These symbol pairs change together but share no import link."
420 "\n Consider adding docs, a shared interface, or an explicit integration test."
421 )
422
423
424 # ── CLI ────────────────────────────────────────────────────────────────────────
425
426
427 def register(
428 subparsers: "argparse._SubParsersAction[argparse.ArgumentParser]",
429 ) -> None:
430 """Register the entangle subcommand."""
431 parser = subparsers.add_parser(
432 "entangle",
433 help=(
434 "Find symbol pairs that always change together but have no "
435 "structural import link — hidden coupling."
436 ),
437 description=__doc__,
438 formatter_class=argparse.RawDescriptionHelpFormatter,
439 )
440 parser.add_argument(
441 "--top", "-n",
442 type=int, default=_DEFAULT_TOP, metavar="N",
443 help=f"Number of pairs to show (default: {_DEFAULT_TOP}).",
444 )
445 parser.add_argument(
446 "--min-co-changes",
447 type=int, default=_DEFAULT_MIN_CO_CHANGES, metavar="N",
448 dest="min_co_changes",
449 help=(
450 f"Minimum number of commits where both symbols co-changed "
451 f"(default: {_DEFAULT_MIN_CO_CHANGES})."
452 ),
453 )
454 parser.add_argument(
455 "--min-rate",
456 type=float, default=_DEFAULT_MIN_RATE, metavar="RATE",
457 dest="min_rate",
458 help=(
459 "Minimum co-change rate 0.0–1.0: fraction of commits where "
460 "both symbols were active that they co-changed "
461 f"(default: {_DEFAULT_MIN_RATE}). "
462 "E.g. --min-rate 0.5 = show only pairs that co-changed >50 %% of the time."
463 ),
464 )
465 parser.add_argument(
466 "--symbol", "-s",
467 default=None, metavar="ADDRESS", dest="symbol_filter",
468 help=(
469 "Focus on a single symbol: show all pairs it forms with other "
470 "symbols, including structurally-linked ones. "
471 "Address format: file.py::SymbolName"
472 ),
473 )
474 parser.add_argument(
475 "--since",
476 default=None, metavar="REF",
477 help="Limit analysis to commits reachable from HEAD but not from REF.",
478 )
479 parser.add_argument(
480 "--max-commits",
481 type=int, default=_DEFAULT_MAX_COMMITS, metavar="N",
482 dest="max_commits",
483 help=f"Maximum commits to scan (default: {_DEFAULT_MAX_COMMITS}).",
484 )
485 parser.add_argument(
486 "--include-same-file",
487 action="store_true", dest="include_same_file",
488 help=(
489 "Include symbol pairs within the same file. By default, "
490 "same-file pairs are excluded since same-file co-change is expected."
491 ),
492 )
493 parser.add_argument(
494 "--json",
495 action="store_true", dest="as_json",
496 help="Emit results as JSON.",
497 )
498 parser.set_defaults(func=run)
499
500
501 def run(args: argparse.Namespace) -> None:
502 """Find symbol pairs that always change together but share no import link.
503
504 Mines the commit history for symbol-level co-change patterns. Pairs
505 that co-change frequently but have no structural import link are
506 "entangled" — a hidden dependency that only shows up when one side is
507 changed and the other isn't.
508
509 The co-change *rate* is defined as::
510
511 co_changes / min(commits_where_A_changed, commits_where_B_changed)
512
513 A rate of 1.0 means the two symbols changed together every single time
514 either of them changed.
515 """
516 top: int = clamp_int(args.top, 1, 10_000, 'top')
517 min_co_changes: int = clamp_int(args.min_co_changes, 1, 100000, 'min_co_changes')
518 min_rate: float = args.min_rate
519 symbol_filter: str | None = args.symbol_filter
520 since: str | None = args.since
521 max_commits: int = clamp_int(args.max_commits, 1, 100_000, 'max_commits')
522 include_same_file: bool = args.include_same_file
523 as_json: bool = args.as_json
524
525 # ── Validation ────────────────────────────────────────────────────────────
526 if top < 1:
527 print("❌ --top must be >= 1.", file=sys.stderr)
528 raise SystemExit(ExitCode.USER_ERROR)
529 if min_co_changes < 1:
530 print("❌ --min-co-changes must be >= 1.", file=sys.stderr)
531 raise SystemExit(ExitCode.USER_ERROR)
532 if not (0.0 <= min_rate <= 1.0):
533 print("❌ --min-rate must be between 0.0 and 1.0.", file=sys.stderr)
534 raise SystemExit(ExitCode.USER_ERROR)
535 if max_commits < 1:
536 print("❌ --max-commits must be >= 1.", file=sys.stderr)
537 raise SystemExit(ExitCode.USER_ERROR)
538 if symbol_filter is not None and "::" not in symbol_filter:
539 print(
540 "❌ --symbol must be a qualified address (file.py::SymbolName).",
541 file=sys.stderr,
542 )
543 raise SystemExit(ExitCode.USER_ERROR)
544 if symbol_filter is not None and len(symbol_filter) > 500:
545 print("❌ --symbol address is too long (max 500 chars).", file=sys.stderr)
546 raise SystemExit(ExitCode.USER_ERROR)
547
548 # ── Repo setup ────────────────────────────────────────────────────────────
549 root = require_repo()
550
551 from muse.plugins.registry import read_domain
552 try:
553 if read_domain(root) == "knowtation":
554 from muse.plugins.knowtation.cli_hooks import run_entangle_for_vault
555 run_entangle_for_vault(root, args)
556 return
557 except Exception: # noqa: BLE001
558 pass
559
560 repo_id = read_repo_id(root)
561 branch = read_current_branch(root)
562
563 head = resolve_commit_ref(root, repo_id, branch, None)
564 if head is None:
565 print("❌ HEAD commit not found.", file=sys.stderr)
566 raise SystemExit(ExitCode.USER_ERROR)
567
568 stop_at: str | None = None
569 if since is not None:
570 since_commit = resolve_commit_ref(root, repo_id, branch, since)
571 if since_commit is None:
572 print(f"❌ Commit '{since}' not found.", file=sys.stderr)
573 raise SystemExit(ExitCode.USER_ERROR)
574 stop_at = since_commit.commit_id
575
576 # ── Phase 1: build import map from HEAD snapshot ──────────────────────────
577 manifest = get_commit_snapshot_manifest(root, head.commit_id) or {}
578 import_map = _build_import_map(root, manifest)
579
580 # ── Phase 2: mine co-changes in one BFS pass ──────────────────────────────
581 co_changes, active, commits_analysed, truncated = _collect_symbol_pairs(
582 root,
583 head_commit_id=head.commit_id,
584 stop_at=stop_at,
585 max_commits=max_commits,
586 include_same_file=include_same_file,
587 )
588
589 # ── Phase 3: filter + rank ────────────────────────────────────────────────
590 pairs = _build_pairs(
591 co_changes=co_changes,
592 active=active,
593 import_map=import_map,
594 min_co_changes=min_co_changes,
595 min_rate=min_rate,
596 symbol_filter=symbol_filter,
597 top=top,
598 include_same_file=include_same_file,
599 )
600
601 # ── Output ────────────────────────────────────────────────────────────────
602 ref = branch
603 filters: _JsonFilters = {
604 "min_rate": min_rate,
605 "min_co_changes": min_co_changes,
606 "symbol": symbol_filter,
607 "since": since,
608 "include_same_file": include_same_file,
609 "top": top,
610 "max_commits": max_commits,
611 }
612
613 if as_json:
614 print(json.dumps({
615 "ref": ref,
616 "commits_analysed": commits_analysed,
617 "truncated": truncated,
618 "filters": filters,
619 "pairs": [dict(p) for p in pairs],
620 }, indent=2))
621 return
622
623 _print_table(pairs, ref, commits_analysed, truncated, since)
File History 1 commit
sha256:cf6265cea8c21d9228d90dec13ef6ec2dab5103d466db9cc4590681832de4bf8 docs(KD-STAGING): sync governance after KD-6b DONE Human 13 days ago