src/librustc_mir/borrow_check/region_infer/values.rs

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