]>
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 | ||
c30ab7b3 | 15 | use ty::{self, Ty, TyCtxt, TypeFoldable}; |
e9174d1e SL |
16 | |
17 | #[derive(Debug)] | |
18 | pub enum Component<'tcx> { | |
7cac9316 | 19 | Region(ty::Region<'tcx>), |
e9174d1e SL |
20 | Param(ty::ParamTy), |
21 | UnresolvedInferenceVariable(ty::InferTy), | |
22 | ||
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>), | |
33 | ||
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: | |
38 | // | |
39 | // for<'a> Trait1< <T as Trait2<'a,'b>>::Foo > | |
40 | // ~~~~~~~~~~~~~~~~~~~~~~~~~ | |
41 | // | |
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`). | |
47 | // | |
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>>), | |
e9174d1e SL |
55 | } |
56 | ||
c30ab7b3 | 57 | impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> { |
a7813a04 | 58 | /// Returns all the things that must outlive `'a` for the condition |
c30ab7b3 | 59 | /// `ty0: 'a` to hold. Note that `ty0` must be a **fully resolved type**. |
a7813a04 XL |
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); | |
65 | components | |
66 | } | |
e9174d1e | 67 | |
a7813a04 XL |
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 | |
73 | // projection). | |
74 | match ty.sty { | |
476ff2be | 75 | ty::TyClosure(def_id, ref substs) => { |
e9174d1e | 76 | |
476ff2be | 77 | for upvar_ty in substs.upvar_tys(def_id, *self) { |
a7813a04 XL |
78 | self.compute_components(upvar_ty, out); |
79 | } | |
e9174d1e | 80 | } |
e9174d1e | 81 | |
2c00a5a8 | 82 | ty::TyGenerator(def_id, ref substs, _) => { |
ea8adc8c XL |
83 | // Same as the closure case |
84 | for upvar_ty in substs.upvar_tys(def_id, *self) { | |
85 | self.compute_components(upvar_ty, out); | |
86 | } | |
87 | ||
2c00a5a8 XL |
88 | // We ignore regions in the generator interior as we don't |
89 | // want these to affect region inference | |
ea8adc8c XL |
90 | } |
91 | ||
2c00a5a8 XL |
92 | // All regions are bound inside a witness |
93 | ty::TyGeneratorWitness(..) => (), | |
94 | ||
a7813a04 XL |
95 | // OutlivesTypeParameterEnv -- the actual checking that `X:'a` |
96 | // is implied by the environment is done in regionck. | |
97 | ty::TyParam(p) => { | |
98 | out.push(Component::Param(p)); | |
99 | } | |
e9174d1e | 100 | |
a7813a04 XL |
101 | // For projections, we prefer to generate an obligation like |
102 | // `<P0 as Trait<P1...Pn>>::Foo: 'a`, because this gives the | |
103 | // regionck more ways to prove that it holds. However, | |
104 | // regionck is not (at least currently) prepared to deal with | |
105 | // higher-ranked regions that may appear in the | |
106 | // trait-ref. Therefore, if we see any higher-ranke regions, | |
107 | // we simply fallback to the most restrictive rule, which | |
108 | // requires that `Pi: 'a` for all `i`. | |
109 | ty::TyProjection(ref data) => { | |
110 | if !data.has_escaping_regions() { | |
111 | // best case: no escaping regions, so push the | |
112 | // projection and skip the subtree (thus generating no | |
113 | // constraints for Pi). This defers the choice between | |
114 | // the rules OutlivesProjectionEnv, | |
115 | // OutlivesProjectionTraitDef, and | |
116 | // OutlivesProjectionComponents to regionck. | |
117 | out.push(Component::Projection(*data)); | |
118 | } else { | |
119 | // fallback case: hard code | |
120 | // OutlivesProjectionComponents. Continue walking | |
121 | // through and constrain Pi. | |
122 | let subcomponents = self.capture_components(ty); | |
123 | out.push(Component::EscapingProjection(subcomponents)); | |
124 | } | |
e9174d1e | 125 | } |
e9174d1e | 126 | |
c30ab7b3 SL |
127 | // We assume that inference variables are fully resolved. |
128 | // So, if we encounter an inference variable, just record | |
129 | // the unresolved variable as a component. | |
130 | ty::TyInfer(infer_ty) => { | |
131 | out.push(Component::UnresolvedInferenceVariable(infer_ty)); | |
e9174d1e | 132 | } |
e9174d1e | 133 | |
a7813a04 XL |
134 | // Most types do not introduce any region binders, nor |
135 | // involve any other subtle cases, and so the WF relation | |
136 | // simply constraints any regions referenced directly by | |
137 | // the type and then visits the types that are lexically | |
138 | // contained within. (The comments refer to relevant rules | |
139 | // from RFC1214.) | |
140 | ty::TyBool | // OutlivesScalar | |
141 | ty::TyChar | // OutlivesScalar | |
142 | ty::TyInt(..) | // OutlivesScalar | |
143 | ty::TyUint(..) | // OutlivesScalar | |
144 | ty::TyFloat(..) | // OutlivesScalar | |
5bcae85e | 145 | ty::TyNever | // ... |
9e0c209e | 146 | ty::TyAdt(..) | // OutlivesNominalType |
5bcae85e | 147 | ty::TyAnon(..) | // OutlivesNominalType (ish) |
abe05a73 | 148 | ty::TyForeign(..) | // OutlivesNominalType |
a7813a04 XL |
149 | ty::TyStr | // OutlivesScalar (ish) |
150 | ty::TyArray(..) | // ... | |
151 | ty::TySlice(..) | // ... | |
152 | ty::TyRawPtr(..) | // ... | |
153 | ty::TyRef(..) | // OutlivesReference | |
154 | ty::TyTuple(..) | // ... | |
155 | ty::TyFnDef(..) | // OutlivesFunction (*) | |
156 | ty::TyFnPtr(_) | // OutlivesFunction (*) | |
476ff2be | 157 | ty::TyDynamic(..) | // OutlivesObject, OutlivesFragment (*) |
a7813a04 XL |
158 | ty::TyError => { |
159 | // (*) Bare functions and traits are both binders. In the | |
160 | // RFC, this means we would add the bound regions to the | |
161 | // "bound regions list". In our representation, no such | |
162 | // list is maintained explicitly, because bound regions | |
163 | // themselves can be readily identified. | |
9cc50fc6 | 164 | |
a7813a04 XL |
165 | push_region_constraints(out, ty.regions()); |
166 | for subty in ty.walk_shallow() { | |
167 | self.compute_components(subty, out); | |
168 | } | |
e9174d1e SL |
169 | } |
170 | } | |
171 | } | |
e9174d1e | 172 | |
a7813a04 XL |
173 | fn capture_components(&self, ty: Ty<'tcx>) -> Vec<Component<'tcx>> { |
174 | let mut temp = vec![]; | |
175 | push_region_constraints(&mut temp, ty.regions()); | |
176 | for subty in ty.walk_shallow() { | |
177 | self.compute_components(subty, &mut temp); | |
178 | } | |
179 | temp | |
e9174d1e | 180 | } |
e9174d1e SL |
181 | } |
182 | ||
7cac9316 | 183 | fn push_region_constraints<'tcx>(out: &mut Vec<Component<'tcx>>, regions: Vec<ty::Region<'tcx>>) { |
e9174d1e | 184 | for r in regions { |
7cac9316 | 185 | if !r.is_late_bound() { |
e9174d1e SL |
186 | out.push(Component::Region(r)); |
187 | } | |
188 | } | |
189 | } |