src/librustc/ty/outlives.rs

   1 // The outlines relation `T: 'a` or `'a: 'b`. This code frequently
   2 // refers to rules defined in RFC 1214 (`OutlivesFooBar`), so see that
   3 // RFC for reference.
   4
   5 use crate::ty::{self, Ty, TyCtxt, TypeFoldable};
   6 use smallvec::SmallVec;
   7
   8 #[derive(Debug)]
   9 pub enum Component<'tcx> {
  10     Region(ty::Region<'tcx>),
  11     Param(ty::ParamTy),
  12     UnresolvedInferenceVariable(ty::InferTy),
  13
  14     // Projections like `T::Foo` are tricky because a constraint like
  15     // `T::Foo: 'a` can be satisfied in so many ways. There may be a
  16     // where-clause that says `T::Foo: 'a`, or the defining trait may
  17     // include a bound like `type Foo: 'static`, or -- in the most
  18     // conservative way -- we can prove that `T: 'a` (more generally,
  19     // that all components in the projection outlive `'a`). This code
  20     // is not in a position to judge which is the best technique, so
  21     // we just product the projection as a component and leave it to
  22     // the consumer to decide (but see `EscapingProjection` below).
  23     Projection(ty::ProjectionTy<'tcx>),
  24
  25     // In the case where a projection has escaping regions -- meaning
  26     // regions bound within the type itself -- we always use
  27     // the most conservative rule, which requires that all components
  28     // outlive the bound. So for example if we had a type like this:
  29     //
  30     //     for<'a> Trait1<  <T as Trait2<'a,'b>>::Foo  >
  31     //                      ~~~~~~~~~~~~~~~~~~~~~~~~~
  32     //
  33     // then the inner projection (underlined) has an escaping region
  34     // `'a`. We consider that outer trait `'c` to meet a bound if `'b`
  35     // outlives `'b: 'c`, and we don't consider whether the trait
  36     // declares that `Foo: 'static` etc. Therefore, we just return the
  37     // free components of such a projection (in this case, `'b`).
  38     //
  39     // However, in the future, we may want to get smarter, and
  40     // actually return a "higher-ranked projection" here. Therefore,
  41     // we mark that these components are part of an escaping
  42     // projection, so that implied bounds code can avoid relying on
  43     // them. This gives us room to improve the regionck reasoning in
  44     // the future without breaking backwards compat.
  45     EscapingProjection(Vec<Component<'tcx>>),
  46 }
  47
  48 impl<'tcx> TyCtxt<'tcx> {
  49     /// Push onto `out` all the things that must outlive `'a` for the condition
  50     /// `ty0: 'a` to hold. Note that `ty0` must be a **fully resolved type**.
  51     pub fn push_outlives_components(self, ty0: Ty<'tcx>, out: &mut SmallVec<[Component<'tcx>; 4]>) {
  52         compute_components(self, ty0, out);
  53         debug!("components({:?}) = {:?}", ty0, out);
  54     }
  55 }
  56
  57 fn compute_components(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>, out: &mut SmallVec<[Component<'tcx>; 4]>) {
  58     // Descend through the types, looking for the various "base"
  59     // components and collecting them into `out`. This is not written
  60     // with `collect()` because of the need to sometimes skip subtrees
  61     // in the `subtys` iterator (e.g., when encountering a
  62     // projection).
  63     match ty.kind {
  64             ty::Closure(def_id, ref substs) => {
  65                 for upvar_ty in substs.as_closure().upvar_tys(def_id, tcx) {
  66                     compute_components(tcx, upvar_ty, out);
  67                 }
  68             }
  69
  70             ty::Generator(def_id, ref substs, _) => {
  71                 // Same as the closure case
  72                 for upvar_ty in substs.as_generator().upvar_tys(def_id, tcx) {
  73                     compute_components(tcx, upvar_ty, out);
  74                 }
  75
  76                 // We ignore regions in the generator interior as we don't
  77                 // want these to affect region inference
  78             }
  79
  80             // All regions are bound inside a witness
  81             ty::GeneratorWitness(..) => (),
  82
  83             // OutlivesTypeParameterEnv -- the actual checking that `X:'a`
  84             // is implied by the environment is done in regionck.
  85             ty::Param(p) => {
  86                 out.push(Component::Param(p));
  87             }
  88
  89             // For projections, we prefer to generate an obligation like
  90             // `<P0 as Trait<P1...Pn>>::Foo: 'a`, because this gives the
  91             // regionck more ways to prove that it holds. However,
  92             // regionck is not (at least currently) prepared to deal with
  93             // higher-ranked regions that may appear in the
  94             // trait-ref. Therefore, if we see any higher-ranke regions,
  95             // we simply fallback to the most restrictive rule, which
  96             // requires that `Pi: 'a` for all `i`.
  97             ty::Projection(ref data) => {
  98                 if !data.has_escaping_bound_vars() {
  99                     // best case: no escaping regions, so push the
 100                     // projection and skip the subtree (thus generating no
 101                     // constraints for Pi). This defers the choice between
 102                     // the rules OutlivesProjectionEnv,
 103                     // OutlivesProjectionTraitDef, and
 104                     // OutlivesProjectionComponents to regionck.
 105                     out.push(Component::Projection(*data));
 106                 } else {
 107                     // fallback case: hard code
 108                     // OutlivesProjectionComponents.  Continue walking
 109                     // through and constrain Pi.
 110                     let subcomponents = capture_components(tcx, ty);
 111                     out.push(Component::EscapingProjection(subcomponents));
 112                 }
 113             }
 114
 115             ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
 116
 117             // We assume that inference variables are fully resolved.
 118             // So, if we encounter an inference variable, just record
 119             // the unresolved variable as a component.
 120             ty::Infer(infer_ty) => {
 121                 out.push(Component::UnresolvedInferenceVariable(infer_ty));
 122             }
 123
 124             // Most types do not introduce any region binders, nor
 125             // involve any other subtle cases, and so the WF relation
 126             // simply constraints any regions referenced directly by
 127             // the type and then visits the types that are lexically
 128             // contained within. (The comments refer to relevant rules
 129             // from RFC1214.)
 130             ty::Bool |            // OutlivesScalar
 131             ty::Char |            // OutlivesScalar
 132             ty::Int(..) |         // OutlivesScalar
 133             ty::Uint(..) |        // OutlivesScalar
 134             ty::Float(..) |       // OutlivesScalar
 135             ty::Never |           // ...
 136             ty::Adt(..) |         // OutlivesNominalType
 137             ty::Opaque(..) |        // OutlivesNominalType (ish)
 138             ty::Foreign(..) |     // OutlivesNominalType
 139             ty::Str |             // OutlivesScalar (ish)
 140             ty::Array(..) |       // ...
 141             ty::Slice(..) |       // ...
 142             ty::RawPtr(..) |      // ...
 143             ty::Ref(..) |         // OutlivesReference
 144             ty::Tuple(..) |       // ...
 145             ty::FnDef(..) |       // OutlivesFunction (*)
 146             ty::FnPtr(_) |        // OutlivesFunction (*)
 147             ty::Dynamic(..) |       // OutlivesObject, OutlivesFragment (*)
 148             ty::Placeholder(..) |
 149             ty::Bound(..) |
 150             ty::Error => {
 151                 // (*) Bare functions and traits are both binders. In the
 152                 // RFC, this means we would add the bound regions to the
 153                 // "bound regions list".  In our representation, no such
 154                 // list is maintained explicitly, because bound regions
 155                 // themselves can be readily identified.
 156
 157                 push_region_constraints(ty, out);
 158                 for subty in ty.walk_shallow() {
 159                     compute_components(tcx, subty, out);
 160                 }
 161             }
 162         }
 163 }
 164
 165 fn capture_components(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Vec<Component<'tcx>> {
 166     let mut temp = smallvec![];
 167     push_region_constraints(ty, &mut temp);
 168     for subty in ty.walk_shallow() {
 169         compute_components(tcx, subty, &mut temp);
 170     }
 171     temp.into_iter().collect()
 172 }
 173
 174 fn push_region_constraints<'tcx>(ty: Ty<'tcx>, out: &mut SmallVec<[Component<'tcx>; 4]>) {
 175     let mut regions = smallvec![];
 176     ty.push_regions(&mut regions);
 177     out.extend(regions.iter().filter(|&r| !r.is_late_bound()).map(|r| Component::Region(r)));
 178 }