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 and has a few advantages:
13 //! * A `DepNode` can simply be serialized to disk and loaded in another session
14 //! without the need to do any "rebasing (like we have to do for Spans and
15 //! NodeIds) or "retracing" like we had to do for `DefId` in earlier
16 //! implementations of the dependency graph.
17 //! * A `Fingerprint` is just a bunch of bits, which allows `DepNode` to
18 //! implement `Copy`, `Sync`, `Send`, `Freeze`, etc.
19 //! * Since we just have a bit pattern, `DepNode` can be mapped from disk into
20 //! memory without any post-processing (e.g., "abomination-style" pointer
22 //! * Because a `DepNode` is self-contained, we can instantiate `DepNodes` that
23 //! refer to things that do not exist anymore. In previous implementations
24 //! `DepNode` contained a `DefId`. A `DepNode` referring to something that
25 //! had been removed between the previous and the current compilation session
26 //! could not be instantiated because the current compilation session
27 //! contained no `DefId` for thing that had been removed.
29 //! `DepNode` definition happens in `rustc_middle` with the `define_dep_nodes!()` macro.
30 //! This macro defines the `DepKind` enum and a corresponding `DepConstructor` enum. The
31 //! `DepConstructor` enum links a `DepKind` to the parameters that are needed at runtime in order
32 //! to construct a valid `DepNode` fingerprint.
34 //! Because the macro sees what parameters a given `DepKind` requires, it can
35 //! "infer" some properties for each kind of `DepNode`:
37 //! * Whether a `DepNode` of a given kind has any parameters at all. Some
38 //! `DepNode`s could represent global concepts with only one value.
39 //! * Whether it is possible, in principle, to reconstruct a query key from a
40 //! given `DepNode`. Many `DepKind`s only require a single `DefId` parameter,
41 //! in which case it is possible to map the node's fingerprint back to the
42 //! `DefId` it was computed from. In other cases, too much information gets
43 //! lost during fingerprint computation.
45 use super::{DepContext, DepKind, FingerprintStyle}
;
46 use crate::ich
::StableHashingContext
;
48 use rustc_data_structures
::fingerprint
::{Fingerprint, PackedFingerprint}
;
49 use rustc_data_structures
::stable_hasher
::{HashStable, StableHasher}
;
50 use rustc_hir
::definitions
::DefPathHash
;
54 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)]
55 pub struct DepNode
<K
> {
57 pub hash
: PackedFingerprint
,
60 impl<K
: DepKind
> DepNode
<K
> {
61 /// Creates a new, parameterless DepNode. This method will assert
62 /// that the DepNode corresponding to the given DepKind actually
63 /// does not require any parameters.
64 pub fn new_no_params
<Tcx
>(tcx
: Tcx
, kind
: K
) -> DepNode
<K
>
66 Tcx
: super::DepContext
<DepKind
= K
>,
68 debug_assert_eq
!(tcx
.fingerprint_style(kind
), FingerprintStyle
::Unit
);
69 DepNode { kind, hash: Fingerprint::ZERO.into() }
72 pub fn construct
<Tcx
, Key
>(tcx
: Tcx
, kind
: K
, arg
: &Key
) -> DepNode
<K
>
74 Tcx
: super::DepContext
<DepKind
= K
>,
75 Key
: DepNodeParams
<Tcx
>,
77 let hash
= arg
.to_fingerprint(tcx
);
78 let dep_node
= DepNode { kind, hash: hash.into() }
;
80 #[cfg(debug_assertions)]
82 if !tcx
.fingerprint_style(kind
).reconstructible()
83 && (tcx
.sess().opts
.unstable_opts
.incremental_info
84 || tcx
.sess().opts
.unstable_opts
.query_dep_graph
)
86 tcx
.dep_graph().register_dep_node_debug_str(dep_node
, || arg
.to_debug_str(tcx
));
93 /// Construct a DepNode from the given DepKind and DefPathHash. This
94 /// method will assert that the given DepKind actually requires a
95 /// single DefId/DefPathHash parameter.
96 pub fn from_def_path_hash
<Tcx
>(tcx
: Tcx
, def_path_hash
: DefPathHash
, kind
: K
) -> Self
98 Tcx
: super::DepContext
<DepKind
= K
>,
100 debug_assert
!(tcx
.fingerprint_style(kind
) == FingerprintStyle
::DefPathHash
);
101 DepNode { kind, hash: def_path_hash.0.into() }
105 impl<K
: DepKind
> fmt
::Debug
for DepNode
<K
> {
106 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
107 K
::debug_node(self, f
)
111 pub trait DepNodeParams
<Tcx
: DepContext
>: fmt
::Debug
+ Sized
{
112 fn fingerprint_style() -> FingerprintStyle
;
114 /// This method turns the parameters of a DepNodeConstructor into an opaque
115 /// Fingerprint to be used in DepNode.
116 /// Not all DepNodeParams support being turned into a Fingerprint (they
117 /// don't need to if the corresponding DepNode is anonymous).
118 fn to_fingerprint(&self, _
: Tcx
) -> Fingerprint
{
119 panic
!("Not implemented. Accidentally called on anonymous node?")
122 fn to_debug_str(&self, _
: Tcx
) -> String
{
123 format
!("{:?}", self)
126 /// This method tries to recover the query key from the given `DepNode`,
127 /// something which is needed when forcing `DepNode`s during red-green
128 /// evaluation. The query system will only call this method if
129 /// `fingerprint_style()` is not `FingerprintStyle::Opaque`.
130 /// It is always valid to return `None` here, in which case incremental
131 /// compilation will treat the query as having changed instead of forcing it.
132 fn recover(tcx
: Tcx
, dep_node
: &DepNode
<Tcx
::DepKind
>) -> Option
<Self>;
135 impl<Tcx
: DepContext
, T
> DepNodeParams
<Tcx
> for T
137 T
: for<'a
> HashStable
<StableHashingContext
<'a
>> + fmt
::Debug
,
140 default fn fingerprint_style() -> FingerprintStyle
{
141 FingerprintStyle
::Opaque
145 default fn to_fingerprint(&self, tcx
: Tcx
) -> Fingerprint
{
146 tcx
.with_stable_hashing_context(|mut hcx
| {
147 let mut hasher
= StableHasher
::new();
148 self.hash_stable(&mut hcx
, &mut hasher
);
154 default fn to_debug_str(&self, _
: Tcx
) -> String
{
155 format
!("{:?}", *self)
159 default fn recover(_
: Tcx
, _
: &DepNode
<Tcx
::DepKind
>) -> Option
<Self> {
164 /// This struct stores metadata about each DepKind.
166 /// Information is retrieved by indexing the `DEP_KINDS` array using the integer value
167 /// of the `DepKind`. Overall, this allows to implement `DepContext` using this manual
168 /// jump table instead of large matches.
169 pub struct DepKindStruct
<Tcx
: DepContext
> {
170 /// Anonymous queries cannot be replayed from one compiler invocation to the next.
171 /// When their result is needed, it is recomputed. They are useful for fine-grained
172 /// dependency tracking, and caching within one compiler invocation.
175 /// Eval-always queries do not track their dependencies, and are always recomputed, even if
176 /// their inputs have not changed since the last compiler invocation. The result is still
177 /// cached within one compiler invocation.
178 pub is_eval_always
: bool
,
180 /// Whether the query key can be recovered from the hashed fingerprint.
181 /// See [DepNodeParams] trait for the behaviour of each key type.
182 pub fingerprint_style
: FingerprintStyle
,
184 /// The red/green evaluation system will try to mark a specific DepNode in the
185 /// dependency graph as green by recursively trying to mark the dependencies of
186 /// that `DepNode` as green. While doing so, it will sometimes encounter a `DepNode`
187 /// where we don't know if it is red or green and we therefore actually have
188 /// to recompute its value in order to find out. Since the only piece of
189 /// information that we have at that point is the `DepNode` we are trying to
190 /// re-evaluate, we need some way to re-run a query from just that. This is what
191 /// `force_from_dep_node()` implements.
193 /// In the general case, a `DepNode` consists of a `DepKind` and an opaque
194 /// GUID/fingerprint that will uniquely identify the node. This GUID/fingerprint
195 /// is usually constructed by computing a stable hash of the query-key that the
196 /// `DepNode` corresponds to. Consequently, it is not in general possible to go
197 /// back from hash to query-key (since hash functions are not reversible). For
198 /// this reason `force_from_dep_node()` is expected to fail from time to time
199 /// because we just cannot find out, from the `DepNode` alone, what the
200 /// corresponding query-key is and therefore cannot re-run the query.
202 /// The system deals with this case letting `try_mark_green` fail which forces
203 /// the root query to be re-evaluated.
205 /// Now, if `force_from_dep_node()` would always fail, it would be pretty useless.
206 /// Fortunately, we can use some contextual information that will allow us to
207 /// reconstruct query-keys for certain kinds of `DepNode`s. In particular, we
208 /// enforce by construction that the GUID/fingerprint of certain `DepNode`s is a
209 /// valid `DefPathHash`. Since we also always build a huge table that maps every
210 /// `DefPathHash` in the current codebase to the corresponding `DefId`, we have
211 /// everything we need to re-run the query.
213 /// Take the `mir_promoted` query as an example. Like many other queries, it
214 /// just has a single parameter: the `DefId` of the item it will compute the
215 /// validated MIR for. Now, when we call `force_from_dep_node()` on a `DepNode`
216 /// with kind `MirValidated`, we know that the GUID/fingerprint of the `DepNode`
217 /// is actually a `DefPathHash`, and can therefore just look up the corresponding
218 /// `DefId` in `tcx.def_path_hash_to_def_id`.
219 pub force_from_dep_node
: Option
<fn(tcx
: Tcx
, dep_node
: DepNode
<Tcx
::DepKind
>) -> bool
>,
221 /// Invoke a query to put the on-disk cached value in memory.
222 pub try_load_from_on_disk_cache
: Option
<fn(Tcx
, DepNode
<Tcx
::DepKind
>)>,
225 /// A "work product" corresponds to a `.o` (or other) file that we
226 /// save in between runs. These IDs do not have a `DefId` but rather
227 /// some independent path or string that persists between runs without
228 /// the need to be mapped or unmapped. (This ensures we can serialize
229 /// them even in the absence of a tcx.)
230 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
231 #[derive(Encodable, Decodable)]
232 pub struct WorkProductId
{
237 pub fn from_cgu_name(cgu_name
: &str) -> WorkProductId
{
238 let mut hasher
= StableHasher
::new();
239 cgu_name
.hash(&mut hasher
);
240 WorkProductId { hash: hasher.finish() }
244 impl<HCX
> HashStable
<HCX
> for WorkProductId
{
246 fn hash_stable(&self, hcx
: &mut HCX
, hasher
: &mut StableHasher
) {
247 self.hash
.hash_stable(hcx
, hasher
)