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.
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.
11 // The outlines relation `T: 'a` or `'a: 'b`. This code frequently
12 // refers to rules defined in RFC 1214 (`OutlivesFooBar`), so see that
15 use ty::{self, Ty, TyCtxt, TypeFoldable};
18 pub enum Component<'tcx> {
19 Region(ty::Region<'tcx>),
21 UnresolvedInferenceVariable(ty::InferTy),
23 // Projections like `T::Foo` are tricky because a constraint like
24 // `T::Foo: 'a` can be satisfied in so many ways. There may be a
25 // where-clause that says `T::Foo: 'a`, or the defining trait may
26 // include a bound like `type Foo: 'static`, or -- in the most
27 // conservative way -- we can prove that `T: 'a` (more generally,
28 // that all components in the projection outlive `'a`). This code
29 // is not in a position to judge which is the best technique, so
30 // we just product the projection as a component and leave it to
31 // the consumer to decide (but see `EscapingProjection` below).
32 Projection(ty::ProjectionTy<'tcx>),
34 // In the case where a projection has escaping regions -- meaning
35 // regions bound within the type itself -- we always use
36 // the most conservative rule, which requires that all components
37 // outlive the bound. So for example if we had a type like this:
39 // for<'a> Trait1< <T as Trait2<'a,'b>>::Foo >
40 // ~~~~~~~~~~~~~~~~~~~~~~~~~
42 // then the inner projection (underlined) has an escaping region
43 // `'a`. We consider that outer trait `'c` to meet a bound if `'b`
44 // outlives `'b: 'c`, and we don't consider whether the trait
45 // declares that `Foo: 'static` etc. Therefore, we just return the
46 // free components of such a projection (in this case, `'b`).
48 // However, in the future, we may want to get smarter, and
49 // actually return a "higher-ranked projection" here. Therefore,
50 // we mark that these components are part of an escaping
51 // projection, so that implied bounds code can avoid relying on
52 // them. This gives us room to improve the regionck reasoning in
53 // the future without breaking backwards compat.
54 EscapingProjection(Vec<Component<'tcx>>),
57 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
58 /// Returns all the things that must outlive `'a` for the condition
59 /// `ty0: 'a` to hold. Note that `ty0` must be a **fully resolved type**.
60 pub fn outlives_components(&self, ty0: Ty<'tcx>)
61 -> Vec<Component<'tcx>> {
62 let mut components = vec![];
63 self.compute_components(ty0, &mut components);
64 debug!("components({:?}) = {:?}", ty0, components);
68 fn compute_components(&self, ty: Ty<'tcx>, out: &mut Vec<Component<'tcx>>) {
69 // Descend through the types, looking for the various "base"
70 // components and collecting them into `out`. This is not written
71 // with `collect()` because of the need to sometimes skip subtrees
72 // in the `subtys` iterator (e.g., when encountering a
75 ty::TyClosure(def_id, ref substs) => {
76 // FIXME(#27086). We do not accumulate from substs, since they
77 // don't represent reachable data. This means that, in
78 // practice, some of the lifetime parameters might not
79 // be in scope when the body runs, so long as there is
80 // no reachable data with that lifetime. For better or
81 // worse, this is consistent with fn types, however,
82 // which can also encapsulate data in this fashion
83 // (though it's somewhat harder, and typically
84 // requires virtual dispatch).
86 // Note that changing this (in a naive way, at least)
87 // causes regressions for what appears to be perfectly
88 // reasonable code like this:
91 // fn foo<'a>(p: &Data<'a>) {
92 // bar(|q: &mut Parser| q.read_addr())
94 // fn bar(p: Box<FnMut(&mut Parser)+'static>) {
98 // Note that `p` (and `'a`) are not used in the
99 // closure at all, but to meet the requirement that
100 // the closure type `C: 'static` (so it can be coerced
101 // to the object type), we get the requirement that
102 // `'a: 'static` since `'a` appears in the closure
105 // A smarter fix might "prune" unused `func_substs` --
106 // this would avoid breaking simple examples like
107 // this, but would still break others (which might
108 // indeed be invalid, depending on your POV). Pruning
109 // would be a subtle process, since we have to see
110 // what func/type parameters are used and unused,
111 // taking into consideration UFCS and so forth.
113 for upvar_ty in substs.upvar_tys(def_id, *self) {
114 self.compute_components(upvar_ty, out);
118 // OutlivesTypeParameterEnv -- the actual checking that `X:'a`
119 // is implied by the environment is done in regionck.
121 out.push(Component::Param(p));
124 // For projections, we prefer to generate an obligation like
125 // `<P0 as Trait<P1...Pn>>::Foo: 'a`, because this gives the
126 // regionck more ways to prove that it holds. However,
127 // regionck is not (at least currently) prepared to deal with
128 // higher-ranked regions that may appear in the
129 // trait-ref. Therefore, if we see any higher-ranke regions,
130 // we simply fallback to the most restrictive rule, which
131 // requires that `Pi: 'a` for all `i`.
132 ty::TyProjection(ref data) => {
133 if !data.has_escaping_regions() {
134 // best case: no escaping regions, so push the
135 // projection and skip the subtree (thus generating no
136 // constraints for Pi). This defers the choice between
137 // the rules OutlivesProjectionEnv,
138 // OutlivesProjectionTraitDef, and
139 // OutlivesProjectionComponents to regionck.
140 out.push(Component::Projection(*data));
142 // fallback case: hard code
143 // OutlivesProjectionComponents. Continue walking
144 // through and constrain Pi.
145 let subcomponents = self.capture_components(ty);
146 out.push(Component::EscapingProjection(subcomponents));
150 // We assume that inference variables are fully resolved.
151 // So, if we encounter an inference variable, just record
152 // the unresolved variable as a component.
153 ty::TyInfer(infer_ty) => {
154 out.push(Component::UnresolvedInferenceVariable(infer_ty));
157 // Most types do not introduce any region binders, nor
158 // involve any other subtle cases, and so the WF relation
159 // simply constraints any regions referenced directly by
160 // the type and then visits the types that are lexically
161 // contained within. (The comments refer to relevant rules
163 ty::TyBool | // OutlivesScalar
164 ty::TyChar | // OutlivesScalar
165 ty::TyInt(..) | // OutlivesScalar
166 ty::TyUint(..) | // OutlivesScalar
167 ty::TyFloat(..) | // OutlivesScalar
169 ty::TyAdt(..) | // OutlivesNominalType
170 ty::TyAnon(..) | // OutlivesNominalType (ish)
171 ty::TyStr | // OutlivesScalar (ish)
172 ty::TyArray(..) | // ...
173 ty::TySlice(..) | // ...
174 ty::TyRawPtr(..) | // ...
175 ty::TyRef(..) | // OutlivesReference
176 ty::TyTuple(..) | // ...
177 ty::TyFnDef(..) | // OutlivesFunction (*)
178 ty::TyFnPtr(_) | // OutlivesFunction (*)
179 ty::TyDynamic(..) | // OutlivesObject, OutlivesFragment (*)
181 // (*) Bare functions and traits are both binders. In the
182 // RFC, this means we would add the bound regions to the
183 // "bound regions list". In our representation, no such
184 // list is maintained explicitly, because bound regions
185 // themselves can be readily identified.
187 push_region_constraints(out, ty.regions());
188 for subty in ty.walk_shallow() {
189 self.compute_components(subty, out);
195 fn capture_components(&self, ty: Ty<'tcx>) -> Vec<Component<'tcx>> {
196 let mut temp = vec![];
197 push_region_constraints(&mut temp, ty.regions());
198 for subty in ty.walk_shallow() {
199 self.compute_components(subty, &mut temp);
205 fn push_region_constraints<'tcx>(out: &mut Vec<Component<'tcx>>, regions: Vec<ty::Region<'tcx>>) {
208 out.push(Component::Region(r));