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 two 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.
57 //! Upon completion, none of the existing obligations were *shallowly
58 //! successful* (that is, no callback returned `Changed(_)`). This implies that
59 //! all obligations were either errors or returned an ambiguous result.
61 //! ### Implementation details
63 //! For the most part, comments specific to the implementation are in the
64 //! code. This file only contains a very high-level overview. Basically,
65 //! the forest is stored in a vector. Each element of the vector is a node
66 //! in some tree. Each node in the vector has the index of its dependents,
67 //! including the first dependent which is known as the parent. It also
68 //! has a current state, described by `NodeState`. After each processing
69 //! step, we compress the vector to remove completed and error nodes, which
70 //! aren't needed anymore.
72 use crate::fx::{FxHashMap, FxHashSet};
75 use std::collections::hash_map::Entry;
78 use std::marker::PhantomData;
85 pub trait ForestObligation: Clone + Debug {
86 type CacheKey: Clone + hash::Hash + Eq + Debug;
88 /// Converts this `ForestObligation` suitable for use as a cache key.
89 /// If two distinct `ForestObligations`s return the same cache key,
90 /// then it must be sound to use the result of processing one obligation
91 /// (e.g. success for error) for the other obligation
92 fn as_cache_key(&self) -> Self::CacheKey;
95 pub trait ObligationProcessor {
96 type Obligation: ForestObligation;
98 type OUT: OutcomeTrait<Obligation = Self::Obligation, Error = Error<Self::Obligation, Self::Error>>;
100 fn needs_process_obligation(&self, obligation: &Self::Obligation) -> bool;
102 fn process_obligation(
104 obligation: &mut Self::Obligation,
105 ) -> ProcessResult<Self::Obligation, Self::Error>;
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
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).
115 fn process_backedge<'c, I>(
118 _marker: PhantomData<&'c Self::Obligation>,
119 ) -> Result<(), Self::Error>
121 I: Clone + Iterator<Item = &'c Self::Obligation>;
124 /// The result type used by `process_obligation`.
125 // `repr(C)` to inhibit the niche filling optimization. Otherwise, the `match` appearing
126 // in `process_obligations` is significantly slower, which can substantially affect
127 // benchmarks like `rustc-perf`'s inflate and keccak.
130 pub enum ProcessResult<O, E> {
136 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
137 struct ObligationTreeId(usize);
139 type ObligationTreeIdGenerator = impl Iterator<Item = ObligationTreeId>;
141 pub struct ObligationForest<O: ForestObligation> {
142 /// The list of obligations. In between calls to [Self::process_obligations],
143 /// this list only contains nodes in the `Pending` or `Waiting` state.
145 /// `usize` indices are used here and throughout this module, rather than
146 /// [`rustc_index::newtype_index!`] indices, because this code is hot enough
147 /// that the `u32`-to-`usize` conversions that would be required are
148 /// significant, and space considerations are not important.
151 /// A cache of predicates that have been successfully completed.
152 done_cache: FxHashSet<O::CacheKey>,
154 /// A cache of the nodes in `nodes`, indexed by predicate. Unfortunately,
155 /// its contents are not guaranteed to match those of `nodes`. See the
156 /// comments in `Self::process_obligation` for details.
157 active_cache: FxHashMap<O::CacheKey, usize>,
159 /// A vector reused in [Self::compress()] and [Self::find_cycles_from_node()],
160 /// to avoid allocating new vectors.
161 reused_node_vec: Vec<usize>,
163 obligation_tree_id_generator: ObligationTreeIdGenerator,
165 /// Per tree error cache. This is used to deduplicate errors,
166 /// which is necessary to avoid trait resolution overflow in
169 /// See [this][details] for details.
171 /// [details]: https://github.com/rust-lang/rust/pull/53255#issuecomment-421184780
172 error_cache: FxHashMap<ObligationTreeId, FxHashSet<O::CacheKey>>,
178 state: Cell<NodeState>,
180 /// Obligations that depend on this obligation for their completion. They
181 /// must all be in a non-pending state.
182 dependents: Vec<usize>,
184 /// If true, `dependents[0]` points to a "parent" node, which requires
185 /// special treatment upon error but is otherwise treated the same.
186 /// (It would be more idiomatic to store the parent node in a separate
187 /// `Option<usize>` field, but that slows down the common case of
188 /// iterating over the parent and other descendants together.)
191 /// Identifier of the obligation tree to which this node belongs.
192 obligation_tree_id: ObligationTreeId,
196 fn new(parent: Option<usize>, obligation: O, obligation_tree_id: ObligationTreeId) -> Node<O> {
199 state: Cell::new(NodeState::Pending),
200 dependents: if let Some(parent_index) = parent { vec![parent_index] } else { vec![] },
201 has_parent: parent.is_some(),
207 /// The state of one node in some tree within the forest. This represents the
208 /// current state of processing for the obligation (of type `O`) associated
211 /// The non-`Error` state transitions are as follows.
215 /// | register_obligation_at() (called by process_obligations() and
216 /// v from outside the crate)
219 /// | process_obligations()
223 /// | | mark_successes()
227 /// | process_cycles()
235 /// The `Error` state can be introduced in several places, via `error_at()`.
237 /// Outside of `ObligationForest` methods, nodes should be either `Pending` or
239 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
241 /// This obligation has not yet been selected successfully. Cannot have
245 /// This obligation was selected successfully, but may or may not have
249 /// This obligation was selected successfully, but it has a pending
253 /// This obligation, along with its subobligations, are complete, and will
254 /// be removed in the next collection.
257 /// This obligation was resolved to an error. It will be removed by the
258 /// next compression step.
262 /// This trait allows us to have two different Outcome types:
263 /// - the normal one that does as little as possible
264 /// - one for tests that does some additional work and checking
265 pub trait OutcomeTrait {
270 fn record_completed(&mut self, outcome: &Self::Obligation);
271 fn record_error(&mut self, error: Self::Error);
275 pub struct Outcome<O, E> {
276 /// Backtrace of obligations that were found to be in error.
277 pub errors: Vec<Error<O, E>>,
280 impl<O, E> OutcomeTrait for Outcome<O, E> {
281 type Error = Error<O, E>;
285 Self { errors: vec![] }
288 fn record_completed(&mut self, _outcome: &Self::Obligation) {
292 fn record_error(&mut self, error: Self::Error) {
293 self.errors.push(error)
297 #[derive(Debug, PartialEq, Eq)]
298 pub struct Error<O, E> {
300 pub backtrace: Vec<O>,
303 impl<O: ForestObligation> ObligationForest<O> {
304 pub fn new() -> ObligationForest<O> {
307 done_cache: Default::default(),
308 active_cache: Default::default(),
309 reused_node_vec: vec![],
310 obligation_tree_id_generator: (0..).map(ObligationTreeId),
311 error_cache: Default::default(),
315 /// Returns the total number of nodes in the forest that have not
316 /// yet been fully resolved.
317 pub fn len(&self) -> usize {
321 /// Registers an obligation.
322 pub fn register_obligation(&mut self, obligation: O) {
323 // Ignore errors here - there is no guarantee of success.
324 let _ = self.register_obligation_at(obligation, None);
327 // Returns Err(()) if we already know this obligation failed.
328 fn register_obligation_at(&mut self, obligation: O, parent: Option<usize>) -> Result<(), ()> {
329 let cache_key = obligation.as_cache_key();
330 if self.done_cache.contains(&cache_key) {
331 debug!("register_obligation_at: ignoring already done obligation: {:?}", obligation);
335 match self.active_cache.entry(cache_key) {
336 Entry::Occupied(o) => {
337 let node = &mut self.nodes[*o.get()];
338 if let Some(parent_index) = parent {
339 // If the node is already in `active_cache`, it has already
340 // had its chance to be marked with a parent. So if it's
341 // not already present, just dump `parent` into the
342 // dependents as a non-parent.
343 if !node.dependents.contains(&parent_index) {
344 node.dependents.push(parent_index);
347 if let NodeState::Error = node.state.get() { Err(()) } else { Ok(()) }
349 Entry::Vacant(v) => {
350 let obligation_tree_id = match parent {
351 Some(parent_index) => self.nodes[parent_index].obligation_tree_id,
352 None => self.obligation_tree_id_generator.next().unwrap(),
355 let already_failed = parent.is_some()
358 .get(&obligation_tree_id)
359 .map_or(false, |errors| errors.contains(v.key()));
364 let new_index = self.nodes.len();
366 self.nodes.push(Node::new(parent, obligation, obligation_tree_id));
373 /// Converts all remaining obligations to the given error.
374 pub fn to_errors<E: Clone>(&mut self, error: E) -> Vec<Error<O, E>> {
379 .filter(|(_index, node)| node.state.get() == NodeState::Pending)
380 .map(|(index, _node)| Error { error: error.clone(), backtrace: self.error_at(index) })
383 self.compress(|_| assert!(false));
387 /// Returns the set of obligations that are in a pending state.
388 pub fn map_pending_obligations<P, F>(&self, f: F) -> Vec<P>
394 .filter(|node| node.state.get() == NodeState::Pending)
395 .map(|node| f(&node.obligation))
399 fn insert_into_error_cache(&mut self, index: usize) {
400 let node = &self.nodes[index];
402 .entry(node.obligation_tree_id)
404 .insert(node.obligation.as_cache_key());
407 /// Performs a fixpoint computation over the obligation list.
409 pub fn process_obligations<P>(&mut self, processor: &mut P) -> P::OUT
411 P: ObligationProcessor<Obligation = O>,
413 let mut outcome = P::OUT::new();
415 // Fixpoint computation: we repeat until the inner loop stalls.
417 let mut has_changed = false;
419 // Note that the loop body can append new nodes, and those new nodes
420 // will then be processed by subsequent iterations of the loop.
422 // We can't use an iterator for the loop because `self.nodes` is
423 // appended to and the borrow checker would complain. We also can't use
424 // `for index in 0..self.nodes.len() { ... }` because the range would
425 // be computed with the initial length, and we would miss the appended
426 // nodes. Therefore we use a `while` loop.
428 while let Some(node) = self.nodes.get_mut(index) {
429 if node.state.get() != NodeState::Pending
430 || !processor.needs_process_obligation(&node.obligation)
436 // `processor.process_obligation` can modify the predicate within
437 // `node.obligation`, and that predicate is the key used for
438 // `self.active_cache`. This means that `self.active_cache` can get
439 // out of sync with `nodes`. It's not very common, but it does
440 // happen, and code in `compress` has to allow for it.
442 match processor.process_obligation(&mut node.obligation) {
443 ProcessResult::Unchanged => {
444 // No change in state.
446 ProcessResult::Changed(children) => {
447 // We are not (yet) stalled.
449 node.state.set(NodeState::Success);
451 for child in children {
452 let st = self.register_obligation_at(child, Some(index));
453 if let Err(()) = st {
454 // Error already reported - propagate it
456 self.error_at(index);
460 ProcessResult::Error(err) => {
462 outcome.record_error(Error { error: err, backtrace: self.error_at(index) });
468 // If unchanged, then we saw no successful obligations, which means
469 // there is no point in further iteration. This is based on the
470 // assumption that when trait matching returns `Error` or
471 // `Unchanged`, those results do not affect environmental inference
472 // state. (Note that this will occur if we invoke
473 // `process_obligations` with no pending obligations.)
478 self.mark_successes();
479 self.process_cycles(processor, &mut outcome);
480 self.compress(|obl| outcome.record_completed(obl));
486 /// Returns a vector of obligations for `p` and all of its
487 /// ancestors, putting them into the error state in the process.
488 fn error_at(&self, mut index: usize) -> Vec<O> {
489 let mut error_stack: Vec<usize> = vec![];
490 let mut trace = vec![];
493 let node = &self.nodes[index];
494 node.state.set(NodeState::Error);
495 trace.push(node.obligation.clone());
497 // The first dependent is the parent, which is treated
499 error_stack.extend(node.dependents.iter().skip(1));
500 index = node.dependents[0];
502 // No parent; treat all dependents non-specially.
503 error_stack.extend(node.dependents.iter());
508 while let Some(index) = error_stack.pop() {
509 let node = &self.nodes[index];
510 if node.state.get() != NodeState::Error {
511 node.state.set(NodeState::Error);
512 error_stack.extend(node.dependents.iter());
519 /// Mark all `Waiting` nodes as `Success`, except those that depend on a
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);
529 // Convert `Success` nodes that depend on a pending node back to
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);
539 // This always-inlined function is for the hot call site.
541 fn inlined_mark_dependents_as_waiting(&self, node: &Node<O>) {
542 for &index in node.dependents.iter() {
543 let node = &self.nodes[index];
544 let state = node.state.get();
545 if state == NodeState::Success {
546 // This call site is cold.
547 self.uninlined_mark_dependents_as_waiting(node);
549 debug_assert!(state == NodeState::Waiting || state == NodeState::Error)
554 // This never-inlined function is for the cold call site.
556 fn uninlined_mark_dependents_as_waiting(&self, node: &Node<O>) {
557 // Mark node Waiting in the cold uninlined code instead of the hot inlined
558 node.state.set(NodeState::Waiting);
559 self.inlined_mark_dependents_as_waiting(node)
562 /// Report cycles between all `Success` nodes, and convert all `Success`
563 /// nodes to `Done`. This must be called after `mark_successes`.
564 fn process_cycles<P>(&mut self, processor: &mut P, outcome: &mut P::OUT)
566 P: ObligationProcessor<Obligation = O>,
568 let mut stack = std::mem::take(&mut self.reused_node_vec);
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
573 if node.state.get() == NodeState::Success {
574 self.find_cycles_from_node(&mut stack, processor, index, outcome);
578 debug_assert!(stack.is_empty());
579 self.reused_node_vec = stack;
582 fn find_cycles_from_node<P>(
584 stack: &mut Vec<usize>,
587 outcome: &mut P::OUT,
589 P: ObligationProcessor<Obligation = O>,
591 let node = &self.nodes[index];
592 if node.state.get() == NodeState::Success {
593 match stack.iter().rposition(|&n| n == index) {
596 for &dep_index in node.dependents.iter() {
597 self.find_cycles_from_node(stack, processor, dep_index, outcome);
600 node.state.set(NodeState::Done);
604 let result = processor.process_backedge(
605 stack[rpos..].iter().map(|&i| &self.nodes[i].obligation),
608 if let Err(err) = result {
609 outcome.record_error(Error { error: err, backtrace: self.error_at(index) });
616 /// Compresses the vector, removing all popped nodes. This adjusts the
617 /// indices and hence invalidates any outstanding indices. `process_cycles`
618 /// must be run beforehand to remove any cycles on `Success` nodes.
620 fn compress(&mut self, mut outcome_cb: impl FnMut(&O)) {
621 let orig_nodes_len = self.nodes.len();
622 let mut node_rewrites: Vec<_> = std::mem::take(&mut self.reused_node_vec);
623 debug_assert!(node_rewrites.is_empty());
624 node_rewrites.extend(0..orig_nodes_len);
625 let mut dead_nodes = 0;
627 // Move removable nodes to the end, preserving the order of the
631 // self.nodes[0..index - dead_nodes] are the first remaining nodes
632 // self.nodes[index - dead_nodes..index] are all dead
633 // self.nodes[index..] are unchanged
634 for index in 0..orig_nodes_len {
635 let node = &self.nodes[index];
636 match node.state.get() {
637 NodeState::Pending | NodeState::Waiting => {
639 self.nodes.swap(index, index - dead_nodes);
640 node_rewrites[index] -= dead_nodes;
644 // The removal lookup might fail because the contents of
645 // `self.active_cache` are not guaranteed to match those of
646 // `self.nodes`. See the comment in `process_obligation`
648 let cache_key = node.obligation.as_cache_key();
649 self.active_cache.remove(&cache_key);
650 self.done_cache.insert(cache_key);
652 // Extract the success stories.
653 outcome_cb(&node.obligation);
654 node_rewrites[index] = orig_nodes_len;
657 NodeState::Error => {
658 // We *intentionally* remove the node from the cache at this point. Otherwise
659 // tests must come up with a different type on every type error they
661 self.active_cache.remove(&node.obligation.as_cache_key());
662 self.insert_into_error_cache(index);
663 node_rewrites[index] = orig_nodes_len;
666 NodeState::Success => unreachable!(),
671 // Remove the dead nodes and rewrite indices.
672 self.nodes.truncate(orig_nodes_len - dead_nodes);
673 self.apply_rewrites(&node_rewrites);
676 node_rewrites.truncate(0);
677 self.reused_node_vec = node_rewrites;
681 fn apply_rewrites(&mut self, node_rewrites: &[usize]) {
682 let orig_nodes_len = node_rewrites.len();
684 for node in &mut self.nodes {
686 while let Some(dependent) = node.dependents.get_mut(i) {
687 let new_index = node_rewrites[*dependent];
688 if new_index >= orig_nodes_len {
689 node.dependents.swap_remove(i);
690 if i == 0 && node.has_parent {
691 // We just removed the parent.
692 node.has_parent = false;
695 *dependent = new_index;
701 // This updating of `self.active_cache` is necessary because the
702 // removal of nodes within `compress` can fail. See above.
703 self.active_cache.retain(|_predicate, index| {
704 let new_index = node_rewrites[*index];
705 if new_index >= orig_nodes_len {