]> git.proxmox.com Git - rustc.git/blob - src/librustc/ty/outlives.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc / ty / outlives.rs
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 infer::InferCtxt;
16 use ty::{self, Ty, TypeFoldable};
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
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
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.)
171 ty::TyBool | // OutlivesScalar
172 ty::TyChar | // OutlivesScalar
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)
179 ty::TyStr | // OutlivesScalar (ish)
180 ty::TyArray(..) | // ...
181 ty::TySlice(..) | // ...
182 ty::TyRawPtr(..) | // ...
183 ty::TyRef(..) | // OutlivesReference
184 ty::TyTuple(..) | // ...
185 ty::TyFnDef(..) | // OutlivesFunction (*)
186 ty::TyFnPtr(_) | // OutlivesFunction (*)
187 ty::TyTrait(..) | // OutlivesObject, OutlivesFragment (*)
188 ty::TyError => {
189 // (*) Bare functions and traits are both binders. In the
190 // RFC, this means we would add the bound regions to the
191 // "bound regions list". In our representation, no such
192 // list is maintained explicitly, because bound regions
193 // themselves can be readily identified.
194
195 push_region_constraints(out, ty.regions());
196 for subty in ty.walk_shallow() {
197 compute_components(infcx, subty, out);
198 }
199 }
200 }
201 }
202
203 fn capture_components<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>,
204 ty: Ty<'tcx>)
205 -> Vec<Component<'tcx>> {
206 let mut temp = vec![];
207 push_region_constraints(&mut temp, ty.regions());
208 for subty in ty.walk_shallow() {
209 compute_components(infcx, subty, &mut temp);
210 }
211 temp
212 }
213
214 fn push_region_constraints<'tcx>(out: &mut Vec<Component<'tcx>>, regions: Vec<ty::Region>) {
215 for r in regions {
216 if !r.is_bound() {
217 out.push(Component::Region(r));
218 }
219 }
220 }