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 fnv::{FnvHashMap, FnvHashSet};
  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     fn process_backedge<'c, I>(&mut self, cycle: I,
  47                                _marker: PhantomData<&'c Self::Obligation>)
  48         where I: Clone + Iterator<Item=&'c Self::Obligation>;
  49 }
  50
  51 struct SnapshotData {
  52     node_len: usize,
  53     cache_list_len: usize,
  54 }
  55
  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`.
  65     ///
  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`).
  69     nodes: Vec<Node<O>>,
  70     /// A cache of predicates that have been successfully completed.
  71     done_cache: FnvHashSet<O::Predicate>,
  72     /// An cache of the nodes in `nodes`, indexed by predicate.
  73     waiting_cache: FnvHashMap<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>>,
  79 }
  80
  81 pub struct Snapshot {
  82     len: usize,
  83 }
  84
  85 #[derive(Debug)]
  86 struct Node<O> {
  87     obligation: O,
  88     state: Cell<NodeState>,
  89
  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>,
  97 }
  98
  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.
 102 ///
 103 /// Outside of ObligationForest methods, nodes should be either Pending
 104 /// or Waiting.
 105 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
 106 enum NodeState {
 107     /// Obligations for which selection had not yet returned a
 108     /// non-ambiguous result.
 109     Pending,
 110
 111     /// This obligation was selected successfuly, but may or
 112     /// may not have subobligations.
 113     Success,
 114
 115     /// This obligation was selected sucessfully, but it has
 116     /// a pending subobligation.
 117     Waiting,
 118
 119     /// This obligation, along with its subobligations, are complete,
 120     /// and will be removed in the next collection.
 121     Done,
 122
 123     /// This obligation was resolved to an error. Error nodes are
 124     /// removed from the vector by the compression step.
 125     Error,
 126
 127     /// This is a temporary state used in DFS loops to detect cycles,
 128     /// it should not exist outside of these DFSes.
 129     OnDfsStack,
 130 }
 131
 132 #[derive(Debug)]
 133 pub struct Outcome<O, E> {
 134     /// Obligations that were completely evaluated, including all
 135     /// (transitive) subobligations.
 136     pub completed: Vec<O>,
 137
 138     /// Backtrace of obligations that were found to be in error.
 139     pub errors: Vec<Error<O, E>>,
 140
 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.)
 147     pub stalled: bool,
 148 }
 149
 150 #[derive(Debug, PartialEq, Eq)]
 151 pub struct Error<O, E> {
 152     pub error: E,
 153     pub backtrace: Vec<O>,
 154 }
 155
 156 impl<O: ForestObligation> ObligationForest<O> {
 157     pub fn new() -> ObligationForest<O> {
 158         ObligationForest {
 159             nodes: vec![],
 160             snapshots: vec![],
 161             done_cache: FnvHashSet(),
 162             waiting_cache: FnvHashMap(),
 163             cache_list: vec![],
 164             scratch: Some(vec![]),
 165         }
 166     }
 167
 168     /// Return the total number of nodes in the forest that have not
 169     /// yet been fully resolved.
 170     pub fn len(&self) -> usize {
 171         self.nodes.len()
 172     }
 173
 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()
 178         });
 179         Snapshot { len: self.snapshots.len() }
 180     }
 181
 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);
 187     }
 188
 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();
 193
 194         for entry in &self.cache_list[info.cache_list_len..] {
 195             self.done_cache.remove(entry);
 196             self.waiting_cache.remove(entry);
 197         }
 198
 199         self.nodes.truncate(info.node_len);
 200         self.cache_list.truncate(info.cache_list_len);
 201     }
 202
 203     pub fn in_snapshot(&self) -> bool {
 204         !self.snapshots.is_empty()
 205     }
 206
 207     /// Registers an obligation
 208     ///
 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);
 213     }
 214
 215     // returns Err(()) if we already know this obligation failed.
 216     fn register_obligation_at(&mut self, obligation: O, parent: Option<NodeIndex>)
 217                               -> Result<(), ()>
 218     {
 219         if self.done_cache.contains(obligation.as_predicate()) {
 220             return Ok(())
 221         }
 222
 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",
 230                                obligation, parent);
 231                     } else {
 232                         self.nodes[o.get().get()].dependents.push(parent);
 233                     }
 234                 }
 235                 if let NodeState::Error = self.nodes[o.get().get()].state.get() {
 236                     Err(())
 237                 } else {
 238                     Ok(())
 239                 }
 240             }
 241             Entry::Vacant(v) => {
 242                 debug!("register_obligation_at({:?}, {:?}) - ok",
 243                        obligation, parent);
 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));
 247                 Ok(())
 248             }
 249         }
 250     }
 251
 252     /// Convert all remaining obligations to the given error.
 253     ///
 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);
 261                 errors.push(Error {
 262                     error: error.clone(),
 263                     backtrace: backtrace,
 264                 });
 265             }
 266         }
 267         let successful_obligations = self.compress();
 268         assert!(successful_obligations.is_empty());
 269         errors
 270     }
 271
 272     /// Returns the set of obligations that are in a pending state.
 273     pub fn pending_obligations(&self) -> Vec<O>
 274         where O: Clone
 275     {
 276         self.nodes
 277             .iter()
 278             .filter(|n| n.state.get() == NodeState::Pending)
 279             .map(|n| n.obligation.clone())
 280             .collect()
 281     }
 282
 283     /// Perform a pass through the obligation list. This must
 284     /// be called in a loop until `outcome.stalled` is false.
 285     ///
 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>
 289     {
 290         debug!("process_obligations(len={})", self.nodes.len());
 291         assert!(!self.in_snapshot()); // cannot unroll this action
 292
 293         let mut errors = vec![];
 294         let mut stalled = true;
 295
 296         for index in 0..self.nodes.len() {
 297             debug!("process_obligations: node {} == {:?}",
 298                    index,
 299                    self.nodes[index]);
 300
 301             let result = match self.nodes[index] {
 302                 Node { state: ref _state, ref mut obligation, .. }
 303                     if _state.get() == NodeState::Pending =>
 304                 {
 305                     processor.process_obligation(obligation)
 306                 }
 307                 _ => continue
 308             };
 309
 310             debug!("process_obligations: node {} got result {:?}",
 311                    index,
 312                    result);
 313
 314             match result {
 315                 Ok(None) => {
 316                     // no change in state
 317                 }
 318                 Ok(Some(children)) => {
 319                     // if we saw a Some(_) result, we are not (yet) stalled
 320                     stalled = false;
 321                     self.nodes[index].state.set(NodeState::Success);
 322
 323                     for child in children {
 324                         let st = self.register_obligation_at(
 325                             child,
 326                             Some(NodeIndex::new(index))
 327                         );
 328                         if let Err(()) = st {
 329                             // error already reported - propagate it
 330                             // to our node.
 331                             self.error_at(index);
 332                         }
 333                     }
 334                 }
 335                 Err(err) => {
 336                     stalled = false;
 337                     let backtrace = self.error_at(index);
 338                     errors.push(Error {
 339                         error: err,
 340                         backtrace: backtrace,
 341                     });
 342                 }
 343             }
 344         }
 345
 346         if stalled {
 347             // There's no need to perform marking, cycle processing and compression when nothing
 348             // changed.
 349             return Outcome {
 350                 completed: vec![],
 351                 errors: errors,
 352                 stalled: stalled,
 353             };
 354         }
 355
 356         self.mark_as_waiting();
 357         self.process_cycles(processor);
 358
 359         // Now we have to compress the result
 360         let completed_obligations = self.compress();
 361
 362         debug!("process_obligations: complete");
 363
 364         Outcome {
 365             completed: completed_obligations,
 366             errors: errors,
 367             stalled: stalled,
 368         }
 369     }
 370
 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>
 377     {
 378         let mut stack = self.scratch.take().unwrap();
 379
 380         for node in 0..self.nodes.len() {
 381             self.find_cycles_from_node(&mut stack, processor, node);
 382         }
 383
 384         self.scratch = Some(stack);
 385     }
 386
 387     fn find_cycles_from_node<P>(&self, stack: &mut Vec<usize>,
 388                                 processor: &mut P, index: usize)
 389         where P: ObligationProcessor<Obligation=O>
 390     {
 391         let node = &self.nodes[index];
 392         let state = node.state.get();
 393         match state {
 394             NodeState::OnDfsStack => {
 395                 let index =
 396                     stack.iter().rposition(|n| *n == index).unwrap();
 397                 // I need a Clone closure
 398                 #[derive(Clone)]
 399                 struct GetObligation<'a, O: 'a>(&'a [Node<O>]);
 400                 impl<'a, 'b, O> FnOnce<(&'b usize,)> for GetObligation<'a, O> {
 401                     type Output = &'a O;
 402                     extern "rust-call" fn call_once(self, args: (&'b usize,)) -> &'a O {
 403                         &self.0[*args.0].obligation
 404                     }
 405                 }
 406                 impl<'a, 'b, O> FnMut<(&'b usize,)> for GetObligation<'a, O> {
 407                     extern "rust-call" fn call_mut(&mut self, args: (&'b usize,)) -> &'a O {
 408                         &self.0[*args.0].obligation
 409                     }
 410                 }
 411
 412                 processor.process_backedge(stack[index..].iter().map(GetObligation(&self.nodes)),
 413                                            PhantomData);
 414             }
 415             NodeState::Success => {
 416                 node.state.set(NodeState::OnDfsStack);
 417                 stack.push(index);
 418                 if let Some(parent) = node.parent {
 419                     self.find_cycles_from_node(stack, processor, parent.get());
 420                 }
 421                 for dependent in &node.dependents {
 422                     self.find_cycles_from_node(stack, processor, dependent.get());
 423                 }
 424                 stack.pop();
 425                 node.state.set(NodeState::Done);
 426             },
 427             NodeState::Waiting | NodeState::Pending => {
 428                 // this node is still reachable from some pending node. We
 429                 // will get to it when they are all processed.
 430             }
 431             NodeState::Done | NodeState::Error => {
 432                 // already processed that node
 433             }
 434         };
 435     }
 436
 437     /// Returns a vector of obligations for `p` and all of its
 438     /// ancestors, putting them into the error state in the process.
 439     fn error_at(&mut self, p: usize) -> Vec<O> {
 440         let mut error_stack = self.scratch.take().unwrap();
 441         let mut trace = vec![];
 442
 443         let mut n = p;
 444         loop {
 445             self.nodes[n].state.set(NodeState::Error);
 446             trace.push(self.nodes[n].obligation.clone());
 447             error_stack.extend(self.nodes[n].dependents.iter().map(|x| x.get()));
 448
 449             // loop to the parent
 450             match self.nodes[n].parent {
 451                 Some(q) => n = q.get(),
 452                 None => break
 453             }
 454         }
 455
 456         loop {
 457             // non-standard `while let` to bypass #6393
 458             let i = match error_stack.pop() {
 459                 Some(i) => i,
 460                 None => break
 461             };
 462
 463             let node = &self.nodes[i];
 464
 465             match node.state.get() {
 466                 NodeState::Error => continue,
 467                 _ => node.state.set(NodeState::Error)
 468             }
 469
 470             error_stack.extend(
 471                 node.dependents.iter().cloned().chain(node.parent).map(|x| x.get())
 472             );
 473         }
 474
 475         self.scratch = Some(error_stack);
 476         trace
 477     }
 478
 479     /// Marks all nodes that depend on a pending node as NodeState;:Waiting.
 480     fn mark_as_waiting(&self) {
 481         for node in &self.nodes {
 482             if node.state.get() == NodeState::Waiting {
 483                 node.state.set(NodeState::Success);
 484             }
 485         }
 486
 487         for node in &self.nodes {
 488             if node.state.get() == NodeState::Pending {
 489                 self.mark_as_waiting_from(node)
 490             }
 491         }
 492     }
 493
 494     fn mark_as_waiting_from(&self, node: &Node<O>) {
 495         match node.state.get() {
 496             NodeState::Pending | NodeState::Done => {},
 497             NodeState::Waiting | NodeState::Error | NodeState::OnDfsStack => return,
 498             NodeState::Success => {
 499                 node.state.set(NodeState::Waiting);
 500             }
 501         }
 502
 503         if let Some(parent) = node.parent {
 504             self.mark_as_waiting_from(&self.nodes[parent.get()]);
 505         }
 506
 507         for dependent in &node.dependents {
 508             self.mark_as_waiting_from(&self.nodes[dependent.get()]);
 509         }
 510     }
 511
 512     /// Compresses the vector, removing all popped nodes. This adjusts
 513     /// the indices and hence invalidates any outstanding
 514     /// indices. Cannot be used during a transaction.
 515     ///
 516     /// Beforehand, all nodes must be marked as `Done` and no cycles
 517     /// on these nodes may be present. This is done by e.g. `process_cycles`.
 518     #[inline(never)]
 519     fn compress(&mut self) -> Vec<O> {
 520         assert!(!self.in_snapshot()); // didn't write code to unroll this action
 521
 522         let nodes_len = self.nodes.len();
 523         let mut node_rewrites: Vec<_> = self.scratch.take().unwrap();
 524         node_rewrites.extend(0..nodes_len);
 525         let mut dead_nodes = 0;
 526
 527         // Now move all popped nodes to the end. Try to keep the order.
 528         //
 529         // LOOP INVARIANT:
 530         //     self.nodes[0..i - dead_nodes] are the first remaining nodes
 531         //     self.nodes[i - dead_nodes..i] are all dead
 532         //     self.nodes[i..] are unchanged
 533         for i in 0..self.nodes.len() {
 534             match self.nodes[i].state.get() {
 535                 NodeState::Done => {
 536                     self.waiting_cache.remove(self.nodes[i].obligation.as_predicate());
 537                     // FIXME(HashMap): why can't I get my key back?
 538                     self.done_cache.insert(self.nodes[i].obligation.as_predicate().clone());
 539                 }
 540                 NodeState::Error => {
 541                     // We *intentionally* remove the node from the cache at this point. Otherwise
 542                     // tests must come up with a different type on every type error they
 543                     // check against.
 544                     self.waiting_cache.remove(self.nodes[i].obligation.as_predicate());
 545                 }
 546                 _ => {}
 547             }
 548
 549             if self.nodes[i].is_popped() {
 550                 node_rewrites[i] = nodes_len;
 551                 dead_nodes += 1;
 552             } else {
 553                 if dead_nodes > 0 {
 554                     self.nodes.swap(i, i - dead_nodes);
 555                     node_rewrites[i] -= dead_nodes;
 556                 }
 557             }
 558         }
 559
 560         // No compression needed.
 561         if dead_nodes == 0 {
 562             node_rewrites.truncate(0);
 563             self.scratch = Some(node_rewrites);
 564             return vec![];
 565         }
 566
 567         // Pop off all the nodes we killed and extract the success
 568         // stories.
 569         let successful = (0..dead_nodes)
 570                              .map(|_| self.nodes.pop().unwrap())
 571                              .flat_map(|node| {
 572                                  match node.state.get() {
 573                                      NodeState::Error => None,
 574                                      NodeState::Done => Some(node.obligation),
 575                                      _ => unreachable!()
 576                                  }
 577                              })
 578             .collect();
 579         self.apply_rewrites(&node_rewrites);
 580
 581         node_rewrites.truncate(0);
 582         self.scratch = Some(node_rewrites);
 583
 584         successful
 585     }
 586
 587     fn apply_rewrites(&mut self, node_rewrites: &[usize]) {
 588         let nodes_len = node_rewrites.len();
 589
 590         for node in &mut self.nodes {
 591             if let Some(index) = node.parent {
 592                 let new_index = node_rewrites[index.get()];
 593                 if new_index >= nodes_len {
 594                     // parent dead due to error
 595                     node.parent = None;
 596                 } else {
 597                     node.parent = Some(NodeIndex::new(new_index));
 598                 }
 599             }
 600
 601             let mut i = 0;
 602             while i < node.dependents.len() {
 603                 let new_index = node_rewrites[node.dependents[i].get()];
 604                 if new_index >= nodes_len {
 605                     node.dependents.swap_remove(i);
 606                 } else {
 607                     node.dependents[i] = NodeIndex::new(new_index);
 608                     i += 1;
 609                 }
 610             }
 611         }
 612
 613         let mut kill_list = vec![];
 614         for (predicate, index) in self.waiting_cache.iter_mut() {
 615             let new_index = node_rewrites[index.get()];
 616             if new_index >= nodes_len {
 617                 kill_list.push(predicate.clone());
 618             } else {
 619                 *index = NodeIndex::new(new_index);
 620             }
 621         }
 622
 623         for predicate in kill_list { self.waiting_cache.remove(&predicate); }
 624     }
 625 }
 626
 627 impl<O> Node<O> {
 628     fn new(parent: Option<NodeIndex>, obligation: O) -> Node<O> {
 629         Node {
 630             obligation: obligation,
 631             parent: parent,
 632             state: Cell::new(NodeState::Pending),
 633             dependents: vec![],
 634         }
 635     }
 636
 637     fn is_popped(&self) -> bool {
 638         match self.state.get() {
 639             NodeState::Pending | NodeState::Waiting => false,
 640             NodeState::Error | NodeState::Done => true,
 641             NodeState::OnDfsStack | NodeState::Success => unreachable!()
 642         }
 643     }
 644 }