use std::fmt::Debug;
use std::rc::Rc;
use rustc_data_structures::fx::{FxHashSet, FxIndexSet};
use rustc_index::bit_set::SparseBitMatrix;
use rustc_index::interval::{IntervalSet, SparseIntervalMatrix};
use rustc_index::Idx;
use rustc_middle::mir::{BasicBlock, Location};
use rustc_middle::ty::{self, RegionVid};
use rustc_mir_dataflow::points::{DenseLocationMap, PointIndex};
use tracing::debug;
use crate::BorrowIndex;
rustc_index::newtype_index! {
#[debug_format = "PlaceholderIndex({})"]
pub struct PlaceholderIndex {}
}
#[derive(Debug, Clone)]
pub(crate) enum RegionElement {
Location(Location),
RootUniversalRegion(RegionVid),
PlaceholderRegion(ty::PlaceholderRegion),
}
pub(crate) struct LivenessValues {
elements: Rc<DenseLocationMap>,
live_regions: Option<FxHashSet<RegionVid>>,
points: Option<SparseIntervalMatrix<RegionVid, PointIndex>>,
pub(crate) loans: Option<LiveLoans>,
}
pub(crate) struct LiveLoans {
pub(crate) inflowing_loans: SparseBitMatrix<RegionVid, BorrowIndex>,
pub(crate) live_loans: SparseBitMatrix<PointIndex, BorrowIndex>,
}
impl LiveLoans {
pub(crate) fn new(num_loans: usize) -> Self {
LiveLoans {
live_loans: SparseBitMatrix::new(num_loans),
inflowing_loans: SparseBitMatrix::new(num_loans),
}
}
}
impl LivenessValues {
pub(crate) fn with_specific_points(elements: Rc<DenseLocationMap>) -> Self {
LivenessValues {
live_regions: None,
points: Some(SparseIntervalMatrix::new(elements.num_points())),
elements,
loans: None,
}
}
pub(crate) fn without_specific_points(elements: Rc<DenseLocationMap>) -> Self {
LivenessValues {
live_regions: Some(Default::default()),
points: None,
elements,
loans: None,
}
}
pub(crate) fn regions(&self) -> impl Iterator<Item = RegionVid> + '_ {
self.points.as_ref().expect("use with_specific_points").rows()
}
#[rustc_lint_query_instability]
#[allow(rustc::potential_query_instability)]
pub(crate) fn live_regions_unordered(&self) -> impl Iterator<Item = RegionVid> + '_ {
self.live_regions.as_ref().unwrap().iter().copied()
}
pub(crate) fn add_location(&mut self, region: RegionVid, location: Location) {
let point = self.elements.point_from_location(location);
debug!("LivenessValues::add_location(region={:?}, location={:?})", region, location);
if let Some(points) = &mut self.points {
points.insert(region, point);
} else {
if self.elements.point_in_range(point) {
self.live_regions.as_mut().unwrap().insert(region);
}
}
if let Some(loans) = self.loans.as_mut() {
if let Some(inflowing) = loans.inflowing_loans.row(region) {
loans.live_loans.union_row(point, inflowing);
}
}
}
pub(crate) fn add_points(&mut self, region: RegionVid, points: &IntervalSet<PointIndex>) {
debug!("LivenessValues::add_points(region={:?}, points={:?})", region, points);
if let Some(this) = &mut self.points {
this.union_row(region, points);
} else {
if points.iter().any(|point| self.elements.point_in_range(point)) {
self.live_regions.as_mut().unwrap().insert(region);
}
}
if let Some(loans) = self.loans.as_mut() {
if let Some(inflowing) = loans.inflowing_loans.row(region) {
if !inflowing.is_empty() {
for point in points.iter() {
loans.live_loans.union_row(point, inflowing);
}
}
}
}
}
pub(crate) fn add_all_points(&mut self, region: RegionVid) {
if let Some(points) = &mut self.points {
points.insert_all_into_row(region);
} else {
self.live_regions.as_mut().unwrap().insert(region);
}
}
pub(crate) fn is_live_at(&self, region: RegionVid, location: Location) -> bool {
let point = self.elements.point_from_location(location);
if let Some(points) = &self.points {
points.row(region).is_some_and(|r| r.contains(point))
} else {
unreachable!(
"Should be using LivenessValues::with_specific_points to ask whether live at a location"
)
}
}
fn live_points(&self, region: RegionVid) -> impl Iterator<Item = PointIndex> + '_ {
let Some(points) = &self.points else {
unreachable!(
"Should be using LivenessValues::with_specific_points to ask whether live at a location"
)
};
points
.row(region)
.into_iter()
.flat_map(|set| set.iter())
.take_while(|&p| self.elements.point_in_range(p))
}
pub(crate) fn pretty_print_live_points(&self, region: RegionVid) -> String {
pretty_print_region_elements(
self.live_points(region).map(|p| RegionElement::Location(self.elements.to_location(p))),
)
}
#[inline]
pub(crate) fn point_from_location(&self, location: Location) -> PointIndex {
self.elements.point_from_location(location)
}
pub(crate) fn is_loan_live_at(&self, loan_idx: BorrowIndex, point: PointIndex) -> bool {
self.loans
.as_ref()
.expect("Accessing live loans requires `-Zpolonius=next`")
.live_loans
.contains(point, loan_idx)
}
}
#[derive(Debug, Default)]
pub(crate) struct PlaceholderIndices {
indices: FxIndexSet<ty::PlaceholderRegion>,
}
impl PlaceholderIndices {
pub(crate) fn insert(&mut self, placeholder: ty::PlaceholderRegion) -> PlaceholderIndex {
let (index, _) = self.indices.insert_full(placeholder);
index.into()
}
pub(crate) fn lookup_index(&self, placeholder: ty::PlaceholderRegion) -> PlaceholderIndex {
self.indices.get_index_of(&placeholder).unwrap().into()
}
pub(crate) fn lookup_placeholder(
&self,
placeholder: PlaceholderIndex,
) -> ty::PlaceholderRegion {
self.indices[placeholder.index()]
}
pub(crate) fn len(&self) -> usize {
self.indices.len()
}
}
#[derive(Clone)]
pub(crate) struct RegionValues<N: Idx> {
elements: Rc<DenseLocationMap>,
placeholder_indices: Rc<PlaceholderIndices>,
points: SparseIntervalMatrix<N, PointIndex>,
free_regions: SparseBitMatrix<N, RegionVid>,
placeholders: SparseBitMatrix<N, PlaceholderIndex>,
}
impl<N: Idx> RegionValues<N> {
pub(crate) fn new(
elements: &Rc<DenseLocationMap>,
num_universal_regions: usize,
placeholder_indices: &Rc<PlaceholderIndices>,
) -> Self {
let num_placeholders = placeholder_indices.len();
Self {
elements: elements.clone(),
points: SparseIntervalMatrix::new(elements.num_points()),
placeholder_indices: placeholder_indices.clone(),
free_regions: SparseBitMatrix::new(num_universal_regions),
placeholders: SparseBitMatrix::new(num_placeholders),
}
}
pub(crate) fn add_element(&mut self, r: N, elem: impl ToElementIndex) -> bool {
debug!("add(r={:?}, elem={:?})", r, elem);
elem.add_to_row(self, r)
}
pub(crate) fn add_all_points(&mut self, r: N) {
self.points.insert_all_into_row(r);
}
pub(crate) fn add_region(&mut self, r_to: N, r_from: N) -> bool {
self.points.union_rows(r_from, r_to)
| self.free_regions.union_rows(r_from, r_to)
| self.placeholders.union_rows(r_from, r_to)
}
pub(crate) fn contains(&self, r: N, elem: impl ToElementIndex) -> bool {
elem.contained_in_row(self, r)
}
pub(crate) fn first_non_contained_inclusive(
&self,
r: N,
block: BasicBlock,
start: usize,
end: usize,
) -> Option<usize> {
let row = self.points.row(r)?;
let block = self.elements.entry_point(block);
let start = block.plus(start);
let end = block.plus(end);
let first_unset = row.first_unset_in(start..=end)?;
Some(first_unset.index() - block.index())
}
pub(crate) fn merge_liveness(&mut self, to: N, from: RegionVid, values: &LivenessValues) {
let Some(value_points) = &values.points else {
panic!("LivenessValues must track specific points for use in merge_liveness");
};
if let Some(set) = value_points.row(from) {
self.points.union_row(to, set);
}
}
pub(crate) fn contains_points(&self, sup_region: N, sub_region: N) -> bool {
if let Some(sub_row) = self.points.row(sub_region) {
if let Some(sup_row) = self.points.row(sup_region) {
sup_row.superset(sub_row)
} else {
sub_row.is_empty()
}
} else {
true
}
}
pub(crate) fn locations_outlived_by<'a>(&'a self, r: N) -> impl Iterator<Item = Location> + 'a {
self.points.row(r).into_iter().flat_map(move |set| {
set.iter()
.take_while(move |&p| self.elements.point_in_range(p))
.map(move |p| self.elements.to_location(p))
})
}
pub(crate) fn universal_regions_outlived_by<'a>(
&'a self,
r: N,
) -> impl Iterator<Item = RegionVid> + 'a {
self.free_regions.row(r).into_iter().flat_map(|set| set.iter())
}
pub(crate) fn placeholders_contained_in<'a>(
&'a self,
r: N,
) -> impl Iterator<Item = ty::PlaceholderRegion> + 'a {
self.placeholders
.row(r)
.into_iter()
.flat_map(|set| set.iter())
.map(move |p| self.placeholder_indices.lookup_placeholder(p))
}
pub(crate) fn elements_contained_in<'a>(
&'a self,
r: N,
) -> impl Iterator<Item = RegionElement> + 'a {
let points_iter = self.locations_outlived_by(r).map(RegionElement::Location);
let free_regions_iter =
self.universal_regions_outlived_by(r).map(RegionElement::RootUniversalRegion);
let placeholder_universes_iter =
self.placeholders_contained_in(r).map(RegionElement::PlaceholderRegion);
points_iter.chain(free_regions_iter).chain(placeholder_universes_iter)
}
pub(crate) fn region_value_str(&self, r: N) -> String {
pretty_print_region_elements(self.elements_contained_in(r))
}
}
pub(crate) trait ToElementIndex: Debug + Copy {
fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool;
fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool;
}
impl ToElementIndex for Location {
fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
let index = values.elements.point_from_location(self);
values.points.insert(row, index)
}
fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
let index = values.elements.point_from_location(self);
values.points.contains(row, index)
}
}
impl ToElementIndex for RegionVid {
fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
values.free_regions.insert(row, self)
}
fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
values.free_regions.contains(row, self)
}
}
impl ToElementIndex for ty::PlaceholderRegion {
fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool {
let index = values.placeholder_indices.lookup_index(self);
values.placeholders.insert(row, index)
}
fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool {
let index = values.placeholder_indices.lookup_index(self);
values.placeholders.contains(row, index)
}
}
pub(crate) fn pretty_print_points(
elements: &DenseLocationMap,
points: impl IntoIterator<Item = PointIndex>,
) -> String {
pretty_print_region_elements(
points
.into_iter()
.take_while(|&p| elements.point_in_range(p))
.map(|p| elements.to_location(p))
.map(RegionElement::Location),
)
}
fn pretty_print_region_elements(elements: impl IntoIterator<Item = RegionElement>) -> String {
let mut result = String::new();
result.push('{');
let mut open_location: Option<(Location, Location)> = None;
let mut sep = "";
let mut push_sep = |s: &mut String| {
s.push_str(sep);
sep = ", ";
};
for element in elements {
match element {
RegionElement::Location(l) => {
if let Some((location1, location2)) = open_location {
if location2.block == l.block
&& location2.statement_index == l.statement_index - 1
{
open_location = Some((location1, l));
continue;
}
push_sep(&mut result);
push_location_range(&mut result, location1, location2);
}
open_location = Some((l, l));
}
RegionElement::RootUniversalRegion(fr) => {
if let Some((location1, location2)) = open_location {
push_sep(&mut result);
push_location_range(&mut result, location1, location2);
open_location = None;
}
push_sep(&mut result);
result.push_str(&format!("{fr:?}"));
}
RegionElement::PlaceholderRegion(placeholder) => {
if let Some((location1, location2)) = open_location {
push_sep(&mut result);
push_location_range(&mut result, location1, location2);
open_location = None;
}
push_sep(&mut result);
result.push_str(&format!("{placeholder:?}"));
}
}
}
if let Some((location1, location2)) = open_location {
push_sep(&mut result);
push_location_range(&mut result, location1, location2);
}
result.push('}');
return result;
fn push_location_range(str: &mut String, location1: Location, location2: Location) {
if location1 == location2 {
str.push_str(&format!("{location1:?}"));
} else {
assert_eq!(location1.block, location2.block);
str.push_str(&format!(
"{:?}[{}..={}]",
location1.block, location1.statement_index, location2.statement_index
));
}
}
}