diff options
Diffstat (limited to 'compiler/rustc_typeck/src/outlives')
| -rw-r--r-- | compiler/rustc_typeck/src/outlives/explicit.rs | 69 | ||||
| -rw-r--r-- | compiler/rustc_typeck/src/outlives/implicit_infer.rs | 300 | ||||
| -rw-r--r-- | compiler/rustc_typeck/src/outlives/mod.rs | 130 | ||||
| -rw-r--r-- | compiler/rustc_typeck/src/outlives/outlives_bounds.rs | 90 | ||||
| -rw-r--r-- | compiler/rustc_typeck/src/outlives/test.rs | 21 | ||||
| -rw-r--r-- | compiler/rustc_typeck/src/outlives/utils.rs | 175 |
6 files changed, 785 insertions, 0 deletions
diff --git a/compiler/rustc_typeck/src/outlives/explicit.rs b/compiler/rustc_typeck/src/outlives/explicit.rs new file mode 100644 index 000000000..7534482cc --- /dev/null +++ b/compiler/rustc_typeck/src/outlives/explicit.rs @@ -0,0 +1,69 @@ +use rustc_data_structures::fx::FxHashMap; +use rustc_hir::def_id::DefId; +use rustc_middle::ty::{self, OutlivesPredicate, TyCtxt}; + +use super::utils::*; + +#[derive(Debug)] +pub struct ExplicitPredicatesMap<'tcx> { + map: FxHashMap<DefId, ty::EarlyBinder<RequiredPredicates<'tcx>>>, +} + +impl<'tcx> ExplicitPredicatesMap<'tcx> { + pub fn new() -> ExplicitPredicatesMap<'tcx> { + ExplicitPredicatesMap { map: FxHashMap::default() } + } + + pub(crate) fn explicit_predicates_of( + &mut self, + tcx: TyCtxt<'tcx>, + def_id: DefId, + ) -> &ty::EarlyBinder<RequiredPredicates<'tcx>> { + self.map.entry(def_id).or_insert_with(|| { + let predicates = if def_id.is_local() { + tcx.explicit_predicates_of(def_id) + } else { + tcx.predicates_of(def_id) + }; + let mut required_predicates = RequiredPredicates::default(); + + // process predicates and convert to `RequiredPredicates` entry, see below + for &(predicate, span) in predicates.predicates { + match predicate.kind().skip_binder() { + ty::PredicateKind::TypeOutlives(OutlivesPredicate(ty, reg)) => { + insert_outlives_predicate( + tcx, + ty.into(), + reg, + span, + &mut required_predicates, + ) + } + + ty::PredicateKind::RegionOutlives(OutlivesPredicate(reg1, reg2)) => { + insert_outlives_predicate( + tcx, + reg1.into(), + reg2, + span, + &mut required_predicates, + ) + } + + ty::PredicateKind::Trait(..) + | ty::PredicateKind::Projection(..) + | ty::PredicateKind::WellFormed(..) + | ty::PredicateKind::ObjectSafe(..) + | ty::PredicateKind::ClosureKind(..) + | ty::PredicateKind::Subtype(..) + | ty::PredicateKind::Coerce(..) + | ty::PredicateKind::ConstEvaluatable(..) + | ty::PredicateKind::ConstEquate(..) + | ty::PredicateKind::TypeWellFormedFromEnv(..) => (), + } + } + + ty::EarlyBinder(required_predicates) + }) + } +} diff --git a/compiler/rustc_typeck/src/outlives/implicit_infer.rs b/compiler/rustc_typeck/src/outlives/implicit_infer.rs new file mode 100644 index 000000000..3b779280e --- /dev/null +++ b/compiler/rustc_typeck/src/outlives/implicit_infer.rs @@ -0,0 +1,300 @@ +use rustc_data_structures::fx::FxHashMap; +use rustc_hir::def::DefKind; +use rustc_hir::def_id::DefId; +use rustc_middle::ty::subst::{GenericArg, GenericArgKind, Subst}; +use rustc_middle::ty::{self, DefIdTree, Ty, TyCtxt}; +use rustc_span::Span; + +use super::explicit::ExplicitPredicatesMap; +use super::utils::*; + +/// Infer predicates for the items in the crate. +/// +/// `global_inferred_outlives`: this is initially the empty map that +/// was generated by walking the items in the crate. This will +/// now be filled with inferred predicates. +pub(super) fn infer_predicates<'tcx>( + tcx: TyCtxt<'tcx>, +) -> FxHashMap<DefId, ty::EarlyBinder<RequiredPredicates<'tcx>>> { + debug!("infer_predicates"); + + let mut explicit_map = ExplicitPredicatesMap::new(); + + let mut global_inferred_outlives = FxHashMap::default(); + + // If new predicates were added then we need to re-calculate + // all crates since there could be new implied predicates. + 'outer: loop { + let mut predicates_added = false; + + // Visit all the crates and infer predicates + for id in tcx.hir().items() { + let item_did = id.def_id; + + debug!("InferVisitor::visit_item(item={:?})", item_did); + + let mut item_required_predicates = RequiredPredicates::default(); + match tcx.def_kind(item_did) { + DefKind::Union | DefKind::Enum | DefKind::Struct => { + let adt_def = tcx.adt_def(item_did.to_def_id()); + + // Iterate over all fields in item_did + for field_def in adt_def.all_fields() { + // Calculating the predicate requirements necessary + // for item_did. + // + // For field of type &'a T (reference) or Adt + // (struct/enum/union) there will be outlive + // requirements for adt_def. + let field_ty = tcx.type_of(field_def.did); + let field_span = tcx.def_span(field_def.did); + insert_required_predicates_to_be_wf( + tcx, + field_ty, + field_span, + &global_inferred_outlives, + &mut item_required_predicates, + &mut explicit_map, + ); + } + } + + _ => {} + }; + + // If new predicates were added (`local_predicate_map` has more + // predicates than the `global_inferred_outlives`), the new predicates + // might result in implied predicates for their parent types. + // Therefore mark `predicates_added` as true and which will ensure + // we walk the crates again and re-calculate predicates for all + // items. + let item_predicates_len: usize = + global_inferred_outlives.get(&item_did.to_def_id()).map_or(0, |p| p.0.len()); + if item_required_predicates.len() > item_predicates_len { + predicates_added = true; + global_inferred_outlives + .insert(item_did.to_def_id(), ty::EarlyBinder(item_required_predicates)); + } + } + + if !predicates_added { + break 'outer; + } + } + + global_inferred_outlives +} + +fn insert_required_predicates_to_be_wf<'tcx>( + tcx: TyCtxt<'tcx>, + field_ty: Ty<'tcx>, + field_span: Span, + global_inferred_outlives: &FxHashMap<DefId, ty::EarlyBinder<RequiredPredicates<'tcx>>>, + required_predicates: &mut RequiredPredicates<'tcx>, + explicit_map: &mut ExplicitPredicatesMap<'tcx>, +) { + for arg in field_ty.walk() { + let ty = match arg.unpack() { + GenericArgKind::Type(ty) => ty, + + // No predicates from lifetimes or constants, except potentially + // constants' types, but `walk` will get to them as well. + GenericArgKind::Lifetime(_) | GenericArgKind::Const(_) => continue, + }; + + match *ty.kind() { + // The field is of type &'a T which means that we will have + // a predicate requirement of T: 'a (T outlives 'a). + // + // We also want to calculate potential predicates for the T + ty::Ref(region, rty, _) => { + debug!("Ref"); + insert_outlives_predicate(tcx, rty.into(), region, field_span, required_predicates); + } + + // For each Adt (struct/enum/union) type `Foo<'a, T>`, we + // can load the current set of inferred and explicit + // predicates from `global_inferred_outlives` and filter the + // ones that are TypeOutlives. + ty::Adt(def, substs) => { + // First check the inferred predicates + // + // Example 1: + // + // struct Foo<'a, T> { + // field1: Bar<'a, T> + // } + // + // struct Bar<'b, U> { + // field2: &'b U + // } + // + // Here, when processing the type of `field1`, we would + // request the set of implicit predicates computed for `Bar` + // thus far. This will initially come back empty, but in next + // round we will get `U: 'b`. We then apply the substitution + // `['b => 'a, U => T]` and thus get the requirement that `T: + // 'a` holds for `Foo`. + debug!("Adt"); + if let Some(unsubstituted_predicates) = global_inferred_outlives.get(&def.did()) { + for (unsubstituted_predicate, &span) in &unsubstituted_predicates.0 { + // `unsubstituted_predicate` is `U: 'b` in the + // example above. So apply the substitution to + // get `T: 'a` (or `predicate`): + let predicate = unsubstituted_predicates + .rebind(*unsubstituted_predicate) + .subst(tcx, substs); + insert_outlives_predicate( + tcx, + predicate.0, + predicate.1, + span, + required_predicates, + ); + } + } + + // Check if the type has any explicit predicates that need + // to be added to `required_predicates` + // let _: () = substs.region_at(0); + check_explicit_predicates( + tcx, + def.did(), + substs, + required_predicates, + explicit_map, + None, + ); + } + + ty::Dynamic(obj, ..) => { + // This corresponds to `dyn Trait<..>`. In this case, we should + // use the explicit predicates as well. + + debug!("Dynamic"); + debug!("field_ty = {}", &field_ty); + debug!("ty in field = {}", &ty); + if let Some(ex_trait_ref) = obj.principal() { + // Here, we are passing the type `usize` as a + // placeholder value with the function + // `with_self_ty`, since there is no concrete type + // `Self` for a `dyn Trait` at this + // stage. Therefore when checking explicit + // predicates in `check_explicit_predicates` we + // need to ignore checking the explicit_map for + // Self type. + let substs = + ex_trait_ref.with_self_ty(tcx, tcx.types.usize).skip_binder().substs; + check_explicit_predicates( + tcx, + ex_trait_ref.skip_binder().def_id, + substs, + required_predicates, + explicit_map, + Some(tcx.types.self_param), + ); + } + } + + ty::Projection(obj) => { + // This corresponds to `<T as Foo<'a>>::Bar`. In this case, we should use the + // explicit predicates as well. + debug!("Projection"); + check_explicit_predicates( + tcx, + tcx.parent(obj.item_def_id), + obj.substs, + required_predicates, + explicit_map, + None, + ); + } + + _ => {} + } + } +} + +/// We also have to check the explicit predicates +/// declared on the type. +/// ```ignore (illustrative) +/// struct Foo<'a, T> { +/// field1: Bar<T> +/// } +/// +/// struct Bar<U> where U: 'static, U: Foo { +/// ... +/// } +/// ``` +/// Here, we should fetch the explicit predicates, which +/// will give us `U: 'static` and `U: Foo`. The latter we +/// can ignore, but we will want to process `U: 'static`, +/// applying the substitution as above. +fn check_explicit_predicates<'tcx>( + tcx: TyCtxt<'tcx>, + def_id: DefId, + substs: &[GenericArg<'tcx>], + required_predicates: &mut RequiredPredicates<'tcx>, + explicit_map: &mut ExplicitPredicatesMap<'tcx>, + ignored_self_ty: Option<Ty<'tcx>>, +) { + debug!( + "check_explicit_predicates(def_id={:?}, \ + substs={:?}, \ + explicit_map={:?}, \ + required_predicates={:?}, \ + ignored_self_ty={:?})", + def_id, substs, explicit_map, required_predicates, ignored_self_ty, + ); + let explicit_predicates = explicit_map.explicit_predicates_of(tcx, def_id); + + for (outlives_predicate, &span) in &explicit_predicates.0 { + debug!("outlives_predicate = {:?}", &outlives_predicate); + + // Careful: If we are inferring the effects of a `dyn Trait<..>` + // type, then when we look up the predicates for `Trait`, + // we may find some that reference `Self`. e.g., perhaps the + // definition of `Trait` was: + // + // ``` + // trait Trait<'a, T> where Self: 'a { .. } + // ``` + // + // we want to ignore such predicates here, because + // there is no type parameter for them to affect. Consider + // a struct containing `dyn Trait`: + // + // ``` + // struct MyStruct<'x, X> { field: Box<dyn Trait<'x, X>> } + // ``` + // + // The `where Self: 'a` predicate refers to the *existential, hidden type* + // that is represented by the `dyn Trait`, not to the `X` type parameter + // (or any other generic parameter) declared on `MyStruct`. + // + // Note that we do this check for self **before** applying `substs`. In the + // case that `substs` come from a `dyn Trait` type, our caller will have + // included `Self = usize` as the value for `Self`. If we were + // to apply the substs, and not filter this predicate, we might then falsely + // conclude that e.g., `X: 'x` was a reasonable inferred requirement. + // + // Another similar case is where we have an inferred + // requirement like `<Self as Trait>::Foo: 'b`. We presently + // ignore such requirements as well (cc #54467)-- though + // conceivably it might be better if we could extract the `Foo + // = X` binding from the object type (there must be such a + // binding) and thus infer an outlives requirement that `X: + // 'b`. + if let Some(self_ty) = ignored_self_ty + && let GenericArgKind::Type(ty) = outlives_predicate.0.unpack() + && ty.walk().any(|arg| arg == self_ty.into()) + { + debug!("skipping self ty = {:?}", &ty); + continue; + } + + let predicate = explicit_predicates.rebind(*outlives_predicate).subst(tcx, substs); + debug!("predicate = {:?}", &predicate); + insert_outlives_predicate(tcx, predicate.0, predicate.1, span, required_predicates); + } +} diff --git a/compiler/rustc_typeck/src/outlives/mod.rs b/compiler/rustc_typeck/src/outlives/mod.rs new file mode 100644 index 000000000..8fa65d51e --- /dev/null +++ b/compiler/rustc_typeck/src/outlives/mod.rs @@ -0,0 +1,130 @@ +use hir::Node; +use rustc_hir as hir; +use rustc_hir::def_id::DefId; +use rustc_middle::ty::query::Providers; +use rustc_middle::ty::subst::GenericArgKind; +use rustc_middle::ty::{self, CratePredicatesMap, ToPredicate, TyCtxt}; +use rustc_span::symbol::sym; +use rustc_span::Span; + +mod explicit; +mod implicit_infer; +pub(crate) mod outlives_bounds; +/// Code to write unit test for outlives. +pub mod test; +mod utils; + +pub fn provide(providers: &mut Providers) { + *providers = Providers { inferred_outlives_of, inferred_outlives_crate, ..*providers }; +} + +fn inferred_outlives_of(tcx: TyCtxt<'_>, item_def_id: DefId) -> &[(ty::Predicate<'_>, Span)] { + let id = tcx.hir().local_def_id_to_hir_id(item_def_id.expect_local()); + + if matches!(tcx.def_kind(item_def_id), hir::def::DefKind::AnonConst) && tcx.lazy_normalization() + { + if tcx.hir().opt_const_param_default_param_hir_id(id).is_some() { + // In `generics_of` we set the generics' parent to be our parent's parent which means that + // we lose out on the predicates of our actual parent if we dont return those predicates here. + // (See comment in `generics_of` for more information on why the parent shenanigans is necessary) + // + // struct Foo<'a, 'b, const N: usize = { ... }>(&'a &'b ()); + // ^^^ ^^^^^^^ the def id we are calling + // ^^^ inferred_outlives_of on + // parent item we dont have set as the + // parent of generics returned by `generics_of` + // + // In the above code we want the anon const to have predicates in its param env for `'b: 'a` + let item_def_id = tcx.hir().get_parent_item(id); + // In the above code example we would be calling `inferred_outlives_of(Foo)` here + return tcx.inferred_outlives_of(item_def_id); + } + } + + match tcx.hir().get(id) { + Node::Item(item) => match item.kind { + hir::ItemKind::Struct(..) | hir::ItemKind::Enum(..) | hir::ItemKind::Union(..) => { + let crate_map = tcx.inferred_outlives_crate(()); + + let predicates = crate_map.predicates.get(&item_def_id).copied().unwrap_or(&[]); + + if tcx.has_attr(item_def_id, sym::rustc_outlives) { + let mut pred: Vec<String> = predicates + .iter() + .map(|(out_pred, _)| match out_pred.kind().skip_binder() { + ty::PredicateKind::RegionOutlives(p) => p.to_string(), + ty::PredicateKind::TypeOutlives(p) => p.to_string(), + err => bug!("unexpected predicate {:?}", err), + }) + .collect(); + pred.sort(); + + let span = tcx.def_span(item_def_id); + let mut err = tcx.sess.struct_span_err(span, "rustc_outlives"); + for p in &pred { + err.note(p); + } + err.emit(); + } + + debug!("inferred_outlives_of({:?}) = {:?}", item_def_id, predicates); + + predicates + } + + _ => &[], + }, + + _ => &[], + } +} + +fn inferred_outlives_crate(tcx: TyCtxt<'_>, (): ()) -> CratePredicatesMap<'_> { + // Compute a map from each struct/enum/union S to the **explicit** + // outlives predicates (`T: 'a`, `'a: 'b`) that the user wrote. + // Typically there won't be many of these, except in older code where + // they were mandatory. Nonetheless, we have to ensure that every such + // predicate is satisfied, so they form a kind of base set of requirements + // for the type. + + // Compute the inferred predicates + let global_inferred_outlives = implicit_infer::infer_predicates(tcx); + + // Convert the inferred predicates into the "collected" form the + // global data structure expects. + // + // FIXME -- consider correcting impedance mismatch in some way, + // probably by updating the global data structure. + let predicates = global_inferred_outlives + .iter() + .map(|(&def_id, set)| { + let predicates = &*tcx.arena.alloc_from_iter(set.0.iter().filter_map( + |(ty::OutlivesPredicate(kind1, region2), &span)| { + match kind1.unpack() { + GenericArgKind::Type(ty1) => Some(( + ty::Binder::dummy(ty::PredicateKind::TypeOutlives( + ty::OutlivesPredicate(ty1, *region2), + )) + .to_predicate(tcx), + span, + )), + GenericArgKind::Lifetime(region1) => Some(( + ty::Binder::dummy(ty::PredicateKind::RegionOutlives( + ty::OutlivesPredicate(region1, *region2), + )) + .to_predicate(tcx), + span, + )), + GenericArgKind::Const(_) => { + // Generic consts don't impose any constraints. + None + } + } + }, + )); + (def_id, predicates) + }) + .collect(); + + ty::CratePredicatesMap { predicates } +} diff --git a/compiler/rustc_typeck/src/outlives/outlives_bounds.rs b/compiler/rustc_typeck/src/outlives/outlives_bounds.rs new file mode 100644 index 000000000..229a64650 --- /dev/null +++ b/compiler/rustc_typeck/src/outlives/outlives_bounds.rs @@ -0,0 +1,90 @@ +use rustc_hir as hir; +use rustc_middle::ty::{self, Ty}; +use rustc_trait_selection::infer::InferCtxt; +use rustc_trait_selection::traits::query::type_op::{self, TypeOp, TypeOpOutput}; +use rustc_trait_selection::traits::query::NoSolution; +use rustc_trait_selection::traits::{ObligationCause, TraitEngine, TraitEngineExt}; + +pub use rustc_middle::traits::query::OutlivesBound; + +pub trait InferCtxtExt<'tcx> { + fn implied_outlives_bounds( + &self, + param_env: ty::ParamEnv<'tcx>, + body_id: hir::HirId, + ty: Ty<'tcx>, + ) -> Vec<OutlivesBound<'tcx>>; +} + +impl<'cx, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'cx, 'tcx> { + /// Implied bounds are region relationships that we deduce + /// automatically. The idea is that (e.g.) a caller must check that a + /// function's argument types are well-formed immediately before + /// calling that fn, and hence the *callee* can assume that its + /// argument types are well-formed. This may imply certain relationships + /// between generic parameters. For example: + /// ``` + /// fn foo<'a,T>(x: &'a T) {} + /// ``` + /// can only be called with a `'a` and `T` such that `&'a T` is WF. + /// For `&'a T` to be WF, `T: 'a` must hold. So we can assume `T: 'a`. + /// + /// # Parameters + /// + /// - `param_env`, the where-clauses in scope + /// - `body_id`, the body-id to use when normalizing assoc types. + /// Note that this may cause outlives obligations to be injected + /// into the inference context with this body-id. + /// - `ty`, the type that we are supposed to assume is WF. + #[instrument(level = "debug", skip(self, param_env, body_id))] + fn implied_outlives_bounds( + &self, + param_env: ty::ParamEnv<'tcx>, + body_id: hir::HirId, + ty: Ty<'tcx>, + ) -> Vec<OutlivesBound<'tcx>> { + let span = self.tcx.hir().span(body_id); + let result = param_env + .and(type_op::implied_outlives_bounds::ImpliedOutlivesBounds { ty }) + .fully_perform(self); + let result = match result { + Ok(r) => r, + Err(NoSolution) => { + self.tcx.sess.delay_span_bug( + span, + "implied_outlives_bounds failed to solve all obligations", + ); + return vec![]; + } + }; + + let TypeOpOutput { output, constraints, .. } = result; + + if let Some(constraints) = constraints { + // Instantiation may have produced new inference variables and constraints on those + // variables. Process these constraints. + let mut fulfill_cx = <dyn TraitEngine<'tcx>>::new(self.tcx); + let cause = ObligationCause::misc(span, body_id); + for &constraint in &constraints.outlives { + let obligation = self.query_outlives_constraint_to_obligation( + constraint, + cause.clone(), + param_env, + ); + fulfill_cx.register_predicate_obligation(self, obligation); + } + if !constraints.member_constraints.is_empty() { + span_bug!(span, "{:#?}", constraints.member_constraints); + } + let errors = fulfill_cx.select_all_or_error(self); + if !errors.is_empty() { + self.tcx.sess.delay_span_bug( + span, + "implied_outlives_bounds failed to solve obligations from instantiation", + ); + } + }; + + output + } +} diff --git a/compiler/rustc_typeck/src/outlives/test.rs b/compiler/rustc_typeck/src/outlives/test.rs new file mode 100644 index 000000000..eb0e12034 --- /dev/null +++ b/compiler/rustc_typeck/src/outlives/test.rs @@ -0,0 +1,21 @@ +use rustc_errors::struct_span_err; +use rustc_middle::ty::TyCtxt; +use rustc_span::symbol::sym; + +pub fn test_inferred_outlives(tcx: TyCtxt<'_>) { + for id in tcx.hir().items() { + // For unit testing: check for a special "rustc_outlives" + // attribute and report an error with various results if found. + if tcx.has_attr(id.def_id.to_def_id(), sym::rustc_outlives) { + let inferred_outlives_of = tcx.inferred_outlives_of(id.def_id); + struct_span_err!( + tcx.sess, + tcx.def_span(id.def_id), + E0640, + "{:?}", + inferred_outlives_of + ) + .emit(); + } + } +} diff --git a/compiler/rustc_typeck/src/outlives/utils.rs b/compiler/rustc_typeck/src/outlives/utils.rs new file mode 100644 index 000000000..b718ca942 --- /dev/null +++ b/compiler/rustc_typeck/src/outlives/utils.rs @@ -0,0 +1,175 @@ +use rustc_infer::infer::outlives::components::{push_outlives_components, Component}; +use rustc_middle::ty::subst::{GenericArg, GenericArgKind}; +use rustc_middle::ty::{self, Region, Ty, TyCtxt}; +use rustc_span::Span; +use smallvec::smallvec; +use std::collections::BTreeMap; + +/// Tracks the `T: 'a` or `'a: 'a` predicates that we have inferred +/// must be added to the struct header. +pub(crate) type RequiredPredicates<'tcx> = + BTreeMap<ty::OutlivesPredicate<GenericArg<'tcx>, ty::Region<'tcx>>, Span>; + +/// Given a requirement `T: 'a` or `'b: 'a`, deduce the +/// outlives_component and add it to `required_predicates` +pub(crate) fn insert_outlives_predicate<'tcx>( + tcx: TyCtxt<'tcx>, + kind: GenericArg<'tcx>, + outlived_region: Region<'tcx>, + span: Span, + required_predicates: &mut RequiredPredicates<'tcx>, +) { + // If the `'a` region is bound within the field type itself, we + // don't want to propagate this constraint to the header. + if !is_free_region(outlived_region) { + return; + } + + match kind.unpack() { + GenericArgKind::Type(ty) => { + // `T: 'outlived_region` for some type `T` + // But T could be a lot of things: + // e.g., if `T = &'b u32`, then `'b: 'outlived_region` is + // what we want to add. + // + // Or if within `struct Foo<U>` you had `T = Vec<U>`, then + // we would want to add `U: 'outlived_region` + let mut components = smallvec![]; + push_outlives_components(tcx, ty, &mut components); + for component in components { + match component { + Component::Region(r) => { + // This would arise from something like: + // + // ``` + // struct Foo<'a, 'b> { + // x: &'a &'b u32 + // } + // ``` + // + // Here `outlived_region = 'a` and `kind = &'b + // u32`. Decomposing `&'b u32` into + // components would yield `'b`, and we add the + // where clause that `'b: 'a`. + insert_outlives_predicate( + tcx, + r.into(), + outlived_region, + span, + required_predicates, + ); + } + + Component::Param(param_ty) => { + // param_ty: ty::ParamTy + // This would arise from something like: + // + // ``` + // struct Foo<'a, U> { + // x: &'a Vec<U> + // } + // ``` + // + // Here `outlived_region = 'a` and `kind = + // Vec<U>`. Decomposing `Vec<U>` into + // components would yield `U`, and we add the + // where clause that `U: 'a`. + let ty: Ty<'tcx> = param_ty.to_ty(tcx); + required_predicates + .entry(ty::OutlivesPredicate(ty.into(), outlived_region)) + .or_insert(span); + } + + Component::Projection(proj_ty) => { + // This would arise from something like: + // + // ``` + // struct Foo<'a, T: Iterator> { + // x: &'a <T as Iterator>::Item + // } + // ``` + // + // Here we want to add an explicit `where <T as Iterator>::Item: 'a`. + let ty: Ty<'tcx> = tcx.mk_projection(proj_ty.item_def_id, proj_ty.substs); + required_predicates + .entry(ty::OutlivesPredicate(ty.into(), outlived_region)) + .or_insert(span); + } + + Component::EscapingProjection(_) => { + // As above, but the projection involves + // late-bound regions. Therefore, the WF + // requirement is not checked in type definition + // but at fn call site, so ignore it. + // + // ``` + // struct Foo<'a, T: Iterator> { + // x: for<'b> fn(<&'b T as Iterator>::Item) + // // ^^^^^^^^^^^^^^^^^^^^^^^^^ + // } + // ``` + // + // Since `'b` is not in scope on `Foo`, can't + // do anything here, ignore it. + } + + Component::UnresolvedInferenceVariable(_) => bug!("not using infcx"), + } + } + } + + GenericArgKind::Lifetime(r) => { + if !is_free_region(r) { + return; + } + required_predicates.entry(ty::OutlivesPredicate(kind, outlived_region)).or_insert(span); + } + + GenericArgKind::Const(_) => { + // Generic consts don't impose any constraints. + } + } +} + +fn is_free_region(region: Region<'_>) -> bool { + // First, screen for regions that might appear in a type header. + match *region { + // These correspond to `T: 'a` relationships: + // + // struct Foo<'a, T> { + // field: &'a T, // this would generate a ReEarlyBound referencing `'a` + // } + // + // We care about these, so fall through. + ty::ReEarlyBound(_) => true, + + // These correspond to `T: 'static` relationships which can be + // rather surprising. + // + // struct Foo<'a, T> { + // field: &'static T, // this would generate a ReStatic + // } + ty::ReStatic => false, + + // Late-bound regions can appear in `fn` types: + // + // struct Foo<T> { + // field: for<'b> fn(&'b T) // e.g., 'b here + // } + // + // The type above might generate a `T: 'b` bound, but we can + // ignore it. We can't put it on the struct header anyway. + ty::ReLateBound(..) => false, + + // This can appear in `where Self: ` bounds (#64855): + // + // struct Bar<T>(<Self as Foo>::Type) where Self: ; + // struct Baz<'a>(&'a Self) where Self: ; + ty::ReEmpty(_) => false, + + // These regions don't appear in types from type declarations: + ty::ReErased | ty::ReVar(..) | ty::RePlaceholder(..) | ty::ReFree(..) => { + bug!("unexpected region in outlives inference: {:?}", region); + } + } +} |