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