compiler/rustc_borrowck/src/region_infer/values.rs

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