src/librustc_data_structures/obligation_forest/mod.rs

   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.
   4 //
   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.
  10
  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.
  17
  18 use fx::{FxHashMap, FxHashSet};
  19
  20 use std::cell::Cell;
  21 use std::collections::hash_map::Entry;
  22 use std::fmt::Debug;
  23 use std::hash;
  24 use std::marker::PhantomData;
  25
  26 mod node_index;
  27 use self::node_index::NodeIndex;
  28
  29 #[cfg(test)]
  30 mod test;
  31
  32 pub trait ForestObligation : Clone + Debug {
  33     type Predicate : Clone + hash::Hash + Eq + Debug;
  34
  35     fn as_predicate(&self) -> &Self::Predicate;
  36 }
  37
  38 pub trait ObligationProcessor {
  39     type Obligation : ForestObligation;
  40     type Error : Debug;
  41
  42     fn process_obligation(&mut self,
  43                           obligation: &mut Self::Obligation)
  44                           -> ProcessResult<Self::Obligation, Self::Error>;
  45
  46     /// As we do the cycle check, we invoke this callback when we
  47     /// encounter an actual cycle. `cycle` is an iterator that starts
  48     /// at the start of the cycle in the stack and walks **toward the
  49     /// top**.
  50     ///
  51     /// In other words, if we had O1 which required O2 which required
  52     /// O3 which required O1, we would give an iterator yielding O1,
  53     /// O2, O3 (O1 is not yielded twice).
  54     fn process_backedge<'c, I>(&mut self,
  55                                cycle: I,
  56                                _marker: PhantomData<&'c Self::Obligation>)
  57         where I: Clone + Iterator<Item=&'c Self::Obligation>;
  58 }
  59
  60 /// The result type used by `process_obligation`.
  61 #[derive(Debug)]
  62 pub enum ProcessResult<O, E> {
  63     Unchanged,
  64     Changed(Vec<O>),
  65     Error(E),
  66 }
  67
  68 pub struct ObligationForest<O: ForestObligation> {
  69     /// The list of obligations. In between calls to
  70     /// `process_obligations`, this list only contains nodes in the
  71     /// `Pending` or `Success` state (with a non-zero number of
  72     /// incomplete children). During processing, some of those nodes
  73     /// may be changed to the error state, or we may find that they
  74     /// are completed (That is, `num_incomplete_children` drops to 0).
  75     /// At the end of processing, those nodes will be removed by a
  76     /// call to `compress`.
  77     ///
  78     /// At all times we maintain the invariant that every node appears
  79     /// at a higher index than its parent. This is needed by the
  80     /// backtrace iterator (which uses `split_at`).
  81     nodes: Vec<Node<O>>,
  82     /// A cache of predicates that have been successfully completed.
  83     done_cache: FxHashSet<O::Predicate>,
  84     /// An cache of the nodes in `nodes`, indexed by predicate.
  85     waiting_cache: FxHashMap<O::Predicate, NodeIndex>,
  86     scratch: Option<Vec<usize>>,
  87 }
  88
  89 #[derive(Debug)]
  90 struct Node<O> {
  91     obligation: O,
  92     state: Cell<NodeState>,
  93
  94     /// Obligations that depend on this obligation for their
  95     /// completion. They must all be in a non-pending state.
  96     dependents: Vec<NodeIndex>,
  97     /// The parent of a node - the original obligation of
  98     /// which it is a subobligation. Except for error reporting,
  99     /// this is just another member of `dependents`.
 100     parent: Option<NodeIndex>,
 101 }
 102
 103 /// The state of one node in some tree within the forest. This
 104 /// represents the current state of processing for the obligation (of
 105 /// type `O`) associated with this node.
 106 ///
 107 /// Outside of ObligationForest methods, nodes should be either Pending
 108 /// or Waiting.
 109 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
 110 enum NodeState {
 111     /// Obligations for which selection had not yet returned a
 112     /// non-ambiguous result.
 113     Pending,
 114
 115     /// This obligation was selected successfully, but may or
 116     /// may not have subobligations.
 117     Success,
 118
 119     /// This obligation was selected successfully, but it has
 120     /// a pending subobligation.
 121     Waiting,
 122
 123     /// This obligation, along with its subobligations, are complete,
 124     /// and will be removed in the next collection.
 125     Done,
 126
 127     /// This obligation was resolved to an error. Error nodes are
 128     /// removed from the vector by the compression step.
 129     Error,
 130
 131     /// This is a temporary state used in DFS loops to detect cycles,
 132     /// it should not exist outside of these DFSes.
 133     OnDfsStack,
 134 }
 135
 136 #[derive(Debug)]
 137 pub struct Outcome<O, E> {
 138     /// Obligations that were completely evaluated, including all
 139     /// (transitive) subobligations.
 140     pub completed: Vec<O>,
 141
 142     /// Backtrace of obligations that were found to be in error.
 143     pub errors: Vec<Error<O, E>>,
 144
 145     /// If true, then we saw no successful obligations, which means
 146     /// there is no point in further iteration. This is based on the
 147     /// assumption that when trait matching returns `Error` or
 148     /// `Unchanged`, those results do not affect environmental
 149     /// inference state. (Note that if we invoke `process_obligations`
 150     /// with no pending obligations, stalled will be true.)
 151     pub stalled: bool,
 152 }
 153
 154 #[derive(Debug, PartialEq, Eq)]
 155 pub struct Error<O, E> {
 156     pub error: E,
 157     pub backtrace: Vec<O>,
 158 }
 159
 160 impl<O: ForestObligation> ObligationForest<O> {
 161     pub fn new() -> ObligationForest<O> {
 162         ObligationForest {
 163             nodes: vec![],
 164             done_cache: FxHashSet(),
 165             waiting_cache: FxHashMap(),
 166             scratch: Some(vec![]),
 167         }
 168     }
 169
 170     /// Return the total number of nodes in the forest that have not
 171     /// yet been fully resolved.
 172     pub fn len(&self) -> usize {
 173         self.nodes.len()
 174     }
 175
 176     /// Registers an obligation
 177     ///
 178     /// This CAN be done in a snapshot
 179     pub fn register_obligation(&mut self, obligation: O) {
 180         // Ignore errors here - there is no guarantee of success.
 181         let _ = self.register_obligation_at(obligation, None);
 182     }
 183
 184     // returns Err(()) if we already know this obligation failed.
 185     fn register_obligation_at(&mut self, obligation: O, parent: Option<NodeIndex>)
 186                               -> Result<(), ()>
 187     {
 188         if self.done_cache.contains(obligation.as_predicate()) {
 189             return Ok(())
 190         }
 191
 192         match self.waiting_cache.entry(obligation.as_predicate().clone()) {
 193             Entry::Occupied(o) => {
 194                 debug!("register_obligation_at({:?}, {:?}) - duplicate of {:?}!",
 195                        obligation, parent, o.get());
 196                 if let Some(parent) = parent {
 197                     if self.nodes[o.get().get()].dependents.contains(&parent) {
 198                         debug!("register_obligation_at({:?}, {:?}) - duplicate subobligation",
 199                                obligation, parent);
 200                     } else {
 201                         self.nodes[o.get().get()].dependents.push(parent);
 202                     }
 203                 }
 204                 if let NodeState::Error = self.nodes[o.get().get()].state.get() {
 205                     Err(())
 206                 } else {
 207                     Ok(())
 208                 }
 209             }
 210             Entry::Vacant(v) => {
 211                 debug!("register_obligation_at({:?}, {:?}) - ok, new index is {}",
 212                        obligation, parent, self.nodes.len());
 213                 v.insert(NodeIndex::new(self.nodes.len()));
 214                 self.nodes.push(Node::new(parent, obligation));
 215                 Ok(())
 216             }
 217         }
 218     }
 219
 220     /// Convert all remaining obligations to the given error.
 221     ///
 222     /// This cannot be done during a snapshot.
 223     pub fn to_errors<E: Clone>(&mut self, error: E) -> Vec<Error<O, E>> {
 224         let mut errors = vec![];
 225         for index in 0..self.nodes.len() {
 226             if let NodeState::Pending = self.nodes[index].state.get() {
 227                 let backtrace = self.error_at(index);
 228                 errors.push(Error {
 229                     error: error.clone(),
 230                     backtrace,
 231                 });
 232             }
 233         }
 234         let successful_obligations = self.compress();
 235         assert!(successful_obligations.is_empty());
 236         errors
 237     }
 238
 239     /// Returns the set of obligations that are in a pending state.
 240     pub fn map_pending_obligations<P, F>(&self, f: F) -> Vec<P>
 241         where F: Fn(&O) -> P
 242     {
 243         self.nodes
 244             .iter()
 245             .filter(|n| n.state.get() == NodeState::Pending)
 246             .map(|n| f(&n.obligation))
 247             .collect()
 248     }
 249
 250     /// Perform a pass through the obligation list. This must
 251     /// be called in a loop until `outcome.stalled` is false.
 252     ///
 253     /// This CANNOT be unrolled (presently, at least).
 254     pub fn process_obligations<P>(&mut self, processor: &mut P) -> Outcome<O, P::Error>
 255         where P: ObligationProcessor<Obligation=O>
 256     {
 257         debug!("process_obligations(len={})", self.nodes.len());
 258
 259         let mut errors = vec![];
 260         let mut stalled = true;
 261
 262         for index in 0..self.nodes.len() {
 263             debug!("process_obligations: node {} == {:?}",
 264                    index,
 265                    self.nodes[index]);
 266
 267             let result = match self.nodes[index] {
 268                 Node { state: ref _state, ref mut obligation, .. }
 269                     if _state.get() == NodeState::Pending =>
 270                 {
 271                     processor.process_obligation(obligation)
 272                 }
 273                 _ => continue
 274             };
 275
 276             debug!("process_obligations: node {} got result {:?}",
 277                    index,
 278                    result);
 279
 280             match result {
 281                 ProcessResult::Unchanged => {
 282                     // No change in state.
 283                 }
 284                 ProcessResult::Changed(children) => {
 285                     // We are not (yet) stalled.
 286                     stalled = false;
 287                     self.nodes[index].state.set(NodeState::Success);
 288
 289                     for child in children {
 290                         let st = self.register_obligation_at(
 291                             child,
 292                             Some(NodeIndex::new(index))
 293                         );
 294                         if let Err(()) = st {
 295                             // error already reported - propagate it
 296                             // to our node.
 297                             self.error_at(index);
 298                         }
 299                     }
 300                 }
 301                 ProcessResult::Error(err) => {
 302                     stalled = false;
 303                     let backtrace = self.error_at(index);
 304                     errors.push(Error {
 305                         error: err,
 306                         backtrace,
 307                     });
 308                 }
 309             }
 310         }
 311
 312         if stalled {
 313             // There's no need to perform marking, cycle processing and compression when nothing
 314             // changed.
 315             return Outcome {
 316                 completed: vec![],
 317                 errors,
 318                 stalled,
 319             };
 320         }
 321
 322         self.mark_as_waiting();
 323         self.process_cycles(processor);
 324
 325         // Now we have to compress the result
 326         let completed_obligations = self.compress();
 327
 328         debug!("process_obligations: complete");
 329
 330         Outcome {
 331             completed: completed_obligations,
 332             errors,
 333             stalled,
 334         }
 335     }
 336
 337     /// Mark all NodeState::Success nodes as NodeState::Done and
 338     /// report all cycles between them. This should be called
 339     /// after `mark_as_waiting` marks all nodes with pending
 340     /// subobligations as NodeState::Waiting.
 341     fn process_cycles<P>(&mut self, processor: &mut P)
 342         where P: ObligationProcessor<Obligation=O>
 343     {
 344         let mut stack = self.scratch.take().unwrap();
 345         debug_assert!(stack.is_empty());
 346
 347         debug!("process_cycles()");
 348
 349         for index in 0..self.nodes.len() {
 350             // For rustc-benchmarks/inflate-0.1.0 this state test is extremely
 351             // hot and the state is almost always `Pending` or `Waiting`. It's
 352             // a win to handle the no-op cases immediately to avoid the cost of
 353             // the function call.
 354             let state = self.nodes[index].state.get();
 355             match state {
 356                 NodeState::Waiting | NodeState::Pending | NodeState::Done | NodeState::Error => {},
 357                 _ => self.find_cycles_from_node(&mut stack, processor, index),
 358             }
 359         }
 360
 361         debug!("process_cycles: complete");
 362
 363         debug_assert!(stack.is_empty());
 364         self.scratch = Some(stack);
 365     }
 366
 367     fn find_cycles_from_node<P>(&self, stack: &mut Vec<usize>,
 368                                 processor: &mut P, index: usize)
 369         where P: ObligationProcessor<Obligation=O>
 370     {
 371         let node = &self.nodes[index];
 372         let state = node.state.get();
 373         match state {
 374             NodeState::OnDfsStack => {
 375                 let index =
 376                     stack.iter().rposition(|n| *n == index).unwrap();
 377                 processor.process_backedge(stack[index..].iter().map(GetObligation(&self.nodes)),
 378                                            PhantomData);
 379             }
 380             NodeState::Success => {
 381                 node.state.set(NodeState::OnDfsStack);
 382                 stack.push(index);
 383                 if let Some(parent) = node.parent {
 384                     self.find_cycles_from_node(stack, processor, parent.get());
 385                 }
 386                 for dependent in &node.dependents {
 387                     self.find_cycles_from_node(stack, processor, dependent.get());
 388                 }
 389                 stack.pop();
 390                 node.state.set(NodeState::Done);
 391             },
 392             NodeState::Waiting | NodeState::Pending => {
 393                 // this node is still reachable from some pending node. We
 394                 // will get to it when they are all processed.
 395             }
 396             NodeState::Done | NodeState::Error => {
 397                 // already processed that node
 398             }
 399         };
 400     }
 401
 402     /// Returns a vector of obligations for `p` and all of its
 403     /// ancestors, putting them into the error state in the process.
 404     fn error_at(&mut self, p: usize) -> Vec<O> {
 405         let mut error_stack = self.scratch.take().unwrap();
 406         let mut trace = vec![];
 407
 408         let mut n = p;
 409         loop {
 410             self.nodes[n].state.set(NodeState::Error);
 411             trace.push(self.nodes[n].obligation.clone());
 412             error_stack.extend(self.nodes[n].dependents.iter().map(|x| x.get()));
 413
 414             // loop to the parent
 415             match self.nodes[n].parent {
 416                 Some(q) => n = q.get(),
 417                 None => break
 418             }
 419         }
 420
 421         while let Some(i) = error_stack.pop() {
 422             let node = &self.nodes[i];
 423
 424             match node.state.get() {
 425                 NodeState::Error => continue,
 426                 _ => node.state.set(NodeState::Error)
 427             }
 428
 429             error_stack.extend(
 430                 node.dependents.iter().cloned().chain(node.parent).map(|x| x.get())
 431             );
 432         }
 433
 434         self.scratch = Some(error_stack);
 435         trace
 436     }
 437
 438     #[inline]
 439     fn mark_neighbors_as_waiting_from(&self, node: &Node<O>) {
 440         if let Some(parent) = node.parent {
 441             self.mark_as_waiting_from(&self.nodes[parent.get()]);
 442         }
 443
 444         for dependent in &node.dependents {
 445             self.mark_as_waiting_from(&self.nodes[dependent.get()]);
 446         }
 447     }
 448
 449     /// Marks all nodes that depend on a pending node as NodeState::Waiting.
 450     fn mark_as_waiting(&self) {
 451         for node in &self.nodes {
 452             if node.state.get() == NodeState::Waiting {
 453                 node.state.set(NodeState::Success);
 454             }
 455         }
 456
 457         for node in &self.nodes {
 458             if node.state.get() == NodeState::Pending {
 459                 self.mark_neighbors_as_waiting_from(node);
 460             }
 461         }
 462     }
 463
 464     fn mark_as_waiting_from(&self, node: &Node<O>) {
 465         match node.state.get() {
 466             NodeState::Waiting | NodeState::Error | NodeState::OnDfsStack => return,
 467             NodeState::Success => node.state.set(NodeState::Waiting),
 468             NodeState::Pending | NodeState::Done => {},
 469         }
 470
 471         self.mark_neighbors_as_waiting_from(node);
 472     }
 473
 474     /// Compresses the vector, removing all popped nodes. This adjusts
 475     /// the indices and hence invalidates any outstanding
 476     /// indices. Cannot be used during a transaction.
 477     ///
 478     /// Beforehand, all nodes must be marked as `Done` and no cycles
 479     /// on these nodes may be present. This is done by e.g. `process_cycles`.
 480     #[inline(never)]
 481     fn compress(&mut self) -> Vec<O> {
 482         let nodes_len = self.nodes.len();
 483         let mut node_rewrites: Vec<_> = self.scratch.take().unwrap();
 484         node_rewrites.extend(0..nodes_len);
 485         let mut dead_nodes = 0;
 486
 487         // Now move all popped nodes to the end. Try to keep the order.
 488         //
 489         // LOOP INVARIANT:
 490         //     self.nodes[0..i - dead_nodes] are the first remaining nodes
 491         //     self.nodes[i - dead_nodes..i] are all dead
 492         //     self.nodes[i..] are unchanged
 493         for i in 0..self.nodes.len() {
 494             match self.nodes[i].state.get() {
 495                 NodeState::Pending | NodeState::Waiting => {
 496                     if dead_nodes > 0 {
 497                         self.nodes.swap(i, i - dead_nodes);
 498                         node_rewrites[i] -= dead_nodes;
 499                     }
 500                 }
 501                 NodeState::Done => {
 502                     self.waiting_cache.remove(self.nodes[i].obligation.as_predicate());
 503                     // FIXME(HashMap): why can't I get my key back?
 504                     self.done_cache.insert(self.nodes[i].obligation.as_predicate().clone());
 505                     node_rewrites[i] = nodes_len;
 506                     dead_nodes += 1;
 507                 }
 508                 NodeState::Error => {
 509                     // We *intentionally* remove the node from the cache at this point. Otherwise
 510                     // tests must come up with a different type on every type error they
 511                     // check against.
 512                     self.waiting_cache.remove(self.nodes[i].obligation.as_predicate());
 513                     node_rewrites[i] = nodes_len;
 514                     dead_nodes += 1;
 515                 }
 516                 NodeState::OnDfsStack | NodeState::Success => unreachable!()
 517             }
 518         }
 519
 520         // No compression needed.
 521         if dead_nodes == 0 {
 522             node_rewrites.truncate(0);
 523             self.scratch = Some(node_rewrites);
 524             return vec![];
 525         }
 526
 527         // Pop off all the nodes we killed and extract the success
 528         // stories.
 529         let successful = (0..dead_nodes)
 530                              .map(|_| self.nodes.pop().unwrap())
 531                              .flat_map(|node| {
 532                                  match node.state.get() {
 533                                      NodeState::Error => None,
 534                                      NodeState::Done => Some(node.obligation),
 535                                      _ => unreachable!()
 536                                  }
 537                              })
 538             .collect();
 539         self.apply_rewrites(&node_rewrites);
 540
 541         node_rewrites.truncate(0);
 542         self.scratch = Some(node_rewrites);
 543
 544         successful
 545     }
 546
 547     fn apply_rewrites(&mut self, node_rewrites: &[usize]) {
 548         let nodes_len = node_rewrites.len();
 549
 550         for node in &mut self.nodes {
 551             if let Some(index) = node.parent {
 552                 let new_index = node_rewrites[index.get()];
 553                 if new_index >= nodes_len {
 554                     // parent dead due to error
 555                     node.parent = None;
 556                 } else {
 557                     node.parent = Some(NodeIndex::new(new_index));
 558                 }
 559             }
 560
 561             let mut i = 0;
 562             while i < node.dependents.len() {
 563                 let new_index = node_rewrites[node.dependents[i].get()];
 564                 if new_index >= nodes_len {
 565                     node.dependents.swap_remove(i);
 566                 } else {
 567                     node.dependents[i] = NodeIndex::new(new_index);
 568                     i += 1;
 569                 }
 570             }
 571         }
 572
 573         let mut kill_list = vec![];
 574         for (predicate, index) in self.waiting_cache.iter_mut() {
 575             let new_index = node_rewrites[index.get()];
 576             if new_index >= nodes_len {
 577                 kill_list.push(predicate.clone());
 578             } else {
 579                 *index = NodeIndex::new(new_index);
 580             }
 581         }
 582
 583         for predicate in kill_list { self.waiting_cache.remove(&predicate); }
 584     }
 585 }
 586
 587 impl<O> Node<O> {
 588     fn new(parent: Option<NodeIndex>, obligation: O) -> Node<O> {
 589         Node {
 590             obligation,
 591             parent,
 592             state: Cell::new(NodeState::Pending),
 593             dependents: vec![],
 594         }
 595     }
 596 }
 597
 598 // I need a Clone closure
 599 #[derive(Clone)]
 600 struct GetObligation<'a, O: 'a>(&'a [Node<O>]);
 601
 602 impl<'a, 'b, O> FnOnce<(&'b usize,)> for GetObligation<'a, O> {
 603     type Output = &'a O;
 604     extern "rust-call" fn call_once(self, args: (&'b usize,)) -> &'a O {
 605         &self.0[*args.0].obligation
 606     }
 607 }
 608
 609 impl<'a, 'b, O> FnMut<(&'b usize,)> for GetObligation<'a, O> {
 610     extern "rust-call" fn call_mut(&mut self, args: (&'b usize,)) -> &'a O {
 611         &self.0[*args.0].obligation
 612     }
 613 }