1 //! Nodes in the dependency graph.
3 //! A node in the [dependency graph] is represented by a [`DepNode`].
4 //! A `DepNode` consists of a [`DepKind`] (which
5 //! specifies the kind of thing it represents, like a piece of HIR, MIR, etc.)
6 //! and a [`Fingerprint`], a 128-bit hash value, the exact meaning of which
7 //! depends on the node's `DepKind`. Together, the kind and the fingerprint
8 //! fully identify a dependency node, even across multiple compilation sessions.
9 //! In other words, the value of the fingerprint does not depend on anything
10 //! that is specific to a given compilation session, like an unpredictable
11 //! interning key (e.g., `NodeId`, `DefId`, `Symbol`) or the numeric value of a
12 //! pointer. The concept behind this could be compared to how git commit hashes
13 //! uniquely identify a given commit. The fingerprinting approach has
16 //! * A `DepNode` can simply be serialized to disk and loaded in another session
17 //! without the need to do any "rebasing" (like we have to do for Spans and
18 //! NodeIds) or "retracing" (like we had to do for `DefId` in earlier
19 //! implementations of the dependency graph).
20 //! * A `Fingerprint` is just a bunch of bits, which allows `DepNode` to
21 //! implement `Copy`, `Sync`, `Send`, `Freeze`, etc.
22 //! * Since we just have a bit pattern, `DepNode` can be mapped from disk into
23 //! memory without any post-processing (e.g., "abomination-style" pointer
25 //! * Because a `DepNode` is self-contained, we can instantiate `DepNodes` that
26 //! refer to things that do not exist anymore. In previous implementations
27 //! `DepNode` contained a `DefId`. A `DepNode` referring to something that
28 //! had been removed between the previous and the current compilation session
29 //! could not be instantiated because the current compilation session
30 //! contained no `DefId` for thing that had been removed.
32 //! `DepNode` definition happens in the `define_dep_nodes!()` macro. This macro
33 //! defines the `DepKind` enum. Each `DepKind` has its own parameters that are
34 //! needed at runtime in order to construct a valid `DepNode` fingerprint.
35 //! However, only `CompileCodegenUnit` and `CompileMonoItem` are constructed
36 //! explicitly (with `make_compile_codegen_unit` cq `make_compile_mono_item`).
38 //! Because the macro sees what parameters a given `DepKind` requires, it can
39 //! "infer" some properties for each kind of `DepNode`:
41 //! * Whether a `DepNode` of a given kind has any parameters at all. Some
42 //! `DepNode`s could represent global concepts with only one value.
43 //! * Whether it is possible, in principle, to reconstruct a query key from a
44 //! given `DepNode`. Many `DepKind`s only require a single `DefId` parameter,
45 //! in which case it is possible to map the node's fingerprint back to the
46 //! `DefId` it was computed from. In other cases, too much information gets
47 //! lost during fingerprint computation.
49 //! `make_compile_codegen_unit` and `make_compile_mono_items`, together with
50 //! `DepNode::new()`, ensures that only valid `DepNode` instances can be
51 //! constructed. For example, the API does not allow for constructing
52 //! parameterless `DepNode`s with anything other than a zeroed out fingerprint.
53 //! More generally speaking, it relieves the user of the `DepNode` API of
54 //! having to know how to compute the expected fingerprint for a given set of
57 //! [dependency graph]: https://rustc-dev-guide.rust-lang.org/query.html
59 use crate::mir::mono::MonoItem;
60 use crate::ty::TyCtxt;
62 use rustc_data_structures::fingerprint::Fingerprint;
63 use rustc_hir::def_id::{CrateNum, DefId, LocalDefId};
64 use rustc_hir::definitions::DefPathHash;
65 use rustc_hir::{HirId, ItemLocalId};
66 use rustc_query_system::dep_graph::FingerprintStyle;
67 use rustc_span::symbol::Symbol;
70 pub use rustc_query_system::dep_graph::{DepContext, DepNodeParams};
72 /// This struct stores metadata about each DepKind.
74 /// Information is retrieved by indexing the `DEP_KINDS` array using the integer value
75 /// of the `DepKind`. Overall, this allows to implement `DepContext` using this manual
76 /// jump table instead of large matches.
77 pub struct DepKindStruct<'tcx> {
78 /// Anonymous queries cannot be replayed from one compiler invocation to the next.
79 /// When their result is needed, it is recomputed. They are useful for fine-grained
80 /// dependency tracking, and caching within one compiler invocation.
83 /// Eval-always queries do not track their dependencies, and are always recomputed, even if
84 /// their inputs have not changed since the last compiler invocation. The result is still
85 /// cached within one compiler invocation.
86 pub is_eval_always: bool,
88 /// Whether the query key can be recovered from the hashed fingerprint.
89 /// See [DepNodeParams] trait for the behaviour of each key type.
90 pub fingerprint_style: FingerprintStyle,
92 /// The red/green evaluation system will try to mark a specific DepNode in the
93 /// dependency graph as green by recursively trying to mark the dependencies of
94 /// that `DepNode` as green. While doing so, it will sometimes encounter a `DepNode`
95 /// where we don't know if it is red or green and we therefore actually have
96 /// to recompute its value in order to find out. Since the only piece of
97 /// information that we have at that point is the `DepNode` we are trying to
98 /// re-evaluate, we need some way to re-run a query from just that. This is what
99 /// `force_from_dep_node()` implements.
101 /// In the general case, a `DepNode` consists of a `DepKind` and an opaque
102 /// GUID/fingerprint that will uniquely identify the node. This GUID/fingerprint
103 /// is usually constructed by computing a stable hash of the query-key that the
104 /// `DepNode` corresponds to. Consequently, it is not in general possible to go
105 /// back from hash to query-key (since hash functions are not reversible). For
106 /// this reason `force_from_dep_node()` is expected to fail from time to time
107 /// because we just cannot find out, from the `DepNode` alone, what the
108 /// corresponding query-key is and therefore cannot re-run the query.
110 /// The system deals with this case letting `try_mark_green` fail which forces
111 /// the root query to be re-evaluated.
113 /// Now, if `force_from_dep_node()` would always fail, it would be pretty useless.
114 /// Fortunately, we can use some contextual information that will allow us to
115 /// reconstruct query-keys for certain kinds of `DepNode`s. In particular, we
116 /// enforce by construction that the GUID/fingerprint of certain `DepNode`s is a
117 /// valid `DefPathHash`. Since we also always build a huge table that maps every
118 /// `DefPathHash` in the current codebase to the corresponding `DefId`, we have
119 /// everything we need to re-run the query.
121 /// Take the `mir_promoted` query as an example. Like many other queries, it
122 /// just has a single parameter: the `DefId` of the item it will compute the
123 /// validated MIR for. Now, when we call `force_from_dep_node()` on a `DepNode`
124 /// with kind `MirValidated`, we know that the GUID/fingerprint of the `DepNode`
125 /// is actually a `DefPathHash`, and can therefore just look up the corresponding
126 /// `DefId` in `tcx.def_path_hash_to_def_id`.
127 pub force_from_dep_node: Option<fn(tcx: TyCtxt<'tcx>, dep_node: DepNode) -> bool>,
129 /// Invoke a query to put the on-disk cached value in memory.
130 pub try_load_from_on_disk_cache: Option<fn(TyCtxt<'tcx>, DepNode)>,
135 pub fn fingerprint_style(self, tcx: TyCtxt<'_>) -> FingerprintStyle {
136 // Only fetch the DepKindStruct once.
137 let data = tcx.query_kind(self);
139 return FingerprintStyle::Opaque;
141 data.fingerprint_style
145 macro_rules! define_dep_nodes {
148 [$($modifiers:tt)*] fn $variant:ident($($K:tt)*) -> $V:ty,)*) => {
151 macro_rules! make_dep_kind_array {
152 ($mod:ident) => {[ $($mod::$variant()),* ]};
155 /// This enum serves as an index into arrays built by `make_dep_kind_array`.
156 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Encodable, Decodable)]
157 #[allow(non_camel_case_types)]
159 $( $( #[$attr] )* $variant),*
162 fn dep_kind_from_label_string(label: &str) -> Result<DepKind, ()> {
164 $(stringify!($variant) => Ok(DepKind::$variant),)*
169 /// Contains variant => str representations for constructing
170 /// DepNode groups for tests.
171 #[allow(dead_code, non_upper_case_globals)]
174 pub const $variant: &str = stringify!($variant);
180 rustc_query_append!(define_dep_nodes![
181 /// We use this for most things when incr. comp. is turned off.
183 /// We use this to create a forever-red node.
185 [] fn TraitSelect() -> (),
186 [] fn CompileCodegenUnit() -> (),
187 [] fn CompileMonoItem() -> (),
190 // WARNING: `construct` is generic and does not know that `CompileCodegenUnit` takes `Symbol`s as keys.
191 // Be very careful changing this type signature!
192 pub(crate) fn make_compile_codegen_unit(tcx: TyCtxt<'_>, name: Symbol) -> DepNode {
193 DepNode::construct(tcx, DepKind::CompileCodegenUnit, &name)
196 // WARNING: `construct` is generic and does not know that `CompileMonoItem` takes `MonoItem`s as keys.
197 // Be very careful changing this type signature!
198 pub(crate) fn make_compile_mono_item<'tcx>(
200 mono_item: &MonoItem<'tcx>,
202 DepNode::construct(tcx, DepKind::CompileMonoItem, mono_item)
205 pub type DepNode = rustc_query_system::dep_graph::DepNode<DepKind>;
207 // We keep a lot of `DepNode`s in memory during compilation. It's not
208 // required that their size stay the same, but we don't want to change
209 // it inadvertently. This assert just ensures we're aware of any change.
210 #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
211 static_assert_size!(DepNode, 18);
213 #[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))]
214 static_assert_size!(DepNode, 24);
216 pub trait DepNodeExt: Sized {
217 /// Construct a DepNode from the given DepKind and DefPathHash. This
218 /// method will assert that the given DepKind actually requires a
219 /// single DefId/DefPathHash parameter.
220 fn from_def_path_hash(tcx: TyCtxt<'_>, def_path_hash: DefPathHash, kind: DepKind) -> Self;
222 /// Extracts the DefId corresponding to this DepNode. This will work
223 /// if two conditions are met:
225 /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and
226 /// 2. the item that the DefPath refers to exists in the current tcx.
228 /// Condition (1) is determined by the DepKind variant of the
229 /// DepNode. Condition (2) might not be fulfilled if a DepNode
230 /// refers to something from the previous compilation session that
231 /// has been removed.
232 fn extract_def_id(&self, tcx: TyCtxt<'_>) -> Option<DefId>;
235 fn from_label_string(
238 def_path_hash: DefPathHash,
239 ) -> Result<Self, ()>;
242 fn has_label_string(label: &str) -> bool;
245 impl DepNodeExt for DepNode {
246 /// Construct a DepNode from the given DepKind and DefPathHash. This
247 /// method will assert that the given DepKind actually requires a
248 /// single DefId/DefPathHash parameter.
249 fn from_def_path_hash(tcx: TyCtxt<'_>, def_path_hash: DefPathHash, kind: DepKind) -> DepNode {
250 debug_assert!(kind.fingerprint_style(tcx) == FingerprintStyle::DefPathHash);
251 DepNode { kind, hash: def_path_hash.0.into() }
254 /// Extracts the DefId corresponding to this DepNode. This will work
255 /// if two conditions are met:
257 /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and
258 /// 2. the item that the DefPath refers to exists in the current tcx.
260 /// Condition (1) is determined by the DepKind variant of the
261 /// DepNode. Condition (2) might not be fulfilled if a DepNode
262 /// refers to something from the previous compilation session that
263 /// has been removed.
264 fn extract_def_id<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Option<DefId> {
265 if self.kind.fingerprint_style(tcx) == FingerprintStyle::DefPathHash {
266 Some(tcx.def_path_hash_to_def_id(DefPathHash(self.hash.into()), &mut || {
267 panic!("Failed to extract DefId: {:?} {}", self.kind, self.hash)
275 fn from_label_string(
278 def_path_hash: DefPathHash,
279 ) -> Result<DepNode, ()> {
280 let kind = dep_kind_from_label_string(label)?;
282 match kind.fingerprint_style(tcx) {
283 FingerprintStyle::Opaque | FingerprintStyle::HirId => Err(()),
284 FingerprintStyle::Unit => Ok(DepNode::new_no_params(tcx, kind)),
285 FingerprintStyle::DefPathHash => {
286 Ok(DepNode::from_def_path_hash(tcx, def_path_hash, kind))
292 fn has_label_string(label: &str) -> bool {
293 dep_kind_from_label_string(label).is_ok()
297 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for () {
299 fn fingerprint_style() -> FingerprintStyle {
300 FingerprintStyle::Unit
304 fn to_fingerprint(&self, _: TyCtxt<'tcx>) -> Fingerprint {
309 fn recover(_: TyCtxt<'tcx>, _: &DepNode) -> Option<Self> {
314 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for DefId {
316 fn fingerprint_style() -> FingerprintStyle {
317 FingerprintStyle::DefPathHash
321 fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
322 tcx.def_path_hash(*self).0
326 fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
327 tcx.def_path_str(*self)
331 fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> {
332 dep_node.extract_def_id(tcx)
336 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for LocalDefId {
338 fn fingerprint_style() -> FingerprintStyle {
339 FingerprintStyle::DefPathHash
343 fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
344 self.to_def_id().to_fingerprint(tcx)
348 fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
349 self.to_def_id().to_debug_str(tcx)
353 fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> {
354 dep_node.extract_def_id(tcx).map(|id| id.expect_local())
358 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for CrateNum {
360 fn fingerprint_style() -> FingerprintStyle {
361 FingerprintStyle::DefPathHash
365 fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
366 let def_id = self.as_def_id();
367 def_id.to_fingerprint(tcx)
371 fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
372 tcx.crate_name(*self).to_string()
376 fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> {
377 dep_node.extract_def_id(tcx).map(|id| id.krate)
381 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for (DefId, DefId) {
383 fn fingerprint_style() -> FingerprintStyle {
384 FingerprintStyle::Opaque
387 // We actually would not need to specialize the implementation of this
388 // method but it's faster to combine the hashes than to instantiate a full
389 // hashing context and stable-hashing state.
391 fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
392 let (def_id_0, def_id_1) = *self;
394 let def_path_hash_0 = tcx.def_path_hash(def_id_0);
395 let def_path_hash_1 = tcx.def_path_hash(def_id_1);
397 def_path_hash_0.0.combine(def_path_hash_1.0)
401 fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
402 let (def_id_0, def_id_1) = *self;
404 format!("({}, {})", tcx.def_path_debug_str(def_id_0), tcx.def_path_debug_str(def_id_1))
408 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for HirId {
410 fn fingerprint_style() -> FingerprintStyle {
411 FingerprintStyle::HirId
414 // We actually would not need to specialize the implementation of this
415 // method but it's faster to combine the hashes than to instantiate a full
416 // hashing context and stable-hashing state.
418 fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
419 let HirId { owner, local_id } = *self;
420 let def_path_hash = tcx.def_path_hash(owner.to_def_id());
422 // `owner` is local, so is completely defined by the local hash
423 def_path_hash.local_hash(),
424 local_id.as_u32().into(),
429 fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
430 let HirId { owner, local_id } = *self;
431 format!("{}.{}", tcx.def_path_str(owner.to_def_id()), local_id.as_u32())
435 fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> {
436 if dep_node.kind.fingerprint_style(tcx) == FingerprintStyle::HirId {
437 let (local_hash, local_id) = Fingerprint::from(dep_node.hash).as_value();
438 let def_path_hash = DefPathHash::new(tcx.sess.local_stable_crate_id(), local_hash);
440 .def_path_hash_to_def_id(def_path_hash, &mut || {
441 panic!("Failed to extract HirId: {:?} {}", dep_node.kind, dep_node.hash)
444 let local_id = local_id
446 .unwrap_or_else(|_| panic!("local id should be u32, found {:?}", local_id));
447 Some(HirId { owner, local_id: ItemLocalId::from_u32(local_id) })