compiler/rustc_borrowck/src/region_infer/values.rs

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