summaryrefslogtreecommitdiffstats
path: root/compiler/rustc_infer/src/infer/outlives
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-17 12:02:58 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-17 12:02:58 +0000
commit698f8c2f01ea549d77d7dc3338a12e04c11057b9 (patch)
tree173a775858bd501c378080a10dca74132f05bc50 /compiler/rustc_infer/src/infer/outlives
parentInitial commit. (diff)
downloadrustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.tar.xz
rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.zip
Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'compiler/rustc_infer/src/infer/outlives')
-rw-r--r--compiler/rustc_infer/src/infer/outlives/components.rs219
-rw-r--r--compiler/rustc_infer/src/infer/outlives/env.rs131
-rw-r--r--compiler/rustc_infer/src/infer/outlives/mod.rs37
-rw-r--r--compiler/rustc_infer/src/infer/outlives/obligations.rs470
-rw-r--r--compiler/rustc_infer/src/infer/outlives/test_type_match.rs207
-rw-r--r--compiler/rustc_infer/src/infer/outlives/verify.rs373
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, &region_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,
+ )
+ })
+ }
+}