src/librustc/ty/outlives.rs

   1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 // The outlines relation `T: 'a` or `'a: 'b`. This code frequently
  12 // refers to rules defined in RFC 1214 (`OutlivesFooBar`), so see that
  13 // RFC for reference.
  14
  15 use ty::{self, Ty, TyCtxt, TypeFoldable};
  16
  17 #[derive(Debug)]
  18 pub enum Component<'tcx> {
  19     Region(ty::Region<'tcx>),
  20     Param(ty::ParamTy),
  21     UnresolvedInferenceVariable(ty::InferTy),
  22
  23     // Projections like `T::Foo` are tricky because a constraint like
  24     // `T::Foo: 'a` can be satisfied in so many ways. There may be a
  25     // where-clause that says `T::Foo: 'a`, or the defining trait may
  26     // include a bound like `type Foo: 'static`, or -- in the most
  27     // conservative way -- we can prove that `T: 'a` (more generally,
  28     // that all components in the projection outlive `'a`). This code
  29     // is not in a position to judge which is the best technique, so
  30     // we just product the projection as a component and leave it to
  31     // the consumer to decide (but see `EscapingProjection` below).
  32     Projection(ty::ProjectionTy<'tcx>),
  33
  34     // In the case where a projection has escaping regions -- meaning
  35     // regions bound within the type itself -- we always use
  36     // the most conservative rule, which requires that all components
  37     // outlive the bound. So for example if we had a type like this:
  38     //
  39     //     for<'a> Trait1<  <T as Trait2<'a,'b>>::Foo  >
  40     //                      ~~~~~~~~~~~~~~~~~~~~~~~~~
  41     //
  42     // then the inner projection (underlined) has an escaping region
  43     // `'a`. We consider that outer trait `'c` to meet a bound if `'b`
  44     // outlives `'b: 'c`, and we don't consider whether the trait
  45     // declares that `Foo: 'static` etc. Therefore, we just return the
  46     // free components of such a projection (in this case, `'b`).
  47     //
  48     // However, in the future, we may want to get smarter, and
  49     // actually return a "higher-ranked projection" here. Therefore,
  50     // we mark that these components are part of an escaping
  51     // projection, so that implied bounds code can avoid relying on
  52     // them. This gives us room to improve the regionck reasoning in
  53     // the future without breaking backwards compat.
  54     EscapingProjection(Vec<Component<'tcx>>),
  55 }
  56
  57 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
  58     /// Returns all the things that must outlive `'a` for the condition
  59     /// `ty0: 'a` to hold. Note that `ty0` must be a **fully resolved type**.
  60     pub fn outlives_components(&self, ty0: Ty<'tcx>)
  61                                -> Vec<Component<'tcx>> {
  62         let mut components = vec![];
  63         self.compute_components(ty0, &mut components);
  64         debug!("components({:?}) = {:?}", ty0, components);
  65         components
  66     }
  67
  68     fn compute_components(&self, ty: Ty<'tcx>, out: &mut Vec<Component<'tcx>>) {
  69         // Descend through the types, looking for the various "base"
  70         // components and collecting them into `out`. This is not written
  71         // with `collect()` because of the need to sometimes skip subtrees
  72         // in the `subtys` iterator (e.g., when encountering a
  73         // projection).
  74         match ty.sty {
  75             ty::TyClosure(def_id, ref substs) => {
  76                 // FIXME(#27086). We do not accumulate from substs, since they
  77                 // don't represent reachable data. This means that, in
  78                 // practice, some of the lifetime parameters might not
  79                 // be in scope when the body runs, so long as there is
  80                 // no reachable data with that lifetime. For better or
  81                 // worse, this is consistent with fn types, however,
  82                 // which can also encapsulate data in this fashion
  83                 // (though it's somewhat harder, and typically
  84                 // requires virtual dispatch).
  85                 //
  86                 // Note that changing this (in a naive way, at least)
  87                 // causes regressions for what appears to be perfectly
  88                 // reasonable code like this:
  89                 //
  90                 // ```
  91                 // fn foo<'a>(p: &Data<'a>) {
  92                 //    bar(|q: &mut Parser| q.read_addr())
  93                 // }
  94                 // fn bar(p: Box<FnMut(&mut Parser)+'static>) {
  95                 // }
  96                 // ```
  97                 //
  98                 // Note that `p` (and `'a`) are not used in the
  99                 // closure at all, but to meet the requirement that
 100                 // the closure type `C: 'static` (so it can be coerced
 101                 // to the object type), we get the requirement that
 102                 // `'a: 'static` since `'a` appears in the closure
 103                 // type `C`.
 104                 //
 105                 // A smarter fix might "prune" unused `func_substs` --
 106                 // this would avoid breaking simple examples like
 107                 // this, but would still break others (which might
 108                 // indeed be invalid, depending on your POV). Pruning
 109                 // would be a subtle process, since we have to see
 110                 // what func/type parameters are used and unused,
 111                 // taking into consideration UFCS and so forth.
 112
 113                 for upvar_ty in substs.upvar_tys(def_id, *self) {
 114                     self.compute_components(upvar_ty, out);
 115                 }
 116             }
 117
 118             ty::TyGenerator(def_id, ref substs, ref interior) => {
 119                 // Same as the closure case
 120                 for upvar_ty in substs.upvar_tys(def_id, *self) {
 121                     self.compute_components(upvar_ty, out);
 122                 }
 123
 124                 // But generators can have additional interior types
 125                 self.compute_components(interior.witness, out);
 126             }
 127
 128             // OutlivesTypeParameterEnv -- the actual checking that `X:'a`
 129             // is implied by the environment is done in regionck.
 130             ty::TyParam(p) => {
 131                 out.push(Component::Param(p));
 132             }
 133
 134             // For projections, we prefer to generate an obligation like
 135             // `<P0 as Trait<P1...Pn>>::Foo: 'a`, because this gives the
 136             // regionck more ways to prove that it holds. However,
 137             // regionck is not (at least currently) prepared to deal with
 138             // higher-ranked regions that may appear in the
 139             // trait-ref. Therefore, if we see any higher-ranke regions,
 140             // we simply fallback to the most restrictive rule, which
 141             // requires that `Pi: 'a` for all `i`.
 142             ty::TyProjection(ref data) => {
 143                 if !data.has_escaping_regions() {
 144                     // best case: no escaping regions, so push the
 145                     // projection and skip the subtree (thus generating no
 146                     // constraints for Pi). This defers the choice between
 147                     // the rules OutlivesProjectionEnv,
 148                     // OutlivesProjectionTraitDef, and
 149                     // OutlivesProjectionComponents to regionck.
 150                     out.push(Component::Projection(*data));
 151                 } else {
 152                     // fallback case: hard code
 153                     // OutlivesProjectionComponents.  Continue walking
 154                     // through and constrain Pi.
 155                     let subcomponents = self.capture_components(ty);
 156                     out.push(Component::EscapingProjection(subcomponents));
 157                 }
 158             }
 159
 160             // We assume that inference variables are fully resolved.
 161             // So, if we encounter an inference variable, just record
 162             // the unresolved variable as a component.
 163             ty::TyInfer(infer_ty) => {
 164                 out.push(Component::UnresolvedInferenceVariable(infer_ty));
 165             }
 166
 167             // Most types do not introduce any region binders, nor
 168             // involve any other subtle cases, and so the WF relation
 169             // simply constraints any regions referenced directly by
 170             // the type and then visits the types that are lexically
 171             // contained within. (The comments refer to relevant rules
 172             // from RFC1214.)
 173             ty::TyBool |            // OutlivesScalar
 174             ty::TyChar |            // OutlivesScalar
 175             ty::TyInt(..) |         // OutlivesScalar
 176             ty::TyUint(..) |        // OutlivesScalar
 177             ty::TyFloat(..) |       // OutlivesScalar
 178             ty::TyNever |           // ...
 179             ty::TyAdt(..) |         // OutlivesNominalType
 180             ty::TyAnon(..) |        // OutlivesNominalType (ish)
 181             ty::TyStr |             // OutlivesScalar (ish)
 182             ty::TyArray(..) |       // ...
 183             ty::TySlice(..) |       // ...
 184             ty::TyRawPtr(..) |      // ...
 185             ty::TyRef(..) |         // OutlivesReference
 186             ty::TyTuple(..) |       // ...
 187             ty::TyFnDef(..) |       // OutlivesFunction (*)
 188             ty::TyFnPtr(_) |        // OutlivesFunction (*)
 189             ty::TyDynamic(..) |       // OutlivesObject, OutlivesFragment (*)
 190             ty::TyError => {
 191                 // (*) Bare functions and traits are both binders. In the
 192                 // RFC, this means we would add the bound regions to the
 193                 // "bound regions list".  In our representation, no such
 194                 // list is maintained explicitly, because bound regions
 195                 // themselves can be readily identified.
 196
 197                 push_region_constraints(out, ty.regions());
 198                 for subty in ty.walk_shallow() {
 199                     self.compute_components(subty, out);
 200                 }
 201             }
 202         }
 203     }
 204
 205     fn capture_components(&self, ty: Ty<'tcx>) -> Vec<Component<'tcx>> {
 206         let mut temp = vec![];
 207         push_region_constraints(&mut temp, ty.regions());
 208         for subty in ty.walk_shallow() {
 209             self.compute_components(subty, &mut temp);
 210         }
 211         temp
 212     }
 213 }
 214
 215 fn push_region_constraints<'tcx>(out: &mut Vec<Component<'tcx>>, regions: Vec<ty::Region<'tcx>>) {
 216     for r in regions {
 217         if !r.is_late_bound() {
 218             out.push(Component::Region(r));
 219         }
 220     }
 221 }