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