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                           -> Result<Option<Vec<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 struct SnapshotData {
  61     node_len: usize,
  62     cache_list_len: usize,
  63 }
  64
  65 pub struct ObligationForest<O: ForestObligation> {
  66     /// The list of obligations. In between calls to
  67     /// `process_obligations`, this list only contains nodes in the
  68     /// `Pending` or `Success` state (with a non-zero number of
  69     /// incomplete children). During processing, some of those nodes
  70     /// may be changed to the error state, or we may find that they
  71     /// are completed (That is, `num_incomplete_children` drops to 0).
  72     /// At the end of processing, those nodes will be removed by a
  73     /// call to `compress`.
  74     ///
  75     /// At all times we maintain the invariant that every node appears
  76     /// at a higher index than its parent. This is needed by the
  77     /// backtrace iterator (which uses `split_at`).
  78     nodes: Vec<Node<O>>,
  79     /// A cache of predicates that have been successfully completed.
  80     done_cache: FxHashSet<O::Predicate>,
  81     /// An cache of the nodes in `nodes`, indexed by predicate.
  82     waiting_cache: FxHashMap<O::Predicate, NodeIndex>,
  83     /// A list of the obligations added in snapshots, to allow
  84     /// for their removal.
  85     cache_list: Vec<O::Predicate>,
  86     snapshots: Vec<SnapshotData>,
  87     scratch: Option<Vec<usize>>,
  88 }
  89
  90 pub struct Snapshot {
  91     len: usize,
  92 }
  93
  94 #[derive(Debug)]
  95 struct Node<O> {
  96     obligation: O,
  97     state: Cell<NodeState>,
  98
  99     /// Obligations that depend on this obligation for their
 100     /// completion. They must all be in a non-pending state.
 101     dependents: Vec<NodeIndex>,
 102     /// The parent of a node - the original obligation of
 103     /// which it is a subobligation. Except for error reporting,
 104     /// this is just another member of `dependents`.
 105     parent: Option<NodeIndex>,
 106 }
 107
 108 /// The state of one node in some tree within the forest. This
 109 /// represents the current state of processing for the obligation (of
 110 /// type `O`) associated with this node.
 111 ///
 112 /// Outside of ObligationForest methods, nodes should be either Pending
 113 /// or Waiting.
 114 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
 115 enum NodeState {
 116     /// Obligations for which selection had not yet returned a
 117     /// non-ambiguous result.
 118     Pending,
 119
 120     /// This obligation was selected successfuly, but may or
 121     /// may not have subobligations.
 122     Success,
 123
 124     /// This obligation was selected sucessfully, but it has
 125     /// a pending subobligation.
 126     Waiting,
 127
 128     /// This obligation, along with its subobligations, are complete,
 129     /// and will be removed in the next collection.
 130     Done,
 131
 132     /// This obligation was resolved to an error. Error nodes are
 133     /// removed from the vector by the compression step.
 134     Error,
 135
 136     /// This is a temporary state used in DFS loops to detect cycles,
 137     /// it should not exist outside of these DFSes.
 138     OnDfsStack,
 139 }
 140
 141 #[derive(Debug)]
 142 pub struct Outcome<O, E> {
 143     /// Obligations that were completely evaluated, including all
 144     /// (transitive) subobligations.
 145     pub completed: Vec<O>,
 146
 147     /// Backtrace of obligations that were found to be in error.
 148     pub errors: Vec<Error<O, E>>,
 149
 150     /// If true, then we saw no successful obligations, which means
 151     /// there is no point in further iteration. This is based on the
 152     /// assumption that when trait matching returns `Err` or
 153     /// `Ok(None)`, those results do not affect environmental
 154     /// inference state. (Note that if we invoke `process_obligations`
 155     /// with no pending obligations, stalled will be true.)
 156     pub stalled: bool,
 157 }
 158
 159 #[derive(Debug, PartialEq, Eq)]
 160 pub struct Error<O, E> {
 161     pub error: E,
 162     pub backtrace: Vec<O>,
 163 }
 164
 165 impl<O: ForestObligation> ObligationForest<O> {
 166     pub fn new() -> ObligationForest<O> {
 167         ObligationForest {
 168             nodes: vec![],
 169             snapshots: vec![],
 170             done_cache: FxHashSet(),
 171             waiting_cache: FxHashMap(),
 172             cache_list: vec![],
 173             scratch: Some(vec![]),
 174         }
 175     }
 176
 177     /// Return the total number of nodes in the forest that have not
 178     /// yet been fully resolved.
 179     pub fn len(&self) -> usize {
 180         self.nodes.len()
 181     }
 182
 183     pub fn start_snapshot(&mut self) -> Snapshot {
 184         self.snapshots.push(SnapshotData {
 185             node_len: self.nodes.len(),
 186             cache_list_len: self.cache_list.len()
 187         });
 188         Snapshot { len: self.snapshots.len() }
 189     }
 190
 191     pub fn commit_snapshot(&mut self, snapshot: Snapshot) {
 192         assert_eq!(snapshot.len, self.snapshots.len());
 193         let info = self.snapshots.pop().unwrap();
 194         assert!(self.nodes.len() >= info.node_len);
 195         assert!(self.cache_list.len() >= info.cache_list_len);
 196     }
 197
 198     pub fn rollback_snapshot(&mut self, snapshot: Snapshot) {
 199         // Check that we are obeying stack discipline.
 200         assert_eq!(snapshot.len, self.snapshots.len());
 201         let info = self.snapshots.pop().unwrap();
 202
 203         for entry in &self.cache_list[info.cache_list_len..] {
 204             self.done_cache.remove(entry);
 205             self.waiting_cache.remove(entry);
 206         }
 207
 208         self.nodes.truncate(info.node_len);
 209         self.cache_list.truncate(info.cache_list_len);
 210     }
 211
 212     pub fn in_snapshot(&self) -> bool {
 213         !self.snapshots.is_empty()
 214     }
 215
 216     /// Registers an obligation
 217     ///
 218     /// This CAN be done in a snapshot
 219     pub fn register_obligation(&mut self, obligation: O) {
 220         // Ignore errors here - there is no guarantee of success.
 221         let _ = self.register_obligation_at(obligation, None);
 222     }
 223
 224     // returns Err(()) if we already know this obligation failed.
 225     fn register_obligation_at(&mut self, obligation: O, parent: Option<NodeIndex>)
 226                               -> Result<(), ()>
 227     {
 228         if self.done_cache.contains(obligation.as_predicate()) {
 229             return Ok(())
 230         }
 231
 232         match self.waiting_cache.entry(obligation.as_predicate().clone()) {
 233             Entry::Occupied(o) => {
 234                 debug!("register_obligation_at({:?}, {:?}) - duplicate of {:?}!",
 235                        obligation, parent, o.get());
 236                 if let Some(parent) = parent {
 237                     if self.nodes[o.get().get()].dependents.contains(&parent) {
 238                         debug!("register_obligation_at({:?}, {:?}) - duplicate subobligation",
 239                                obligation, parent);
 240                     } else {
 241                         self.nodes[o.get().get()].dependents.push(parent);
 242                     }
 243                 }
 244                 if let NodeState::Error = self.nodes[o.get().get()].state.get() {
 245                     Err(())
 246                 } else {
 247                     Ok(())
 248                 }
 249             }
 250             Entry::Vacant(v) => {
 251                 debug!("register_obligation_at({:?}, {:?}) - ok, new index is {}",
 252                        obligation, parent, self.nodes.len());
 253                 v.insert(NodeIndex::new(self.nodes.len()));
 254                 self.cache_list.push(obligation.as_predicate().clone());
 255                 self.nodes.push(Node::new(parent, obligation));
 256                 Ok(())
 257             }
 258         }
 259     }
 260
 261     /// Convert all remaining obligations to the given error.
 262     ///
 263     /// This cannot be done during a snapshot.
 264     pub fn to_errors<E: Clone>(&mut self, error: E) -> Vec<Error<O, E>> {
 265         assert!(!self.in_snapshot());
 266         let mut errors = vec![];
 267         for index in 0..self.nodes.len() {
 268             if let NodeState::Pending = self.nodes[index].state.get() {
 269                 let backtrace = self.error_at(index);
 270                 errors.push(Error {
 271                     error: error.clone(),
 272                     backtrace: backtrace,
 273                 });
 274             }
 275         }
 276         let successful_obligations = self.compress();
 277         assert!(successful_obligations.is_empty());
 278         errors
 279     }
 280
 281     /// Returns the set of obligations that are in a pending state.
 282     pub fn pending_obligations(&self) -> Vec<O>
 283         where O: Clone
 284     {
 285         self.nodes
 286             .iter()
 287             .filter(|n| n.state.get() == NodeState::Pending)
 288             .map(|n| n.obligation.clone())
 289             .collect()
 290     }
 291
 292     /// Perform a pass through the obligation list. This must
 293     /// be called in a loop until `outcome.stalled` is false.
 294     ///
 295     /// This CANNOT be unrolled (presently, at least).
 296     pub fn process_obligations<P>(&mut self, processor: &mut P) -> Outcome<O, P::Error>
 297         where P: ObligationProcessor<Obligation=O>
 298     {
 299         debug!("process_obligations(len={})", self.nodes.len());
 300         assert!(!self.in_snapshot()); // cannot unroll this action
 301
 302         let mut errors = vec![];
 303         let mut stalled = true;
 304
 305         for index in 0..self.nodes.len() {
 306             debug!("process_obligations: node {} == {:?}",
 307                    index,
 308                    self.nodes[index]);
 309
 310             let result = match self.nodes[index] {
 311                 Node { state: ref _state, ref mut obligation, .. }
 312                     if _state.get() == NodeState::Pending =>
 313                 {
 314                     processor.process_obligation(obligation)
 315                 }
 316                 _ => continue
 317             };
 318
 319             debug!("process_obligations: node {} got result {:?}",
 320                    index,
 321                    result);
 322
 323             match result {
 324                 Ok(None) => {
 325                     // no change in state
 326                 }
 327                 Ok(Some(children)) => {
 328                     // if we saw a Some(_) result, we are not (yet) stalled
 329                     stalled = false;
 330                     self.nodes[index].state.set(NodeState::Success);
 331
 332                     for child in children {
 333                         let st = self.register_obligation_at(
 334                             child,
 335                             Some(NodeIndex::new(index))
 336                         );
 337                         if let Err(()) = st {
 338                             // error already reported - propagate it
 339                             // to our node.
 340                             self.error_at(index);
 341                         }
 342                     }
 343                 }
 344                 Err(err) => {
 345                     stalled = false;
 346                     let backtrace = self.error_at(index);
 347                     errors.push(Error {
 348                         error: err,
 349                         backtrace: backtrace,
 350                     });
 351                 }
 352             }
 353         }
 354
 355         if stalled {
 356             // There's no need to perform marking, cycle processing and compression when nothing
 357             // changed.
 358             return Outcome {
 359                 completed: vec![],
 360                 errors: errors,
 361                 stalled: stalled,
 362             };
 363         }
 364
 365         self.mark_as_waiting();
 366         self.process_cycles(processor);
 367
 368         // Now we have to compress the result
 369         let completed_obligations = self.compress();
 370
 371         debug!("process_obligations: complete");
 372
 373         Outcome {
 374             completed: completed_obligations,
 375             errors: errors,
 376             stalled: stalled,
 377         }
 378     }
 379
 380     /// Mark all NodeState::Success nodes as NodeState::Done and
 381     /// report all cycles between them. This should be called
 382     /// after `mark_as_waiting` marks all nodes with pending
 383     /// subobligations as NodeState::Waiting.
 384     fn process_cycles<P>(&mut self, processor: &mut P)
 385         where P: ObligationProcessor<Obligation=O>
 386     {
 387         let mut stack = self.scratch.take().unwrap();
 388         debug_assert!(stack.is_empty());
 389
 390         debug!("process_cycles()");
 391
 392         for index in 0..self.nodes.len() {
 393             // For rustc-benchmarks/inflate-0.1.0 this state test is extremely
 394             // hot and the state is almost always `Pending` or `Waiting`. It's
 395             // a win to handle the no-op cases immediately to avoid the cost of
 396             // the function call.
 397             let state = self.nodes[index].state.get();
 398             match state {
 399                 NodeState::Waiting | NodeState::Pending | NodeState::Done | NodeState::Error => {},
 400                 _ => self.find_cycles_from_node(&mut stack, processor, index),
 401             }
 402         }
 403
 404         debug!("process_cycles: complete");
 405
 406         debug_assert!(stack.is_empty());
 407         self.scratch = Some(stack);
 408     }
 409
 410     fn find_cycles_from_node<P>(&self, stack: &mut Vec<usize>,
 411                                 processor: &mut P, index: usize)
 412         where P: ObligationProcessor<Obligation=O>
 413     {
 414         let node = &self.nodes[index];
 415         let state = node.state.get();
 416         match state {
 417             NodeState::OnDfsStack => {
 418                 let index =
 419                     stack.iter().rposition(|n| *n == index).unwrap();
 420                 processor.process_backedge(stack[index..].iter().map(GetObligation(&self.nodes)),
 421                                            PhantomData);
 422             }
 423             NodeState::Success => {
 424                 node.state.set(NodeState::OnDfsStack);
 425                 stack.push(index);
 426                 if let Some(parent) = node.parent {
 427                     self.find_cycles_from_node(stack, processor, parent.get());
 428                 }
 429                 for dependent in &node.dependents {
 430                     self.find_cycles_from_node(stack, processor, dependent.get());
 431                 }
 432                 stack.pop();
 433                 node.state.set(NodeState::Done);
 434             },
 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.
 438             }
 439             NodeState::Done | NodeState::Error => {
 440                 // already processed that node
 441             }
 442         };
 443     }
 444
 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![];
 450
 451         let mut n = p;
 452         loop {
 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()));
 456
 457             // loop to the parent
 458             match self.nodes[n].parent {
 459                 Some(q) => n = q.get(),
 460                 None => break
 461             }
 462         }
 463
 464         loop {
 465             // non-standard `while let` to bypass #6393
 466             let i = match error_stack.pop() {
 467                 Some(i) => i,
 468                 None => break
 469             };
 470
 471             let node = &self.nodes[i];
 472
 473             match node.state.get() {
 474                 NodeState::Error => continue,
 475                 _ => node.state.set(NodeState::Error)
 476             }
 477
 478             error_stack.extend(
 479                 node.dependents.iter().cloned().chain(node.parent).map(|x| x.get())
 480             );
 481         }
 482
 483         self.scratch = Some(error_stack);
 484         trace
 485     }
 486
 487     #[inline]
 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()]);
 491         }
 492
 493         for dependent in &node.dependents {
 494             self.mark_as_waiting_from(&self.nodes[dependent.get()]);
 495         }
 496     }
 497
 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);
 503             }
 504         }
 505
 506         for node in &self.nodes {
 507             if node.state.get() == NodeState::Pending {
 508                 self.mark_neighbors_as_waiting_from(node);
 509             }
 510         }
 511     }
 512
 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 => {},
 518         }
 519
 520         self.mark_neighbors_as_waiting_from(node);
 521     }
 522
 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.
 526     ///
 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`.
 529     #[inline(never)]
 530     fn compress(&mut self) -> Vec<O> {
 531         assert!(!self.in_snapshot()); // didn't write code to unroll this action
 532
 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;
 537
 538         // Now move all popped nodes to the end. Try to keep the order.
 539         //
 540         // LOOP INVARIANT:
 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 => {
 547                     if dead_nodes > 0 {
 548                         self.nodes.swap(i, i - dead_nodes);
 549                         node_rewrites[i] -= dead_nodes;
 550                     }
 551                 }
 552                 NodeState::Done => {
 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;
 557                     dead_nodes += 1;
 558                 }
 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
 562                     // check against.
 563                     self.waiting_cache.remove(self.nodes[i].obligation.as_predicate());
 564                     node_rewrites[i] = nodes_len;
 565                     dead_nodes += 1;
 566                 }
 567                 NodeState::OnDfsStack | NodeState::Success => unreachable!()
 568             }
 569         }
 570
 571         // No compression needed.
 572         if dead_nodes == 0 {
 573             node_rewrites.truncate(0);
 574             self.scratch = Some(node_rewrites);
 575             return vec![];
 576         }
 577
 578         // Pop off all the nodes we killed and extract the success
 579         // stories.
 580         let successful = (0..dead_nodes)
 581                              .map(|_| self.nodes.pop().unwrap())
 582                              .flat_map(|node| {
 583                                  match node.state.get() {
 584                                      NodeState::Error => None,
 585                                      NodeState::Done => Some(node.obligation),
 586                                      _ => unreachable!()
 587                                  }
 588                              })
 589             .collect();
 590         self.apply_rewrites(&node_rewrites);
 591
 592         node_rewrites.truncate(0);
 593         self.scratch = Some(node_rewrites);
 594
 595         successful
 596     }
 597
 598     fn apply_rewrites(&mut self, node_rewrites: &[usize]) {
 599         let nodes_len = node_rewrites.len();
 600
 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
 606                     node.parent = None;
 607                 } else {
 608                     node.parent = Some(NodeIndex::new(new_index));
 609                 }
 610             }
 611
 612             let mut i = 0;
 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);
 617                 } else {
 618                     node.dependents[i] = NodeIndex::new(new_index);
 619                     i += 1;
 620                 }
 621             }
 622         }
 623
 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());
 629             } else {
 630                 *index = NodeIndex::new(new_index);
 631             }
 632         }
 633
 634         for predicate in kill_list { self.waiting_cache.remove(&predicate); }
 635     }
 636 }
 637
 638 impl<O> Node<O> {
 639     fn new(parent: Option<NodeIndex>, obligation: O) -> Node<O> {
 640         Node {
 641             obligation: obligation,
 642             parent: parent,
 643             state: Cell::new(NodeState::Pending),
 644             dependents: vec![],
 645         }
 646     }
 647 }
 648
 649 // I need a Clone closure
 650 #[derive(Clone)]
 651 struct GetObligation<'a, O: 'a>(&'a [Node<O>]);
 652
 653 impl<'a, 'b, O> FnOnce<(&'b usize,)> for GetObligation<'a, O> {
 654     type Output = &'a O;
 655     extern "rust-call" fn call_once(self, args: (&'b usize,)) -> &'a O {
 656         &self.0[*args.0].obligation
 657     }
 658 }
 659
 660 impl<'a, 'b, O> FnMut<(&'b usize,)> for GetObligation<'a, O> {
 661     extern "rust-call" fn call_mut(&mut self, args: (&'b usize,)) -> &'a O {
 662         &self.0[*args.0].obligation
 663     }
 664 }