1 //! The `ObligationForest` is a utility data structure used in trait
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
9 //! `ObligationForest` supports two main public operations (there are a
10 //! few others not discussed here):
12 //! 1. Add a new root obligations (`register_obligation`).
13 //! 2. Process the pending obligations (`process_obligations`).
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`
23 //! that it is given and return a `ProcessResult`:
25 //! - `Unchanged` -> ambiguous result. Obligation was neither a success
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.
29 //! - `Changed(C)` - the obligation was *shallowly successful*. The
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`.
37 //! - `Error(E)` -> obligation failed with error `E`. We will collect this
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.
44 //! When the call to `process_obligations` completes, you get back an `Outcome`,
45 //! which includes three bits of information:
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
50 //! `process_obligations` returns `Changed(C)` for some obligation `O`,
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
57 //! *shallowly successful* (that is, no callback returned `Changed(_)`).
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.
64 //! ### Implementation details
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
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.
75 use crate::fx
::{FxHashMap, FxHashSet}
;
77 use std
::cell
::{Cell, RefCell}
;
78 use std
::collections
::hash_map
::Entry
;
81 use std
::marker
::PhantomData
;
88 pub trait ForestObligation
: Clone
+ Debug
{
89 type Predicate
: Clone
+ hash
::Hash
+ Eq
+ Debug
;
91 fn as_predicate(&self) -> &Self::Predicate
;
94 pub trait ObligationProcessor
{
95 type Obligation
: ForestObligation
;
98 fn process_obligation(
100 obligation
: &mut Self::Obligation
,
101 ) -> ProcessResult
<Self::Obligation
, Self::Error
>;
103 /// As we do the cycle check, we invoke this callback when we
104 /// encounter an actual cycle. `cycle` is an iterator that starts
105 /// at the start of the cycle in the stack and walks **toward the
108 /// In other words, if we had O1 which required O2 which required
109 /// O3 which required O1, we would give an iterator yielding O1,
110 /// O2, O3 (O1 is not yielded twice).
111 fn process_backedge
<'c
, I
>(&mut self, cycle
: I
, _marker
: PhantomData
<&'c
Self::Obligation
>)
113 I
: Clone
+ Iterator
<Item
= &'c
Self::Obligation
>;
116 /// The result type used by `process_obligation`.
118 pub enum ProcessResult
<O
, E
> {
124 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
125 struct ObligationTreeId(usize);
127 type ObligationTreeIdGenerator
=
128 ::std
::iter
::Map
<::std
::ops
::RangeFrom
<usize>, fn(usize) -> ObligationTreeId
>;
130 pub struct ObligationForest
<O
: ForestObligation
> {
131 /// The list of obligations. In between calls to `process_obligations`,
132 /// this list only contains nodes in the `Pending` or `Waiting` state.
134 /// `usize` indices are used here and throughout this module, rather than
135 /// `rustc_index::newtype_index!` indices, because this code is hot enough
136 /// that the `u32`-to-`usize` conversions that would be required are
137 /// significant, and space considerations are not important.
140 /// A cache of predicates that have been successfully completed.
141 done_cache
: FxHashSet
<O
::Predicate
>,
143 /// A cache of the nodes in `nodes`, indexed by predicate. Unfortunately,
144 /// its contents are not guaranteed to match those of `nodes`. See the
145 /// comments in `process_obligation` for details.
146 active_cache
: FxHashMap
<O
::Predicate
, usize>,
148 /// A vector reused in compress(), to avoid allocating new vectors.
149 node_rewrites
: RefCell
<Vec
<usize>>,
151 obligation_tree_id_generator
: ObligationTreeIdGenerator
,
153 /// Per tree error cache. This is used to deduplicate errors,
154 /// which is necessary to avoid trait resolution overflow in
157 /// See [this][details] for details.
159 /// [details]: https://github.com/rust-lang/rust/pull/53255#issuecomment-421184780
160 error_cache
: FxHashMap
<ObligationTreeId
, FxHashSet
<O
::Predicate
>>,
166 state
: Cell
<NodeState
>,
168 /// Obligations that depend on this obligation for their completion. They
169 /// must all be in a non-pending state.
170 dependents
: Vec
<usize>,
172 /// If true, dependents[0] points to a "parent" node, which requires
173 /// special treatment upon error but is otherwise treated the same.
174 /// (It would be more idiomatic to store the parent node in a separate
175 /// `Option<usize>` field, but that slows down the common case of
176 /// iterating over the parent and other descendants together.)
179 /// Identifier of the obligation tree to which this node belongs.
180 obligation_tree_id
: ObligationTreeId
,
184 fn new(parent
: Option
<usize>, obligation
: O
, obligation_tree_id
: ObligationTreeId
) -> Node
<O
> {
187 state
: Cell
::new(NodeState
::Pending
),
188 dependents
: if let Some(parent_index
) = parent { vec![parent_index] }
else { vec![] }
,
189 has_parent
: parent
.is_some(),
195 /// The state of one node in some tree within the forest. This represents the
196 /// current state of processing for the obligation (of type `O`) associated
199 /// The non-`Error` state transitions are as follows.
203 /// | register_obligation_at() (called by process_obligations() and
204 /// v from outside the crate)
207 /// | process_obligations()
211 /// | | mark_successes()
215 /// | process_cycles()
223 /// The `Error` state can be introduced in several places, via `error_at()`.
225 /// Outside of `ObligationForest` methods, nodes should be either `Pending` or
227 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
229 /// This obligation has not yet been selected successfully. Cannot have
233 /// This obligation was selected successfully, but may or may not have
237 /// This obligation was selected successfully, but it has a pending
241 /// This obligation, along with its subobligations, are complete, and will
242 /// be removed in the next collection.
245 /// This obligation was resolved to an error. It will be removed by the
246 /// next compression step.
251 pub struct Outcome
<O
, E
> {
252 /// Obligations that were completely evaluated, including all
253 /// (transitive) subobligations. Only computed if requested.
254 pub completed
: Option
<Vec
<O
>>,
256 /// Backtrace of obligations that were found to be in error.
257 pub errors
: Vec
<Error
<O
, E
>>,
259 /// If true, then we saw no successful obligations, which means
260 /// there is no point in further iteration. This is based on the
261 /// assumption that when trait matching returns `Error` or
262 /// `Unchanged`, those results do not affect environmental
263 /// inference state. (Note that if we invoke `process_obligations`
264 /// with no pending obligations, stalled will be true.)
268 /// Should `process_obligations` compute the `Outcome::completed` field of its
271 pub enum DoCompleted
{
276 #[derive(Debug, PartialEq, Eq)]
277 pub struct Error
<O
, E
> {
279 pub backtrace
: Vec
<O
>,
282 impl<O
: ForestObligation
> ObligationForest
<O
> {
283 pub fn new() -> ObligationForest
<O
> {
286 done_cache
: Default
::default(),
287 active_cache
: Default
::default(),
288 node_rewrites
: RefCell
::new(vec
![]),
289 obligation_tree_id_generator
: (0..).map(ObligationTreeId
),
290 error_cache
: Default
::default(),
294 /// Returns the total number of nodes in the forest that have not
295 /// yet been fully resolved.
296 pub fn len(&self) -> usize {
300 /// Registers an obligation.
301 pub fn register_obligation(&mut self, obligation
: O
) {
302 // Ignore errors here - there is no guarantee of success.
303 let _
= self.register_obligation_at(obligation
, None
);
306 // Returns Err(()) if we already know this obligation failed.
307 fn register_obligation_at(&mut self, obligation
: O
, parent
: Option
<usize>) -> Result
<(), ()> {
308 if self.done_cache
.contains(obligation
.as_predicate()) {
312 match self.active_cache
.entry(obligation
.as_predicate().clone()) {
313 Entry
::Occupied(o
) => {
314 let node
= &mut self.nodes
[*o
.get()];
315 if let Some(parent_index
) = parent
{
316 // If the node is already in `active_cache`, it has already
317 // had its chance to be marked with a parent. So if it's
318 // not already present, just dump `parent` into the
319 // dependents as a non-parent.
320 if !node
.dependents
.contains(&parent_index
) {
321 node
.dependents
.push(parent_index
);
324 if let NodeState
::Error
= node
.state
.get() { Err(()) }
else { Ok(()) }
326 Entry
::Vacant(v
) => {
327 let obligation_tree_id
= match parent
{
328 Some(parent_index
) => self.nodes
[parent_index
].obligation_tree_id
,
329 None
=> self.obligation_tree_id_generator
.next().unwrap(),
332 let already_failed
= parent
.is_some()
335 .get(&obligation_tree_id
)
336 .map(|errors
| errors
.contains(obligation
.as_predicate()))
342 let new_index
= self.nodes
.len();
344 self.nodes
.push(Node
::new(parent
, obligation
, obligation_tree_id
));
351 /// Converts all remaining obligations to the given error.
352 pub fn to_errors
<E
: Clone
>(&mut self, error
: E
) -> Vec
<Error
<O
, E
>> {
357 .filter(|(_index
, node
)| node
.state
.get() == NodeState
::Pending
)
358 .map(|(index
, _node
)| Error { error: error.clone(), backtrace: self.error_at(index) }
)
361 let successful_obligations
= self.compress(DoCompleted
::Yes
);
362 assert
!(successful_obligations
.unwrap().is_empty());
366 /// Returns the set of obligations that are in a pending state.
367 pub fn map_pending_obligations
<P
, F
>(&self, f
: F
) -> Vec
<P
>
373 .filter(|node
| node
.state
.get() == NodeState
::Pending
)
374 .map(|node
| f(&node
.obligation
))
378 fn insert_into_error_cache(&mut self, index
: usize) {
379 let node
= &self.nodes
[index
];
381 .entry(node
.obligation_tree_id
)
383 .insert(node
.obligation
.as_predicate().clone());
386 /// Performs a pass through the obligation list. This must
387 /// be called in a loop until `outcome.stalled` is false.
389 /// This _cannot_ be unrolled (presently, at least).
390 pub fn process_obligations
<P
>(
393 do_completed
: DoCompleted
,
394 ) -> Outcome
<O
, P
::Error
>
396 P
: ObligationProcessor
<Obligation
= O
>,
398 let mut errors
= vec
![];
399 let mut stalled
= true;
401 // Note that the loop body can append new nodes, and those new nodes
402 // will then be processed by subsequent iterations of the loop.
404 // We can't use an iterator for the loop because `self.nodes` is
405 // appended to and the borrow checker would complain. We also can't use
406 // `for index in 0..self.nodes.len() { ... }` because the range would
407 // be computed with the initial length, and we would miss the appended
408 // nodes. Therefore we use a `while` loop.
410 while index
< self.nodes
.len() {
411 let node
= &mut self.nodes
[index
];
413 // `processor.process_obligation` can modify the predicate within
414 // `node.obligation`, and that predicate is the key used for
415 // `self.active_cache`. This means that `self.active_cache` can get
416 // out of sync with `nodes`. It's not very common, but it does
417 // happen, and code in `compress` has to allow for it.
418 if node
.state
.get() != NodeState
::Pending
{
423 match processor
.process_obligation(&mut node
.obligation
) {
424 ProcessResult
::Unchanged
=> {
425 // No change in state.
427 ProcessResult
::Changed(children
) => {
428 // We are not (yet) stalled.
430 node
.state
.set(NodeState
::Success
);
432 for child
in children
{
433 let st
= self.register_obligation_at(child
, Some(index
));
434 if let Err(()) = st
{
435 // Error already reported - propagate it
437 self.error_at(index
);
441 ProcessResult
::Error(err
) => {
443 errors
.push(Error { error: err, backtrace: self.error_at(index) }
);
450 // There's no need to perform marking, cycle processing and compression when nothing
453 completed
: if do_completed
== DoCompleted
::Yes { Some(vec![]) }
else { None }
,
459 self.mark_successes();
460 self.process_cycles(processor
);
461 let completed
= self.compress(do_completed
);
463 Outcome { completed, errors, stalled }
466 /// Returns a vector of obligations for `p` and all of its
467 /// ancestors, putting them into the error state in the process.
468 fn error_at(&self, mut index
: usize) -> Vec
<O
> {
469 let mut error_stack
: Vec
<usize> = vec
![];
470 let mut trace
= vec
![];
473 let node
= &self.nodes
[index
];
474 node
.state
.set(NodeState
::Error
);
475 trace
.push(node
.obligation
.clone());
477 // The first dependent is the parent, which is treated
479 error_stack
.extend(node
.dependents
.iter().skip(1));
480 index
= node
.dependents
[0];
482 // No parent; treat all dependents non-specially.
483 error_stack
.extend(node
.dependents
.iter());
488 while let Some(index
) = error_stack
.pop() {
489 let node
= &self.nodes
[index
];
490 if node
.state
.get() != NodeState
::Error
{
491 node
.state
.set(NodeState
::Error
);
492 error_stack
.extend(node
.dependents
.iter());
499 /// Mark all `Waiting` nodes as `Success`, except those that depend on a
501 fn mark_successes(&self) {
502 // Convert all `Waiting` nodes to `Success`.
503 for node
in &self.nodes
{
504 if node
.state
.get() == NodeState
::Waiting
{
505 node
.state
.set(NodeState
::Success
);
509 // Convert `Success` nodes that depend on a pending node back to
511 for node
in &self.nodes
{
512 if node
.state
.get() == NodeState
::Pending
{
513 // This call site is hot.
514 self.inlined_mark_dependents_as_waiting(node
);
519 // This always-inlined function is for the hot call site.
521 fn inlined_mark_dependents_as_waiting(&self, node
: &Node
<O
>) {
522 for &index
in node
.dependents
.iter() {
523 let node
= &self.nodes
[index
];
524 let state
= node
.state
.get();
525 if state
== NodeState
::Success
{
526 node
.state
.set(NodeState
::Waiting
);
527 // This call site is cold.
528 self.uninlined_mark_dependents_as_waiting(node
);
530 debug_assert
!(state
== NodeState
::Waiting
|| state
== NodeState
::Error
)
535 // This never-inlined function is for the cold call site.
537 fn uninlined_mark_dependents_as_waiting(&self, node
: &Node
<O
>) {
538 self.inlined_mark_dependents_as_waiting(node
)
541 /// Report cycles between all `Success` nodes, and convert all `Success`
542 /// nodes to `Done`. This must be called after `mark_successes`.
543 fn process_cycles
<P
>(&self, processor
: &mut P
)
545 P
: ObligationProcessor
<Obligation
= O
>,
547 let mut stack
= vec
![];
549 for (index
, node
) in self.nodes
.iter().enumerate() {
550 // For some benchmarks this state test is extremely hot. It's a win
551 // to handle the no-op cases immediately to avoid the cost of the
553 if node
.state
.get() == NodeState
::Success
{
554 self.find_cycles_from_node(&mut stack
, processor
, index
);
558 debug_assert
!(stack
.is_empty());
561 fn find_cycles_from_node
<P
>(&self, stack
: &mut Vec
<usize>, processor
: &mut P
, index
: usize)
563 P
: ObligationProcessor
<Obligation
= O
>,
565 let node
= &self.nodes
[index
];
566 if node
.state
.get() == NodeState
::Success
{
567 match stack
.iter().rposition(|&n
| n
== index
) {
570 for &dep_index
in node
.dependents
.iter() {
571 self.find_cycles_from_node(stack
, processor
, dep_index
);
574 node
.state
.set(NodeState
::Done
);
578 processor
.process_backedge(
579 stack
[rpos
..].iter().map(GetObligation(&self.nodes
)),
587 /// Compresses the vector, removing all popped nodes. This adjusts the
588 /// indices and hence invalidates any outstanding indices. `process_cycles`
589 /// must be run beforehand to remove any cycles on `Success` nodes.
591 fn compress(&mut self, do_completed
: DoCompleted
) -> Option
<Vec
<O
>> {
592 let orig_nodes_len
= self.nodes
.len();
593 let mut node_rewrites
: Vec
<_
> = self.node_rewrites
.replace(vec
![]);
594 debug_assert
!(node_rewrites
.is_empty());
595 node_rewrites
.extend(0..orig_nodes_len
);
596 let mut dead_nodes
= 0;
597 let mut removed_done_obligations
: Vec
<O
> = vec
![];
599 // Move removable nodes to the end, preserving the order of the
603 // self.nodes[0..index - dead_nodes] are the first remaining nodes
604 // self.nodes[index - dead_nodes..index] are all dead
605 // self.nodes[index..] are unchanged
606 for index
in 0..orig_nodes_len
{
607 let node
= &self.nodes
[index
];
608 match node
.state
.get() {
609 NodeState
::Pending
| NodeState
::Waiting
=> {
611 self.nodes
.swap(index
, index
- dead_nodes
);
612 node_rewrites
[index
] -= dead_nodes
;
616 // This lookup can fail because the contents of
617 // `self.active_cache` are not guaranteed to match those of
618 // `self.nodes`. See the comment in `process_obligation`
620 if let Some((predicate
, _
)) =
621 self.active_cache
.remove_entry(node
.obligation
.as_predicate())
623 self.done_cache
.insert(predicate
);
625 self.done_cache
.insert(node
.obligation
.as_predicate().clone());
627 if do_completed
== DoCompleted
::Yes
{
628 // Extract the success stories.
629 removed_done_obligations
.push(node
.obligation
.clone());
631 node_rewrites
[index
] = orig_nodes_len
;
634 NodeState
::Error
=> {
635 // We *intentionally* remove the node from the cache at this point. Otherwise
636 // tests must come up with a different type on every type error they
638 self.active_cache
.remove(node
.obligation
.as_predicate());
639 self.insert_into_error_cache(index
);
640 node_rewrites
[index
] = orig_nodes_len
;
643 NodeState
::Success
=> unreachable
!(),
648 // Remove the dead nodes and rewrite indices.
649 self.nodes
.truncate(orig_nodes_len
- dead_nodes
);
650 self.apply_rewrites(&node_rewrites
);
653 node_rewrites
.truncate(0);
654 self.node_rewrites
.replace(node_rewrites
);
656 if do_completed
== DoCompleted
::Yes { Some(removed_done_obligations) }
else { None }
659 fn apply_rewrites(&mut self, node_rewrites
: &[usize]) {
660 let orig_nodes_len
= node_rewrites
.len();
662 for node
in &mut self.nodes
{
664 while i
< node
.dependents
.len() {
665 let new_index
= node_rewrites
[node
.dependents
[i
]];
666 if new_index
>= orig_nodes_len
{
667 node
.dependents
.swap_remove(i
);
668 if i
== 0 && node
.has_parent
{
669 // We just removed the parent.
670 node
.has_parent
= false;
673 node
.dependents
[i
] = new_index
;
679 // This updating of `self.active_cache` is necessary because the
680 // removal of nodes within `compress` can fail. See above.
681 self.active_cache
.retain(|_predicate
, index
| {
682 let new_index
= node_rewrites
[*index
];
683 if new_index
>= orig_nodes_len
{
693 // I need a Clone closure.
695 struct GetObligation
<'a
, O
>(&'a
[Node
<O
>]);
697 impl<'a
, 'b
, O
> FnOnce
<(&'b
usize,)> for GetObligation
<'a
, O
> {
699 extern "rust-call" fn call_once(self, args
: (&'b
usize,)) -> &'a O
{
700 &self.0[*args
.0].obligation
704 impl<'a
, 'b
, O
> FnMut
<(&'b
usize,)> for GetObligation
<'a
, O
> {
705 extern "rust-call" fn call_mut(&mut self, args
: (&'b
usize,)) -> &'a O
{
706 &self.0[*args
.0].obligation