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
) => {
77 for upvar_ty
in substs
.upvar_tys(def_id
, *self) {
78 self.compute_components(upvar_ty
, out
);
82 ty
::TyGenerator(def_id
, ref substs
, _
) => {
83 // Same as the closure case
84 for upvar_ty
in substs
.upvar_tys(def_id
, *self) {
85 self.compute_components(upvar_ty
, out
);
88 // We ignore regions in the generator interior as we don't
89 // want these to affect region inference
92 // All regions are bound inside a witness
93 ty
::TyGeneratorWitness(..) => (),
95 // OutlivesTypeParameterEnv -- the actual checking that `X:'a`
96 // is implied by the environment is done in regionck.
98 out
.push(Component
::Param(p
));
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
));
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
));
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
));
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
140 ty
::TyBool
| // OutlivesScalar
141 ty
::TyChar
| // OutlivesScalar
142 ty
::TyInt(..) | // OutlivesScalar
143 ty
::TyUint(..) | // OutlivesScalar
144 ty
::TyFloat(..) | // OutlivesScalar
146 ty
::TyAdt(..) | // OutlivesNominalType
147 ty
::TyAnon(..) | // OutlivesNominalType (ish)
148 ty
::TyForeign(..) | // OutlivesNominalType
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 (*)
157 ty
::TyDynamic(..) | // OutlivesObject, OutlivesFragment (*)
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.
165 push_region_constraints(out
, ty
.regions());
166 for subty
in ty
.walk_shallow() {
167 self.compute_components(subty
, out
);
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
);
183 fn push_region_constraints
<'tcx
>(out
: &mut Vec
<Component
<'tcx
>>, regions
: Vec
<ty
::Region
<'tcx
>>) {
185 if !r
.is_late_bound() {
186 out
.push(Component
::Region(r
));