]>
Commit | Line | Data |
---|---|---|
5869c6ff | 1 | //! Nodes in the dependency graph. |
3dfed10e | 2 | //! |
5869c6ff XL |
3 | //! A node in the [dependency graph] is represented by a [`DepNode`]. |
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 | |
041b39d2 XL |
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 | |
5869c6ff | 11 | //! interning key (e.g., `NodeId`, `DefId`, `Symbol`) or the numeric value of a |
041b39d2 | 12 | //! pointer. The concept behind this could be compared to how git commit hashes |
5869c6ff XL |
13 | //! uniquely identify a given commit. The fingerprinting approach has |
14 | //! a few advantages: | |
041b39d2 XL |
15 | //! |
16 | //! * A `DepNode` can simply be serialized to disk and loaded in another session | |
3dfed10e XL |
17 | //! without the need to do any "rebasing" (like we have to do for Spans and |
18 | //! NodeIds) or "retracing" (like we had to do for `DefId` in earlier | |
19 | //! implementations of the dependency graph). | |
041b39d2 XL |
20 | //! * A `Fingerprint` is just a bunch of bits, which allows `DepNode` to |
21 | //! implement `Copy`, `Sync`, `Send`, `Freeze`, etc. | |
22 | //! * Since we just have a bit pattern, `DepNode` can be mapped from disk into | |
0731742a | 23 | //! memory without any post-processing (e.g., "abomination-style" pointer |
041b39d2 XL |
24 | //! reconstruction). |
25 | //! * Because a `DepNode` is self-contained, we can instantiate `DepNodes` that | |
26 | //! refer to things that do not exist anymore. In previous implementations | |
27 | //! `DepNode` contained a `DefId`. A `DepNode` referring to something that | |
28 | //! had been removed between the previous and the current compilation session | |
29 | //! could not be instantiated because the current compilation session | |
30 | //! contained no `DefId` for thing that had been removed. | |
31 | //! | |
32 | //! `DepNode` definition happens in the `define_dep_nodes!()` macro. This macro | |
5869c6ff XL |
33 | //! defines the `DepKind` enum. Each `DepKind` has its own parameters that are |
34 | //! needed at runtime in order to construct a valid `DepNode` fingerprint. | |
cdc7bbd5 XL |
35 | //! However, only `CompileCodegenUnit` and `CompileMonoItem` are constructed |
36 | //! explicitly (with `make_compile_codegen_unit` cq `make_compile_mono_item`). | |
041b39d2 XL |
37 | //! |
38 | //! Because the macro sees what parameters a given `DepKind` requires, it can | |
39 | //! "infer" some properties for each kind of `DepNode`: | |
40 | //! | |
41 | //! * Whether a `DepNode` of a given kind has any parameters at all. Some | |
ba9703b0 | 42 | //! `DepNode`s could represent global concepts with only one value. |
041b39d2 XL |
43 | //! * Whether it is possible, in principle, to reconstruct a query key from a |
44 | //! given `DepNode`. Many `DepKind`s only require a single `DefId` parameter, | |
45 | //! in which case it is possible to map the node's fingerprint back to the | |
46 | //! `DefId` it was computed from. In other cases, too much information gets | |
47 | //! lost during fingerprint computation. | |
48 | //! | |
cdc7bbd5 XL |
49 | //! `make_compile_codegen_unit` and `make_compile_mono_items`, together with |
50 | //! `DepNode::new()`, ensures that only valid `DepNode` instances can be | |
51 | //! constructed. For example, the API does not allow for constructing | |
52 | //! parameterless `DepNode`s with anything other than a zeroed out fingerprint. | |
53 | //! More generally speaking, it relieves the user of the `DepNode` API of | |
54 | //! having to know how to compute the expected fingerprint for a given set of | |
55 | //! node parameters. | |
5869c6ff XL |
56 | //! |
57 | //! [dependency graph]: https://rustc-dev-guide.rust-lang.org/query.html | |
041b39d2 | 58 | |
cdc7bbd5 | 59 | use crate::mir::mono::MonoItem; |
5869c6ff | 60 | use crate::ty::TyCtxt; |
dfeec247 | 61 | |
ba9703b0 | 62 | use rustc_data_structures::fingerprint::Fingerprint; |
04454e1e | 63 | use rustc_hir::def_id::{CrateNum, DefId, LocalDefId}; |
ba9703b0 | 64 | use rustc_hir::definitions::DefPathHash; |
2b03887a | 65 | use rustc_hir::{HirId, ItemLocalId, OwnerId}; |
c295e0f8 | 66 | use rustc_query_system::dep_graph::FingerprintStyle; |
dfeec247 | 67 | use rustc_span::symbol::Symbol; |
dfeec247 | 68 | use std::hash::Hash; |
041b39d2 | 69 | |
ba9703b0 XL |
70 | pub use rustc_query_system::dep_graph::{DepContext, DepNodeParams}; |
71 | ||
5869c6ff | 72 | macro_rules! define_dep_nodes { |
f2b60f7d FG |
73 | ( |
74 | $($(#[$attr:meta])* | |
75 | [$($modifiers:tt)*] fn $variant:ident($($K:tt)*) -> $V:ty,)*) => { | |
76 | ||
6a06907d XL |
77 | #[macro_export] |
78 | macro_rules! make_dep_kind_array { | |
3c0e092e | 79 | ($mod:ident) => {[ $($mod::$variant()),* ]}; |
6a06907d XL |
80 | } |
81 | ||
3c0e092e | 82 | /// This enum serves as an index into arrays built by `make_dep_kind_array`. |
5869c6ff XL |
83 | #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Encodable, Decodable)] |
84 | #[allow(non_camel_case_types)] | |
85 | pub enum DepKind { | |
f2b60f7d | 86 | $( $( #[$attr] )* $variant),* |
5869c6ff XL |
87 | } |
88 | ||
2b03887a | 89 | pub(super) fn dep_kind_from_label_string(label: &str) -> Result<DepKind, ()> { |
5869c6ff XL |
90 | match label { |
91 | $(stringify!($variant) => Ok(DepKind::$variant),)* | |
92 | _ => Err(()), | |
ea8adc8c XL |
93 | } |
94 | } | |
95 | ||
96 | /// Contains variant => str representations for constructing | |
97 | /// DepNode groups for tests. | |
98 | #[allow(dead_code, non_upper_case_globals)] | |
99 | pub mod label_strs { | |
100 | $( | |
0731742a | 101 | pub const $variant: &str = stringify!($variant); |
ea8adc8c | 102 | )* |
041b39d2 | 103 | } |
f2b60f7d | 104 | }; |
041b39d2 XL |
105 | } |
106 | ||
f2b60f7d FG |
107 | rustc_query_append!(define_dep_nodes![ |
108 | /// We use this for most things when incr. comp. is turned off. | |
109 | [] fn Null() -> (), | |
110 | /// We use this to create a forever-red node. | |
111 | [] fn Red() -> (), | |
112 | [] fn TraitSelect() -> (), | |
113 | [] fn CompileCodegenUnit() -> (), | |
114 | [] fn CompileMonoItem() -> (), | |
532ac7d7 XL |
115 | ]); |
116 | ||
5869c6ff XL |
117 | // WARNING: `construct` is generic and does not know that `CompileCodegenUnit` takes `Symbol`s as keys. |
118 | // Be very careful changing this type signature! | |
923072b8 | 119 | pub(crate) fn make_compile_codegen_unit(tcx: TyCtxt<'_>, name: Symbol) -> DepNode { |
5869c6ff XL |
120 | DepNode::construct(tcx, DepKind::CompileCodegenUnit, &name) |
121 | } | |
122 | ||
cdc7bbd5 XL |
123 | // WARNING: `construct` is generic and does not know that `CompileMonoItem` takes `MonoItem`s as keys. |
124 | // Be very careful changing this type signature! | |
923072b8 FG |
125 | pub(crate) fn make_compile_mono_item<'tcx>( |
126 | tcx: TyCtxt<'tcx>, | |
127 | mono_item: &MonoItem<'tcx>, | |
128 | ) -> DepNode { | |
cdc7bbd5 XL |
129 | DepNode::construct(tcx, DepKind::CompileMonoItem, mono_item) |
130 | } | |
131 | ||
5869c6ff XL |
132 | pub type DepNode = rustc_query_system::dep_graph::DepNode<DepKind>; |
133 | ||
134 | // We keep a lot of `DepNode`s in memory during compilation. It's not | |
135 | // required that their size stay the same, but we don't want to change | |
136 | // it inadvertently. This assert just ensures we're aware of any change. | |
137 | #[cfg(any(target_arch = "x86", target_arch = "x86_64"))] | |
17df50a5 | 138 | static_assert_size!(DepNode, 18); |
5869c6ff XL |
139 | |
140 | #[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))] | |
141 | static_assert_size!(DepNode, 24); | |
142 | ||
143 | pub trait DepNodeExt: Sized { | |
5869c6ff XL |
144 | /// Extracts the DefId corresponding to this DepNode. This will work |
145 | /// if two conditions are met: | |
146 | /// | |
147 | /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and | |
148 | /// 2. the item that the DefPath refers to exists in the current tcx. | |
149 | /// | |
150 | /// Condition (1) is determined by the DepKind variant of the | |
151 | /// DepNode. Condition (2) might not be fulfilled if a DepNode | |
152 | /// refers to something from the previous compilation session that | |
153 | /// has been removed. | |
154 | fn extract_def_id(&self, tcx: TyCtxt<'_>) -> Option<DefId>; | |
155 | ||
156 | /// Used in testing | |
3c0e092e XL |
157 | fn from_label_string( |
158 | tcx: TyCtxt<'_>, | |
159 | label: &str, | |
160 | def_path_hash: DefPathHash, | |
161 | ) -> Result<Self, ()>; | |
5869c6ff XL |
162 | |
163 | /// Used in testing | |
164 | fn has_label_string(label: &str) -> bool; | |
165 | } | |
166 | ||
167 | impl DepNodeExt for DepNode { | |
5869c6ff XL |
168 | /// Extracts the DefId corresponding to this DepNode. This will work |
169 | /// if two conditions are met: | |
170 | /// | |
171 | /// 1. The Fingerprint of the DepNode actually is a DefPathHash, and | |
172 | /// 2. the item that the DefPath refers to exists in the current tcx. | |
173 | /// | |
174 | /// Condition (1) is determined by the DepKind variant of the | |
175 | /// DepNode. Condition (2) might not be fulfilled if a DepNode | |
176 | /// refers to something from the previous compilation session that | |
177 | /// has been removed. | |
9c376795 | 178 | fn extract_def_id(&self, tcx: TyCtxt<'_>) -> Option<DefId> { |
2b03887a | 179 | if tcx.fingerprint_style(self.kind) == FingerprintStyle::DefPathHash { |
5099ac24 FG |
180 | Some(tcx.def_path_hash_to_def_id(DefPathHash(self.hash.into()), &mut || { |
181 | panic!("Failed to extract DefId: {:?} {}", self.kind, self.hash) | |
182 | })) | |
5869c6ff XL |
183 | } else { |
184 | None | |
185 | } | |
186 | } | |
187 | ||
188 | /// Used in testing | |
3c0e092e XL |
189 | fn from_label_string( |
190 | tcx: TyCtxt<'_>, | |
191 | label: &str, | |
192 | def_path_hash: DefPathHash, | |
193 | ) -> Result<DepNode, ()> { | |
5869c6ff XL |
194 | let kind = dep_kind_from_label_string(label)?; |
195 | ||
2b03887a FG |
196 | match tcx.fingerprint_style(kind) { |
197 | FingerprintStyle::Opaque | FingerprintStyle::HirId => Err(()), | |
3c0e092e XL |
198 | FingerprintStyle::Unit => Ok(DepNode::new_no_params(tcx, kind)), |
199 | FingerprintStyle::DefPathHash => { | |
200 | Ok(DepNode::from_def_path_hash(tcx, def_path_hash, kind)) | |
c295e0f8 | 201 | } |
5869c6ff XL |
202 | } |
203 | } | |
204 | ||
205 | /// Used in testing | |
206 | fn has_label_string(label: &str) -> bool { | |
207 | dep_kind_from_label_string(label).is_ok() | |
208 | } | |
209 | } | |
210 | ||
211 | impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for () { | |
212 | #[inline(always)] | |
c295e0f8 XL |
213 | fn fingerprint_style() -> FingerprintStyle { |
214 | FingerprintStyle::Unit | |
5869c6ff XL |
215 | } |
216 | ||
3c0e092e | 217 | #[inline(always)] |
5869c6ff XL |
218 | fn to_fingerprint(&self, _: TyCtxt<'tcx>) -> Fingerprint { |
219 | Fingerprint::ZERO | |
220 | } | |
221 | ||
3c0e092e | 222 | #[inline(always)] |
5869c6ff XL |
223 | fn recover(_: TyCtxt<'tcx>, _: &DepNode) -> Option<Self> { |
224 | Some(()) | |
225 | } | |
226 | } | |
227 | ||
ba9703b0 | 228 | impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for DefId { |
5869c6ff | 229 | #[inline(always)] |
c295e0f8 XL |
230 | fn fingerprint_style() -> FingerprintStyle { |
231 | FingerprintStyle::DefPathHash | |
f035d41b | 232 | } |
041b39d2 | 233 | |
3c0e092e | 234 | #[inline(always)] |
ba9703b0 | 235 | fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { |
c295e0f8 | 236 | tcx.def_path_hash(*self).0 |
041b39d2 XL |
237 | } |
238 | ||
3c0e092e | 239 | #[inline(always)] |
dc9dc135 | 240 | fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String { |
532ac7d7 | 241 | tcx.def_path_str(*self) |
041b39d2 | 242 | } |
74b04a01 | 243 | |
3c0e092e | 244 | #[inline(always)] |
74b04a01 XL |
245 | fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> { |
246 | dep_node.extract_def_id(tcx) | |
247 | } | |
041b39d2 | 248 | } |
9e0c209e | 249 | |
ba9703b0 | 250 | impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for LocalDefId { |
5869c6ff | 251 | #[inline(always)] |
c295e0f8 XL |
252 | fn fingerprint_style() -> FingerprintStyle { |
253 | FingerprintStyle::DefPathHash | |
f035d41b | 254 | } |
ea8adc8c | 255 | |
3c0e092e | 256 | #[inline(always)] |
ba9703b0 XL |
257 | fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { |
258 | self.to_def_id().to_fingerprint(tcx) | |
ea8adc8c XL |
259 | } |
260 | ||
3c0e092e | 261 | #[inline(always)] |
dc9dc135 | 262 | fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String { |
ba9703b0 | 263 | self.to_def_id().to_debug_str(tcx) |
ea8adc8c | 264 | } |
74b04a01 | 265 | |
3c0e092e | 266 | #[inline(always)] |
74b04a01 | 267 | fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> { |
ba9703b0 | 268 | dep_node.extract_def_id(tcx).map(|id| id.expect_local()) |
74b04a01 | 269 | } |
ea8adc8c XL |
270 | } |
271 | ||
2b03887a FG |
272 | impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for OwnerId { |
273 | #[inline(always)] | |
274 | fn fingerprint_style() -> FingerprintStyle { | |
275 | FingerprintStyle::DefPathHash | |
276 | } | |
277 | ||
278 | #[inline(always)] | |
279 | fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { | |
280 | self.to_def_id().to_fingerprint(tcx) | |
281 | } | |
282 | ||
283 | #[inline(always)] | |
284 | fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String { | |
285 | self.to_def_id().to_debug_str(tcx) | |
286 | } | |
287 | ||
288 | #[inline(always)] | |
289 | fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> { | |
290 | dep_node.extract_def_id(tcx).map(|id| OwnerId { def_id: id.expect_local() }) | |
291 | } | |
292 | } | |
293 | ||
ba9703b0 | 294 | impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for CrateNum { |
5869c6ff | 295 | #[inline(always)] |
c295e0f8 XL |
296 | fn fingerprint_style() -> FingerprintStyle { |
297 | FingerprintStyle::DefPathHash | |
f035d41b | 298 | } |
ea8adc8c | 299 | |
3c0e092e | 300 | #[inline(always)] |
ba9703b0 | 301 | fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { |
04454e1e | 302 | let def_id = self.as_def_id(); |
fc512014 | 303 | def_id.to_fingerprint(tcx) |
ea8adc8c XL |
304 | } |
305 | ||
3c0e092e | 306 | #[inline(always)] |
dc9dc135 | 307 | fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String { |
60c5eb7d | 308 | tcx.crate_name(*self).to_string() |
ea8adc8c | 309 | } |
74b04a01 | 310 | |
3c0e092e | 311 | #[inline(always)] |
74b04a01 XL |
312 | fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> { |
313 | dep_node.extract_def_id(tcx).map(|id| id.krate) | |
314 | } | |
ea8adc8c XL |
315 | } |
316 | ||
ba9703b0 | 317 | impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for (DefId, DefId) { |
5869c6ff | 318 | #[inline(always)] |
c295e0f8 XL |
319 | fn fingerprint_style() -> FingerprintStyle { |
320 | FingerprintStyle::Opaque | |
f035d41b | 321 | } |
041b39d2 XL |
322 | |
323 | // We actually would not need to specialize the implementation of this | |
324 | // method but it's faster to combine the hashes than to instantiate a full | |
325 | // hashing context and stable-hashing state. | |
3c0e092e | 326 | #[inline(always)] |
ba9703b0 | 327 | fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { |
041b39d2 XL |
328 | let (def_id_0, def_id_1) = *self; |
329 | ||
330 | let def_path_hash_0 = tcx.def_path_hash(def_id_0); | |
331 | let def_path_hash_1 = tcx.def_path_hash(def_id_1); | |
332 | ||
333 | def_path_hash_0.0.combine(def_path_hash_1.0) | |
334 | } | |
335 | ||
3c0e092e | 336 | #[inline(always)] |
dc9dc135 | 337 | fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String { |
041b39d2 XL |
338 | let (def_id_0, def_id_1) = *self; |
339 | ||
dfeec247 | 340 | format!("({}, {})", tcx.def_path_debug_str(def_id_0), tcx.def_path_debug_str(def_id_1)) |
041b39d2 XL |
341 | } |
342 | } | |
343 | ||
ba9703b0 | 344 | impl<'tcx> DepNodeParams<TyCtxt<'tcx>> for HirId { |
5869c6ff | 345 | #[inline(always)] |
c295e0f8 | 346 | fn fingerprint_style() -> FingerprintStyle { |
2b03887a | 347 | FingerprintStyle::HirId |
f035d41b | 348 | } |
041b39d2 XL |
349 | |
350 | // We actually would not need to specialize the implementation of this | |
351 | // method but it's faster to combine the hashes than to instantiate a full | |
352 | // hashing context and stable-hashing state. | |
3c0e092e | 353 | #[inline(always)] |
ba9703b0 | 354 | fn to_fingerprint(&self, tcx: TyCtxt<'tcx>) -> Fingerprint { |
dfeec247 | 355 | let HirId { owner, local_id } = *self; |
ba9703b0 | 356 | let def_path_hash = tcx.def_path_hash(owner.to_def_id()); |
2b03887a FG |
357 | Fingerprint::new( |
358 | // `owner` is local, so is completely defined by the local hash | |
359 | def_path_hash.local_hash(), | |
360 | local_id.as_u32().into(), | |
361 | ) | |
362 | } | |
363 | ||
364 | #[inline(always)] | |
365 | fn to_debug_str(&self, tcx: TyCtxt<'tcx>) -> String { | |
366 | let HirId { owner, local_id } = *self; | |
367 | format!("{}.{}", tcx.def_path_str(owner.to_def_id()), local_id.as_u32()) | |
368 | } | |
041b39d2 | 369 | |
2b03887a FG |
370 | #[inline(always)] |
371 | fn recover(tcx: TyCtxt<'tcx>, dep_node: &DepNode) -> Option<Self> { | |
372 | if tcx.fingerprint_style(dep_node.kind) == FingerprintStyle::HirId { | |
373 | let (local_hash, local_id) = Fingerprint::from(dep_node.hash).as_value(); | |
374 | let def_path_hash = DefPathHash::new(tcx.sess.local_stable_crate_id(), local_hash); | |
375 | let def_id = tcx | |
376 | .def_path_hash_to_def_id(def_path_hash, &mut || { | |
377 | panic!("Failed to extract HirId: {:?} {}", dep_node.kind, dep_node.hash) | |
378 | }) | |
379 | .expect_local(); | |
380 | let local_id = local_id | |
381 | .try_into() | |
382 | .unwrap_or_else(|_| panic!("local id should be u32, found {:?}", local_id)); | |
383 | Some(HirId { owner: OwnerId { def_id }, local_id: ItemLocalId::from_u32(local_id) }) | |
384 | } else { | |
385 | None | |
386 | } | |
54a0048b SL |
387 | } |
388 | } |