What causes "counting sort fills every slot of a kind's range" in rust-lang/rust?

Delete the incremental compilation cache directory (e.g. target/debug/incremental) and rebuild clean.

counting sort fills every slot of a kind's range

Error message

counting sort fills every slot of a kind's range

What it means

Sanity-check panic inside SerializedDepGraph's reverse-index construction (compiler/rustc_middle/src/dep_graph/serialized.rs:189). While building the key_fingerprint->index map for a given DepKind, it iterates the kind's contiguous range in nodes_by_kind and expects every slot to be Some (the counting sort that built nodes_by_kind should leave no holes). A None slot means the serialized dep-graph is internally inconsistent/corrupt.

Source

Thrown at compiler/rustc_middle/src/dep_graph/serialized.rs:189

impl LazyKindIndex {
    /// Returns this kind's `key_fingerprint -> node index` map.
    fn fingerprint_map(
        &self,
        kind: DepKind,
        nodes: &IndexSlice<SerializedDepNodeIndex, DepNode>,
        nodes_by_kind: &[Option<SerializedDepNodeIndex>],
        profiler: &Option<SelfProfilerRef>,
    ) -> &UnhashMap<PackedFingerprint, SerializedDepNodeIndex> {
        self.map.get_or_init(|| {
            let _prof_timer = profiler
                .as_ref()
                .map(|p| p.generic_activity("incr_comp_load_dep_graph_reverse_index"));
            let range = (self.start as usize)..(self.start as usize + self.len as usize);
            let mut map =
                UnhashMap::with_capacity_and_hasher(self.len as usize, Default::default());
            for &idx in &nodes_by_kind[range] {
                let idx = idx.expect("counting sort fills every slot of a kind's range");
                let node = nodes[idx];
                debug_assert_eq!(node.kind, kind);
                if map.insert(node.key_fingerprint, idx).is_some()
                    // Side effect nodes can legitimately share a fingerprint.
                    && node.kind != DepKind::SideEffect
                {
                    panic!(
                        "Error: A dep graph node ({kind:?}) does not have an unique index. \
                         Running a clean build on a nightly compiler with \
                         `-Z incremental-verify-ich` can help narrow down the issue for reporting. \
                         A clean build may also work around the issue.\n
                         DepNode: {node:?}"
                    )
                }
            }
            map
        })
    }

View on GitHub (pinned to 22057b88b0)

Solutions

Delete the incremental compilation cache directory (e.g. target/debug/incremental) and rebuild clean.
Run with -C incremental=no to bypass incremental loading entirely until the root cause is identified.
Ensure only one rustc process writes a given target dir and that the same toolchain version is used across builds.
If reproducible on a clean build, file a rustc bug with the reproduction case — the serialized dep-graph should never have gaps.

Example fix

# before
rm -rf target/debug/incremental  # scattered leftovers

# after
cargo clean && cargo build

Defensive patterns

Strategy: retry

Validate before calling

// The assertion fires during dep-graph serialization counting sort;
// no user-facing input can be validated. Pre-flight by ensuring the
// incremental cache is in a clean state.
fn ensure_clean_incremental(target_dir: &std::path::Path) {
    let inc = target_dir.join("incremental");
    if inc.exists() {
        std::fs::remove_dir_all(&inc)
            .expect("failed to remove stale incremental cache");
    }
}

Try / catch

// Wrapper that retries the build once after wiping the incremental
// cache when an internal dep-graph panic is observed.
fn build_with_cache_fallback(cmd_fn: impl Fn() -> std::process::Command) -> std::process::ExitStatus {
    let status = cmd_fn().status().expect("failed to spawn cargo");
    if !status.success() && std::env::var("RUST_BACKTRACE").is_ok() {
        let _ = std::fs::remove_dir_all("target/debug/incremental");
        return cmd_fn().status().expect("failed to spawn cargo retry");
    }
    status
}

Prevention

Run periodic clean builds (cargo clean) to discard corrupted incremental state
Avoid interrupting builds mid-write to the incremental cache
Disable incremental compilation for crates with heavy procedural-macro use
Pin a single nightly toolchain per project; do not alternate between nightlies on the same target dir

When it happens

Trigger: Loading an incremental compilation cache whose on-disk SerializedDepGraph was truncated, partially overwritten, or produced by a different rustc version with an incompatible encoding. The panic fires the first time that kind's fingerprint_map is queried (lazy OnceLock init).

Common situations: Incremental cache left over from an older/newer nightly after an ABI change; a crashed or killed previous build leaving a half-written dep-graph file; concurrent invocations of rustc writing the same target directory; disk/NFS corruption.

Related errors

AI-assisted analysis of rust-lang/rust@22057b88b0 (2026-08-03). Data as JSON: /data/errors/3378c1560700ea47.json. Report an issue: GitHub.