dep_node.rs

//! This module defines the [`DepNode`] type which the compiler uses to represent
//! nodes in the [dependency graph]. A `DepNode` consists of a [`DepKind`] (which
//! specifies the kind of thing it represents, like a piece of HIR, MIR, etc.)
//! and a "key fingerprint", a 128-bit hash value, the exact meaning of which
//! depends on the node's `DepKind`. Together, the kind and the key fingerprint
//! fully identify a dependency node, even across multiple compilation sessions.
//! In other words, the value of the key fingerprint does not depend on anything
//! that is specific to a given compilation session, like an unpredictable
//! interning key (e.g., `NodeId`, `DefId`, `Symbol`) or the numeric value of a
//! pointer. The concept behind this could be compared to how git commit hashes
//! uniquely identify a given commit. The fingerprinting approach has
//! a few advantages:
//!
//! * A `DepNode` can simply be serialized to disk and loaded in another session
//!   without the need to do any "rebasing" (like we have to do for Spans and
//!   NodeIds) or "retracing" (like we had to do for `DefId` in earlier
//!   implementations of the dependency graph).
//! * A `Fingerprint` is just a bunch of bits, which allows `DepNode` to
//!   implement `Copy`, `Sync`, `Send`, `Freeze`, etc.
//! * Since we just have a bit pattern, `DepNode` can be mapped from disk into
//!   memory without any post-processing (e.g., "abomination-style" pointer
//!   reconstruction).
//! * Because a `DepNode` is self-contained, we can instantiate `DepNodes` that
//!   refer to things that do not exist anymore. In previous implementations
//!   `DepNode` contained a `DefId`. A `DepNode` referring to something that
//!   had been removed between the previous and the current compilation session
//!   could not be instantiated because the current compilation session
//!   contained no `DefId` for thing that had been removed.
//!
//! `DepNode` definition happens in `rustc_middle` with the
//! `define_dep_nodes!()` macro. This macro defines the `DepKind` enum. Each
//! `DepKind` has its own parameters that are needed at runtime in order to
//! construct a valid `DepNode` fingerprint. However, only `CompileCodegenUnit`
//! and `CompileMonoItem` are constructed explicitly (with
//! `make_compile_codegen_unit` and `make_compile_mono_item`).
//!
//! Because the macro sees what parameters a given `DepKind` requires, it can
//! "infer" some properties for each kind of `DepNode`:
//!
//! * Whether a `DepNode` of a given kind has any parameters at all. Some
//!   `DepNode`s could represent global concepts with only one value.
//! * Whether it is possible, in principle, to reconstruct a query key from a
//!   given `DepNode`. Many `DepKind`s only require a single `DefId` parameter,
//!   in which case it is possible to map the node's key fingerprint back to the
//!   `DefId` it was computed from. In other cases, too much information gets
//!   lost when computing a key fingerprint.
//!
//! [dependency graph]: https://rustc-dev-guide.rust-lang.org/query.html

use std::fmt;
use std::hash::Hash;

use rustc_data_structures::fingerprint::{Fingerprint, PackedFingerprint};
use rustc_data_structures::stable_hasher::{StableHasher, StableOrd, ToStableHashKey};
use rustc_hir::def_id::DefId;
use rustc_hir::definitions::DefPathHash;
use rustc_macros::{Decodable, Encodable, HashStable};
use rustc_span::Symbol;

use super::{KeyFingerprintStyle, SerializedDepNodeIndex};
use crate::dep_graph::DepNodeKey;
use crate::mir::mono::MonoItem;
use crate::ty::{TyCtxt, tls};

// `enum DepKind` is generated by `define_dep_nodes!` below.
impl DepKind {
    #[inline]
    pub(crate) fn from_u16(u: u16) -> Self {
        if u > Self::MAX {
            panic!("Invalid DepKind {u}");
        }
        // SAFETY: See comment on DEP_KIND_NUM_VARIANTS
        unsafe { std::mem::transmute(u) }
    }

    #[inline]
    pub(crate) const fn as_u16(&self) -> u16 {
        *self as u16
    }

    #[inline]
    pub const fn as_usize(&self) -> usize {
        *self as usize
    }

    /// This is the highest value a `DepKind` can have. It's used during encoding to
    /// pack information into the unused bits.
    pub(crate) const MAX: u16 = DEP_KIND_NUM_VARIANTS - 1;
}

/// Combination of a [`DepKind`] and a key fingerprint that uniquely identifies
/// a node in the dep graph.
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct DepNode {
    pub kind: DepKind,

    /// This is _typically_ a hash of the query key, but sometimes not.
    ///
    /// For example, `anon` nodes have a fingerprint that is derived from their
    /// dependencies instead of a key.
    ///
    /// In some cases the key value can be reconstructed from this fingerprint;
    /// see [`KeyFingerprintStyle`].
    pub key_fingerprint: PackedFingerprint,
}

impl DepNode {
    /// Creates a new, parameterless DepNode. This method will assert
    /// that the DepNode corresponding to the given DepKind actually
    /// does not require any parameters.
    pub fn new_no_params<'tcx>(tcx: TyCtxt<'tcx>, kind: DepKind) -> DepNode {
        debug_assert_eq!(tcx.key_fingerprint_style(kind), KeyFingerprintStyle::Unit);
        DepNode { kind, key_fingerprint: Fingerprint::ZERO.into() }
    }

    pub fn construct<'tcx, Key>(tcx: TyCtxt<'tcx>, kind: DepKind, key: &Key) -> DepNode
    where
        Key: DepNodeKey<'tcx>,
    {
        let dep_node = DepNode { kind, key_fingerprint: key.to_fingerprint(tcx).into() };

        #[cfg(debug_assertions)]
        {
            if !tcx.key_fingerprint_style(kind).is_maybe_recoverable()
                && (tcx.sess.opts.unstable_opts.incremental_info
                    || tcx.sess.opts.unstable_opts.query_dep_graph)
            {
                tcx.dep_graph.register_dep_node_debug_str(dep_node, || key.to_debug_str(tcx));
            }
        }

        dep_node
    }

    /// Construct a DepNode from the given DepKind and DefPathHash. This
    /// method will assert that the given DepKind actually requires a
    /// single DefId/DefPathHash parameter.
    pub fn from_def_path_hash<'tcx>(
        tcx: TyCtxt<'tcx>,
        def_path_hash: DefPathHash,
        kind: DepKind,
    ) -> Self {
        debug_assert!(tcx.key_fingerprint_style(kind) == KeyFingerprintStyle::DefPathHash);
        DepNode { kind, key_fingerprint: def_path_hash.0.into() }
    }
}

impl fmt::Debug for DepNode {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{:?}(", self.kind)?;

        tls::with_opt(|opt_tcx| {
            if let Some(tcx) = opt_tcx {
                if let Some(def_id) = self.extract_def_id(tcx) {
                    write!(f, "{}", tcx.def_path_debug_str(def_id))?;
                } else if let Some(ref s) = tcx.dep_graph.dep_node_debug_str(*self) {
                    write!(f, "{s}")?;
                } else {
                    write!(f, "{}", self.key_fingerprint)?;
                }
            } else {
                write!(f, "{}", self.key_fingerprint)?;
            }
            Ok(())
        })?;

        write!(f, ")")
    }
}

/// This struct stores function pointers and other metadata for a particular DepKind.
///
/// Information is retrieved by indexing the `DEP_KINDS` array using the integer value
/// of the `DepKind`. Overall, this allows to implement `DepContext` using this manual
/// jump table instead of large matches.
pub struct DepKindVTable<'tcx> {
    /// Eval-always queries do not track their dependencies, and are always recomputed, even if
    /// their inputs have not changed since the last compiler invocation. The result is still
    /// cached within one compiler invocation.
    pub is_eval_always: bool,

    /// Indicates whether and how a query key can be reconstructed from the
    /// key fingerprint of a dep node with this [`DepKind`].
    ///
    /// The [`DepNodeKey`] trait determines the fingerprint style for each key type.
    pub key_fingerprint_style: KeyFingerprintStyle,

    /// The red/green evaluation system will try to mark a specific DepNode in the
    /// dependency graph as green by recursively trying to mark the dependencies of
    /// that `DepNode` as green. While doing so, it will sometimes encounter a `DepNode`
    /// where we don't know if it is red or green and we therefore actually have
    /// to recompute its value in order to find out. Since the only piece of
    /// information that we have at that point is the `DepNode` we are trying to
    /// re-evaluate, we need some way to re-run a query from just that. This is what
    /// `force_from_dep_node()` implements.
    ///
    /// In the general case, a `DepNode` consists of a `DepKind` and an opaque
    /// "key fingerprint" that will uniquely identify the node. This key fingerprint
    /// is usually constructed by computing a stable hash of the query-key that the
    /// `DepNode` corresponds to. Consequently, it is not in general possible to go
    /// back from hash to query-key (since hash functions are not reversible). For
    /// this reason `force_from_dep_node()` is expected to fail from time to time
    /// because we just cannot find out, from the `DepNode` alone, what the
    /// corresponding query-key is and therefore cannot re-run the query.
    ///
    /// The system deals with this case letting `try_mark_green` fail which forces
    /// the root query to be re-evaluated.
    ///
    /// Now, if `force_from_dep_node()` would always fail, it would be pretty useless.
    /// Fortunately, we can use some contextual information that will allow us to
    /// reconstruct query-keys for certain kinds of `DepNode`s. In particular, we
    /// enforce by construction that the key fingerprint of certain `DepNode`s is a
    /// valid `DefPathHash`. Since we also always build a huge table that maps every
    /// `DefPathHash` in the current codebase to the corresponding `DefId`, we have
    /// everything we need to re-run the query.
    ///
    /// Take the `mir_promoted` query as an example. Like many other queries, it
    /// just has a single parameter: the `DefId` of the item it will compute the
    /// validated MIR for. Now, when we call `force_from_dep_node()` on a `DepNode`
    /// with kind `mir_promoted`, we know that the key fingerprint of the `DepNode`
    /// is actually a `DefPathHash`, and can therefore just look up the corresponding
    /// `DefId` in `tcx.def_path_hash_to_def_id`.
    pub force_from_dep_node_fn: Option<
        fn(tcx: TyCtxt<'tcx>, dep_node: DepNode, prev_index: SerializedDepNodeIndex) -> bool,
    >,

    /// Invoke a query to put the on-disk cached value in memory.
    pub promote_from_disk_fn: Option<fn(TyCtxt<'tcx>, DepNode)>,
}

/// A "work product" corresponds to a `.o` (or other) file that we
/// save in between runs. These IDs do not have a `DefId` but rather
/// some independent path or string that persists between runs without
/// the need to be mapped or unmapped. (This ensures we can serialize
/// them even in the absence of a tcx.)
#[derive(
    Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable, HashStable
)]
pub struct WorkProductId {
    hash: Fingerprint,
}

impl WorkProductId {
    pub fn from_cgu_name(cgu_name: &str) -> WorkProductId {
        let mut hasher = StableHasher::new();
        cgu_name.hash(&mut hasher);
        WorkProductId { hash: hasher.finish() }
    }
}
impl<HCX> ToStableHashKey<HCX> for WorkProductId {
    type KeyType = Fingerprint;
    #[inline]
    fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
        self.hash
    }
}
impl StableOrd for WorkProductId {
    // Fingerprint can use unstable (just a tuple of `u64`s), so WorkProductId can as well
    const CAN_USE_UNSTABLE_SORT: bool = true;

    // `WorkProductId` sort order is not affected by (de)serialization.
    const THIS_IMPLEMENTATION_HAS_BEEN_TRIPLE_CHECKED: () = ();
}

// Note: `$K` and `$V` are unused but present so this can be called by `rustc_with_all_queries`.
macro_rules! define_dep_nodes {
    (
        queries {
            $(
                $(#[$q_attr:meta])*
                fn $q_name:ident($K:ty) -> $V:ty
                // Search for (QMODLIST) to find all occurrences of this query modifier list.
                // Query modifiers are currently not used here, so skip the whole list.
                { $($modifiers:tt)* }
            )*
        }
        non_queries {
            $(
                $(#[$nq_attr:meta])*
                $nq_name:ident,
            )*
        }
    ) => {
        // This enum has more than u8::MAX variants so we need some kind of multi-byte
        // encoding. The derived Encodable/Decodable uses leb128 encoding which is
        // dense when only considering this enum. But DepKind is encoded in a larger
        // struct, and there we can take advantage of the unused bits in the u16.
        #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
        #[allow(non_camel_case_types)]
        #[repr(u16)] // Must be kept in sync with the rest of `DepKind`.
        pub enum DepKind {
            $( $(#[$nq_attr])* $nq_name, )*
            $( $(#[$q_attr])* $q_name, )*
        }

        // This computes the number of dep kind variants. Along the way, it sanity-checks that the
        // discriminants of the variants have been assigned consecutively from 0 so that they can
        // be used as a dense index, and that all discriminants fit in a `u16`.
        pub(crate) const DEP_KIND_NUM_VARIANTS: u16 = {
            let deps = &[
                $(DepKind::$nq_name,)*
                $(DepKind::$q_name,)*
            ];
            let mut i = 0;
            while i < deps.len() {
                if i != deps[i].as_usize() {
                    panic!();
                }
                i += 1;
            }
            assert!(deps.len() <= u16::MAX as usize);
            deps.len() as u16
        };

        pub(super) fn dep_kind_from_label_string(label: &str) -> Result<DepKind, ()> {
            match label {
                $( stringify!($nq_name) => Ok(self::DepKind::$nq_name), )*
                $( stringify!($q_name) => Ok(self::DepKind::$q_name), )*
                _ => Err(()),
            }
        }

        /// Contains variant => str representations for constructing
        /// DepNode groups for tests.
        #[expect(non_upper_case_globals)]
        pub mod label_strs {
            $( pub const $nq_name: &str = stringify!($nq_name); )*
            $( pub const $q_name: &str = stringify!($q_name); )*
        }
    };
}

// Create various data structures for each query, and also for a few things that aren't queries.
rustc_with_all_queries! { define_dep_nodes! }

// WARNING: `construct` is generic and does not know that `CompileCodegenUnit` takes `Symbol`s as keys.
// Be very careful changing this type signature!
pub(crate) fn make_compile_codegen_unit(tcx: TyCtxt<'_>, name: Symbol) -> DepNode {
    DepNode::construct(tcx, DepKind::CompileCodegenUnit, &name)
}

// WARNING: `construct` is generic and does not know that `CompileMonoItem` takes `MonoItem`s as keys.
// Be very careful changing this type signature!
pub(crate) fn make_compile_mono_item<'tcx>(
    tcx: TyCtxt<'tcx>,
    mono_item: &MonoItem<'tcx>,
) -> DepNode {
    DepNode::construct(tcx, DepKind::CompileMonoItem, mono_item)
}

// WARNING: `construct` is generic and does not know that `Metadata` takes `()`s as keys.
// Be very careful changing this type signature!
pub(crate) fn make_metadata(tcx: TyCtxt<'_>) -> DepNode {
    DepNode::construct(tcx, DepKind::Metadata, &())
}

impl DepNode {
    /// Extracts the DefId corresponding to this DepNode. This will work
    /// if two conditions are met:
    ///
    /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and
    /// 2. the item that the DefPath refers to exists in the current tcx.
    ///
    /// Condition (1) is determined by the DepKind variant of the
    /// DepNode. Condition (2) might not be fulfilled if a DepNode
    /// refers to something from the previous compilation session that
    /// has been removed.
    pub fn extract_def_id(&self, tcx: TyCtxt<'_>) -> Option<DefId> {
        if tcx.key_fingerprint_style(self.kind) == KeyFingerprintStyle::DefPathHash {
            tcx.def_path_hash_to_def_id(DefPathHash(self.key_fingerprint.into()))
        } else {
            None
        }
    }

    pub fn from_label_string(
        tcx: TyCtxt<'_>,
        label: &str,
        def_path_hash: DefPathHash,
    ) -> Result<DepNode, ()> {
        let kind = dep_kind_from_label_string(label)?;

        match tcx.key_fingerprint_style(kind) {
            KeyFingerprintStyle::Opaque | KeyFingerprintStyle::HirId => Err(()),
            KeyFingerprintStyle::Unit => Ok(DepNode::new_no_params(tcx, kind)),
            KeyFingerprintStyle::DefPathHash => {
                Ok(DepNode::from_def_path_hash(tcx, def_path_hash, kind))
            }
        }
    }

    pub fn has_label_string(label: &str) -> bool {
        dep_kind_from_label_string(label).is_ok()
    }
}

/// Maps a query label to its DepKind. Panics if a query with the given label does not exist.
pub fn dep_kind_from_label(label: &str) -> DepKind {
    dep_kind_from_label_string(label)
        .unwrap_or_else(|_| panic!("Query label {label} does not exist"))
}

// Some types are used a lot. Make sure they don't unintentionally get bigger.
#[cfg(target_pointer_width = "64")]
mod size_asserts {
    use rustc_data_structures::static_assert_size;

    use super::*;
    // tidy-alphabetical-start
    static_assert_size!(DepKind, 2);
    #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
    static_assert_size!(DepNode, 18);
    #[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))]
    static_assert_size!(DepNode, 24);
    // tidy-alphabetical-end
}