src/librustc_mir/borrow_check/nll/region_infer/values.rs

   1 use rustc::mir::{BasicBlock, Location, Mir};
   2 use rustc::ty::{self, RegionVid};
   3 use rustc_data_structures::bit_set::{HybridBitSet, SparseBitMatrix};
   4 use rustc_data_structures::fx::FxHashMap;
   5 use rustc_data_structures::indexed_vec::Idx;
   6 use rustc_data_structures::indexed_vec::IndexVec;
   7 use std::fmt::Debug;
   8 use std::rc::Rc;
   9
  10 /// Maps between a `Location` and a `PointIndex` (and vice versa).
  11 crate struct RegionValueElements {
  12     /// For each basic block, how many points are contained within?
  13     statements_before_block: IndexVec<BasicBlock, usize>,
  14
  15     /// Map backward from each point to the basic block that it
  16     /// belongs to.
  17     basic_blocks: IndexVec<PointIndex, BasicBlock>,
  18
  19     num_points: usize,
  20 }
  21
  22 impl RegionValueElements {
  23     crate fn new(mir: &Mir<'_>) -> Self {
  24         let mut num_points = 0;
  25         let statements_before_block: IndexVec<BasicBlock, usize> = mir.basic_blocks()
  26             .iter()
  27             .map(|block_data| {
  28                 let v = num_points;
  29                 num_points += block_data.statements.len() + 1;
  30                 v
  31             })
  32             .collect();
  33         debug!(
  34             "RegionValueElements: statements_before_block={:#?}",
  35             statements_before_block
  36         );
  37         debug!("RegionValueElements: num_points={:#?}", num_points);
  38
  39         let mut basic_blocks = IndexVec::with_capacity(num_points);
  40         for (bb, bb_data) in mir.basic_blocks().iter_enumerated() {
  41             basic_blocks.extend((0..=bb_data.statements.len()).map(|_| bb));
  42         }
  43
  44         Self {
  45             statements_before_block,
  46             basic_blocks,
  47             num_points,
  48         }
  49     }
  50
  51     /// Total number of point indices
  52     crate fn num_points(&self) -> usize {
  53         self.num_points
  54     }
  55
  56     /// Converts a `Location` into a `PointIndex`. O(1).
  57     crate fn point_from_location(&self, location: Location) -> PointIndex {
  58         let Location {
  59             block,
  60             statement_index,
  61         } = location;
  62         let start_index = self.statements_before_block[block];
  63         PointIndex::new(start_index + statement_index)
  64     }
  65
  66     /// Converts a `Location` into a `PointIndex`. O(1).
  67     crate fn entry_point(&self, block: BasicBlock) -> PointIndex {
  68         let start_index = self.statements_before_block[block];
  69         PointIndex::new(start_index)
  70     }
  71
  72     /// Converts a `PointIndex` back to a location. O(1).
  73     crate fn to_location(&self, index: PointIndex) -> Location {
  74         assert!(index.index() < self.num_points);
  75         let block = self.basic_blocks[index];
  76         let start_index = self.statements_before_block[block];
  77         let statement_index = index.index() - start_index;
  78         Location {
  79             block,
  80             statement_index,
  81         }
  82     }
  83
  84     /// Sometimes we get point-indices back from bitsets that may be
  85     /// out of range (because they round up to the nearest 2^N number
  86     /// of bits). Use this function to filter such points out if you
  87     /// like.
  88     crate fn point_in_range(&self, index: PointIndex) -> bool {
  89         index.index() < self.num_points
  90     }
  91
  92     /// Pushes all predecessors of `index` onto `stack`.
  93     crate fn push_predecessors(
  94         &self,
  95         mir: &Mir<'_>,
  96         index: PointIndex,
  97         stack: &mut Vec<PointIndex>,
  98     ) {
  99         let Location {
 100             block,
 101             statement_index,
 102         } = self.to_location(index);
 103         if statement_index == 0 {
 104             // If this is a basic block head, then the predecessors are
 105             // the terminators of other basic blocks
 106             stack.extend(
 107                 mir.predecessors_for(block)
 108                     .iter()
 109                     .map(|&pred_bb| mir.terminator_loc(pred_bb))
 110                     .map(|pred_loc| self.point_from_location(pred_loc)),
 111             );
 112         } else {
 113             // Otherwise, the pred is just the previous statement
 114             stack.push(PointIndex::new(index.index() - 1));
 115         }
 116     }
 117 }
 118
 119 newtype_index! {
 120     /// A single integer representing a `Location` in the MIR control-flow
 121     /// graph. Constructed efficiently from `RegionValueElements`.
 122     pub struct PointIndex { DEBUG_FORMAT = "PointIndex({})" }
 123 }
 124
 125 newtype_index! {
 126     /// A single integer representing a `ty::Placeholder`.
 127     pub struct PlaceholderIndex { DEBUG_FORMAT = "PlaceholderIndex({})" }
 128 }
 129
 130 /// An individual element in a region value -- the value of a
 131 /// particular region variable consists of a set of these elements.
 132 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
 133 crate enum RegionElement {
 134     /// A point in the control-flow graph.
 135     Location(Location),
 136
 137     /// A universally quantified region from the root universe (e.g.,
 138     /// a lifetime parameter).
 139     RootUniversalRegion(RegionVid),
 140
 141     /// A placeholder (e.g., instantiated from a `for<'a> fn(&'a u32)`
 142     /// type).
 143     PlaceholderRegion(ty::PlaceholderRegion),
 144 }
 145
 146 /// When we initially compute liveness, we use a bit matrix storing
 147 /// points for each region-vid.
 148 crate struct LivenessValues<N: Idx> {
 149     elements: Rc<RegionValueElements>,
 150     points: SparseBitMatrix<N, PointIndex>,
 151 }
 152
 153 impl<N: Idx> LivenessValues<N> {
 154     /// Creates a new set of "region values" that tracks causal information.
 155     /// Each of the regions in num_region_variables will be initialized with an
 156     /// empty set of points and no causal information.
 157     crate fn new(elements: Rc<RegionValueElements>) -> Self {
 158         Self {
 159             points: SparseBitMatrix::new(elements.num_points),
 160             elements: elements,
 161         }
 162     }
 163
 164     /// Iterate through each region that has a value in this set.
 165     crate fn rows<'a>(&'a self) -> impl Iterator<Item = N> {
 166         self.points.rows()
 167     }
 168
 169     /// Adds the given element to the value for the given region. Returns whether
 170     /// the element is newly added (i.e., was not already present).
 171     crate fn add_element(&mut self, row: N, location: Location) -> bool {
 172         debug!("LivenessValues::add(r={:?}, location={:?})", row, location);
 173         let index = self.elements.point_from_location(location);
 174         self.points.insert(row, index)
 175     }
 176
 177     /// Adds all the elements in the given bit array into the given
 178     /// region. Returns whether any of them are newly added.
 179     crate fn add_elements(&mut self, row: N, locations: &HybridBitSet<PointIndex>) -> bool {
 180         debug!(
 181             "LivenessValues::add_elements(row={:?}, locations={:?})",
 182             row, locations
 183         );
 184         self.points.union_into_row(row, locations)
 185     }
 186
 187     /// Adds all the control-flow points to the values for `r`.
 188     crate fn add_all_points(&mut self, row: N) {
 189         self.points.insert_all_into_row(row);
 190     }
 191
 192     /// Returns `true` if the region `r` contains the given element.
 193     crate fn contains(&self, row: N, location: Location) -> bool {
 194         let index = self.elements.point_from_location(location);
 195         self.points.contains(row, index)
 196     }
 197
 198     /// Returns a "pretty" string value of the region. Meant for debugging.
 199     crate fn region_value_str(&self, r: N) -> String {
 200         region_value_str(
 201             self.points
 202                 .row(r)
 203                 .into_iter()
 204                 .flat_map(|set| set.iter())
 205                 .take_while(|&p| self.elements.point_in_range(p))
 206                 .map(|p| self.elements.to_location(p))
 207                 .map(RegionElement::Location),
 208         )
 209     }
 210 }
 211
 212 /// Maps from `ty::PlaceholderRegion` values that are used in the rest of
 213 /// rustc to the internal `PlaceholderIndex` values that are used in
 214 /// NLL.
 215 #[derive(Default)]
 216 crate struct PlaceholderIndices {
 217     to_index: FxHashMap<ty::PlaceholderRegion, PlaceholderIndex>,
 218     from_index: IndexVec<PlaceholderIndex, ty::PlaceholderRegion>,
 219 }
 220
 221 impl PlaceholderIndices {
 222     crate fn insert(&mut self, placeholder: ty::PlaceholderRegion) -> PlaceholderIndex {
 223         let PlaceholderIndices {
 224             to_index,
 225             from_index,
 226         } = self;
 227         *to_index
 228             .entry(placeholder)
 229             .or_insert_with(|| from_index.push(placeholder))
 230     }
 231
 232     crate fn lookup_index(&self, placeholder: ty::PlaceholderRegion) -> PlaceholderIndex {
 233         self.to_index[&placeholder]
 234     }
 235
 236     crate fn lookup_placeholder(&self, placeholder: PlaceholderIndex) -> ty::PlaceholderRegion {
 237         self.from_index[placeholder]
 238     }
 239
 240     crate fn len(&self) -> usize {
 241         self.from_index.len()
 242     }
 243 }
 244
 245 /// Stores the full values for a set of regions (in contrast to
 246 /// `LivenessValues`, which only stores those points in the where a
 247 /// region is live). The full value for a region may contain points in
 248 /// the CFG, but also free regions as well as bound universe
 249 /// placeholders.
 250 ///
 251 /// Example:
 252 ///
 253 /// ```text
 254 /// fn foo(x: &'a u32) -> &'a u32 {
 255 ///    let y: &'0 u32 = x; // let's call this `'0`
 256 ///    y
 257 /// }
 258 /// ```
 259 ///
 260 /// Here, the variable `'0` would contain the free region `'a`,
 261 /// because (since it is returned) it must live for at least `'a`. But
 262 /// it would also contain various points from within the function.
 263 #[derive(Clone)]
 264 crate struct RegionValues<N: Idx> {
 265     elements: Rc<RegionValueElements>,
 266     placeholder_indices: Rc<PlaceholderIndices>,
 267     points: SparseBitMatrix<N, PointIndex>,
 268     free_regions: SparseBitMatrix<N, RegionVid>,
 269
 270     /// Placeholders represent bound regions -- so something like `'a`
 271     /// in for<'a> fn(&'a u32)`.
 272     placeholders: SparseBitMatrix<N, PlaceholderIndex>,
 273 }
 274
 275 impl<N: Idx> RegionValues<N> {
 276     /// Creates a new set of "region values" that tracks causal information.
 277     /// Each of the regions in num_region_variables will be initialized with an
 278     /// empty set of points and no causal information.
 279     crate fn new(
 280         elements: &Rc<RegionValueElements>,
 281         num_universal_regions: usize,
 282         placeholder_indices: &Rc<PlaceholderIndices>,
 283     ) -> Self {
 284         let num_placeholders = placeholder_indices.len();
 285         Self {
 286             elements: elements.clone(),
 287             points: SparseBitMatrix::new(elements.num_points),
 288             placeholder_indices: placeholder_indices.clone(),
 289             free_regions: SparseBitMatrix::new(num_universal_regions),
 290             placeholders: SparseBitMatrix::new(num_placeholders),
 291         }
 292     }
 293
 294     /// Adds the given element to the value for the given region. Returns whether
 295     /// the element is newly added (i.e., was not already present).
 296     crate fn add_element(&mut self, r: N, elem: impl ToElementIndex) -> bool {
 297         debug!("add(r={:?}, elem={:?})", r, elem);
 298         elem.add_to_row(self, r)
 299     }
 300
 301     /// Adds all the control-flow points to the values for `r`.
 302     crate fn add_all_points(&mut self, r: N) {
 303         self.points.insert_all_into_row(r);
 304     }
 305
 306     /// Adds all elements in `r_from` to `r_to` (because e.g., `r_to:
 307     /// r_from`).
 308     crate fn add_region(&mut self, r_to: N, r_from: N) -> bool {
 309         self.points.union_rows(r_from, r_to)
 310             | self.free_regions.union_rows(r_from, r_to)
 311             | self.placeholders.union_rows(r_from, r_to)
 312     }
 313
 314     /// Returns `true` if the region `r` contains the given element.
 315     crate fn contains(&self, r: N, elem: impl ToElementIndex) -> bool {
 316         elem.contained_in_row(self, r)
 317     }
 318
 319     /// `self[to] |= values[from]`, essentially: that is, take all the
 320     /// elements for the region `from` from `values` and add them to
 321     /// the region `to` in `self`.
 322     crate fn merge_liveness<M: Idx>(&mut self, to: N, from: M, values: &LivenessValues<M>) {
 323         if let Some(set) = values.points.row(from) {
 324             self.points.union_into_row(to, set);
 325         }
 326     }
 327
 328     /// Returns `true` if `sup_region` contains all the CFG points that
 329     /// `sub_region` contains. Ignores universal regions.
 330     crate fn contains_points(&self, sup_region: N, sub_region: N) -> bool {
 331         if let Some(sub_row) = self.points.row(sub_region) {
 332             if let Some(sup_row) = self.points.row(sup_region) {
 333                 sup_row.superset(sub_row)
 334             } else {
 335                 // sup row is empty, so sub row must be empty
 336                 sub_row.is_empty()
 337             }
 338         } else {
 339             // sub row is empty, always true
 340             true
 341         }
 342     }
 343
 344     /// Returns the locations contained within a given region `r`.
 345     crate fn locations_outlived_by<'a>(&'a self, r: N) -> impl Iterator<Item = Location> + 'a {
 346         self.points.row(r).into_iter().flat_map(move |set| {
 347             set.iter()
 348                 .take_while(move |&p| self.elements.point_in_range(p))
 349                 .map(move |p| self.elements.to_location(p))
 350         })
 351     }
 352
 353     /// Returns just the universal regions that are contained in a given region's value.
 354     crate fn universal_regions_outlived_by<'a>(
 355         &'a self,
 356         r: N,
 357     ) -> impl Iterator<Item = RegionVid> + 'a {
 358         self.free_regions
 359             .row(r)
 360             .into_iter()
 361             .flat_map(|set| set.iter())
 362     }
 363
 364     /// Returns all the elements contained in a given region's value.
 365     crate fn placeholders_contained_in<'a>(
 366         &'a self,
 367         r: N,
 368     ) -> impl Iterator<Item = ty::PlaceholderRegion> + 'a {
 369         self.placeholders
 370             .row(r)
 371             .into_iter()
 372             .flat_map(|set| set.iter())
 373             .map(move |p| self.placeholder_indices.lookup_placeholder(p))
 374     }
 375
 376     /// Returns all the elements contained in a given region's value.
 377     crate fn elements_contained_in<'a>(&'a self, r: N) -> impl Iterator<Item = RegionElement> + 'a {
 378         let points_iter = self.locations_outlived_by(r).map(RegionElement::Location);
 379
 380         let free_regions_iter = self.universal_regions_outlived_by(r)
 381             .map(RegionElement::RootUniversalRegion);
 382
 383         let placeholder_universes_iter = self.placeholders_contained_in(r)
 384             .map(RegionElement::PlaceholderRegion);
 385
 386         points_iter
 387             .chain(free_regions_iter)
 388             .chain(placeholder_universes_iter)
 389     }
 390
 391     /// Returns a "pretty" string value of the region. Meant for debugging.
 392     crate fn region_value_str(&self, r: N) -> String {
 393         region_value_str(self.elements_contained_in(r))
 394     }
 395 }
 396
 397 crate trait ToElementIndex: Debug + Copy {
 398     fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool;
 399
 400     fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool;
 401 }
 402
 403 impl ToElementIndex for Location {
 404     fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
 405         let index = values.elements.point_from_location(self);
 406         values.points.insert(row, index)
 407     }
 408
 409     fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
 410         let index = values.elements.point_from_location(self);
 411         values.points.contains(row, index)
 412     }
 413 }
 414
 415 impl ToElementIndex for RegionVid {
 416     fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
 417         values.free_regions.insert(row, self)
 418     }
 419
 420     fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
 421         values.free_regions.contains(row, self)
 422     }
 423 }
 424
 425 impl ToElementIndex for ty::PlaceholderRegion {
 426     fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
 427         let index = values.placeholder_indices.lookup_index(self);
 428         values.placeholders.insert(row, index)
 429     }
 430
 431     fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
 432         let index = values.placeholder_indices.lookup_index(self);
 433         values.placeholders.contains(row, index)
 434     }
 435 }
 436
 437 crate fn location_set_str(
 438     elements: &RegionValueElements,
 439     points: impl IntoIterator<Item = PointIndex>,
 440 ) -> String {
 441     region_value_str(
 442         points
 443             .into_iter()
 444             .take_while(|&p| elements.point_in_range(p))
 445             .map(|p| elements.to_location(p))
 446             .map(RegionElement::Location),
 447     )
 448 }
 449
 450 fn region_value_str(elements: impl IntoIterator<Item = RegionElement>) -> String {
 451     let mut result = String::new();
 452     result.push_str("{");
 453
 454     // Set to Some(l1, l2) when we have observed all the locations
 455     // from l1..=l2 (inclusive) but not yet printed them. This
 456     // gets extended if we then see l3 where l3 is the successor
 457     // to l2.
 458     let mut open_location: Option<(Location, Location)> = None;
 459
 460     let mut sep = "";
 461     let mut push_sep = |s: &mut String| {
 462         s.push_str(sep);
 463         sep = ", ";
 464     };
 465
 466     for element in elements {
 467         match element {
 468             RegionElement::Location(l) => {
 469                 if let Some((location1, location2)) = open_location {
 470                     if location2.block == l.block
 471                         && location2.statement_index == l.statement_index - 1
 472                     {
 473                         open_location = Some((location1, l));
 474                         continue;
 475                     }
 476
 477                     push_sep(&mut result);
 478                     push_location_range(&mut result, location1, location2);
 479                 }
 480
 481                 open_location = Some((l, l));
 482             }
 483
 484             RegionElement::RootUniversalRegion(fr) => {
 485                 if let Some((location1, location2)) = open_location {
 486                     push_sep(&mut result);
 487                     push_location_range(&mut result, location1, location2);
 488                     open_location = None;
 489                 }
 490
 491                 push_sep(&mut result);
 492                 result.push_str(&format!("{:?}", fr));
 493             }
 494
 495             RegionElement::PlaceholderRegion(placeholder) => {
 496                 if let Some((location1, location2)) = open_location {
 497                     push_sep(&mut result);
 498                     push_location_range(&mut result, location1, location2);
 499                     open_location = None;
 500                 }
 501
 502                 push_sep(&mut result);
 503                 result.push_str(&format!("{:?}", placeholder));
 504             }
 505         }
 506     }
 507
 508     if let Some((location1, location2)) = open_location {
 509         push_sep(&mut result);
 510         push_location_range(&mut result, location1, location2);
 511     }
 512
 513     result.push_str("}");
 514
 515     return result;
 516
 517     fn push_location_range(str: &mut String, location1: Location, location2: Location) {
 518         if location1 == location2 {
 519             str.push_str(&format!("{:?}", location1));
 520         } else {
 521             assert_eq!(location1.block, location2.block);
 522             str.push_str(&format!(
 523                 "{:?}[{}..={}]",
 524                 location1.block, location1.statement_index, location2.statement_index
 525             ));
 526         }
 527     }
 528 }