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