src/librustc_typeck/outlives/utils.rs

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