From b7b3d2cee0e371fdecf9726ab949a24ead3dcb97 Mon Sep 17 00:00:00 2001 From: Niko Matsakis Date: Wed, 15 Jun 2022 08:46:19 -0400 Subject: [PATCH] generalize the outlives obligation code The code now accepts `Binder` instead of just `OutlivesPredicate` and thus exercises the new, generalized `IfEqBound` codepaths. Note though that we never *produce* Binder, so we are only testing a subset of those codepaths that excludes actual higher-ranked outlives bounds. --- .../src/infer/outlives/obligations.rs | 36 ++++++++--- .../src/infer/outlives/test_type_match.rs | 26 +++++++- .../rustc_infer/src/infer/outlives/verify.rs | 63 +++++++++++++------ src/test/ui/borrowck/issue-71546.rs | 14 ++--- src/test/ui/borrowck/issue-71546.stderr | 59 ----------------- .../generic-associated-types/issue-86483.rs | 8 ++- .../issue-86483.stderr | 50 --------------- ...sue-88586-hr-self-outlives-in-trait-def.rs | 8 ++- ...88586-hr-self-outlives-in-trait-def.stderr | 19 ------ 9 files changed, 109 insertions(+), 174 deletions(-) delete mode 100644 src/test/ui/borrowck/issue-71546.stderr delete mode 100644 src/test/ui/generic-associated-types/issue-86483.stderr delete mode 100644 src/test/ui/higher-rank-trait-bounds/issue-88586-hr-self-outlives-in-trait-def.stderr diff --git a/compiler/rustc_infer/src/infer/outlives/obligations.rs b/compiler/rustc_infer/src/infer/outlives/obligations.rs index cd9f020abd0..42a173bf092 100644 --- a/compiler/rustc_infer/src/infer/outlives/obligations.rs +++ b/compiler/rustc_infer/src/infer/outlives/obligations.rs @@ -359,13 +359,21 @@ fn projection_must_outlive( // #55756) in cases where you have e.g., `>::Item: // 'a` in the environment but `trait Foo<'b> { type Item: 'b // }` in the trait definition. - approx_env_bounds.retain(|bound| match *bound.0.kind() { - ty::Projection(projection_ty) => self - .verify_bound - .projection_declared_bounds_from_trait(projection_ty) - .all(|r| r != bound.1), - - _ => panic!("expected only projection types from env, not {:?}", bound.0), + approx_env_bounds.retain(|bound_outlives| { + // OK to skip binder because we only manipulate and compare against other + // values from the same inder. e.g. if we have (e.g.) `for<'a> >::Item: 'a` + // in `bound`, the `'a` will be a `^1` (bound, debruijn index == innermost) region. + // If the declaration is `trait Trait<'b> { type Item: 'b; }`, then `projection_declared_bounds_from_trait` + // will be invoked with `['b => ^1]` and so we will get `^1` returned. + let bound = bound_outlives.skip_binder(); + match *bound.0.kind() { + ty::Projection(projection_ty) => self + .verify_bound + .projection_declared_bounds_from_trait(projection_ty) + .all(|r| r != bound.1), + + _ => panic!("expected only projection types from env, not {:?}", bound.0), + } }); // If declared bounds list is empty, the only applicable rule is @@ -416,8 +424,16 @@ fn projection_must_outlive( if !trait_bounds.is_empty() && trait_bounds[1..] .iter() - .chain(approx_env_bounds.iter().map(|b| &b.1)) - .all(|b| *b == trait_bounds[0]) + .map(|r| Some(*r)) + .chain( + // NB: The environment may contain `for<'a> T: 'a` style bounds. + // In that case, we don't know if they are equal to the trait bound + // or not (since we don't *know* whether the environment bound even applies), + // so just map to `None` here if there are bound vars, ensuring that + // the call to `all` will fail below. + approx_env_bounds.iter().map(|b| b.map_bound(|b| b.1).no_bound_vars()), + ) + .all(|b| b == Some(trait_bounds[0])) { let unique_bound = trait_bounds[0]; debug!("projection_must_outlive: unique trait bound = {:?}", unique_bound); @@ -433,7 +449,7 @@ fn projection_must_outlive( // even though a satisfactory solution exists. let generic = GenericKind::Projection(projection_ty); let verify_bound = self.verify_bound.generic_bound(generic); - debug!("projection_must_outlive: pushing verify_bound={:?}", verify_bound,); + debug!("projection_must_outlive: pushing {:?}", verify_bound); self.delegate.push_verify(origin, generic, region, verify_bound); } } diff --git a/compiler/rustc_infer/src/infer/outlives/test_type_match.rs b/compiler/rustc_infer/src/infer/outlives/test_type_match.rs index 99d6aabf0d6..bdd31dafd90 100644 --- a/compiler/rustc_infer/src/infer/outlives/test_type_match.rs +++ b/compiler/rustc_infer/src/infer/outlives/test_type_match.rs @@ -34,6 +34,7 @@ /// like are used. This is a particular challenge since this function is invoked /// very late in inference and hence cannot make use of the normal inference /// machinery. +#[tracing::instrument(level = "Debug", skip(tcx, param_env))] pub fn extract_verify_if_eq_bound<'tcx>( tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>, @@ -61,6 +62,25 @@ pub fn extract_verify_if_eq_bound<'tcx>( } } +/// True if a (potentially higher-ranked) outlives +#[tracing::instrument(level = "Debug", skip(tcx, param_env))] +pub(super) fn can_match_erased_ty<'tcx>( + tcx: TyCtxt<'tcx>, + param_env: ty::ParamEnv<'tcx>, + outlives_predicate: ty::Binder<'tcx, ty::TypeOutlivesPredicate<'tcx>>, + erased_ty: Ty<'tcx>, +) -> bool { + assert!(!outlives_predicate.has_escaping_bound_vars()); + let erased_outlives_predicate = tcx.erase_regions(outlives_predicate); + let outlives_ty = erased_outlives_predicate.skip_binder().0; + if outlives_ty == erased_ty { + // pointless micro-optimization + true + } else { + Match::new(tcx, param_env).relate(outlives_ty, erased_ty).is_ok() + } +} + struct Match<'tcx> { tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>, @@ -82,6 +102,7 @@ fn no_match(&self) -> RelateResult<'tcx, T> { /// Binds the pattern variable `br` to `value`; returns an `Err` if the pattern /// is already bound to a different value. + #[tracing::instrument(level = "Debug", skip(self))] fn bind( &mut self, br: ty::BoundRegion, @@ -133,8 +154,9 @@ fn regions( pattern: ty::Region<'tcx>, value: ty::Region<'tcx>, ) -> RelateResult<'tcx, ty::Region<'tcx>> { + debug!("self.pattern_depth = {:?}", self.pattern_depth); if let ty::RegionKind::ReLateBound(depth, br) = pattern.kind() && depth == self.pattern_depth { - self.bind(br, pattern) + self.bind(br, value) } else if pattern == value { Ok(pattern) } else { @@ -142,6 +164,7 @@ fn regions( } } + #[instrument(skip(self), level = "debug")] fn tys(&mut self, pattern: Ty<'tcx>, value: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> { if pattern == value { return Ok(pattern); @@ -150,6 +173,7 @@ fn tys(&mut self, pattern: Ty<'tcx>, value: Ty<'tcx>) -> RelateResult<'tcx, Ty<' } } + #[instrument(skip(self), level = "debug")] fn consts( &mut self, pattern: ty::Const<'tcx>, diff --git a/compiler/rustc_infer/src/infer/outlives/verify.rs b/compiler/rustc_infer/src/infer/outlives/verify.rs index e17ec3034a5..a88bcdaef58 100644 --- a/compiler/rustc_infer/src/infer/outlives/verify.rs +++ b/compiler/rustc_infer/src/infer/outlives/verify.rs @@ -1,4 +1,5 @@ use crate::infer::outlives::env::RegionBoundPairs; +use crate::infer::region_constraints::VerifyIfEq; use crate::infer::{GenericKind, VerifyBound}; use rustc_data_structures::captures::Captures; use rustc_data_structures::sso::SsoHashSet; @@ -82,25 +83,39 @@ fn param_bound(&self, param_ty: ty::ParamTy) -> VerifyBound<'tcx> { debug!("param_bound(param_ty={:?})", param_ty); // Start with anything like `T: 'a` we can scrape from the - // environment - let param_bounds = - self.declared_generic_bounds_from_env(param_ty).into_iter().map(|outlives| outlives.1); + // environment. If the environment contains something like + // `for<'a> T: 'a`, then we know that `T` outlives everything. + let declared_bounds_from_env = self.declared_generic_bounds_from_env(param_ty); + let mut param_bounds = vec![]; + for declared_bound in declared_bounds_from_env { + let bound_region = declared_bound.map_bound(|outlives| outlives.1); + if let Some(region) = bound_region.no_bound_vars() { + // This is `T: 'a` for some free region `'a`. + param_bounds.push(VerifyBound::OutlivedBy(region)); + } else { + // This is `for<'a> T: 'a`. This means that `T` outlives everything! All done here. + return VerifyBound::AllBounds(vec![]); + } + } // Add in the default bound of fn body that applies to all in // scope type parameters: - let param_bounds = param_bounds.chain(self.implicit_region_bound); - - let any_bounds: Vec<_> = param_bounds.map(|r| VerifyBound::OutlivedBy(r)).collect(); + if let Some(r) = self.implicit_region_bound { + param_bounds.push(VerifyBound::OutlivedBy(r)); + } - if any_bounds.is_empty() { + if param_bounds.is_empty() { // We know that all types `T` outlive `'empty`, so if we // can find no other bound, then check that the region // being tested is `'empty`. VerifyBound::IsEmpty + } else if param_bounds.len() == 1 { + // Micro-opt: no need to store the vector if it's just len 1 + param_bounds.pop().unwrap() } else { // If we can find any other bound `R` such that `T: R`, then // we don't need to check for `'empty`, because `R: 'empty`. - VerifyBound::AnyBound(any_bounds) + VerifyBound::AnyBound(param_bounds) } } @@ -120,7 +135,7 @@ fn param_bound(&self, param_ty: ty::ParamTy) -> VerifyBound<'tcx> { pub fn projection_approx_declared_bounds_from_env( &self, projection_ty: ty::ProjectionTy<'tcx>, - ) -> Vec, ty::Region<'tcx>>> { + ) -> Vec, ty::Region<'tcx>>>> { let projection_ty = GenericKind::Projection(projection_ty).to_ty(self.tcx); let erased_projection_ty = self.tcx.erase_regions(projection_ty); self.declared_generic_bounds_from_env_for_erased_ty(erased_projection_ty) @@ -150,14 +165,15 @@ pub fn projection_bound( let env_bounds = self .projection_approx_declared_bounds_from_env(projection_ty) .into_iter() - .map(|ty::OutlivesPredicate(ty, r)| { - if ty == projection_ty_as_ty { + .map(|binder| { + if let Some(ty::OutlivesPredicate(ty, r)) = binder.no_bound_vars() && ty == projection_ty_as_ty { // Micro-optimize if this is an exact match (this // occurs often when there are no region variables // involved). VerifyBound::OutlivedBy(r) } else { - VerifyBound::IfEq(ty, r) + let verify_if_eq_b = binder.map_bound(|ty::OutlivesPredicate(ty, bound)| VerifyIfEq { ty, bound }); + VerifyBound::IfEqBound(verify_if_eq_b) } }); @@ -210,7 +226,7 @@ fn recursive_bound( fn declared_generic_bounds_from_env( &self, param_ty: ty::ParamTy, - ) -> Vec, ty::Region<'tcx>>> { + ) -> Vec, ty::Region<'tcx>>>> { let generic_ty = param_ty.to_ty(self.tcx); self.declared_generic_bounds_from_env_for_erased_ty(generic_ty) } @@ -229,7 +245,7 @@ fn declared_generic_bounds_from_env( fn declared_generic_bounds_from_env_for_erased_ty( &self, erased_ty: Ty<'tcx>, - ) -> Vec, ty::Region<'tcx>>> { + ) -> Vec, ty::Region<'tcx>>>> { let tcx = self.tcx; // To start, collect bounds from user environment. Note that @@ -259,7 +275,8 @@ fn declared_generic_bounds_from_env_for_erased_ty( ); let p_ty = p.to_ty(tcx); let erased_p_ty = self.tcx.erase_regions(p_ty); - (erased_p_ty == erased_ty).then_some(ty::OutlivesPredicate(p.to_ty(tcx), r)) + (erased_p_ty == erased_ty) + .then_some(ty::Binder::dummy(ty::OutlivesPredicate(p.to_ty(tcx), r))) }); param_bounds @@ -348,11 +365,17 @@ fn collect_outlives_from_predicate_list( &self, erased_ty: Ty<'tcx>, predicates: impl Iterator>, - ) -> impl Iterator, ty::Region<'tcx>>> { + ) -> impl Iterator, ty::Region<'tcx>>>> + { let tcx = self.tcx; - predicates - .filter_map(|p| p.to_opt_type_outlives()) - .filter_map(|p| p.no_bound_vars()) - .filter(move |p| tcx.erase_regions(p.0) == erased_ty) + let param_env = self.param_env; + predicates.filter_map(|p| p.to_opt_type_outlives()).filter(move |outlives_predicate| { + super::test_type_match::can_match_erased_ty( + tcx, + param_env, + *outlives_predicate, + erased_ty, + ) + }) } } diff --git a/src/test/ui/borrowck/issue-71546.rs b/src/test/ui/borrowck/issue-71546.rs index b20c39193de..42100edeaa7 100644 --- a/src/test/ui/borrowck/issue-71546.rs +++ b/src/test/ui/borrowck/issue-71546.rs @@ -1,4 +1,8 @@ // Regression test for #71546. +// +// Made to pass as part of fixing #98095. +// +// check-pass pub fn serialize_as_csv(value: &V) -> Result where @@ -6,15 +10,7 @@ pub fn serialize_as_csv(value: &V) -> Result for<'a> &'a V: IntoIterator, for<'a> <&'a V as IntoIterator>::Item: ToString + 'static, { - let csv_str: String = value - //~^ ERROR higher-ranked lifetime error - //~| ERROR higher-ranked lifetime error - //~| ERROR higher-ranked lifetime error - .into_iter() - .map(|elem| elem.to_string()) - //~^ ERROR higher-ranked lifetime error - .collect::(); - //~^ ERROR higher-ranked lifetime error + let csv_str: String = value.into_iter().map(|elem| elem.to_string()).collect::(); Ok(csv_str) } diff --git a/src/test/ui/borrowck/issue-71546.stderr b/src/test/ui/borrowck/issue-71546.stderr deleted file mode 100644 index b8d79f0939b..00000000000 --- a/src/test/ui/borrowck/issue-71546.stderr +++ /dev/null @@ -1,59 +0,0 @@ -error: higher-ranked lifetime error - --> $DIR/issue-71546.rs:9:27 - | -LL | let csv_str: String = value - | ___________________________^ -LL | | -LL | | -LL | | -LL | | .into_iter() -LL | | .map(|elem| elem.to_string()) - | |_____________________________________^ - | - = note: could not prove for<'r> [closure@$DIR/issue-71546.rs:14:14: 14:37] well-formed - -error: higher-ranked lifetime error - --> $DIR/issue-71546.rs:9:27 - | -LL | let csv_str: String = value - | ___________________________^ -LL | | -LL | | -LL | | -LL | | .into_iter() -LL | | .map(|elem| elem.to_string()) - | |_____________________________________^ - | - = note: could not prove for<'r, 's> Map<<&'r V as IntoIterator>::IntoIter, [closure@$DIR/issue-71546.rs:14:14: 14:37]> well-formed - -error: higher-ranked lifetime error - --> $DIR/issue-71546.rs:9:27 - | -LL | let csv_str: String = value - | ___________________________^ -LL | | -LL | | -LL | | -... | -LL | | -LL | | .collect::(); - | |____________________________^ - | - = note: could not prove for<'r, 's> Map<<&'r V as IntoIterator>::IntoIter, [closure@$DIR/issue-71546.rs:14:14: 14:37]> well-formed - -error: higher-ranked lifetime error - --> $DIR/issue-71546.rs:14:14 - | -LL | .map(|elem| elem.to_string()) - | ^^^^^^^^^^^^^^^^^^^^^^^ - | - = note: could not prove for<'a> <&'a V as IntoIterator>::Item: 'static - -error: higher-ranked lifetime error - --> $DIR/issue-71546.rs:16:10 - | -LL | .collect::(); - | ^^^^^^^ - -error: aborting due to 5 previous errors - diff --git a/src/test/ui/generic-associated-types/issue-86483.rs b/src/test/ui/generic-associated-types/issue-86483.rs index a8b54c354e3..07dd0bffd46 100644 --- a/src/test/ui/generic-associated-types/issue-86483.rs +++ b/src/test/ui/generic-associated-types/issue-86483.rs @@ -1,14 +1,16 @@ // Regression test of #86483. +// +// Made to pass as part of fixing #98095. +// +// check-pass #![feature(generic_associated_types)] -pub trait IceIce //~ ERROR: the parameter type `T` may not live long enough +pub trait IceIce where for<'a> T: 'a, { type Ice<'v>: IntoIterator; - //~^ ERROR: the parameter type `T` may not live long enough - //~| ERROR: the parameter type `T` may not live long enough } fn main() {} diff --git a/src/test/ui/generic-associated-types/issue-86483.stderr b/src/test/ui/generic-associated-types/issue-86483.stderr deleted file mode 100644 index a13dc043dc5..00000000000 --- a/src/test/ui/generic-associated-types/issue-86483.stderr +++ /dev/null @@ -1,50 +0,0 @@ -error[E0311]: the parameter type `T` may not live long enough - --> $DIR/issue-86483.rs:5:1 - | -LL | / pub trait IceIce -LL | | where -LL | | for<'a> T: 'a, -LL | | { -... | -LL | | -LL | | } - | |_^ - | - = note: ...so that the type `T` will meet its required lifetime bounds... -note: ...that is required by this bound - --> $DIR/issue-86483.rs:7:16 - | -LL | for<'a> T: 'a, - | ^^ -help: consider adding an explicit lifetime bound... - | -LL | for<'a> T: 'a + 'a, - | ++++ - -error[E0311]: the parameter type `T` may not live long enough - --> $DIR/issue-86483.rs:9:5 - | -LL | type Ice<'v>: IntoIterator; - | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ...so that the type `T` will meet its required lifetime bounds... - | -note: ...that is required by this bound - --> $DIR/issue-86483.rs:7:16 - | -LL | for<'a> T: 'a, - | ^^ -help: consider adding an explicit lifetime bound... - | -LL | for<'a> T: 'a + 'a, - | ++++ - -error[E0309]: the parameter type `T` may not live long enough - --> $DIR/issue-86483.rs:9:32 - | -LL | type Ice<'v>: IntoIterator; - | ^^^^^^^^^^^^ - help: consider adding a where clause: `where T: 'v` - | | - | ...so that the reference type `&'v T` does not outlive the data it points at - -error: aborting due to 3 previous errors - -For more information about this error, try `rustc --explain E0309`. diff --git a/src/test/ui/higher-rank-trait-bounds/issue-88586-hr-self-outlives-in-trait-def.rs b/src/test/ui/higher-rank-trait-bounds/issue-88586-hr-self-outlives-in-trait-def.rs index b50f56b03d9..92b7c5deb81 100644 --- a/src/test/ui/higher-rank-trait-bounds/issue-88586-hr-self-outlives-in-trait-def.rs +++ b/src/test/ui/higher-rank-trait-bounds/issue-88586-hr-self-outlives-in-trait-def.rs @@ -1,10 +1,12 @@ // Regression test for #88586: a higher-ranked outlives bound on Self in a trait // definition caused an ICE when debug_assertions were enabled. // -// FIXME: The error output in the absence of the ICE is unhelpful; this should be improved. +// Made to pass as part of fixing #98095. +// +// check-pass -trait A where for<'a> Self: 'a -//~^ ERROR the parameter type `Self` may not live long enough +trait A where + for<'a> Self: 'a, { } diff --git a/src/test/ui/higher-rank-trait-bounds/issue-88586-hr-self-outlives-in-trait-def.stderr b/src/test/ui/higher-rank-trait-bounds/issue-88586-hr-self-outlives-in-trait-def.stderr deleted file mode 100644 index 18618ffcc86..00000000000 --- a/src/test/ui/higher-rank-trait-bounds/issue-88586-hr-self-outlives-in-trait-def.stderr +++ /dev/null @@ -1,19 +0,0 @@ -error[E0311]: the parameter type `Self` may not live long enough - --> $DIR/issue-88586-hr-self-outlives-in-trait-def.rs:6:1 - | -LL | / trait A where for<'a> Self: 'a -LL | | -LL | | { -LL | | } - | |_^ - | - = help: consider adding an explicit lifetime bound `Self: 'a`... - = note: ...so that the type `Self` will meet its required lifetime bounds... -note: ...that is required by this bound - --> $DIR/issue-88586-hr-self-outlives-in-trait-def.rs:6:29 - | -LL | trait A where for<'a> Self: 'a - | ^^ - -error: aborting due to previous error - -- 2.44.0