diff options
Diffstat (limited to 'compiler/rustc_borrowck/src/region_infer')
5 files changed, 137 insertions, 86 deletions
diff --git a/compiler/rustc_borrowck/src/region_infer/dump_mir.rs b/compiler/rustc_borrowck/src/region_infer/dump_mir.rs index 4d620ac9d..cfbb2766c 100644 --- a/compiler/rustc_borrowck/src/region_infer/dump_mir.rs +++ b/compiler/rustc_borrowck/src/region_infer/dump_mir.rs @@ -67,7 +67,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { with_msg: &mut dyn FnMut(&str) -> io::Result<()>, ) -> io::Result<()> { for region in self.definitions.indices() { - let value = self.liveness_constraints.region_value_str(region); + let value = self.liveness_constraints.pretty_print_live_points(region); if value != "{}" { with_msg(&format!("{region:?} live at {value}"))?; } diff --git a/compiler/rustc_borrowck/src/region_infer/graphviz.rs b/compiler/rustc_borrowck/src/region_infer/graphviz.rs index a0cf22e93..408c8390e 100644 --- a/compiler/rustc_borrowck/src/region_infer/graphviz.rs +++ b/compiler/rustc_borrowck/src/region_infer/graphviz.rs @@ -8,7 +8,6 @@ use std::borrow::Cow; use std::io::{self, Write}; use super::*; -use crate::constraints::OutlivesConstraint; use rustc_graphviz as dot; impl<'tcx> RegionInferenceContext<'tcx> { diff --git a/compiler/rustc_borrowck/src/region_infer/mod.rs b/compiler/rustc_borrowck/src/region_infer/mod.rs index b1f91a056..948221e94 100644 --- a/compiler/rustc_borrowck/src/region_infer/mod.rs +++ b/compiler/rustc_borrowck/src/region_infer/mod.rs @@ -7,7 +7,6 @@ use rustc_data_structures::fx::{FxIndexMap, FxIndexSet}; use rustc_data_structures::graph::scc::Sccs; use rustc_errors::Diagnostic; use rustc_hir::def_id::CRATE_DEF_ID; -use rustc_index::bit_set::SparseBitMatrix; use rustc_index::{IndexSlice, IndexVec}; use rustc_infer::infer::outlives::test_type_match; use rustc_infer::infer::region_constraints::{GenericKind, VarInfos, VerifyBound, VerifyIfEq}; @@ -31,8 +30,8 @@ use crate::{ nll::PoloniusOutput, region_infer::reverse_sccs::ReverseSccGraph, region_infer::values::{ - LivenessValues, PlaceholderIndices, PointIndex, RegionElement, RegionValueElements, - RegionValues, ToElementIndex, + LivenessValues, PlaceholderIndices, RegionElement, RegionValueElements, RegionValues, + ToElementIndex, }, type_check::{free_region_relations::UniversalRegionRelations, Locations}, universal_regions::UniversalRegions, @@ -59,7 +58,7 @@ pub struct RegionInferenceContext<'tcx> { /// regions, these start out empty and steadily grow, though for /// each universally quantified region R they start out containing /// the entire CFG and `end(R)`. - liveness_constraints: LivenessValues<RegionVid>, + liveness_constraints: LivenessValues, /// The outlives constraints computed by the type-check. constraints: Frozen<OutlivesConstraintSet<'tcx>>, @@ -120,9 +119,6 @@ pub struct RegionInferenceContext<'tcx> { /// Information about how the universally quantified regions in /// scope on this function relate to one another. universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>, - - /// The set of loans that are live at a given point in the CFG, when using `-Zpolonius=next`. - live_loans: SparseBitMatrix<PointIndex, BorrowIndex>, } /// Each time that `apply_member_constraint` is successful, it appends @@ -151,6 +147,7 @@ pub(crate) struct AppliedMemberConstraint { pub(crate) member_constraint_index: NllMemberConstraintIndex, } +#[derive(Debug)] pub(crate) struct RegionDefinition<'tcx> { /// What kind of variable is this -- a free region? existential /// variable? etc. (See the `NllRegionVariableOrigin` for more @@ -332,9 +329,8 @@ impl<'tcx> RegionInferenceContext<'tcx> { member_constraints_in: MemberConstraintSet<'tcx, RegionVid>, universe_causes: FxIndexMap<ty::UniverseIndex, UniverseInfo<'tcx>>, type_tests: Vec<TypeTest<'tcx>>, - liveness_constraints: LivenessValues<RegionVid>, + liveness_constraints: LivenessValues, elements: &Rc<RegionValueElements>, - live_loans: SparseBitMatrix<PointIndex, BorrowIndex>, ) -> Self { debug!("universal_regions: {:#?}", universal_regions); debug!("outlives constraints: {:#?}", outlives_constraints); @@ -359,7 +355,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { let mut scc_values = RegionValues::new(elements, universal_regions.len(), &placeholder_indices); - for region in liveness_constraints.rows() { + for region in liveness_constraints.regions() { let scc = constraint_sccs.scc(region); scc_values.merge_liveness(scc, region, &liveness_constraints); } @@ -388,7 +384,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { type_tests, universal_regions, universal_region_relations, - live_loans, }; result.init_free_and_bound_regions(); @@ -679,13 +674,10 @@ impl<'tcx> RegionInferenceContext<'tcx> { // eagerly. let mut outlives_requirements = infcx.tcx.is_typeck_child(mir_def_id).then(Vec::new); - self.check_type_tests( - infcx, - param_env, - body, - outlives_requirements.as_mut(), - &mut errors_buffer, - ); + self.check_type_tests(infcx, body, outlives_requirements.as_mut(), &mut errors_buffer); + + debug!(?errors_buffer); + debug!(?outlives_requirements); // In Polonius mode, the errors about missing universal region relations are in the output // and need to be emitted or propagated. Otherwise, we need to check whether the @@ -700,10 +692,14 @@ impl<'tcx> RegionInferenceContext<'tcx> { self.check_universal_regions(outlives_requirements.as_mut(), &mut errors_buffer); } + debug!(?errors_buffer); + if errors_buffer.is_empty() { self.check_member_constraints(infcx, &mut errors_buffer); } + debug!(?errors_buffer); + let outlives_requirements = outlives_requirements.unwrap_or_default(); if outlives_requirements.is_empty() { @@ -936,7 +932,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { fn check_type_tests( &self, infcx: &InferCtxt<'tcx>, - param_env: ty::ParamEnv<'tcx>, body: &Body<'tcx>, mut propagated_outlives_requirements: Option<&mut Vec<ClosureOutlivesRequirement<'tcx>>>, errors_buffer: &mut RegionErrors<'tcx>, @@ -954,7 +949,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { let generic_ty = type_test.generic_kind.to_ty(tcx); if self.eval_verify_bound( infcx, - param_env, generic_ty, type_test.lower_bound, &type_test.verify_bound, @@ -965,7 +959,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { if let Some(propagated_outlives_requirements) = &mut propagated_outlives_requirements { if self.try_promote_type_test( infcx, - param_env, body, type_test, propagated_outlives_requirements, @@ -1023,7 +1016,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { fn try_promote_type_test( &self, infcx: &InferCtxt<'tcx>, - param_env: ty::ParamEnv<'tcx>, body: &Body<'tcx>, type_test: &TypeTest<'tcx>, propagated_outlives_requirements: &mut Vec<ClosureOutlivesRequirement<'tcx>>, @@ -1085,7 +1077,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { // where `ur` is a local bound -- we are sometimes in a // position to prove things that our caller cannot. See // #53570 for an example. - if self.eval_verify_bound(infcx, param_env, generic_ty, ur, &type_test.verify_bound) { + if self.eval_verify_bound(infcx, generic_ty, ur, &type_test.verify_bound) { continue; } @@ -1268,7 +1260,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { fn eval_verify_bound( &self, infcx: &InferCtxt<'tcx>, - param_env: ty::ParamEnv<'tcx>, generic_ty: Ty<'tcx>, lower_bound: RegionVid, verify_bound: &VerifyBound<'tcx>, @@ -1277,7 +1268,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { match verify_bound { VerifyBound::IfEq(verify_if_eq_b) => { - self.eval_if_eq(infcx, param_env, generic_ty, lower_bound, *verify_if_eq_b) + self.eval_if_eq(infcx, generic_ty, lower_bound, *verify_if_eq_b) } VerifyBound::IsEmpty => { @@ -1291,11 +1282,11 @@ impl<'tcx> RegionInferenceContext<'tcx> { } VerifyBound::AnyBound(verify_bounds) => verify_bounds.iter().any(|verify_bound| { - self.eval_verify_bound(infcx, param_env, generic_ty, lower_bound, verify_bound) + self.eval_verify_bound(infcx, generic_ty, lower_bound, verify_bound) }), VerifyBound::AllBounds(verify_bounds) => verify_bounds.iter().all(|verify_bound| { - self.eval_verify_bound(infcx, param_env, generic_ty, lower_bound, verify_bound) + self.eval_verify_bound(infcx, generic_ty, lower_bound, verify_bound) }), } } @@ -1303,19 +1294,13 @@ impl<'tcx> RegionInferenceContext<'tcx> { fn eval_if_eq( &self, infcx: &InferCtxt<'tcx>, - param_env: ty::ParamEnv<'tcx>, generic_ty: Ty<'tcx>, lower_bound: RegionVid, verify_if_eq_b: ty::Binder<'tcx, VerifyIfEq<'tcx>>, ) -> bool { let generic_ty = self.normalize_to_scc_representatives(infcx.tcx, generic_ty); let verify_if_eq_b = self.normalize_to_scc_representatives(infcx.tcx, verify_if_eq_b); - match test_type_match::extract_verify_if_eq( - infcx.tcx, - param_env, - &verify_if_eq_b, - generic_ty, - ) { + match test_type_match::extract_verify_if_eq(infcx.tcx, &verify_if_eq_b, generic_ty) { Some(r) => { let r_vid = self.to_region_vid(r); self.eval_outlives(r_vid, lower_bound) @@ -1457,6 +1442,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { errors_buffer: &mut RegionErrors<'tcx>, ) { for (fr, fr_definition) in self.definitions.iter_enumerated() { + debug!(?fr, ?fr_definition); match fr_definition.origin { NllRegionVariableOrigin::FreeRegion => { // Go through each of the universal regions `fr` and check that @@ -1963,15 +1949,15 @@ impl<'tcx> RegionInferenceContext<'tcx> { None } - /// Finds some region R such that `fr1: R` and `R` is live at `elem`. + /// Finds some region R such that `fr1: R` and `R` is live at `location`. #[instrument(skip(self), level = "trace", ret)] - pub(crate) fn find_sub_region_live_at(&self, fr1: RegionVid, elem: Location) -> RegionVid { + pub(crate) fn find_sub_region_live_at(&self, fr1: RegionVid, location: Location) -> RegionVid { trace!(scc = ?self.constraint_sccs.scc(fr1)); trace!(universe = ?self.scc_universes[self.constraint_sccs.scc(fr1)]); self.find_constraint_paths_between_regions(fr1, |r| { - // First look for some `r` such that `fr1: r` and `r` is live at `elem` - trace!(?r, liveness_constraints=?self.liveness_constraints.region_value_str(r)); - self.liveness_constraints.contains(r, elem) + // First look for some `r` such that `fr1: r` and `r` is live at `location` + trace!(?r, liveness_constraints=?self.liveness_constraints.pretty_print_live_points(r)); + self.liveness_constraints.is_live_at(r, location) }) .or_else(|| { // If we fail to find that, we may find some `r` such that @@ -2316,7 +2302,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { /// Note: for now, the sets of live loans is only available when using `-Zpolonius=next`. pub(crate) fn is_loan_live_at(&self, loan_idx: BorrowIndex, location: Location) -> bool { let point = self.liveness_constraints.point_from_location(location); - self.live_loans.contains(point, loan_idx) + self.liveness_constraints.is_loan_live_at(loan_idx, point) } } diff --git a/compiler/rustc_borrowck/src/region_infer/opaque_types.rs b/compiler/rustc_borrowck/src/region_infer/opaque_types.rs index fb0e5811c..3764e4c40 100644 --- a/compiler/rustc_borrowck/src/region_infer/opaque_types.rs +++ b/compiler/rustc_borrowck/src/region_infer/opaque_types.rs @@ -36,7 +36,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { /// call `infer_opaque_definition_from_instantiation` to get the inferred /// type of `_Return<'_a>`. `infer_opaque_definition_from_instantiation` /// compares lifetimes directly, so we need to map the inference variables - /// back to concrete lifetimes: `'static`, `ReEarlyBound` or `ReFree`. + /// back to concrete lifetimes: `'static`, `ReEarlyParam` or `ReLateParam`. /// /// First we map all the lifetimes in the concrete type to an equal /// universal region that occurs in the concrete type's args, in this case @@ -315,7 +315,7 @@ fn check_opaque_type_well_formed<'tcx>( parent_def_id = tcx.local_parent(parent_def_id); } - // FIXME(-Ztrait-solver=next): We probably should use `DefiningAnchor::Error` + // FIXME(-Znext-solver): We probably should use `DefiningAnchor::Error` // and prepopulate this `InferCtxt` with known opaque values, rather than // using the `Bind` anchor here. For now it's fine. let infcx = tcx @@ -386,7 +386,7 @@ fn check_opaque_type_parameter_valid( let arg_is_param = match arg.unpack() { GenericArgKind::Type(ty) => matches!(ty.kind(), ty::Param(_)), GenericArgKind::Lifetime(lt) if is_ty_alias => { - matches!(*lt, ty::ReEarlyBound(_) | ty::ReFree(_)) + matches!(*lt, ty::ReEarlyParam(_) | ty::ReLateParam(_)) } // FIXME(#113916): we can't currently check for unique lifetime params, // see that issue for more. We will also have to ignore unused lifetime diff --git a/compiler/rustc_borrowck/src/region_infer/values.rs b/compiler/rustc_borrowck/src/region_infer/values.rs index 38452df32..dc3ee849d 100644 --- a/compiler/rustc_borrowck/src/region_infer/values.rs +++ b/compiler/rustc_borrowck/src/region_infer/values.rs @@ -11,6 +11,8 @@ use rustc_middle::ty::{self, RegionVid}; use std::fmt::Debug; use std::rc::Rc; +use crate::dataflow::BorrowIndex; + /// Maps between a `Location` and a `PointIndex` (and vice versa). pub(crate) struct RegionValueElements { /// For each basic block, how many points are contained within? @@ -90,6 +92,7 @@ impl RegionValueElements { rustc_index::newtype_index! { /// A single integer representing a `Location` in the MIR control-flow /// graph. Constructed efficiently from `RegionValueElements`. + #[orderable] #[debug_format = "PointIndex({})"] pub struct PointIndex {} } @@ -116,71 +119,132 @@ pub(crate) enum RegionElement { PlaceholderRegion(ty::PlaceholderRegion), } -/// When we initially compute liveness, we use an interval matrix storing -/// liveness ranges for each region-vid. -pub(crate) struct LivenessValues<N: Idx> { +/// Records the CFG locations where each region is live. When we initially compute liveness, we use +/// an interval matrix storing liveness ranges for each region-vid. +pub(crate) struct LivenessValues { + /// The map from locations to points. elements: Rc<RegionValueElements>, - points: SparseIntervalMatrix<N, PointIndex>, + + /// For each region: the points where it is live. + points: SparseIntervalMatrix<RegionVid, PointIndex>, + + /// When using `-Zpolonius=next`, for each point: the loans flowing into the live regions at + /// that point. + pub(crate) loans: Option<LiveLoans>, } -impl<N: Idx> LivenessValues<N> { - /// Creates a new set of "region values" that tracks causal information. - /// Each of the regions in num_region_variables will be initialized with an - /// empty set of points and no causal information. +/// Data used to compute the loans that are live at a given point in the CFG, when using +/// `-Zpolonius=next`. +pub(crate) struct LiveLoans { + /// The set of loans that flow into a given region. When individual regions are marked as live + /// in the CFG, these inflowing loans are recorded as live. + pub(crate) inflowing_loans: SparseBitMatrix<RegionVid, BorrowIndex>, + + /// The set of loans that are live at a given point in the CFG. + 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 { + /// Create an empty map of regions to locations where they're live. pub(crate) fn new(elements: Rc<RegionValueElements>) -> Self { - Self { points: SparseIntervalMatrix::new(elements.num_points), elements } + LivenessValues { + points: SparseIntervalMatrix::new(elements.num_points), + elements, + loans: None, + } } /// Iterate through each region that has a value in this set. - pub(crate) fn rows(&self) -> impl Iterator<Item = N> { + pub(crate) fn regions(&self) -> impl Iterator<Item = RegionVid> { self.points.rows() } - /// Adds the given element to the value for the given region. Returns whether - /// the element is newly added (i.e., was not already present). - pub(crate) fn add_element(&mut self, row: N, location: Location) -> bool { - debug!("LivenessValues::add(r={:?}, location={:?})", row, location); - let index = self.elements.point_from_location(location); - self.points.insert(row, index) + /// Records `region` as being live at the given `location`. + pub(crate) fn add_location(&mut self, region: RegionVid, location: Location) { + debug!("LivenessValues::add_location(region={:?}, location={:?})", region, location); + let point = self.elements.point_from_location(location); + self.points.insert(region, point); + + // When available, record the loans flowing into this region as live at the given point. + if let Some(loans) = self.loans.as_mut() { + if let Some(inflowing) = loans.inflowing_loans.row(region) { + loans.live_loans.union_row(point, inflowing); + } + } } - /// Adds all the elements in the given bit array into the given - /// region. Returns whether any of them are newly added. - pub(crate) fn add_elements(&mut self, row: N, locations: &IntervalSet<PointIndex>) -> bool { - debug!("LivenessValues::add_elements(row={:?}, locations={:?})", row, locations); - self.points.union_row(row, locations) + /// Records `region` as being live at all the given `points`. + pub(crate) fn add_points(&mut self, region: RegionVid, points: &IntervalSet<PointIndex>) { + debug!("LivenessValues::add_points(region={:?}, points={:?})", region, points); + self.points.union_row(region, points); + + // When available, record the loans flowing into this region as live at the given points. + 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); + } + } + } + } } - /// Adds all the control-flow points to the values for `r`. - pub(crate) fn add_all_points(&mut self, row: N) { - self.points.insert_all_into_row(row); + /// Records `region` as being live at all the control-flow points. + pub(crate) fn add_all_points(&mut self, region: RegionVid) { + self.points.insert_all_into_row(region); } - /// Returns `true` if the region `r` contains the given element. - pub(crate) fn contains(&self, row: N, location: Location) -> bool { - let index = self.elements.point_from_location(location); - self.points.row(row).is_some_and(|r| r.contains(index)) + /// Returns whether `region` is marked live at the given `location`. + pub(crate) fn is_live_at(&self, region: RegionVid, location: Location) -> bool { + let point = self.elements.point_from_location(location); + self.points.row(region).is_some_and(|r| r.contains(point)) + } + + /// Returns whether `region` is marked live at any location. + pub(crate) fn is_live_anywhere(&self, region: RegionVid) -> bool { + self.live_points(region).next().is_some() } - /// Returns an iterator of all the elements contained by the region `r` - pub(crate) fn get_elements(&self, row: N) -> impl Iterator<Item = Location> + '_ { + /// Returns an iterator of all the points where `region` is live. + fn live_points(&self, region: RegionVid) -> impl Iterator<Item = PointIndex> + '_ { self.points - .row(row) + .row(region) .into_iter() .flat_map(|set| set.iter()) - .take_while(move |&p| self.elements.point_in_range(p)) - .map(move |p| self.elements.to_location(p)) + .take_while(|&p| self.elements.point_in_range(p)) } - /// Returns a "pretty" string value of the region. Meant for debugging. - pub(crate) fn region_value_str(&self, r: N) -> String { - region_value_str(self.get_elements(r).map(RegionElement::Location)) + /// For debugging purposes, returns a pretty-printed string of the points where the `region` is + /// live. + 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) } + + /// When using `-Zpolonius=next`, returns whether the `loan_idx` is live at the given `point`. + 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) + } } /// Maps from `ty::PlaceholderRegion` values that are used in the rest of @@ -307,7 +371,7 @@ impl<N: Idx> RegionValues<N> { /// `self[to] |= values[from]`, essentially: that is, take all the /// elements for the region `from` from `values` and add them to /// the region `to` in `self`. - pub(crate) fn merge_liveness<M: Idx>(&mut self, to: N, from: M, values: &LivenessValues<M>) { + pub(crate) fn merge_liveness(&mut self, to: N, from: RegionVid, values: &LivenessValues) { if let Some(set) = values.points.row(from) { self.points.union_row(to, set); } @@ -376,7 +440,7 @@ impl<N: Idx> RegionValues<N> { /// Returns a "pretty" string value of the region. Meant for debugging. pub(crate) fn region_value_str(&self, r: N) -> String { - region_value_str(self.elements_contained_in(r)) + pretty_print_region_elements(self.elements_contained_in(r)) } } @@ -420,11 +484,12 @@ impl ToElementIndex for ty::PlaceholderRegion { } } -pub(crate) fn location_set_str( +/// For debugging purposes, returns a pretty-printed string of the given points. +pub(crate) fn pretty_print_points( elements: &RegionValueElements, points: impl IntoIterator<Item = PointIndex>, ) -> String { - region_value_str( + pretty_print_region_elements( points .into_iter() .take_while(|&p| elements.point_in_range(p)) @@ -433,7 +498,8 @@ pub(crate) fn location_set_str( ) } -fn region_value_str(elements: impl IntoIterator<Item = RegionElement>) -> String { +/// For debugging purposes, returns a pretty-printed string of the given region elements. +fn pretty_print_region_elements(elements: impl IntoIterator<Item = RegionElement>) -> String { let mut result = String::new(); result.push('{'); |