src/librustc_mir/borrow_check/location.rs

   1 use rustc::mir::{BasicBlock, Location, Body};
   2 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
   3
   4 /// Maps between a MIR Location, which identifies a particular
   5 /// statement within a basic block, to a "rich location", which
   6 /// identifies at a finer granularity. In particular, we distinguish
   7 /// the *start* of a statement and the *mid-point*. The mid-point is
   8 /// the point *just* before the statement takes effect; in particular,
   9 /// for an assignment `A = B`, it is the point where B is about to be
  10 /// written into A. This mid-point is a kind of hack to work around
  11 /// our inability to track the position information at sufficient
  12 /// granularity through outlives relations; however, the rich location
  13 /// table serves another purpose: it compresses locations from
  14 /// multiple words into a single u32.
  15 crate struct LocationTable {
  16     num_points: usize,
  17     statements_before_block: IndexVec<BasicBlock, usize>,
  18 }
  19
  20 newtype_index! {
  21     pub struct LocationIndex {
  22         DEBUG_FORMAT = "LocationIndex({})"
  23     }
  24 }
  25
  26 #[derive(Copy, Clone, Debug)]
  27 crate enum RichLocation {
  28     Start(Location),
  29     Mid(Location),
  30 }
  31
  32 impl LocationTable {
  33     crate fn new(mir: &Body<'_>) -> Self {
  34         let mut num_points = 0;
  35         let statements_before_block = mir.basic_blocks()
  36             .iter()
  37             .map(|block_data| {
  38                 let v = num_points;
  39                 num_points += (block_data.statements.len() + 1) * 2;
  40                 v
  41             })
  42             .collect();
  43
  44         debug!(
  45             "LocationTable(statements_before_block={:#?})",
  46             statements_before_block
  47         );
  48         debug!("LocationTable: num_points={:#?}", num_points);
  49
  50         Self {
  51             num_points,
  52             statements_before_block,
  53         }
  54     }
  55
  56     crate fn all_points(&self) -> impl Iterator<Item = LocationIndex> {
  57         (0..self.num_points).map(LocationIndex::new)
  58     }
  59
  60     crate fn start_index(&self, location: Location) -> LocationIndex {
  61         let Location {
  62             block,
  63             statement_index,
  64         } = location;
  65         let start_index = self.statements_before_block[block];
  66         LocationIndex::new(start_index + statement_index * 2)
  67     }
  68
  69     crate fn mid_index(&self, location: Location) -> LocationIndex {
  70         let Location {
  71             block,
  72             statement_index,
  73         } = location;
  74         let start_index = self.statements_before_block[block];
  75         LocationIndex::new(start_index + statement_index * 2 + 1)
  76     }
  77
  78     crate fn to_location(&self, index: LocationIndex) -> RichLocation {
  79         let point_index = index.index();
  80
  81         // Find the basic block. We have a vector with the
  82         // starting index of the statement in each block. Imagine
  83         // we have statement #22, and we have a vector like:
  84         //
  85         // [0, 10, 20]
  86         //
  87         // In that case, this represents point_index 2 of
  88         // basic block BB2. We know this because BB0 accounts for
  89         // 0..10, BB1 accounts for 11..20, and BB2 accounts for
  90         // 20...
  91         //
  92         // To compute this, we could do a binary search, but
  93         // because I am lazy we instead iterate through to find
  94         // the last point where the "first index" (0, 10, or 20)
  95         // was less than the statement index (22). In our case, this will
  96         // be (BB2, 20).
  97         let (block, &first_index) = self.statements_before_block
  98             .iter_enumerated()
  99             .filter(|(_, first_index)| **first_index <= point_index)
 100             .last()
 101             .unwrap();
 102
 103         let statement_index = (point_index - first_index) / 2;
 104         if index.is_start() {
 105             RichLocation::Start(Location { block, statement_index })
 106         } else {
 107             RichLocation::Mid(Location { block, statement_index })
 108         }
 109     }
 110 }
 111
 112 impl LocationIndex {
 113     fn is_start(&self) -> bool {
 114         // even indices are start points; odd indices are mid points
 115         (self.index() % 2) == 0
 116     }
 117 }