1 //! This module defines the `DepNode` type which the compiler uses to represent
2 //! nodes in the dependency graph.
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 and has a few advantages:
15 //! * A `DepNode` can simply be serialized to disk and loaded in another session
16 //! without the need to do any "rebasing" (like we have to do for Spans and
17 //! NodeIds) or "retracing" (like we had to do for `DefId` in earlier
18 //! implementations of the dependency graph).
19 //! * A `Fingerprint` is just a bunch of bits, which allows `DepNode` to
20 //! implement `Copy`, `Sync`, `Send`, `Freeze`, etc.
21 //! * Since we just have a bit pattern, `DepNode` can be mapped from disk into
22 //! memory without any post-processing (e.g., "abomination-style" pointer
24 //! * Because a `DepNode` is self-contained, we can instantiate `DepNodes` that
25 //! refer to things that do not exist anymore. In previous implementations
26 //! `DepNode` contained a `DefId`. A `DepNode` referring to something that
27 //! had been removed between the previous and the current compilation session
28 //! could not be instantiated because the current compilation session
29 //! contained no `DefId` for thing that had been removed.
31 //! `DepNode` definition happens in the `define_dep_nodes!()` macro. This macro
32 //! defines the `DepKind` enum and a corresponding `DepConstructor` enum. The
33 //! `DepConstructor` enum links a `DepKind` to the parameters that are needed at
34 //! runtime in order to construct a valid `DepNode` fingerprint.
36 //! Because the macro sees what parameters a given `DepKind` requires, it can
37 //! "infer" some properties for each kind of `DepNode`:
39 //! * Whether a `DepNode` of a given kind has any parameters at all. Some
40 //! `DepNode`s could represent global concepts with only one value.
41 //! * Whether it is possible, in principle, to reconstruct a query key from a
42 //! given `DepNode`. Many `DepKind`s only require a single `DefId` parameter,
43 //! in which case it is possible to map the node's fingerprint back to the
44 //! `DefId` it was computed from. In other cases, too much information gets
45 //! lost during fingerprint computation.
47 //! The `DepConstructor` enum, together with `DepNode::new()`, ensures that only
48 //! valid `DepNode` instances can be constructed. For example, the API does not
49 //! allow for constructing parameterless `DepNode`s with anything other
50 //! than a zeroed out fingerprint. More generally speaking, it relieves the
51 //! user of the `DepNode` API of having to know how to compute the expected
52 //! fingerprint for a given set of node parameters.
54 use crate::mir
::interpret
::{GlobalId, LitToConstInput}
;
56 use crate::traits
::query
::{
57 CanonicalPredicateGoal
, CanonicalProjectionGoal
, CanonicalTyGoal
,
58 CanonicalTypeOpAscribeUserTypeGoal
, CanonicalTypeOpEqGoal
, CanonicalTypeOpNormalizeGoal
,
59 CanonicalTypeOpProvePredicateGoal
, CanonicalTypeOpSubtypeGoal
,
61 use crate::ty
::subst
::{GenericArg, SubstsRef}
;
62 use crate::ty
::{self, ParamEnvAnd, Ty, TyCtxt}
;
64 use rustc_data_structures
::fingerprint
::Fingerprint
;
65 use rustc_hir
::def_id
::{CrateNum, DefId, LocalDefId, CRATE_DEF_INDEX}
;
66 use rustc_hir
::definitions
::DefPathHash
;
68 use rustc_span
::symbol
::Symbol
;
71 pub use rustc_query_system
::dep_graph
::{DepContext, DepNodeParams}
;
73 // erase!() just makes tokens go away. It's used to specify which macro argument
74 // is repeated (i.e., which sub-expression of the macro we are in) but don't need
75 // to actually use any of the arguments.
80 macro_rules
! is_anon_attr
{
89 macro_rules
! is_eval_always_attr
{
98 macro_rules
! contains_anon_attr
{
99 ($
($attr
:ident $
(($
($attr_args
:tt
)*))* ),*) => ({$(is_anon_attr!($attr) | )* false}
);
102 macro_rules
! contains_eval_always_attr
{
103 ($
($attr
:ident $
(($
($attr_args
:tt
)*))* ),*) => ({$(is_eval_always_attr!($attr) | )* false}
);
106 macro_rules
! define_dep_nodes
{
110 $variant
:ident $
(( $tuple_arg_ty
:ty $
(,)?
))*
113 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)]
114 #[allow(non_camel_case_types)]
120 #[allow(unreachable_code)]
121 pub fn can_reconstruct_query_key
<$tcx
>(&self) -> bool
{
124 DepKind
:: $variant
=> {
125 if contains_anon_attr
!($
($attrs
)*) {
131 return <$tuple_arg_ty
as DepNodeParams
<TyCtxt
<'_
>>>
132 ::can_reconstruct_query_key();
141 pub fn is_anon(&self) -> bool
{
144 DepKind
:: $variant
=> { contains_anon_attr!($($attrs)*) }
149 pub fn is_eval_always(&self) -> bool
{
152 DepKind
:: $variant
=> { contains_eval_always_attr!($($attrs)*) }
157 #[allow(unreachable_code)]
158 pub fn has_params(&self) -> bool
{
161 DepKind
:: $variant
=> {
164 erase
!($tuple_arg_ty
);
175 pub struct DepConstructor
;
177 #[allow(non_camel_case_types)]
178 impl DepConstructor
{
181 #[allow(unreachable_code, non_snake_case)]
182 pub fn $
variant(_tcx
: TyCtxt
<'_
>, $
(arg
: $tuple_arg_ty
)*) -> DepNode
{
185 erase
!($tuple_arg_ty
);
186 return DepNode
::construct(_tcx
, DepKind
::$variant
, &arg
)
189 return DepNode
::construct(_tcx
, DepKind
::$variant
, &())
194 pub type DepNode
= rustc_query_system
::dep_graph
::DepNode
<DepKind
>;
196 // We keep a lot of `DepNode`s in memory during compilation. It's not
197 // required that their size stay the same, but we don't want to change
198 // it inadvertently. This assert just ensures we're aware of any change.
199 #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
200 static_assert_size
!(DepNode
, 17);
202 #[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))]
203 static_assert_size
!(DepNode
, 24);
205 pub trait DepNodeExt
: Sized
{
206 /// Construct a DepNode from the given DepKind and DefPathHash. This
207 /// method will assert that the given DepKind actually requires a
208 /// single DefId/DefPathHash parameter.
209 fn from_def_path_hash(def_path_hash
: DefPathHash
, kind
: DepKind
) -> Self;
211 /// Extracts the DefId corresponding to this DepNode. This will work
212 /// if two conditions are met:
214 /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and
215 /// 2. the item that the DefPath refers to exists in the current tcx.
217 /// Condition (1) is determined by the DepKind variant of the
218 /// DepNode. Condition (2) might not be fulfilled if a DepNode
219 /// refers to something from the previous compilation session that
220 /// has been removed.
221 fn extract_def_id(&self, tcx
: TyCtxt
<'_
>) -> Option
<DefId
>;
224 fn from_label_string(label
: &str, def_path_hash
: DefPathHash
)
228 fn has_label_string(label
: &str) -> bool
;
231 impl DepNodeExt
for DepNode
{
232 /// Construct a DepNode from the given DepKind and DefPathHash. This
233 /// method will assert that the given DepKind actually requires a
234 /// single DefId/DefPathHash parameter.
235 fn from_def_path_hash(def_path_hash
: DefPathHash
, kind
: DepKind
) -> DepNode
{
236 debug_assert
!(kind
.can_reconstruct_query_key() && kind
.has_params());
239 hash
: def_path_hash
.0.into
(),
243 /// Extracts the DefId corresponding to this DepNode. This will work
244 /// if two conditions are met:
246 /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and
247 /// 2. the item that the DefPath refers to exists in the current tcx.
249 /// Condition (1) is determined by the DepKind variant of the
250 /// DepNode. Condition (2) might not be fulfilled if a DepNode
251 /// refers to something from the previous compilation session that
252 /// has been removed.
253 fn extract_def_id(&self, tcx
: TyCtxt
<'tcx
>) -> Option
<DefId
> {
254 if self.kind
.can_reconstruct_query_key() {
255 tcx
.queries
.on_disk_cache
.as_ref()?
.def_path_hash_to_def_id(tcx
, DefPathHash(self.hash
.into()))
262 fn from_label_string(label
: &str, def_path_hash
: DefPathHash
) -> Result
<DepNode
, ()> {
263 let kind
= match label
{
265 stringify
!($variant
) => DepKind
::$variant
,
270 if !kind
.can_reconstruct_query_key() {
274 if kind
.has_params() {
275 Ok(DepNode
::from_def_path_hash(def_path_hash
, kind
))
277 Ok(DepNode
::new_no_params(kind
))
282 fn has_label_string(label
: &str) -> bool
{
285 stringify
!($variant
) => true,
292 /// Contains variant => str representations for constructing
293 /// DepNode groups for tests.
294 #[allow(dead_code, non_upper_case_globals)]
297 pub const $variant
: &str = stringify
!($variant
);
303 rustc_dep_node_append
!([define_dep_nodes
!][ <'tcx
>
304 // We use this for most things when incr. comp. is turned off.
307 // Represents metadata from an extern crate.
308 [eval_always
] CrateMetadata(CrateNum
),
312 [] CompileCodegenUnit(Symbol
),
315 impl<'tcx
> DepNodeParams
<TyCtxt
<'tcx
>> for DefId
{
317 fn can_reconstruct_query_key() -> bool
{
321 fn to_fingerprint(&self, tcx
: TyCtxt
<'tcx
>) -> Fingerprint
{
322 let hash
= tcx
.def_path_hash(*self);
323 // If this is a foreign `DefId`, store its current value
324 // in the incremental cache. When we decode the cache,
325 // we will use the old DefIndex as an initial guess for
326 // a lookup into the crate metadata.
327 if !self.is_local() {
328 if let Some(cache
) = &tcx
.queries
.on_disk_cache
{
329 cache
.store_foreign_def_id_hash(*self, hash
);
335 fn to_debug_str(&self, tcx
: TyCtxt
<'tcx
>) -> String
{
336 tcx
.def_path_str(*self)
339 fn recover(tcx
: TyCtxt
<'tcx
>, dep_node
: &DepNode
) -> Option
<Self> {
340 dep_node
.extract_def_id(tcx
)
344 impl<'tcx
> DepNodeParams
<TyCtxt
<'tcx
>> for LocalDefId
{
346 fn can_reconstruct_query_key() -> bool
{
350 fn to_fingerprint(&self, tcx
: TyCtxt
<'tcx
>) -> Fingerprint
{
351 self.to_def_id().to_fingerprint(tcx
)
354 fn to_debug_str(&self, tcx
: TyCtxt
<'tcx
>) -> String
{
355 self.to_def_id().to_debug_str(tcx
)
358 fn recover(tcx
: TyCtxt
<'tcx
>, dep_node
: &DepNode
) -> Option
<Self> {
359 dep_node
.extract_def_id(tcx
).map(|id
| id
.expect_local())
363 impl<'tcx
> DepNodeParams
<TyCtxt
<'tcx
>> for CrateNum
{
365 fn can_reconstruct_query_key() -> bool
{
369 fn to_fingerprint(&self, tcx
: TyCtxt
<'tcx
>) -> Fingerprint
{
370 let def_id
= DefId { krate: *self, index: CRATE_DEF_INDEX }
;
371 def_id
.to_fingerprint(tcx
)
374 fn to_debug_str(&self, tcx
: TyCtxt
<'tcx
>) -> String
{
375 tcx
.crate_name(*self).to_string()
378 fn recover(tcx
: TyCtxt
<'tcx
>, dep_node
: &DepNode
) -> Option
<Self> {
379 dep_node
.extract_def_id(tcx
).map(|id
| id
.krate
)
383 impl<'tcx
> DepNodeParams
<TyCtxt
<'tcx
>> for (DefId
, DefId
) {
385 fn can_reconstruct_query_key() -> bool
{
389 // We actually would not need to specialize the implementation of this
390 // method but it's faster to combine the hashes than to instantiate a full
391 // hashing context and stable-hashing state.
392 fn to_fingerprint(&self, tcx
: TyCtxt
<'tcx
>) -> Fingerprint
{
393 let (def_id_0
, def_id_1
) = *self;
395 let def_path_hash_0
= tcx
.def_path_hash(def_id_0
);
396 let def_path_hash_1
= tcx
.def_path_hash(def_id_1
);
398 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 can_reconstruct_query_key() -> bool
{
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.
417 fn to_fingerprint(&self, tcx
: TyCtxt
<'tcx
>) -> Fingerprint
{
418 let HirId { owner, local_id }
= *self;
420 let def_path_hash
= tcx
.def_path_hash(owner
.to_def_id());
421 let local_id
= Fingerprint
::from_smaller_hash(local_id
.as_u32().into());
423 def_path_hash
.0.combine(local_id
)