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