1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! The `ObligationForest` is a utility data structure used in trait
12 //! matching to track the set of outstanding obligations (those not
13 //! yet resolved to success or error). It also tracks the "backtrace"
14 //! of each pending obligation (why we are trying to figure this out
15 //! in the first place). See README.md for a general overview of how
16 //! to use this class.
18 use fx::{FxHashMap, FxHashSet};
21 use std::collections::hash_map::Entry;
24 use std::marker::PhantomData;
27 use self::node_index::NodeIndex;
32 pub trait ForestObligation : Clone + Debug {
33 type Predicate : Clone + hash::Hash + Eq + Debug;
35 fn as_predicate(&self) -> &Self::Predicate;
38 pub trait ObligationProcessor {
39 type Obligation : ForestObligation;
42 fn process_obligation(&mut self,
43 obligation: &mut Self::Obligation)
44 -> Result<Option<Vec<Self::Obligation>>, Self::Error>;
46 fn process_backedge<'c, I>(&mut self, cycle: I,
47 _marker: PhantomData<&'c Self::Obligation>)
48 where I: Clone + Iterator<Item=&'c Self::Obligation>;
53 cache_list_len: usize,
56 pub struct ObligationForest<O: ForestObligation> {
57 /// The list of obligations. In between calls to
58 /// `process_obligations`, this list only contains nodes in the
59 /// `Pending` or `Success` state (with a non-zero number of
60 /// incomplete children). During processing, some of those nodes
61 /// may be changed to the error state, or we may find that they
62 /// are completed (That is, `num_incomplete_children` drops to 0).
63 /// At the end of processing, those nodes will be removed by a
64 /// call to `compress`.
66 /// At all times we maintain the invariant that every node appears
67 /// at a higher index than its parent. This is needed by the
68 /// backtrace iterator (which uses `split_at`).
70 /// A cache of predicates that have been successfully completed.
71 done_cache: FxHashSet<O::Predicate>,
72 /// An cache of the nodes in `nodes`, indexed by predicate.
73 waiting_cache: FxHashMap<O::Predicate, NodeIndex>,
74 /// A list of the obligations added in snapshots, to allow
75 /// for their removal.
76 cache_list: Vec<O::Predicate>,
77 snapshots: Vec<SnapshotData>,
78 scratch: Option<Vec<usize>>,
88 state: Cell<NodeState>,
90 /// Obligations that depend on this obligation for their
91 /// completion. They must all be in a non-pending state.
92 dependents: Vec<NodeIndex>,
93 /// The parent of a node - the original obligation of
94 /// which it is a subobligation. Except for error reporting,
95 /// this is just another member of `dependents`.
96 parent: Option<NodeIndex>,
99 /// The state of one node in some tree within the forest. This
100 /// represents the current state of processing for the obligation (of
101 /// type `O`) associated with this node.
103 /// Outside of ObligationForest methods, nodes should be either Pending
105 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
107 /// Obligations for which selection had not yet returned a
108 /// non-ambiguous result.
111 /// This obligation was selected successfuly, but may or
112 /// may not have subobligations.
115 /// This obligation was selected sucessfully, but it has
116 /// a pending subobligation.
119 /// This obligation, along with its subobligations, are complete,
120 /// and will be removed in the next collection.
123 /// This obligation was resolved to an error. Error nodes are
124 /// removed from the vector by the compression step.
127 /// This is a temporary state used in DFS loops to detect cycles,
128 /// it should not exist outside of these DFSes.
133 pub struct Outcome<O, E> {
134 /// Obligations that were completely evaluated, including all
135 /// (transitive) subobligations.
136 pub completed: Vec<O>,
138 /// Backtrace of obligations that were found to be in error.
139 pub errors: Vec<Error<O, E>>,
141 /// If true, then we saw no successful obligations, which means
142 /// there is no point in further iteration. This is based on the
143 /// assumption that when trait matching returns `Err` or
144 /// `Ok(None)`, those results do not affect environmental
145 /// inference state. (Note that if we invoke `process_obligations`
146 /// with no pending obligations, stalled will be true.)
150 #[derive(Debug, PartialEq, Eq)]
151 pub struct Error<O, E> {
153 pub backtrace: Vec<O>,
156 impl<O: ForestObligation> ObligationForest<O> {
157 pub fn new() -> ObligationForest<O> {
161 done_cache: FxHashSet(),
162 waiting_cache: FxHashMap(),
164 scratch: Some(vec![]),
168 /// Return the total number of nodes in the forest that have not
169 /// yet been fully resolved.
170 pub fn len(&self) -> usize {
174 pub fn start_snapshot(&mut self) -> Snapshot {
175 self.snapshots.push(SnapshotData {
176 node_len: self.nodes.len(),
177 cache_list_len: self.cache_list.len()
179 Snapshot { len: self.snapshots.len() }
182 pub fn commit_snapshot(&mut self, snapshot: Snapshot) {
183 assert_eq!(snapshot.len, self.snapshots.len());
184 let info = self.snapshots.pop().unwrap();
185 assert!(self.nodes.len() >= info.node_len);
186 assert!(self.cache_list.len() >= info.cache_list_len);
189 pub fn rollback_snapshot(&mut self, snapshot: Snapshot) {
190 // Check that we are obeying stack discipline.
191 assert_eq!(snapshot.len, self.snapshots.len());
192 let info = self.snapshots.pop().unwrap();
194 for entry in &self.cache_list[info.cache_list_len..] {
195 self.done_cache.remove(entry);
196 self.waiting_cache.remove(entry);
199 self.nodes.truncate(info.node_len);
200 self.cache_list.truncate(info.cache_list_len);
203 pub fn in_snapshot(&self) -> bool {
204 !self.snapshots.is_empty()
207 /// Registers an obligation
209 /// This CAN be done in a snapshot
210 pub fn register_obligation(&mut self, obligation: O) {
211 // Ignore errors here - there is no guarantee of success.
212 let _ = self.register_obligation_at(obligation, None);
215 // returns Err(()) if we already know this obligation failed.
216 fn register_obligation_at(&mut self, obligation: O, parent: Option<NodeIndex>)
219 if self.done_cache.contains(obligation.as_predicate()) {
223 match self.waiting_cache.entry(obligation.as_predicate().clone()) {
224 Entry::Occupied(o) => {
225 debug!("register_obligation_at({:?}, {:?}) - duplicate of {:?}!",
226 obligation, parent, o.get());
227 if let Some(parent) = parent {
228 if self.nodes[o.get().get()].dependents.contains(&parent) {
229 debug!("register_obligation_at({:?}, {:?}) - duplicate subobligation",
232 self.nodes[o.get().get()].dependents.push(parent);
235 if let NodeState::Error = self.nodes[o.get().get()].state.get() {
241 Entry::Vacant(v) => {
242 debug!("register_obligation_at({:?}, {:?}) - ok",
244 v.insert(NodeIndex::new(self.nodes.len()));
245 self.cache_list.push(obligation.as_predicate().clone());
246 self.nodes.push(Node::new(parent, obligation));
252 /// Convert all remaining obligations to the given error.
254 /// This cannot be done during a snapshot.
255 pub fn to_errors<E: Clone>(&mut self, error: E) -> Vec<Error<O, E>> {
256 assert!(!self.in_snapshot());
257 let mut errors = vec![];
258 for index in 0..self.nodes.len() {
259 if let NodeState::Pending = self.nodes[index].state.get() {
260 let backtrace = self.error_at(index);
262 error: error.clone(),
263 backtrace: backtrace,
267 let successful_obligations = self.compress();
268 assert!(successful_obligations.is_empty());
272 /// Returns the set of obligations that are in a pending state.
273 pub fn pending_obligations(&self) -> Vec<O>
278 .filter(|n| n.state.get() == NodeState::Pending)
279 .map(|n| n.obligation.clone())
283 /// Perform a pass through the obligation list. This must
284 /// be called in a loop until `outcome.stalled` is false.
286 /// This CANNOT be unrolled (presently, at least).
287 pub fn process_obligations<P>(&mut self, processor: &mut P) -> Outcome<O, P::Error>
288 where P: ObligationProcessor<Obligation=O>
290 debug!("process_obligations(len={})", self.nodes.len());
291 assert!(!self.in_snapshot()); // cannot unroll this action
293 let mut errors = vec![];
294 let mut stalled = true;
296 for index in 0..self.nodes.len() {
297 debug!("process_obligations: node {} == {:?}",
301 let result = match self.nodes[index] {
302 Node { state: ref _state, ref mut obligation, .. }
303 if _state.get() == NodeState::Pending =>
305 processor.process_obligation(obligation)
310 debug!("process_obligations: node {} got result {:?}",
316 // no change in state
318 Ok(Some(children)) => {
319 // if we saw a Some(_) result, we are not (yet) stalled
321 self.nodes[index].state.set(NodeState::Success);
323 for child in children {
324 let st = self.register_obligation_at(
326 Some(NodeIndex::new(index))
328 if let Err(()) = st {
329 // error already reported - propagate it
331 self.error_at(index);
337 let backtrace = self.error_at(index);
340 backtrace: backtrace,
347 // There's no need to perform marking, cycle processing and compression when nothing
356 self.mark_as_waiting();
357 self.process_cycles(processor);
359 // Now we have to compress the result
360 let completed_obligations = self.compress();
362 debug!("process_obligations: complete");
365 completed: completed_obligations,
371 /// Mark all NodeState::Success nodes as NodeState::Done and
372 /// report all cycles between them. This should be called
373 /// after `mark_as_waiting` marks all nodes with pending
374 /// subobligations as NodeState::Waiting.
375 fn process_cycles<P>(&mut self, processor: &mut P)
376 where P: ObligationProcessor<Obligation=O>
378 let mut stack = self.scratch.take().unwrap();
380 for index in 0..self.nodes.len() {
381 // For rustc-benchmarks/inflate-0.1.0 this state test is extremely
382 // hot and the state is almost always `Pending` or `Waiting`. It's
383 // a win to handle the no-op cases immediately to avoid the cost of
384 // the function call.
385 let state = self.nodes[index].state.get();
387 NodeState::Waiting | NodeState::Pending | NodeState::Done | NodeState::Error => {},
388 _ => self.find_cycles_from_node(&mut stack, processor, index),
392 self.scratch = Some(stack);
395 fn find_cycles_from_node<P>(&self, stack: &mut Vec<usize>,
396 processor: &mut P, index: usize)
397 where P: ObligationProcessor<Obligation=O>
399 let node = &self.nodes[index];
400 let state = node.state.get();
402 NodeState::OnDfsStack => {
404 stack.iter().rposition(|n| *n == index).unwrap();
405 // I need a Clone closure
407 struct GetObligation<'a, O: 'a>(&'a [Node<O>]);
408 impl<'a, 'b, O> FnOnce<(&'b usize,)> for GetObligation<'a, O> {
410 extern "rust-call" fn call_once(self, args: (&'b usize,)) -> &'a O {
411 &self.0[*args.0].obligation
414 impl<'a, 'b, O> FnMut<(&'b usize,)> for GetObligation<'a, O> {
415 extern "rust-call" fn call_mut(&mut self, args: (&'b usize,)) -> &'a O {
416 &self.0[*args.0].obligation
420 processor.process_backedge(stack[index..].iter().map(GetObligation(&self.nodes)),
423 NodeState::Success => {
424 node.state.set(NodeState::OnDfsStack);
426 if let Some(parent) = node.parent {
427 self.find_cycles_from_node(stack, processor, parent.get());
429 for dependent in &node.dependents {
430 self.find_cycles_from_node(stack, processor, dependent.get());
433 node.state.set(NodeState::Done);
435 NodeState::Waiting | NodeState::Pending => {
436 // this node is still reachable from some pending node. We
437 // will get to it when they are all processed.
439 NodeState::Done | NodeState::Error => {
440 // already processed that node
445 /// Returns a vector of obligations for `p` and all of its
446 /// ancestors, putting them into the error state in the process.
447 fn error_at(&mut self, p: usize) -> Vec<O> {
448 let mut error_stack = self.scratch.take().unwrap();
449 let mut trace = vec![];
453 self.nodes[n].state.set(NodeState::Error);
454 trace.push(self.nodes[n].obligation.clone());
455 error_stack.extend(self.nodes[n].dependents.iter().map(|x| x.get()));
457 // loop to the parent
458 match self.nodes[n].parent {
459 Some(q) => n = q.get(),
465 // non-standard `while let` to bypass #6393
466 let i = match error_stack.pop() {
471 let node = &self.nodes[i];
473 match node.state.get() {
474 NodeState::Error => continue,
475 _ => node.state.set(NodeState::Error)
479 node.dependents.iter().cloned().chain(node.parent).map(|x| x.get())
483 self.scratch = Some(error_stack);
488 fn mark_neighbors_as_waiting_from(&self, node: &Node<O>) {
489 if let Some(parent) = node.parent {
490 self.mark_as_waiting_from(&self.nodes[parent.get()]);
493 for dependent in &node.dependents {
494 self.mark_as_waiting_from(&self.nodes[dependent.get()]);
498 /// Marks all nodes that depend on a pending node as NodeState::Waiting.
499 fn mark_as_waiting(&self) {
500 for node in &self.nodes {
501 if node.state.get() == NodeState::Waiting {
502 node.state.set(NodeState::Success);
506 for node in &self.nodes {
507 if node.state.get() == NodeState::Pending {
508 self.mark_neighbors_as_waiting_from(node);
513 fn mark_as_waiting_from(&self, node: &Node<O>) {
514 match node.state.get() {
515 NodeState::Waiting | NodeState::Error | NodeState::OnDfsStack => return,
516 NodeState::Success => node.state.set(NodeState::Waiting),
517 NodeState::Pending | NodeState::Done => {},
520 self.mark_neighbors_as_waiting_from(node);
523 /// Compresses the vector, removing all popped nodes. This adjusts
524 /// the indices and hence invalidates any outstanding
525 /// indices. Cannot be used during a transaction.
527 /// Beforehand, all nodes must be marked as `Done` and no cycles
528 /// on these nodes may be present. This is done by e.g. `process_cycles`.
530 fn compress(&mut self) -> Vec<O> {
531 assert!(!self.in_snapshot()); // didn't write code to unroll this action
533 let nodes_len = self.nodes.len();
534 let mut node_rewrites: Vec<_> = self.scratch.take().unwrap();
535 node_rewrites.extend(0..nodes_len);
536 let mut dead_nodes = 0;
538 // Now move all popped nodes to the end. Try to keep the order.
541 // self.nodes[0..i - dead_nodes] are the first remaining nodes
542 // self.nodes[i - dead_nodes..i] are all dead
543 // self.nodes[i..] are unchanged
544 for i in 0..self.nodes.len() {
545 match self.nodes[i].state.get() {
546 NodeState::Pending | NodeState::Waiting => {
548 self.nodes.swap(i, i - dead_nodes);
549 node_rewrites[i] -= dead_nodes;
553 self.waiting_cache.remove(self.nodes[i].obligation.as_predicate());
554 // FIXME(HashMap): why can't I get my key back?
555 self.done_cache.insert(self.nodes[i].obligation.as_predicate().clone());
556 node_rewrites[i] = nodes_len;
559 NodeState::Error => {
560 // We *intentionally* remove the node from the cache at this point. Otherwise
561 // tests must come up with a different type on every type error they
563 self.waiting_cache.remove(self.nodes[i].obligation.as_predicate());
564 node_rewrites[i] = nodes_len;
567 NodeState::OnDfsStack | NodeState::Success => unreachable!()
571 // No compression needed.
573 node_rewrites.truncate(0);
574 self.scratch = Some(node_rewrites);
578 // Pop off all the nodes we killed and extract the success
580 let successful = (0..dead_nodes)
581 .map(|_| self.nodes.pop().unwrap())
583 match node.state.get() {
584 NodeState::Error => None,
585 NodeState::Done => Some(node.obligation),
590 self.apply_rewrites(&node_rewrites);
592 node_rewrites.truncate(0);
593 self.scratch = Some(node_rewrites);
598 fn apply_rewrites(&mut self, node_rewrites: &[usize]) {
599 let nodes_len = node_rewrites.len();
601 for node in &mut self.nodes {
602 if let Some(index) = node.parent {
603 let new_index = node_rewrites[index.get()];
604 if new_index >= nodes_len {
605 // parent dead due to error
608 node.parent = Some(NodeIndex::new(new_index));
613 while i < node.dependents.len() {
614 let new_index = node_rewrites[node.dependents[i].get()];
615 if new_index >= nodes_len {
616 node.dependents.swap_remove(i);
618 node.dependents[i] = NodeIndex::new(new_index);
624 let mut kill_list = vec![];
625 for (predicate, index) in self.waiting_cache.iter_mut() {
626 let new_index = node_rewrites[index.get()];
627 if new_index >= nodes_len {
628 kill_list.push(predicate.clone());
630 *index = NodeIndex::new(new_index);
634 for predicate in kill_list { self.waiting_cache.remove(&predicate); }
639 fn new(parent: Option<NodeIndex>, obligation: O) -> Node<O> {
641 obligation: obligation,
643 state: Cell::new(NodeState::Pending),