rustc_query_system/dep_graph/
dep_node.rs

1//! This module defines the [`DepNode`] type which the compiler uses to represent
2//! nodes in the [dependency graph]. A `DepNode` consists of a [`DepKind`] (which
3//! specifies the kind of thing it represents, like a piece of HIR, MIR, etc.)
4//! and a [`Fingerprint`], a 128-bit hash value, the exact meaning of which
5//! depends on the node's `DepKind`. Together, the kind and the fingerprint
6//! fully identify a dependency node, even across multiple compilation sessions.
7//! In other words, the value of the fingerprint does not depend on anything
8//! that is specific to a given compilation session, like an unpredictable
9//! interning key (e.g., `NodeId`, `DefId`, `Symbol`) or the numeric value of a
10//! pointer. The concept behind this could be compared to how git commit hashes
11//! uniquely identify a given commit. The fingerprinting approach has
12//! a few advantages:
13//!
14//! * A `DepNode` can simply be serialized to disk and loaded in another session
15//!   without the need to do any "rebasing" (like we have to do for Spans and
16//!   NodeIds) or "retracing" (like we had to do for `DefId` in earlier
17//!   implementations of the dependency graph).
18//! * A `Fingerprint` is just a bunch of bits, which allows `DepNode` to
19//!   implement `Copy`, `Sync`, `Send`, `Freeze`, etc.
20//! * Since we just have a bit pattern, `DepNode` can be mapped from disk into
21//!   memory without any post-processing (e.g., "abomination-style" pointer
22//!   reconstruction).
23//! * Because a `DepNode` is self-contained, we can instantiate `DepNodes` that
24//!   refer to things that do not exist anymore. In previous implementations
25//!   `DepNode` contained a `DefId`. A `DepNode` referring to something that
26//!   had been removed between the previous and the current compilation session
27//!   could not be instantiated because the current compilation session
28//!   contained no `DefId` for thing that had been removed.
29//!
30//! `DepNode` definition happens in `rustc_middle` with the
31//! `define_dep_nodes!()` macro. This macro defines the `DepKind` enum. Each
32//! `DepKind` has its own parameters that are needed at runtime in order to
33//! construct a valid `DepNode` fingerprint. However, only `CompileCodegenUnit`
34//! and `CompileMonoItem` are constructed explicitly (with
35//! `make_compile_codegen_unit` and `make_compile_mono_item`).
36//!
37//! Because the macro sees what parameters a given `DepKind` requires, it can
38//! "infer" some properties for each kind of `DepNode`:
39//!
40//! * Whether a `DepNode` of a given kind has any parameters at all. Some
41//!   `DepNode`s could represent global concepts with only one value.
42//! * Whether it is possible, in principle, to reconstruct a query key from a
43//!   given `DepNode`. Many `DepKind`s only require a single `DefId` parameter,
44//!   in which case it is possible to map the node's fingerprint back to the
45//!   `DefId` it was computed from. In other cases, too much information gets
46//!   lost during fingerprint computation.
47//!
48//! `make_compile_codegen_unit` and `make_compile_mono_items`, together with
49//! `DepNode::new()`, ensure that only valid `DepNode` instances can be
50//! constructed. For example, the API does not allow for constructing
51//! parameterless `DepNode`s with anything other than a zeroed out fingerprint.
52//! More generally speaking, it relieves the user of the `DepNode` API of
53//! having to know how to compute the expected fingerprint for a given set of
54//! node parameters.
55//!
56//! [dependency graph]: https://rustc-dev-guide.rust-lang.org/query.html
57
58use std::fmt;
59use std::hash::Hash;
60
61use rustc_data_structures::AtomicRef;
62use rustc_data_structures::fingerprint::{Fingerprint, PackedFingerprint};
63use rustc_data_structures::stable_hasher::{HashStable, StableHasher, StableOrd, ToStableHashKey};
64use rustc_hir::definitions::DefPathHash;
65use rustc_macros::{Decodable, Encodable};
66
67use super::{DepContext, FingerprintStyle};
68use crate::ich::StableHashingContext;
69
70/// This serves as an index into arrays built by `make_dep_kind_array`.
71#[derive(Clone, Copy, PartialEq, Eq, Hash)]
72pub struct DepKind {
73    variant: u16,
74}
75
76impl DepKind {
77    #[inline]
78    pub const fn new(variant: u16) -> Self {
79        Self { variant }
80    }
81
82    #[inline]
83    pub const fn as_inner(&self) -> u16 {
84        self.variant
85    }
86
87    #[inline]
88    pub const fn as_usize(&self) -> usize {
89        self.variant as usize
90    }
91}
92
93pub fn default_dep_kind_debug(kind: DepKind, f: &mut fmt::Formatter<'_>) -> fmt::Result {
94    f.debug_struct("DepKind").field("variant", &kind.variant).finish()
95}
96
97pub static DEP_KIND_DEBUG: AtomicRef<fn(DepKind, &mut fmt::Formatter<'_>) -> fmt::Result> =
98    AtomicRef::new(&(default_dep_kind_debug as fn(_, &mut fmt::Formatter<'_>) -> _));
99
100impl fmt::Debug for DepKind {
101    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
102        (*DEP_KIND_DEBUG)(*self, f)
103    }
104}
105
106#[derive(Clone, Copy, PartialEq, Eq, Hash)]
107pub struct DepNode {
108    pub kind: DepKind,
109    pub hash: PackedFingerprint,
110}
111
112impl DepNode {
113    /// Creates a new, parameterless DepNode. This method will assert
114    /// that the DepNode corresponding to the given DepKind actually
115    /// does not require any parameters.
116    pub fn new_no_params<Tcx>(tcx: Tcx, kind: DepKind) -> DepNode
117    where
118        Tcx: super::DepContext,
119    {
120        debug_assert_eq!(tcx.fingerprint_style(kind), FingerprintStyle::Unit);
121        DepNode { kind, hash: Fingerprint::ZERO.into() }
122    }
123
124    pub fn construct<Tcx, Key>(tcx: Tcx, kind: DepKind, arg: &Key) -> DepNode
125    where
126        Tcx: super::DepContext,
127        Key: DepNodeParams<Tcx>,
128    {
129        let hash = arg.to_fingerprint(tcx);
130        let dep_node = DepNode { kind, hash: hash.into() };
131
132        #[cfg(debug_assertions)]
133        {
134            if !tcx.fingerprint_style(kind).reconstructible()
135                && (tcx.sess().opts.unstable_opts.incremental_info
136                    || tcx.sess().opts.unstable_opts.query_dep_graph)
137            {
138                tcx.dep_graph().register_dep_node_debug_str(dep_node, || arg.to_debug_str(tcx));
139            }
140        }
141
142        dep_node
143    }
144
145    /// Construct a DepNode from the given DepKind and DefPathHash. This
146    /// method will assert that the given DepKind actually requires a
147    /// single DefId/DefPathHash parameter.
148    pub fn from_def_path_hash<Tcx>(tcx: Tcx, def_path_hash: DefPathHash, kind: DepKind) -> Self
149    where
150        Tcx: super::DepContext,
151    {
152        debug_assert!(tcx.fingerprint_style(kind) == FingerprintStyle::DefPathHash);
153        DepNode { kind, hash: def_path_hash.0.into() }
154    }
155}
156
157pub fn default_dep_node_debug(node: DepNode, f: &mut fmt::Formatter<'_>) -> fmt::Result {
158    f.debug_struct("DepNode").field("kind", &node.kind).field("hash", &node.hash).finish()
159}
160
161pub static DEP_NODE_DEBUG: AtomicRef<fn(DepNode, &mut fmt::Formatter<'_>) -> fmt::Result> =
162    AtomicRef::new(&(default_dep_node_debug as fn(_, &mut fmt::Formatter<'_>) -> _));
163
164impl fmt::Debug for DepNode {
165    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
166        (*DEP_NODE_DEBUG)(*self, f)
167    }
168}
169
170pub trait DepNodeParams<Tcx: DepContext>: fmt::Debug + Sized {
171    fn fingerprint_style() -> FingerprintStyle;
172
173    /// This method turns the parameters of a DepNodeConstructor into an opaque
174    /// Fingerprint to be used in DepNode.
175    /// Not all DepNodeParams support being turned into a Fingerprint (they
176    /// don't need to if the corresponding DepNode is anonymous).
177    fn to_fingerprint(&self, _: Tcx) -> Fingerprint {
178        panic!("Not implemented. Accidentally called on anonymous node?")
179    }
180
181    fn to_debug_str(&self, _: Tcx) -> String {
182        format!("{self:?}")
183    }
184
185    /// This method tries to recover the query key from the given `DepNode`,
186    /// something which is needed when forcing `DepNode`s during red-green
187    /// evaluation. The query system will only call this method if
188    /// `fingerprint_style()` is not `FingerprintStyle::Opaque`.
189    /// It is always valid to return `None` here, in which case incremental
190    /// compilation will treat the query as having changed instead of forcing it.
191    fn recover(tcx: Tcx, dep_node: &DepNode) -> Option<Self>;
192}
193
194impl<Tcx: DepContext, T> DepNodeParams<Tcx> for T
195where
196    T: for<'a> HashStable<StableHashingContext<'a>> + fmt::Debug,
197{
198    #[inline(always)]
199    default fn fingerprint_style() -> FingerprintStyle {
200        FingerprintStyle::Opaque
201    }
202
203    #[inline(always)]
204    default fn to_fingerprint(&self, tcx: Tcx) -> Fingerprint {
205        tcx.with_stable_hashing_context(|mut hcx| {
206            let mut hasher = StableHasher::new();
207            self.hash_stable(&mut hcx, &mut hasher);
208            hasher.finish()
209        })
210    }
211
212    #[inline(always)]
213    default fn to_debug_str(&self, _: Tcx) -> String {
214        format!("{:?}", *self)
215    }
216
217    #[inline(always)]
218    default fn recover(_: Tcx, _: &DepNode) -> Option<Self> {
219        None
220    }
221}
222
223/// This struct stores metadata about each DepKind.
224///
225/// Information is retrieved by indexing the `DEP_KINDS` array using the integer value
226/// of the `DepKind`. Overall, this allows to implement `DepContext` using this manual
227/// jump table instead of large matches.
228pub struct DepKindStruct<Tcx: DepContext> {
229    /// Anonymous queries cannot be replayed from one compiler invocation to the next.
230    /// When their result is needed, it is recomputed. They are useful for fine-grained
231    /// dependency tracking, and caching within one compiler invocation.
232    pub is_anon: bool,
233
234    /// Eval-always queries do not track their dependencies, and are always recomputed, even if
235    /// their inputs have not changed since the last compiler invocation. The result is still
236    /// cached within one compiler invocation.
237    pub is_eval_always: bool,
238
239    /// Whether the query key can be recovered from the hashed fingerprint.
240    /// See [DepNodeParams] trait for the behaviour of each key type.
241    pub fingerprint_style: FingerprintStyle,
242
243    /// The red/green evaluation system will try to mark a specific DepNode in the
244    /// dependency graph as green by recursively trying to mark the dependencies of
245    /// that `DepNode` as green. While doing so, it will sometimes encounter a `DepNode`
246    /// where we don't know if it is red or green and we therefore actually have
247    /// to recompute its value in order to find out. Since the only piece of
248    /// information that we have at that point is the `DepNode` we are trying to
249    /// re-evaluate, we need some way to re-run a query from just that. This is what
250    /// `force_from_dep_node()` implements.
251    ///
252    /// In the general case, a `DepNode` consists of a `DepKind` and an opaque
253    /// GUID/fingerprint that will uniquely identify the node. This GUID/fingerprint
254    /// is usually constructed by computing a stable hash of the query-key that the
255    /// `DepNode` corresponds to. Consequently, it is not in general possible to go
256    /// back from hash to query-key (since hash functions are not reversible). For
257    /// this reason `force_from_dep_node()` is expected to fail from time to time
258    /// because we just cannot find out, from the `DepNode` alone, what the
259    /// corresponding query-key is and therefore cannot re-run the query.
260    ///
261    /// The system deals with this case letting `try_mark_green` fail which forces
262    /// the root query to be re-evaluated.
263    ///
264    /// Now, if `force_from_dep_node()` would always fail, it would be pretty useless.
265    /// Fortunately, we can use some contextual information that will allow us to
266    /// reconstruct query-keys for certain kinds of `DepNode`s. In particular, we
267    /// enforce by construction that the GUID/fingerprint of certain `DepNode`s is a
268    /// valid `DefPathHash`. Since we also always build a huge table that maps every
269    /// `DefPathHash` in the current codebase to the corresponding `DefId`, we have
270    /// everything we need to re-run the query.
271    ///
272    /// Take the `mir_promoted` query as an example. Like many other queries, it
273    /// just has a single parameter: the `DefId` of the item it will compute the
274    /// validated MIR for. Now, when we call `force_from_dep_node()` on a `DepNode`
275    /// with kind `MirValidated`, we know that the GUID/fingerprint of the `DepNode`
276    /// is actually a `DefPathHash`, and can therefore just look up the corresponding
277    /// `DefId` in `tcx.def_path_hash_to_def_id`.
278    pub force_from_dep_node: Option<fn(tcx: Tcx, dep_node: DepNode) -> bool>,
279
280    /// Invoke a query to put the on-disk cached value in memory.
281    pub try_load_from_on_disk_cache: Option<fn(Tcx, DepNode)>,
282
283    /// The name of this dep kind.
284    pub name: &'static &'static str,
285}
286
287/// A "work product" corresponds to a `.o` (or other) file that we
288/// save in between runs. These IDs do not have a `DefId` but rather
289/// some independent path or string that persists between runs without
290/// the need to be mapped or unmapped. (This ensures we can serialize
291/// them even in the absence of a tcx.)
292#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)]
293pub struct WorkProductId {
294    hash: Fingerprint,
295}
296
297impl WorkProductId {
298    pub fn from_cgu_name(cgu_name: &str) -> WorkProductId {
299        let mut hasher = StableHasher::new();
300        cgu_name.hash(&mut hasher);
301        WorkProductId { hash: hasher.finish() }
302    }
303}
304
305impl<HCX> HashStable<HCX> for WorkProductId {
306    #[inline]
307    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
308        self.hash.hash_stable(hcx, hasher)
309    }
310}
311impl<HCX> ToStableHashKey<HCX> for WorkProductId {
312    type KeyType = Fingerprint;
313    #[inline]
314    fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
315        self.hash
316    }
317}
318impl StableOrd for WorkProductId {
319    // Fingerprint can use unstable (just a tuple of `u64`s), so WorkProductId can as well
320    const CAN_USE_UNSTABLE_SORT: bool = true;
321
322    // `WorkProductId` sort order is not affected by (de)serialization.
323    const THIS_IMPLEMENTATION_HAS_BEEN_TRIPLE_CHECKED: () = ();
324}
325
326// Some types are used a lot. Make sure they don't unintentionally get bigger.
327#[cfg(target_pointer_width = "64")]
328mod size_asserts {
329    use rustc_data_structures::static_assert_size;
330
331    use super::*;
332    // tidy-alphabetical-start
333    static_assert_size!(DepKind, 2);
334    #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
335    static_assert_size!(DepNode, 18);
336    #[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))]
337    static_assert_size!(DepNode, 24);
338    // tidy-alphabetical-end
339}