src/librustc/mir/traversal.rs

   1 // Copyright 2016 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 use rustc_data_structures::bitvec::BitVector;
  12 use rustc_data_structures::indexed_vec::Idx;
  13
  14 use super::*;
  15
  16 /// Preorder traversal of a graph.
  17 ///
  18 /// Preorder traversal is when each node is visited before an of it's
  19 /// successors
  20 ///
  21 /// ```text
  22 ///
  23 ///         A
  24 ///        / \
  25 ///       /   \
  26 ///      B     C
  27 ///       \   /
  28 ///        \ /
  29 ///         D
  30 /// ```
  31 ///
  32 /// A preorder traversal of this graph is either `A B D C` or `A C D B`
  33 #[derive(Clone)]
  34 pub struct Preorder<'a, 'tcx: 'a> {
  35     mir: &'a Mir<'tcx>,
  36     visited: BitVector,
  37     worklist: Vec<BasicBlock>,
  38 }
  39
  40 impl<'a, 'tcx> Preorder<'a, 'tcx> {
  41     pub fn new(mir: &'a Mir<'tcx>, root: BasicBlock) -> Preorder<'a, 'tcx> {
  42         let worklist = vec![root];
  43
  44         Preorder {
  45             mir,
  46             visited: BitVector::new(mir.basic_blocks().len()),
  47             worklist,
  48         }
  49     }
  50 }
  51
  52 pub fn preorder<'a, 'tcx>(mir: &'a Mir<'tcx>) -> Preorder<'a, 'tcx> {
  53     Preorder::new(mir, START_BLOCK)
  54 }
  55
  56 impl<'a, 'tcx> Iterator for Preorder<'a, 'tcx> {
  57     type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
  58
  59     fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
  60         while let Some(idx) = self.worklist.pop() {
  61             if !self.visited.insert(idx.index()) {
  62                 continue;
  63             }
  64
  65             let data = &self.mir[idx];
  66
  67             if let Some(ref term) = data.terminator {
  68                 for &succ in term.successors() {
  69                     self.worklist.push(succ);
  70                 }
  71             }
  72
  73             return Some((idx, data));
  74         }
  75
  76         None
  77     }
  78
  79     fn size_hint(&self) -> (usize, Option<usize>) {
  80         // All the blocks, minus the number of blocks we've visited.
  81         let remaining = self.mir.basic_blocks().len() - self.visited.count();
  82
  83         // We will visit all remaining blocks exactly once.
  84         (remaining, Some(remaining))
  85     }
  86 }
  87
  88 impl<'a, 'tcx> ExactSizeIterator for Preorder<'a, 'tcx> {}
  89
  90 /// Postorder traversal of a graph.
  91 ///
  92 /// Postorder traversal is when each node is visited after all of it's
  93 /// successors, except when the successor is only reachable by a back-edge
  94 ///
  95 ///
  96 /// ```text
  97 ///
  98 ///         A
  99 ///        / \
 100 ///       /   \
 101 ///      B     C
 102 ///       \   /
 103 ///        \ /
 104 ///         D
 105 /// ```
 106 ///
 107 /// A Postorder traversal of this graph is `D B C A` or `D C B A`
 108 pub struct Postorder<'a, 'tcx: 'a> {
 109     mir: &'a Mir<'tcx>,
 110     visited: BitVector,
 111     visit_stack: Vec<(BasicBlock, Successors<'a>)>
 112 }
 113
 114 impl<'a, 'tcx> Postorder<'a, 'tcx> {
 115     pub fn new(mir: &'a Mir<'tcx>, root: BasicBlock) -> Postorder<'a, 'tcx> {
 116         let mut po = Postorder {
 117             mir,
 118             visited: BitVector::new(mir.basic_blocks().len()),
 119             visit_stack: Vec::new()
 120         };
 121
 122
 123         let data = &po.mir[root];
 124
 125         if let Some(ref term) = data.terminator {
 126             po.visited.insert(root.index());
 127             po.visit_stack.push((root, term.successors()));
 128             po.traverse_successor();
 129         }
 130
 131         po
 132     }
 133
 134     fn traverse_successor(&mut self) {
 135         // This is quite a complex loop due to 1. the borrow checker not liking it much
 136         // and 2. what exactly is going on is not clear
 137         //
 138         // It does the actual traversal of the graph, while the `next` method on the iterator
 139         // just pops off of the stack. `visit_stack` is a stack containing pairs of nodes and
 140         // iterators over the sucessors of those nodes. Each iteration attempts to get the next
 141         // node from the top of the stack, then pushes that node and an iterator over the
 142         // successors to the top of the stack. This loop only grows `visit_stack`, stopping when
 143         // we reach a child that has no children that we haven't already visited.
 144         //
 145         // For a graph that looks like this:
 146         //
 147         //         A
 148         //        / \
 149         //       /   \
 150         //      B     C
 151         //      |     |
 152         //      |     |
 153         //      D     |
 154         //       \   /
 155         //        \ /
 156         //         E
 157         //
 158         // The state of the stack starts out with just the root node (`A` in this case);
 159         //     [(A, [B, C])]
 160         //
 161         // When the first call to `traverse_sucessor` happens, the following happens:
 162         //
 163         //     [(B, [D]),  // `B` taken from the successors of `A`, pushed to the
 164         //                 // top of the stack along with the successors of `B`
 165         //      (A, [C])]
 166         //
 167         //     [(D, [E]),  // `D` taken from successors of `B`, pushed to stack
 168         //      (B, []),
 169         //      (A, [C])]
 170         //
 171         //     [(E, []),   // `E` taken from successors of `D`, pushed to stack
 172         //      (D, []),
 173         //      (B, []),
 174         //      (A, [C])]
 175         //
 176         // Now that the top of the stack has no successors we can traverse, each item will
 177         // be popped off during iteration until we get back to `A`. This yeilds [E, D, B].
 178         //
 179         // When we yield `B` and call `traverse_successor`, we push `C` to the stack, but
 180         // since we've already visited `E`, that child isn't added to the stack. The last
 181         // two iterations yield `C` and finally `A` for a final traversal of [E, D, B, C, A]
 182         loop {
 183             let bb = if let Some(&mut (_, ref mut iter)) = self.visit_stack.last_mut() {
 184                 if let Some(&bb) = iter.next() {
 185                     bb
 186                 } else {
 187                     break;
 188                 }
 189             } else {
 190                 break;
 191             };
 192
 193             if self.visited.insert(bb.index()) {
 194                 if let Some(ref term) = self.mir[bb].terminator {
 195                     self.visit_stack.push((bb, term.successors()));
 196                 }
 197             }
 198         }
 199     }
 200 }
 201
 202 pub fn postorder<'a, 'tcx>(mir: &'a Mir<'tcx>) -> Postorder<'a, 'tcx> {
 203     Postorder::new(mir, START_BLOCK)
 204 }
 205
 206 impl<'a, 'tcx> Iterator for Postorder<'a, 'tcx> {
 207     type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
 208
 209     fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
 210         let next = self.visit_stack.pop();
 211         if next.is_some() {
 212             self.traverse_successor();
 213         }
 214
 215         next.map(|(bb, _)| (bb, &self.mir[bb]))
 216     }
 217
 218     fn size_hint(&self) -> (usize, Option<usize>) {
 219         // All the blocks, minus the number of blocks we've visited.
 220         let remaining = self.mir.basic_blocks().len() - self.visited.count();
 221
 222         // We will visit all remaining blocks exactly once.
 223         (remaining, Some(remaining))
 224     }
 225 }
 226
 227 impl<'a, 'tcx> ExactSizeIterator for Postorder<'a, 'tcx> {}
 228
 229 /// Reverse postorder traversal of a graph
 230 ///
 231 /// Reverse postorder is the reverse order of a postorder traversal.
 232 /// This is different to a preorder traversal and represents a natural
 233 /// linearization of control-flow.
 234 ///
 235 /// ```text
 236 ///
 237 ///         A
 238 ///        / \
 239 ///       /   \
 240 ///      B     C
 241 ///       \   /
 242 ///        \ /
 243 ///         D
 244 /// ```
 245 ///
 246 /// A reverse postorder traversal of this graph is either `A B C D` or `A C B D`
 247 /// Note that for a graph containing no loops (i.e. A DAG), this is equivalent to
 248 /// a topological sort.
 249 ///
 250 /// Construction of a `ReversePostorder` traversal requires doing a full
 251 /// postorder traversal of the graph, therefore this traversal should be
 252 /// constructed as few times as possible. Use the `reset` method to be able
 253 /// to re-use the traversal
 254 #[derive(Clone)]
 255 pub struct ReversePostorder<'a, 'tcx: 'a> {
 256     mir: &'a Mir<'tcx>,
 257     blocks: Vec<BasicBlock>,
 258     idx: usize
 259 }
 260
 261 impl<'a, 'tcx> ReversePostorder<'a, 'tcx> {
 262     pub fn new(mir: &'a Mir<'tcx>, root: BasicBlock) -> ReversePostorder<'a, 'tcx> {
 263         let blocks : Vec<_> = Postorder::new(mir, root).map(|(bb, _)| bb).collect();
 264
 265         let len = blocks.len();
 266
 267         ReversePostorder {
 268             mir,
 269             blocks,
 270             idx: len
 271         }
 272     }
 273
 274     pub fn reset(&mut self) {
 275         self.idx = self.blocks.len();
 276     }
 277 }
 278
 279
 280 pub fn reverse_postorder<'a, 'tcx>(mir: &'a Mir<'tcx>) -> ReversePostorder<'a, 'tcx> {
 281     ReversePostorder::new(mir, START_BLOCK)
 282 }
 283
 284 impl<'a, 'tcx> Iterator for ReversePostorder<'a, 'tcx> {
 285     type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
 286
 287     fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
 288         if self.idx == 0 { return None; }
 289         self.idx -= 1;
 290
 291         self.blocks.get(self.idx).map(|&bb| (bb, &self.mir[bb]))
 292     }
 293
 294     fn size_hint(&self) -> (usize, Option<usize>) {
 295         (self.idx, Some(self.idx))
 296     }
 297 }
 298
 299 impl<'a, 'tcx> ExactSizeIterator for ReversePostorder<'a, 'tcx> {}