]>
Commit | Line | Data |
---|---|---|
ba9703b0 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 | |
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: | |
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 | |
20 | //! memory without any post-processing (e.g., "abomination-style" pointer | |
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 | //! | |
cdc7bbd5 | 29 | //! `DepNode` definition happens in `rustc_middle` with the `define_dep_nodes!()` macro. |
ba9703b0 XL |
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. | |
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 | |
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. | |
44 | ||
781aab86 | 45 | use super::{DepContext, FingerprintStyle}; |
c295e0f8 | 46 | use crate::ich::StableHashingContext; |
ba9703b0 | 47 | |
fc512014 | 48 | use rustc_data_structures::fingerprint::{Fingerprint, PackedFingerprint}; |
fe692bf9 | 49 | use rustc_data_structures::stable_hasher::{HashStable, StableHasher, StableOrd, ToStableHashKey}; |
781aab86 | 50 | use rustc_data_structures::AtomicRef; |
2b03887a | 51 | use rustc_hir::definitions::DefPathHash; |
ba9703b0 XL |
52 | use std::fmt; |
53 | use std::hash::Hash; | |
54 | ||
781aab86 FG |
55 | /// This serves as an index into arrays built by `make_dep_kind_array`. |
56 | #[derive(Clone, Copy, PartialEq, Eq, Hash)] | |
57 | pub struct DepKind { | |
58 | variant: u16, | |
59 | } | |
60 | ||
61 | impl DepKind { | |
62 | #[inline] | |
63 | pub const fn new(variant: u16) -> Self { | |
64 | Self { variant } | |
65 | } | |
66 | ||
67 | #[inline] | |
68 | pub const fn as_inner(&self) -> u16 { | |
69 | self.variant | |
70 | } | |
71 | ||
72 | #[inline] | |
73 | pub const fn as_usize(&self) -> usize { | |
74 | self.variant as usize | |
75 | } | |
76 | } | |
77 | ||
78 | static_assert_size!(DepKind, 2); | |
79 | ||
80 | pub fn default_dep_kind_debug(kind: DepKind, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
81 | f.debug_struct("DepKind").field("variant", &kind.variant).finish() | |
82 | } | |
83 | ||
84 | pub static DEP_KIND_DEBUG: AtomicRef<fn(DepKind, &mut fmt::Formatter<'_>) -> fmt::Result> = | |
85 | AtomicRef::new(&(default_dep_kind_debug as fn(_, &mut fmt::Formatter<'_>) -> _)); | |
86 | ||
87 | impl fmt::Debug for DepKind { | |
88 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
89 | (*DEP_KIND_DEBUG)(*self, f) | |
90 | } | |
91 | } | |
92 | ||
93 | #[derive(Clone, Copy, PartialEq, Eq, Hash)] | |
94 | pub struct DepNode { | |
95 | pub kind: DepKind, | |
fc512014 | 96 | pub hash: PackedFingerprint, |
ba9703b0 XL |
97 | } |
98 | ||
781aab86 FG |
99 | // We keep a lot of `DepNode`s in memory during compilation. It's not |
100 | // required that their size stay the same, but we don't want to change | |
101 | // it inadvertently. This assert just ensures we're aware of any change. | |
102 | #[cfg(any(target_arch = "x86", target_arch = "x86_64"))] | |
103 | static_assert_size!(DepNode, 18); | |
104 | ||
105 | #[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))] | |
106 | static_assert_size!(DepNode, 24); | |
107 | ||
108 | impl DepNode { | |
ba9703b0 XL |
109 | /// Creates a new, parameterless DepNode. This method will assert |
110 | /// that the DepNode corresponding to the given DepKind actually | |
111 | /// does not require any parameters. | |
781aab86 | 112 | pub fn new_no_params<Tcx>(tcx: Tcx, kind: DepKind) -> DepNode |
3c0e092e | 113 | where |
781aab86 | 114 | Tcx: super::DepContext, |
3c0e092e XL |
115 | { |
116 | debug_assert_eq!(tcx.fingerprint_style(kind), FingerprintStyle::Unit); | |
fc512014 | 117 | DepNode { kind, hash: Fingerprint::ZERO.into() } |
ba9703b0 | 118 | } |
f9f354fc | 119 | |
781aab86 | 120 | pub fn construct<Tcx, Key>(tcx: Tcx, kind: DepKind, arg: &Key) -> DepNode |
f9f354fc | 121 | where |
781aab86 | 122 | Tcx: super::DepContext, |
487cf647 | 123 | Key: DepNodeParams<Tcx>, |
f9f354fc XL |
124 | { |
125 | let hash = arg.to_fingerprint(tcx); | |
fc512014 | 126 | let dep_node = DepNode { kind, hash: hash.into() }; |
f9f354fc XL |
127 | |
128 | #[cfg(debug_assertions)] | |
129 | { | |
3c0e092e | 130 | if !tcx.fingerprint_style(kind).reconstructible() |
064997fb FG |
131 | && (tcx.sess().opts.unstable_opts.incremental_info |
132 | || tcx.sess().opts.unstable_opts.query_dep_graph) | |
6a06907d | 133 | { |
f9f354fc XL |
134 | tcx.dep_graph().register_dep_node_debug_str(dep_node, || arg.to_debug_str(tcx)); |
135 | } | |
136 | } | |
137 | ||
138 | dep_node | |
139 | } | |
2b03887a FG |
140 | |
141 | /// Construct a DepNode from the given DepKind and DefPathHash. This | |
142 | /// method will assert that the given DepKind actually requires a | |
143 | /// single DefId/DefPathHash parameter. | |
781aab86 | 144 | pub fn from_def_path_hash<Tcx>(tcx: Tcx, def_path_hash: DefPathHash, kind: DepKind) -> Self |
2b03887a | 145 | where |
781aab86 | 146 | Tcx: super::DepContext, |
2b03887a FG |
147 | { |
148 | debug_assert!(tcx.fingerprint_style(kind) == FingerprintStyle::DefPathHash); | |
149 | DepNode { kind, hash: def_path_hash.0.into() } | |
150 | } | |
ba9703b0 XL |
151 | } |
152 | ||
781aab86 FG |
153 | pub fn default_dep_node_debug(node: DepNode, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
154 | f.debug_struct("DepNode").field("kind", &node.kind).field("hash", &node.hash).finish() | |
155 | } | |
156 | ||
157 | pub static DEP_NODE_DEBUG: AtomicRef<fn(DepNode, &mut fmt::Formatter<'_>) -> fmt::Result> = | |
158 | AtomicRef::new(&(default_dep_node_debug as fn(_, &mut fmt::Formatter<'_>) -> _)); | |
159 | ||
160 | impl fmt::Debug for DepNode { | |
ba9703b0 | 161 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
781aab86 | 162 | (*DEP_NODE_DEBUG)(*self, f) |
ba9703b0 XL |
163 | } |
164 | } | |
165 | ||
487cf647 | 166 | pub trait DepNodeParams<Tcx: DepContext>: fmt::Debug + Sized { |
c295e0f8 | 167 | fn fingerprint_style() -> FingerprintStyle; |
ba9703b0 XL |
168 | |
169 | /// This method turns the parameters of a DepNodeConstructor into an opaque | |
170 | /// Fingerprint to be used in DepNode. | |
171 | /// Not all DepNodeParams support being turned into a Fingerprint (they | |
172 | /// don't need to if the corresponding DepNode is anonymous). | |
487cf647 | 173 | fn to_fingerprint(&self, _: Tcx) -> Fingerprint { |
ba9703b0 XL |
174 | panic!("Not implemented. Accidentally called on anonymous node?") |
175 | } | |
176 | ||
487cf647 | 177 | fn to_debug_str(&self, _: Tcx) -> String { |
9c376795 | 178 | format!("{self:?}") |
ba9703b0 XL |
179 | } |
180 | ||
181 | /// This method tries to recover the query key from the given `DepNode`, | |
182 | /// something which is needed when forcing `DepNode`s during red-green | |
183 | /// evaluation. The query system will only call this method if | |
c295e0f8 | 184 | /// `fingerprint_style()` is not `FingerprintStyle::Opaque`. |
ba9703b0 XL |
185 | /// It is always valid to return `None` here, in which case incremental |
186 | /// compilation will treat the query as having changed instead of forcing it. | |
781aab86 | 187 | fn recover(tcx: Tcx, dep_node: &DepNode) -> Option<Self>; |
ba9703b0 XL |
188 | } |
189 | ||
487cf647 | 190 | impl<Tcx: DepContext, T> DepNodeParams<Tcx> for T |
ba9703b0 | 191 | where |
c295e0f8 | 192 | T: for<'a> HashStable<StableHashingContext<'a>> + fmt::Debug, |
ba9703b0 | 193 | { |
3c0e092e | 194 | #[inline(always)] |
c295e0f8 XL |
195 | default fn fingerprint_style() -> FingerprintStyle { |
196 | FingerprintStyle::Opaque | |
f035d41b | 197 | } |
ba9703b0 | 198 | |
3c0e092e | 199 | #[inline(always)] |
487cf647 | 200 | default fn to_fingerprint(&self, tcx: Tcx) -> Fingerprint { |
064997fb FG |
201 | tcx.with_stable_hashing_context(|mut hcx| { |
202 | let mut hasher = StableHasher::new(); | |
203 | self.hash_stable(&mut hcx, &mut hasher); | |
204 | hasher.finish() | |
205 | }) | |
ba9703b0 XL |
206 | } |
207 | ||
3c0e092e | 208 | #[inline(always)] |
487cf647 | 209 | default fn to_debug_str(&self, _: Tcx) -> String { |
ba9703b0 XL |
210 | format!("{:?}", *self) |
211 | } | |
212 | ||
3c0e092e | 213 | #[inline(always)] |
781aab86 | 214 | default fn recover(_: Tcx, _: &DepNode) -> Option<Self> { |
ba9703b0 XL |
215 | None |
216 | } | |
217 | } | |
218 | ||
2b03887a FG |
219 | /// This struct stores metadata about each DepKind. |
220 | /// | |
221 | /// Information is retrieved by indexing the `DEP_KINDS` array using the integer value | |
222 | /// of the `DepKind`. Overall, this allows to implement `DepContext` using this manual | |
223 | /// jump table instead of large matches. | |
487cf647 | 224 | pub struct DepKindStruct<Tcx: DepContext> { |
2b03887a FG |
225 | /// Anonymous queries cannot be replayed from one compiler invocation to the next. |
226 | /// When their result is needed, it is recomputed. They are useful for fine-grained | |
227 | /// dependency tracking, and caching within one compiler invocation. | |
228 | pub is_anon: bool, | |
229 | ||
230 | /// Eval-always queries do not track their dependencies, and are always recomputed, even if | |
231 | /// their inputs have not changed since the last compiler invocation. The result is still | |
232 | /// cached within one compiler invocation. | |
233 | pub is_eval_always: bool, | |
234 | ||
235 | /// Whether the query key can be recovered from the hashed fingerprint. | |
236 | /// See [DepNodeParams] trait for the behaviour of each key type. | |
237 | pub fingerprint_style: FingerprintStyle, | |
238 | ||
239 | /// The red/green evaluation system will try to mark a specific DepNode in the | |
240 | /// dependency graph as green by recursively trying to mark the dependencies of | |
241 | /// that `DepNode` as green. While doing so, it will sometimes encounter a `DepNode` | |
242 | /// where we don't know if it is red or green and we therefore actually have | |
243 | /// to recompute its value in order to find out. Since the only piece of | |
244 | /// information that we have at that point is the `DepNode` we are trying to | |
245 | /// re-evaluate, we need some way to re-run a query from just that. This is what | |
246 | /// `force_from_dep_node()` implements. | |
247 | /// | |
248 | /// In the general case, a `DepNode` consists of a `DepKind` and an opaque | |
249 | /// GUID/fingerprint that will uniquely identify the node. This GUID/fingerprint | |
250 | /// is usually constructed by computing a stable hash of the query-key that the | |
251 | /// `DepNode` corresponds to. Consequently, it is not in general possible to go | |
252 | /// back from hash to query-key (since hash functions are not reversible). For | |
253 | /// this reason `force_from_dep_node()` is expected to fail from time to time | |
254 | /// because we just cannot find out, from the `DepNode` alone, what the | |
255 | /// corresponding query-key is and therefore cannot re-run the query. | |
256 | /// | |
257 | /// The system deals with this case letting `try_mark_green` fail which forces | |
258 | /// the root query to be re-evaluated. | |
259 | /// | |
260 | /// Now, if `force_from_dep_node()` would always fail, it would be pretty useless. | |
261 | /// Fortunately, we can use some contextual information that will allow us to | |
262 | /// reconstruct query-keys for certain kinds of `DepNode`s. In particular, we | |
263 | /// enforce by construction that the GUID/fingerprint of certain `DepNode`s is a | |
264 | /// valid `DefPathHash`. Since we also always build a huge table that maps every | |
265 | /// `DefPathHash` in the current codebase to the corresponding `DefId`, we have | |
266 | /// everything we need to re-run the query. | |
267 | /// | |
268 | /// Take the `mir_promoted` query as an example. Like many other queries, it | |
269 | /// just has a single parameter: the `DefId` of the item it will compute the | |
270 | /// validated MIR for. Now, when we call `force_from_dep_node()` on a `DepNode` | |
271 | /// with kind `MirValidated`, we know that the GUID/fingerprint of the `DepNode` | |
272 | /// is actually a `DefPathHash`, and can therefore just look up the corresponding | |
273 | /// `DefId` in `tcx.def_path_hash_to_def_id`. | |
781aab86 | 274 | pub force_from_dep_node: Option<fn(tcx: Tcx, dep_node: DepNode) -> bool>, |
2b03887a FG |
275 | |
276 | /// Invoke a query to put the on-disk cached value in memory. | |
781aab86 FG |
277 | pub try_load_from_on_disk_cache: Option<fn(Tcx, DepNode)>, |
278 | ||
279 | /// The name of this dep kind. | |
280 | pub name: &'static &'static str, | |
2b03887a FG |
281 | } |
282 | ||
ba9703b0 XL |
283 | /// A "work product" corresponds to a `.o` (or other) file that we |
284 | /// save in between runs. These IDs do not have a `DefId` but rather | |
285 | /// some independent path or string that persists between runs without | |
286 | /// the need to be mapped or unmapped. (This ensures we can serialize | |
287 | /// them even in the absence of a tcx.) | |
3dfed10e XL |
288 | #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] |
289 | #[derive(Encodable, Decodable)] | |
ba9703b0 XL |
290 | pub struct WorkProductId { |
291 | hash: Fingerprint, | |
292 | } | |
293 | ||
294 | impl WorkProductId { | |
295 | pub fn from_cgu_name(cgu_name: &str) -> WorkProductId { | |
296 | let mut hasher = StableHasher::new(); | |
ba9703b0 XL |
297 | cgu_name.hash(&mut hasher); |
298 | WorkProductId { hash: hasher.finish() } | |
299 | } | |
ba9703b0 XL |
300 | } |
301 | ||
302 | impl<HCX> HashStable<HCX> for WorkProductId { | |
303 | #[inline] | |
304 | fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { | |
305 | self.hash.hash_stable(hcx, hasher) | |
306 | } | |
307 | } | |
fe692bf9 FG |
308 | impl<HCX> ToStableHashKey<HCX> for WorkProductId { |
309 | type KeyType = Fingerprint; | |
310 | #[inline] | |
311 | fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType { | |
312 | self.hash | |
313 | } | |
314 | } | |
315 | unsafe impl StableOrd for WorkProductId { | |
316 | // Fingerprint can use unstable (just a tuple of `u64`s), so WorkProductId can as well | |
317 | const CAN_USE_UNSTABLE_SORT: bool = true; | |
318 | } |