diff options
Diffstat (limited to 'compiler/rustc_infer/src/infer/outlives')
| -rw-r--r-- | compiler/rustc_infer/src/infer/outlives/components.rs | 219 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/outlives/env.rs | 131 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/outlives/mod.rs | 37 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/outlives/obligations.rs | 470 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/outlives/test_type_match.rs | 207 | ||||
| -rw-r--r-- | compiler/rustc_infer/src/infer/outlives/verify.rs | 373 |
6 files changed, 1437 insertions, 0 deletions
diff --git a/compiler/rustc_infer/src/infer/outlives/components.rs b/compiler/rustc_infer/src/infer/outlives/components.rs new file mode 100644 index 000000000..b2d7f4a66 --- /dev/null +++ b/compiler/rustc_infer/src/infer/outlives/components.rs @@ -0,0 +1,219 @@ +// The outlines relation `T: 'a` or `'a: 'b`. This code frequently +// refers to rules defined in RFC 1214 (`OutlivesFooBar`), so see that +// RFC for reference. + +use rustc_data_structures::sso::SsoHashSet; +use rustc_middle::ty::subst::{GenericArg, GenericArgKind}; +use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitable}; +use smallvec::{smallvec, SmallVec}; + +#[derive(Debug)] +pub enum Component<'tcx> { + Region(ty::Region<'tcx>), + Param(ty::ParamTy), + UnresolvedInferenceVariable(ty::InferTy), + + // Projections like `T::Foo` are tricky because a constraint like + // `T::Foo: 'a` can be satisfied in so many ways. There may be a + // where-clause that says `T::Foo: 'a`, or the defining trait may + // include a bound like `type Foo: 'static`, or -- in the most + // conservative way -- we can prove that `T: 'a` (more generally, + // that all components in the projection outlive `'a`). This code + // is not in a position to judge which is the best technique, so + // we just product the projection as a component and leave it to + // the consumer to decide (but see `EscapingProjection` below). + Projection(ty::ProjectionTy<'tcx>), + + // In the case where a projection has escaping regions -- meaning + // regions bound within the type itself -- we always use + // the most conservative rule, which requires that all components + // outlive the bound. So for example if we had a type like this: + // + // for<'a> Trait1< <T as Trait2<'a,'b>>::Foo > + // ~~~~~~~~~~~~~~~~~~~~~~~~~ + // + // then the inner projection (underlined) has an escaping region + // `'a`. We consider that outer trait `'c` to meet a bound if `'b` + // outlives `'b: 'c`, and we don't consider whether the trait + // declares that `Foo: 'static` etc. Therefore, we just return the + // free components of such a projection (in this case, `'b`). + // + // However, in the future, we may want to get smarter, and + // actually return a "higher-ranked projection" here. Therefore, + // we mark that these components are part of an escaping + // projection, so that implied bounds code can avoid relying on + // them. This gives us room to improve the regionck reasoning in + // the future without breaking backwards compat. + EscapingProjection(Vec<Component<'tcx>>), +} + +/// Push onto `out` all the things that must outlive `'a` for the condition +/// `ty0: 'a` to hold. Note that `ty0` must be a **fully resolved type**. +pub fn push_outlives_components<'tcx>( + tcx: TyCtxt<'tcx>, + ty0: Ty<'tcx>, + out: &mut SmallVec<[Component<'tcx>; 4]>, +) { + let mut visited = SsoHashSet::new(); + compute_components(tcx, ty0, out, &mut visited); + debug!("components({:?}) = {:?}", ty0, out); +} + +fn compute_components<'tcx>( + tcx: TyCtxt<'tcx>, + ty: Ty<'tcx>, + out: &mut SmallVec<[Component<'tcx>; 4]>, + visited: &mut SsoHashSet<GenericArg<'tcx>>, +) { + // Descend through the types, looking for the various "base" + // components and collecting them into `out`. This is not written + // with `collect()` because of the need to sometimes skip subtrees + // in the `subtys` iterator (e.g., when encountering a + // projection). + match *ty.kind() { + ty::FnDef(_, substs) => { + // HACK(eddyb) ignore lifetimes found shallowly in `substs`. + // This is inconsistent with `ty::Adt` (including all substs) + // and with `ty::Closure` (ignoring all substs other than + // upvars, of which a `ty::FnDef` doesn't have any), but + // consistent with previous (accidental) behavior. + // See https://github.com/rust-lang/rust/issues/70917 + // for further background and discussion. + for child in substs { + match child.unpack() { + GenericArgKind::Type(ty) => { + compute_components(tcx, ty, out, visited); + } + GenericArgKind::Lifetime(_) => {} + GenericArgKind::Const(_) => { + compute_components_recursive(tcx, child, out, visited); + } + } + } + } + + ty::Array(element, _) => { + // Don't look into the len const as it doesn't affect regions + compute_components(tcx, element, out, visited); + } + + ty::Closure(_, ref substs) => { + let tupled_ty = substs.as_closure().tupled_upvars_ty(); + compute_components(tcx, tupled_ty, out, visited); + } + + ty::Generator(_, ref substs, _) => { + // Same as the closure case + let tupled_ty = substs.as_generator().tupled_upvars_ty(); + compute_components(tcx, tupled_ty, out, visited); + + // We ignore regions in the generator interior as we don't + // want these to affect region inference + } + + // All regions are bound inside a witness + ty::GeneratorWitness(..) => (), + + // OutlivesTypeParameterEnv -- the actual checking that `X:'a` + // is implied by the environment is done in regionck. + ty::Param(p) => { + out.push(Component::Param(p)); + } + + // 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, + // regionck is not (at least currently) prepared to deal with + // higher-ranked regions that may appear in the + // trait-ref. Therefore, if we see any higher-ranked regions, + // we simply fallback to the most restrictive rule, which + // requires that `Pi: 'a` for all `i`. + ty::Projection(ref data) => { + if !data.has_escaping_bound_vars() { + // best case: no escaping regions, so push the + // projection and skip the subtree (thus generating no + // constraints for Pi). This defers the choice between + // the rules OutlivesProjectionEnv, + // OutlivesProjectionTraitDef, and + // OutlivesProjectionComponents to regionck. + out.push(Component::Projection(*data)); + } else { + // fallback case: hard code + // OutlivesProjectionComponents. Continue walking + // through and constrain Pi. + let mut subcomponents = smallvec![]; + let mut subvisited = SsoHashSet::new(); + compute_components_recursive(tcx, ty.into(), &mut subcomponents, &mut subvisited); + out.push(Component::EscapingProjection(subcomponents.into_iter().collect())); + } + } + + // We assume that inference variables are fully resolved. + // So, if we encounter an inference variable, just record + // the unresolved variable as a component. + ty::Infer(infer_ty) => { + out.push(Component::UnresolvedInferenceVariable(infer_ty)); + } + + // Most types do not introduce any region binders, nor + // involve any other subtle cases, and so the WF relation + // simply constraints any regions referenced directly by + // the type and then visits the types that are lexically + // contained within. (The comments refer to relevant rules + // from RFC1214.) + ty::Bool | // OutlivesScalar + ty::Char | // OutlivesScalar + ty::Int(..) | // OutlivesScalar + ty::Uint(..) | // OutlivesScalar + ty::Float(..) | // OutlivesScalar + ty::Never | // ... + ty::Adt(..) | // OutlivesNominalType + ty::Opaque(..) | // OutlivesNominalType (ish) + ty::Foreign(..) | // OutlivesNominalType + ty::Str | // OutlivesScalar (ish) + ty::Slice(..) | // ... + ty::RawPtr(..) | // ... + ty::Ref(..) | // OutlivesReference + ty::Tuple(..) | // ... + ty::FnPtr(_) | // OutlivesFunction (*) + ty::Dynamic(..) | // OutlivesObject, OutlivesFragment (*) + ty::Placeholder(..) | + ty::Bound(..) | + ty::Error(_) => { + // (*) Function pointers and trait objects are both binders. + // In the RFC, this means we would add the bound regions to + // the "bound regions list". In our representation, no such + // list is maintained explicitly, because bound regions + // themselves can be readily identified. + compute_components_recursive(tcx, ty.into(), out, visited); + } + } +} + +/// Collect [Component]s for *all* the substs of `parent`. +/// +/// This should not be used to get the components of `parent` itself. +/// Use [push_outlives_components] instead. +pub(super) fn compute_components_recursive<'tcx>( + tcx: TyCtxt<'tcx>, + parent: GenericArg<'tcx>, + out: &mut SmallVec<[Component<'tcx>; 4]>, + visited: &mut SsoHashSet<GenericArg<'tcx>>, +) { + for child in parent.walk_shallow(visited) { + match child.unpack() { + GenericArgKind::Type(ty) => { + compute_components(tcx, ty, out, visited); + } + GenericArgKind::Lifetime(lt) => { + // Ignore late-bound regions. + if !lt.is_late_bound() { + out.push(Component::Region(lt)); + } + } + GenericArgKind::Const(_) => { + compute_components_recursive(tcx, child, out, visited); + } + } + } +} diff --git a/compiler/rustc_infer/src/infer/outlives/env.rs b/compiler/rustc_infer/src/infer/outlives/env.rs new file mode 100644 index 000000000..b2decd64f --- /dev/null +++ b/compiler/rustc_infer/src/infer/outlives/env.rs @@ -0,0 +1,131 @@ +use crate::infer::free_regions::FreeRegionMap; +use crate::infer::{GenericKind, InferCtxt}; +use crate::traits::query::OutlivesBound; +use rustc_data_structures::fx::FxIndexSet; +use rustc_middle::ty::{self, ReEarlyBound, ReFree, ReVar, Region}; + +use super::explicit_outlives_bounds; + +/// The `OutlivesEnvironment` collects information about what outlives +/// what in a given type-checking setting. For example, if we have a +/// where-clause like `where T: 'a` in scope, then the +/// `OutlivesEnvironment` would record that (in its +/// `region_bound_pairs` field). Similarly, it contains methods for +/// processing and adding implied bounds into the outlives +/// environment. +/// +/// Other code at present does not typically take a +/// `&OutlivesEnvironment`, but rather takes some of its fields (e.g., +/// `process_registered_region_obligations` wants the +/// region-bound-pairs). There is no mistaking it: the current setup +/// of tracking region information is quite scattered! The +/// `OutlivesEnvironment`, for example, needs to sometimes be combined +/// with the `middle::RegionRelations`, to yield a full picture of how +/// (lexical) lifetimes interact. However, I'm reluctant to do more +/// refactoring here, since the setup with NLL is quite different. +/// For example, NLL has no need of `RegionRelations`, and is solely +/// interested in the `OutlivesEnvironment`. -nmatsakis +#[derive(Clone)] +pub struct OutlivesEnvironment<'tcx> { + pub param_env: ty::ParamEnv<'tcx>, + free_region_map: FreeRegionMap<'tcx>, + + // Contains the implied region bounds in scope for our current body. + // + // Example: + // + // ``` + // fn foo<'a, 'b, T>(x: &'a T, y: &'b ()) { + // bar(x, y, |y: &'b T| { .. } // body B1) + // } // body B0 + // ``` + // + // Here, when checking the body B0, the list would be `[T: 'a]`, because we + // infer that `T` must outlive `'a` from the implied bounds on the + // fn declaration. + // + // For the body B1 however, the list would be `[T: 'a, T: 'b]`, because we + // also can see that -- within the closure body! -- `T` must + // outlive `'b`. This is not necessarily true outside the closure + // body, since the closure may never be called. + region_bound_pairs: RegionBoundPairs<'tcx>, +} + +/// "Region-bound pairs" tracks outlives relations that are known to +/// be true, either because of explicit where-clauses like `T: 'a` or +/// because of implied bounds. +pub type RegionBoundPairs<'tcx> = + FxIndexSet<ty::OutlivesPredicate<GenericKind<'tcx>, Region<'tcx>>>; + +impl<'a, 'tcx> OutlivesEnvironment<'tcx> { + pub fn new(param_env: ty::ParamEnv<'tcx>) -> Self { + let mut env = OutlivesEnvironment { + param_env, + free_region_map: Default::default(), + region_bound_pairs: Default::default(), + }; + + env.add_outlives_bounds(None, explicit_outlives_bounds(param_env)); + + env + } + + /// Borrows current value of the `free_region_map`. + pub fn free_region_map(&self) -> &FreeRegionMap<'tcx> { + &self.free_region_map + } + + /// Borrows current `region_bound_pairs`. + pub fn region_bound_pairs(&self) -> &RegionBoundPairs<'tcx> { + &self.region_bound_pairs + } + + /// Processes outlives bounds that are known to hold, whether from implied or other sources. + /// + /// The `infcx` parameter is optional; if the implied bounds may + /// contain inference variables, it must be supplied, in which + /// case we will register "givens" on the inference context. (See + /// `RegionConstraintData`.) + pub fn add_outlives_bounds<I>( + &mut self, + infcx: Option<&InferCtxt<'a, 'tcx>>, + outlives_bounds: I, + ) where + I: IntoIterator<Item = OutlivesBound<'tcx>>, + { + // Record relationships such as `T:'x` that don't go into the + // free-region-map but which we use here. + for outlives_bound in outlives_bounds { + debug!("add_outlives_bounds: outlives_bound={:?}", outlives_bound); + match outlives_bound { + OutlivesBound::RegionSubParam(r_a, param_b) => { + self.region_bound_pairs + .insert(ty::OutlivesPredicate(GenericKind::Param(param_b), r_a)); + } + OutlivesBound::RegionSubProjection(r_a, projection_b) => { + self.region_bound_pairs + .insert(ty::OutlivesPredicate(GenericKind::Projection(projection_b), r_a)); + } + OutlivesBound::RegionSubRegion(r_a, r_b) => { + if let (ReEarlyBound(_) | ReFree(_), ReVar(vid_b)) = (r_a.kind(), r_b.kind()) { + infcx + .expect("no infcx provided but region vars found") + .add_given(r_a, vid_b); + } else { + // In principle, we could record (and take + // advantage of) every relationship here, but + // we are also free not to -- it simply means + // strictly less that we can successfully type + // check. Right now we only look for things + // relationships between free regions. (It may + // also be that we should revise our inference + // system to be more general and to make use + // of *every* relationship that arises here, + // but presently we do not.) + self.free_region_map.relate_regions(r_a, r_b); + } + } + } + } + } +} diff --git a/compiler/rustc_infer/src/infer/outlives/mod.rs b/compiler/rustc_infer/src/infer/outlives/mod.rs new file mode 100644 index 000000000..2a085288f --- /dev/null +++ b/compiler/rustc_infer/src/infer/outlives/mod.rs @@ -0,0 +1,37 @@ +//! Various code related to computing outlives relations. + +pub mod components; +pub mod env; +pub mod obligations; +pub mod test_type_match; +pub mod verify; + +use rustc_middle::traits::query::OutlivesBound; +use rustc_middle::ty; + +#[instrument(level = "debug", skip(param_env))] +pub fn explicit_outlives_bounds<'tcx>( + param_env: ty::ParamEnv<'tcx>, +) -> impl Iterator<Item = OutlivesBound<'tcx>> + 'tcx { + param_env + .caller_bounds() + .into_iter() + .map(ty::Predicate::kind) + .filter_map(ty::Binder::no_bound_vars) + .filter_map(move |kind| match kind { + ty::PredicateKind::Projection(..) + | ty::PredicateKind::Trait(..) + | ty::PredicateKind::Coerce(..) + | ty::PredicateKind::Subtype(..) + | ty::PredicateKind::WellFormed(..) + | ty::PredicateKind::ObjectSafe(..) + | ty::PredicateKind::ClosureKind(..) + | ty::PredicateKind::TypeOutlives(..) + | ty::PredicateKind::ConstEvaluatable(..) + | ty::PredicateKind::ConstEquate(..) + | ty::PredicateKind::TypeWellFormedFromEnv(..) => None, + ty::PredicateKind::RegionOutlives(ty::OutlivesPredicate(r_a, r_b)) => { + Some(OutlivesBound::RegionSubRegion(r_b, r_a)) + } + }) +} diff --git a/compiler/rustc_infer/src/infer/outlives/obligations.rs b/compiler/rustc_infer/src/infer/outlives/obligations.rs new file mode 100644 index 000000000..ad052f58c --- /dev/null +++ b/compiler/rustc_infer/src/infer/outlives/obligations.rs @@ -0,0 +1,470 @@ +//! Code that handles "type-outlives" constraints like `T: 'a`. This +//! is based on the `push_outlives_components` function defined in rustc_infer, +//! but it adds a bit of heuristics on top, in particular to deal with +//! associated types and projections. +//! +//! When we process a given `T: 'a` obligation, we may produce two +//! kinds of constraints for the region inferencer: +//! +//! - Relationships between inference variables and other regions. +//! For example, if we have `&'?0 u32: 'a`, then we would produce +//! a constraint that `'a <= '?0`. +//! - "Verifys" that must be checked after inferencing is done. +//! For example, if we know that, for some type parameter `T`, +//! `T: 'a + 'b`, and we have a requirement that `T: '?1`, +//! then we add a "verify" that checks that `'?1 <= 'a || '?1 <= 'b`. +//! - Note the difference with the previous case: here, the region +//! variable must be less than something else, so this doesn't +//! affect how inference works (it finds the smallest region that +//! will do); it's just a post-condition that we have to check. +//! +//! **The key point is that once this function is done, we have +//! reduced all of our "type-region outlives" obligations into relationships +//! between individual regions.** +//! +//! One key input to this function is the set of "region-bound pairs". +//! These are basically the relationships between type parameters and +//! regions that are in scope at the point where the outlives +//! obligation was incurred. **When type-checking a function, +//! particularly in the face of closures, this is not known until +//! regionck runs!** This is because some of those bounds come +//! from things we have yet to infer. +//! +//! Consider: +//! +//! ``` +//! fn bar<T>(a: T, b: impl for<'a> Fn(&'a T)) {} +//! fn foo<T>(x: T) { +//! bar(x, |y| { /* ... */}) +//! // ^ closure arg +//! } +//! ``` +//! +//! Here, the type of `y` may involve inference variables and the +//! like, and it may also contain implied bounds that are needed to +//! type-check the closure body (e.g., here it informs us that `T` +//! outlives the late-bound region `'a`). +//! +//! Note that by delaying the gathering of implied bounds until all +//! inference information is known, we may find relationships between +//! bound regions and other regions in the environment. For example, +//! when we first check a closure like the one expected as argument +//! to `foo`: +//! +//! ``` +//! fn foo<U, F: for<'a> FnMut(&'a U)>(_f: F) {} +//! ``` +//! +//! the type of the closure's first argument would be `&'a ?U`. We +//! might later infer `?U` to something like `&'b u32`, which would +//! imply that `'b: 'a`. + +use crate::infer::outlives::components::{push_outlives_components, Component}; +use crate::infer::outlives::env::OutlivesEnvironment; +use crate::infer::outlives::env::RegionBoundPairs; +use crate::infer::outlives::verify::VerifyBoundCx; +use crate::infer::{ + self, GenericKind, InferCtxt, RegionObligation, SubregionOrigin, UndoLog, VerifyBound, +}; +use crate::traits::{ObligationCause, ObligationCauseCode}; +use rustc_data_structures::undo_log::UndoLogs; +use rustc_hir::def_id::LocalDefId; +use rustc_middle::ty::subst::GenericArgKind; +use rustc_middle::ty::{self, Region, Ty, TyCtxt, TypeVisitable}; +use smallvec::smallvec; + +impl<'cx, 'tcx> InferCtxt<'cx, '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 + /// available (see `region_obligations` field for more + /// information). + #[instrument(level = "debug", skip(self))] + pub fn register_region_obligation(&self, obligation: RegionObligation<'tcx>) { + let mut inner = self.inner.borrow_mut(); + inner.undo_log.push(UndoLog::PushRegionObligation); + inner.region_obligations.push(obligation); + } + + pub fn register_region_obligation_with_cause( + &self, + sup_type: Ty<'tcx>, + sub_region: Region<'tcx>, + cause: &ObligationCause<'tcx>, + ) { + let origin = SubregionOrigin::from_obligation_cause(cause, || { + infer::RelateParamBound( + cause.span, + sup_type, + match cause.code().peel_derives() { + ObligationCauseCode::BindingObligation(_, span) => Some(*span), + _ => None, + }, + ) + }); + + self.register_region_obligation(RegionObligation { sup_type, sub_region, origin }); + } + + /// Trait queries just want to pass back type obligations "as is" + pub fn take_registered_region_obligations(&self) -> Vec<RegionObligation<'tcx>> { + std::mem::take(&mut self.inner.borrow_mut().region_obligations) + } + + /// NOTE: Prefer using [`InferCtxt::check_region_obligations_and_report_errors`] + /// instead of calling this directly. + /// + /// Process the region obligations that must be proven (during + /// `regionck`) for the given `body_id`, given information about + /// the region bounds in scope and so forth. This function must be + /// invoked for all relevant body-ids before region inference is + /// done (or else an assert will fire). + /// + /// See the `region_obligations` field of `InferCtxt` for some + /// comments about how this function fits into the overall expected + /// flow of the inferencer. The key point is that it is + /// invoked after all type-inference variables have been bound -- + /// towards the end of regionck. This also ensures that the + /// region-bound-pairs are available (see comments above regarding + /// closures). + /// + /// # Parameters + /// + /// - `region_bound_pairs_map`: the set of region bounds implied by + /// the parameters and where-clauses. In particular, each pair + /// `('a, K)` in this list tells us that the bounds in scope + /// indicate that `K: 'a`, where `K` is either a generic + /// parameter like `T` or a projection like `T::Item`. + /// - `param_env` is the parameter environment for the enclosing function. + /// - `body_id` is the body-id whose region obligations are being + /// processed. + #[instrument(level = "debug", skip(self, region_bound_pairs))] + pub fn process_registered_region_obligations( + &self, + region_bound_pairs: &RegionBoundPairs<'tcx>, + param_env: ty::ParamEnv<'tcx>, + ) { + assert!( + !self.in_snapshot.get(), + "cannot process registered region obligations in a snapshot" + ); + + let my_region_obligations = self.take_registered_region_obligations(); + + for RegionObligation { sup_type, sub_region, origin } in my_region_obligations { + debug!( + "process_registered_region_obligations: sup_type={:?} sub_region={:?} origin={:?}", + sup_type, sub_region, origin + ); + + let sup_type = self.resolve_vars_if_possible(sup_type); + + let outlives = + &mut TypeOutlives::new(self, self.tcx, ®ion_bound_pairs, None, param_env); + outlives.type_must_outlive(origin, sup_type, sub_region); + } + } + + /// Processes registered region obliations and resolves regions, reporting + /// any errors if any were raised. Prefer using this function over manually + /// calling `resolve_regions_and_report_errors`. + pub fn check_region_obligations_and_report_errors( + &self, + generic_param_scope: LocalDefId, + outlives_env: &OutlivesEnvironment<'tcx>, + ) { + self.process_registered_region_obligations( + outlives_env.region_bound_pairs(), + outlives_env.param_env, + ); + + self.resolve_regions_and_report_errors(generic_param_scope, outlives_env) + } +} + +/// The `TypeOutlives` struct has the job of "lowering" a `T: 'a` +/// obligation into a series of `'a: 'b` constraints and "verify"s, as +/// described on the module comment. The final constraints are emitted +/// via a "delegate" of type `D` -- this is usually the `infcx`, which +/// accrues them into the `region_obligations` code, but for NLL we +/// use something else. +pub struct TypeOutlives<'cx, 'tcx, D> +where + D: TypeOutlivesDelegate<'tcx>, +{ + // See the comments on `process_registered_region_obligations` for the meaning + // of these fields. + delegate: D, + tcx: TyCtxt<'tcx>, + verify_bound: VerifyBoundCx<'cx, 'tcx>, +} + +pub trait TypeOutlivesDelegate<'tcx> { + fn push_sub_region_constraint( + &mut self, + origin: SubregionOrigin<'tcx>, + a: ty::Region<'tcx>, + b: ty::Region<'tcx>, + ); + + fn push_verify( + &mut self, + origin: SubregionOrigin<'tcx>, + kind: GenericKind<'tcx>, + a: ty::Region<'tcx>, + bound: VerifyBound<'tcx>, + ); +} + +impl<'cx, 'tcx, D> TypeOutlives<'cx, 'tcx, D> +where + D: TypeOutlivesDelegate<'tcx>, +{ + pub fn new( + delegate: D, + tcx: TyCtxt<'tcx>, + region_bound_pairs: &'cx RegionBoundPairs<'tcx>, + implicit_region_bound: Option<ty::Region<'tcx>>, + param_env: ty::ParamEnv<'tcx>, + ) -> Self { + Self { + delegate, + tcx, + verify_bound: VerifyBoundCx::new( + tcx, + region_bound_pairs, + implicit_region_bound, + param_env, + ), + } + } + + /// Adds constraints to inference such that `T: 'a` holds (or + /// reports an error if it cannot). + /// + /// # Parameters + /// + /// - `origin`, the reason we need this constraint + /// - `ty`, the type `T` + /// - `region`, the region `'a` + pub fn type_must_outlive( + &mut self, + origin: infer::SubregionOrigin<'tcx>, + ty: Ty<'tcx>, + region: ty::Region<'tcx>, + ) { + debug!("type_must_outlive(ty={:?}, region={:?}, origin={:?})", ty, region, origin); + + assert!(!ty.has_escaping_bound_vars()); + + let mut components = smallvec![]; + push_outlives_components(self.tcx, ty, &mut components); + self.components_must_outlive(origin, &components, region); + } + + fn components_must_outlive( + &mut self, + origin: infer::SubregionOrigin<'tcx>, + components: &[Component<'tcx>], + region: ty::Region<'tcx>, + ) { + for component in components.iter() { + let origin = origin.clone(); + match component { + Component::Region(region1) => { + self.delegate.push_sub_region_constraint(origin, region, *region1); + } + Component::Param(param_ty) => { + self.param_ty_must_outlive(origin, region, *param_ty); + } + Component::Projection(projection_ty) => { + self.projection_must_outlive(origin, region, *projection_ty); + } + Component::EscapingProjection(subcomponents) => { + self.components_must_outlive(origin, &subcomponents, region); + } + Component::UnresolvedInferenceVariable(v) => { + // ignore this, we presume it will yield an error + // later, since if a type variable is not resolved by + // this point it never will be + self.tcx.sess.delay_span_bug( + origin.span(), + &format!("unresolved inference variable in outlives: {:?}", v), + ); + } + } + } + } + + fn param_ty_must_outlive( + &mut self, + origin: infer::SubregionOrigin<'tcx>, + region: ty::Region<'tcx>, + param_ty: ty::ParamTy, + ) { + debug!( + "param_ty_must_outlive(region={:?}, param_ty={:?}, origin={:?})", + region, param_ty, origin + ); + + let generic = GenericKind::Param(param_ty); + let verify_bound = self.verify_bound.generic_bound(generic); + self.delegate.push_verify(origin, generic, region, verify_bound); + } + + #[tracing::instrument(level = "debug", skip(self))] + fn projection_must_outlive( + &mut self, + origin: infer::SubregionOrigin<'tcx>, + region: ty::Region<'tcx>, + projection_ty: ty::ProjectionTy<'tcx>, + ) { + // 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 + // particular). :) First off, we have to choose between using the + // OutlivesProjectionEnv, OutlivesProjectionTraitDef, and + // OutlivesProjectionComponent rules, any one of which is + // sufficient. If there are no inference variables involved, it's + // not hard to pick the right rule, but if there are, we're in a + // bit of a catch 22: if we picked which rule we were going to + // use, we could add constraints to the region inference graph + // that make it apply, but if we don't add those constraints, the + // rule might not apply (but another rule might). For now, we err + // on the side of adding too few edges into the graph. + + // Compute the bounds we can derive from the trait definition. + // 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(); + + 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); + + // Remove outlives bounds that we get from the environment but + // which are also deducible from the trait. This arises (cc + // #55756) in cases where you have e.g., `<T as Foo<'a>>::Item: + // 'a` in the environment but `trait Foo<'b> { type Item: 'b + // }` in the trait definition. + approx_env_bounds.retain(|bound_outlives| { + // OK to skip binder because we only manipulate and compare against other + // values from the same binder. e.g. if we have (e.g.) `for<'a> <T as Trait<'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 + // OutlivesProjectionComponent. If there are inference variables, + // then, we can break down the outlives into more primitive + // components without adding unnecessary edges. + // + // If there are *no* inference variables, however, we COULD do + // this, but we choose not to, because the error messages are less + // good. For example, a requirement like `T::Item: 'r` would be + // translated to a requirement that `T: 'r`; when this is reported + // to the user, it will thus say "T: 'r must hold so that T::Item: + // 'r holds". But that makes it sound like the only way to fix + // 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"); + + for k in projection_ty.substs { + match k.unpack() { + GenericArgKind::Lifetime(lt) => { + self.delegate.push_sub_region_constraint(origin.clone(), region, lt); + } + GenericArgKind::Type(ty) => { + self.type_must_outlive(origin.clone(), ty, region); + } + GenericArgKind::Const(_) => { + // Const parameters don't impose constraints. + } + } + } + + return; + } + + // If we found a unique bound `'b` from the trait, and we + // found nothing else from the environment, then the best + // action is to require that `'b: 'r`, so do that. + // + // This is best no matter what rule we use: + // + // - OutlivesProjectionEnv: these would translate to the requirement that `'b:'r` + // - OutlivesProjectionTraitDef: these would translate to the requirement that `'b:'r` + // - OutlivesProjectionComponent: this would require `'b:'r` + // in addition to other conditions + if !trait_bounds.is_empty() + && trait_bounds[1..] + .iter() + .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); + debug!("projection_must_outlive: unique declared bound appears in trait ref"); + self.delegate.push_sub_region_constraint(origin, region, unique_bound); + return; + } + + // Fallback to verifying after the fact that there exists a + // declared bound, or that all the components appearing in the + // 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); + debug!("projection_must_outlive: pushing {:?}", verify_bound); + self.delegate.push_verify(origin, generic, region, verify_bound); + } +} + +impl<'cx, 'tcx> TypeOutlivesDelegate<'tcx> for &'cx InferCtxt<'cx, 'tcx> { + fn push_sub_region_constraint( + &mut self, + origin: SubregionOrigin<'tcx>, + a: ty::Region<'tcx>, + b: ty::Region<'tcx>, + ) { + self.sub_regions(origin, a, b) + } + + fn push_verify( + &mut self, + origin: SubregionOrigin<'tcx>, + kind: GenericKind<'tcx>, + a: ty::Region<'tcx>, + bound: VerifyBound<'tcx>, + ) { + self.verify_generic_bound(origin, kind, a, 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 new file mode 100644 index 000000000..772e297b7 --- /dev/null +++ b/compiler/rustc_infer/src/infer/outlives/test_type_match.rs @@ -0,0 +1,207 @@ +use std::collections::hash_map::Entry; + +use rustc_data_structures::fx::FxHashMap; +use rustc_middle::ty::TypeVisitable; +use rustc_middle::ty::{ + self, + error::TypeError, + relate::{self, Relate, RelateResult, TypeRelation}, + Ty, TyCtxt, +}; + +use crate::infer::region_constraints::VerifyIfEq; + +/// Given a "verify-if-eq" type test like: +/// +/// exists<'a...> { +/// verify_if_eq(some_type, bound_region) +/// } +/// +/// and the type `test_ty` that the type test is being tested against, +/// returns: +/// +/// * `None` if `some_type` cannot be made equal to `test_ty`, +/// no matter the values of the variables in `exists`. +/// * `Some(r)` with a suitable bound (typically the value of `bound_region`, modulo +/// any bound existential variables, which will be substituted) for the +/// type under test. +/// +/// NB: This function uses a simplistic, syntactic version of type equality. +/// In other words, it may spuriously return `None` even if the type-under-test +/// is in fact equal to `some_type`. In practice, though, this is used on types +/// that are either projections like `T::Item` or `T` and it works fine, but it +/// could have trouble when complex types with higher-ranked binders and the +/// 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<'tcx>( + tcx: TyCtxt<'tcx>, + param_env: ty::ParamEnv<'tcx>, + verify_if_eq_b: &ty::Binder<'tcx, VerifyIfEq<'tcx>>, + test_ty: Ty<'tcx>, +) -> Option<ty::Region<'tcx>> { + assert!(!verify_if_eq_b.has_escaping_bound_vars()); + let mut m = Match::new(tcx, param_env); + let verify_if_eq = verify_if_eq_b.skip_binder(); + m.relate(verify_if_eq.ty, test_ty).ok()?; + + if let ty::RegionKind::ReLateBound(depth, br) = verify_if_eq.bound.kind() { + assert!(depth == ty::INNERMOST); + match m.map.get(&br) { + Some(&r) => Some(r), + None => { + // If there is no mapping, then this region is unconstrained. + // In that case, we escalate to `'static`. + Some(tcx.lifetimes.re_static) + } + } + } else { + // The region does not contain any bound variables, so we don't need + // to do any substitution. + // + // Example: + // + // for<'a> <T as Foo<'a>>::Item: 'b + // + // In this case, we've now matched and found a value for + // `'a`, but it doesn't affect the bound `'b`. + Some(verify_if_eq.bound) + } +} + +/// 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>, + pattern_depth: ty::DebruijnIndex, + map: FxHashMap<ty::BoundRegion, ty::Region<'tcx>>, +} + +impl<'tcx> Match<'tcx> { + fn new(tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> Match<'tcx> { + Match { tcx, param_env, pattern_depth: ty::INNERMOST, map: FxHashMap::default() } + } +} + +impl<'tcx> Match<'tcx> { + /// Creates the "Error" variant that signals "no match". + fn no_match<T>(&self) -> RelateResult<'tcx, T> { + Err(TypeError::Mismatch) + } + + /// 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, + value: ty::Region<'tcx>, + ) -> RelateResult<'tcx, ty::Region<'tcx>> { + match self.map.entry(br) { + Entry::Occupied(entry) => { + if *entry.get() == value { + Ok(value) + } else { + self.no_match() + } + } + Entry::Vacant(entry) => { + entry.insert(value); + Ok(value) + } + } + } +} + +impl<'tcx> TypeRelation<'tcx> for Match<'tcx> { + fn tag(&self) -> &'static str { + "Match" + } + fn tcx(&self) -> TyCtxt<'tcx> { + self.tcx + } + fn param_env(&self) -> ty::ParamEnv<'tcx> { + self.param_env + } + fn a_is_expected(&self) -> bool { + true + } // irrelevant + + fn relate_with_variance<T: Relate<'tcx>>( + &mut self, + _: ty::Variance, + _: ty::VarianceDiagInfo<'tcx>, + a: T, + b: T, + ) -> RelateResult<'tcx, T> { + self.relate(a, b) + } + + #[instrument(skip(self), level = "debug")] + fn regions( + &mut self, + 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, value) + } else if pattern == value { + Ok(pattern) + } else { + self.no_match() + } + } + + #[instrument(skip(self), level = "debug")] + fn tys(&mut self, pattern: Ty<'tcx>, value: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> { + if pattern == value { Ok(pattern) } else { relate::super_relate_tys(self, pattern, value) } + } + + #[instrument(skip(self), level = "debug")] + fn consts( + &mut self, + pattern: ty::Const<'tcx>, + value: ty::Const<'tcx>, + ) -> RelateResult<'tcx, ty::Const<'tcx>> { + debug!("{}.consts({:?}, {:?})", self.tag(), pattern, value); + if pattern == value { + Ok(pattern) + } else { + relate::super_relate_consts(self, pattern, value) + } + } + + fn binders<T>( + &mut self, + pattern: ty::Binder<'tcx, T>, + value: ty::Binder<'tcx, T>, + ) -> RelateResult<'tcx, ty::Binder<'tcx, T>> + where + T: Relate<'tcx>, + { + self.pattern_depth.shift_in(1); + let result = Ok(pattern.rebind(self.relate(pattern.skip_binder(), value.skip_binder())?)); + self.pattern_depth.shift_out(1); + result + } +} diff --git a/compiler/rustc_infer/src/infer/outlives/verify.rs b/compiler/rustc_infer/src/infer/outlives/verify.rs new file mode 100644 index 000000000..c7d7ef40d --- /dev/null +++ b/compiler/rustc_infer/src/infer/outlives/verify.rs @@ -0,0 +1,373 @@ +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 smallvec::smallvec; + +/// The `TypeOutlives` struct has the job of "lowering" a `T: 'a` +/// obligation into a series of `'a: 'b` constraints and "verifys", as +/// described on the module comment. The final constraints are emitted +/// via a "delegate" of type `D` -- this is usually the `infcx`, which +/// accrues them into the `region_obligations` code, but for NLL we +/// use something else. +pub struct VerifyBoundCx<'cx, 'tcx> { + tcx: TyCtxt<'tcx>, + region_bound_pairs: &'cx RegionBoundPairs<'tcx>, + /// During borrowck, if there are no outlives bounds on a generic + /// parameter `T`, we assume that `T: 'in_fn_body` holds. + /// + /// Outside of borrowck the only way to prove `T: '?0` is by + /// setting `'?0` to `'empty`. + implicit_region_bound: Option<ty::Region<'tcx>>, + param_env: ty::ParamEnv<'tcx>, +} + +impl<'cx, 'tcx> VerifyBoundCx<'cx, 'tcx> { + pub fn new( + tcx: TyCtxt<'tcx>, + region_bound_pairs: &'cx RegionBoundPairs<'tcx>, + implicit_region_bound: Option<ty::Region<'tcx>>, + param_env: ty::ParamEnv<'tcx>, + ) -> Self { + 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) + } + } + } + + 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. 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: + if let Some(r) = self.implicit_region_bound { + param_bounds.push(VerifyBound::OutlivedBy(r)); + } + + 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(param_bounds) + } + } + + /// Given a projection like `T::Item`, searches the environment + /// for where-clauses like `T::Item: 'a`. Returns the set of + /// regions `'a` that it finds. + /// + /// This is an "approximate" check -- it may not find all + /// applicable bounds, and not all the bounds it returns can be + /// relied upon. In particular, this check ignores region + /// identity. So, for example, if we have `<T as + /// Trait<'0>>::Item` where `'0` is a region variable, and the + /// user has `<T as Trait<'a>>::Item: 'b` in the environment, then + /// 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( + &self, + projection_ty: ty::ProjectionTy<'tcx>, + ) -> Vec<ty::Binder<'tcx, ty::OutlivesPredicate<Ty<'tcx>, 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) + } + + /// 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( + &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>, + 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); + + // Search the env for where clauses like `P: 'a`. + let env_bounds = self + .projection_approx_declared_bounds_from_env(projection_ty) + .into_iter() + .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 { + let verify_if_eq_b = binder.map_bound(|ty::OutlivesPredicate(ty, bound)| VerifyIfEq { ty, bound }); + 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)); + + // 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); + self.bound_from_components(&components, visited) + }; + + VerifyBound::AnyBound(env_bounds.chain(trait_bounds).collect()).or(recursive_bound) + } + + fn bound_from_components( + &self, + components: &[Component<'tcx>], + visited: &mut SsoHashSet<GenericArg<'tcx>>, + ) -> VerifyBound<'tcx> { + let mut bounds = components + .iter() + .map(|component| self.bound_from_single_component(component, visited)) + .filter(|bound| { + // Remove bounds that must hold, since they are not interesting. + !bound.must_hold() + }); + + match (bounds.next(), bounds.next()) { + (Some(first), None) => first, + (first, second) => { + VerifyBound::AllBounds(first.into_iter().chain(second).chain(bounds).collect()) + } + } + } + + fn bound_from_single_component( + &self, + component: &Component<'tcx>, + visited: &mut SsoHashSet<GenericArg<'tcx>>, + ) -> VerifyBound<'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::EscapingProjection(ref components) => { + self.bound_from_components(components, visited) + } + Component::UnresolvedInferenceVariable(v) => { + // ignore this, we presume it will yield an error + // later, since if a type variable is not resolved by + // this point it never will be + self.tcx.sess.delay_span_bug( + rustc_span::DUMMY_SP, + &format!("unresolved inference variable in outlives: {:?}", v), + ); + // add a bound that never holds + VerifyBound::AnyBound(vec![]) + } + } + } + + /// Searches the environment for where-clauses like `G: 'a` where + /// `G` is either some type parameter `T` or a projection like + /// `T::Item`. Returns a vector of the `'a` bounds it can find. + /// + /// This is a conservative check -- it may not find all applicable + /// bounds, but all the bounds it returns can be relied upon. + fn declared_generic_bounds_from_env( + &self, + param_ty: ty::ParamTy, + ) -> Vec<ty::Binder<'tcx, ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>>> { + let generic_ty = param_ty.to_ty(self.tcx); + self.declared_generic_bounds_from_env_for_erased_ty(generic_ty) + } + + /// Searches the environment to find all bounds that apply to `erased_ty`. + /// Obviously these must be approximate -- they are in fact both *over* and + /// and *under* approximated: + /// + /// * Over-approximated because we erase regions, so + /// * Under-approximated because we look for syntactic equality and so for complex types + /// like `<T as Foo<fn(&u32, &u32)>>::Item` or whatever we may fail to figure out + /// all the subtleties. + /// + /// In some cases, such as when `erased_ty` represents a `ty::Param`, however, + /// the result is precise. + fn declared_generic_bounds_from_env_for_erased_ty( + &self, + erased_ty: Ty<'tcx>, + ) -> Vec<ty::Binder<'tcx, ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>>> { + let tcx = self.tcx; + + // To start, collect bounds from user environment. Note that + // parameter environments are already elaborated, so we don't + // have to worry about that. + let c_b = self.param_env.caller_bounds(); + let param_bounds = self.collect_outlives_from_predicate_list(erased_ty, c_b.into_iter()); + + // Next, collect regions we scraped from the well-formedness + // constraints in the fn signature. To do that, we walk the list + // of known relations from the fn ctxt. + // + // This is crucial because otherwise code like this fails: + // + // fn foo<'a, A>(x: &'a A) { x.bar() } + // + // The problem is that the type of `x` is `&'a A`. To be + // well-formed, then, A must outlive `'a`, but we don't know that + // this holds from first principles. + let from_region_bound_pairs = + self.region_bound_pairs.iter().filter_map(|&OutlivesPredicate(p, r)| { + debug!( + "declared_generic_bounds_from_env_for_erased_ty: region_bound_pair = {:?}", + (r, p) + ); + 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::Binder::dummy(ty::OutlivesPredicate(p.to_ty(tcx), r))) + }); + + param_bounds + .chain(from_region_bound_pairs) + .inspect(|bound| { + debug!( + "declared_generic_bounds_from_env_for_erased_ty: result predicate = {:?}", + bound + ) + }) + .collect() + } + + /// Given a projection like `<T as Foo<'x>>::Bar`, returns any bounds + /// declared in the trait definition. For example, if the trait were + /// + /// ```rust + /// trait Foo<'a> { + /// type Bar: 'a; + /// } + /// ``` + /// + /// 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 + /// works if the user writes `where <Self as Foo<'a>>::Bar: 'a` on + /// the trait. In fact, it works by searching for just such a + /// where-clause. + /// + /// It will not, however, work for higher-ranked bounds like: + /// + /// ```compile_fail,E0311 + /// trait Foo<'a, 'b> + /// where for<'x> <Self as Foo<'x, 'b>>::Bar: 'x + /// { + /// type Bar; + /// } + /// ``` + /// + /// 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( + &self, + assoc_item_def_id: DefId, + ) -> impl Iterator<Item = ty::Region<'tcx>> { + let tcx = self.tcx; + let bounds = tcx.item_bounds(assoc_item_def_id); + bounds + .into_iter() + .filter_map(|p| p.to_opt_type_outlives()) + .filter_map(|p| p.no_bound_vars()) + .map(|b| b.1) + } + + /// Searches through a predicate list for a predicate `T: 'a`. + /// + /// Careful: does not elaborate predicates, and just uses `==` + /// when comparing `ty` for equality, so `ty` must be something + /// that does not involve inference variables and where you + /// otherwise want a precise match. + fn collect_outlives_from_predicate_list( + &self, + erased_ty: Ty<'tcx>, + predicates: impl Iterator<Item = ty::Predicate<'tcx>>, + ) -> impl Iterator<Item = ty::Binder<'tcx, ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>>> + { + let tcx = self.tcx; + 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, + ) + }) + } +} |