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 (`push_tree`).
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 one of three results:
25 //! - `Ok(None)` -> 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 //! - `Ok(Some(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 //! - `Err(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 `Ok(Some(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 `Ok(Some(_))`).
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.
66 //! The `ObligationForest` supports a limited form of snapshots; see
67 //! `start_snapshot`, `commit_snapshot`, and `rollback_snapshot`. In
68 //! particular, you can use a snapshot to roll back new root
69 //! obligations. However, it is an error to attempt to
70 //! `process_obligations` during a snapshot.
72 //! ### Implementation details
74 //! For the most part, comments specific to the implementation are in the
75 //! code. This file only contains a very high-level overview. Basically,
76 //! the forest is stored in a vector. Each element of the vector is a node
77 //! in some tree. Each node in the vector has the index of an (optional)
78 //! parent and (for convenience) its root (which may be itself). It also
79 //! has a current state, described by `NodeState`. After each
80 //! processing step, we compress the vector to remove completed and error
81 //! nodes, which aren't needed anymore.
83 use crate::fx::{FxHashMap, FxHashSet};
86 use std::collections::hash_map::Entry;
89 use std::marker::PhantomData;
92 use self::node_index::NodeIndex;
99 pub trait ForestObligation : Clone + Debug {
100 type Predicate : Clone + hash::Hash + Eq + Debug;
102 fn as_predicate(&self) -> &Self::Predicate;
105 pub trait ObligationProcessor {
106 type Obligation : ForestObligation;
109 fn process_obligation(&mut self,
110 obligation: &mut Self::Obligation)
111 -> ProcessResult<Self::Obligation, Self::Error>;
113 /// As we do the cycle check, we invoke this callback when we
114 /// encounter an actual cycle. `cycle` is an iterator that starts
115 /// at the start of the cycle in the stack and walks **toward the
118 /// In other words, if we had O1 which required O2 which required
119 /// O3 which required O1, we would give an iterator yielding O1,
120 /// O2, O3 (O1 is not yielded twice).
121 fn process_backedge<'c, I>(&mut self,
123 _marker: PhantomData<&'c Self::Obligation>)
124 where I: Clone + Iterator<Item=&'c Self::Obligation>;
127 /// The result type used by `process_obligation`.
129 pub enum ProcessResult<O, E> {
135 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
136 struct ObligationTreeId(usize);
138 type ObligationTreeIdGenerator =
139 ::std::iter::Map<::std::ops::RangeFrom<usize>, fn(usize) -> ObligationTreeId>;
141 pub struct ObligationForest<O: ForestObligation> {
142 /// The list of obligations. In between calls to
143 /// `process_obligations`, this list only contains nodes in the
144 /// `Pending` or `Success` state (with a non-zero number of
145 /// incomplete children). During processing, some of those nodes
146 /// may be changed to the error state, or we may find that they
147 /// are completed (That is, `num_incomplete_children` drops to 0).
148 /// At the end of processing, those nodes will be removed by a
149 /// call to `compress`.
151 /// At all times we maintain the invariant that every node appears
152 /// at a higher index than its parent. This is needed by the
153 /// backtrace iterator (which uses `split_at`).
156 /// A cache of predicates that have been successfully completed.
157 done_cache: FxHashSet<O::Predicate>,
159 /// An cache of the nodes in `nodes`, indexed by predicate.
160 waiting_cache: FxHashMap<O::Predicate, NodeIndex>,
162 scratch: Option<Vec<usize>>,
164 obligation_tree_id_generator: ObligationTreeIdGenerator,
166 /// Per tree error cache. This is used to deduplicate errors,
167 /// which is necessary to avoid trait resolution overflow in
170 /// See [this][details] for details.
172 /// [details]: https://github.com/rust-lang/rust/pull/53255#issuecomment-421184780
173 error_cache: FxHashMap<ObligationTreeId, FxHashSet<O::Predicate>>,
179 state: Cell<NodeState>,
181 /// The parent of a node - the original obligation of
182 /// which it is a subobligation. Except for error reporting,
183 /// it is just like any member of `dependents`.
184 parent: Option<NodeIndex>,
186 /// Obligations that depend on this obligation for their
187 /// completion. They must all be in a non-pending state.
188 dependents: Vec<NodeIndex>,
190 /// Identifier of the obligation tree to which this node belongs.
191 obligation_tree_id: ObligationTreeId,
194 /// The state of one node in some tree within the forest. This
195 /// represents the current state of processing for the obligation (of
196 /// type `O`) associated with this node.
198 /// Outside of ObligationForest methods, nodes should be either Pending
200 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
202 /// Obligations for which selection had not yet returned a
203 /// non-ambiguous result.
206 /// This obligation was selected successfully, but may or
207 /// may not have subobligations.
210 /// This obligation was selected successfully, but it has
211 /// a pending subobligation.
214 /// This obligation, along with its subobligations, are complete,
215 /// and will be removed in the next collection.
218 /// This obligation was resolved to an error. Error nodes are
219 /// removed from the vector by the compression step.
222 /// This is a temporary state used in DFS loops to detect cycles,
223 /// it should not exist outside of these DFSes.
228 pub struct Outcome<O, E> {
229 /// Obligations that were completely evaluated, including all
230 /// (transitive) subobligations. Only computed if requested.
231 pub completed: Option<Vec<O>>,
233 /// Backtrace of obligations that were found to be in error.
234 pub errors: Vec<Error<O, E>>,
236 /// If true, then we saw no successful obligations, which means
237 /// there is no point in further iteration. This is based on the
238 /// assumption that when trait matching returns `Error` or
239 /// `Unchanged`, those results do not affect environmental
240 /// inference state. (Note that if we invoke `process_obligations`
241 /// with no pending obligations, stalled will be true.)
245 /// Should `process_obligations` compute the `Outcome::completed` field of its
248 pub enum DoCompleted {
253 #[derive(Debug, PartialEq, Eq)]
254 pub struct Error<O, E> {
256 pub backtrace: Vec<O>,
259 impl<O: ForestObligation> ObligationForest<O> {
260 pub fn new() -> ObligationForest<O> {
263 done_cache: Default::default(),
264 waiting_cache: Default::default(),
265 scratch: Some(vec![]),
266 obligation_tree_id_generator: (0..).map(|i| ObligationTreeId(i)),
267 error_cache: Default::default(),
271 /// Returns the total number of nodes in the forest that have not
272 /// yet been fully resolved.
273 pub fn len(&self) -> usize {
277 /// Registers an obligation.
279 /// This CAN be done in a snapshot
280 pub fn register_obligation(&mut self, obligation: O) {
281 // Ignore errors here - there is no guarantee of success.
282 let _ = self.register_obligation_at(obligation, None);
285 // returns Err(()) if we already know this obligation failed.
286 fn register_obligation_at(&mut self, obligation: O, parent: Option<NodeIndex>)
289 if self.done_cache.contains(obligation.as_predicate()) {
293 match self.waiting_cache.entry(obligation.as_predicate().clone()) {
294 Entry::Occupied(o) => {
295 debug!("register_obligation_at({:?}, {:?}) - duplicate of {:?}!",
296 obligation, parent, o.get());
297 let node = &mut self.nodes[o.get().get()];
298 if let Some(parent) = parent {
299 // If the node is already in `waiting_cache`, it's already
300 // been marked with a parent. (It's possible that parent
301 // has been cleared by `apply_rewrites`, though.) So just
302 // dump `parent` into `node.dependents`... unless it's
303 // already in `node.dependents` or `node.parent`.
304 if !node.dependents.contains(&parent) && Some(parent) != node.parent {
305 node.dependents.push(parent);
308 if let NodeState::Error = node.state.get() {
314 Entry::Vacant(v) => {
315 debug!("register_obligation_at({:?}, {:?}) - ok, new index is {}",
316 obligation, parent, self.nodes.len());
318 let obligation_tree_id = match parent {
320 let parent_node = &self.nodes[p.get()];
321 parent_node.obligation_tree_id
323 None => self.obligation_tree_id_generator.next().unwrap()
329 .get(&obligation_tree_id)
330 .map(|errors| errors.contains(obligation.as_predicate()))
336 v.insert(NodeIndex::new(self.nodes.len()));
337 self.nodes.push(Node::new(parent, obligation, obligation_tree_id));
344 /// Converts all remaining obligations to the given error.
346 /// This cannot be done during a snapshot.
347 pub fn to_errors<E: Clone>(&mut self, error: E) -> Vec<Error<O, E>> {
348 let mut errors = vec![];
349 for index in 0..self.nodes.len() {
350 if let NodeState::Pending = self.nodes[index].state.get() {
351 let backtrace = self.error_at(index);
353 error: error.clone(),
358 let successful_obligations = self.compress(DoCompleted::Yes);
359 assert!(successful_obligations.unwrap().is_empty());
363 /// Returns the set of obligations that are in a pending state.
364 pub fn map_pending_obligations<P, F>(&self, f: F) -> Vec<P>
369 .filter(|n| n.state.get() == NodeState::Pending)
370 .map(|n| f(&n.obligation))
374 fn insert_into_error_cache(&mut self, node_index: usize) {
375 let node = &self.nodes[node_index];
378 .entry(node.obligation_tree_id)
380 .insert(node.obligation.as_predicate().clone());
383 /// Performs a pass through the obligation list. This must
384 /// be called in a loop until `outcome.stalled` is false.
386 /// This _cannot_ be unrolled (presently, at least).
387 pub fn process_obligations<P>(&mut self, processor: &mut P, do_completed: DoCompleted)
388 -> Outcome<O, P::Error>
389 where P: ObligationProcessor<Obligation=O>
391 debug!("process_obligations(len={})", self.nodes.len());
393 let mut errors = vec![];
394 let mut stalled = true;
396 for index in 0..self.nodes.len() {
397 debug!("process_obligations: node {} == {:?}", index, self.nodes[index]);
399 let result = match self.nodes[index] {
400 Node { ref state, ref mut obligation, .. } if state.get() == NodeState::Pending =>
401 processor.process_obligation(obligation),
405 debug!("process_obligations: node {} got result {:?}", index, result);
408 ProcessResult::Unchanged => {
409 // No change in state.
411 ProcessResult::Changed(children) => {
412 // We are not (yet) stalled.
414 self.nodes[index].state.set(NodeState::Success);
416 for child in children {
417 let st = self.register_obligation_at(
419 Some(NodeIndex::new(index))
421 if let Err(()) = st {
422 // error already reported - propagate it
424 self.error_at(index);
428 ProcessResult::Error(err) => {
430 let backtrace = self.error_at(index);
440 // There's no need to perform marking, cycle processing and compression when nothing
443 completed: if do_completed == DoCompleted::Yes { Some(vec![]) } else { None },
449 self.mark_as_waiting();
450 self.process_cycles(processor);
452 // Now we have to compress the result
453 let completed = self.compress(do_completed);
455 debug!("process_obligations: complete");
464 /// Mark all `NodeState::Success` nodes as `NodeState::Done` and
465 /// report all cycles between them. This should be called
466 /// after `mark_as_waiting` marks all nodes with pending
467 /// subobligations as NodeState::Waiting.
468 fn process_cycles<P>(&mut self, processor: &mut P)
469 where P: ObligationProcessor<Obligation=O>
471 let mut stack = self.scratch.take().unwrap();
472 debug_assert!(stack.is_empty());
474 debug!("process_cycles()");
476 for index in 0..self.nodes.len() {
477 // For rustc-benchmarks/inflate-0.1.0 this state test is extremely
478 // hot and the state is almost always `Pending` or `Waiting`. It's
479 // a win to handle the no-op cases immediately to avoid the cost of
480 // the function call.
481 let state = self.nodes[index].state.get();
483 NodeState::Waiting | NodeState::Pending | NodeState::Done | NodeState::Error => {},
484 _ => self.find_cycles_from_node(&mut stack, processor, index),
488 debug!("process_cycles: complete");
490 debug_assert!(stack.is_empty());
491 self.scratch = Some(stack);
494 fn find_cycles_from_node<P>(&self, stack: &mut Vec<usize>,
495 processor: &mut P, index: usize)
496 where P: ObligationProcessor<Obligation=O>
498 let node = &self.nodes[index];
499 let state = node.state.get();
501 NodeState::OnDfsStack => {
503 stack.iter().rposition(|n| *n == index).unwrap();
504 processor.process_backedge(stack[index..].iter().map(GetObligation(&self.nodes)),
507 NodeState::Success => {
508 node.state.set(NodeState::OnDfsStack);
510 for dependent in node.parent.iter().chain(node.dependents.iter()) {
511 self.find_cycles_from_node(stack, processor, dependent.get());
514 node.state.set(NodeState::Done);
516 NodeState::Waiting | NodeState::Pending => {
517 // this node is still reachable from some pending node. We
518 // will get to it when they are all processed.
520 NodeState::Done | NodeState::Error => {
521 // already processed that node
526 /// Returns a vector of obligations for `p` and all of its
527 /// ancestors, putting them into the error state in the process.
528 fn error_at(&mut self, p: usize) -> Vec<O> {
529 let mut error_stack = self.scratch.take().unwrap();
530 let mut trace = vec![];
534 self.nodes[n].state.set(NodeState::Error);
535 trace.push(self.nodes[n].obligation.clone());
536 error_stack.extend(self.nodes[n].dependents.iter().map(|x| x.get()));
538 // loop to the parent
539 match self.nodes[n].parent {
540 Some(q) => n = q.get(),
545 while let Some(i) = error_stack.pop() {
546 match self.nodes[i].state.get() {
547 NodeState::Error => continue,
548 _ => self.nodes[i].state.set(NodeState::Error),
551 let node = &self.nodes[i];
554 node.parent.iter().chain(node.dependents.iter()).map(|x| x.get())
558 self.scratch = Some(error_stack);
563 fn mark_neighbors_as_waiting_from(&self, node: &Node<O>) {
564 for dependent in node.parent.iter().chain(node.dependents.iter()) {
565 self.mark_as_waiting_from(&self.nodes[dependent.get()]);
569 /// Marks all nodes that depend on a pending node as `NodeState::Waiting`.
570 fn mark_as_waiting(&self) {
571 for node in &self.nodes {
572 if node.state.get() == NodeState::Waiting {
573 node.state.set(NodeState::Success);
577 for node in &self.nodes {
578 if node.state.get() == NodeState::Pending {
579 self.mark_neighbors_as_waiting_from(node);
584 fn mark_as_waiting_from(&self, node: &Node<O>) {
585 match node.state.get() {
586 NodeState::Waiting | NodeState::Error | NodeState::OnDfsStack => return,
587 NodeState::Success => node.state.set(NodeState::Waiting),
588 NodeState::Pending | NodeState::Done => {},
591 self.mark_neighbors_as_waiting_from(node);
594 /// Compresses the vector, removing all popped nodes. This adjusts
595 /// the indices and hence invalidates any outstanding
596 /// indices. Cannot be used during a transaction.
598 /// Beforehand, all nodes must be marked as `Done` and no cycles
599 /// on these nodes may be present. This is done by e.g., `process_cycles`.
601 fn compress(&mut self, do_completed: DoCompleted) -> Option<Vec<O>> {
602 let nodes_len = self.nodes.len();
603 let mut node_rewrites: Vec<_> = self.scratch.take().unwrap();
604 node_rewrites.extend(0..nodes_len);
605 let mut dead_nodes = 0;
607 // Now move all popped nodes to the end. Try to keep the order.
610 // self.nodes[0..i - dead_nodes] are the first remaining nodes
611 // self.nodes[i - dead_nodes..i] are all dead
612 // self.nodes[i..] are unchanged
613 for i in 0..self.nodes.len() {
614 match self.nodes[i].state.get() {
615 NodeState::Pending | NodeState::Waiting => {
617 self.nodes.swap(i, i - dead_nodes);
618 node_rewrites[i] -= dead_nodes;
622 // Avoid cloning the key (predicate) in case it exists in the waiting cache
623 if let Some((predicate, _)) = self.waiting_cache
624 .remove_entry(self.nodes[i].obligation.as_predicate())
626 self.done_cache.insert(predicate);
628 self.done_cache.insert(self.nodes[i].obligation.as_predicate().clone());
630 node_rewrites[i] = nodes_len;
633 NodeState::Error => {
634 // We *intentionally* remove the node from the cache at this point. Otherwise
635 // tests must come up with a different type on every type error they
637 self.waiting_cache.remove(self.nodes[i].obligation.as_predicate());
638 node_rewrites[i] = nodes_len;
640 self.insert_into_error_cache(i);
642 NodeState::OnDfsStack | NodeState::Success => unreachable!()
646 // No compression needed.
648 node_rewrites.truncate(0);
649 self.scratch = Some(node_rewrites);
650 return if do_completed == DoCompleted::Yes { Some(vec![]) } else { None };
653 // Pop off all the nodes we killed and extract the success
655 let successful = if do_completed == DoCompleted::Yes {
657 .map(|_| self.nodes.pop().unwrap())
659 match node.state.get() {
660 NodeState::Error => None,
661 NodeState::Done => Some(node.obligation),
667 self.nodes.truncate(self.nodes.len() - dead_nodes);
670 self.apply_rewrites(&node_rewrites);
672 node_rewrites.truncate(0);
673 self.scratch = Some(node_rewrites);
678 fn apply_rewrites(&mut self, node_rewrites: &[usize]) {
679 let nodes_len = node_rewrites.len();
681 for node in &mut self.nodes {
682 if let Some(index) = node.parent {
683 let new_index = node_rewrites[index.get()];
684 if new_index >= nodes_len {
685 // parent dead due to error
688 node.parent = Some(NodeIndex::new(new_index));
693 while i < node.dependents.len() {
694 let new_index = node_rewrites[node.dependents[i].get()];
695 if new_index >= nodes_len {
696 node.dependents.swap_remove(i);
698 node.dependents[i] = NodeIndex::new(new_index);
704 let mut kill_list = vec![];
705 for (predicate, index) in &mut self.waiting_cache {
706 let new_index = node_rewrites[index.get()];
707 if new_index >= nodes_len {
708 kill_list.push(predicate.clone());
710 *index = NodeIndex::new(new_index);
714 for predicate in kill_list { self.waiting_cache.remove(&predicate); }
720 parent: Option<NodeIndex>,
722 obligation_tree_id: ObligationTreeId
726 state: Cell::new(NodeState::Pending),
734 // I need a Clone closure
736 struct GetObligation<'a, O>(&'a [Node<O>]);
738 impl<'a, 'b, O> FnOnce<(&'b usize,)> for GetObligation<'a, O> {
740 extern "rust-call" fn call_once(self, args: (&'b usize,)) -> &'a O {
741 &self.0[*args.0].obligation
745 impl<'a, 'b, O> FnMut<(&'b usize,)> for GetObligation<'a, O> {
746 extern "rust-call" fn call_mut(&mut self, args: (&'b usize,)) -> &'a O {
747 &self.0[*args.0].obligation