compiler/rustc_borrowck/src/location.rs

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