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(&mut self,
99 obligation: &mut Self::Obligation)
100 -> ProcessResult<Self::Obligation, Self::Error>;
102 /// As we do the cycle check, we invoke this callback when we
103 /// encounter an actual cycle. `cycle` is an iterator that starts
104 /// at the start of the cycle in the stack and walks **toward the
107 /// In other words, if we had O1 which required O2 which required
108 /// O3 which required O1, we would give an iterator yielding O1,
109 /// O2, O3 (O1 is not yielded twice).
110 fn process_backedge<'c, I>(&mut self,
112 _marker: PhantomData<&'c Self::Obligation>)
113 where 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
132 /// `process_obligations`, this list only contains nodes in the
133 /// `Pending` or `Success` state (with a non-zero number of
134 /// incomplete children). During processing, some of those nodes
135 /// may be changed to the error state, or we may find that they
136 /// are completed (That is, `num_incomplete_children` drops to 0).
137 /// At the end of processing, those nodes will be removed by a
138 /// call to `compress`.
140 /// `usize` indices are used here and throughout this module, rather than
141 /// `rustc_index::newtype_index!` indices, because this code is hot enough that the
142 /// `u32`-to-`usize` conversions that would be required are significant,
143 /// and space considerations are not important.
146 /// A cache of predicates that have been successfully completed.
147 done_cache: FxHashSet<O::Predicate>,
149 /// A cache of the nodes in `nodes`, indexed by predicate. Unfortunately,
150 /// its contents are not guaranteed to match those of `nodes`. See the
151 /// comments in `process_obligation` for details.
152 active_cache: FxHashMap<O::Predicate, usize>,
154 /// A vector reused in compress(), to avoid allocating new vectors.
155 node_rewrites: RefCell<Vec<usize>>,
157 obligation_tree_id_generator: ObligationTreeIdGenerator,
159 /// Per tree error cache. This is used to deduplicate errors,
160 /// which is necessary to avoid trait resolution overflow in
163 /// See [this][details] for details.
165 /// [details]: https://github.com/rust-lang/rust/pull/53255#issuecomment-421184780
166 error_cache: FxHashMap<ObligationTreeId, FxHashSet<O::Predicate>>,
172 state: Cell<NodeState>,
174 /// Obligations that depend on this obligation for their completion. They
175 /// must all be in a non-pending state.
176 dependents: Vec<usize>,
178 /// If true, dependents[0] points to a "parent" node, which requires
179 /// special treatment upon error but is otherwise treated the same.
180 /// (It would be more idiomatic to store the parent node in a separate
181 /// `Option<usize>` field, but that slows down the common case of
182 /// iterating over the parent and other descendants together.)
185 /// Identifier of the obligation tree to which this node belongs.
186 obligation_tree_id: ObligationTreeId,
191 parent: Option<usize>,
193 obligation_tree_id: ObligationTreeId
197 state: Cell::new(NodeState::Pending),
199 if let Some(parent_index) = parent {
204 has_parent: parent.is_some(),
210 /// The state of one node in some tree within the forest. This
211 /// represents the current state of processing for the obligation (of
212 /// type `O`) associated with this node.
214 /// Outside of ObligationForest methods, nodes should be either Pending
216 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
218 /// Obligations for which selection had not yet returned a
219 /// non-ambiguous result.
222 /// This obligation was selected successfully, but may or
223 /// may not have subobligations.
226 /// This obligation was selected successfully, but it has
227 /// a pending subobligation.
230 /// This obligation, along with its subobligations, are complete,
231 /// and will be removed in the next collection.
234 /// This obligation was resolved to an error. Error nodes are
235 /// removed from the vector by the compression step.
240 pub struct Outcome<O, E> {
241 /// Obligations that were completely evaluated, including all
242 /// (transitive) subobligations. Only computed if requested.
243 pub completed: Option<Vec<O>>,
245 /// Backtrace of obligations that were found to be in error.
246 pub errors: Vec<Error<O, E>>,
248 /// If true, then we saw no successful obligations, which means
249 /// there is no point in further iteration. This is based on the
250 /// assumption that when trait matching returns `Error` or
251 /// `Unchanged`, those results do not affect environmental
252 /// inference state. (Note that if we invoke `process_obligations`
253 /// with no pending obligations, stalled will be true.)
257 /// Should `process_obligations` compute the `Outcome::completed` field of its
260 pub enum DoCompleted {
265 #[derive(Debug, PartialEq, Eq)]
266 pub struct Error<O, E> {
268 pub backtrace: Vec<O>,
271 impl<O: ForestObligation> ObligationForest<O> {
272 pub fn new() -> ObligationForest<O> {
275 done_cache: Default::default(),
276 active_cache: Default::default(),
277 node_rewrites: RefCell::new(vec![]),
278 obligation_tree_id_generator: (0..).map(ObligationTreeId),
279 error_cache: Default::default(),
283 /// Returns the total number of nodes in the forest that have not
284 /// yet been fully resolved.
285 pub fn len(&self) -> usize {
289 /// Registers an obligation.
290 pub fn register_obligation(&mut self, obligation: O) {
291 // Ignore errors here - there is no guarantee of success.
292 let _ = self.register_obligation_at(obligation, None);
295 // Returns Err(()) if we already know this obligation failed.
296 fn register_obligation_at(&mut self, obligation: O, parent: Option<usize>) -> Result<(), ()> {
297 if self.done_cache.contains(obligation.as_predicate()) {
301 match self.active_cache.entry(obligation.as_predicate().clone()) {
302 Entry::Occupied(o) => {
303 let index = *o.get();
304 debug!("register_obligation_at({:?}, {:?}) - duplicate of {:?}!",
305 obligation, parent, index);
306 let node = &mut self.nodes[index];
307 if let Some(parent_index) = parent {
308 // If the node is already in `active_cache`, it has already
309 // had its chance to be marked with a parent. So if it's
310 // not already present, just dump `parent` into the
311 // dependents as a non-parent.
312 if !node.dependents.contains(&parent_index) {
313 node.dependents.push(parent_index);
316 if let NodeState::Error = node.state.get() {
322 Entry::Vacant(v) => {
323 debug!("register_obligation_at({:?}, {:?}) - ok, new index is {}",
324 obligation, parent, self.nodes.len());
326 let obligation_tree_id = match parent {
327 Some(parent_index) => self.nodes[parent_index].obligation_tree_id,
328 None => self.obligation_tree_id_generator.next().unwrap(),
334 .get(&obligation_tree_id)
335 .map(|errors| errors.contains(obligation.as_predicate()))
341 let new_index = self.nodes.len();
343 self.nodes.push(Node::new(parent, obligation, obligation_tree_id));
350 /// Converts all remaining obligations to the given error.
351 pub fn to_errors<E: Clone>(&mut self, error: E) -> Vec<Error<O, E>> {
352 let errors = self.nodes.iter().enumerate()
353 .filter(|(_index, node)| node.state.get() == NodeState::Pending)
354 .map(|(index, _node)| {
356 error: error.clone(),
357 backtrace: self.error_at(index),
362 let successful_obligations = self.compress(DoCompleted::Yes);
363 assert!(successful_obligations.unwrap().is_empty());
367 /// Returns the set of obligations that are in a pending state.
368 pub fn map_pending_obligations<P, F>(&self, f: F) -> Vec<P>
372 .filter(|node| node.state.get() == NodeState::Pending)
373 .map(|node| f(&node.obligation))
377 fn insert_into_error_cache(&mut self, index: usize) {
378 let node = &self.nodes[index];
380 .entry(node.obligation_tree_id)
382 .insert(node.obligation.as_predicate().clone());
385 /// Performs a pass through the obligation list. This must
386 /// be called in a loop until `outcome.stalled` is false.
388 /// This _cannot_ be unrolled (presently, at least).
389 pub fn process_obligations<P>(&mut self, processor: &mut P, do_completed: DoCompleted)
390 -> Outcome<O, P::Error>
391 where P: ObligationProcessor<Obligation=O>
393 debug!("process_obligations(len={})", self.nodes.len());
395 let mut errors = vec![];
396 let mut stalled = true;
398 for index in 0..self.nodes.len() {
399 let node = &mut self.nodes[index];
401 debug!("process_obligations: node {} == {:?}", index, node);
403 // `processor.process_obligation` can modify the predicate within
404 // `node.obligation`, and that predicate is the key used for
405 // `self.active_cache`. This means that `self.active_cache` can get
406 // out of sync with `nodes`. It's not very common, but it does
407 // happen, and code in `compress` has to allow for it.
408 if node.state.get() != NodeState::Pending {
411 let result = processor.process_obligation(&mut node.obligation);
413 debug!("process_obligations: node {} got result {:?}", index, result);
416 ProcessResult::Unchanged => {
417 // No change in state.
419 ProcessResult::Changed(children) => {
420 // We are not (yet) stalled.
422 node.state.set(NodeState::Success);
424 for child in children {
425 let st = self.register_obligation_at(
429 if let Err(()) = st {
430 // Error already reported - propagate it
432 self.error_at(index);
436 ProcessResult::Error(err) => {
440 backtrace: self.error_at(index),
447 // There's no need to perform marking, cycle processing and compression when nothing
450 completed: if do_completed == DoCompleted::Yes { Some(vec![]) } else { None },
456 self.mark_as_waiting();
457 self.process_cycles(processor);
458 let completed = self.compress(do_completed);
460 debug!("process_obligations: complete");
469 /// Mark all `NodeState::Success` nodes as `NodeState::Done` and
470 /// report all cycles between them. This should be called
471 /// after `mark_as_waiting` marks all nodes with pending
472 /// subobligations as NodeState::Waiting.
473 fn process_cycles<P>(&self, processor: &mut P)
474 where P: ObligationProcessor<Obligation=O>
476 let mut stack = vec![];
478 debug!("process_cycles()");
480 for (index, node) in self.nodes.iter().enumerate() {
481 // For some benchmarks this state test is extremely
482 // hot. It's a win to handle the no-op cases immediately to avoid
483 // the cost of the function call.
484 if node.state.get() == NodeState::Success {
485 self.find_cycles_from_node(&mut stack, processor, index);
489 debug!("process_cycles: complete");
491 debug_assert!(stack.is_empty());
494 fn find_cycles_from_node<P>(&self, stack: &mut Vec<usize>, processor: &mut P, index: usize)
495 where P: ObligationProcessor<Obligation=O>
497 let node = &self.nodes[index];
498 if node.state.get() == NodeState::Success {
499 match stack.iter().rposition(|&n| n == index) {
502 for &index in node.dependents.iter() {
503 self.find_cycles_from_node(stack, processor, index);
506 node.state.set(NodeState::Done);
510 processor.process_backedge(
511 stack[rpos..].iter().map(GetObligation(&self.nodes)),
519 /// Returns a vector of obligations for `p` and all of its
520 /// ancestors, putting them into the error state in the process.
521 fn error_at(&self, mut index: usize) -> Vec<O> {
522 let mut error_stack: Vec<usize> = vec![];
523 let mut trace = vec![];
526 let node = &self.nodes[index];
527 node.state.set(NodeState::Error);
528 trace.push(node.obligation.clone());
530 // The first dependent is the parent, which is treated
532 error_stack.extend(node.dependents.iter().skip(1));
533 index = node.dependents[0];
535 // No parent; treat all dependents non-specially.
536 error_stack.extend(node.dependents.iter());
541 while let Some(index) = error_stack.pop() {
542 let node = &self.nodes[index];
543 if node.state.get() != NodeState::Error {
544 node.state.set(NodeState::Error);
545 error_stack.extend(node.dependents.iter());
552 // This always-inlined function is for the hot call site.
554 fn inlined_mark_neighbors_as_waiting_from(&self, node: &Node<O>) {
555 for &index in node.dependents.iter() {
556 let node = &self.nodes[index];
557 match node.state.get() {
558 NodeState::Waiting | NodeState::Error => {}
559 NodeState::Success => {
560 node.state.set(NodeState::Waiting);
561 // This call site is cold.
562 self.uninlined_mark_neighbors_as_waiting_from(node);
564 NodeState::Pending | NodeState::Done => {
565 // This call site is cold.
566 self.uninlined_mark_neighbors_as_waiting_from(node);
572 // This never-inlined function is for the cold call site.
574 fn uninlined_mark_neighbors_as_waiting_from(&self, node: &Node<O>) {
575 self.inlined_mark_neighbors_as_waiting_from(node)
578 /// Marks all nodes that depend on a pending node as `NodeState::Waiting`.
579 fn mark_as_waiting(&self) {
580 for node in &self.nodes {
581 if node.state.get() == NodeState::Waiting {
582 node.state.set(NodeState::Success);
586 for node in &self.nodes {
587 if node.state.get() == NodeState::Pending {
588 // This call site is hot.
589 self.inlined_mark_neighbors_as_waiting_from(node);
594 /// Compresses the vector, removing all popped nodes. This adjusts the
595 /// indices and hence invalidates any outstanding indices.
597 /// Beforehand, all nodes must be marked as `Done` and no cycles
598 /// on these nodes may be present. This is done by e.g., `process_cycles`.
600 fn compress(&mut self, do_completed: DoCompleted) -> Option<Vec<O>> {
601 let orig_nodes_len = self.nodes.len();
602 let mut node_rewrites: Vec<_> = self.node_rewrites.replace(vec![]);
603 debug_assert!(node_rewrites.is_empty());
604 node_rewrites.extend(0..orig_nodes_len);
605 let mut dead_nodes = 0;
606 let mut removed_done_obligations: Vec<O> = vec![];
608 // Now move all Done/Error nodes to the end, preserving the order of
609 // the Pending/Waiting nodes.
612 // self.nodes[0..index - dead_nodes] are the first remaining nodes
613 // self.nodes[index - dead_nodes..index] are all dead
614 // self.nodes[index..] are unchanged
615 for index in 0..orig_nodes_len {
616 let node = &self.nodes[index];
617 match node.state.get() {
618 NodeState::Pending | NodeState::Waiting => {
620 self.nodes.swap(index, index - dead_nodes);
621 node_rewrites[index] -= dead_nodes;
625 // This lookup can fail because the contents of
626 // `self.active_cache` are not guaranteed to match those of
627 // `self.nodes`. See the comment in `process_obligation`
629 if let Some((predicate, _)) =
630 self.active_cache.remove_entry(node.obligation.as_predicate())
632 self.done_cache.insert(predicate);
634 self.done_cache.insert(node.obligation.as_predicate().clone());
636 if do_completed == DoCompleted::Yes {
637 // Extract the success stories.
638 removed_done_obligations.push(node.obligation.clone());
640 node_rewrites[index] = orig_nodes_len;
643 NodeState::Error => {
644 // We *intentionally* remove the node from the cache at this point. Otherwise
645 // tests must come up with a different type on every type error they
647 self.active_cache.remove(node.obligation.as_predicate());
648 self.insert_into_error_cache(index);
649 node_rewrites[index] = orig_nodes_len;
652 NodeState::Success => unreachable!()
657 // Remove the dead nodes and rewrite indices.
658 self.nodes.truncate(orig_nodes_len - dead_nodes);
659 self.apply_rewrites(&node_rewrites);
662 node_rewrites.truncate(0);
663 self.node_rewrites.replace(node_rewrites);
665 if do_completed == DoCompleted::Yes {
666 Some(removed_done_obligations)
672 fn apply_rewrites(&mut self, node_rewrites: &[usize]) {
673 let orig_nodes_len = node_rewrites.len();
675 for node in &mut self.nodes {
677 while i < node.dependents.len() {
678 let new_index = node_rewrites[node.dependents[i]];
679 if new_index >= orig_nodes_len {
680 node.dependents.swap_remove(i);
681 if i == 0 && node.has_parent {
682 // We just removed the parent.
683 node.has_parent = false;
686 node.dependents[i] = new_index;
692 // This updating of `self.active_cache` is necessary because the
693 // removal of nodes within `compress` can fail. See above.
694 self.active_cache.retain(|_predicate, index| {
695 let new_index = node_rewrites[*index];
696 if new_index >= orig_nodes_len {
706 // I need a Clone closure.
708 struct GetObligation<'a, O>(&'a [Node<O>]);
710 impl<'a, 'b, O> FnOnce<(&'b usize,)> for GetObligation<'a, O> {
712 extern "rust-call" fn call_once(self, args: (&'b usize,)) -> &'a O {
713 &self.0[*args.0].obligation
717 impl<'a, 'b, O> FnMut<(&'b usize,)> for GetObligation<'a, O> {
718 extern "rust-call" fn call_mut(&mut self, args: (&'b usize,)) -> &'a O {
719 &self.0[*args.0].obligation