Green Means Same: How rustc Re-runs Every Query and Then Throws Most of the Work Away

// compiler/rustc_middle/src/dep_graph/graph.rs:791-835

fn alloc_and_color_node(
    &self,
    key: DepNode,
    edges: &[DepNodeIndex],
    value_fingerprint: Option<Fingerprint>,
) -> DepNodeIndex {
    if let Some(prev_index) = self.previous.node_to_index_opt(&key) {
        // Determine the color and index of the new `DepNode`.
        let is_green = if let Some(value_fingerprint) = value_fingerprint {
            if value_fingerprint == self.previous.value_fingerprint_for_index(prev_index) {
                // This is a green node: it existed in the previous compilation,
                // its query was re-executed, and it has the same result as before.
                true
            } else {
                // This is a red node: it existed in the previous compilation, its
                // query was re-executed, but it has a different result from before.
                false
            }
        } else {
            // This is a red node, effectively: it existed in the previous compilation
            // session, its query was re-executed, but it doesn't compute a result hash
            // (i.e. it represents a `no_hash` query), so we have no way of determining
            // whether or not the result was the same as before.
            false
        };

// compiler/rustc_middle/src/dep_graph/mod.rs:26-56

#[derive(Debug, PartialEq, Eq, Copy, Clone)]
pub enum KeyFingerprintStyle {
    /// The fingerprint is actually a DefPathHash.
    DefPathHash,
    /// The fingerprint is actually a HirId.
    HirId,
    /// Query key was `()` or equivalent, so fingerprint is just zero.
    Unit,
    /// The fingerprint is an opaque hash, and a key cannot be reconstructed from it.
    Opaque,
}

impl KeyFingerprintStyle {
    /// True if a key can _potentially_ be recovered from a key fingerprint
    /// with this style.
    #[inline]
    pub const fn is_maybe_recoverable(self) -> bool {
        match self {
            KeyFingerprintStyle::DefPathHash
            | KeyFingerprintStyle::Unit
            | KeyFingerprintStyle::HirId => true,
            KeyFingerprintStyle::Opaque => false,
        }
    }
}

// compiler/rustc_span/src/def_id.rs:61-101

/// A `DefPathHash` is a fixed-size representation of a `DefPath` that is
/// stable across crate and compilation session boundaries. It consists of two
/// separate 64-bit hashes. The first uniquely identifies the crate this
/// `DefPathHash` originates from (see [StableCrateId]), and the second
/// uniquely identifies the corresponding `DefPath` within that crate.
///
/// There is a very small chance of hash collisions, which would mean that two
/// different `DefPath`s map to the same `DefPathHash`. Proceeding compilation
/// with such a hash collision would very probably lead to an ICE, and in the
/// worst case lead to a silent mis-compilation. The compiler therefore actively
/// and exhaustively checks for such hash collisions and aborts compilation if
/// it finds one.

// compiler/rustc_middle/src/dep_graph/dep_node_key.rs:160-178

fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
    let HirId { owner, local_id } = *self;
    let def_path_hash = tcx.def_path_hash(owner.to_def_id());
    Fingerprint::new(
        // `owner` is local, so is completely defined by the local hash
        def_path_hash.local_hash(),
        local_id.as_u32() as u64,
    )
}

// compiler/rustc_hir_id/src/definitions.rs:361-370

// We want *both* halves of a DefPathHash to depend on the crate-id of the defining crate.
// The crate-id can be more easily changed than the DefPath of an item, so, in the case of
// a crate-local DefPathHash collision, the user can simply "roll the dice again" for all
// DefPathHashes in the crate by changing the crate disambiguator (e.g. by bumping the
// crate's version number).
//
// Children paths will only hash the local portion, and still inherit the change to the
// root hash.
let def_path_hash =
    DefPathHash::new(stable_crate_id, Hash64::new(stable_crate_id.as_u64()));

// compiler/rustc_query_impl/src/incremental.rs:82-103

/// Whether a value loaded from the on-disk cache should have its fingerprint
/// verified with `incremental_verify_ich`. If `-Zincremental-verify-ich` is
/// specified, re-hash results from the cache and make sure that they have the
/// expected fingerprint.
///
/// If not, we still verify a subset: re-hashing is too expensive to do for
/// every value. The subset rotates with the session count, covering the whole
/// cache every 32 sessions, and is deterministic so that a verification
/// failure reproduces on retry.
///
/// `to_smaller_hash` mixes both fingerprint halves because neither half is
/// evenly distributed on its own (`DefPathHash` keys share the
/// `StableCrateId`, `HirId` keys contain a sequential id).
pub(crate) fn should_verify_loaded_value(
    tcx: TyCtxt<'_>,
    dep_graph_data: &DepGraphData,
    key_fingerprint: PackedFingerprint,
) -> bool {
    let hash = Fingerprint::from(key_fingerprint).to_smaller_hash().as_u64();
    hash % 32 == dep_graph_data.session_count() % 32
        || tcx.sess.opts.unstable_opts.incremental_verify_ich
}

// compiler/rustc_data_structures/src/fingerprint.rs:45-53

#[inline]
pub fn to_smaller_hash(&self) -> Hash64 {
    // Even though both halves of the fingerprint are expected to be good
    // quality hash values, let's still combine the two values because the
    // Fingerprints in DefPathHash have the StableCrateId portion which is
    // the same for all DefPathHashes from the same crate. Combining the
    // two halves makes sure we get a good quality hash in such cases too.
    Hash64::new(self.0.wrapping_mul(3).wrapping_add(self.1))
}