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