compiler/rustc_typeck/src/outlives/implicit_infer.rs

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