src/librustc_typeck/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
 114 fn insert_required_predicates_to_be_wf<'tcx>(
 115     tcx: TyCtxt<'tcx>,
 116     field_ty: Ty<'tcx>,
 117     field_span: Span,
 118     global_inferred_outlives: &FxHashMap<DefId, RequiredPredicates<'tcx>>,
 119     required_predicates: &mut RequiredPredicates<'tcx>,
 120     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
 121 ) {
 122     for arg in field_ty.walk() {
 123         let ty = match arg.unpack() {
 124             GenericArgKind::Type(ty) => ty,
 125
 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,
 129         };
 130
 131         match ty.kind {
 132             // The field is of type &'a T which means that we will have
 133             // a predicate requirement of T: 'a (T outlives 'a).
 134             //
 135             // We also want to calculate potential predicates for the T
 136             ty::Ref(region, rty, _) => {
 137                 debug!("Ref");
 138                 insert_outlives_predicate(tcx, rty.into(), region, field_span, required_predicates);
 139             }
 140
 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
 147                 //
 148                 // Example 1:
 149                 //
 150                 //     struct Foo<'a, T> {
 151                 //         field1: Bar<'a, T>
 152                 //     }
 153                 //
 154                 //     struct Bar<'b, U> {
 155                 //         field2: &'b U
 156                 //     }
 157                 //
 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`.
 164                 debug!("Adt");
 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(
 172                             tcx,
 173                             predicate.0,
 174                             predicate.1,
 175                             span,
 176                             required_predicates,
 177                         );
 178                     }
 179                 }
 180
 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(
 185                     tcx,
 186                     def.did,
 187                     substs,
 188                     required_predicates,
 189                     explicit_map,
 190                     None,
 191                 );
 192             }
 193
 194             ty::Dynamic(obj, ..) => {
 195                 // This corresponds to `dyn Trait<..>`. In this case, we should
 196                 // use the explicit predicates as well.
 197
 198                 debug!("Dynamic");
 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
 209                     // Self type.
 210                     let substs =
 211                         ex_trait_ref.with_self_ty(tcx, tcx.types.usize).skip_binder().substs;
 212                     check_explicit_predicates(
 213                         tcx,
 214                         ex_trait_ref.skip_binder().def_id,
 215                         substs,
 216                         required_predicates,
 217                         explicit_map,
 218                         Some(tcx.types.self_param),
 219                     );
 220                 }
 221             }
 222
 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(
 228                     tcx,
 229                     tcx.associated_item(obj.item_def_id).container.id(),
 230                     obj.substs,
 231                     required_predicates,
 232                     explicit_map,
 233                     None,
 234                 );
 235             }
 236
 237             _ => {}
 238         }
 239     }
 240 }
 241
 242 /// We also have to check the explicit predicates
 243 /// declared on the type.
 244 ///
 245 ///     struct Foo<'a, T> {
 246 ///         field1: Bar<T>
 247 ///     }
 248 ///
 249 ///     struct Bar<U> where U: 'static, U: Foo {
 250 ///         ...
 251 ///     }
 252 ///
 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>(
 258     tcx: TyCtxt<'tcx>,
 259     def_id: DefId,
 260     substs: &[GenericArg<'tcx>],
 261     required_predicates: &mut RequiredPredicates<'tcx>,
 262     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
 263     ignored_self_ty: Option<Ty<'tcx>>,
 264 ) {
 265     debug!(
 266         "check_explicit_predicates(def_id={:?}, \
 267          substs={:?}, \
 268          explicit_map={:?}, \
 269          required_predicates={:?}, \
 270          ignored_self_ty={:?})",
 271         def_id, substs, explicit_map, required_predicates, ignored_self_ty,
 272     );
 273     let explicit_predicates = explicit_map.explicit_predicates_of(tcx, def_id);
 274
 275     for (outlives_predicate, &span) in explicit_predicates {
 276         debug!("outlives_predicate = {:?}", &outlives_predicate);
 277
 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:
 282         //
 283         // ```
 284         // trait Trait<'a, T> where Self: 'a  { .. }
 285         // ```
 286         //
 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`:
 290         //
 291         // ```
 292         // struct MyStruct<'x, X> { field: Box<dyn Trait<'x, X>> }
 293         // ```
 294         //
 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`.
 298         //
 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.
 304         //
 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:
 311         // 'b`.
 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);
 316                     continue;
 317                 }
 318             }
 319         }
 320
 321         let predicate = outlives_predicate.subst(tcx, substs);
 322         debug!("predicate = {:?}", &predicate);
 323         insert_outlives_predicate(tcx, predicate.0, predicate.1, span, required_predicates);
 324     }
 325 }