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 the `define_dep_nodes!()` macro. This macro
30 //! defines the `DepKind` enum and a corresponding `DepConstructor` enum. The
31 //! `DepConstructor` enum links a `DepKind` to the parameters that are needed at
32 //! runtime in order 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 //! The `DepConstructor` enum, together with `DepNode::new()` ensures that only
46 //! valid `DepNode` instances can be constructed. For example, the API does not
47 //! allow for constructing parameterless `DepNode`s with anything other
48 //! than a zeroed out fingerprint. More generally speaking, it relieves the
49 //! user of the `DepNode` API of having to know how to compute the expected
50 //! fingerprint for a given set of node parameters.
52 use crate::mir
::interpret
::{GlobalId, LitToConstInput}
;
54 use crate::traits
::query
::{
55 CanonicalPredicateGoal
, CanonicalProjectionGoal
, CanonicalTyGoal
,
56 CanonicalTypeOpAscribeUserTypeGoal
, CanonicalTypeOpEqGoal
, CanonicalTypeOpNormalizeGoal
,
57 CanonicalTypeOpProvePredicateGoal
, CanonicalTypeOpSubtypeGoal
,
59 use crate::ty
::subst
::{GenericArg, SubstsRef}
;
60 use crate::ty
::{self, ParamEnvAnd, 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 // erase!() just makes tokens go away. It's used to specify which macro argument
72 // is repeated (i.e., which sub-expression of the macro we are in) but don't need
73 // to actually use any of the arguments.
78 macro_rules
! is_anon_attr
{
87 macro_rules
! is_eval_always_attr
{
96 macro_rules
! contains_anon_attr
{
97 ($
($attr
:ident $
(($
($attr_args
:tt
)*))* ),*) => ({$(is_anon_attr!($attr) | )* false}
);
100 macro_rules
! contains_eval_always_attr
{
101 ($
($attr
:ident $
(($
($attr_args
:tt
)*))* ),*) => ({$(is_eval_always_attr!($attr) | )* false}
);
104 macro_rules
! define_dep_nodes
{
108 $variant
:ident $
(( $tuple_arg_ty
:ty $
(,)?
))*
111 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash,
112 RustcEncodable
, RustcDecodable
)]
113 #[allow(non_camel_case_types)]
119 #[allow(unreachable_code)]
120 pub fn can_reconstruct_query_key
<$tcx
>(&self) -> bool
{
123 DepKind
:: $variant
=> {
124 if contains_anon_attr
!($
($attrs
)*) {
130 return <$tuple_arg_ty
as DepNodeParams
<TyCtxt
<'_
>>>
131 ::CAN_RECONSTRUCT_QUERY_KEY
;
140 pub fn is_anon(&self) -> bool
{
143 DepKind
:: $variant
=> { contains_anon_attr!($($attrs)*) }
148 pub fn is_eval_always(&self) -> bool
{
151 DepKind
:: $variant
=> { contains_eval_always_attr!($($attrs)*) }
156 #[allow(unreachable_code)]
157 pub fn has_params(&self) -> bool
{
160 DepKind
:: $variant
=> {
163 erase
!($tuple_arg_ty
);
174 pub struct DepConstructor
;
176 #[allow(non_camel_case_types)]
177 impl DepConstructor
{
180 #[allow(unreachable_code, non_snake_case)]
181 pub fn $
variant(_tcx
: TyCtxt
<'_
>, $
(arg
: $tuple_arg_ty
)*) -> DepNode
{
184 erase
!($tuple_arg_ty
);
185 return DepNode
::construct(_tcx
, DepKind
::$variant
, &arg
)
188 return DepNode
::construct(_tcx
, DepKind
::$variant
, &())
193 pub type DepNode
= rustc_query_system
::dep_graph
::DepNode
<DepKind
>;
195 pub trait DepNodeExt
: Sized
{
196 /// Construct a DepNode from the given DepKind and DefPathHash. This
197 /// method will assert that the given DepKind actually requires a
198 /// single DefId/DefPathHash parameter.
199 fn from_def_path_hash(def_path_hash
: DefPathHash
, kind
: DepKind
) -> Self;
201 /// Extracts the DefId corresponding to this DepNode. This will work
202 /// if two conditions are met:
204 /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and
205 /// 2. the item that the DefPath refers to exists in the current tcx.
207 /// Condition (1) is determined by the DepKind variant of the
208 /// DepNode. Condition (2) might not be fulfilled if a DepNode
209 /// refers to something from the previous compilation session that
210 /// has been removed.
211 fn extract_def_id(&self, tcx
: TyCtxt
<'_
>) -> Option
<DefId
>;
214 fn from_label_string(label
: &str, def_path_hash
: DefPathHash
)
218 fn has_label_string(label
: &str) -> bool
;
221 impl DepNodeExt
for DepNode
{
222 /// Construct a DepNode from the given DepKind and DefPathHash. This
223 /// method will assert that the given DepKind actually requires a
224 /// single DefId/DefPathHash parameter.
225 fn from_def_path_hash(def_path_hash
: DefPathHash
, kind
: DepKind
) -> DepNode
{
226 debug_assert
!(kind
.can_reconstruct_query_key() && kind
.has_params());
229 hash
: def_path_hash
.0,
233 /// Extracts the DefId corresponding to this DepNode. This will work
234 /// if two conditions are met:
236 /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and
237 /// 2. the item that the DefPath refers to exists in the current tcx.
239 /// Condition (1) is determined by the DepKind variant of the
240 /// DepNode. Condition (2) might not be fulfilled if a DepNode
241 /// refers to something from the previous compilation session that
242 /// has been removed.
243 fn extract_def_id(&self, tcx
: TyCtxt
<'tcx
>) -> Option
<DefId
> {
244 if self.kind
.can_reconstruct_query_key() {
245 let def_path_hash
= DefPathHash(self.hash
);
246 tcx
.def_path_hash_to_def_id
.as_ref()?
.get(&def_path_hash
).cloned()
253 fn from_label_string(label
: &str, def_path_hash
: DefPathHash
) -> Result
<DepNode
, ()> {
254 let kind
= match label
{
256 stringify
!($variant
) => DepKind
::$variant
,
261 if !kind
.can_reconstruct_query_key() {
265 if kind
.has_params() {
266 Ok(DepNode
::from_def_path_hash(def_path_hash
, kind
))
268 Ok(DepNode
::new_no_params(kind
))
273 fn has_label_string(label
: &str) -> bool
{
276 stringify
!($variant
) => true,
283 /// Contains variant => str representations for constructing
284 /// DepNode groups for tests.
285 #[allow(dead_code, non_upper_case_globals)]
288 pub const $variant
: &str = stringify
!($variant
);
294 rustc_dep_node_append
!([define_dep_nodes
!][ <'tcx
>
295 // We use this for most things when incr. comp. is turned off.
298 // Represents metadata from an extern crate.
299 [eval_always
] CrateMetadata(CrateNum
),
303 [] CompileCodegenUnit(Symbol
),
306 impl<'tcx
> DepNodeParams
<TyCtxt
<'tcx
>> for DefId
{
307 const CAN_RECONSTRUCT_QUERY_KEY
: bool
= true;
309 fn to_fingerprint(&self, tcx
: TyCtxt
<'tcx
>) -> Fingerprint
{
310 tcx
.def_path_hash(*self).0
313 fn to_debug_str(&self, tcx
: TyCtxt
<'tcx
>) -> String
{
314 tcx
.def_path_str(*self)
317 fn recover(tcx
: TyCtxt
<'tcx
>, dep_node
: &DepNode
) -> Option
<Self> {
318 dep_node
.extract_def_id(tcx
)
322 impl<'tcx
> DepNodeParams
<TyCtxt
<'tcx
>> for LocalDefId
{
323 const CAN_RECONSTRUCT_QUERY_KEY
: bool
= true;
325 fn to_fingerprint(&self, tcx
: TyCtxt
<'tcx
>) -> Fingerprint
{
326 self.to_def_id().to_fingerprint(tcx
)
329 fn to_debug_str(&self, tcx
: TyCtxt
<'tcx
>) -> String
{
330 self.to_def_id().to_debug_str(tcx
)
333 fn recover(tcx
: TyCtxt
<'tcx
>, dep_node
: &DepNode
) -> Option
<Self> {
334 dep_node
.extract_def_id(tcx
).map(|id
| id
.expect_local())
338 impl<'tcx
> DepNodeParams
<TyCtxt
<'tcx
>> for CrateNum
{
339 const CAN_RECONSTRUCT_QUERY_KEY
: bool
= true;
341 fn to_fingerprint(&self, tcx
: TyCtxt
<'tcx
>) -> Fingerprint
{
342 let def_id
= DefId { krate: *self, index: CRATE_DEF_INDEX }
;
343 tcx
.def_path_hash(def_id
).0
346 fn to_debug_str(&self, tcx
: TyCtxt
<'tcx
>) -> String
{
347 tcx
.crate_name(*self).to_string()
350 fn recover(tcx
: TyCtxt
<'tcx
>, dep_node
: &DepNode
) -> Option
<Self> {
351 dep_node
.extract_def_id(tcx
).map(|id
| id
.krate
)
355 impl<'tcx
> DepNodeParams
<TyCtxt
<'tcx
>> for (DefId
, DefId
) {
356 const CAN_RECONSTRUCT_QUERY_KEY
: bool
= false;
358 // We actually would not need to specialize the implementation of this
359 // method but it's faster to combine the hashes than to instantiate a full
360 // hashing context and stable-hashing state.
361 fn to_fingerprint(&self, tcx
: TyCtxt
<'tcx
>) -> Fingerprint
{
362 let (def_id_0
, def_id_1
) = *self;
364 let def_path_hash_0
= tcx
.def_path_hash(def_id_0
);
365 let def_path_hash_1
= tcx
.def_path_hash(def_id_1
);
367 def_path_hash_0
.0
.combine(def_path_hash_1
.0
)
370 fn to_debug_str(&self, tcx
: TyCtxt
<'tcx
>) -> String
{
371 let (def_id_0
, def_id_1
) = *self;
373 format
!("({}, {})", tcx
.def_path_debug_str(def_id_0
), tcx
.def_path_debug_str(def_id_1
))
377 impl<'tcx
> DepNodeParams
<TyCtxt
<'tcx
>> for HirId
{
378 const CAN_RECONSTRUCT_QUERY_KEY
: bool
= false;
380 // We actually would not need to specialize the implementation of this
381 // method but it's faster to combine the hashes than to instantiate a full
382 // hashing context and stable-hashing state.
383 fn to_fingerprint(&self, tcx
: TyCtxt
<'tcx
>) -> Fingerprint
{
384 let HirId { owner, local_id }
= *self;
386 let def_path_hash
= tcx
.def_path_hash(owner
.to_def_id());
387 let local_id
= Fingerprint
::from_smaller_hash(local_id
.as_u32().into());
389 def_path_hash
.0.combine(local_id
)