Inside find_changed: How a Monorepo’s Homegrown Test Selector Actually Works

Every monorepo has this problem: you changed three files, but the repo has a hundred packages. Which tests do you run? Run everything and you’re burning 45 minutes of CI on every PR. Run nothing and you’re pushing broken code to main.

The usual answer is “use Bazel” or “use some affected-test-detection tool.” But what does that tool actually do? Like, concretely, what happens between git diff and “here’s your test matrix”? I’ve been staring at our test selector’s source code for a week, and the internals are more interesting than I expected.

This is about find_changed — the ~2,650-line Python system that decides which tests run on every PR in our monorepo. Not a Bazel pitch. Not a comparison post. Just: here’s what’s under the hood of a real, production test selector.

Two graphs, one question

The core insight is that find_changed maintains two parallel dependency graphs and walks them both.

Graph 1: Package-level, built from uv.lock. Every workspace package is a node. Every external dependency (numpy, pydantic, torch) is a node. Edges are dependency relationships from the lockfile — including version numbers. This graph answers: “did package X or any of its transitive dependencies change?”

Graph 2: File-level, built from ruff analyze graph plus Python AST scanning. Every .py file is a node. Edges are import relationships. This graph answers the finer question: “did the specific files that this test file transitively imports change?”

The two graphs feed into two different modes:

The GPU workflow uses both: find_changed for coarse gating (“should we build the Docker image at all?”) and tests for fine-grained file selection (“which specific test files need a GPU?”). Two questions, two granularities, same system.

Here’s the data flow:

                    ┌─────────────┐
                    │  git diff   │
                    │ --name-only │
                    └──────┬──────┘
                           │
                           ▼
       ┌──────────────────────────────────────┐
       │      Two Parallel Graph Builders      │
       │                                       │
       │  PACKAGE GRAPH        FILE GRAPH      │
       │  uv.lock ──────►     ruff analyze ──► │
       │  parse_uv_lock()     _run_ruff_graph()│
       │       │                    │          │
       │       ▼                    ▼          │
       │  WorkspaceDist       WorkspaceFile    │
       │  + ExternalDist      + AST scanning   │
       │  + PkgDepGlobs       + yolo.ci hdrs   │
       └──────┬──────────────────┬─────────────┘
              │                  │
              ▼                  ▼
       ┌─────────────┐  ┌──────────────────┐
       │ Package DFS │  │   File-level DFS │
       │ (version    │  │   (imports +     │
       │  bumps,     │  │    conftest +    │
       │  dep sets)  │  │    globs +       │
       │             │  │    externals)    │
       └──────┬──────┘  └──────┬───────────┘
              │                │
              ▼                ▼
       ┌────────────────────────────────────┐
       │       GitHub Actions Workflows      │
       │  CPU tests → tests-by-package       │
       │  GPU tests → find_changed + tests   │
       └────────────────────────────────────┘

Building the package graph

The package graph comes from uv.lock — our lockfile. The builder is build_workspace_distributions(), and the logic is:

1. Parse uv.lock via Pydantic (the lockfile is TOML)
2. Filter by environment — evaluate uv’s resolution markers, PEP 508 markers, Python version. Default target: Linux x86_64 Python 3.12
3. Partition — workspace members become WorkspaceDistribution nodes, everything else becomes ExternalDistribution nodes with name + version
4. Wire edges — regular + optional + dev dependencies per workspace member
5. Inject non-Python deps from package_extra_dependencies.yml (more on this later)

The data structures are clean:

@dataclass(slots=True, kw_only=True)
class ExternalDistribution:
    distribution: Distribution  # name + version
    dependencies: list["ExternalDistribution"]

@dataclass(slots=True, kw_only=True)
class WorkspaceDistribution:
    name: DistributionName
    dependencies: list[WorkspaceDistribution | ExternalDistribution | PackageDependencyGlob]

Notice that a workspace distribution’s dependencies can be other workspace packages, external packages, or glob patterns for non-Python files. That third type is how the system knows that if you change a Dockerfile, the packages that depend on it need retesting.

Building the file graph

This is where it gets clever. The file graph is built in three layers:

Layer 1: ruff. ruff analyze graph --direction=dependencies produces a JSON map of file → imported files. One subprocess call for the entire workspace. Fast, but it only sees static Python imports.

def _run_ruff_graph(repo_root: Path, paths: Iterable[Path]) -> dict[Path, list[Path]]:
    cmd = [
        "uv", "run", "ruff", "analyze", "graph",
        "--direction=dependencies",
        "--config", "namespace-packages=[]",
        *expanded_paths,
    ]
    r = subprocess.run(cmd, capture_output=True, text=True, cwd=str(repo_root), check=False)
    raw = json.loads(r.stdout or "{}")

    graph: dict[Path, list[Path]] = {}
    for key, deps in raw.items():
        if _should_skip_file(key):
            continue
        filtered_deps = [d for d in deps if not _should_skip_file(d)]
        graph[Path(key)] = [Path(dep) for dep in filtered_deps or []]
    return graph

Layer 2: AST scanning. Every file in the import graph gets parsed to extract:

• All import X / from X import Y statements → top-level package names
• # /// [yolo.ci] headers (inline TOML, more on this below)

This runs in parallel — up to 32 workers via ProcessPoolExecutor. Results are cached to disk by SHA256 of file content, sharded into .cache/ci/ast_scan/. The cache survives across CI runs via GitHub Actions cache.

Layer 3: Package name resolution. This is the gnarly part. You have an import like import numpy. Which distribution is that? Usually numpy. But import PIL is the pillow distribution. import yaml is pyyaml. import cv2 is opencv-python. The mapping isn’t always obvious.

The resolver tries four strategies in order:

def package_to_distributions(pkg: PackageName) -> set[DistributionName]:
    if is_stdlib_base(pkg.base): return set()     # stdlib — skip
    if _is_private_package(pkg): return set()     # _foo — skip
    if pkg.base in IGNORE_PACKAGES: return set()  # known unresolvable

    # Strategy 1: installed metadata (top_level.txt)
    dists = _module_to_distnames().get(pkg.base)
    if not dists:
        # Strategy 2: uv.lock fallback
        uv_dists = _module_to_distnames_from_uv_lock().get(pkg.base)
        if uv_dists:
            return {d for d in uv_dists if not _is_stub(d.canonical)}
        raise KeyError(f'Could not find "{pkg.base}"')

    return {d for d in dists if not _is_stub(d.canonical)}

When that chain fails, there’s a manual override table — KNOWN_DIST_TO_IMPORT — with ~30 hardcoded mappings. And ~35 packages in IGNORE_PACKAGES that are known unresolvable (CUDA extensions, internal packages, test helpers).

Every time someone adds a new package with a non-standard import name and forgets to add it to the mapping table, find_changed throws a KeyError. Ask me how I know.

The DFS walk

Both graphs get traversed with the same core primitive — a decorator called dfs_cached that handles memoization and cycle detection in 40 lines:

def dfs_cached(memo, key, return_on_cycle):
    visiting: set[K] = set()
    def decorator(fn):
        def wrapper(*args, **kwargs):
            k = key(*args, **kwargs)
            if k in memo:           # Already computed — return cached
                return memo[k]
            if k in visiting:       # Cycle detected — bail
                return return_on_cycle
            visiting.add(k)
            try:
                res = fn(*args, **kwargs)
            finally:
                visiting.remove(k)
            memo[k] = res
            return res
        return wrapper
    return decorator

Three states per node: unvisited, visiting, computed. When you hit a node that’s currently being visited, you’ve found a cycle — return the conservative default and move on. No separate visited/path sets. No recursion limit tricks. Just clean state tracking.

This decorator wraps the real change-detection logic. The file-level checker’s _file_differs() runs a 5-step priority cascade for each file:

@dfs_cached(self._fd_memo, key=lambda file: id(file), return_on_cycle=None)
def _file_differs(file: WorkspaceFile) -> DiffResult | None:
    # 1. Direct change — is this file in the diff?
    if self._path_changed(file.path):
        return DiffResult(path=file.path, trigger=Trigger(kind="path", ...))

    files, exts, globs = self._partition_file(file)

    # 2. Glob direct hit — do any declared glob patterns match a changed path?
    glob_hit = self._glob_hits(globs)
    if glob_hit is not None:
        return DiffResult(...)

    # 3. Glob transitive — expand globs, then check if matched files' imports changed
    for glob in globs:
        glob_res = self._glob_transitive_diff(glob, _file_differs)
        if glob_res is not None:
            return DiffResult(path=file.path, trigger=glob_res)

    # 4. External version bump — compare base vs head external deps
    for name, head_ext in exts.items():
        base_ext = self.base_externals.get(name)
        if base_ext is None or self.dist_checker.externals_differ(base_ext, head_ext):
            return DiffResult(...)

    # 5. Recursive import walk — follow the import graph
    for child in files.values():
        child_res = _file_differs(child)
        if child_res is not None:
            return DiffResult(path=file.path, trigger=child_res)

    return None

Step 3 is the subtle one. If a test declares dependencies = ["scripts/*.py"] via a yolo.ci header, and one of those scripts’ imports changed (not the script itself), the test still gets flagged. Two-level expansion — globs to files, then files to their transitive import chains.

Step 4 is the one that catches what most CI systems miss. If someone bumps numpy in uv.lock without changing any Python files, every file that transitively depends on numpy gets flagged. A new version of a dependency is a change — the behavior might be different.

For test files specifically, the checker also walks the conftest chain:

# For test files, also check conftest.py and __init__.py chains
if is_test_file(rel):
    files.extend(self._applicable_conftest_files(rel))
    files.extend(self._applicable_init_files(rel))

For a/b/c/test_foo.py, this finds: a/b/c/conftest.py, a/b/conftest.py, a/conftest.py, conftest.py. If any of them changed, the test is affected. Very pytest-aware.

The escape hatches

Static analysis misses things. find_changed has three mechanisms for the stuff that imports can’t see.

yolo.ci inline headers

Files can declare extra dependencies via embedded TOML in comments:

# /// [yolo.ci]
# dependencies = [
#    "mai_trainer/src/mai_trainer/checkpointing/offline_resharding.py",
# ]
# ///

This handles the “test runs a script via subprocess” case, the “test loads a config file by path” case, the “dynamic dispatch that no import scanner can see” case. About 20 files in the repo use these headers.

Available fields:

package_extra_dependencies.yml

This config connects non-Python artifacts to the package graph:

mai_kernels: &mai_kernels
  - .gitmodules
  - mai_kernels/CMakeLists.txt
  - mai_kernels/csrc/**
simplertransformer: &simplertransformer
  - *mai_kernels                        # YAML anchor inheritance
  - docker-bake.hcl
  - docker/simplertransformer/Dockerfile
  - simplertransformer/CMakeLists.txt
  - simplertransformer/csrc/**
rocket:
  - *simplertransformer
  - docker/Dockerfile
  - docker/rocket/Dockerfile

YAML anchors allow inheritance chains: mai_kernels globs feed into simplertransformer, which feeds into rocket. So if mai_kernels/csrc/attention.cu changes, rocket tests get flagged. An import scanner would never see this.

conftest.py propagation

This one’s automatic, not opt-in. For every test file, the system finds all conftest.py and __init__.py files in ancestor directories and checks them for changes. The discovery is a clean one-liner:

def find_chain(rel: Path, name: str) -> list[Path]:
    """For 'a/b/c/test_foo.py', returns:
    ['a/b/c/conftest.py', 'a/b/conftest.py', 'a/conftest.py', 'conftest.py']
    """
    rel_posix = PurePosixPath(rel.as_posix().rstrip("/"))
    return [Path((d / name).as_posix()) for d in rel_posix.parents]

Conservative? Yes — any conftest change triggers every test under it. But that’s the correct semantic for pytest, where conftest fixtures propagate downward through the filesystem tree with no explicit declaration.

How CI consumes the output

The system feeds into GitHub Actions in two main paths.

CPU tests

1. Changed files hit the find-changed composite action
2. If not a blanket trigger-all or skip-all, runs ci.cli tests-by-package --config ci/configs/cpu_tests.yml
3. Output: a JSON matrix mapping each affected package to a runner type, pytest flags, and environment
4. Matrix fans out into three runner types: ubuntu-latest, big (self-hosted), cpu (condor cluster)

Each package in cpu_tests.yml specifies its test path, extra flags, paths to ignore, and which runner to use. ~80 packages configured this way.

GPU tests

Three stages:

Stage 1: Coarse gating. ci.cli find_changed checks 8 logical dependency specs (like “did anything in simplertransformer or mai_distributed change?”). Each resolves to true/false. These booleans gate expensive downstream jobs — no point spinning up a GPU runner if nothing GPU-related changed.

Stage 2: Fine-grained selection. ci.cli tests --filter "$GPU_TEST_PKGS" identifies the specific test files. GPU_TEST_PKGS is a hardcoded list of ~13 test paths in the workflow YAML.

Stage 3: Sharding. Tests are distributed across GPU shards using historical duration weights from gpu_test_durations.json. Tests are classified into execution modes — serial (uses all GPUs), isolated (separate process), normal (parallel), or skip.

The coarse gating saves real money. If your PR only touches a docs package, the GPU workflow’s find_changed job runs in seconds, returns “nothing changed,” and no GPU runners spin up.

The trigger-all / skip-all system

Two more escape hatches, but at the workflow level.

Trigger-all: If any changed file matches certain patterns, everything runs. No analysis.

Skip-all: If every changed file matches these patterns, nothing runs.

Makes sense. If you changed the CI config, you want full validation. If you only changed markdown, you want zero tests. The escape hatches bracket the analysis from both sides.

The numbers

Let’s make this concrete.

Core system:

Config and workflow files:

Grand total: ~5,665 lines. Python logic plus the workflow YAML that wires it together.

16 key data structures. 3 caching layers (DFS memoization, AST disk cache, GitHub Actions cache). 7 config files. 8 workflow files consuming the output.

The maintenance surface

Here’s the cost of a homegrown system — the stuff someone has to keep alive.

~35 ignored packages in IGNORE_PACKAGES. CUDA extensions, internal packages, test helpers that can’t be resolved to a distribution name. If one of these changes version, the system won’t detect it.

~30 manual distribution→import mappings in KNOWN_DIST_TO_IMPORT. The PIL → pillow stuff. Every new PyPI package with a non-obvious import name needs a manual entry. Miss one, get a KeyError.

15+ ruff skip paths in RUFF_GRAPH_ANALYZE_SKIP_IMPORTS. Paths that ruff’s import analyzer chokes on or that shouldn’t be tracked (.github/, mai_kernels/csrc/, user_scripts/). Tests in skipped directories don’t get proper import tracking.

3 shadowed packages with special handling. megatron, ds1000, sglang have workspace members that shadow external package names. Fragile.

~80 package entries in cpu_tests.yml, manually maintained. There’s a verify_test_configs.py check to catch missing entries, but someone still has to write the config.

~13 GPU test paths hardcoded in a workflow env var. Adding a new GPU test package means editing YAML.

This is the tax on homegrown. Every one of these is a thing that works until it doesn’t, and “doesn’t” usually manifests as a false negative — a test that should have run, didn’t, and now main is broken.

What it gets right

Credit where it’s due. This system catches things that most CI selectors — including Bazel — don’t.

External version bumps. Bump numpy in the lockfile with zero code changes? Every package that depends on numpy gets retested. Bazel’s @pypi//numpy is @pypi//numpy regardless of version. find_changed actually diffs versions.

Non-Python artifacts. C++ source changes, Dockerfile changes, CMakeLists changes — all wired into the package graph via package_extra_dependencies.yml. Bazel’s Python rules don’t natively know about Dockerfiles.

conftest propagation. Automatic, correct for pytest semantics. Bazel requires you to explicitly declare conftest as a library dependency on each test target. Miss one and it’s a sandbox failure.

The yolo.ci escape hatch. For dynamic dependencies that static analysis can’t see, there’s a simple, file-local way to declare them. Twenty lines of TOML in a comment. No build system changes, no external config.

Content-hash caching. AST scan results are cached by SHA256 of file content, not path. Rename a file, same hash, cache hit. Survives across CI runs.

What it misses

No target-level precision. The system operates at package level (for find_changed) or file level (for tests). It can’t say “only these 3 tests out of 200 in this package are affected.” Bazel can.

Dynamic imports are invisible. importlib.import_module(), __import__(), conditional imports inside functions — none of these create edges in the ruff graph. The yolo.ci header is the escape hatch, but it requires someone to think about it.

The graph is inferred, not declared. Bazel’s dependency graph is authoritative — you declared it, it’s enforced. find_changed infers the graph from imports and lockfiles. If the inference is wrong, you get a false negative.

No test-level caching. Bazel caches individual test results by input hash. find_changed only decides run or skip — it can’t say “this test already passed with this exact set of inputs, don’t bother.”

Cycle handling is conservative. The dfs_cached decorator returns “unchanged” on cycle detection. That means if you have circular imports (Python allows them; they exist), the system might miss a real change.

The bigger picture

find_changed is ~5,665 lines of code and config that answers one question: “what should CI run?” It does this by building two dependency graphs, walking them with DFS, and handling a dozen edge cases that pure import scanning misses.

Is it elegant? Parts of it — the dfs_cached decorator, the dual-graph architecture, the content-hash caching. Those are genuinely good engineering.

Is it sustainable? That’s the harder question. ~35 ignored packages, ~30 manual mappings, ~15 skip paths, ~80 manually-configured test entries. Every one is a thing someone wrote because they understood the system, and every one is a thing that’ll confuse the next person.

The important thing is that this system works. Every PR in our monorepo goes through it. It’s been catching real changes and skipping real non-changes for months. When we talk about graduating to Bazel, we’re not fleeing a broken system. We’re graduating from one that does its job — at a maintenance cost that scales with the repo.

Understanding the incumbent is the first step to replacing it well. You don’t deprecate a system you haven’t studied. That’s how you lose the edge cases it was built for.

This is part of a series on CI and build systems in a Python monorepo. Related: Your Monorepo Has Two Dependency Graphs (and They Disagree) covers the conceptual framing. The Dep Graph Is the Product covers the Bazel side. The Test Hierarchy Map covers the testing concepts. What a Full Dep Graph Actually Unlocks covers what comes next.