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