]>
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; | |
16 | use middle::ty::{self, RegionEscape, Ty}; | |
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>>), | |
56 | ||
57 | // This is a temporary marker indicating "outlives components" | |
58 | // that are due to the new rules introduced by RFC 1214. For the | |
59 | // time being, violations of these requirements generally induce | |
60 | // warnings, not errors. | |
61 | RFC1214(Vec<Component<'tcx>>), | |
62 | } | |
63 | ||
64 | /// Returns all the things that must outlive `'a` for the condition | |
65 | /// `ty0: 'a` to hold. | |
66 | pub fn components<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>, | |
67 | ty0: Ty<'tcx>) | |
68 | -> Vec<Component<'tcx>> { | |
69 | let mut components = vec![]; | |
70 | compute_components(infcx, ty0, &mut components); | |
71 | debug!("components({:?}) = {:?}", ty0, components); | |
72 | components | |
73 | } | |
74 | ||
75 | fn compute_components<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>, | |
76 | ty: Ty<'tcx>, | |
77 | out: &mut Vec<Component<'tcx>>) { | |
78 | // Descend through the types, looking for the various "base" | |
79 | // components and collecting them into `out`. This is not written | |
80 | // with `collect()` because of the need to sometimes skip subtrees | |
81 | // in the `subtys` iterator (e.g., when encountering a | |
82 | // projection). | |
83 | match ty.sty { | |
84 | ty::TyClosure(_, ref substs) => { | |
85 | // FIXME(#27086). We do not accumulate from substs, since they | |
86 | // don't represent reachable data. This means that, in | |
87 | // practice, some of the lifetime parameters might not | |
88 | // be in scope when the body runs, so long as there is | |
89 | // no reachable data with that lifetime. For better or | |
90 | // worse, this is consistent with fn types, however, | |
91 | // which can also encapsulate data in this fashion | |
92 | // (though it's somewhat harder, and typically | |
93 | // requires virtual dispatch). | |
94 | // | |
95 | // Note that changing this (in a naive way, at least) | |
96 | // causes regressions for what appears to be perfectly | |
97 | // reasonable code like this: | |
98 | // | |
99 | // ``` | |
100 | // fn foo<'a>(p: &Data<'a>) { | |
101 | // bar(|q: &mut Parser| q.read_addr()) | |
102 | // } | |
103 | // fn bar(p: Box<FnMut(&mut Parser)+'static>) { | |
104 | // } | |
105 | // ``` | |
106 | // | |
107 | // Note that `p` (and `'a`) are not used in the | |
108 | // closure at all, but to meet the requirement that | |
109 | // the closure type `C: 'static` (so it can be coerced | |
110 | // to the object type), we get the requirement that | |
111 | // `'a: 'static` since `'a` appears in the closure | |
112 | // type `C`. | |
113 | // | |
114 | // A smarter fix might "prune" unused `func_substs` -- | |
115 | // this would avoid breaking simple examples like | |
116 | // this, but would still break others (which might | |
117 | // indeed be invalid, depending on your POV). Pruning | |
118 | // would be a subtle process, since we have to see | |
119 | // what func/type parameters are used and unused, | |
120 | // taking into consideration UFCS and so forth. | |
121 | ||
122 | for &upvar_ty in &substs.upvar_tys { | |
123 | compute_components(infcx, upvar_ty, out); | |
124 | } | |
125 | } | |
126 | ||
127 | // Bare functions and traits are both binders. In the RFC, | |
128 | // this means we would add the bound regions to the "bound | |
129 | // regions list". In our representation, no such list is | |
130 | // maintained explicitly, because bound regions themselves can | |
131 | // be readily identified. However, because the outlives | |
132 | // relation did not used to be applied to fn/trait-object | |
133 | // arguments, we wrap the resulting components in an RFC1214 | |
134 | // wrapper so we can issue warnings. | |
135 | ty::TyBareFn(..) | ty::TyTrait(..) => { | |
136 | // OutlivesFunction, OutlivesObject, OutlivesFragment | |
137 | let subcomponents = capture_components(infcx, ty); | |
138 | out.push(Component::RFC1214(subcomponents)); | |
139 | } | |
140 | ||
141 | // OutlivesTypeParameterEnv -- the actual checking that `X:'a` | |
142 | // is implied by the environment is done in regionck. | |
143 | ty::TyParam(p) => { | |
144 | out.push(Component::Param(p)); | |
145 | } | |
146 | ||
147 | // For projections, we prefer to generate an obligation like | |
148 | // `<P0 as Trait<P1...Pn>>::Foo: 'a`, because this gives the | |
149 | // regionck more ways to prove that it holds. However, | |
150 | // regionck is not (at least currently) prepared to deal with | |
151 | // higher-ranked regions that may appear in the | |
152 | // trait-ref. Therefore, if we see any higher-ranke regions, | |
153 | // we simply fallback to the most restrictive rule, which | |
154 | // requires that `Pi: 'a` for all `i`. | |
155 | ty::TyProjection(ref data) => { | |
156 | if !data.has_escaping_regions() { | |
157 | // best case: no escaping regions, so push the | |
158 | // projection and skip the subtree (thus generating no | |
159 | // constraints for Pi). This defers the choice between | |
160 | // the rules OutlivesProjectionEnv, | |
161 | // OutlivesProjectionTraitDef, and | |
162 | // OutlivesProjectionComponents to regionck. | |
163 | out.push(Component::Projection(*data)); | |
164 | } else { | |
165 | // fallback case: hard code | |
166 | // OutlivesProjectionComponents. Continue walking | |
167 | // through and constrain Pi. | |
168 | let subcomponents = capture_components(infcx, ty); | |
169 | out.push(Component::EscapingProjection(subcomponents)); | |
170 | } | |
171 | } | |
172 | ||
173 | // If we encounter an inference variable, try to resolve it | |
174 | // and proceed with resolved version. If we cannot resolve it, | |
175 | // then record the unresolved variable as a component. | |
176 | ty::TyInfer(_) => { | |
177 | let ty = infcx.resolve_type_vars_if_possible(&ty); | |
178 | if let ty::TyInfer(infer_ty) = ty.sty { | |
179 | out.push(Component::UnresolvedInferenceVariable(infer_ty)); | |
180 | } else { | |
181 | compute_components(infcx, ty, out); | |
182 | } | |
183 | } | |
184 | ||
185 | // Most types do not introduce any region binders, nor | |
186 | // involve any other subtle cases, and so the WF relation | |
187 | // simply constraints any regions referenced directly by | |
188 | // the type and then visits the types that are lexically | |
189 | // contained within. (The comments refer to relevant rules | |
190 | // from RFC1214.) | |
92a42be0 SL |
191 | ty::TyBool | // OutlivesScalar |
192 | ty::TyChar | // OutlivesScalar | |
e9174d1e SL |
193 | ty::TyInt(..) | // OutlivesScalar |
194 | ty::TyUint(..) | // OutlivesScalar | |
195 | ty::TyFloat(..) | // OutlivesScalar | |
196 | ty::TyEnum(..) | // OutlivesNominalType | |
197 | ty::TyStruct(..) | // OutlivesNominalType | |
198 | ty::TyBox(..) | // OutlivesNominalType (ish) | |
92a42be0 | 199 | ty::TyStr | // OutlivesScalar (ish) |
e9174d1e SL |
200 | ty::TyArray(..) | // ... |
201 | ty::TySlice(..) | // ... | |
202 | ty::TyRawPtr(..) | // ... | |
203 | ty::TyRef(..) | // OutlivesReference | |
204 | ty::TyTuple(..) | // ... | |
92a42be0 | 205 | ty::TyError => { |
e9174d1e SL |
206 | push_region_constraints(out, ty.regions()); |
207 | for subty in ty.walk_shallow() { | |
208 | compute_components(infcx, subty, out); | |
209 | } | |
210 | } | |
211 | } | |
212 | } | |
213 | ||
214 | fn capture_components<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>, | |
215 | ty: Ty<'tcx>) | |
216 | -> Vec<Component<'tcx>> { | |
217 | let mut temp = vec![]; | |
218 | push_region_constraints(&mut temp, ty.regions()); | |
219 | for subty in ty.walk_shallow() { | |
220 | compute_components(infcx, subty, &mut temp); | |
221 | } | |
222 | temp | |
223 | } | |
224 | ||
225 | fn push_region_constraints<'tcx>(out: &mut Vec<Component<'tcx>>, regions: Vec<ty::Region>) { | |
226 | for r in regions { | |
227 | if !r.is_bound() { | |
228 | out.push(Component::Region(r)); | |
229 | } | |
230 | } | |
231 | } |