compiler/rustc_hir_analysis/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::{self, DefIdTree, Ty, TyCtxt};
   5 use rustc_middle::ty::{GenericArg, GenericArgKind};
   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(super) fn infer_predicates(
  17     tcx: TyCtxt<'_>,
  18 ) -> FxHashMap<DefId, ty::EarlyBinder<RequiredPredicates<'_>>> {
  19     debug!("infer_predicates");
  20
  21     let mut explicit_map = ExplicitPredicatesMap::new();
  22
  23     let mut global_inferred_outlives = FxHashMap::default();
  24
  25     // If new predicates were added then we need to re-calculate
  26     // all crates since there could be new implied predicates.
  27     'outer: loop {
  28         let mut predicates_added = false;
  29
  30         // Visit all the crates and infer predicates
  31         for id in tcx.hir().items() {
  32             let item_did = id.owner_id;
  33
  34             debug!("InferVisitor::visit_item(item={:?})", item_did);
  35
  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());
  40
  41                     // Iterate over all fields in item_did
  42                     for field_def in adt_def.all_fields() {
  43                         // Calculating the predicate requirements necessary
  44                         // for item_did.
  45                         //
  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(
  52                             tcx,
  53                             field_ty,
  54                             field_span,
  55                             &global_inferred_outlives,
  56                             &mut item_required_predicates,
  57                             &mut explicit_map,
  58                         );
  59                     }
  60                 }
  61
  62                 _ => {}
  63             };
  64
  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
  70             // items.
  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));
  77             }
  78         }
  79
  80         if !predicates_added {
  81             break 'outer;
  82         }
  83     }
  84
  85     global_inferred_outlives
  86 }
  87
  88 fn insert_required_predicates_to_be_wf<'tcx>(
  89     tcx: TyCtxt<'tcx>,
  90     field_ty: Ty<'tcx>,
  91     field_span: Span,
  92     global_inferred_outlives: &FxHashMap<DefId, ty::EarlyBinder<RequiredPredicates<'tcx>>>,
  93     required_predicates: &mut RequiredPredicates<'tcx>,
  94     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
  95 ) {
  96     for arg in field_ty.walk() {
  97         let ty = match arg.unpack() {
  98             GenericArgKind::Type(ty) => ty,
  99
 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,
 103         };
 104
 105         match *ty.kind() {
 106             // The field is of type &'a T which means that we will have
 107             // a predicate requirement of T: 'a (T outlives 'a).
 108             //
 109             // We also want to calculate potential predicates for the T
 110             ty::Ref(region, rty, _) => {
 111                 debug!("Ref");
 112                 insert_outlives_predicate(tcx, rty.into(), region, field_span, required_predicates);
 113             }
 114
 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
 121                 //
 122                 // Example 1:
 123                 //
 124                 //     struct Foo<'a, T> {
 125                 //         field1: Bar<'a, T>
 126                 //     }
 127                 //
 128                 //     struct Bar<'b, U> {
 129                 //         field2: &'b U
 130                 //     }
 131                 //
 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`.
 138                 debug!("Adt");
 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)
 146                             .subst(tcx, substs);
 147                         insert_outlives_predicate(
 148                             tcx,
 149                             predicate.0,
 150                             predicate.1,
 151                             span,
 152                             required_predicates,
 153                         );
 154                     }
 155                 }
 156
 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(
 161                     tcx,
 162                     def.did(),
 163                     substs,
 164                     required_predicates,
 165                     explicit_map,
 166                     None,
 167                 );
 168             }
 169
 170             ty::Dynamic(obj, ..) => {
 171                 // This corresponds to `dyn Trait<..>`. In this case, we should
 172                 // use the explicit predicates as well.
 173
 174                 debug!("Dynamic");
 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
 185                     // Self type.
 186                     let substs =
 187                         ex_trait_ref.with_self_ty(tcx, tcx.types.usize).skip_binder().substs;
 188                     check_explicit_predicates(
 189                         tcx,
 190                         ex_trait_ref.skip_binder().def_id,
 191                         substs,
 192                         required_predicates,
 193                         explicit_map,
 194                         Some(tcx.types.self_param),
 195                     );
 196                 }
 197             }
 198
 199             ty::Alias(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(
 204                     tcx,
 205                     tcx.parent(obj.def_id),
 206                     obj.substs,
 207                     required_predicates,
 208                     explicit_map,
 209                     None,
 210                 );
 211             }
 212
 213             _ => {}
 214         }
 215     }
 216 }
 217
 218 /// We also have to check the explicit predicates
 219 /// declared on the type.
 220 /// ```ignore (illustrative)
 221 /// struct Foo<'a, T> {
 222 ///     field1: Bar<T>
 223 /// }
 224 ///
 225 /// struct Bar<U> where U: 'static, U: Foo {
 226 ///     ...
 227 /// }
 228 /// ```
 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>(
 234     tcx: TyCtxt<'tcx>,
 235     def_id: DefId,
 236     substs: &[GenericArg<'tcx>],
 237     required_predicates: &mut RequiredPredicates<'tcx>,
 238     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
 239     ignored_self_ty: Option<Ty<'tcx>>,
 240 ) {
 241     debug!(
 242         "check_explicit_predicates(def_id={:?}, \
 243          substs={:?}, \
 244          explicit_map={:?}, \
 245          required_predicates={:?}, \
 246          ignored_self_ty={:?})",
 247         def_id, substs, explicit_map, required_predicates, ignored_self_ty,
 248     );
 249     let explicit_predicates = explicit_map.explicit_predicates_of(tcx, def_id);
 250
 251     for (outlives_predicate, &span) in &explicit_predicates.0 {
 252         debug!("outlives_predicate = {:?}", &outlives_predicate);
 253
 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:
 258         //
 259         // ```
 260         // trait Trait<'a, T> where Self: 'a  { .. }
 261         // ```
 262         //
 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`:
 266         //
 267         // ```
 268         // struct MyStruct<'x, X> { field: Box<dyn Trait<'x, X>> }
 269         // ```
 270         //
 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`.
 274         //
 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.
 280         //
 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:
 287         // 'b`.
 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())
 291         {
 292             debug!("skipping self ty = {:?}", &ty);
 293             continue;
 294         }
 295
 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);
 299     }
 300 }