1 use crate::hir
::def_id
::DefId
;
2 use crate::infer
::outlives
::env
::RegionBoundPairs
;
3 use crate::infer
::{GenericKind, VerifyBound}
;
5 use crate::ty
::subst
::{Subst, InternalSubsts}
;
6 use crate::ty
::{self, Ty, TyCtxt}
;
7 use crate::util
::captures
::Captures
;
9 /// The `TypeOutlives` struct has the job of "lowering" a `T: 'a`
10 /// obligation into a series of `'a: 'b` constraints and "verifys", as
11 /// described on the module comment. The final constraints are emitted
12 /// via a "delegate" of type `D` -- this is usually the `infcx`, which
13 /// accrues them into the `region_obligations` code, but for NLL we
14 /// use something else.
15 pub struct VerifyBoundCx
<'cx
, 'tcx
> {
17 region_bound_pairs
: &'cx RegionBoundPairs
<'tcx
>,
18 implicit_region_bound
: Option
<ty
::Region
<'tcx
>>,
19 param_env
: ty
::ParamEnv
<'tcx
>,
22 impl<'cx
, 'tcx
> VerifyBoundCx
<'cx
, 'tcx
> {
25 region_bound_pairs
: &'cx RegionBoundPairs
<'tcx
>,
26 implicit_region_bound
: Option
<ty
::Region
<'tcx
>>,
27 param_env
: ty
::ParamEnv
<'tcx
>,
32 implicit_region_bound
,
37 /// Returns a "verify bound" that encodes what we know about
38 /// `generic` and the regions it outlives.
39 pub fn generic_bound(&self, generic
: GenericKind
<'tcx
>) -> VerifyBound
<'tcx
> {
41 GenericKind
::Param(param_ty
) => self.param_bound(param_ty
),
42 GenericKind
::Projection(projection_ty
) => self.projection_bound(projection_ty
),
46 fn type_bound(&self, ty
: Ty
<'tcx
>) -> VerifyBound
<'tcx
> {
48 ty
::Param(p
) => self.param_bound(p
),
49 ty
::Projection(data
) => self.projection_bound(data
),
50 _
=> self.recursive_type_bound(ty
),
54 fn param_bound(&self, param_ty
: ty
::ParamTy
) -> VerifyBound
<'tcx
> {
55 debug
!("param_bound(param_ty={:?})", param_ty
);
57 // Start with anything like `T: 'a` we can scrape from the
59 let param_bounds
= self.declared_generic_bounds_from_env(GenericKind
::Param(param_ty
))
61 .map(|outlives
| outlives
.1);
63 // Add in the default bound of fn body that applies to all in
64 // scope type parameters:
65 let param_bounds
= param_bounds
.chain(self.implicit_region_bound
);
67 VerifyBound
::AnyBound(param_bounds
.map(|r
| VerifyBound
::OutlivedBy(r
)).collect())
70 /// Given a projection like `T::Item`, searches the environment
71 /// for where-clauses like `T::Item: 'a`. Returns the set of
72 /// regions `'a` that it finds.
74 /// This is an "approximate" check -- it may not find all
75 /// applicable bounds, and not all the bounds it returns can be
76 /// relied upon. In particular, this check ignores region
77 /// identity. So, for example, if we have `<T as
78 /// Trait<'0>>::Item` where `'0` is a region variable, and the
79 /// user has `<T as Trait<'a>>::Item: 'b` in the environment, then
80 /// the clause from the environment only applies if `'0 = 'a`,
81 /// which we don't know yet. But we would still include `'b` in
83 pub fn projection_approx_declared_bounds_from_env(
85 projection_ty
: ty
::ProjectionTy
<'tcx
>,
86 ) -> Vec
<ty
::OutlivesPredicate
<Ty
<'tcx
>, ty
::Region
<'tcx
>>> {
87 let projection_ty
= GenericKind
::Projection(projection_ty
).to_ty(self.tcx
);
88 let erased_projection_ty
= self.tcx
.erase_regions(&projection_ty
);
89 self.declared_generic_bounds_from_env_with_compare_fn(|ty
| {
90 if let ty
::Projection(..) = ty
.sty
{
91 let erased_ty
= self.tcx
.erase_regions(&ty
);
92 erased_ty
== erased_projection_ty
99 /// Searches the where-clauses in scope for regions that
100 /// `projection_ty` is known to outlive. Currently requires an
102 pub fn projection_declared_bounds_from_trait(
104 projection_ty
: ty
::ProjectionTy
<'tcx
>,
105 ) -> impl Iterator
<Item
= ty
::Region
<'tcx
>> + 'cx
+ Captures
<'tcx
> {
106 self.declared_projection_bounds_from_trait(projection_ty
)
109 pub fn projection_bound(&self, projection_ty
: ty
::ProjectionTy
<'tcx
>) -> VerifyBound
<'tcx
> {
110 debug
!("projection_bound(projection_ty={:?})", projection_ty
);
112 let projection_ty_as_ty
=
113 self.tcx
.mk_projection(projection_ty
.item_def_id
, projection_ty
.substs
);
115 // Search the env for where clauses like `P: 'a`.
116 let env_bounds
= self.projection_approx_declared_bounds_from_env(projection_ty
)
118 .map(|ty
::OutlivesPredicate(ty
, r
)| {
119 let vb
= VerifyBound
::OutlivedBy(r
);
120 if ty
== projection_ty_as_ty
{
121 // Micro-optimize if this is an exact match (this
122 // occurs often when there are no region variables
126 VerifyBound
::IfEq(ty
, Box
::new(vb
))
130 // Extend with bounds that we can find from the trait.
131 let trait_bounds
= self.projection_declared_bounds_from_trait(projection_ty
)
133 .map(|r
| VerifyBound
::OutlivedBy(r
));
135 // see the extensive comment in projection_must_outlive
137 .mk_projection(projection_ty
.item_def_id
, projection_ty
.substs
);
138 let recursive_bound
= self.recursive_type_bound(ty
);
140 VerifyBound
::AnyBound(env_bounds
.chain(trait_bounds
).collect()).or(recursive_bound
)
143 fn recursive_type_bound(&self, ty
: Ty
<'tcx
>) -> VerifyBound
<'tcx
> {
144 let mut bounds
= ty
.walk_shallow()
145 .map(|subty
| self.type_bound(subty
))
146 .collect
::<Vec
<_
>>();
148 let mut regions
= smallvec
![];
149 ty
.push_regions(&mut regions
);
150 regions
.retain(|r
| !r
.is_late_bound()); // ignore late-bound regions
151 bounds
.push(VerifyBound
::AllBounds(
154 .map(|r
| VerifyBound
::OutlivedBy(r
))
158 // remove bounds that must hold, since they are not interesting
159 bounds
.retain(|b
| !b
.must_hold());
161 if bounds
.len() == 1 {
162 bounds
.pop().unwrap()
164 VerifyBound
::AllBounds(bounds
)
168 /// Searches the environment for where-clauses like `G: 'a` where
169 /// `G` is either some type parameter `T` or a projection like
170 /// `T::Item`. Returns a vector of the `'a` bounds it can find.
172 /// This is a conservative check -- it may not find all applicable
173 /// bounds, but all the bounds it returns can be relied upon.
174 fn declared_generic_bounds_from_env(
176 generic
: GenericKind
<'tcx
>,
177 ) -> Vec
<ty
::OutlivesPredicate
<Ty
<'tcx
>, ty
::Region
<'tcx
>>> {
178 let generic_ty
= generic
.to_ty(self.tcx
);
179 self.declared_generic_bounds_from_env_with_compare_fn(|ty
| ty
== generic_ty
)
182 fn declared_generic_bounds_from_env_with_compare_fn(
184 compare_ty
: impl Fn(Ty
<'tcx
>) -> bool
,
185 ) -> Vec
<ty
::OutlivesPredicate
<Ty
<'tcx
>, ty
::Region
<'tcx
>>> {
188 // To start, collect bounds from user environment. Note that
189 // parameter environments are already elaborated, so we don't
190 // have to worry about that. Comparing using `==` is a bit
191 // dubious for projections, but it will work for simple cases
192 // like `T` and `T::Item`. It may not work as well for things
193 // like `<T as Foo<'a>>::Item`.
194 let c_b
= self.param_env
.caller_bounds
;
195 let param_bounds
= self.collect_outlives_from_predicate_list(&compare_ty
, c_b
);
197 // Next, collect regions we scraped from the well-formedness
198 // constraints in the fn signature. To do that, we walk the list
199 // of known relations from the fn ctxt.
201 // This is crucial because otherwise code like this fails:
203 // fn foo<'a, A>(x: &'a A) { x.bar() }
205 // The problem is that the type of `x` is `&'a A`. To be
206 // well-formed, then, A must be lower-generic by `'a`, but we
207 // don't know that this holds from first principles.
208 let from_region_bound_pairs
= self.region_bound_pairs
.iter().filter_map(|&(r
, p
)| {
210 "declared_generic_bounds_from_env_with_compare_fn: region_bound_pair = {:?}",
213 let p_ty
= p
.to_ty(tcx
);
214 if compare_ty(p_ty
) {
215 Some(ty
::OutlivesPredicate(p_ty
, r
))
222 .chain(from_region_bound_pairs
)
225 "declared_generic_bounds_from_env_with_compare_fn: result predicate = {:?}",
232 /// Given a projection like `<T as Foo<'x>>::Bar`, returns any bounds
233 /// declared in the trait definition. For example, if the trait were
241 /// then this function would return `'x`. This is subject to the
242 /// limitations around higher-ranked bounds described in
243 /// `region_bounds_declared_on_associated_item`.
244 fn declared_projection_bounds_from_trait(
246 projection_ty
: ty
::ProjectionTy
<'tcx
>,
247 ) -> impl Iterator
<Item
= ty
::Region
<'tcx
>> + 'cx
+ Captures
<'tcx
> {
248 debug
!("projection_bounds(projection_ty={:?})", projection_ty
);
250 self.region_bounds_declared_on_associated_item(projection_ty
.item_def_id
)
251 .map(move |r
| r
.subst(tcx
, projection_ty
.substs
))
254 /// Given the `DefId` of an associated item, returns any region
255 /// bounds attached to that associated item from the trait definition.
265 /// If we were given the `DefId` of `Foo::Bar`, we would return
266 /// `'a`. You could then apply the substitutions from the
267 /// projection to convert this into your namespace. This also
268 /// works if the user writes `where <Self as Foo<'a>>::Bar: 'a` on
269 /// the trait. In fact, it works by searching for just such a
272 /// It will not, however, work for higher-ranked bounds like:
275 /// trait Foo<'a, 'b>
276 /// where for<'x> <Self as Foo<'x, 'b>>::Bar: 'x
282 /// This is for simplicity, and because we are not really smart
283 /// enough to cope with such bounds anywhere.
284 fn region_bounds_declared_on_associated_item(
286 assoc_item_def_id
: DefId
,
287 ) -> impl Iterator
<Item
= ty
::Region
<'tcx
>> + 'cx
+ Captures
<'tcx
> {
289 let assoc_item
= tcx
.associated_item(assoc_item_def_id
);
290 let trait_def_id
= assoc_item
.container
.assert_trait();
291 let trait_predicates
= tcx
.predicates_of(trait_def_id
).predicates
295 let identity_substs
= InternalSubsts
::identity_for_item(tcx
, assoc_item_def_id
);
296 let identity_proj
= tcx
.mk_projection(assoc_item_def_id
, identity_substs
);
297 self.collect_outlives_from_predicate_list(
298 move |ty
| ty
== identity_proj
,
299 traits
::elaborate_predicates(tcx
, trait_predicates
),
303 /// Searches through a predicate list for a predicate `T: 'a`.
305 /// Careful: does not elaborate predicates, and just uses `==`
306 /// when comparing `ty` for equality, so `ty` must be something
307 /// that does not involve inference variables and where you
308 /// otherwise want a precise match.
309 fn collect_outlives_from_predicate_list(
311 compare_ty
: impl Fn(Ty
<'tcx
>) -> bool
,
312 predicates
: impl IntoIterator
<Item
= impl AsRef
<ty
::Predicate
<'tcx
>>>,
313 ) -> impl Iterator
<Item
= ty
::OutlivesPredicate
<Ty
<'tcx
>, ty
::Region
<'tcx
>>> {
316 .filter_map(|p
| p
.as_ref().to_opt_type_outlives())
317 .filter_map(|p
| p
.no_bound_vars())
318 .filter(move |p
| compare_ty(p
.0))