]> git.lizzy.rs Git - rust.git/blob - compiler/rustc_typeck/src/outlives/implicit_infer.rs
Rollup merge of #79443 - GuillaumeGomez:improve-rustdoc-js-error-output, r=jyn514
[rust.git] / compiler / rustc_typeck / src / outlives / implicit_infer.rs
1 use rustc_data_structures::fx::FxHashMap;
2 use rustc_hir as hir;
3 use rustc_hir::def_id::DefId;
4 use rustc_hir::itemlikevisit::ItemLikeVisitor;
5 use rustc_hir::Node;
6 use rustc_middle::ty::subst::{GenericArg, GenericArgKind, Subst};
7 use rustc_middle::ty::{self, Ty, TyCtxt};
8 use rustc_span::Span;
9
10 use super::explicit::ExplicitPredicatesMap;
11 use super::utils::*;
12
13 /// Infer predicates for the items in the crate.
14 ///
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>(
19     tcx: TyCtxt<'tcx>,
20     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
21 ) -> FxHashMap<DefId, RequiredPredicates<'tcx>> {
22     debug!("infer_predicates");
23
24     let mut predicates_added = true;
25
26     let mut global_inferred_outlives = FxHashMap::default();
27
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;
32
33         let mut visitor = InferVisitor {
34             tcx,
35             global_inferred_outlives: &mut global_inferred_outlives,
36             predicates_added: &mut predicates_added,
37             explicit_map,
38         };
39
40         // Visit all the crates and infer predicates
41         tcx.hir().krate().visit_all_item_likes(&mut visitor);
42     }
43
44     global_inferred_outlives
45 }
46
47 pub struct InferVisitor<'cx, 'tcx> {
48     tcx: TyCtxt<'tcx>,
49     global_inferred_outlives: &'cx mut FxHashMap<DefId, RequiredPredicates<'tcx>>,
50     predicates_added: &'cx mut bool,
51     explicit_map: &'cx mut ExplicitPredicatesMap<'tcx>,
52 }
53
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);
57
58         debug!("InferVisitor::visit_item(item={:?})", item_did);
59
60         let hir_id = self.tcx.hir().local_def_id_to_hir_id(item_did);
61         let item = match self.tcx.hir().get(hir_id) {
62             Node::Item(item) => item,
63             _ => bug!(),
64         };
65
66         let mut item_required_predicates = RequiredPredicates::default();
67         match item.kind {
68             hir::ItemKind::Union(..) | hir::ItemKind::Enum(..) | hir::ItemKind::Struct(..) => {
69                 let adt_def = self.tcx.adt_def(item_did.to_def_id());
70
71                 // Iterate over all fields in item_did
72                 for field_def in adt_def.all_fields() {
73                     // Calculating the predicate requirements necessary
74                     // for item_did.
75                     //
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(
82                         self.tcx,
83                         field_ty,
84                         field_span,
85                         self.global_inferred_outlives,
86                         &mut item_required_predicates,
87                         &mut self.explicit_map,
88                     );
89                 }
90             }
91
92             _ => {}
93         };
94
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
100         // items.
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);
106         }
107     }
108
109     fn visit_trait_item(&mut self, _trait_item: &'tcx hir::TraitItem<'tcx>) {}
110
111     fn visit_impl_item(&mut self, _impl_item: &'tcx hir::ImplItem<'tcx>) {}
112
113     fn visit_foreign_item(&mut self, _foreign_item: &'tcx hir::ForeignItem<'tcx>) {}
114 }
115
116 fn insert_required_predicates_to_be_wf<'tcx>(
117     tcx: TyCtxt<'tcx>,
118     field_ty: Ty<'tcx>,
119     field_span: Span,
120     global_inferred_outlives: &FxHashMap<DefId, RequiredPredicates<'tcx>>,
121     required_predicates: &mut RequiredPredicates<'tcx>,
122     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
123 ) {
124     for arg in field_ty.walk() {
125         let ty = match arg.unpack() {
126             GenericArgKind::Type(ty) => ty,
127
128             // No predicates from lifetimes or constants, except potentially
129             // constants' types, but `walk` will get to them as well.
130             GenericArgKind::Lifetime(_) | GenericArgKind::Const(_) => continue,
131         };
132
133         match *ty.kind() {
134             // The field is of type &'a T which means that we will have
135             // a predicate requirement of T: 'a (T outlives 'a).
136             //
137             // We also want to calculate potential predicates for the T
138             ty::Ref(region, rty, _) => {
139                 debug!("Ref");
140                 insert_outlives_predicate(tcx, rty.into(), region, field_span, required_predicates);
141             }
142
143             // For each Adt (struct/enum/union) type `Foo<'a, T>`, we
144             // can load the current set of inferred and explicit
145             // predicates from `global_inferred_outlives` and filter the
146             // ones that are TypeOutlives.
147             ty::Adt(def, substs) => {
148                 // First check the inferred predicates
149                 //
150                 // Example 1:
151                 //
152                 //     struct Foo<'a, T> {
153                 //         field1: Bar<'a, T>
154                 //     }
155                 //
156                 //     struct Bar<'b, U> {
157                 //         field2: &'b U
158                 //     }
159                 //
160                 // Here, when processing the type of `field1`, we would
161                 // request the set of implicit predicates computed for `Bar`
162                 // thus far. This will initially come back empty, but in next
163                 // round we will get `U: 'b`. We then apply the substitution
164                 // `['b => 'a, U => T]` and thus get the requirement that `T:
165                 // 'a` holds for `Foo`.
166                 debug!("Adt");
167                 if let Some(unsubstituted_predicates) = global_inferred_outlives.get(&def.did) {
168                     for (unsubstituted_predicate, &span) in unsubstituted_predicates {
169                         // `unsubstituted_predicate` is `U: 'b` in the
170                         // example above.  So apply the substitution to
171                         // get `T: 'a` (or `predicate`):
172                         let predicate = unsubstituted_predicate.subst(tcx, substs);
173                         insert_outlives_predicate(
174                             tcx,
175                             predicate.0,
176                             predicate.1,
177                             span,
178                             required_predicates,
179                         );
180                     }
181                 }
182
183                 // Check if the type has any explicit predicates that need
184                 // to be added to `required_predicates`
185                 // let _: () = substs.region_at(0);
186                 check_explicit_predicates(
187                     tcx,
188                     def.did,
189                     substs,
190                     required_predicates,
191                     explicit_map,
192                     None,
193                 );
194             }
195
196             ty::Dynamic(obj, ..) => {
197                 // This corresponds to `dyn Trait<..>`. In this case, we should
198                 // use the explicit predicates as well.
199
200                 debug!("Dynamic");
201                 debug!("field_ty = {}", &field_ty);
202                 debug!("ty in field = {}", &ty);
203                 if let Some(ex_trait_ref) = obj.principal() {
204                     // Here, we are passing the type `usize` as a
205                     // placeholder value with the function
206                     // `with_self_ty`, since there is no concrete type
207                     // `Self` for a `dyn Trait` at this
208                     // stage. Therefore when checking explicit
209                     // predicates in `check_explicit_predicates` we
210                     // need to ignore checking the explicit_map for
211                     // Self type.
212                     let substs =
213                         ex_trait_ref.with_self_ty(tcx, tcx.types.usize).skip_binder().substs;
214                     check_explicit_predicates(
215                         tcx,
216                         ex_trait_ref.skip_binder().def_id,
217                         substs,
218                         required_predicates,
219                         explicit_map,
220                         Some(tcx.types.self_param),
221                     );
222                 }
223             }
224
225             ty::Projection(obj) => {
226                 // This corresponds to `<T as Foo<'a>>::Bar`. In this case, we should use the
227                 // explicit predicates as well.
228                 debug!("Projection");
229                 check_explicit_predicates(
230                     tcx,
231                     tcx.associated_item(obj.item_def_id).container.id(),
232                     obj.substs,
233                     required_predicates,
234                     explicit_map,
235                     None,
236                 );
237             }
238
239             _ => {}
240         }
241     }
242 }
243
244 /// We also have to check the explicit predicates
245 /// declared on the type.
246 ///
247 ///     struct Foo<'a, T> {
248 ///         field1: Bar<T>
249 ///     }
250 ///
251 ///     struct Bar<U> where U: 'static, U: Foo {
252 ///         ...
253 ///     }
254 ///
255 /// Here, we should fetch the explicit predicates, which
256 /// will give us `U: 'static` and `U: Foo`. The latter we
257 /// can ignore, but we will want to process `U: 'static`,
258 /// applying the substitution as above.
259 pub fn check_explicit_predicates<'tcx>(
260     tcx: TyCtxt<'tcx>,
261     def_id: DefId,
262     substs: &[GenericArg<'tcx>],
263     required_predicates: &mut RequiredPredicates<'tcx>,
264     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
265     ignored_self_ty: Option<Ty<'tcx>>,
266 ) {
267     debug!(
268         "check_explicit_predicates(def_id={:?}, \
269          substs={:?}, \
270          explicit_map={:?}, \
271          required_predicates={:?}, \
272          ignored_self_ty={:?})",
273         def_id, substs, explicit_map, required_predicates, ignored_self_ty,
274     );
275     let explicit_predicates = explicit_map.explicit_predicates_of(tcx, def_id);
276
277     for (outlives_predicate, &span) in explicit_predicates {
278         debug!("outlives_predicate = {:?}", &outlives_predicate);
279
280         // Careful: If we are inferring the effects of a `dyn Trait<..>`
281         // type, then when we look up the predicates for `Trait`,
282         // we may find some that reference `Self`. e.g., perhaps the
283         // definition of `Trait` was:
284         //
285         // ```
286         // trait Trait<'a, T> where Self: 'a  { .. }
287         // ```
288         //
289         // we want to ignore such predicates here, because
290         // there is no type parameter for them to affect. Consider
291         // a struct containing `dyn Trait`:
292         //
293         // ```
294         // struct MyStruct<'x, X> { field: Box<dyn Trait<'x, X>> }
295         // ```
296         //
297         // The `where Self: 'a` predicate refers to the *existential, hidden type*
298         // that is represented by the `dyn Trait`, not to the `X` type parameter
299         // (or any other generic parameter) declared on `MyStruct`.
300         //
301         // Note that we do this check for self **before** applying `substs`. In the
302         // case that `substs` come from a `dyn Trait` type, our caller will have
303         // included `Self = usize` as the value for `Self`. If we were
304         // to apply the substs, and not filter this predicate, we might then falsely
305         // conclude that e.g., `X: 'x` was a reasonable inferred requirement.
306         //
307         // Another similar case is where we have a inferred
308         // requirement like `<Self as Trait>::Foo: 'b`. We presently
309         // ignore such requirements as well (cc #54467)-- though
310         // conceivably it might be better if we could extract the `Foo
311         // = X` binding from the object type (there must be such a
312         // binding) and thus infer an outlives requirement that `X:
313         // 'b`.
314         if let Some(self_ty) = ignored_self_ty {
315             if let GenericArgKind::Type(ty) = outlives_predicate.0.unpack() {
316                 if ty.walk().any(|arg| arg == self_ty.into()) {
317                     debug!("skipping self ty = {:?}", &ty);
318                     continue;
319                 }
320             }
321         }
322
323         let predicate = outlives_predicate.subst(tcx, substs);
324         debug!("predicate = {:?}", &predicate);
325         insert_outlives_predicate(tcx, predicate.0, predicate.1, span, required_predicates);
326     }
327 }