]>
Commit | Line | Data |
---|---|---|
7453a54e | 1 | //! The `ObligationForest` is a utility data structure used in trait |
9fa01778 XL |
2 | //! matching to track the set of outstanding obligations (those not yet |
3 | //! resolved to success or error). It also tracks the "backtrace" of each | |
4 | //! pending obligation (why we are trying to figure this out in the first | |
5 | //! place). | |
6 | //! | |
7 | //! ### External view | |
8 | //! | |
9 | //! `ObligationForest` supports two main public operations (there are a | |
10 | //! few others not discussed here): | |
11 | //! | |
e1599b0c | 12 | //! 1. Add a new root obligations (`register_obligation`). |
9fa01778 XL |
13 | //! 2. Process the pending obligations (`process_obligations`). |
14 | //! | |
15 | //! When a new obligation `N` is added, it becomes the root of an | |
16 | //! obligation tree. This tree can also carry some per-tree state `T`, | |
17 | //! which is given at the same time. This tree is a singleton to start, so | |
18 | //! `N` is both the root and the only leaf. Each time the | |
19 | //! `process_obligations` method is called, it will invoke its callback | |
20 | //! with every pending obligation (so that will include `N`, the first | |
21 | //! time). The callback also receives a (mutable) reference to the | |
22 | //! per-tree state `T`. The callback should process the obligation `O` | |
e1599b0c | 23 | //! that it is given and return a `ProcessResult`: |
9fa01778 | 24 | //! |
e1599b0c | 25 | //! - `Unchanged` -> ambiguous result. Obligation was neither a success |
9fa01778 XL |
26 | //! nor a failure. It is assumed that further attempts to process the |
27 | //! obligation will yield the same result unless something in the | |
28 | //! surrounding environment changes. | |
e1599b0c | 29 | //! - `Changed(C)` - the obligation was *shallowly successful*. The |
9fa01778 XL |
30 | //! vector `C` is a list of subobligations. The meaning of this is that |
31 | //! `O` was successful on the assumption that all the obligations in `C` | |
32 | //! are also successful. Therefore, `O` is only considered a "true" | |
33 | //! success if `C` is empty. Otherwise, `O` is put into a suspended | |
34 | //! state and the obligations in `C` become the new pending | |
35 | //! obligations. They will be processed the next time you call | |
36 | //! `process_obligations`. | |
e1599b0c | 37 | //! - `Error(E)` -> obligation failed with error `E`. We will collect this |
9fa01778 XL |
38 | //! error and return it from `process_obligations`, along with the |
39 | //! "backtrace" of obligations (that is, the list of obligations up to | |
40 | //! and including the root of the failed obligation). No further | |
41 | //! obligations from that same tree will be processed, since the tree is | |
42 | //! now considered to be in error. | |
43 | //! | |
44 | //! When the call to `process_obligations` completes, you get back an `Outcome`, | |
923072b8 | 45 | //! which includes two bits of information: |
9fa01778 XL |
46 | //! |
47 | //! - `completed`: a list of obligations where processing was fully | |
48 | //! completed without error (meaning that all transitive subobligations | |
49 | //! have also been completed). So, for example, if the callback from | |
e1599b0c | 50 | //! `process_obligations` returns `Changed(C)` for some obligation `O`, |
9fa01778 XL |
51 | //! then `O` will be considered completed right away if `C` is the |
52 | //! empty vector. Otherwise it will only be considered completed once | |
53 | //! all the obligations in `C` have been found completed. | |
54 | //! - `errors`: a list of errors that occurred and associated backtraces | |
55 | //! at the time of error, which can be used to give context to the user. | |
923072b8 FG |
56 | //! |
57 | //! Upon completion, none of the existing obligations were *shallowly | |
58 | //! successful* (that is, no callback returned `Changed(_)`). This implies that | |
59 | //! all obligations were either errors or returned an ambiguous result. | |
9fa01778 | 60 | //! |
9fa01778 XL |
61 | //! ### Implementation details |
62 | //! | |
63 | //! For the most part, comments specific to the implementation are in the | |
64 | //! code. This file only contains a very high-level overview. Basically, | |
65 | //! the forest is stored in a vector. Each element of the vector is a node | |
e1599b0c XL |
66 | //! in some tree. Each node in the vector has the index of its dependents, |
67 | //! including the first dependent which is known as the parent. It also | |
68 | //! has a current state, described by `NodeState`. After each processing | |
69 | //! step, we compress the vector to remove completed and error nodes, which | |
70 | //! aren't needed anymore. | |
9fa01778 XL |
71 | |
72 | use crate::fx::{FxHashMap, FxHashSet}; | |
a7813a04 | 73 | |
74b04a01 | 74 | use std::cell::Cell; |
a7813a04 | 75 | use std::collections::hash_map::Entry; |
7453a54e | 76 | use std::fmt::Debug; |
a7813a04 XL |
77 | use std::hash; |
78 | use std::marker::PhantomData; | |
7453a54e | 79 | |
0bf4aa26 XL |
80 | mod graphviz; |
81 | ||
7453a54e | 82 | #[cfg(test)] |
416331ca | 83 | mod tests; |
7453a54e | 84 | |
60c5eb7d | 85 | pub trait ForestObligation: Clone + Debug { |
74b04a01 | 86 | type CacheKey: Clone + hash::Hash + Eq + Debug; |
a7813a04 | 87 | |
74b04a01 XL |
88 | /// Converts this `ForestObligation` suitable for use as a cache key. |
89 | /// If two distinct `ForestObligations`s return the same cache key, | |
90 | /// then it must be sound to use the result of processing one obligation | |
91 | /// (e.g. success for error) for the other obligation | |
92 | fn as_cache_key(&self) -> Self::CacheKey; | |
a7813a04 XL |
93 | } |
94 | ||
95 | pub trait ObligationProcessor { | |
60c5eb7d XL |
96 | type Obligation: ForestObligation; |
97 | type Error: Debug; | |
a7813a04 | 98 | |
923072b8 FG |
99 | fn needs_process_obligation(&self, obligation: &Self::Obligation) -> bool; |
100 | ||
60c5eb7d XL |
101 | fn process_obligation( |
102 | &mut self, | |
103 | obligation: &mut Self::Obligation, | |
104 | ) -> ProcessResult<Self::Obligation, Self::Error>; | |
a7813a04 | 105 | |
cc61c64b XL |
106 | /// As we do the cycle check, we invoke this callback when we |
107 | /// encounter an actual cycle. `cycle` is an iterator that starts | |
108 | /// at the start of the cycle in the stack and walks **toward the | |
109 | /// top**. | |
110 | /// | |
111 | /// In other words, if we had O1 which required O2 which required | |
112 | /// O3 which required O1, we would give an iterator yielding O1, | |
113 | /// O2, O3 (O1 is not yielded twice). | |
60c5eb7d XL |
114 | fn process_backedge<'c, I>(&mut self, cycle: I, _marker: PhantomData<&'c Self::Obligation>) |
115 | where | |
116 | I: Clone + Iterator<Item = &'c Self::Obligation>; | |
a7813a04 XL |
117 | } |
118 | ||
94b46f34 | 119 | /// The result type used by `process_obligation`. |
f2b60f7d FG |
120 | // `repr(C)` to inhibit the niche filling optimization. Otherwise, the `match` appearing |
121 | // in `process_obligations` is significantly slower, which can substantially affect | |
122 | // benchmarks like `rustc-perf`'s inflate and keccak. | |
123 | #[repr(C)] | |
94b46f34 XL |
124 | #[derive(Debug)] |
125 | pub enum ProcessResult<O, E> { | |
126 | Unchanged, | |
127 | Changed(Vec<O>), | |
128 | Error(E), | |
129 | } | |
130 | ||
0bf4aa26 XL |
131 | #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)] |
132 | struct ObligationTreeId(usize); | |
133 | ||
134 | type ObligationTreeIdGenerator = | |
29967ef6 | 135 | std::iter::Map<std::ops::RangeFrom<usize>, fn(usize) -> ObligationTreeId>; |
0bf4aa26 | 136 | |
a7813a04 | 137 | pub struct ObligationForest<O: ForestObligation> { |
5e7ed085 | 138 | /// The list of obligations. In between calls to [Self::process_obligations], |
60c5eb7d | 139 | /// this list only contains nodes in the `Pending` or `Waiting` state. |
7453a54e | 140 | /// |
e1599b0c | 141 | /// `usize` indices are used here and throughout this module, rather than |
5e7ed085 | 142 | /// [`rustc_index::newtype_index!`] indices, because this code is hot enough |
60c5eb7d XL |
143 | /// that the `u32`-to-`usize` conversions that would be required are |
144 | /// significant, and space considerations are not important. | |
7453a54e | 145 | nodes: Vec<Node<O>>, |
0bf4aa26 | 146 | |
a7813a04 | 147 | /// A cache of predicates that have been successfully completed. |
74b04a01 | 148 | done_cache: FxHashSet<O::CacheKey>, |
0bf4aa26 | 149 | |
e1599b0c XL |
150 | /// A cache of the nodes in `nodes`, indexed by predicate. Unfortunately, |
151 | /// its contents are not guaranteed to match those of `nodes`. See the | |
923072b8 | 152 | /// comments in `Self::process_obligation` for details. |
74b04a01 | 153 | active_cache: FxHashMap<O::CacheKey, usize>, |
0bf4aa26 | 154 | |
5e7ed085 FG |
155 | /// A vector reused in [Self::compress()] and [Self::find_cycles_from_node()], |
156 | /// to avoid allocating new vectors. | |
29967ef6 | 157 | reused_node_vec: Vec<usize>, |
0bf4aa26 XL |
158 | |
159 | obligation_tree_id_generator: ObligationTreeIdGenerator, | |
160 | ||
9fa01778 | 161 | /// Per tree error cache. This is used to deduplicate errors, |
0bf4aa26 XL |
162 | /// which is necessary to avoid trait resolution overflow in |
163 | /// some cases. | |
164 | /// | |
165 | /// See [this][details] for details. | |
166 | /// | |
167 | /// [details]: https://github.com/rust-lang/rust/pull/53255#issuecomment-421184780 | |
74b04a01 | 168 | error_cache: FxHashMap<ObligationTreeId, FxHashSet<O::CacheKey>>, |
7453a54e SL |
169 | } |
170 | ||
a7813a04 | 171 | #[derive(Debug)] |
7453a54e | 172 | struct Node<O> { |
a7813a04 XL |
173 | obligation: O, |
174 | state: Cell<NodeState>, | |
175 | ||
e1599b0c XL |
176 | /// Obligations that depend on this obligation for their completion. They |
177 | /// must all be in a non-pending state. | |
178 | dependents: Vec<usize>, | |
8faf50e0 | 179 | |
f9f354fc | 180 | /// If true, `dependents[0]` points to a "parent" node, which requires |
e1599b0c XL |
181 | /// special treatment upon error but is otherwise treated the same. |
182 | /// (It would be more idiomatic to store the parent node in a separate | |
183 | /// `Option<usize>` field, but that slows down the common case of | |
184 | /// iterating over the parent and other descendants together.) | |
185 | has_parent: bool, | |
0bf4aa26 XL |
186 | |
187 | /// Identifier of the obligation tree to which this node belongs. | |
188 | obligation_tree_id: ObligationTreeId, | |
7453a54e SL |
189 | } |
190 | ||
e1599b0c | 191 | impl<O> Node<O> { |
60c5eb7d | 192 | fn new(parent: Option<usize>, obligation: O, obligation_tree_id: ObligationTreeId) -> Node<O> { |
e1599b0c XL |
193 | Node { |
194 | obligation, | |
195 | state: Cell::new(NodeState::Pending), | |
60c5eb7d | 196 | dependents: if let Some(parent_index) = parent { vec![parent_index] } else { vec![] }, |
e1599b0c XL |
197 | has_parent: parent.is_some(), |
198 | obligation_tree_id, | |
199 | } | |
200 | } | |
201 | } | |
202 | ||
60c5eb7d XL |
203 | /// The state of one node in some tree within the forest. This represents the |
204 | /// current state of processing for the obligation (of type `O`) associated | |
205 | /// with this node. | |
a7813a04 | 206 | /// |
60c5eb7d | 207 | /// The non-`Error` state transitions are as follows. |
04454e1e | 208 | /// ```text |
60c5eb7d XL |
209 | /// (Pre-creation) |
210 | /// | | |
211 | /// | register_obligation_at() (called by process_obligations() and | |
212 | /// v from outside the crate) | |
213 | /// Pending | |
214 | /// | | |
215 | /// | process_obligations() | |
216 | /// v | |
217 | /// Success | |
218 | /// | ^ | |
219 | /// | | mark_successes() | |
220 | /// | v | |
221 | /// | Waiting | |
222 | /// | | |
223 | /// | process_cycles() | |
224 | /// v | |
225 | /// Done | |
226 | /// | | |
227 | /// | compress() | |
228 | /// v | |
229 | /// (Removed) | |
230 | /// ``` | |
231 | /// The `Error` state can be introduced in several places, via `error_at()`. | |
232 | /// | |
233 | /// Outside of `ObligationForest` methods, nodes should be either `Pending` or | |
234 | /// `Waiting`. | |
a7813a04 XL |
235 | #[derive(Debug, Copy, Clone, PartialEq, Eq)] |
236 | enum NodeState { | |
60c5eb7d XL |
237 | /// This obligation has not yet been selected successfully. Cannot have |
238 | /// subobligations. | |
a7813a04 XL |
239 | Pending, |
240 | ||
60c5eb7d XL |
241 | /// This obligation was selected successfully, but may or may not have |
242 | /// subobligations. | |
a7813a04 XL |
243 | Success, |
244 | ||
60c5eb7d XL |
245 | /// This obligation was selected successfully, but it has a pending |
246 | /// subobligation. | |
a7813a04 XL |
247 | Waiting, |
248 | ||
60c5eb7d XL |
249 | /// This obligation, along with its subobligations, are complete, and will |
250 | /// be removed in the next collection. | |
a7813a04 | 251 | Done, |
7453a54e | 252 | |
60c5eb7d XL |
253 | /// This obligation was resolved to an error. It will be removed by the |
254 | /// next compression step. | |
7453a54e SL |
255 | Error, |
256 | } | |
257 | ||
29967ef6 XL |
258 | /// This trait allows us to have two different Outcome types: |
259 | /// - the normal one that does as little as possible | |
260 | /// - one for tests that does some additional work and checking | |
261 | pub trait OutcomeTrait { | |
262 | type Error; | |
263 | type Obligation; | |
264 | ||
265 | fn new() -> Self; | |
29967ef6 XL |
266 | fn record_completed(&mut self, outcome: &Self::Obligation); |
267 | fn record_error(&mut self, error: Self::Error); | |
268 | } | |
269 | ||
7453a54e | 270 | #[derive(Debug)] |
54a0048b | 271 | pub struct Outcome<O, E> { |
7453a54e | 272 | /// Backtrace of obligations that were found to be in error. |
54a0048b | 273 | pub errors: Vec<Error<O, E>>, |
7453a54e SL |
274 | } |
275 | ||
29967ef6 XL |
276 | impl<O, E> OutcomeTrait for Outcome<O, E> { |
277 | type Error = Error<O, E>; | |
278 | type Obligation = O; | |
279 | ||
280 | fn new() -> Self { | |
923072b8 | 281 | Self { errors: vec![] } |
29967ef6 XL |
282 | } |
283 | ||
284 | fn record_completed(&mut self, _outcome: &Self::Obligation) { | |
285 | // do nothing | |
286 | } | |
287 | ||
288 | fn record_error(&mut self, error: Self::Error) { | |
289 | self.errors.push(error) | |
290 | } | |
a1dfa0c6 XL |
291 | } |
292 | ||
7453a54e | 293 | #[derive(Debug, PartialEq, Eq)] |
54a0048b | 294 | pub struct Error<O, E> { |
7453a54e SL |
295 | pub error: E, |
296 | pub backtrace: Vec<O>, | |
297 | } | |
298 | ||
a7813a04 XL |
299 | impl<O: ForestObligation> ObligationForest<O> { |
300 | pub fn new() -> ObligationForest<O> { | |
7453a54e | 301 | ObligationForest { |
7453a54e | 302 | nodes: vec![], |
0bf4aa26 | 303 | done_cache: Default::default(), |
e74abb32 | 304 | active_cache: Default::default(), |
29967ef6 | 305 | reused_node_vec: vec![], |
dc9dc135 | 306 | obligation_tree_id_generator: (0..).map(ObligationTreeId), |
0bf4aa26 | 307 | error_cache: Default::default(), |
7453a54e SL |
308 | } |
309 | } | |
310 | ||
9fa01778 | 311 | /// Returns the total number of nodes in the forest that have not |
7453a54e SL |
312 | /// yet been fully resolved. |
313 | pub fn len(&self) -> usize { | |
314 | self.nodes.len() | |
315 | } | |
316 | ||
9fa01778 | 317 | /// Registers an obligation. |
a7813a04 XL |
318 | pub fn register_obligation(&mut self, obligation: O) { |
319 | // Ignore errors here - there is no guarantee of success. | |
320 | let _ = self.register_obligation_at(obligation, None); | |
321 | } | |
322 | ||
e1599b0c XL |
323 | // Returns Err(()) if we already know this obligation failed. |
324 | fn register_obligation_at(&mut self, obligation: O, parent: Option<usize>) -> Result<(), ()> { | |
17df50a5 XL |
325 | let cache_key = obligation.as_cache_key(); |
326 | if self.done_cache.contains(&cache_key) { | |
74b04a01 | 327 | debug!("register_obligation_at: ignoring already done obligation: {:?}", obligation); |
0bf4aa26 | 328 | return Ok(()); |
a7813a04 XL |
329 | } |
330 | ||
17df50a5 | 331 | match self.active_cache.entry(cache_key) { |
a7813a04 | 332 | Entry::Occupied(o) => { |
60c5eb7d | 333 | let node = &mut self.nodes[*o.get()]; |
e1599b0c | 334 | if let Some(parent_index) = parent { |
e74abb32 XL |
335 | // If the node is already in `active_cache`, it has already |
336 | // had its chance to be marked with a parent. So if it's | |
337 | // not already present, just dump `parent` into the | |
e1599b0c XL |
338 | // dependents as a non-parent. |
339 | if !node.dependents.contains(&parent_index) { | |
340 | node.dependents.push(parent_index); | |
a7813a04 XL |
341 | } |
342 | } | |
60c5eb7d | 343 | if let NodeState::Error = node.state.get() { Err(()) } else { Ok(()) } |
a7813a04 XL |
344 | } |
345 | Entry::Vacant(v) => { | |
0bf4aa26 | 346 | let obligation_tree_id = match parent { |
e1599b0c XL |
347 | Some(parent_index) => self.nodes[parent_index].obligation_tree_id, |
348 | None => self.obligation_tree_id_generator.next().unwrap(), | |
0bf4aa26 XL |
349 | }; |
350 | ||
60c5eb7d XL |
351 | let already_failed = parent.is_some() |
352 | && self | |
353 | .error_cache | |
354 | .get(&obligation_tree_id) | |
17df50a5 | 355 | .map_or(false, |errors| errors.contains(v.key())); |
0bf4aa26 XL |
356 | |
357 | if already_failed { | |
358 | Err(()) | |
359 | } else { | |
e74abb32 XL |
360 | let new_index = self.nodes.len(); |
361 | v.insert(new_index); | |
0bf4aa26 XL |
362 | self.nodes.push(Node::new(parent, obligation, obligation_tree_id)); |
363 | Ok(()) | |
364 | } | |
a7813a04 XL |
365 | } |
366 | } | |
7453a54e SL |
367 | } |
368 | ||
9fa01778 | 369 | /// Converts all remaining obligations to the given error. |
54a0048b | 370 | pub fn to_errors<E: Clone>(&mut self, error: E) -> Vec<Error<O, E>> { |
60c5eb7d XL |
371 | let errors = self |
372 | .nodes | |
373 | .iter() | |
374 | .enumerate() | |
e74abb32 | 375 | .filter(|(_index, node)| node.state.get() == NodeState::Pending) |
60c5eb7d | 376 | .map(|(index, _node)| Error { error: error.clone(), backtrace: self.error_at(index) }) |
e74abb32 XL |
377 | .collect(); |
378 | ||
3c0e092e | 379 | self.compress(|_| assert!(false)); |
7453a54e SL |
380 | errors |
381 | } | |
382 | ||
383 | /// Returns the set of obligations that are in a pending state. | |
94b46f34 | 384 | pub fn map_pending_obligations<P, F>(&self, f: F) -> Vec<P> |
60c5eb7d XL |
385 | where |
386 | F: Fn(&O) -> P, | |
54a0048b | 387 | { |
60c5eb7d XL |
388 | self.nodes |
389 | .iter() | |
e74abb32 XL |
390 | .filter(|node| node.state.get() == NodeState::Pending) |
391 | .map(|node| f(&node.obligation)) | |
54a0048b | 392 | .collect() |
7453a54e SL |
393 | } |
394 | ||
e74abb32 XL |
395 | fn insert_into_error_cache(&mut self, index: usize) { |
396 | let node = &self.nodes[index]; | |
0bf4aa26 XL |
397 | self.error_cache |
398 | .entry(node.obligation_tree_id) | |
399 | .or_default() | |
74b04a01 | 400 | .insert(node.obligation.as_cache_key()); |
0bf4aa26 XL |
401 | } |
402 | ||
923072b8 | 403 | /// Performs a fixpoint computation over the obligation list. |
136023e0 | 404 | #[inline(never)] |
29967ef6 | 405 | pub fn process_obligations<P, OUT>(&mut self, processor: &mut P) -> OUT |
60c5eb7d XL |
406 | where |
407 | P: ObligationProcessor<Obligation = O>, | |
29967ef6 | 408 | OUT: OutcomeTrait<Obligation = O, Error = Error<O, P::Error>>, |
7453a54e | 409 | { |
29967ef6 | 410 | let mut outcome = OUT::new(); |
7453a54e | 411 | |
923072b8 FG |
412 | // Fixpoint computation: we repeat until the inner loop stalls. |
413 | loop { | |
414 | let mut has_changed = false; | |
415 | ||
416 | // Note that the loop body can append new nodes, and those new nodes | |
417 | // will then be processed by subsequent iterations of the loop. | |
418 | // | |
419 | // We can't use an iterator for the loop because `self.nodes` is | |
420 | // appended to and the borrow checker would complain. We also can't use | |
421 | // `for index in 0..self.nodes.len() { ... }` because the range would | |
422 | // be computed with the initial length, and we would miss the appended | |
423 | // nodes. Therefore we use a `while` loop. | |
424 | let mut index = 0; | |
425 | while let Some(node) = self.nodes.get_mut(index) { | |
426 | if node.state.get() != NodeState::Pending | |
427 | || !processor.needs_process_obligation(&node.obligation) | |
428 | { | |
429 | index += 1; | |
430 | continue; | |
7453a54e | 431 | } |
923072b8 FG |
432 | |
433 | // `processor.process_obligation` can modify the predicate within | |
434 | // `node.obligation`, and that predicate is the key used for | |
435 | // `self.active_cache`. This means that `self.active_cache` can get | |
436 | // out of sync with `nodes`. It's not very common, but it does | |
437 | // happen, and code in `compress` has to allow for it. | |
438 | ||
439 | match processor.process_obligation(&mut node.obligation) { | |
440 | ProcessResult::Unchanged => { | |
441 | // No change in state. | |
442 | } | |
443 | ProcessResult::Changed(children) => { | |
444 | // We are not (yet) stalled. | |
445 | has_changed = true; | |
446 | node.state.set(NodeState::Success); | |
447 | ||
448 | for child in children { | |
449 | let st = self.register_obligation_at(child, Some(index)); | |
450 | if let Err(()) = st { | |
451 | // Error already reported - propagate it | |
452 | // to our node. | |
453 | self.error_at(index); | |
454 | } | |
a7813a04 XL |
455 | } |
456 | } | |
923072b8 FG |
457 | ProcessResult::Error(err) => { |
458 | has_changed = true; | |
459 | outcome.record_error(Error { error: err, backtrace: self.error_at(index) }); | |
460 | } | |
7453a54e | 461 | } |
923072b8 FG |
462 | index += 1; |
463 | } | |
464 | ||
465 | // If unchanged, then we saw no successful obligations, which means | |
466 | // there is no point in further iteration. This is based on the | |
467 | // assumption that when trait matching returns `Error` or | |
468 | // `Unchanged`, those results do not affect environmental inference | |
469 | // state. (Note that this will occur if we invoke | |
470 | // `process_obligations` with no pending obligations.) | |
471 | if !has_changed { | |
472 | break; | |
7453a54e | 473 | } |
7453a54e | 474 | |
29967ef6 XL |
475 | self.mark_successes(); |
476 | self.process_cycles(processor); | |
477 | self.compress(|obl| outcome.record_completed(obl)); | |
c30ab7b3 SL |
478 | } |
479 | ||
29967ef6 | 480 | outcome |
7453a54e SL |
481 | } |
482 | ||
483 | /// Returns a vector of obligations for `p` and all of its | |
484 | /// ancestors, putting them into the error state in the process. | |
e1599b0c | 485 | fn error_at(&self, mut index: usize) -> Vec<O> { |
e74abb32 | 486 | let mut error_stack: Vec<usize> = vec![]; |
7453a54e | 487 | let mut trace = vec![]; |
a7813a04 | 488 | |
7453a54e | 489 | loop { |
e1599b0c XL |
490 | let node = &self.nodes[index]; |
491 | node.state.set(NodeState::Error); | |
492 | trace.push(node.obligation.clone()); | |
493 | if node.has_parent { | |
494 | // The first dependent is the parent, which is treated | |
495 | // specially. | |
496 | error_stack.extend(node.dependents.iter().skip(1)); | |
497 | index = node.dependents[0]; | |
498 | } else { | |
499 | // No parent; treat all dependents non-specially. | |
500 | error_stack.extend(node.dependents.iter()); | |
501 | break; | |
a7813a04 XL |
502 | } |
503 | } | |
504 | ||
e1599b0c XL |
505 | while let Some(index) = error_stack.pop() { |
506 | let node = &self.nodes[index]; | |
e74abb32 XL |
507 | if node.state.get() != NodeState::Error { |
508 | node.state.set(NodeState::Error); | |
509 | error_stack.extend(node.dependents.iter()); | |
a7813a04 | 510 | } |
a7813a04 XL |
511 | } |
512 | ||
a7813a04 XL |
513 | trace |
514 | } | |
515 | ||
60c5eb7d XL |
516 | /// Mark all `Waiting` nodes as `Success`, except those that depend on a |
517 | /// pending node. | |
518 | fn mark_successes(&self) { | |
519 | // Convert all `Waiting` nodes to `Success`. | |
520 | for node in &self.nodes { | |
521 | if node.state.get() == NodeState::Waiting { | |
522 | node.state.set(NodeState::Success); | |
523 | } | |
524 | } | |
525 | ||
526 | // Convert `Success` nodes that depend on a pending node back to | |
527 | // `Waiting`. | |
528 | for node in &self.nodes { | |
529 | if node.state.get() == NodeState::Pending { | |
530 | // This call site is hot. | |
531 | self.inlined_mark_dependents_as_waiting(node); | |
532 | } | |
533 | } | |
534 | } | |
535 | ||
e1599b0c XL |
536 | // This always-inlined function is for the hot call site. |
537 | #[inline(always)] | |
60c5eb7d | 538 | fn inlined_mark_dependents_as_waiting(&self, node: &Node<O>) { |
e1599b0c | 539 | for &index in node.dependents.iter() { |
e74abb32 | 540 | let node = &self.nodes[index]; |
60c5eb7d XL |
541 | let state = node.state.get(); |
542 | if state == NodeState::Success { | |
60c5eb7d XL |
543 | // This call site is cold. |
544 | self.uninlined_mark_dependents_as_waiting(node); | |
545 | } else { | |
546 | debug_assert!(state == NodeState::Waiting || state == NodeState::Error) | |
e74abb32 | 547 | } |
c30ab7b3 SL |
548 | } |
549 | } | |
550 | ||
e1599b0c XL |
551 | // This never-inlined function is for the cold call site. |
552 | #[inline(never)] | |
60c5eb7d | 553 | fn uninlined_mark_dependents_as_waiting(&self, node: &Node<O>) { |
29967ef6 XL |
554 | // Mark node Waiting in the cold uninlined code instead of the hot inlined |
555 | node.state.set(NodeState::Waiting); | |
60c5eb7d | 556 | self.inlined_mark_dependents_as_waiting(node) |
e1599b0c XL |
557 | } |
558 | ||
60c5eb7d XL |
559 | /// Report cycles between all `Success` nodes, and convert all `Success` |
560 | /// nodes to `Done`. This must be called after `mark_successes`. | |
29967ef6 | 561 | fn process_cycles<P>(&mut self, processor: &mut P) |
60c5eb7d XL |
562 | where |
563 | P: ObligationProcessor<Obligation = O>, | |
564 | { | |
29967ef6 | 565 | let mut stack = std::mem::take(&mut self.reused_node_vec); |
60c5eb7d XL |
566 | for (index, node) in self.nodes.iter().enumerate() { |
567 | // For some benchmarks this state test is extremely hot. It's a win | |
568 | // to handle the no-op cases immediately to avoid the cost of the | |
569 | // function call. | |
570 | if node.state.get() == NodeState::Success { | |
571 | self.find_cycles_from_node(&mut stack, processor, index); | |
a7813a04 XL |
572 | } |
573 | } | |
574 | ||
60c5eb7d | 575 | debug_assert!(stack.is_empty()); |
29967ef6 | 576 | self.reused_node_vec = stack; |
60c5eb7d XL |
577 | } |
578 | ||
579 | fn find_cycles_from_node<P>(&self, stack: &mut Vec<usize>, processor: &mut P, index: usize) | |
580 | where | |
581 | P: ObligationProcessor<Obligation = O>, | |
582 | { | |
583 | let node = &self.nodes[index]; | |
584 | if node.state.get() == NodeState::Success { | |
585 | match stack.iter().rposition(|&n| n == index) { | |
586 | None => { | |
587 | stack.push(index); | |
588 | for &dep_index in node.dependents.iter() { | |
589 | self.find_cycles_from_node(stack, processor, dep_index); | |
590 | } | |
591 | stack.pop(); | |
592 | node.state.set(NodeState::Done); | |
593 | } | |
594 | Some(rpos) => { | |
595 | // Cycle detected. | |
596 | processor.process_backedge( | |
17df50a5 | 597 | stack[rpos..].iter().map(|&i| &self.nodes[i].obligation), |
60c5eb7d XL |
598 | PhantomData, |
599 | ); | |
600 | } | |
7453a54e SL |
601 | } |
602 | } | |
603 | } | |
604 | ||
e74abb32 | 605 | /// Compresses the vector, removing all popped nodes. This adjusts the |
60c5eb7d XL |
606 | /// indices and hence invalidates any outstanding indices. `process_cycles` |
607 | /// must be run beforehand to remove any cycles on `Success` nodes. | |
a7813a04 | 608 | #[inline(never)] |
29967ef6 | 609 | fn compress(&mut self, mut outcome_cb: impl FnMut(&O)) { |
e74abb32 | 610 | let orig_nodes_len = self.nodes.len(); |
29967ef6 | 611 | let mut node_rewrites: Vec<_> = std::mem::take(&mut self.reused_node_vec); |
3c0e092e | 612 | debug_assert!(node_rewrites.is_empty()); |
e74abb32 | 613 | node_rewrites.extend(0..orig_nodes_len); |
a7813a04 | 614 | let mut dead_nodes = 0; |
7453a54e | 615 | |
60c5eb7d XL |
616 | // Move removable nodes to the end, preserving the order of the |
617 | // remaining nodes. | |
a7813a04 XL |
618 | // |
619 | // LOOP INVARIANT: | |
e1599b0c XL |
620 | // self.nodes[0..index - dead_nodes] are the first remaining nodes |
621 | // self.nodes[index - dead_nodes..index] are all dead | |
622 | // self.nodes[index..] are unchanged | |
3c0e092e | 623 | for index in 0..orig_nodes_len { |
e1599b0c XL |
624 | let node = &self.nodes[index]; |
625 | match node.state.get() { | |
c30ab7b3 SL |
626 | NodeState::Pending | NodeState::Waiting => { |
627 | if dead_nodes > 0 { | |
e1599b0c | 628 | self.nodes.swap(index, index - dead_nodes); |
3c0e092e | 629 | node_rewrites[index] -= dead_nodes; |
c30ab7b3 SL |
630 | } |
631 | } | |
a7813a04 | 632 | NodeState::Done => { |
923072b8 | 633 | // The removal lookup might fail because the contents of |
e74abb32 | 634 | // `self.active_cache` are not guaranteed to match those of |
e1599b0c XL |
635 | // `self.nodes`. See the comment in `process_obligation` |
636 | // for more details. | |
923072b8 FG |
637 | let cache_key = node.obligation.as_cache_key(); |
638 | self.active_cache.remove(&cache_key); | |
639 | self.done_cache.insert(cache_key); | |
640 | ||
29967ef6 XL |
641 | // Extract the success stories. |
642 | outcome_cb(&node.obligation); | |
3c0e092e | 643 | node_rewrites[index] = orig_nodes_len; |
c30ab7b3 | 644 | dead_nodes += 1; |
a7813a04 XL |
645 | } |
646 | NodeState::Error => { | |
647 | // We *intentionally* remove the node from the cache at this point. Otherwise | |
648 | // tests must come up with a different type on every type error they | |
649 | // check against. | |
74b04a01 | 650 | self.active_cache.remove(&node.obligation.as_cache_key()); |
e1599b0c | 651 | self.insert_into_error_cache(index); |
3c0e092e | 652 | node_rewrites[index] = orig_nodes_len; |
e74abb32 | 653 | dead_nodes += 1; |
a7813a04 | 654 | } |
60c5eb7d | 655 | NodeState::Success => unreachable!(), |
7453a54e SL |
656 | } |
657 | } | |
658 | ||
e74abb32 XL |
659 | if dead_nodes > 0 { |
660 | // Remove the dead nodes and rewrite indices. | |
661 | self.nodes.truncate(orig_nodes_len - dead_nodes); | |
662 | self.apply_rewrites(&node_rewrites); | |
7453a54e SL |
663 | } |
664 | ||
a7813a04 | 665 | node_rewrites.truncate(0); |
29967ef6 | 666 | self.reused_node_vec = node_rewrites; |
a7813a04 XL |
667 | } |
668 | ||
136023e0 | 669 | #[inline(never)] |
a7813a04 | 670 | fn apply_rewrites(&mut self, node_rewrites: &[usize]) { |
e74abb32 | 671 | let orig_nodes_len = node_rewrites.len(); |
7453a54e | 672 | |
7453a54e | 673 | for node in &mut self.nodes { |
e74abb32 | 674 | let mut i = 0; |
f035d41b XL |
675 | while let Some(dependent) = node.dependents.get_mut(i) { |
676 | let new_index = node_rewrites[*dependent]; | |
e74abb32 XL |
677 | if new_index >= orig_nodes_len { |
678 | node.dependents.swap_remove(i); | |
679 | if i == 0 && node.has_parent { | |
e1599b0c XL |
680 | // We just removed the parent. |
681 | node.has_parent = false; | |
682 | } | |
a7813a04 | 683 | } else { |
f035d41b | 684 | *dependent = new_index; |
e74abb32 | 685 | i += 1; |
a7813a04 XL |
686 | } |
687 | } | |
7453a54e SL |
688 | } |
689 | ||
e74abb32 | 690 | // This updating of `self.active_cache` is necessary because the |
e1599b0c | 691 | // removal of nodes within `compress` can fail. See above. |
e74abb32 | 692 | self.active_cache.retain(|_predicate, index| { |
e1599b0c | 693 | let new_index = node_rewrites[*index]; |
e74abb32 | 694 | if new_index >= orig_nodes_len { |
e1599b0c | 695 | false |
a7813a04 | 696 | } else { |
e1599b0c XL |
697 | *index = new_index; |
698 | true | |
a7813a04 | 699 | } |
e1599b0c | 700 | }); |
7453a54e | 701 | } |
7453a54e | 702 | } |