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_middle::ty::subst::{GenericArg, GenericArgKind, Subst};
   6 use rustc_middle::ty::{self, Ty, TyCtxt};
   7 use rustc_span::Span;
   8
   9 use super::explicit::ExplicitPredicatesMap;
  10 use super::utils::*;
  11
  12 /// Infer predicates for the items in the crate.
  13 ///
  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>(
  18     tcx: TyCtxt<'tcx>,
  19     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
  20 ) -> FxHashMap<DefId, RequiredPredicates<'tcx>> {
  21     debug!("infer_predicates");
  22
  23     let mut predicates_added = true;
  24
  25     let mut global_inferred_outlives = FxHashMap::default();
  26
  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;
  31
  32         let mut visitor = InferVisitor {
  33             tcx,
  34             global_inferred_outlives: &mut global_inferred_outlives,
  35             predicates_added: &mut predicates_added,
  36             explicit_map,
  37         };
  38
  39         // Visit all the crates and infer predicates
  40         tcx.hir().visit_all_item_likes(&mut visitor);
  41     }
  42
  43     global_inferred_outlives
  44 }
  45
  46 pub struct InferVisitor<'cx, 'tcx> {
  47     tcx: TyCtxt<'tcx>,
  48     global_inferred_outlives: &'cx mut FxHashMap<DefId, RequiredPredicates<'tcx>>,
  49     predicates_added: &'cx mut bool,
  50     explicit_map: &'cx mut ExplicitPredicatesMap<'tcx>,
  51 }
  52
  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;
  56
  57         debug!("InferVisitor::visit_item(item={:?})", item_did);
  58
  59         let mut item_required_predicates = RequiredPredicates::default();
  60         match item.kind {
  61             hir::ItemKind::Union(..) | hir::ItemKind::Enum(..) | hir::ItemKind::Struct(..) => {
  62                 let adt_def = self.tcx.adt_def(item_did.to_def_id());
  63
  64                 // Iterate over all fields in item_did
  65                 for field_def in adt_def.all_fields() {
  66                     // Calculating the predicate requirements necessary
  67                     // for item_did.
  68                     //
  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(
  75                         self.tcx,
  76                         field_ty,
  77                         field_span,
  78                         self.global_inferred_outlives,
  79                         &mut item_required_predicates,
  80                         &mut self.explicit_map,
  81                     );
  82                 }
  83             }
  84
  85             _ => {}
  86         };
  87
  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
  93         // items.
  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);
  99         }
 100     }
 101
 102     fn visit_trait_item(&mut self, _trait_item: &'tcx hir::TraitItem<'tcx>) {}
 103
 104     fn visit_impl_item(&mut self, _impl_item: &'tcx hir::ImplItem<'tcx>) {}
 105
 106     fn visit_foreign_item(&mut self, _foreign_item: &'tcx hir::ForeignItem<'tcx>) {}
 107 }
 108
 109 fn insert_required_predicates_to_be_wf<'tcx>(
 110     tcx: TyCtxt<'tcx>,
 111     field_ty: Ty<'tcx>,
 112     field_span: Span,
 113     global_inferred_outlives: &FxHashMap<DefId, RequiredPredicates<'tcx>>,
 114     required_predicates: &mut RequiredPredicates<'tcx>,
 115     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
 116 ) {
 117     for arg in field_ty.walk() {
 118         let ty = match arg.unpack() {
 119             GenericArgKind::Type(ty) => ty,
 120
 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,
 124         };
 125
 126         match *ty.kind() {
 127             // The field is of type &'a T which means that we will have
 128             // a predicate requirement of T: 'a (T outlives 'a).
 129             //
 130             // We also want to calculate potential predicates for the T
 131             ty::Ref(region, rty, _) => {
 132                 debug!("Ref");
 133                 insert_outlives_predicate(tcx, rty.into(), region, field_span, required_predicates);
 134             }
 135
 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
 142                 //
 143                 // Example 1:
 144                 //
 145                 //     struct Foo<'a, T> {
 146                 //         field1: Bar<'a, T>
 147                 //     }
 148                 //
 149                 //     struct Bar<'b, U> {
 150                 //         field2: &'b U
 151                 //     }
 152                 //
 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`.
 159                 debug!("Adt");
 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(
 167                             tcx,
 168                             predicate.0,
 169                             predicate.1,
 170                             span,
 171                             required_predicates,
 172                         );
 173                     }
 174                 }
 175
 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(
 180                     tcx,
 181                     def.did(),
 182                     substs,
 183                     required_predicates,
 184                     explicit_map,
 185                     None,
 186                 );
 187             }
 188
 189             ty::Dynamic(obj, ..) => {
 190                 // This corresponds to `dyn Trait<..>`. In this case, we should
 191                 // use the explicit predicates as well.
 192
 193                 debug!("Dynamic");
 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
 204                     // Self type.
 205                     let substs =
 206                         ex_trait_ref.with_self_ty(tcx, tcx.types.usize).skip_binder().substs;
 207                     check_explicit_predicates(
 208                         tcx,
 209                         ex_trait_ref.skip_binder().def_id,
 210                         substs,
 211                         required_predicates,
 212                         explicit_map,
 213                         Some(tcx.types.self_param),
 214                     );
 215                 }
 216             }
 217
 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(
 223                     tcx,
 224                     tcx.associated_item(obj.item_def_id).container.id(),
 225                     obj.substs,
 226                     required_predicates,
 227                     explicit_map,
 228                     None,
 229                 );
 230             }
 231
 232             _ => {}
 233         }
 234     }
 235 }
 236
 237 /// We also have to check the explicit predicates
 238 /// declared on the type.
 239 ///
 240 ///     struct Foo<'a, T> {
 241 ///         field1: Bar<T>
 242 ///     }
 243 ///
 244 ///     struct Bar<U> where U: 'static, U: Foo {
 245 ///         ...
 246 ///     }
 247 ///
 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>(
 253     tcx: TyCtxt<'tcx>,
 254     def_id: DefId,
 255     substs: &[GenericArg<'tcx>],
 256     required_predicates: &mut RequiredPredicates<'tcx>,
 257     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
 258     ignored_self_ty: Option<Ty<'tcx>>,
 259 ) {
 260     debug!(
 261         "check_explicit_predicates(def_id={:?}, \
 262          substs={:?}, \
 263          explicit_map={:?}, \
 264          required_predicates={:?}, \
 265          ignored_self_ty={:?})",
 266         def_id, substs, explicit_map, required_predicates, ignored_self_ty,
 267     );
 268     let explicit_predicates = explicit_map.explicit_predicates_of(tcx, def_id);
 269
 270     for (outlives_predicate, &span) in explicit_predicates {
 271         debug!("outlives_predicate = {:?}", &outlives_predicate);
 272
 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:
 277         //
 278         // ```
 279         // trait Trait<'a, T> where Self: 'a  { .. }
 280         // ```
 281         //
 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`:
 285         //
 286         // ```
 287         // struct MyStruct<'x, X> { field: Box<dyn Trait<'x, X>> }
 288         // ```
 289         //
 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`.
 293         //
 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.
 299         //
 300         // Another similar case is where we have an 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:
 306         // 'b`.
 307         if let Some(self_ty) = ignored_self_ty
 308             && let GenericArgKind::Type(ty) = outlives_predicate.0.unpack()
 309             && ty.walk().any(|arg| arg == self_ty.into())
 310         {
 311             debug!("skipping self ty = {:?}", &ty);
 312             continue;
 313         }
 314
 315         let predicate = outlives_predicate.subst(tcx, substs);
 316         debug!("predicate = {:?}", &predicate);
 317         insert_outlives_predicate(tcx, predicate.0, predicate.1, span, required_predicates);
 318     }
 319 }