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 std::fmt::Debug;
  19 use std::mem;
  20
  21 mod node_index;
  22 use self::node_index::NodeIndex;
  23
  24 mod tree_index;
  25 use self::tree_index::TreeIndex;
  26
  27
  28 #[cfg(test)]
  29 mod test;
  30
  31 pub struct ObligationForest<O, T> {
  32     /// The list of obligations. In between calls to
  33     /// `process_obligations`, this list only contains nodes in the
  34     /// `Pending` or `Success` state (with a non-zero number of
  35     /// incomplete children). During processing, some of those nodes
  36     /// may be changed to the error state, or we may find that they
  37     /// are completed (That is, `num_incomplete_children` drops to 0).
  38     /// At the end of processing, those nodes will be removed by a
  39     /// call to `compress`.
  40     ///
  41     /// At all times we maintain the invariant that every node appears
  42     /// at a higher index than its parent. This is needed by the
  43     /// backtrace iterator (which uses `split_at`).
  44     nodes: Vec<Node<O>>,
  45     trees: Vec<Tree<T>>,
  46     snapshots: Vec<usize>,
  47 }
  48
  49 pub struct Snapshot {
  50     len: usize,
  51 }
  52
  53 struct Tree<T> {
  54     root: NodeIndex,
  55     state: T,
  56 }
  57
  58 struct Node<O> {
  59     state: NodeState<O>,
  60     parent: Option<NodeIndex>,
  61     tree: TreeIndex,
  62 }
  63
  64 /// The state of one node in some tree within the forest. This
  65 /// represents the current state of processing for the obligation (of
  66 /// type `O`) associated with this node.
  67 #[derive(Debug)]
  68 enum NodeState<O> {
  69     /// Obligation not yet resolved to success or error.
  70     Pending {
  71         obligation: O,
  72     },
  73
  74     /// Obligation resolved to success; `num_incomplete_children`
  75     /// indicates the number of children still in an "incomplete"
  76     /// state. Incomplete means that either the child is still
  77     /// pending, or it has children which are incomplete. (Basically,
  78     /// there is pending work somewhere in the subtree of the child.)
  79     ///
  80     /// Once all children have completed, success nodes are removed
  81     /// from the vector by the compression step.
  82     Success {
  83         obligation: O,
  84         num_incomplete_children: usize,
  85     },
  86
  87     /// This obligation was resolved to an error. Error nodes are
  88     /// removed from the vector by the compression step.
  89     Error,
  90 }
  91
  92 #[derive(Debug)]
  93 pub struct Outcome<O, E> {
  94     /// Obligations that were completely evaluated, including all
  95     /// (transitive) subobligations.
  96     pub completed: Vec<O>,
  97
  98     /// Backtrace of obligations that were found to be in error.
  99     pub errors: Vec<Error<O, E>>,
 100
 101     /// If true, then we saw no successful obligations, which means
 102     /// there is no point in further iteration. This is based on the
 103     /// assumption that when trait matching returns `Err` or
 104     /// `Ok(None)`, those results do not affect environmental
 105     /// inference state. (Note that if we invoke `process_obligations`
 106     /// with no pending obligations, stalled will be true.)
 107     pub stalled: bool,
 108 }
 109
 110 #[derive(Debug, PartialEq, Eq)]
 111 pub struct Error<O, E> {
 112     pub error: E,
 113     pub backtrace: Vec<O>,
 114 }
 115
 116 impl<O: Debug, T: Debug> ObligationForest<O, T> {
 117     pub fn new() -> ObligationForest<O, T> {
 118         ObligationForest {
 119             trees: vec![],
 120             nodes: vec![],
 121             snapshots: vec![],
 122         }
 123     }
 124
 125     /// Return the total number of nodes in the forest that have not
 126     /// yet been fully resolved.
 127     pub fn len(&self) -> usize {
 128         self.nodes.len()
 129     }
 130
 131     pub fn start_snapshot(&mut self) -> Snapshot {
 132         self.snapshots.push(self.trees.len());
 133         Snapshot { len: self.snapshots.len() }
 134     }
 135
 136     pub fn commit_snapshot(&mut self, snapshot: Snapshot) {
 137         assert_eq!(snapshot.len, self.snapshots.len());
 138         let trees_len = self.snapshots.pop().unwrap();
 139         assert!(self.trees.len() >= trees_len);
 140     }
 141
 142     pub fn rollback_snapshot(&mut self, snapshot: Snapshot) {
 143         // Check that we are obeying stack discipline.
 144         assert_eq!(snapshot.len, self.snapshots.len());
 145         let trees_len = self.snapshots.pop().unwrap();
 146
 147         // If nothing happened in snapshot, done.
 148         if self.trees.len() == trees_len {
 149             return;
 150         }
 151
 152         // Find root of first tree; because nothing can happen in a
 153         // snapshot but pushing trees, all nodes after that should be
 154         // roots of other trees as well
 155         let first_root_index = self.trees[trees_len].root.get();
 156         debug_assert!(self.nodes[first_root_index..]
 157                           .iter()
 158                           .zip(first_root_index..)
 159                           .all(|(root, root_index)| {
 160                               self.trees[root.tree.get()].root.get() == root_index
 161                           }));
 162
 163         // Pop off tree/root pairs pushed during snapshot.
 164         self.trees.truncate(trees_len);
 165         self.nodes.truncate(first_root_index);
 166     }
 167
 168     pub fn in_snapshot(&self) -> bool {
 169         !self.snapshots.is_empty()
 170     }
 171
 172     /// Adds a new tree to the forest.
 173     ///
 174     /// This CAN be done during a snapshot.
 175     pub fn push_tree(&mut self, obligation: O, tree_state: T) {
 176         let index = NodeIndex::new(self.nodes.len());
 177         let tree = TreeIndex::new(self.trees.len());
 178         self.trees.push(Tree {
 179             root: index,
 180             state: tree_state,
 181         });
 182         self.nodes.push(Node::new(tree, None, obligation));
 183     }
 184
 185     /// Convert all remaining obligations to the given error.
 186     ///
 187     /// This cannot be done during a snapshot.
 188     pub fn to_errors<E: Clone>(&mut self, error: E) -> Vec<Error<O, E>> {
 189         assert!(!self.in_snapshot());
 190         let mut errors = vec![];
 191         for index in 0..self.nodes.len() {
 192             debug_assert!(!self.nodes[index].is_popped());
 193             self.inherit_error(index);
 194             if let NodeState::Pending { .. } = self.nodes[index].state {
 195                 let backtrace = self.backtrace(index);
 196                 errors.push(Error {
 197                     error: error.clone(),
 198                     backtrace: backtrace,
 199                 });
 200             }
 201         }
 202         let successful_obligations = self.compress();
 203         assert!(successful_obligations.is_empty());
 204         errors
 205     }
 206
 207     /// Returns the set of obligations that are in a pending state.
 208     pub fn pending_obligations(&self) -> Vec<O>
 209         where O: Clone
 210     {
 211         self.nodes
 212             .iter()
 213             .filter_map(|n| {
 214                 match n.state {
 215                     NodeState::Pending { ref obligation } => Some(obligation),
 216                     _ => None,
 217                 }
 218             })
 219             .cloned()
 220             .collect()
 221     }
 222
 223     /// Process the obligations.
 224     ///
 225     /// This CANNOT be unrolled (presently, at least).
 226     pub fn process_obligations<E, F>(&mut self, mut action: F) -> Outcome<O, E>
 227         where E: Debug,
 228               F: FnMut(&mut O, &mut T, Backtrace<O>) -> Result<Option<Vec<O>>, E>
 229     {
 230         debug!("process_obligations(len={})", self.nodes.len());
 231         assert!(!self.in_snapshot()); // cannot unroll this action
 232
 233         let mut errors = vec![];
 234         let mut stalled = true;
 235
 236         // We maintain the invariant that the list is in pre-order, so
 237         // parents occur before their children. Also, whenever an
 238         // error occurs, we propagate it from the child all the way to
 239         // the root of the tree. Together, these two facts mean that
 240         // when we visit a node, we can check if its root is in error,
 241         // and we will find out if any prior node within this forest
 242         // encountered an error.
 243
 244         for index in 0..self.nodes.len() {
 245             debug_assert!(!self.nodes[index].is_popped());
 246             self.inherit_error(index);
 247
 248             debug!("process_obligations: node {} == {:?}",
 249                    index,
 250                    self.nodes[index].state);
 251
 252             let result = {
 253                 let Node { tree, parent, .. } = self.nodes[index];
 254                 let (prefix, suffix) = self.nodes.split_at_mut(index);
 255                 let backtrace = Backtrace::new(prefix, parent);
 256                 match suffix[0].state {
 257                     NodeState::Error |
 258                     NodeState::Success { .. } => continue,
 259                     NodeState::Pending { ref mut obligation } => {
 260                         action(obligation, &mut self.trees[tree.get()].state, backtrace)
 261                     }
 262                 }
 263             };
 264
 265             debug!("process_obligations: node {} got result {:?}",
 266                    index,
 267                    result);
 268
 269             match result {
 270                 Ok(None) => {
 271                     // no change in state
 272                 }
 273                 Ok(Some(children)) => {
 274                     // if we saw a Some(_) result, we are not (yet) stalled
 275                     stalled = false;
 276                     self.success(index, children);
 277                 }
 278                 Err(err) => {
 279                     let backtrace = self.backtrace(index);
 280                     errors.push(Error {
 281                         error: err,
 282                         backtrace: backtrace,
 283                     });
 284                 }
 285             }
 286         }
 287
 288         // Now we have to compress the result
 289         let successful_obligations = self.compress();
 290
 291         debug!("process_obligations: complete");
 292
 293         Outcome {
 294             completed: successful_obligations,
 295             errors: errors,
 296             stalled: stalled,
 297         }
 298     }
 299
 300     /// Indicates that node `index` has been processed successfully,
 301     /// yielding `children` as the derivative work. If children is an
 302     /// empty vector, this will update the ref count on the parent of
 303     /// `index` to indicate that a child has completed
 304     /// successfully. Otherwise, adds new nodes to represent the child
 305     /// work.
 306     fn success(&mut self, index: usize, children: Vec<O>) {
 307         debug!("success(index={}, children={:?})", index, children);
 308
 309         let num_incomplete_children = children.len();
 310
 311         if num_incomplete_children == 0 {
 312             // if there is no work left to be done, decrement parent's ref count
 313             self.update_parent(index);
 314         } else {
 315             // create child work
 316             let tree_index = self.nodes[index].tree;
 317             let node_index = NodeIndex::new(index);
 318             self.nodes.extend(children.into_iter()
 319                                       .map(|o| Node::new(tree_index, Some(node_index), o)));
 320         }
 321
 322         // change state from `Pending` to `Success`, temporarily swapping in `Error`
 323         let state = mem::replace(&mut self.nodes[index].state, NodeState::Error);
 324         self.nodes[index].state = match state {
 325             NodeState::Pending { obligation } => {
 326                 NodeState::Success {
 327                     obligation: obligation,
 328                     num_incomplete_children: num_incomplete_children,
 329                 }
 330             }
 331             NodeState::Success { .. } |
 332             NodeState::Error => unreachable!(),
 333         };
 334     }
 335
 336     /// Decrements the ref count on the parent of `child`; if the
 337     /// parent's ref count then reaches zero, proceeds recursively.
 338     fn update_parent(&mut self, child: usize) {
 339         debug!("update_parent(child={})", child);
 340         if let Some(parent) = self.nodes[child].parent {
 341             let parent = parent.get();
 342             match self.nodes[parent].state {
 343                 NodeState::Success { ref mut num_incomplete_children, .. } => {
 344                     *num_incomplete_children -= 1;
 345                     if *num_incomplete_children > 0 {
 346                         return;
 347                     }
 348                 }
 349                 _ => unreachable!(),
 350             }
 351             self.update_parent(parent);
 352         }
 353     }
 354
 355     /// If the root of `child` is in an error state, places `child`
 356     /// into an error state. This is used during processing so that we
 357     /// skip the remaining obligations from a tree once some other
 358     /// node in the tree is found to be in error.
 359     fn inherit_error(&mut self, child: usize) {
 360         let tree = self.nodes[child].tree;
 361         let root = self.trees[tree.get()].root;
 362         if let NodeState::Error = self.nodes[root.get()].state {
 363             self.nodes[child].state = NodeState::Error;
 364         }
 365     }
 366
 367     /// Returns a vector of obligations for `p` and all of its
 368     /// ancestors, putting them into the error state in the process.
 369     /// The fact that the root is now marked as an error is used by
 370     /// `inherit_error` above to propagate the error state to the
 371     /// remainder of the tree.
 372     fn backtrace(&mut self, mut p: usize) -> Vec<O> {
 373         let mut trace = vec![];
 374         loop {
 375             let state = mem::replace(&mut self.nodes[p].state, NodeState::Error);
 376             match state {
 377                 NodeState::Pending { obligation } |
 378                 NodeState::Success { obligation, .. } => {
 379                     trace.push(obligation);
 380                 }
 381                 NodeState::Error => {
 382                     // we should not encounter an error, because if
 383                     // there was an error in the ancestors, it should
 384                     // have been propagated down and we should never
 385                     // have tried to process this obligation
 386                     panic!("encountered error in node {:?} when collecting stack trace",
 387                            p);
 388                 }
 389             }
 390
 391             // loop to the parent
 392             match self.nodes[p].parent {
 393                 Some(q) => {
 394                     p = q.get();
 395                 }
 396                 None => {
 397                     return trace;
 398                 }
 399             }
 400         }
 401     }
 402
 403     /// Compresses the vector, removing all popped nodes. This adjusts
 404     /// the indices and hence invalidates any outstanding
 405     /// indices. Cannot be used during a transaction.
 406     fn compress(&mut self) -> Vec<O> {
 407         assert!(!self.in_snapshot()); // didn't write code to unroll this action
 408         let mut node_rewrites: Vec<_> = (0..self.nodes.len()).collect();
 409         let mut tree_rewrites: Vec<_> = (0..self.trees.len()).collect();
 410
 411         // Finish propagating error state. Note that in this case we
 412         // only have to check immediate parents, rather than all
 413         // ancestors, because all errors have already occurred that
 414         // are going to occur.
 415         let nodes_len = self.nodes.len();
 416         for i in 0..nodes_len {
 417             if !self.nodes[i].is_popped() {
 418                 self.inherit_error(i);
 419             }
 420         }
 421
 422         // Determine which trees to remove by checking if their root
 423         // is popped.
 424         let mut dead_trees = 0;
 425         let trees_len = self.trees.len();
 426         for i in 0..trees_len {
 427             let root_node = self.trees[i].root;
 428             if self.nodes[root_node.get()].is_popped() {
 429                 dead_trees += 1;
 430             } else if dead_trees > 0 {
 431                 self.trees.swap(i, i - dead_trees);
 432                 tree_rewrites[i] -= dead_trees;
 433             }
 434         }
 435
 436         // Now go through and move all nodes that are either
 437         // successful or which have an error over into to the end of
 438         // the list, preserving the relative order of the survivors
 439         // (which is important for the `inherit_error` logic).
 440         let mut dead_nodes = 0;
 441         for i in 0..nodes_len {
 442             if self.nodes[i].is_popped() {
 443                 dead_nodes += 1;
 444             } else if dead_nodes > 0 {
 445                 self.nodes.swap(i, i - dead_nodes);
 446                 node_rewrites[i] -= dead_nodes;
 447             }
 448         }
 449
 450         // No compression needed.
 451         if dead_nodes == 0 && dead_trees == 0 {
 452             return vec![];
 453         }
 454
 455         // Pop off the trees we killed.
 456         self.trees.truncate(trees_len - dead_trees);
 457
 458         // Pop off all the nodes we killed and extract the success
 459         // stories.
 460         let successful = (0..dead_nodes)
 461                              .map(|_| self.nodes.pop().unwrap())
 462                              .flat_map(|node| {
 463                                  match node.state {
 464                                      NodeState::Error => None,
 465                                      NodeState::Pending { .. } => unreachable!(),
 466                                      NodeState::Success { obligation, num_incomplete_children } => {
 467                                          assert_eq!(num_incomplete_children, 0);
 468                                          Some(obligation)
 469                                      }
 470                                  }
 471                              })
 472                              .collect();
 473
 474         // Adjust the various indices, since we compressed things.
 475         for tree in &mut self.trees {
 476             tree.root = NodeIndex::new(node_rewrites[tree.root.get()]);
 477         }
 478         for node in &mut self.nodes {
 479             if let Some(ref mut index) = node.parent {
 480                 let new_index = node_rewrites[index.get()];
 481                 debug_assert!(new_index < (nodes_len - dead_nodes));
 482                 *index = NodeIndex::new(new_index);
 483             }
 484
 485             node.tree = TreeIndex::new(tree_rewrites[node.tree.get()]);
 486         }
 487
 488         successful
 489     }
 490 }
 491
 492 impl<O> Node<O> {
 493     fn new(tree: TreeIndex, parent: Option<NodeIndex>, obligation: O) -> Node<O> {
 494         Node {
 495             parent: parent,
 496             state: NodeState::Pending { obligation: obligation },
 497             tree: tree,
 498         }
 499     }
 500
 501     fn is_popped(&self) -> bool {
 502         match self.state {
 503             NodeState::Pending { .. } => false,
 504             NodeState::Success { num_incomplete_children, .. } => num_incomplete_children == 0,
 505             NodeState::Error => true,
 506         }
 507     }
 508 }
 509
 510 #[derive(Clone)]
 511 pub struct Backtrace<'b, O: 'b> {
 512     nodes: &'b [Node<O>],
 513     pointer: Option<NodeIndex>,
 514 }
 515
 516 impl<'b, O> Backtrace<'b, O> {
 517     fn new(nodes: &'b [Node<O>], pointer: Option<NodeIndex>) -> Backtrace<'b, O> {
 518         Backtrace {
 519             nodes: nodes,
 520             pointer: pointer,
 521         }
 522     }
 523 }
 524
 525 impl<'b, O> Iterator for Backtrace<'b, O> {
 526     type Item = &'b O;
 527
 528     fn next(&mut self) -> Option<&'b O> {
 529         debug!("Backtrace: self.pointer = {:?}", self.pointer);
 530         if let Some(p) = self.pointer {
 531             self.pointer = self.nodes[p.get()].parent;
 532             match self.nodes[p.get()].state {
 533                 NodeState::Pending { ref obligation } |
 534                 NodeState::Success { ref obligation, .. } => Some(obligation),
 535                 NodeState::Error => {
 536                     panic!("Backtrace encountered an error.");
 537                 }
 538             }
 539         } else {
 540             None
 541         }
 542     }
 543 }