Change-Based Test Selection and Where It Stops Being Sound

Running a large suite on every change is wasteful in a way that is easy to quantify: a suite of ten thousand tests that takes forty minutes in aggregate, triggered by a change to one file, spends almost all of that time executing tests that cannot observe the change. Selection replaces the full run with a subset chosen by asking which tests depend on what changed. The question is answerable in more than one way, the answers differ in cost and in what they miss, and the failure that matters most is the quiet one — a subset that runs, passes, and omits the test that would have caught the regression.

Selection is not caching

Two optimisations are often described in the same breath and answer different questions. Caching asks whether the result of a test is still valid: if the test target’s declared inputs are unchanged since the last execution, its previous verdict can be reused without running it. Selection asks whether a test could be affected by a change. A test can be unaffected by a change and still be re-executed because something in its input set changed — a timestamp in a generated file, a version string in a lockfile. A test can be affected by a change and still not be selected, which is the dangerous direction.

Caching is decidable when inputs are declared exactly, which is the property that makes hermetic build systems able to reuse results across machines. Selection relies on a dependency analysis that is almost never exact, so it trades a measured risk of missing a regression for a large reduction in work. Keeping the two mechanisms separate in a design matters because they fail differently: a stale cache entry produces a wrong verdict for a test that should have run, while a selection miss means the test never ran at all, and only the second produces a green build over broken code.

Static dependency graphs and their blind spots

The cheapest approach derives dependencies from the source tree. A module imports another; a package contains modules; a test file imports production code. Following the edges backwards from each changed file yields the set of test files that could observe it. This needs no instrumentation, works on code that has never been executed, and produces a graph that can be queried in milliseconds.

Its precision is bounded by the language’s indirection. An import is an edge, but a dependency obtained at run time is not. Common cases include a plugin registry keyed by a string, dependency injection configured in a container, a module resolved through a name built from configuration, a template that references a helper by name, and any reflection over attributes. A test that exercises such a path has no static edge from the changed file, so it is not selected. The usual mitigation is to treat the registry or container as a hub: everything that registers into it is considered a dependency of everything that reads from it, which recovers soundness at the cost of selecting nearly the whole suite.

Granularity is the second axis. File-level edges are coarse: a change to one function in a widely imported module selects every test that imports the module, even though only a few can reach the function. Symbol-level edges are finer and require a front end that resolves references, which is available in compiled languages and approximated in others. The trade is between rebuilding an index from parsed source and accepting a larger selection.

Dynamic traces and the new-line blind spot

The alternative is to measure rather than infer. A run of the full suite is instrumented to record, for each test, which source files — ideally which lines — it executed. The result is an inverted index from code location to tests, and selecting for a change is a lookup. This is the mechanism behind per-test coverage in build systems and continuous-integration services, and its precision is far better than the static approach because it observes the execution that actually happened.

The cost is the size of the index and the price of collecting it. A per-test, per-line record is a matrix with as many rows as tests and as many columns as executable lines, and for a suite of tens of thousands of tests against a large codebase that is far too much to store densely. Practical implementations store per-test file lists, or per-test sets of covered files compressed as sorted identifier lists, or aggregate counts per test shard. Storing file lists loses line-level precision but keeps the index small enough to hold in memory and to rebuild quickly.

The blind spot is structural and worth stating precisely. The trace records what the tests executed before the change. If a developer modifies a function that no test has ever called, the changed lines appear in no test’s trace, so the selected set is empty — and the change is precisely the kind that most needs a test. Dynamic selection answers “which tests used to exercise this code”, not “which tests ought to exercise it”. A change that introduces a new branch into a covered function is partially handled, because tests that covered the function are selected and the new branch will be recorded on the next full run, but the first run after the change is the one that decides whether the branch is correct. For this reason a selection system built on traces should be paired with a coverage report that names newly added lines with no coverage, and should treat those as an explicit signal rather than silently selecting nothing.

Mixing the two approaches is common: static edges cover code that has never run, dynamic traces refine selection for code that has. Whatever the mix, the index has to be keyed on the identities assigned during collection, so the stability concerns from Test Discovery, Collection Order, and Import Side Effects apply directly — a test whose identifier changes between runs loses its trace entry and its history.

def build_index(traces):
    """traces: {test_id: {source_file, ...}} -> {source_file: {test_id, ...}}"""
    index = {}
    for test_id, files in traces.items():
        for path in files:
            index.setdefault(path, set()).add(test_id)
    return index

def select(index, changed, all_tests):
    """Union over changed paths. Anything unknown means we cannot rule it
    out, so the caller should fall back to running everything."""
    chosen = set()
    unknown = False
    for path in changed:
        hit = index.get(path)
        if hit is None:
            unknown = True      # no evidence that any test touches this file
        else:
            chosen |= hit
    return (all_tests if unknown else chosen), unknown

Failing open, not closed

Every selection system has states in which its map is not trustworthy, and the correct behaviour in all of them is to select everything. The list is short and worth enumerating because each has appeared as a real source of missed regressions.

The first is bootstrapping: before any instrumented run, there are no traces, so nothing can be selected. The second is staleness: traces describe a revision that no longer exists in the working tree, and line numbers have moved. The third is a changed map: when the rules that map changes to tests change, everything that was previously inferred is invalid. The fourth is an unindexed input, which is where non-code dependencies live — a schema, a fixture data directory, a translation catalogue, a golden output file, a dictionary in the build definition. A test that reads such a file is affected by changes to it, and a dependency map built from source imports does not know the file exists. Build systems handle this by requiring declared inputs for a test target, which is exactly the hermetic-input discipline, and selection systems that do not have declared inputs have to discover reads dynamically or over-select.

The asymmetry justifies a strict policy: a miss in the map means run the test, not skip it. Selection should be understood as a filter that removes tests which are provably independent of the change, with “provably” determined by a declared input set rather than by the absence of evidence. When the input set is unknown, the answer is the full suite.

What a partial run changes about the suite

Running a subset is not equivalent to running the whole suite quickly. It changes the environment in which the selected tests execute, and suites that depend on the environment fail differently.

State coupling is the first effect. A test that relied on a session fixture prepared by an unselected test now runs without it, so a selection run can fail for a reason that has nothing to do with the change. That is the shared-state problem from Fixture Scoping and the Lifetime of Shared Test State appearing as a false positive rather than a false negative. The second effect is statistical: flaky tests are distributed unevenly across the suite, so a filtered subset has a different pass rate than the full run, and a gate tuned on full runs will produce a different rate of failure on partial ones. Neither effect is an argument against selection; both are arguments for treating a partial run as a different signal from a full one, and for running the full suite on the branch that matters most rather than on every commit.

The precision of selection is also measurable, and the measurement is worth having. Recall — the fraction of a truly affected test set that was selected — can be estimated by occasionally running the full suite on changes where selection was used and comparing verdicts. Without that check the system has no evidence about its own blind spots, and the cost of a missed regression is paid by whoever debugs the incident weeks later, with no record that a selection decision caused it.