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