src/librustc_mir/borrow_check/location.rs

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