1 use crate::infer
::outlives
::env
::RegionBoundPairs
;
2 use crate::infer
::{GenericKind, VerifyBound}
;
3 use rustc_data_structures
::captures
::Captures
;
4 use rustc_data_structures
::sso
::SsoHashSet
;
5 use rustc_hir
::def_id
::DefId
;
6 use rustc_middle
::ty
::subst
::{GenericArg, GenericArgKind, Subst}
;
7 use rustc_middle
::ty
::{self, EarlyBinder, Ty, TyCtxt}
;
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
>,
29 Self { tcx, region_bound_pairs, implicit_region_bound, param_env }
32 /// Returns a "verify bound" that encodes what we know about
33 /// `generic` and the regions it outlives.
34 pub fn generic_bound(&self, generic
: GenericKind
<'tcx
>) -> VerifyBound
<'tcx
> {
35 let mut visited
= SsoHashSet
::new();
37 GenericKind
::Param(param_ty
) => self.param_bound(param_ty
),
38 GenericKind
::Projection(projection_ty
) => {
39 self.projection_bound(projection_ty
, &mut visited
)
47 visited
: &mut SsoHashSet
<GenericArg
<'tcx
>>,
48 ) -> VerifyBound
<'tcx
> {
50 ty
::Param(p
) => self.param_bound(p
),
51 ty
::Projection(data
) => self.projection_bound(data
, visited
),
52 ty
::FnDef(_
, substs
) => {
53 // HACK(eddyb) ignore lifetimes found shallowly in `substs`.
54 // This is inconsistent with `ty::Adt` (including all substs),
55 // but consistent with previous (accidental) behavior.
56 // See https://github.com/rust-lang/rust/issues/70917
57 // for further background and discussion.
58 let mut bounds
= substs
60 .filter_map(|child
| match child
.unpack() {
61 GenericArgKind
::Type(ty
) => Some(self.type_bound(ty
, visited
)),
62 GenericArgKind
::Lifetime(_
) => None
,
63 GenericArgKind
::Const(_
) => Some(self.recursive_bound(child
, visited
)),
66 // Remove bounds that must hold, since they are not interesting.
70 match (bounds
.next(), bounds
.next()) {
71 (Some(first
), None
) => first
,
72 (first
, second
) => VerifyBound
::AllBounds(
73 first
.into_iter().chain(second
).chain(bounds
).collect(),
77 _
=> self.recursive_bound(ty
.into(), visited
),
81 fn param_bound(&self, param_ty
: ty
::ParamTy
) -> VerifyBound
<'tcx
> {
82 debug
!("param_bound(param_ty={:?})", param_ty
);
84 // Start with anything like `T: 'a` we can scrape from the
86 let param_bounds
= self
87 .declared_generic_bounds_from_env(GenericKind
::Param(param_ty
))
89 .map(|outlives
| outlives
.1);
91 // Add in the default bound of fn body that applies to all in
92 // scope type parameters:
93 let param_bounds
= param_bounds
.chain(self.implicit_region_bound
);
95 let any_bounds
: Vec
<_
> = param_bounds
.map(|r
| VerifyBound
::OutlivedBy(r
)).collect();
97 if any_bounds
.is_empty() {
98 // We know that all types `T` outlive `'empty`, so if we
99 // can find no other bound, then check that the region
100 // being tested is `'empty`.
103 // If we can find any other bound `R` such that `T: R`, then
104 // we don't need to check for `'empty`, because `R: 'empty`.
105 VerifyBound
::AnyBound(any_bounds
)
109 /// Given a projection like `T::Item`, searches the environment
110 /// for where-clauses like `T::Item: 'a`. Returns the set of
111 /// regions `'a` that it finds.
113 /// This is an "approximate" check -- it may not find all
114 /// applicable bounds, and not all the bounds it returns can be
115 /// relied upon. In particular, this check ignores region
116 /// identity. So, for example, if we have `<T as
117 /// Trait<'0>>::Item` where `'0` is a region variable, and the
118 /// user has `<T as Trait<'a>>::Item: 'b` in the environment, then
119 /// the clause from the environment only applies if `'0 = 'a`,
120 /// which we don't know yet. But we would still include `'b` in
122 pub fn projection_approx_declared_bounds_from_env(
124 projection_ty
: ty
::ProjectionTy
<'tcx
>,
125 ) -> Vec
<ty
::OutlivesPredicate
<Ty
<'tcx
>, ty
::Region
<'tcx
>>> {
126 let projection_ty
= GenericKind
::Projection(projection_ty
).to_ty(self.tcx
);
127 let erased_projection_ty
= self.tcx
.erase_regions(projection_ty
);
128 self.declared_generic_bounds_from_env_with_compare_fn(|ty
| {
129 if let ty
::Projection(..) = ty
.kind() {
130 let erased_ty
= self.tcx
.erase_regions(ty
);
131 erased_ty
== erased_projection_ty
138 /// Searches the where-clauses in scope for regions that
139 /// `projection_ty` is known to outlive. Currently requires an
141 pub fn projection_declared_bounds_from_trait(
143 projection_ty
: ty
::ProjectionTy
<'tcx
>,
144 ) -> impl Iterator
<Item
= ty
::Region
<'tcx
>> + 'cx
+ Captures
<'tcx
> {
145 self.declared_projection_bounds_from_trait(projection_ty
)
148 pub fn projection_bound(
150 projection_ty
: ty
::ProjectionTy
<'tcx
>,
151 visited
: &mut SsoHashSet
<GenericArg
<'tcx
>>,
152 ) -> VerifyBound
<'tcx
> {
153 debug
!("projection_bound(projection_ty={:?})", projection_ty
);
155 let projection_ty_as_ty
=
156 self.tcx
.mk_projection(projection_ty
.item_def_id
, projection_ty
.substs
);
158 // Search the env for where clauses like `P: 'a`.
159 let env_bounds
= self
160 .projection_approx_declared_bounds_from_env(projection_ty
)
162 .map(|ty
::OutlivesPredicate(ty
, r
)| {
163 let vb
= VerifyBound
::OutlivedBy(r
);
164 if ty
== projection_ty_as_ty
{
165 // Micro-optimize if this is an exact match (this
166 // occurs often when there are no region variables
170 VerifyBound
::IfEq(ty
, Box
::new(vb
))
174 // Extend with bounds that we can find from the trait.
175 let trait_bounds
= self
176 .projection_declared_bounds_from_trait(projection_ty
)
177 .map(|r
| VerifyBound
::OutlivedBy(r
));
179 // see the extensive comment in projection_must_outlive
180 let ty
= self.tcx
.mk_projection(projection_ty
.item_def_id
, projection_ty
.substs
);
181 let recursive_bound
= self.recursive_bound(ty
.into(), visited
);
183 VerifyBound
::AnyBound(env_bounds
.chain(trait_bounds
).collect()).or(recursive_bound
)
188 parent
: GenericArg
<'tcx
>,
189 visited
: &mut SsoHashSet
<GenericArg
<'tcx
>>,
190 ) -> VerifyBound
<'tcx
> {
191 let mut bounds
= parent
192 .walk_shallow(visited
)
193 .filter_map(|child
| match child
.unpack() {
194 GenericArgKind
::Type(ty
) => Some(self.type_bound(ty
, visited
)),
195 GenericArgKind
::Lifetime(lt
) => {
196 // Ignore late-bound regions.
197 if !lt
.is_late_bound() { Some(VerifyBound::OutlivedBy(lt)) }
else { None }
199 GenericArgKind
::Const(_
) => Some(self.recursive_bound(child
, visited
)),
202 // Remove bounds that must hold, since they are not interesting.
206 match (bounds
.next(), bounds
.next()) {
207 (Some(first
), None
) => first
,
209 VerifyBound
::AllBounds(first
.into_iter().chain(second
).chain(bounds
).collect())
214 /// Searches the environment for where-clauses like `G: 'a` where
215 /// `G` is either some type parameter `T` or a projection like
216 /// `T::Item`. Returns a vector of the `'a` bounds it can find.
218 /// This is a conservative check -- it may not find all applicable
219 /// bounds, but all the bounds it returns can be relied upon.
220 fn declared_generic_bounds_from_env(
222 generic
: GenericKind
<'tcx
>,
223 ) -> Vec
<ty
::OutlivesPredicate
<Ty
<'tcx
>, ty
::Region
<'tcx
>>> {
224 let generic_ty
= generic
.to_ty(self.tcx
);
225 self.declared_generic_bounds_from_env_with_compare_fn(|ty
| ty
== generic_ty
)
228 fn declared_generic_bounds_from_env_with_compare_fn(
230 compare_ty
: impl Fn(Ty
<'tcx
>) -> bool
,
231 ) -> Vec
<ty
::OutlivesPredicate
<Ty
<'tcx
>, ty
::Region
<'tcx
>>> {
234 // To start, collect bounds from user environment. Note that
235 // parameter environments are already elaborated, so we don't
236 // have to worry about that. Comparing using `==` is a bit
237 // dubious for projections, but it will work for simple cases
238 // like `T` and `T::Item`. It may not work as well for things
239 // like `<T as Foo<'a>>::Item`.
240 let c_b
= self.param_env
.caller_bounds();
241 let param_bounds
= self.collect_outlives_from_predicate_list(&compare_ty
, c_b
.into_iter());
243 // Next, collect regions we scraped from the well-formedness
244 // constraints in the fn signature. To do that, we walk the list
245 // of known relations from the fn ctxt.
247 // This is crucial because otherwise code like this fails:
249 // fn foo<'a, A>(x: &'a A) { x.bar() }
251 // The problem is that the type of `x` is `&'a A`. To be
252 // well-formed, then, A must be lower-generic by `'a`, but we
253 // don't know that this holds from first principles.
254 let from_region_bound_pairs
= self.region_bound_pairs
.iter().filter_map(|&(r
, p
)| {
256 "declared_generic_bounds_from_env_with_compare_fn: region_bound_pair = {:?}",
259 let p_ty
= p
.to_ty(tcx
);
260 compare_ty(p_ty
).then_some(ty
::OutlivesPredicate(p_ty
, r
))
264 .chain(from_region_bound_pairs
)
267 "declared_generic_bounds_from_env_with_compare_fn: result predicate = {:?}",
274 /// Given a projection like `<T as Foo<'x>>::Bar`, returns any bounds
275 /// declared in the trait definition. For example, if the trait were
283 /// then this function would return `'x`. This is subject to the
284 /// limitations around higher-ranked bounds described in
285 /// `region_bounds_declared_on_associated_item`.
286 fn declared_projection_bounds_from_trait(
288 projection_ty
: ty
::ProjectionTy
<'tcx
>,
289 ) -> impl Iterator
<Item
= ty
::Region
<'tcx
>> + 'cx
+ Captures
<'tcx
> {
290 debug
!("projection_bounds(projection_ty={:?})", projection_ty
);
292 self.region_bounds_declared_on_associated_item(projection_ty
.item_def_id
)
293 .map(move |r
| EarlyBinder(r
).subst(tcx
, projection_ty
.substs
))
296 /// Given the `DefId` of an associated item, returns any region
297 /// bounds attached to that associated item from the trait definition.
307 /// If we were given the `DefId` of `Foo::Bar`, we would return
308 /// `'a`. You could then apply the substitutions from the
309 /// projection to convert this into your namespace. This also
310 /// works if the user writes `where <Self as Foo<'a>>::Bar: 'a` on
311 /// the trait. In fact, it works by searching for just such a
314 /// It will not, however, work for higher-ranked bounds like:
316 /// ```compile_fail,E0311
317 /// trait Foo<'a, 'b>
318 /// where for<'x> <Self as Foo<'x, 'b>>::Bar: 'x
324 /// This is for simplicity, and because we are not really smart
325 /// enough to cope with such bounds anywhere.
326 fn region_bounds_declared_on_associated_item(
328 assoc_item_def_id
: DefId
,
329 ) -> impl Iterator
<Item
= ty
::Region
<'tcx
>> {
331 let bounds
= tcx
.item_bounds(assoc_item_def_id
);
334 .filter_map(|p
| p
.to_opt_type_outlives())
335 .filter_map(|p
| p
.no_bound_vars())
339 /// Searches through a predicate list for a predicate `T: 'a`.
341 /// Careful: does not elaborate predicates, and just uses `==`
342 /// when comparing `ty` for equality, so `ty` must be something
343 /// that does not involve inference variables and where you
344 /// otherwise want a precise match.
345 fn collect_outlives_from_predicate_list(
347 compare_ty
: impl Fn(Ty
<'tcx
>) -> bool
,
348 predicates
: impl Iterator
<Item
= ty
::Predicate
<'tcx
>>,
349 ) -> impl Iterator
<Item
= ty
::OutlivesPredicate
<Ty
<'tcx
>, ty
::Region
<'tcx
>>> {
351 .filter_map(|p
| p
.to_opt_type_outlives())
352 .filter_map(|p
| p
.no_bound_vars())
353 .filter(move |p
| compare_ty(p
.0))