]> git.proxmox.com Git - rustc.git/blame - src/librustc_data_structures/obligation_forest/mod.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc_data_structures / obligation_forest / mod.rs
CommitLineData
7453a54e
SL
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
18use std::fmt::Debug;
19use std::mem;
20
21mod node_index;
22use self::node_index::NodeIndex;
23
24mod tree_index;
25use self::tree_index::TreeIndex;
26
27
28#[cfg(test)]
29mod test;
30
54a0048b 31pub struct ObligationForest<O, T> {
7453a54e
SL
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>>,
54a0048b 46 snapshots: Vec<usize>,
7453a54e
SL
47}
48
49pub struct Snapshot {
50 len: usize,
51}
52
53struct Tree<T> {
54 root: NodeIndex,
55 state: T,
56}
57
58struct 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)]
68enum NodeState<O> {
69 /// Obligation not yet resolved to success or error.
54a0048b
SL
70 Pending {
71 obligation: O,
72 },
7453a54e
SL
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.
54a0048b
SL
82 Success {
83 obligation: O,
84 num_incomplete_children: usize,
85 },
7453a54e
SL
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)]
54a0048b 93pub struct Outcome<O, E> {
7453a54e
SL
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.
54a0048b 99 pub errors: Vec<Error<O, E>>,
7453a54e
SL
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)]
54a0048b 111pub struct Error<O, E> {
7453a54e
SL
112 pub error: E,
113 pub backtrace: Vec<O>,
114}
115
116impl<O: Debug, T: Debug> ObligationForest<O, T> {
117 pub fn new() -> ObligationForest<O, T> {
118 ObligationForest {
119 trees: vec![],
120 nodes: vec![],
54a0048b 121 snapshots: vec![],
7453a54e
SL
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();
54a0048b
SL
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 }));
7453a54e
SL
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());
54a0048b
SL
178 self.trees.push(Tree {
179 root: index,
180 state: tree_state,
181 });
7453a54e
SL
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.
54a0048b 188 pub fn to_errors<E: Clone>(&mut self, error: E) -> Vec<Error<O, E>> {
7453a54e
SL
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);
54a0048b
SL
196 errors.push(Error {
197 error: error.clone(),
198 backtrace: backtrace,
199 });
7453a54e
SL
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.
54a0048b
SL
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()
7453a54e
SL
221 }
222
223 /// Process the obligations.
224 ///
225 /// This CANNOT be unrolled (presently, at least).
54a0048b
SL
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>
7453a54e
SL
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 {} == {:?}",
54a0048b
SL
249 index,
250 self.nodes[index].state);
7453a54e
SL
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 |
54a0048b
SL
258 NodeState::Success { .. } => continue,
259 NodeState::Pending { ref mut obligation } => {
260 action(obligation, &mut self.trees[tree.get()].state, backtrace)
261 }
7453a54e
SL
262 }
263 };
264
54a0048b
SL
265 debug!("process_obligations: node {} got result {:?}",
266 index,
267 result);
7453a54e
SL
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);
54a0048b
SL
280 errors.push(Error {
281 error: err,
282 backtrace: backtrace,
283 });
7453a54e
SL
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);
54a0048b
SL
318 self.nodes.extend(children.into_iter()
319 .map(|o| Node::new(tree_index, Some(node_index), o)));
7453a54e
SL
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 {
54a0048b
SL
325 NodeState::Pending { obligation } => {
326 NodeState::Success {
327 obligation: obligation,
328 num_incomplete_children: num_incomplete_children,
329 }
330 }
7453a54e 331 NodeState::Success { .. } |
54a0048b 332 NodeState::Error => unreachable!(),
7453a54e
SL
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
54a0048b
SL
386 panic!("encountered error in node {:?} when collecting stack trace",
387 p);
7453a54e
SL
388 }
389 }
390
391 // loop to the parent
392 match self.nodes[p].parent {
54a0048b
SL
393 Some(q) => {
394 p = q.get();
395 }
396 None => {
397 return trace;
398 }
7453a54e
SL
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.
54a0048b
SL
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();
7453a54e
SL
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
492impl<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)]
511pub struct Backtrace<'b, O: 'b> {
512 nodes: &'b [Node<O>],
513 pointer: Option<NodeIndex>,
514}
515
516impl<'b, O> Backtrace<'b, O> {
517 fn new(nodes: &'b [Node<O>], pointer: Option<NodeIndex>) -> Backtrace<'b, O> {
54a0048b
SL
518 Backtrace {
519 nodes: nodes,
520 pointer: pointer,
521 }
7453a54e
SL
522 }
523}
524
525impl<'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 } |
54a0048b 534 NodeState::Success { ref obligation, .. } => Some(obligation),
7453a54e
SL
535 NodeState::Error => {
536 panic!("Backtrace encountered an error.");
537 }
538 }
539 } else {
540 None
541 }
542 }
543}