1 use rustc_data_structures
::fx
::FxHashMap
;
3 use rustc_hir
::def_id
::DefId
;
4 use rustc_hir
::itemlikevisit
::ItemLikeVisitor
;
5 use rustc_middle
::ty
::subst
::{GenericArg, GenericArgKind, Subst}
;
6 use rustc_middle
::ty
::{self, Ty, TyCtxt}
;
9 use super::explicit
::ExplicitPredicatesMap
;
12 /// Infer predicates for the items in the crate.
14 /// `global_inferred_outlives`: this is initially the empty map that
15 /// was generated by walking the items in the crate. This will
16 /// now be filled with inferred predicates.
17 pub fn infer_predicates
<'tcx
>(
19 explicit_map
: &mut ExplicitPredicatesMap
<'tcx
>,
20 ) -> FxHashMap
<DefId
, RequiredPredicates
<'tcx
>> {
21 debug
!("infer_predicates");
23 let mut predicates_added
= true;
25 let mut global_inferred_outlives
= FxHashMap
::default();
27 // If new predicates were added then we need to re-calculate
28 // all crates since there could be new implied predicates.
29 while predicates_added
{
30 predicates_added
= false;
32 let mut visitor
= InferVisitor
{
34 global_inferred_outlives
: &mut global_inferred_outlives
,
35 predicates_added
: &mut predicates_added
,
39 // Visit all the crates and infer predicates
40 tcx
.hir().krate().visit_all_item_likes(&mut visitor
);
43 global_inferred_outlives
46 pub struct InferVisitor
<'cx
, 'tcx
> {
48 global_inferred_outlives
: &'cx
mut FxHashMap
<DefId
, RequiredPredicates
<'tcx
>>,
49 predicates_added
: &'cx
mut bool
,
50 explicit_map
: &'cx
mut ExplicitPredicatesMap
<'tcx
>,
53 impl<'cx
, 'tcx
> ItemLikeVisitor
<'tcx
> for InferVisitor
<'cx
, 'tcx
> {
54 fn visit_item(&mut self, item
: &hir
::Item
<'_
>) {
55 let item_did
= item
.def_id
;
57 debug
!("InferVisitor::visit_item(item={:?})", item_did
);
59 let mut item_required_predicates
= RequiredPredicates
::default();
61 hir
::ItemKind
::Union(..) | hir
::ItemKind
::Enum(..) | hir
::ItemKind
::Struct(..) => {
62 let adt_def
= self.tcx
.adt_def(item_did
.to_def_id());
64 // Iterate over all fields in item_did
65 for field_def
in adt_def
.all_fields() {
66 // Calculating the predicate requirements necessary
69 // For field of type &'a T (reference) or Adt
70 // (struct/enum/union) there will be outlive
71 // requirements for adt_def.
72 let field_ty
= self.tcx
.type_of(field_def
.did
);
73 let field_span
= self.tcx
.def_span(field_def
.did
);
74 insert_required_predicates_to_be_wf(
78 self.global_inferred_outlives
,
79 &mut item_required_predicates
,
80 &mut self.explicit_map
,
88 // If new predicates were added (`local_predicate_map` has more
89 // predicates than the `global_inferred_outlives`), the new predicates
90 // might result in implied predicates for their parent types.
91 // Therefore mark `predicates_added` as true and which will ensure
92 // we walk the crates again and re-calculate predicates for all
94 let item_predicates_len
: usize =
95 self.global_inferred_outlives
.get(&item_did
.to_def_id()).map_or(0, |p
| p
.len());
96 if item_required_predicates
.len() > item_predicates_len
{
97 *self.predicates_added
= true;
98 self.global_inferred_outlives
.insert(item_did
.to_def_id(), item_required_predicates
);
102 fn visit_trait_item(&mut self, _trait_item
: &'tcx hir
::TraitItem
<'tcx
>) {}
104 fn visit_impl_item(&mut self, _impl_item
: &'tcx hir
::ImplItem
<'tcx
>) {}
106 fn visit_foreign_item(&mut self, _foreign_item
: &'tcx hir
::ForeignItem
<'tcx
>) {}
109 fn insert_required_predicates_to_be_wf
<'tcx
>(
113 global_inferred_outlives
: &FxHashMap
<DefId
, RequiredPredicates
<'tcx
>>,
114 required_predicates
: &mut RequiredPredicates
<'tcx
>,
115 explicit_map
: &mut ExplicitPredicatesMap
<'tcx
>,
117 for arg
in field_ty
.walk() {
118 let ty
= match arg
.unpack() {
119 GenericArgKind
::Type(ty
) => ty
,
121 // No predicates from lifetimes or constants, except potentially
122 // constants' types, but `walk` will get to them as well.
123 GenericArgKind
::Lifetime(_
) | GenericArgKind
::Const(_
) => continue,
127 // The field is of type &'a T which means that we will have
128 // a predicate requirement of T: 'a (T outlives 'a).
130 // We also want to calculate potential predicates for the T
131 ty
::Ref(region
, rty
, _
) => {
133 insert_outlives_predicate(tcx
, rty
.into(), region
, field_span
, required_predicates
);
136 // For each Adt (struct/enum/union) type `Foo<'a, T>`, we
137 // can load the current set of inferred and explicit
138 // predicates from `global_inferred_outlives` and filter the
139 // ones that are TypeOutlives.
140 ty
::Adt(def
, substs
) => {
141 // First check the inferred predicates
145 // struct Foo<'a, T> {
146 // field1: Bar<'a, T>
149 // struct Bar<'b, U> {
153 // Here, when processing the type of `field1`, we would
154 // request the set of implicit predicates computed for `Bar`
155 // thus far. This will initially come back empty, but in next
156 // round we will get `U: 'b`. We then apply the substitution
157 // `['b => 'a, U => T]` and thus get the requirement that `T:
158 // 'a` holds for `Foo`.
160 if let Some(unsubstituted_predicates
) = global_inferred_outlives
.get(&def
.did
) {
161 for (unsubstituted_predicate
, &span
) in unsubstituted_predicates
{
162 // `unsubstituted_predicate` is `U: 'b` in the
163 // example above. So apply the substitution to
164 // get `T: 'a` (or `predicate`):
165 let predicate
= unsubstituted_predicate
.subst(tcx
, substs
);
166 insert_outlives_predicate(
176 // Check if the type has any explicit predicates that need
177 // to be added to `required_predicates`
178 // let _: () = substs.region_at(0);
179 check_explicit_predicates(
189 ty
::Dynamic(obj
, ..) => {
190 // This corresponds to `dyn Trait<..>`. In this case, we should
191 // use the explicit predicates as well.
194 debug
!("field_ty = {}", &field_ty
);
195 debug
!("ty in field = {}", &ty
);
196 if let Some(ex_trait_ref
) = obj
.principal() {
197 // Here, we are passing the type `usize` as a
198 // placeholder value with the function
199 // `with_self_ty`, since there is no concrete type
200 // `Self` for a `dyn Trait` at this
201 // stage. Therefore when checking explicit
202 // predicates in `check_explicit_predicates` we
203 // need to ignore checking the explicit_map for
206 ex_trait_ref
.with_self_ty(tcx
, tcx
.types
.usize).skip_binder().substs
;
207 check_explicit_predicates(
209 ex_trait_ref
.skip_binder().def_id
,
213 Some(tcx
.types
.self_param
),
218 ty
::Projection(obj
) => {
219 // This corresponds to `<T as Foo<'a>>::Bar`. In this case, we should use the
220 // explicit predicates as well.
221 debug
!("Projection");
222 check_explicit_predicates(
224 tcx
.associated_item(obj
.item_def_id
).container
.id(),
237 /// We also have to check the explicit predicates
238 /// declared on the type.
240 /// struct Foo<'a, T> {
244 /// struct Bar<U> where U: 'static, U: Foo {
248 /// Here, we should fetch the explicit predicates, which
249 /// will give us `U: 'static` and `U: Foo`. The latter we
250 /// can ignore, but we will want to process `U: 'static`,
251 /// applying the substitution as above.
252 pub fn check_explicit_predicates
<'tcx
>(
255 substs
: &[GenericArg
<'tcx
>],
256 required_predicates
: &mut RequiredPredicates
<'tcx
>,
257 explicit_map
: &mut ExplicitPredicatesMap
<'tcx
>,
258 ignored_self_ty
: Option
<Ty
<'tcx
>>,
261 "check_explicit_predicates(def_id={:?}, \
264 required_predicates={:?}, \
265 ignored_self_ty={:?})",
266 def_id
, substs
, explicit_map
, required_predicates
, ignored_self_ty
,
268 let explicit_predicates
= explicit_map
.explicit_predicates_of(tcx
, def_id
);
270 for (outlives_predicate
, &span
) in explicit_predicates
{
271 debug
!("outlives_predicate = {:?}", &outlives_predicate
);
273 // Careful: If we are inferring the effects of a `dyn Trait<..>`
274 // type, then when we look up the predicates for `Trait`,
275 // we may find some that reference `Self`. e.g., perhaps the
276 // definition of `Trait` was:
279 // trait Trait<'a, T> where Self: 'a { .. }
282 // we want to ignore such predicates here, because
283 // there is no type parameter for them to affect. Consider
284 // a struct containing `dyn Trait`:
287 // struct MyStruct<'x, X> { field: Box<dyn Trait<'x, X>> }
290 // The `where Self: 'a` predicate refers to the *existential, hidden type*
291 // that is represented by the `dyn Trait`, not to the `X` type parameter
292 // (or any other generic parameter) declared on `MyStruct`.
294 // Note that we do this check for self **before** applying `substs`. In the
295 // case that `substs` come from a `dyn Trait` type, our caller will have
296 // included `Self = usize` as the value for `Self`. If we were
297 // to apply the substs, and not filter this predicate, we might then falsely
298 // conclude that e.g., `X: 'x` was a reasonable inferred requirement.
300 // Another similar case is where we have a inferred
301 // requirement like `<Self as Trait>::Foo: 'b`. We presently
302 // ignore such requirements as well (cc #54467)-- though
303 // conceivably it might be better if we could extract the `Foo
304 // = X` binding from the object type (there must be such a
305 // binding) and thus infer an outlives requirement that `X:
307 if let Some(self_ty
) = ignored_self_ty
{
308 if let GenericArgKind
::Type(ty
) = outlives_predicate
.0.unpack
() {
309 if ty
.walk().any(|arg
| arg
== self_ty
.into()) {
310 debug
!("skipping self ty = {:?}", &ty
);
316 let predicate
= outlives_predicate
.subst(tcx
, substs
);
317 debug
!("predicate = {:?}", &predicate
);
318 insert_outlives_predicate(tcx
, predicate
.0, predicate
.1, span
, required_predicates
);