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