]>
Commit | Line | Data |
---|---|---|
041b39d2 XL |
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 | |
0731742a | 9 | //! interning key (e.g., NodeId, DefId, Symbol) or the numeric value of a |
041b39d2 XL |
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: | |
12 | //! | |
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 | |
0731742a | 20 | //! memory without any post-processing (e.g., "abomination-style" pointer |
041b39d2 XL |
21 | //! reconstruction). |
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. | |
28 | //! | |
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. | |
33 | //! | |
34 | //! Because the macro sees what parameters a given `DepKind` requires, it can | |
35 | //! "infer" some properties for each kind of `DepNode`: | |
36 | //! | |
37 | //! * Whether a `DepNode` of a given kind has any parameters at all. Some | |
ba9703b0 | 38 | //! `DepNode`s could represent global concepts with only one value. |
041b39d2 XL |
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. | |
44 | //! | |
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. | |
51 | ||
dfeec247 | 52 | use crate::mir::interpret::{GlobalId, LitToConstInput}; |
9fa01778 XL |
53 | use crate::traits; |
54 | use crate::traits::query::{ | |
dfeec247 XL |
55 | CanonicalPredicateGoal, CanonicalProjectionGoal, CanonicalTyGoal, |
56 | CanonicalTypeOpAscribeUserTypeGoal, CanonicalTypeOpEqGoal, CanonicalTypeOpNormalizeGoal, | |
57 | CanonicalTypeOpProvePredicateGoal, CanonicalTypeOpSubtypeGoal, | |
8faf50e0 | 58 | }; |
ba9703b0 | 59 | use crate::ty::subst::{GenericArg, SubstsRef}; |
dfeec247 XL |
60 | use crate::ty::{self, ParamEnvAnd, Ty, TyCtxt}; |
61 | ||
ba9703b0 XL |
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; | |
dfeec247 XL |
65 | use rustc_hir::HirId; |
66 | use rustc_span::symbol::Symbol; | |
dfeec247 | 67 | use std::hash::Hash; |
041b39d2 | 68 | |
ba9703b0 XL |
69 | pub use rustc_query_system::dep_graph::{DepContext, DepNodeParams}; |
70 | ||
041b39d2 | 71 | // erase!() just makes tokens go away. It's used to specify which macro argument |
0731742a | 72 | // is repeated (i.e., which sub-expression of the macro we are in) but don't need |
041b39d2 XL |
73 | // to actually use any of the arguments. |
74 | macro_rules! erase { | |
dfeec247 | 75 | ($x:tt) => {{}}; |
041b39d2 XL |
76 | } |
77 | ||
ea8adc8c | 78 | macro_rules! is_anon_attr { |
dfeec247 XL |
79 | (anon) => { |
80 | true | |
81 | }; | |
82 | ($attr:ident) => { | |
83 | false | |
84 | }; | |
ea8adc8c XL |
85 | } |
86 | ||
abe05a73 | 87 | macro_rules! is_eval_always_attr { |
dfeec247 XL |
88 | (eval_always) => { |
89 | true | |
90 | }; | |
91 | ($attr:ident) => { | |
92 | false | |
93 | }; | |
abe05a73 XL |
94 | } |
95 | ||
ea8adc8c | 96 | macro_rules! contains_anon_attr { |
74b04a01 | 97 | ($($attr:ident $(($($attr_args:tt)*))* ),*) => ({$(is_anon_attr!($attr) | )* false}); |
ea8adc8c XL |
98 | } |
99 | ||
abe05a73 | 100 | macro_rules! contains_eval_always_attr { |
74b04a01 | 101 | ($($attr:ident $(($($attr_args:tt)*))* ),*) => ({$(is_eval_always_attr!($attr) | )* false}); |
abe05a73 XL |
102 | } |
103 | ||
041b39d2 XL |
104 | macro_rules! define_dep_nodes { |
105 | (<$tcx:tt> | |
106 | $( | |
74b04a01 | 107 | [$($attrs:tt)*] |
9fa01778 | 108 | $variant:ident $(( $tuple_arg_ty:ty $(,)? ))* |
041b39d2 XL |
109 | ,)* |
110 | ) => ( | |
111 | #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, | |
112 | RustcEncodable, RustcDecodable)] | |
ba9703b0 | 113 | #[allow(non_camel_case_types)] |
041b39d2 XL |
114 | pub enum DepKind { |
115 | $($variant),* | |
116 | } | |
117 | ||
118 | impl DepKind { | |
119 | #[allow(unreachable_code)] | |
041b39d2 XL |
120 | pub fn can_reconstruct_query_key<$tcx>(&self) -> bool { |
121 | match *self { | |
122 | $( | |
123 | DepKind :: $variant => { | |
74b04a01 | 124 | if contains_anon_attr!($($attrs)*) { |
ea8adc8c XL |
125 | return false; |
126 | } | |
3b2f2976 | 127 | |
041b39d2 XL |
128 | // tuple args |
129 | $({ | |
ba9703b0 | 130 | return <$tuple_arg_ty as DepNodeParams<TyCtxt<'_>>> |
f035d41b | 131 | ::can_reconstruct_query_key(); |
041b39d2 XL |
132 | })* |
133 | ||
041b39d2 XL |
134 | true |
135 | } | |
136 | )* | |
137 | } | |
138 | } | |
139 | ||
ea8adc8c | 140 | pub fn is_anon(&self) -> bool { |
041b39d2 XL |
141 | match *self { |
142 | $( | |
74b04a01 | 143 | DepKind :: $variant => { contains_anon_attr!($($attrs)*) } |
ea8adc8c XL |
144 | )* |
145 | } | |
146 | } | |
147 | ||
abe05a73 XL |
148 | pub fn is_eval_always(&self) -> bool { |
149 | match *self { | |
150 | $( | |
74b04a01 | 151 | DepKind :: $variant => { contains_eval_always_attr!($($attrs)*) } |
abe05a73 XL |
152 | )* |
153 | } | |
154 | } | |
155 | ||
041b39d2 | 156 | #[allow(unreachable_code)] |
041b39d2 XL |
157 | pub fn has_params(&self) -> bool { |
158 | match *self { | |
159 | $( | |
160 | DepKind :: $variant => { | |
161 | // tuple args | |
162 | $({ | |
0531ce1d | 163 | erase!($tuple_arg_ty); |
041b39d2 XL |
164 | return true; |
165 | })* | |
166 | ||
041b39d2 XL |
167 | false |
168 | } | |
169 | )* | |
170 | } | |
171 | } | |
172 | } | |
173 | ||
74b04a01 XL |
174 | pub struct DepConstructor; |
175 | ||
ba9703b0 | 176 | #[allow(non_camel_case_types)] |
74b04a01 | 177 | impl DepConstructor { |
041b39d2 | 178 | $( |
74b04a01 XL |
179 | #[inline(always)] |
180 | #[allow(unreachable_code, non_snake_case)] | |
ba9703b0 | 181 | pub fn $variant(_tcx: TyCtxt<'_>, $(arg: $tuple_arg_ty)*) -> DepNode { |
74b04a01 XL |
182 | // tuple args |
183 | $({ | |
184 | erase!($tuple_arg_ty); | |
f9f354fc | 185 | return DepNode::construct(_tcx, DepKind::$variant, &arg) |
74b04a01 XL |
186 | })* |
187 | ||
f9f354fc | 188 | return DepNode::construct(_tcx, DepKind::$variant, &()) |
74b04a01 XL |
189 | } |
190 | )* | |
041b39d2 XL |
191 | } |
192 | ||
ba9703b0 XL |
193 | pub type DepNode = rustc_query_system::dep_graph::DepNode<DepKind>; |
194 | ||
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; | |
200 | ||
201 | /// Extracts the DefId corresponding to this DepNode. This will work | |
202 | /// if two conditions are met: | |
203 | /// | |
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. | |
206 | /// | |
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>; | |
212 | ||
213 | /// Used in testing | |
214 | fn from_label_string(label: &str, def_path_hash: DefPathHash) | |
215 | -> Result<Self, ()>; | |
216 | ||
217 | /// Used in testing | |
218 | fn has_label_string(label: &str) -> bool; | |
3157f602 | 219 | } |
041b39d2 | 220 | |
ba9703b0 | 221 | impl DepNodeExt for DepNode { |
041b39d2 XL |
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. | |
ba9703b0 | 225 | fn from_def_path_hash(def_path_hash: DefPathHash, kind: DepKind) -> DepNode { |
0731742a | 226 | debug_assert!(kind.can_reconstruct_query_key() && kind.has_params()); |
041b39d2 XL |
227 | DepNode { |
228 | kind, | |
229 | hash: def_path_hash.0, | |
230 | } | |
231 | } | |
232 | ||
9fa01778 | 233 | /// Extracts the DefId corresponding to this DepNode. This will work |
041b39d2 XL |
234 | /// if two conditions are met: |
235 | /// | |
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. | |
238 | /// | |
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. | |
ba9703b0 | 243 | fn extract_def_id(&self, tcx: TyCtxt<'tcx>) -> Option<DefId> { |
041b39d2 XL |
244 | if self.kind.can_reconstruct_query_key() { |
245 | let def_path_hash = DefPathHash(self.hash); | |
ba9703b0 | 246 | tcx.def_path_hash_to_def_id.as_ref()?.get(&def_path_hash).cloned() |
041b39d2 XL |
247 | } else { |
248 | None | |
249 | } | |
250 | } | |
251 | ||
252 | /// Used in testing | |
ba9703b0 | 253 | fn from_label_string(label: &str, def_path_hash: DefPathHash) -> Result<DepNode, ()> { |
041b39d2 XL |
254 | let kind = match label { |
255 | $( | |
256 | stringify!($variant) => DepKind::$variant, | |
257 | )* | |
258 | _ => return Err(()), | |
259 | }; | |
260 | ||
261 | if !kind.can_reconstruct_query_key() { | |
262 | return Err(()); | |
263 | } | |
264 | ||
265 | if kind.has_params() { | |
ba9703b0 | 266 | Ok(DepNode::from_def_path_hash(def_path_hash, kind)) |
041b39d2 XL |
267 | } else { |
268 | Ok(DepNode::new_no_params(kind)) | |
269 | } | |
270 | } | |
ea8adc8c XL |
271 | |
272 | /// Used in testing | |
ba9703b0 | 273 | fn has_label_string(label: &str) -> bool { |
ea8adc8c XL |
274 | match label { |
275 | $( | |
276 | stringify!($variant) => true, | |
277 | )* | |
278 | _ => false, | |
279 | } | |
280 | } | |
281 | } | |
282 | ||
283 | /// Contains variant => str representations for constructing | |
284 | /// DepNode groups for tests. | |
285 | #[allow(dead_code, non_upper_case_globals)] | |
286 | pub mod label_strs { | |
287 | $( | |
0731742a | 288 | pub const $variant: &str = stringify!($variant); |
ea8adc8c | 289 | )* |
041b39d2 XL |
290 | } |
291 | ); | |
292 | } | |
293 | ||
532ac7d7 | 294 | rustc_dep_node_append!([define_dep_nodes!][ <'tcx> |
0531ce1d XL |
295 | // We use this for most things when incr. comp. is turned off. |
296 | [] Null, | |
297 | ||
ea8adc8c | 298 | // Represents metadata from an extern crate. |
532ac7d7 XL |
299 | [eval_always] CrateMetadata(CrateNum), |
300 | ||
3b2f2976 | 301 | [anon] TraitSelect, |
041b39d2 | 302 | |
e74abb32 | 303 | [] CompileCodegenUnit(Symbol), |
532ac7d7 XL |
304 | ]); |
305 | ||
ba9703b0 | 306 | impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for DefId { |
f035d41b XL |
307 | #[inline] |
308 | fn can_reconstruct_query_key() -> bool { | |
309 | true | |
310 | } | |
041b39d2 | 311 | |
ba9703b0 | 312 | fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { |
0531ce1d | 313 | tcx.def_path_hash(*self).0 |
041b39d2 XL |
314 | } |
315 | ||
dc9dc135 | 316 | fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String { |
532ac7d7 | 317 | tcx.def_path_str(*self) |
041b39d2 | 318 | } |
74b04a01 XL |
319 | |
320 | fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> { | |
321 | dep_node.extract_def_id(tcx) | |
322 | } | |
041b39d2 | 323 | } |
9e0c209e | 324 | |
ba9703b0 | 325 | impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for LocalDefId { |
f035d41b XL |
326 | #[inline] |
327 | fn can_reconstruct_query_key() -> bool { | |
328 | true | |
329 | } | |
ea8adc8c | 330 | |
ba9703b0 XL |
331 | fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { |
332 | self.to_def_id().to_fingerprint(tcx) | |
ea8adc8c XL |
333 | } |
334 | ||
dc9dc135 | 335 | fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String { |
ba9703b0 | 336 | self.to_def_id().to_debug_str(tcx) |
ea8adc8c | 337 | } |
74b04a01 XL |
338 | |
339 | fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> { | |
ba9703b0 | 340 | dep_node.extract_def_id(tcx).map(|id| id.expect_local()) |
74b04a01 | 341 | } |
ea8adc8c XL |
342 | } |
343 | ||
ba9703b0 | 344 | impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for CrateNum { |
f035d41b XL |
345 | #[inline] |
346 | fn can_reconstruct_query_key() -> bool { | |
347 | true | |
348 | } | |
ea8adc8c | 349 | |
ba9703b0 | 350 | fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { |
dfeec247 | 351 | let def_id = DefId { krate: *self, index: CRATE_DEF_INDEX }; |
ea8adc8c XL |
352 | tcx.def_path_hash(def_id).0 |
353 | } | |
354 | ||
dc9dc135 | 355 | fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String { |
60c5eb7d | 356 | tcx.crate_name(*self).to_string() |
ea8adc8c | 357 | } |
74b04a01 XL |
358 | |
359 | fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> { | |
360 | dep_node.extract_def_id(tcx).map(|id| id.krate) | |
361 | } | |
ea8adc8c XL |
362 | } |
363 | ||
ba9703b0 | 364 | impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for (DefId, DefId) { |
f035d41b XL |
365 | #[inline] |
366 | fn can_reconstruct_query_key() -> bool { | |
367 | false | |
368 | } | |
041b39d2 XL |
369 | |
370 | // We actually would not need to specialize the implementation of this | |
371 | // method but it's faster to combine the hashes than to instantiate a full | |
372 | // hashing context and stable-hashing state. | |
ba9703b0 | 373 | fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { |
041b39d2 XL |
374 | let (def_id_0, def_id_1) = *self; |
375 | ||
376 | let def_path_hash_0 = tcx.def_path_hash(def_id_0); | |
377 | let def_path_hash_1 = tcx.def_path_hash(def_id_1); | |
378 | ||
379 | def_path_hash_0.0.combine(def_path_hash_1.0) | |
380 | } | |
381 | ||
dc9dc135 | 382 | fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String { |
041b39d2 XL |
383 | let (def_id_0, def_id_1) = *self; |
384 | ||
dfeec247 | 385 | format!("({}, {})", tcx.def_path_debug_str(def_id_0), tcx.def_path_debug_str(def_id_1)) |
041b39d2 XL |
386 | } |
387 | } | |
388 | ||
ba9703b0 | 389 | impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for HirId { |
f035d41b XL |
390 | #[inline] |
391 | fn can_reconstruct_query_key() -> bool { | |
392 | false | |
393 | } | |
041b39d2 XL |
394 | |
395 | // We actually would not need to specialize the implementation of this | |
396 | // method but it's faster to combine the hashes than to instantiate a full | |
397 | // hashing context and stable-hashing state. | |
ba9703b0 | 398 | fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { |
dfeec247 | 399 | let HirId { owner, local_id } = *self; |
041b39d2 | 400 | |
ba9703b0 | 401 | let def_path_hash = tcx.def_path_hash(owner.to_def_id()); |
a1dfa0c6 | 402 | let local_id = Fingerprint::from_smaller_hash(local_id.as_u32().into()); |
041b39d2 | 403 | |
ea8adc8c | 404 | def_path_hash.0.combine(local_id) |
54a0048b SL |
405 | } |
406 | } |