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::{self, Ty, TyCtxt, TypeFoldable};
6 use smallvec::SmallVec;
9 pub enum Component<'tcx> {
10 Region(ty::Region<'tcx>),
12 UnresolvedInferenceVariable(ty::InferTy),
14 // Projections like `T::Foo` are tricky because a constraint like
15 // `T::Foo: 'a` can be satisfied in so many ways. There may be a
16 // where-clause that says `T::Foo: 'a`, or the defining trait may
17 // include a bound like `type Foo: 'static`, or -- in the most
18 // conservative way -- we can prove that `T: 'a` (more generally,
19 // that all components in the projection outlive `'a`). This code
20 // is not in a position to judge which is the best technique, so
21 // we just product the projection as a component and leave it to
22 // the consumer to decide (but see `EscapingProjection` below).
23 Projection(ty::ProjectionTy<'tcx>),
25 // In the case where a projection has escaping regions -- meaning
26 // regions bound within the type itself -- we always use
27 // the most conservative rule, which requires that all components
28 // outlive the bound. So for example if we had a type like this:
30 // for<'a> Trait1< <T as Trait2<'a,'b>>::Foo >
31 // ~~~~~~~~~~~~~~~~~~~~~~~~~
33 // then the inner projection (underlined) has an escaping region
34 // `'a`. We consider that outer trait `'c` to meet a bound if `'b`
35 // outlives `'b: 'c`, and we don't consider whether the trait
36 // declares that `Foo: 'static` etc. Therefore, we just return the
37 // free components of such a projection (in this case, `'b`).
39 // However, in the future, we may want to get smarter, and
40 // actually return a "higher-ranked projection" here. Therefore,
41 // we mark that these components are part of an escaping
42 // projection, so that implied bounds code can avoid relying on
43 // them. This gives us room to improve the regionck reasoning in
44 // the future without breaking backwards compat.
45 EscapingProjection(Vec<Component<'tcx>>),
48 impl<'tcx> TyCtxt<'tcx> {
49 /// Push onto `out` all the things that must outlive `'a` for the condition
50 /// `ty0: 'a` to hold. Note that `ty0` must be a **fully resolved type**.
51 pub fn push_outlives_components(
54 out: &mut SmallVec<[Component<'tcx>; 4]>,
56 self.compute_components(ty0, out);
57 debug!("components({:?}) = {:?}", ty0, out);
60 fn compute_components(&self, ty: Ty<'tcx>, out: &mut SmallVec<[Component<'tcx>; 4]>) {
61 // Descend through the types, looking for the various "base"
62 // components and collecting them into `out`. This is not written
63 // with `collect()` because of the need to sometimes skip subtrees
64 // in the `subtys` iterator (e.g., when encountering a
67 ty::Closure(def_id, ref substs) => {
68 for upvar_ty in substs.as_closure().upvar_tys(def_id, *self) {
69 self.compute_components(upvar_ty, out);
73 ty::Generator(def_id, ref substs, _) => {
74 // Same as the closure case
75 for upvar_ty in substs.as_generator().upvar_tys(def_id, *self) {
76 self.compute_components(upvar_ty, out);
79 // We ignore regions in the generator interior as we don't
80 // want these to affect region inference
83 // All regions are bound inside a witness
84 ty::GeneratorWitness(..) => (),
86 // OutlivesTypeParameterEnv -- the actual checking that `X:'a`
87 // is implied by the environment is done in regionck.
89 out.push(Component::Param(p));
92 // For projections, we prefer to generate an obligation like
93 // `<P0 as Trait<P1...Pn>>::Foo: 'a`, because this gives the
94 // regionck more ways to prove that it holds. However,
95 // regionck is not (at least currently) prepared to deal with
96 // higher-ranked regions that may appear in the
97 // trait-ref. Therefore, if we see any higher-ranke regions,
98 // we simply fallback to the most restrictive rule, which
99 // requires that `Pi: 'a` for all `i`.
100 ty::Projection(ref data) => {
101 if !data.has_escaping_bound_vars() {
102 // best case: no escaping regions, so push the
103 // projection and skip the subtree (thus generating no
104 // constraints for Pi). This defers the choice between
105 // the rules OutlivesProjectionEnv,
106 // OutlivesProjectionTraitDef, and
107 // OutlivesProjectionComponents to regionck.
108 out.push(Component::Projection(*data));
110 // fallback case: hard code
111 // OutlivesProjectionComponents. Continue walking
112 // through and constrain Pi.
113 let subcomponents = self.capture_components(ty);
114 out.push(Component::EscapingProjection(subcomponents));
118 ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
120 // We assume that inference variables are fully resolved.
121 // So, if we encounter an inference variable, just record
122 // the unresolved variable as a component.
123 ty::Infer(infer_ty) => {
124 out.push(Component::UnresolvedInferenceVariable(infer_ty));
127 // Most types do not introduce any region binders, nor
128 // involve any other subtle cases, and so the WF relation
129 // simply constraints any regions referenced directly by
130 // the type and then visits the types that are lexically
131 // contained within. (The comments refer to relevant rules
133 ty::Bool | // OutlivesScalar
134 ty::Char | // OutlivesScalar
135 ty::Int(..) | // OutlivesScalar
136 ty::Uint(..) | // OutlivesScalar
137 ty::Float(..) | // OutlivesScalar
139 ty::Adt(..) | // OutlivesNominalType
140 ty::Opaque(..) | // OutlivesNominalType (ish)
141 ty::Foreign(..) | // OutlivesNominalType
142 ty::Str | // OutlivesScalar (ish)
143 ty::Array(..) | // ...
144 ty::Slice(..) | // ...
145 ty::RawPtr(..) | // ...
146 ty::Ref(..) | // OutlivesReference
147 ty::Tuple(..) | // ...
148 ty::FnDef(..) | // OutlivesFunction (*)
149 ty::FnPtr(_) | // OutlivesFunction (*)
150 ty::Dynamic(..) | // OutlivesObject, OutlivesFragment (*)
151 ty::Placeholder(..) |
154 // (*) Bare functions and traits are both binders. In the
155 // RFC, this means we would add the bound regions to the
156 // "bound regions list". In our representation, no such
157 // list is maintained explicitly, because bound regions
158 // themselves can be readily identified.
160 push_region_constraints(ty, out);
161 for subty in ty.walk_shallow() {
162 self.compute_components(subty, out);
168 fn capture_components(&self, ty: Ty<'tcx>) -> Vec<Component<'tcx>> {
169 let mut temp = smallvec![];
170 push_region_constraints(ty, &mut temp);
171 for subty in ty.walk_shallow() {
172 self.compute_components(subty, &mut temp);
174 temp.into_iter().collect()
178 fn push_region_constraints<'tcx>(ty: Ty<'tcx>, out: &mut SmallVec<[Component<'tcx>; 4]>) {
179 let mut regions = smallvec![];
180 ty.push_regions(&mut regions);
181 out.extend(regions.iter().filter(|&r| !r.is_late_bound()).map(|r| Component::Region(r)));