compiler/rustc_typeck/src/outlives/utils.rs

   1 use rustc_middle::ty::outlives::Component;
   2 use rustc_middle::ty::subst::{GenericArg, GenericArgKind};
   3 use rustc_middle::ty::{self, Region, RegionKind, Ty, TyCtxt};
   4 use rustc_span::Span;
   5 use smallvec::smallvec;
   6 use std::collections::BTreeMap;
   7
   8 /// Tracks the `T: 'a` or `'a: 'a` predicates that we have inferred
   9 /// must be added to the struct header.
  10 pub type RequiredPredicates<'tcx> =
  11     BTreeMap<ty::OutlivesPredicate<GenericArg<'tcx>, ty::Region<'tcx>>, Span>;
  12
  13 /// Given a requirement `T: 'a` or `'b: 'a`, deduce the
  14 /// outlives_component and add it to `required_predicates`
  15 pub fn insert_outlives_predicate<'tcx>(
  16     tcx: TyCtxt<'tcx>,
  17     kind: GenericArg<'tcx>,
  18     outlived_region: Region<'tcx>,
  19     span: Span,
  20     required_predicates: &mut RequiredPredicates<'tcx>,
  21 ) {
  22     // If the `'a` region is bound within the field type itself, we
  23     // don't want to propagate this constraint to the header.
  24     if !is_free_region(tcx, outlived_region) {
  25         return;
  26     }
  27
  28     match kind.unpack() {
  29         GenericArgKind::Type(ty) => {
  30             // `T: 'outlived_region` for some type `T`
  31             // But T could be a lot of things:
  32             // e.g., if `T = &'b u32`, then `'b: 'outlived_region` is
  33             // what we want to add.
  34             //
  35             // Or if within `struct Foo<U>` you had `T = Vec<U>`, then
  36             // we would want to add `U: 'outlived_region`
  37             let mut components = smallvec![];
  38             tcx.push_outlives_components(ty, &mut components);
  39             for component in components {
  40                 match component {
  41                     Component::Region(r) => {
  42                         // This would arise from something like:
  43                         //
  44                         // ```
  45                         // struct Foo<'a, 'b> {
  46                         //    x:  &'a &'b u32
  47                         // }
  48                         // ```
  49                         //
  50                         // Here `outlived_region = 'a` and `kind = &'b
  51                         // u32`.  Decomposing `&'b u32` into
  52                         // components would yield `'b`, and we add the
  53                         // where clause that `'b: 'a`.
  54                         insert_outlives_predicate(
  55                             tcx,
  56                             r.into(),
  57                             outlived_region,
  58                             span,
  59                             required_predicates,
  60                         );
  61                     }
  62
  63                     Component::Param(param_ty) => {
  64                         // param_ty: ty::ParamTy
  65                         // This would arise from something like:
  66                         //
  67                         // ```
  68                         // struct Foo<'a, U> {
  69                         //    x:  &'a Vec<U>
  70                         // }
  71                         // ```
  72                         //
  73                         // Here `outlived_region = 'a` and `kind =
  74                         // Vec<U>`.  Decomposing `Vec<U>` into
  75                         // components would yield `U`, and we add the
  76                         // where clause that `U: 'a`.
  77                         let ty: Ty<'tcx> = param_ty.to_ty(tcx);
  78                         required_predicates
  79                             .entry(ty::OutlivesPredicate(ty.into(), outlived_region))
  80                             .or_insert(span);
  81                     }
  82
  83                     Component::Projection(proj_ty) => {
  84                         // This would arise from something like:
  85                         //
  86                         // ```
  87                         // struct Foo<'a, T: Iterator> {
  88                         //    x:  &'a <T as Iterator>::Item
  89                         // }
  90                         // ```
  91                         //
  92                         // Here we want to add an explicit `where <T as Iterator>::Item: 'a`.
  93                         let ty: Ty<'tcx> = tcx.mk_projection(proj_ty.item_def_id, proj_ty.substs);
  94                         required_predicates
  95                             .entry(ty::OutlivesPredicate(ty.into(), outlived_region))
  96                             .or_insert(span);
  97                     }
  98
  99                     Component::EscapingProjection(_) => {
 100                         // As above, but the projection involves
 101                         // late-bound regions.  Therefore, the WF
 102                         // requirement is not checked in type definition
 103                         // but at fn call site, so ignore it.
 104                         //
 105                         // ```
 106                         // struct Foo<'a, T: Iterator> {
 107                         //    x: for<'b> fn(<&'b T as Iterator>::Item)
 108                         //              //  ^^^^^^^^^^^^^^^^^^^^^^^^^
 109                         // }
 110                         // ```
 111                         //
 112                         // Since `'b` is not in scope on `Foo`, can't
 113                         // do anything here, ignore it.
 114                     }
 115
 116                     Component::UnresolvedInferenceVariable(_) => bug!("not using infcx"),
 117                 }
 118             }
 119         }
 120
 121         GenericArgKind::Lifetime(r) => {
 122             if !is_free_region(tcx, r) {
 123                 return;
 124             }
 125             required_predicates.entry(ty::OutlivesPredicate(kind, outlived_region)).or_insert(span);
 126         }
 127
 128         GenericArgKind::Const(_) => {
 129             // Generic consts don't impose any constraints.
 130         }
 131     }
 132 }
 133
 134 fn is_free_region(tcx: TyCtxt<'_>, region: Region<'_>) -> bool {
 135     // First, screen for regions that might appear in a type header.
 136     match region {
 137         // These correspond to `T: 'a` relationships:
 138         //
 139         //     struct Foo<'a, T> {
 140         //         field: &'a T, // this would generate a ReEarlyBound referencing `'a`
 141         //     }
 142         //
 143         // We care about these, so fall through.
 144         RegionKind::ReEarlyBound(_) => true,
 145
 146         // These correspond to `T: 'static` relationships which can be
 147         // rather surprising. We are therefore putting this behind a
 148         // feature flag:
 149         //
 150         //     struct Foo<'a, T> {
 151         //         field: &'static T, // this would generate a ReStatic
 152         //     }
 153         RegionKind::ReStatic => tcx.sess.features_untracked().infer_static_outlives_requirements,
 154
 155         // Late-bound regions can appear in `fn` types:
 156         //
 157         //     struct Foo<T> {
 158         //         field: for<'b> fn(&'b T) // e.g., 'b here
 159         //     }
 160         //
 161         // The type above might generate a `T: 'b` bound, but we can
 162         // ignore it.  We can't put it on the struct header anyway.
 163         RegionKind::ReLateBound(..) => false,
 164
 165         // This can appear in `where Self: ` bounds (#64855):
 166         //
 167         //     struct Bar<T>(<Self as Foo>::Type) where Self: ;
 168         //     struct Baz<'a>(&'a Self) where Self: ;
 169         RegionKind::ReEmpty(_) => false,
 170
 171         // These regions don't appear in types from type declarations:
 172         RegionKind::ReErased
 173         | RegionKind::ReVar(..)
 174         | RegionKind::RePlaceholder(..)
 175         | RegionKind::ReFree(..) => {
 176             bug!("unexpected region in outlives inference: {:?}", region);
 177         }
 178     }
 179 }