1 use rustc_data_structures::fx::FxHashMap;
3 use rustc_hir::def_id::DefId;
4 use rustc_hir::itemlikevisit::ItemLikeVisitor;
6 use rustc_middle::ty::subst::{GenericArg, GenericArgKind, Subst};
7 use rustc_middle::ty::{self, Ty, TyCtxt};
10 use super::explicit::ExplicitPredicatesMap;
13 /// Infer predicates for the items in the crate.
15 /// `global_inferred_outlives`: this is initially the empty map that
16 /// was generated by walking the items in the crate. This will
17 /// now be filled with inferred predicates.
18 pub fn infer_predicates<'tcx>(
20 explicit_map: &mut ExplicitPredicatesMap<'tcx>,
21 ) -> FxHashMap<DefId, RequiredPredicates<'tcx>> {
22 debug!("infer_predicates");
24 let mut predicates_added = true;
26 let mut global_inferred_outlives = FxHashMap::default();
28 // If new predicates were added then we need to re-calculate
29 // all crates since there could be new implied predicates.
30 while predicates_added {
31 predicates_added = false;
33 let mut visitor = InferVisitor {
35 global_inferred_outlives: &mut global_inferred_outlives,
36 predicates_added: &mut predicates_added,
40 // Visit all the crates and infer predicates
41 tcx.hir().krate().visit_all_item_likes(&mut visitor);
44 global_inferred_outlives
47 pub struct InferVisitor<'cx, 'tcx> {
49 global_inferred_outlives: &'cx mut FxHashMap<DefId, RequiredPredicates<'tcx>>,
50 predicates_added: &'cx mut bool,
51 explicit_map: &'cx mut ExplicitPredicatesMap<'tcx>,
54 impl<'cx, 'tcx> ItemLikeVisitor<'tcx> for InferVisitor<'cx, 'tcx> {
55 fn visit_item(&mut self, item: &hir::Item<'_>) {
56 let item_did = self.tcx.hir().local_def_id(item.hir_id);
58 debug!("InferVisitor::visit_item(item={:?})", item_did);
60 let hir_id = self.tcx.hir().as_local_hir_id(item_did);
61 let item = match self.tcx.hir().get(hir_id) {
62 Node::Item(item) => item,
66 let mut item_required_predicates = RequiredPredicates::default();
68 hir::ItemKind::Union(..) | hir::ItemKind::Enum(..) | hir::ItemKind::Struct(..) => {
69 let adt_def = self.tcx.adt_def(item_did.to_def_id());
71 // Iterate over all fields in item_did
72 for field_def in adt_def.all_fields() {
73 // Calculating the predicate requirements necessary
76 // For field of type &'a T (reference) or Adt
77 // (struct/enum/union) there will be outlive
78 // requirements for adt_def.
79 let field_ty = self.tcx.type_of(field_def.did);
80 let field_span = self.tcx.def_span(field_def.did);
81 insert_required_predicates_to_be_wf(
85 self.global_inferred_outlives,
86 &mut item_required_predicates,
87 &mut self.explicit_map,
95 // If new predicates were added (`local_predicate_map` has more
96 // predicates than the `global_inferred_outlives`), the new predicates
97 // might result in implied predicates for their parent types.
98 // Therefore mark `predicates_added` as true and which will ensure
99 // we walk the crates again and re-calculate predicates for all
101 let item_predicates_len: usize =
102 self.global_inferred_outlives.get(&item_did.to_def_id()).map(|p| p.len()).unwrap_or(0);
103 if item_required_predicates.len() > item_predicates_len {
104 *self.predicates_added = true;
105 self.global_inferred_outlives.insert(item_did.to_def_id(), item_required_predicates);
109 fn visit_trait_item(&mut self, _trait_item: &'tcx hir::TraitItem<'tcx>) {}
111 fn visit_impl_item(&mut self, _impl_item: &'tcx hir::ImplItem<'tcx>) {}
114 fn insert_required_predicates_to_be_wf<'tcx>(
118 global_inferred_outlives: &FxHashMap<DefId, RequiredPredicates<'tcx>>,
119 required_predicates: &mut RequiredPredicates<'tcx>,
120 explicit_map: &mut ExplicitPredicatesMap<'tcx>,
122 for arg in field_ty.walk() {
123 let ty = match arg.unpack() {
124 GenericArgKind::Type(ty) => ty,
126 // No predicates from lifetimes or constants, except potentially
127 // constants' types, but `walk` will get to them as well.
128 GenericArgKind::Lifetime(_) | GenericArgKind::Const(_) => continue,
132 // The field is of type &'a T which means that we will have
133 // a predicate requirement of T: 'a (T outlives 'a).
135 // We also want to calculate potential predicates for the T
136 ty::Ref(region, rty, _) => {
138 insert_outlives_predicate(tcx, rty.into(), region, field_span, required_predicates);
141 // For each Adt (struct/enum/union) type `Foo<'a, T>`, we
142 // can load the current set of inferred and explicit
143 // predicates from `global_inferred_outlives` and filter the
144 // ones that are TypeOutlives.
145 ty::Adt(def, substs) => {
146 // First check the inferred predicates
150 // struct Foo<'a, T> {
151 // field1: Bar<'a, T>
154 // struct Bar<'b, U> {
158 // Here, when processing the type of `field1`, we would
159 // request the set of implicit predicates computed for `Bar`
160 // thus far. This will initially come back empty, but in next
161 // round we will get `U: 'b`. We then apply the substitution
162 // `['b => 'a, U => T]` and thus get the requirement that `T:
163 // 'a` holds for `Foo`.
165 if let Some(unsubstituted_predicates) = global_inferred_outlives.get(&def.did) {
166 for (unsubstituted_predicate, &span) in unsubstituted_predicates {
167 // `unsubstituted_predicate` is `U: 'b` in the
168 // example above. So apply the substitution to
169 // get `T: 'a` (or `predicate`):
170 let predicate = unsubstituted_predicate.subst(tcx, substs);
171 insert_outlives_predicate(
181 // Check if the type has any explicit predicates that need
182 // to be added to `required_predicates`
183 // let _: () = substs.region_at(0);
184 check_explicit_predicates(
194 ty::Dynamic(obj, ..) => {
195 // This corresponds to `dyn Trait<..>`. In this case, we should
196 // use the explicit predicates as well.
199 debug!("field_ty = {}", &field_ty);
200 debug!("ty in field = {}", &ty);
201 if let Some(ex_trait_ref) = obj.principal() {
202 // Here, we are passing the type `usize` as a
203 // placeholder value with the function
204 // `with_self_ty`, since there is no concrete type
205 // `Self` for a `dyn Trait` at this
206 // stage. Therefore when checking explicit
207 // predicates in `check_explicit_predicates` we
208 // need to ignore checking the explicit_map for
211 ex_trait_ref.with_self_ty(tcx, tcx.types.usize).skip_binder().substs;
212 check_explicit_predicates(
214 ex_trait_ref.skip_binder().def_id,
218 Some(tcx.types.self_param),
223 ty::Projection(obj) => {
224 // This corresponds to `<T as Foo<'a>>::Bar`. In this case, we should use the
225 // explicit predicates as well.
226 debug!("Projection");
227 check_explicit_predicates(
229 tcx.associated_item(obj.item_def_id).container.id(),
242 /// We also have to check the explicit predicates
243 /// declared on the type.
245 /// struct Foo<'a, T> {
249 /// struct Bar<U> where U: 'static, U: Foo {
253 /// Here, we should fetch the explicit predicates, which
254 /// will give us `U: 'static` and `U: Foo`. The latter we
255 /// can ignore, but we will want to process `U: 'static`,
256 /// applying the substitution as above.
257 pub fn check_explicit_predicates<'tcx>(
260 substs: &[GenericArg<'tcx>],
261 required_predicates: &mut RequiredPredicates<'tcx>,
262 explicit_map: &mut ExplicitPredicatesMap<'tcx>,
263 ignored_self_ty: Option<Ty<'tcx>>,
266 "check_explicit_predicates(def_id={:?}, \
269 required_predicates={:?}, \
270 ignored_self_ty={:?})",
271 def_id, substs, explicit_map, required_predicates, ignored_self_ty,
273 let explicit_predicates = explicit_map.explicit_predicates_of(tcx, def_id);
275 for (outlives_predicate, &span) in explicit_predicates {
276 debug!("outlives_predicate = {:?}", &outlives_predicate);
278 // Careful: If we are inferring the effects of a `dyn Trait<..>`
279 // type, then when we look up the predicates for `Trait`,
280 // we may find some that reference `Self`. e.g., perhaps the
281 // definition of `Trait` was:
284 // trait Trait<'a, T> where Self: 'a { .. }
287 // we want to ignore such predicates here, because
288 // there is no type parameter for them to affect. Consider
289 // a struct containing `dyn Trait`:
292 // struct MyStruct<'x, X> { field: Box<dyn Trait<'x, X>> }
295 // The `where Self: 'a` predicate refers to the *existential, hidden type*
296 // that is represented by the `dyn Trait`, not to the `X` type parameter
297 // (or any other generic parameter) declared on `MyStruct`.
299 // Note that we do this check for self **before** applying `substs`. In the
300 // case that `substs` come from a `dyn Trait` type, our caller will have
301 // included `Self = usize` as the value for `Self`. If we were
302 // to apply the substs, and not filter this predicate, we might then falsely
303 // conclude that e.g., `X: 'x` was a reasonable inferred requirement.
305 // Another similar case is where we have a inferred
306 // requirement like `<Self as Trait>::Foo: 'b`. We presently
307 // ignore such requirements as well (cc #54467)-- though
308 // conceivably it might be better if we could extract the `Foo
309 // = X` binding from the object type (there must be such a
310 // binding) and thus infer an outlives requirement that `X:
312 if let Some(self_ty) = ignored_self_ty {
313 if let GenericArgKind::Type(ty) = outlives_predicate.0.unpack() {
314 if ty.walk().any(|arg| arg == self_ty.into()) {
315 debug!("skipping self ty = {:?}", &ty);
321 let predicate = outlives_predicate.subst(tcx, substs);
322 debug!("predicate = {:?}", &predicate);
323 insert_outlives_predicate(tcx, predicate.0, predicate.1, span, required_predicates);