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