1 use rustc_data_structures::fx::FxHashMap;
2 use rustc_hir::def::DefKind;
3 use rustc_hir::def_id::DefId;
4 use rustc_middle::ty::{self, DefIdTree, Ty, TyCtxt};
5 use rustc_middle::ty::{GenericArg, GenericArgKind};
8 use super::explicit::ExplicitPredicatesMap;
11 /// Infer predicates for the items in the crate.
13 /// `global_inferred_outlives`: this is initially the empty map that
14 /// was generated by walking the items in the crate. This will
15 /// now be filled with inferred predicates.
16 pub(super) fn infer_predicates<'tcx>(
18 ) -> FxHashMap<DefId, ty::EarlyBinder<RequiredPredicates<'tcx>>> {
19 debug!("infer_predicates");
21 let mut explicit_map = ExplicitPredicatesMap::new();
23 let mut global_inferred_outlives = FxHashMap::default();
25 // If new predicates were added then we need to re-calculate
26 // all crates since there could be new implied predicates.
28 let mut predicates_added = false;
30 // Visit all the crates and infer predicates
31 for id in tcx.hir().items() {
32 let item_did = id.owner_id;
34 debug!("InferVisitor::visit_item(item={:?})", item_did);
36 let mut item_required_predicates = RequiredPredicates::default();
37 match tcx.def_kind(item_did) {
38 DefKind::Union | DefKind::Enum | DefKind::Struct => {
39 let adt_def = tcx.adt_def(item_did.to_def_id());
41 // Iterate over all fields in item_did
42 for field_def in adt_def.all_fields() {
43 // Calculating the predicate requirements necessary
46 // For field of type &'a T (reference) or Adt
47 // (struct/enum/union) there will be outlive
48 // requirements for adt_def.
49 let field_ty = tcx.type_of(field_def.did);
50 let field_span = tcx.def_span(field_def.did);
51 insert_required_predicates_to_be_wf(
55 &global_inferred_outlives,
56 &mut item_required_predicates,
65 // If new predicates were added (`local_predicate_map` has more
66 // predicates than the `global_inferred_outlives`), the new predicates
67 // might result in implied predicates for their parent types.
68 // Therefore mark `predicates_added` as true and which will ensure
69 // we walk the crates again and re-calculate predicates for all
71 let item_predicates_len: usize =
72 global_inferred_outlives.get(&item_did.to_def_id()).map_or(0, |p| p.0.len());
73 if item_required_predicates.len() > item_predicates_len {
74 predicates_added = true;
75 global_inferred_outlives
76 .insert(item_did.to_def_id(), ty::EarlyBinder(item_required_predicates));
80 if !predicates_added {
85 global_inferred_outlives
88 fn insert_required_predicates_to_be_wf<'tcx>(
92 global_inferred_outlives: &FxHashMap<DefId, ty::EarlyBinder<RequiredPredicates<'tcx>>>,
93 required_predicates: &mut RequiredPredicates<'tcx>,
94 explicit_map: &mut ExplicitPredicatesMap<'tcx>,
96 for arg in field_ty.walk() {
97 let ty = match arg.unpack() {
98 GenericArgKind::Type(ty) => ty,
100 // No predicates from lifetimes or constants, except potentially
101 // constants' types, but `walk` will get to them as well.
102 GenericArgKind::Lifetime(_) | GenericArgKind::Const(_) => continue,
106 // The field is of type &'a T which means that we will have
107 // a predicate requirement of T: 'a (T outlives 'a).
109 // We also want to calculate potential predicates for the T
110 ty::Ref(region, rty, _) => {
112 insert_outlives_predicate(tcx, rty.into(), region, field_span, required_predicates);
115 // For each Adt (struct/enum/union) type `Foo<'a, T>`, we
116 // can load the current set of inferred and explicit
117 // predicates from `global_inferred_outlives` and filter the
118 // ones that are TypeOutlives.
119 ty::Adt(def, substs) => {
120 // First check the inferred predicates
124 // struct Foo<'a, T> {
125 // field1: Bar<'a, T>
128 // struct Bar<'b, U> {
132 // Here, when processing the type of `field1`, we would
133 // request the set of implicit predicates computed for `Bar`
134 // thus far. This will initially come back empty, but in next
135 // round we will get `U: 'b`. We then apply the substitution
136 // `['b => 'a, U => T]` and thus get the requirement that `T:
137 // 'a` holds for `Foo`.
139 if let Some(unsubstituted_predicates) = global_inferred_outlives.get(&def.did()) {
140 for (unsubstituted_predicate, &span) in &unsubstituted_predicates.0 {
141 // `unsubstituted_predicate` is `U: 'b` in the
142 // example above. So apply the substitution to
143 // get `T: 'a` (or `predicate`):
144 let predicate = unsubstituted_predicates
145 .rebind(*unsubstituted_predicate)
147 insert_outlives_predicate(
157 // Check if the type has any explicit predicates that need
158 // to be added to `required_predicates`
159 // let _: () = substs.region_at(0);
160 check_explicit_predicates(
170 ty::Dynamic(obj, ..) => {
171 // This corresponds to `dyn Trait<..>`. In this case, we should
172 // use the explicit predicates as well.
175 debug!("field_ty = {}", &field_ty);
176 debug!("ty in field = {}", &ty);
177 if let Some(ex_trait_ref) = obj.principal() {
178 // Here, we are passing the type `usize` as a
179 // placeholder value with the function
180 // `with_self_ty`, since there is no concrete type
181 // `Self` for a `dyn Trait` at this
182 // stage. Therefore when checking explicit
183 // predicates in `check_explicit_predicates` we
184 // need to ignore checking the explicit_map for
187 ex_trait_ref.with_self_ty(tcx, tcx.types.usize).skip_binder().substs;
188 check_explicit_predicates(
190 ex_trait_ref.skip_binder().def_id,
194 Some(tcx.types.self_param),
199 ty::Projection(obj) => {
200 // This corresponds to `<T as Foo<'a>>::Bar`. In this case, we should use the
201 // explicit predicates as well.
202 debug!("Projection");
203 check_explicit_predicates(
205 tcx.parent(obj.item_def_id),
218 /// We also have to check the explicit predicates
219 /// declared on the type.
220 /// ```ignore (illustrative)
221 /// struct Foo<'a, T> {
225 /// struct Bar<U> where U: 'static, U: Foo {
229 /// Here, we should fetch the explicit predicates, which
230 /// will give us `U: 'static` and `U: Foo`. The latter we
231 /// can ignore, but we will want to process `U: 'static`,
232 /// applying the substitution as above.
233 fn check_explicit_predicates<'tcx>(
236 substs: &[GenericArg<'tcx>],
237 required_predicates: &mut RequiredPredicates<'tcx>,
238 explicit_map: &mut ExplicitPredicatesMap<'tcx>,
239 ignored_self_ty: Option<Ty<'tcx>>,
242 "check_explicit_predicates(def_id={:?}, \
245 required_predicates={:?}, \
246 ignored_self_ty={:?})",
247 def_id, substs, explicit_map, required_predicates, ignored_self_ty,
249 let explicit_predicates = explicit_map.explicit_predicates_of(tcx, def_id);
251 for (outlives_predicate, &span) in &explicit_predicates.0 {
252 debug!("outlives_predicate = {:?}", &outlives_predicate);
254 // Careful: If we are inferring the effects of a `dyn Trait<..>`
255 // type, then when we look up the predicates for `Trait`,
256 // we may find some that reference `Self`. e.g., perhaps the
257 // definition of `Trait` was:
260 // trait Trait<'a, T> where Self: 'a { .. }
263 // we want to ignore such predicates here, because
264 // there is no type parameter for them to affect. Consider
265 // a struct containing `dyn Trait`:
268 // struct MyStruct<'x, X> { field: Box<dyn Trait<'x, X>> }
271 // The `where Self: 'a` predicate refers to the *existential, hidden type*
272 // that is represented by the `dyn Trait`, not to the `X` type parameter
273 // (or any other generic parameter) declared on `MyStruct`.
275 // Note that we do this check for self **before** applying `substs`. In the
276 // case that `substs` come from a `dyn Trait` type, our caller will have
277 // included `Self = usize` as the value for `Self`. If we were
278 // to apply the substs, and not filter this predicate, we might then falsely
279 // conclude that e.g., `X: 'x` was a reasonable inferred requirement.
281 // Another similar case is where we have an inferred
282 // requirement like `<Self as Trait>::Foo: 'b`. We presently
283 // ignore such requirements as well (cc #54467)-- though
284 // conceivably it might be better if we could extract the `Foo
285 // = X` binding from the object type (there must be such a
286 // binding) and thus infer an outlives requirement that `X:
288 if let Some(self_ty) = ignored_self_ty
289 && let GenericArgKind::Type(ty) = outlives_predicate.0.unpack()
290 && ty.walk().any(|arg| arg == self_ty.into())
292 debug!("skipping self ty = {:?}", &ty);
296 let predicate = explicit_predicates.rebind(*outlives_predicate).subst(tcx, substs);
297 debug!("predicate = {:?}", &predicate);
298 insert_outlives_predicate(tcx, predicate.0, predicate.1, span, required_predicates);