diff options
Diffstat (limited to 'compiler/rustc_infer/src/infer/outlives')
| -rw-r--r-- | compiler/rustc_infer/src/infer/outlives/components.rs | 17 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/outlives/env.rs | 12 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/outlives/obligations.rs | 150 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/outlives/verify.rs | 111 |
4 files changed, 167 insertions, 123 deletions
diff --git a/compiler/rustc_infer/src/infer/outlives/components.rs b/compiler/rustc_infer/src/infer/outlives/components.rs index b2d7f4a66..14ee9f051 100644 --- a/compiler/rustc_infer/src/infer/outlives/components.rs +++ b/compiler/rustc_infer/src/infer/outlives/components.rs @@ -3,8 +3,9 @@ // RFC for reference. use rustc_data_structures::sso::SsoHashSet; +use rustc_hir::def_id::DefId; use rustc_middle::ty::subst::{GenericArg, GenericArgKind}; -use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitable}; +use rustc_middle::ty::{self, SubstsRef, Ty, TyCtxt, TypeVisitable}; use smallvec::{smallvec, SmallVec}; #[derive(Debug)] @@ -45,6 +46,8 @@ pub enum Component<'tcx> { // them. This gives us room to improve the regionck reasoning in // the future without breaking backwards compat. EscapingProjection(Vec<Component<'tcx>>), + + Opaque(DefId, SubstsRef<'tcx>), } /// Push onto `out` all the things that must outlive `'a` for the condition @@ -120,6 +123,17 @@ fn compute_components<'tcx>( out.push(Component::Param(p)); } + // Ignore lifetimes found in opaque types. Opaque types can + // have lifetimes in their substs which their hidden type doesn't + // actually use. If we inferred that an opaque type is outlived by + // its parameter lifetimes, then we could prove that any lifetime + // outlives any other lifetime, which is unsound. + // See https://github.com/rust-lang/rust/issues/84305 for + // more details. + ty::Opaque(def_id, substs) => { + out.push(Component::Opaque(def_id, substs)); + }, + // For projections, we prefer to generate an obligation like // `<P0 as Trait<P1...Pn>>::Foo: 'a`, because this gives the // regionck more ways to prove that it holds. However, @@ -168,7 +182,6 @@ fn compute_components<'tcx>( ty::Float(..) | // OutlivesScalar ty::Never | // ... ty::Adt(..) | // OutlivesNominalType - ty::Opaque(..) | // OutlivesNominalType (ish) ty::Foreign(..) | // OutlivesNominalType ty::Str | // OutlivesScalar (ish) ty::Slice(..) | // ... diff --git a/compiler/rustc_infer/src/infer/outlives/env.rs b/compiler/rustc_infer/src/infer/outlives/env.rs index 9922b156e..33543135d 100644 --- a/compiler/rustc_infer/src/infer/outlives/env.rs +++ b/compiler/rustc_infer/src/infer/outlives/env.rs @@ -87,9 +87,9 @@ impl<'tcx> OutlivesEnvironment<'tcx> { } /// Create a new `OutlivesEnvironment` with extra outlives bounds. - pub fn with_bounds<'a>( + pub fn with_bounds( param_env: ty::ParamEnv<'tcx>, - infcx: Option<&InferCtxt<'a, 'tcx>>, + infcx: Option<&InferCtxt<'tcx>>, extra_bounds: impl IntoIterator<Item = OutlivesBound<'tcx>>, ) -> Self { let mut builder = Self::builder(param_env); @@ -108,7 +108,7 @@ impl<'tcx> OutlivesEnvironment<'tcx> { } } -impl<'a, 'tcx> OutlivesEnvironmentBuilder<'tcx> { +impl<'tcx> OutlivesEnvironmentBuilder<'tcx> { #[inline] #[instrument(level = "debug")] fn build(self) -> OutlivesEnvironment<'tcx> { @@ -125,7 +125,7 @@ impl<'a, 'tcx> OutlivesEnvironmentBuilder<'tcx> { /// contain inference variables, it must be supplied, in which /// case we will register "givens" on the inference context. (See /// `RegionConstraintData`.) - fn add_outlives_bounds<I>(&mut self, infcx: Option<&InferCtxt<'a, 'tcx>>, outlives_bounds: I) + fn add_outlives_bounds<I>(&mut self, infcx: Option<&InferCtxt<'tcx>>, outlives_bounds: I) where I: IntoIterator<Item = OutlivesBound<'tcx>>, { @@ -142,6 +142,10 @@ impl<'a, 'tcx> OutlivesEnvironmentBuilder<'tcx> { self.region_bound_pairs .insert(ty::OutlivesPredicate(GenericKind::Projection(projection_b), r_a)); } + OutlivesBound::RegionSubOpaque(r_a, def_id, substs) => { + self.region_bound_pairs + .insert(ty::OutlivesPredicate(GenericKind::Opaque(def_id, substs), r_a)); + } OutlivesBound::RegionSubRegion(r_a, r_b) => { if let (ReEarlyBound(_) | ReFree(_), ReVar(vid_b)) = (r_a.kind(), r_b.kind()) { infcx diff --git a/compiler/rustc_infer/src/infer/outlives/obligations.rs b/compiler/rustc_infer/src/infer/outlives/obligations.rs index 5bd1774f6..6ca884799 100644 --- a/compiler/rustc_infer/src/infer/outlives/obligations.rs +++ b/compiler/rustc_infer/src/infer/outlives/obligations.rs @@ -68,13 +68,14 @@ use crate::infer::{ }; use crate::traits::{ObligationCause, ObligationCauseCode}; use rustc_data_structures::undo_log::UndoLogs; +use rustc_hir::def_id::DefId; use rustc_hir::def_id::LocalDefId; use rustc_middle::mir::ConstraintCategory; use rustc_middle::ty::subst::GenericArgKind; -use rustc_middle::ty::{self, Region, Ty, TyCtxt, TypeVisitable}; +use rustc_middle::ty::{self, Region, SubstsRef, Ty, TyCtxt, TypeVisitable}; use smallvec::smallvec; -impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> { +impl<'tcx> InferCtxt<'tcx> { /// Registers that the given region obligation must be resolved /// from within the scope of `body_id`. These regions are enqueued /// and later processed by regionck, when full type information is @@ -182,7 +183,7 @@ impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> { outlives_env.param_env, ); - self.resolve_regions_and_report_errors(generic_param_scope, outlives_env) + self.err_ctxt().resolve_regions_and_report_errors(generic_param_scope, outlives_env) } } @@ -283,6 +284,9 @@ where Component::Param(param_ty) => { self.param_ty_must_outlive(origin, region, *param_ty); } + Component::Opaque(def_id, substs) => { + self.opaque_must_outlive(*def_id, substs, origin, region) + } Component::Projection(projection_ty) => { self.projection_must_outlive(origin, region, *projection_ty); } @@ -314,17 +318,69 @@ where ); let generic = GenericKind::Param(param_ty); - let verify_bound = self.verify_bound.generic_bound(generic); + let verify_bound = self.verify_bound.param_bound(param_ty); self.delegate.push_verify(origin, generic, region, verify_bound); } #[instrument(level = "debug", skip(self))] + fn opaque_must_outlive( + &mut self, + def_id: DefId, + substs: SubstsRef<'tcx>, + origin: infer::SubregionOrigin<'tcx>, + region: ty::Region<'tcx>, + ) { + self.generic_must_outlive( + origin, + region, + GenericKind::Opaque(def_id, substs), + def_id, + substs, + true, + |ty| match *ty.kind() { + ty::Opaque(def_id, substs) => (def_id, substs), + _ => bug!("expected only projection types from env, not {:?}", ty), + }, + ); + } + + #[instrument(level = "debug", skip(self))] fn projection_must_outlive( &mut self, origin: infer::SubregionOrigin<'tcx>, region: ty::Region<'tcx>, projection_ty: ty::ProjectionTy<'tcx>, ) { + self.generic_must_outlive( + origin, + region, + GenericKind::Projection(projection_ty), + projection_ty.item_def_id, + projection_ty.substs, + false, + |ty| match ty.kind() { + ty::Projection(projection_ty) => (projection_ty.item_def_id, projection_ty.substs), + _ => bug!("expected only projection types from env, not {:?}", ty), + }, + ); + } + + #[instrument(level = "debug", skip(self, filter))] + fn generic_must_outlive( + &mut self, + origin: infer::SubregionOrigin<'tcx>, + region: ty::Region<'tcx>, + generic: GenericKind<'tcx>, + def_id: DefId, + substs: SubstsRef<'tcx>, + is_opaque: bool, + filter: impl Fn(Ty<'tcx>) -> (DefId, SubstsRef<'tcx>), + ) { + // An optimization for a common case with opaque types. + if substs.is_empty() { + return; + } + // This case is thorny for inference. The fundamental problem is // that there are many cases where we have choice, and inference // doesn't like choice (the current region inference in @@ -343,16 +399,15 @@ where // These are guaranteed to apply, no matter the inference // results. let trait_bounds: Vec<_> = - self.verify_bound.projection_declared_bounds_from_trait(projection_ty).collect(); + self.verify_bound.declared_region_bounds(def_id, substs).collect(); debug!(?trait_bounds); // Compute the bounds we can derive from the environment. This // is an "approximate" match -- in some cases, these bounds // may not apply. - let mut approx_env_bounds = - self.verify_bound.projection_approx_declared_bounds_from_env(projection_ty); - debug!("projection_must_outlive: approx_env_bounds={:?}", approx_env_bounds); + let mut approx_env_bounds = self.verify_bound.approx_declared_bounds_from_env(generic); + debug!(?approx_env_bounds); // Remove outlives bounds that we get from the environment but // which are also deducible from the trait. This arises (cc @@ -366,14 +421,8 @@ where // 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), - } + let (def_id, substs) = filter(bound.0); + self.verify_bound.declared_region_bounds(def_id, substs).all(|r| r != bound.1) }); // If declared bounds list is empty, the only applicable rule is @@ -390,29 +439,11 @@ where // the problem is to add `T: 'r`, which isn't true. So, if there are no // inference variables, we use a verify constraint instead of adding // edges, which winds up enforcing the same condition. - let needs_infer = projection_ty.needs_infer(); - if approx_env_bounds.is_empty() && trait_bounds.is_empty() && needs_infer { - debug!("projection_must_outlive: no declared bounds"); - - let constraint = origin.to_constraint_category(); - for k in projection_ty.substs { - match k.unpack() { - GenericArgKind::Lifetime(lt) => { - self.delegate.push_sub_region_constraint( - origin.clone(), - region, - lt, - constraint, - ); - } - GenericArgKind::Type(ty) => { - self.type_must_outlive(origin.clone(), ty, region, constraint); - } - GenericArgKind::Const(_) => { - // Const parameters don't impose constraints. - } - } - } + let needs_infer = substs.needs_infer(); + if approx_env_bounds.is_empty() && trait_bounds.is_empty() && (needs_infer || is_opaque) { + debug!("no declared bounds"); + + self.substs_must_outlive(substs, origin, region); return; } @@ -442,8 +473,8 @@ where .all(|b| b == Some(trait_bounds[0])) { let unique_bound = trait_bounds[0]; - debug!("projection_must_outlive: unique trait bound = {:?}", unique_bound); - debug!("projection_must_outlive: unique declared bound appears in trait ref"); + debug!(?unique_bound); + debug!("unique declared bound appears in trait ref"); let category = origin.to_constraint_category(); self.delegate.push_sub_region_constraint(origin, region, unique_bound, category); return; @@ -454,14 +485,45 @@ where // projection outlive; in some cases, this may add insufficient // edges into the inference graph, leading to inference failures // even though a satisfactory solution exists. - let generic = GenericKind::Projection(projection_ty); - let verify_bound = self.verify_bound.generic_bound(generic); + let verify_bound = self.verify_bound.projection_opaque_bounds( + generic, + def_id, + substs, + &mut Default::default(), + ); debug!("projection_must_outlive: pushing {:?}", verify_bound); self.delegate.push_verify(origin, generic, region, verify_bound); } + + fn substs_must_outlive( + &mut self, + substs: SubstsRef<'tcx>, + origin: infer::SubregionOrigin<'tcx>, + region: ty::Region<'tcx>, + ) { + let constraint = origin.to_constraint_category(); + for k in substs { + match k.unpack() { + GenericArgKind::Lifetime(lt) => { + self.delegate.push_sub_region_constraint( + origin.clone(), + region, + lt, + constraint, + ); + } + GenericArgKind::Type(ty) => { + self.type_must_outlive(origin.clone(), ty, region, constraint); + } + GenericArgKind::Const(_) => { + // Const parameters don't impose constraints. + } + } + } + } } -impl<'cx, 'tcx> TypeOutlivesDelegate<'tcx> for &'cx InferCtxt<'cx, 'tcx> { +impl<'cx, 'tcx> TypeOutlivesDelegate<'tcx> for &'cx InferCtxt<'tcx> { fn push_sub_region_constraint( &mut self, origin: SubregionOrigin<'tcx>, diff --git a/compiler/rustc_infer/src/infer/outlives/verify.rs b/compiler/rustc_infer/src/infer/outlives/verify.rs index 752334950..f470b2eb8 100644 --- a/compiler/rustc_infer/src/infer/outlives/verify.rs +++ b/compiler/rustc_infer/src/infer/outlives/verify.rs @@ -2,11 +2,10 @@ use crate::infer::outlives::components::{compute_components_recursive, Component 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; use rustc_hir::def_id::DefId; -use rustc_middle::ty::subst::{GenericArg, Subst}; -use rustc_middle::ty::{self, EarlyBinder, OutlivesPredicate, Ty, TyCtxt}; +use rustc_middle::ty::GenericArg; +use rustc_middle::ty::{self, EarlyBinder, OutlivesPredicate, SubstsRef, Ty, TyCtxt}; use smallvec::smallvec; @@ -38,20 +37,8 @@ impl<'cx, 'tcx> VerifyBoundCx<'cx, 'tcx> { Self { tcx, region_bound_pairs, implicit_region_bound, param_env } } - /// Returns a "verify bound" that encodes what we know about - /// `generic` and the regions it outlives. - pub fn generic_bound(&self, generic: GenericKind<'tcx>) -> VerifyBound<'tcx> { - let mut visited = SsoHashSet::new(); - match generic { - GenericKind::Param(param_ty) => self.param_bound(param_ty), - GenericKind::Projection(projection_ty) => { - self.projection_bound(projection_ty, &mut visited) - } - } - } - #[instrument(level = "debug", skip(self))] - fn param_bound(&self, param_ty: ty::ParamTy) -> VerifyBound<'tcx> { + pub fn param_bound(&self, param_ty: ty::ParamTy) -> VerifyBound<'tcx> { // Start with anything like `T: 'a` we can scrape from the // environment. If the environment contains something like // `for<'a> T: 'a`, then we know that `T` outlives everything. @@ -105,41 +92,31 @@ impl<'cx, 'tcx> VerifyBoundCx<'cx, 'tcx> { /// the clause from the environment only applies if `'0 = 'a`, /// which we don't know yet. But we would still include `'b` in /// this list. - pub fn projection_approx_declared_bounds_from_env( + pub fn approx_declared_bounds_from_env( &self, - projection_ty: ty::ProjectionTy<'tcx>, + generic: GenericKind<'tcx>, ) -> Vec<ty::Binder<'tcx, ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>>> { - let projection_ty = GenericKind::Projection(projection_ty).to_ty(self.tcx); + let projection_ty = generic.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) } - /// Searches the where-clauses in scope for regions that - /// `projection_ty` is known to outlive. Currently requires an - /// exact match. - pub fn projection_declared_bounds_from_trait( + #[instrument(level = "debug", skip(self, visited))] + pub fn projection_opaque_bounds( &self, - projection_ty: ty::ProjectionTy<'tcx>, - ) -> impl Iterator<Item = ty::Region<'tcx>> + 'cx + Captures<'tcx> { - self.declared_projection_bounds_from_trait(projection_ty) - } - - pub fn projection_bound( - &self, - projection_ty: ty::ProjectionTy<'tcx>, + generic: GenericKind<'tcx>, + def_id: DefId, + substs: SubstsRef<'tcx>, visited: &mut SsoHashSet<GenericArg<'tcx>>, ) -> VerifyBound<'tcx> { - debug!("projection_bound(projection_ty={:?})", projection_ty); - - let projection_ty_as_ty = - self.tcx.mk_projection(projection_ty.item_def_id, projection_ty.substs); + let generic_ty = generic.to_ty(self.tcx); // Search the env for where clauses like `P: 'a`. - let env_bounds = self - .projection_approx_declared_bounds_from_env(projection_ty) + let projection_opaque_bounds = self + .approx_declared_bounds_from_env(generic) .into_iter() .map(|binder| { - if let Some(ty::OutlivesPredicate(ty, r)) = binder.no_bound_vars() && ty == projection_ty_as_ty { + if let Some(ty::OutlivesPredicate(ty, r)) = binder.no_bound_vars() && ty == generic_ty { // Micro-optimize if this is an exact match (this // occurs often when there are no region variables // involved). @@ -149,21 +126,19 @@ impl<'cx, 'tcx> VerifyBoundCx<'cx, 'tcx> { VerifyBound::IfEq(verify_if_eq_b) } }); - // Extend with bounds that we can find from the trait. - let trait_bounds = self - .projection_declared_bounds_from_trait(projection_ty) - .map(|r| VerifyBound::OutlivedBy(r)); + let trait_bounds = + self.declared_region_bounds(def_id, substs).map(|r| VerifyBound::OutlivedBy(r)); // see the extensive comment in projection_must_outlive let recursive_bound = { let mut components = smallvec![]; - let ty = self.tcx.mk_projection(projection_ty.item_def_id, projection_ty.substs); - compute_components_recursive(self.tcx, ty.into(), &mut components, visited); + compute_components_recursive(self.tcx, generic_ty.into(), &mut components, visited); self.bound_from_components(&components, visited) }; - VerifyBound::AnyBound(env_bounds.chain(trait_bounds).collect()).or(recursive_bound) + VerifyBound::AnyBound(projection_opaque_bounds.chain(trait_bounds).collect()) + .or(recursive_bound) } fn bound_from_components( @@ -195,7 +170,18 @@ impl<'cx, 'tcx> VerifyBoundCx<'cx, 'tcx> { match *component { Component::Region(lt) => VerifyBound::OutlivedBy(lt), Component::Param(param_ty) => self.param_bound(param_ty), - Component::Projection(projection_ty) => self.projection_bound(projection_ty, visited), + Component::Opaque(did, substs) => self.projection_opaque_bounds( + GenericKind::Opaque(did, substs), + did, + substs, + visited, + ), + Component::Projection(projection_ty) => self.projection_opaque_bounds( + GenericKind::Projection(projection_ty), + projection_ty.item_def_id, + projection_ty.substs, + visited, + ), Component::EscapingProjection(ref components) => { self.bound_from_components(components, visited) } @@ -293,30 +279,6 @@ impl<'cx, 'tcx> VerifyBoundCx<'cx, 'tcx> { /// } /// ``` /// - /// then this function would return `'x`. This is subject to the - /// limitations around higher-ranked bounds described in - /// `region_bounds_declared_on_associated_item`. - fn declared_projection_bounds_from_trait( - &self, - projection_ty: ty::ProjectionTy<'tcx>, - ) -> impl Iterator<Item = ty::Region<'tcx>> + 'cx + Captures<'tcx> { - debug!("projection_bounds(projection_ty={:?})", projection_ty); - let tcx = self.tcx; - self.region_bounds_declared_on_associated_item(projection_ty.item_def_id) - .map(move |r| EarlyBinder(r).subst(tcx, projection_ty.substs)) - } - - /// Given the `DefId` of an associated item, returns any region - /// bounds attached to that associated item from the trait definition. - /// - /// For example: - /// - /// ```rust - /// trait Foo<'a> { - /// type Bar: 'a; - /// } - /// ``` - /// /// If we were given the `DefId` of `Foo::Bar`, we would return /// `'a`. You could then apply the substitutions from the /// projection to convert this into your namespace. This also @@ -336,17 +298,20 @@ impl<'cx, 'tcx> VerifyBoundCx<'cx, 'tcx> { /// /// This is for simplicity, and because we are not really smart /// enough to cope with such bounds anywhere. - fn region_bounds_declared_on_associated_item( + pub fn declared_region_bounds( &self, - assoc_item_def_id: DefId, + def_id: DefId, + substs: SubstsRef<'tcx>, ) -> impl Iterator<Item = ty::Region<'tcx>> { let tcx = self.tcx; - let bounds = tcx.item_bounds(assoc_item_def_id); + let bounds = tcx.item_bounds(def_id); + trace!("{:#?}", bounds); bounds .into_iter() .filter_map(|p| p.to_opt_type_outlives()) .filter_map(|p| p.no_bound_vars()) .map(|b| b.1) + .map(move |r| EarlyBinder(r).subst(tcx, substs)) } /// Searches through a predicate list for a predicate `T: 'a`. |