Incremental Static Analysis: Dirty Sets and Cache Invalidation

An editor asks for diagnostics after every keystroke. A CI job asks after every push. A repository of a few million lines takes minutes to analyze from scratch, so neither interaction can afford a full run. The only way to make the latency acceptable is to reuse work from the previous run, and the only way to make reuse safe is to know exactly what each cached result depended on.

Three granularities, three reuse stories

Incremental analysis is not one problem. At the finest granularity, a parser reuses the syntax tree for the unchanged region of a file and re-parses only the edited span. That is what an error-tolerant incremental parser provides, and it is why an editor can keep a valid tree while the buffer is half-typed.

At the middle granularity, per-file facts are reused. A file’s exported symbols, its local call edges, its lint findings, and its type information are computed once and stored, keyed by the file’s content. When the file changes, its facts are recomputed. When a file it imports changes, some of its facts may change too, and the dependency graph decides which.

At the coarsest granularity, whole-program facts are reused. The call graph, the points-to relation, and the global type hierarchy are not properties of one file, and a change anywhere can invalidate them. Trying to recompute them per file is what makes naive incremental tools slow, and treating them as globally invalidated is what makes them fast but imprecise.

Most systems use a mix: file-local facts are cached and propagated, and whole-program facts are recomputed only when the set of relevant edges changes. The design question is where to put the boundary, and the answer is determined by which facts the rules actually consume.

A cache key is a claim about dependencies

Every cached result should be stored under a key that includes everything that can change the result. For a per-file analysis that means at least the file’s content hash, the analyzer’s version, and the effective configuration. If the analysis reads other files, their content hashes must be in the key too, directly or through a summary.

The direct approach hashes the transitive closure of imports into the key. It is correct and it is expensive, because a change deep in a dependency tree changes the key of every dependent, even when the exported interface is unchanged. The usual refinement is a Merkle-style key: hash the file’s own content together with the keys of its direct dependencies. A change propagates upward one level at a time, and a dependent’s key changes only if a dependency’s key changed.

That still over-invalidates when a dependency’s implementation changes but its interface does not. Separating interface facts from body facts fixes it: the exported symbol table is hashed into the key for dependents, while the body analysis is keyed only on the file. A change to a function body then invalidates that function’s findings but not every caller’s resolution. This is the same early-cutoff idea that makes content-addressed build systems avoid rebuilding downstream targets whose inputs are unchanged.

import hashlib

def file_key(path, source, deps, analyzer_version, config_digest):
    h = hashlib.sha256()
    h.update(source)
    h.update(analyzer_version.encode())
    h.update(config_digest.encode())
    for dep in sorted(deps):
        h.update(dep.encode())      # interface key, not raw content
    return h.hexdigest()

The sorting is not cosmetic. If dependency order leaks into the hash, two runs over the same logical graph produce different keys, cache hits disappear, and the analysis becomes nondeterministic across machines.

Invalidation is a graph reachability problem

When a file changes, the set of affected results is the set of cached results whose keys depend on it. Computing that set requires a reverse dependency graph: for each file, the files that imported it; for each symbol, the files that referenced it; for each function, the callers whose summaries mention it.

The graph must over-approximate. If a dependency edge is missing, a change does not propagate, and the tool serves a stale result with full confidence. That failure is worse than a cache miss, because it produces a wrong answer that looks authoritative. Adding edges aggressively costs performance but preserves correctness; removing them for speed is how incremental analyzers become unreliable.

Cycles complicate propagation. Two modules that import each other form a strongly connected component, and invalidation must treat the component as a unit: a change to either member invalidates both, and the summaries within the component are iterated to a fixpoint. The same SCC iteration appears in interprocedural analysis, as described in Interprocedural Summaries and Context Sensitivity, and for the same reason: the equations are mutually recursive.

What the key usually forgets

The most common cache bug is a missing input. The second most common is a changing input that is not represented in the key.

Configuration is the classic omission. A rule’s severity, an ignore list, a target language version, and a set of enabled checks all change the output, and all of them live in files that the analysis reads but may not hash. The config digest in the key must cover the resolved configuration, not just the path to the config file, because includes and environment expansion can change the result without changing the file.

The analyzer’s own version is the second. An upgrade changes the analysis, and every cached result from the previous version is invalid. Hashing the version string is enough if versions are bumped correctly; a build identifier or a digest of the analyzer binary is stricter, because development builds often share a version number.

The environment is the third. A path to a standard library, a target triple, a set of feature flags, or a locale can change resolution and diagnostics. If these are not in the key, a run on a different machine can hit a cache entry produced under different assumptions. The safe approach is to canonicalize the environment into an explicit set of values and hash that set, rather than reading ambient state during analysis.

Generated files are the fourth. A file produced by a code generator may be unchanged on disk while its generator’s input changed, or may be regenerated with a new timestamp and identical content. Hashing content handles the second case; the first requires the generator’s inputs to be part of the dependency graph.

Determinism is a prerequisite, not a nicety

A cache assumes that the same key produces the same result. If the analysis iterates over a hash map whose order varies between runs, or parallelizes over files and merges results in completion order, the output can differ for identical inputs. The differences may be cosmetic, such as the order of findings, or substantive, such as which of two conflicting facts wins a join.

The standard remedies are to sort before emitting, to use ordered containers in the merge, and to define a canonical order for diagnostics. Stable fingerprints, discussed in Diagnostic Spans and the Encoding Problem, let a consumer recognize the same finding across runs even when ordering is not guaranteed. Without determinism, a cache hit and a cache miss can produce different reports for the same code, which destroys trust faster than a slow run.

When to stop reusing

Incremental analysis has a failure mode that is invisible in benchmarks: the cache is correct for the code it analyzed, but the code it analyzed is not the code on disk. A stale file, a generated artifact that was not regenerated, a branch switch that changed many files at once, or a cache restored from another machine with a different toolchain can all produce this state.

The defenses are cheap. Verify that the working tree’s content hashes match the keys before serving a cached result. Record the analyzer version and configuration in the cache metadata and refuse entries that do not match. Provide a full-rebuild path and use it in CI, so that a corrupted incremental state is detected rather than trusted indefinitely. The cache is an optimization, and an optimization that can silently change the answer is not worth its latency savings.

The economics are straightforward: a cache hit saves the cost of re-analysis, and a wrong hit costs the credibility of every subsequent result. The design should make the first common and the second impossible, even at the price of recomputing more than a theoretically minimal system would.