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