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, CRATE_DEF_INDEX};
64 use rustc_hir::definitions::DefPathHash;
66 use rustc_span::symbol::Symbol;
69 pub use rustc_query_system::dep_graph::{DepContext, DepNodeParams};
71 /// This struct stores metadata about each DepKind.
73 /// Information is retrieved by indexing the `DEP_KINDS` array using the integer value
74 /// of the `DepKind`. Overall, this allows to implement `DepContext` using this manual
75 /// jump table instead of large matches.
76 pub struct DepKindStruct {
77 /// Whether the DepNode has parameters (query keys).
78 pub(super) has_params: bool,
80 /// Anonymous queries cannot be replayed from one compiler invocation to the next.
81 /// When their result is needed, it is recomputed. They are useful for fine-grained
82 /// dependency tracking, and caching within one compiler invocation.
83 pub(super) is_anon: bool,
85 /// Eval-always queries do not track their dependencies, and are always recomputed, even if
86 /// their inputs have not changed since the last compiler invocation. The result is still
87 /// cached within one compiler invocation.
88 pub(super) is_eval_always: bool,
90 /// Whether the query key can be recovered from the hashed fingerprint.
91 /// See [DepNodeParams] trait for the behaviour of each key type.
92 // FIXME: Make this a simple boolean once DepNodeParams::can_reconstruct_query_key
93 // can be made a specialized associated const.
94 can_reconstruct_query_key: fn() -> bool,
97 impl std::ops::Deref for DepKind {
98 type Target = DepKindStruct;
99 fn deref(&self) -> &DepKindStruct {
100 &DEP_KINDS[*self as usize]
106 pub fn can_reconstruct_query_key(&self) -> bool {
107 // Only fetch the DepKindStruct once.
108 let data: &DepKindStruct = &**self;
113 (data.can_reconstruct_query_key)()
117 // erase!() just makes tokens go away. It's used to specify which macro argument
118 // is repeated (i.e., which sub-expression of the macro we are in) but don't need
119 // to actually use any of the arguments.
124 macro_rules! is_anon_attr {
133 macro_rules! is_eval_always_attr {
142 macro_rules! contains_anon_attr {
143 ($($attr:ident $(($($attr_args:tt)*))* ),*) => ({$(is_anon_attr!($attr) | )* false});
146 macro_rules! contains_eval_always_attr {
147 ($($attr:ident $(($($attr_args:tt)*))* ),*) => ({$(is_eval_always_attr!($attr) | )* false});
150 #[allow(non_upper_case_globals)]
153 use crate::ty::query::query_keys;
155 // We use this for most things when incr. comp. is turned off.
156 pub const Null: DepKindStruct = DepKindStruct {
159 is_eval_always: false,
161 can_reconstruct_query_key: || true,
164 pub const TraitSelect: DepKindStruct = DepKindStruct {
167 is_eval_always: false,
169 can_reconstruct_query_key: || true,
172 pub const CompileCodegenUnit: DepKindStruct = DepKindStruct {
175 is_eval_always: false,
177 can_reconstruct_query_key: || false,
180 pub const CompileMonoItem: DepKindStruct = DepKindStruct {
183 is_eval_always: false,
185 can_reconstruct_query_key: || false,
188 macro_rules! define_query_dep_kinds {
191 $variant:ident $(( $tuple_arg_ty:ty $(,)? ))*
193 $(pub const $variant: DepKindStruct = {
194 const has_params: bool = $({ erase!($tuple_arg_ty); true } |)* false;
195 const is_anon: bool = contains_anon_attr!($($attrs)*);
196 const is_eval_always: bool = contains_eval_always_attr!($($attrs)*);
199 fn can_reconstruct_query_key() -> bool {
200 <query_keys::$variant<'_> as DepNodeParams<TyCtxt<'_>>>
201 ::can_reconstruct_query_key()
208 can_reconstruct_query_key,
214 rustc_dep_node_append!([define_query_dep_kinds!][]);
217 macro_rules! define_dep_nodes {
221 $variant:ident $(( $tuple_arg_ty:ty $(,)? ))*
225 macro_rules! make_dep_kind_array {
226 ($mod:ident) => {[ $(($mod::$variant),)* ]};
229 static DEP_KINDS: &[DepKindStruct] = &make_dep_kind_array!(dep_kind);
231 /// This enum serves as an index into the `DEP_KINDS` array.
232 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Encodable, Decodable)]
233 #[allow(non_camel_case_types)]
238 fn dep_kind_from_label_string(label: &str) -> Result<DepKind, ()> {
240 $(stringify!($variant) => Ok(DepKind::$variant),)*
245 /// Contains variant => str representations for constructing
246 /// DepNode groups for tests.
247 #[allow(dead_code, non_upper_case_globals)]
250 pub const $variant: &str = stringify!($variant);
256 rustc_dep_node_append!([define_dep_nodes!][ <'tcx>
257 // We use this for most things when incr. comp. is turned off.
262 // WARNING: if `Symbol` is changed, make sure you update `make_compile_codegen_unit` below.
263 [] CompileCodegenUnit(Symbol),
265 // WARNING: if `MonoItem` is changed, make sure you update `make_compile_mono_item` below.
266 // Only used by rustc_codegen_cranelift
267 [] CompileMonoItem(MonoItem),
270 // WARNING: `construct` is generic and does not know that `CompileCodegenUnit` takes `Symbol`s as keys.
271 // Be very careful changing this type signature!
272 crate fn make_compile_codegen_unit(tcx: TyCtxt<'_>, name: Symbol) -> DepNode {
273 DepNode::construct(tcx, DepKind::CompileCodegenUnit, &name)
276 // WARNING: `construct` is generic and does not know that `CompileMonoItem` takes `MonoItem`s as keys.
277 // Be very careful changing this type signature!
278 crate fn make_compile_mono_item(tcx: TyCtxt<'tcx>, mono_item: &MonoItem<'tcx>) -> DepNode {
279 DepNode::construct(tcx, DepKind::CompileMonoItem, mono_item)
282 pub type DepNode = rustc_query_system::dep_graph::DepNode<DepKind>;
284 // We keep a lot of `DepNode`s in memory during compilation. It's not
285 // required that their size stay the same, but we don't want to change
286 // it inadvertently. This assert just ensures we're aware of any change.
287 #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
288 static_assert_size!(DepNode, 17);
290 #[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))]
291 static_assert_size!(DepNode, 24);
293 pub trait DepNodeExt: Sized {
294 /// Construct a DepNode from the given DepKind and DefPathHash. This
295 /// method will assert that the given DepKind actually requires a
296 /// single DefId/DefPathHash parameter.
297 fn from_def_path_hash(def_path_hash: DefPathHash, kind: DepKind) -> Self;
299 /// Extracts the DefId corresponding to this DepNode. This will work
300 /// if two conditions are met:
302 /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and
303 /// 2. the item that the DefPath refers to exists in the current tcx.
305 /// Condition (1) is determined by the DepKind variant of the
306 /// DepNode. Condition (2) might not be fulfilled if a DepNode
307 /// refers to something from the previous compilation session that
308 /// has been removed.
309 fn extract_def_id(&self, tcx: TyCtxt<'_>) -> Option<DefId>;
312 fn from_label_string(label: &str, def_path_hash: DefPathHash) -> Result<Self, ()>;
315 fn has_label_string(label: &str) -> bool;
318 impl DepNodeExt for DepNode {
319 /// Construct a DepNode from the given DepKind and DefPathHash. This
320 /// method will assert that the given DepKind actually requires a
321 /// single DefId/DefPathHash parameter.
322 fn from_def_path_hash(def_path_hash: DefPathHash, kind: DepKind) -> DepNode {
323 debug_assert!(kind.can_reconstruct_query_key() && kind.has_params);
324 DepNode { kind, hash: def_path_hash.0.into() }
327 /// Extracts the DefId corresponding to this DepNode. This will work
328 /// if two conditions are met:
330 /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and
331 /// 2. the item that the DefPath refers to exists in the current tcx.
333 /// Condition (1) is determined by the DepKind variant of the
334 /// DepNode. Condition (2) might not be fulfilled if a DepNode
335 /// refers to something from the previous compilation session that
336 /// has been removed.
337 fn extract_def_id(&self, tcx: TyCtxt<'tcx>) -> Option<DefId> {
338 if self.kind.can_reconstruct_query_key() {
339 tcx.on_disk_cache.as_ref()?.def_path_hash_to_def_id(tcx, DefPathHash(self.hash.into()))
346 fn from_label_string(label: &str, def_path_hash: DefPathHash) -> Result<DepNode, ()> {
347 let kind = dep_kind_from_label_string(label)?;
349 if !kind.can_reconstruct_query_key() {
354 Ok(DepNode::from_def_path_hash(def_path_hash, kind))
356 Ok(DepNode::new_no_params(kind))
361 fn has_label_string(label: &str) -> bool {
362 dep_kind_from_label_string(label).is_ok()
366 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for () {
368 fn can_reconstruct_query_key() -> bool {
372 fn to_fingerprint(&self, _: TyCtxt<'tcx>) -> Fingerprint {
376 fn recover(_: TyCtxt<'tcx>, _: &DepNode) -> Option<Self> {
381 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for DefId {
383 fn can_reconstruct_query_key() -> bool {
387 fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
388 let hash = tcx.def_path_hash(*self);
389 // If this is a foreign `DefId`, store its current value
390 // in the incremental cache. When we decode the cache,
391 // we will use the old DefIndex as an initial guess for
392 // a lookup into the crate metadata.
393 if !self.is_local() {
394 if let Some(cache) = &tcx.on_disk_cache {
395 cache.store_foreign_def_id_hash(*self, hash);
401 fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
402 tcx.def_path_str(*self)
405 fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> {
406 dep_node.extract_def_id(tcx)
410 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for LocalDefId {
412 fn can_reconstruct_query_key() -> bool {
416 fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
417 self.to_def_id().to_fingerprint(tcx)
420 fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
421 self.to_def_id().to_debug_str(tcx)
424 fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> {
425 dep_node.extract_def_id(tcx).map(|id| id.expect_local())
429 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for CrateNum {
431 fn can_reconstruct_query_key() -> bool {
435 fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
436 let def_id = DefId { krate: *self, index: CRATE_DEF_INDEX };
437 def_id.to_fingerprint(tcx)
440 fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
441 tcx.crate_name(*self).to_string()
444 fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> {
445 dep_node.extract_def_id(tcx).map(|id| id.krate)
449 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for (DefId, DefId) {
451 fn can_reconstruct_query_key() -> bool {
455 // We actually would not need to specialize the implementation of this
456 // method but it's faster to combine the hashes than to instantiate a full
457 // hashing context and stable-hashing state.
458 fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
459 let (def_id_0, def_id_1) = *self;
461 let def_path_hash_0 = tcx.def_path_hash(def_id_0);
462 let def_path_hash_1 = tcx.def_path_hash(def_id_1);
464 def_path_hash_0.0.combine(def_path_hash_1.0)
467 fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String {
468 let (def_id_0, def_id_1) = *self;
470 format!("({}, {})", tcx.def_path_debug_str(def_id_0), tcx.def_path_debug_str(def_id_1))
474 impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for HirId {
476 fn can_reconstruct_query_key() -> bool {
480 // We actually would not need to specialize the implementation of this
481 // method but it's faster to combine the hashes than to instantiate a full
482 // hashing context and stable-hashing state.
483 fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint {
484 let HirId { owner, local_id } = *self;
486 let def_path_hash = tcx.def_path_hash(owner.to_def_id());
487 let local_id = Fingerprint::from_smaller_hash(local_id.as_u32().into());
489 def_path_hash.0.combine(local_id)