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