test_selection.py
python
sha256:9ca3eeef4f199d5e8d0b21e50c384a2468e2c2477bd9b157f29fd0f7f06fddcd
feat: add muse reflog expire subcommand and reflog.expire-d…
Sonnet 4.6
patch
73 days ago
| 1 | """Symbol-graph–driven test selection for ``muse code test``. |
| 2 | |
| 3 | Given a set of changed symbol addresses (taken from ``muse diff`` or the |
| 4 | working-tree diff), this module identifies the minimal set of test functions |
| 5 | that exercise those symbols — without running a single test. |
| 6 | |
| 7 | How it works |
| 8 | ------------ |
| 9 | 1. Build the **forward call graph** for the committed snapshot (caller → callees). |
| 10 | 2. For every *test function* in the graph, perform a BFS through the forward |
| 11 | graph up to *depth* hops, accumulating the set of production symbols it |
| 12 | transitively calls. |
| 13 | 3. Invert the mapping: production symbol → list[test_node_ids]. |
| 14 | 4. For each changed symbol, look up which tests cover it. Tests that cover |
| 15 | *any* changed symbol are included in the result. |
| 16 | |
| 17 | Why this is better than file-name heuristics |
| 18 | --------------------------------------------- |
| 19 | File-name heuristics (``test_foo.py`` ↔ ``foo.py``) break the moment a |
| 20 | repository uses a non-obvious naming scheme, a shared test module, or a |
| 21 | parameterized fixture that exercises symbols from many files. The call graph |
| 22 | knows exactly what each test calls — it does not guess. |
| 23 | |
| 24 | Security |
| 25 | -------- |
| 26 | This module is purely **read-only and static**. It reads committed objects |
| 27 | from the content-addressed object store (SHA-256 verified blobs) and parses |
| 28 | them with Python's built-in ``ast`` module, which never executes code. |
| 29 | No working-tree file is written. No subprocess is spawned. |
| 30 | |
| 31 | Performance |
| 32 | ----------- |
| 33 | Blobs are read once and cached by the ``SymbolCache``. The call-graph BFS |
| 34 | is bounded by *depth* (default 3) and the size of the snapshot. On a 400- |
| 35 | file Python codebase a warm-cache run completes in <50 ms. |
| 36 | """ |
| 37 | |
| 38 | import logging |
| 39 | import pathlib |
| 40 | from collections.abc import Iterable |
| 41 | from typing import Literal, TypedDict |
| 42 | |
| 43 | from muse.core.callgraph_cache import CallGraphCache, load_callgraph_cache |
| 44 | from muse.core.paths import muse_dir as _muse_dir |
| 45 | from muse.core.types import Manifest |
| 46 | from muse.core.symbol_cache import SymbolCache, load_symbol_cache |
| 47 | |
| 48 | type SymbolIndex = dict[str, SymbolRecord] |
| 49 | type CoverageMap = dict[str, list[tuple[str, int]]] |
| 50 | type CounterMap = dict[str, int] |
| 51 | type TestListMap = dict[str, list[str]] |
| 52 | from muse.plugins.code._callgraph import ( |
| 53 | ForwardGraph, |
| 54 | build_forward_graph, |
| 55 | ) |
| 56 | from muse.plugins.code._query import is_semantic, symbols_for_snapshot |
| 57 | from muse.plugins.code.ast_parser import SymbolRecord |
| 58 | |
| 59 | logger = logging.getLogger(__name__) |
| 60 | |
| 61 | # --------------------------------------------------------------------------- |
| 62 | # Public type definitions |
| 63 | # --------------------------------------------------------------------------- |
| 64 | |
| 65 | class ChangedSymbol(TypedDict): |
| 66 | """A symbol that changed between two snapshots or in the working tree.""" |
| 67 | |
| 68 | address: str |
| 69 | """Fully-qualified symbol address: ``"path/to/file.py::FunctionName"``.""" |
| 70 | |
| 71 | change_kind: Literal["modified", "added", "deleted"] |
| 72 | """Whether the symbol body was modified, newly added, or removed.""" |
| 73 | |
| 74 | class SelectionTarget(TypedDict): |
| 75 | """A single pytest-addressable test target to execute.""" |
| 76 | |
| 77 | node_id: str |
| 78 | """Pytest node ID, e.g. ``"tests/test_foo.py::TestBar::test_baz"``.""" |
| 79 | |
| 80 | file: str |
| 81 | """The test file path, e.g. ``"tests/test_foo.py"``.""" |
| 82 | |
| 83 | reason: str |
| 84 | """Human-readable explanation of why this test was selected.""" |
| 85 | |
| 86 | confidence: float |
| 87 | """Selection confidence in [0.0, 1.0]: |
| 88 | |
| 89 | * 1.0 — test directly calls the changed symbol. |
| 90 | * 0.9 — test reaches changed symbol within depth ≤ 2. |
| 91 | * 0.7 — test reaches changed symbol via depth 3+ hops. |
| 92 | * 0.5 — test is in a file whose name matches the changed file's stem |
| 93 | (file-name heuristic, fallback only). |
| 94 | """ |
| 95 | |
| 96 | class SelectionResult(TypedDict): |
| 97 | """Result of a test-selection pass.""" |
| 98 | |
| 99 | changed_addresses: list[str] |
| 100 | """Addresses of every changed symbol that was considered.""" |
| 101 | |
| 102 | test_targets: list[SelectionTarget] |
| 103 | """Ordered list of tests to run (deduplicated, highest confidence first).""" |
| 104 | |
| 105 | covered_addresses: list[str] |
| 106 | """Subset of *changed_addresses* that have at least one covering test.""" |
| 107 | |
| 108 | uncovered_addresses: list[str] |
| 109 | """Changed symbols with no covering test — coverage gap alert.""" |
| 110 | |
| 111 | coverage_fraction: float |
| 112 | """``len(covered_addresses) / len(changed_addresses)`` in [0.0, 1.0].""" |
| 113 | |
| 114 | fallback_used: bool |
| 115 | """True if file-name heuristics were used for any target (graph miss).""" |
| 116 | |
| 117 | # --------------------------------------------------------------------------- |
| 118 | # Internal helpers |
| 119 | # --------------------------------------------------------------------------- |
| 120 | |
| 121 | def _is_test_file(path: str) -> bool: |
| 122 | """Return True if *path* is a test file by convention.""" |
| 123 | stem = pathlib.PurePosixPath(path).stem |
| 124 | name = pathlib.PurePosixPath(path).name |
| 125 | return ( |
| 126 | stem.startswith("test_") |
| 127 | or stem.endswith("_test") |
| 128 | or name == "conftest.py" |
| 129 | ) |
| 130 | |
| 131 | def _is_test_function(address: str, kind: str) -> bool: |
| 132 | """Return True if *address* refers to a test function or method.""" |
| 133 | parts = address.rsplit("::", 1) |
| 134 | if len(parts) != 2: |
| 135 | return False |
| 136 | name = parts[1] |
| 137 | return ( |
| 138 | kind in {"function", "method", "async_function", "async_method"} |
| 139 | and (name.startswith("test_") or name == "conftest") |
| 140 | ) |
| 141 | |
| 142 | def _confidence(depth: int) -> float: |
| 143 | """Map BFS depth to a confidence score.""" |
| 144 | if depth <= 1: |
| 145 | return 1.0 |
| 146 | if depth <= 2: |
| 147 | return 0.9 |
| 148 | return 0.7 |
| 149 | |
| 150 | # --------------------------------------------------------------------------- |
| 151 | # Core selection algorithm |
| 152 | # --------------------------------------------------------------------------- |
| 153 | |
| 154 | def _build_coverage_map( |
| 155 | forward_graph: ForwardGraph, |
| 156 | all_symbols: SymbolIndex, |
| 157 | max_depth: int, |
| 158 | ) -> CoverageMap: |
| 159 | """Return mapping from production-symbol bare name → list[(test_node_id, depth)]. |
| 160 | |
| 161 | Each value is a list of ``(test_address, bfs_depth)`` pairs. The BFS |
| 162 | starts from every test function and follows the *forward* call graph |
| 163 | (caller → callees) up to *max_depth* hops. At each hop we accumulate |
| 164 | the production symbols reached. |
| 165 | |
| 166 | ``all_symbols`` is a flat mapping of ``address → SymbolRecord`` |
| 167 | used to look up the ``kind`` field. |
| 168 | """ |
| 169 | coverage: CoverageMap = {} |
| 170 | |
| 171 | for addr, rec in all_symbols.items(): |
| 172 | kind = rec["kind"] |
| 173 | if not _is_test_function(addr, kind): |
| 174 | continue |
| 175 | file_part = addr.split("::")[0] |
| 176 | if not _is_test_file(file_part): |
| 177 | continue |
| 178 | |
| 179 | # BFS from this test function through the forward call graph. |
| 180 | bare_start = addr.rsplit("::", 1)[-1] |
| 181 | frontier: list[tuple[str, int]] = [(bare_start, 0)] |
| 182 | visited: set[str] = {bare_start} |
| 183 | |
| 184 | while frontier: |
| 185 | current, depth = frontier.pop(0) |
| 186 | if depth >= max_depth: |
| 187 | continue |
| 188 | for callee in forward_graph.get(current, frozenset()): |
| 189 | if callee in visited: |
| 190 | continue |
| 191 | visited.add(callee) |
| 192 | reach_depth = depth + 1 |
| 193 | bucket = coverage.setdefault(callee, []) |
| 194 | bucket.append((addr, reach_depth)) |
| 195 | frontier.append((callee, reach_depth)) |
| 196 | |
| 197 | return coverage |
| 198 | |
| 199 | def select_tests( |
| 200 | root: pathlib.Path, |
| 201 | changed: Iterable[ChangedSymbol], |
| 202 | manifest: Manifest, |
| 203 | *, |
| 204 | depth: int = 3, |
| 205 | cache: SymbolCache | None = None, |
| 206 | callgraph_cache: CallGraphCache | None = None, |
| 207 | ) -> SelectionResult: |
| 208 | """Select the minimal test set that covers *changed* symbols. |
| 209 | |
| 210 | Args: |
| 211 | root: Repository root (locates the object store and caches). |
| 212 | changed: Iterable of :class:`ChangedSymbol` from ``muse diff``. |
| 213 | manifest: Snapshot manifest mapping ``file_path → sha256``. Pass the |
| 214 | HEAD manifest to analyse the committed graph; pass the |
| 215 | working-tree manifest to include uncommitted edits. |
| 216 | depth: Maximum call-graph hops from a test function to a production |
| 217 | symbol. Higher values yield more coverage but are slower. |
| 218 | Default 3. Capped at 10 internally to bound BFS cost. |
| 219 | cache: Optional pre-loaded :class:`SymbolCache`. When ``None`` the |
| 220 | cache is loaded from disk and saved on return. |
| 221 | callgraph_cache: Optional pre-loaded :class:`CallGraphCache`. When ``None`` |
| 222 | the cache is loaded from disk and saved after the graph is |
| 223 | built. On a warm cache, ``build_forward_graph`` skips every |
| 224 | ``read_object`` / ``ast.parse`` / AST-walk — the primary |
| 225 | speedup lever. |
| 226 | |
| 227 | Returns: |
| 228 | A :class:`SelectionResult` with deduplicated, confidence-sorted test |
| 229 | targets and a coverage gap report. |
| 230 | """ |
| 231 | changed_list = list(changed) |
| 232 | changed_addresses = [c["address"] for c in changed_list] |
| 233 | |
| 234 | if not changed_addresses: |
| 235 | return SelectionResult( |
| 236 | changed_addresses=[], |
| 237 | test_targets=[], |
| 238 | covered_addresses=[], |
| 239 | uncovered_addresses=[], |
| 240 | coverage_fraction=1.0, |
| 241 | fallback_used=False, |
| 242 | ) |
| 243 | |
| 244 | effective_depth = min(depth, 10) |
| 245 | |
| 246 | own_cache = cache is None |
| 247 | active_cache: SymbolCache = cache if cache is not None else load_symbol_cache(root) |
| 248 | |
| 249 | own_cg_cache = callgraph_cache is None |
| 250 | muse_dir = _muse_dir(root) |
| 251 | active_cg_cache: CallGraphCache = ( |
| 252 | callgraph_cache if callgraph_cache is not None else load_callgraph_cache(root) |
| 253 | ) |
| 254 | |
| 255 | # --- Build the full symbol map (all files) ---------------------------- |
| 256 | all_trees = symbols_for_snapshot(root, manifest, cache=active_cache) |
| 257 | |
| 258 | # Flatten to address → SymbolRecord for kind lookups. |
| 259 | flat_symbols: SymbolIndex = {} |
| 260 | for _file_path, tree in all_trees.items(): |
| 261 | for addr, rec in tree.items(): |
| 262 | flat_symbols[addr] = rec |
| 263 | |
| 264 | # --- Build call graph ------------------------------------------------- |
| 265 | # The forward graph is keyed by *bare function name* because call-site |
| 266 | # analysis via AST Name/Attribute nodes only sees the local name. |
| 267 | # Passing callgraph_cache enables the fast path: warm-cache files skip |
| 268 | # read_object + ast.parse + AST walk entirely. |
| 269 | forward_graph = build_forward_graph( |
| 270 | root, manifest, cache=active_cache, callgraph_cache=active_cg_cache |
| 271 | ) |
| 272 | |
| 273 | if own_cache: |
| 274 | active_cache.save() |
| 275 | if own_cg_cache: |
| 276 | active_cg_cache.save() |
| 277 | |
| 278 | # --- Build coverage map ----------------------------------------------- |
| 279 | # coverage_map: bare_callee_name → [(test_addr, depth)] |
| 280 | coverage_map = _build_coverage_map(forward_graph, flat_symbols, effective_depth) |
| 281 | |
| 282 | # --- Map changed addresses → tests ------------------------------------ |
| 283 | # best[(test_addr)] = min depth seen (lower is better) |
| 284 | best: CounterMap = {} |
| 285 | addr_to_tests: TestListMap = {} |
| 286 | covered_set: set[str] = set() |
| 287 | |
| 288 | for changed_addr in changed_addresses: |
| 289 | bare_name = changed_addr.rsplit("::", 1)[-1] |
| 290 | hits = coverage_map.get(bare_name, []) |
| 291 | if hits: |
| 292 | covered_set.add(changed_addr) |
| 293 | for test_addr, hit_depth in hits: |
| 294 | addr_to_tests.setdefault(changed_addr, []).append(test_addr) |
| 295 | if test_addr not in best or hit_depth < best[test_addr]: |
| 296 | best[test_addr] = hit_depth |
| 297 | |
| 298 | # --- Fallback: file-name heuristic for uncovered symbols -------------- |
| 299 | fallback_used = False |
| 300 | uncovered_before_fallback = set(changed_addresses) - covered_set |
| 301 | |
| 302 | if uncovered_before_fallback: |
| 303 | # Build a map: production file stem → test files |
| 304 | stem_to_test_files: TestListMap = {} |
| 305 | for fp in manifest: |
| 306 | if _is_test_file(fp): |
| 307 | # A test file "tests/test_foo.py" covers the stem "foo" |
| 308 | test_stem = pathlib.PurePosixPath(fp).stem |
| 309 | for prefix in ("test_", ""): |
| 310 | if test_stem.startswith("test_"): |
| 311 | prod_stem = test_stem[len("test_"):] |
| 312 | else: |
| 313 | prod_stem = test_stem |
| 314 | stem_to_test_files.setdefault(prod_stem, []).append(fp) |
| 315 | |
| 316 | for changed_addr in uncovered_before_fallback: |
| 317 | prod_file = changed_addr.split("::")[0] |
| 318 | prod_stem = pathlib.PurePosixPath(prod_file).stem |
| 319 | test_files = stem_to_test_files.get(prod_stem, []) |
| 320 | if test_files: |
| 321 | covered_set.add(changed_addr) |
| 322 | fallback_used = True |
| 323 | for tf in test_files: |
| 324 | # Use whole-file node ID for heuristic hits. |
| 325 | synthetic_addr = tf |
| 326 | if synthetic_addr not in best or best[synthetic_addr] > 99: |
| 327 | best[synthetic_addr] = 99 # heuristic sentinel depth |
| 328 | |
| 329 | # --- Build SelectionTarget list ------------------------------------------- |
| 330 | # Deduplicate by node_id, sort by confidence (ascending depth = higher conf) |
| 331 | seen_node_ids: set[str] = set() |
| 332 | targets: list[SelectionTarget] = [] |
| 333 | |
| 334 | for test_addr, min_depth in sorted(best.items(), key=lambda kv: kv[1]): |
| 335 | node_id = test_addr |
| 336 | if node_id in seen_node_ids: |
| 337 | continue |
| 338 | seen_node_ids.add(node_id) |
| 339 | |
| 340 | file_path = test_addr.split("::")[0] if "::" in test_addr else test_addr |
| 341 | is_heuristic = min_depth == 99 |
| 342 | |
| 343 | if is_heuristic: |
| 344 | confidence = 0.5 |
| 345 | reason = f"file-name match for changed symbol(s) in {file_path!r}" |
| 346 | else: |
| 347 | confidence = _confidence(min_depth) |
| 348 | reason = ( |
| 349 | f"covers changed symbol(s) via call graph (depth {min_depth})" |
| 350 | ) |
| 351 | |
| 352 | targets.append( |
| 353 | SelectionTarget( |
| 354 | node_id=node_id, |
| 355 | file=file_path, |
| 356 | reason=reason, |
| 357 | confidence=confidence, |
| 358 | ) |
| 359 | ) |
| 360 | |
| 361 | covered_addresses = sorted(covered_set) |
| 362 | uncovered_addresses = sorted(set(changed_addresses) - covered_set) |
| 363 | total = len(changed_addresses) |
| 364 | coverage_fraction = len(covered_addresses) / total if total > 0 else 1.0 |
| 365 | |
| 366 | logger.debug( |
| 367 | "test_selection: %d changed symbols, %d tests selected, " |
| 368 | "coverage %.0f%%", |
| 369 | total, |
| 370 | len(targets), |
| 371 | coverage_fraction * 100, |
| 372 | ) |
| 373 | |
| 374 | return SelectionResult( |
| 375 | changed_addresses=changed_addresses, |
| 376 | test_targets=targets, |
| 377 | covered_addresses=covered_addresses, |
| 378 | uncovered_addresses=uncovered_addresses, |
| 379 | coverage_fraction=coverage_fraction, |
| 380 | fallback_used=fallback_used, |
| 381 | ) |
| 382 | |
| 383 | # --------------------------------------------------------------------------- |
| 384 | # Convenience: diff the working tree and return changed symbols |
| 385 | # --------------------------------------------------------------------------- |
| 386 | |
| 387 | def changed_symbols_from_diff( |
| 388 | root: pathlib.Path, |
| 389 | head_manifest: Manifest, |
| 390 | *, |
| 391 | cache: SymbolCache | None = None, |
| 392 | ) -> list[ChangedSymbol]: |
| 393 | """Return every symbol that differs between HEAD and the working tree. |
| 394 | |
| 395 | Compares the working-tree parse of every semantic file against the |
| 396 | committed parse at HEAD. Returns :class:`ChangedSymbol` records for |
| 397 | every symbol that was added, modified (body or signature changed), or |
| 398 | deleted. |
| 399 | |
| 400 | This function is the bridge between ``muse diff`` and test selection: it |
| 401 | provides the *changed* list that ``select_tests`` needs. |
| 402 | """ |
| 403 | own_cache = cache is None |
| 404 | active_cache: SymbolCache = cache if cache is not None else load_symbol_cache(root) |
| 405 | |
| 406 | head_trees = symbols_for_snapshot(root, head_manifest, cache=active_cache) |
| 407 | work_trees = symbols_for_snapshot( |
| 408 | root, head_manifest, workdir=root, cache=active_cache |
| 409 | ) |
| 410 | |
| 411 | if own_cache: |
| 412 | active_cache.save() |
| 413 | |
| 414 | result: list[ChangedSymbol] = [] |
| 415 | |
| 416 | all_files: set[str] = set(head_trees) | set(work_trees) |
| 417 | for file_path in sorted(all_files): |
| 418 | if not is_semantic(file_path): |
| 419 | continue |
| 420 | head_tree = head_trees.get(file_path, {}) |
| 421 | work_tree = work_trees.get(file_path, {}) |
| 422 | |
| 423 | all_addrs: set[str] = set(head_tree) | set(work_tree) |
| 424 | for addr in all_addrs: |
| 425 | head_rec = head_tree.get(addr) |
| 426 | work_rec = work_tree.get(addr) |
| 427 | |
| 428 | if head_rec is None and work_rec is not None: |
| 429 | result.append(ChangedSymbol(address=addr, change_kind="added")) |
| 430 | elif head_rec is not None and work_rec is None: |
| 431 | result.append(ChangedSymbol(address=addr, change_kind="deleted")) |
| 432 | elif head_rec is not None and work_rec is not None: |
| 433 | if head_rec["content_id"] != work_rec["content_id"]: |
| 434 | result.append( |
| 435 | ChangedSymbol(address=addr, change_kind="modified") |
| 436 | ) |
| 437 | |
| 438 | return result |
File History
1 commit
sha256:9ca3eeef4f199d5e8d0b21e50c384a2468e2c2477bd9b157f29fd0f7f06fddcd
feat: add muse reflog expire subcommand and reflog.expire-d…
Sonnet 4.6
patch
73 days ago