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