compiler/rustc_middle/src/dep_graph/dep_node.rs - rust - Git at Google

 //! 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,

     /// If `kind` is a query method, then its "key fingerprint" is always a
     /// stable hash of the query key.
     ///
     /// For non-query nodes, the content of this field varies:
     /// - Some dep kinds always use a dummy `ZERO` fingerprint.
     /// - Some dep kinds use the stable hash of some relevant key-like value.
     /// - Some dep kinds use the `with_anon_task` mechanism, and set their key
     ///   fingerprint to a hash derived from the task's dependencies.
     ///
     /// 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.
 crate::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);
     static_assert_size!(DepNode, 18);
     // tidy-alphabetical-end
 }
	//! 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,

	/// If `kind` is a query method, then its "key fingerprint" is always a
	/// stable hash of the query key.
	///
	/// For non-query nodes, the content of this field varies:
	/// - Some dep kinds always use a dummy `ZERO` fingerprint.
	/// - Some dep kinds use the stable hash of some relevant key-like value.
	/// - Some dep kinds use the `with_anon_task` mechanism, and set their key
	/// fingerprint to a hash derived from the task's dependencies.
	///
	/// 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.
	crate::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);
	static_assert_size!(DepNode, 18);
	// tidy-alphabetical-end
	}