src/librustc_typeck/outlives/implicit_infer.rs

   1 use rustc::ty::subst::{GenericArg, GenericArgKind, Subst};
   2 use rustc::ty::{self, Ty, TyCtxt};
   3 use rustc_data_structures::fx::FxHashMap;
   4 use rustc_hir as hir;
   5 use rustc_hir::def_id::DefId;
   6 use rustc_hir::itemlikevisit::ItemLikeVisitor;
   7 use rustc_hir::Node;
   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: tcx,
  35             global_inferred_outlives: &mut global_inferred_outlives,
  36             predicates_added: &mut predicates_added,
  37             explicit_map: 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().as_local_hir_id(item_did).expect("expected local def-id");
  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);
  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).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, 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 ty in field_ty.walk() {
 123         match ty.kind {
 124             // The field is of type &'a T which means that we will have
 125             // a predicate requirement of T: 'a (T outlives 'a).
 126             //
 127             // We also want to calculate potential predicates for the T
 128             ty::Ref(region, rty, _) => {
 129                 debug!("Ref");
 130                 insert_outlives_predicate(tcx, rty.into(), region, field_span, required_predicates);
 131             }
 132
 133             // For each Adt (struct/enum/union) type `Foo<'a, T>`, we
 134             // can load the current set of inferred and explicit
 135             // predicates from `global_inferred_outlives` and filter the
 136             // ones that are TypeOutlives.
 137             ty::Adt(def, substs) => {
 138                 // First check the inferred predicates
 139                 //
 140                 // Example 1:
 141                 //
 142                 //     struct Foo<'a, T> {
 143                 //         field1: Bar<'a, T>
 144                 //     }
 145                 //
 146                 //     struct Bar<'b, U> {
 147                 //         field2: &'b U
 148                 //     }
 149                 //
 150                 // Here, when processing the type of `field1`, we would
 151                 // request the set of implicit predicates computed for `Bar`
 152                 // thus far. This will initially come back empty, but in next
 153                 // round we will get `U: 'b`. We then apply the substitution
 154                 // `['b => 'a, U => T]` and thus get the requirement that `T:
 155                 // 'a` holds for `Foo`.
 156                 debug!("Adt");
 157                 if let Some(unsubstituted_predicates) = global_inferred_outlives.get(&def.did) {
 158                     for (unsubstituted_predicate, &span) in unsubstituted_predicates {
 159                         // `unsubstituted_predicate` is `U: 'b` in the
 160                         // example above.  So apply the substitution to
 161                         // get `T: 'a` (or `predicate`):
 162                         let predicate = unsubstituted_predicate.subst(tcx, substs);
 163                         insert_outlives_predicate(
 164                             tcx,
 165                             predicate.0,
 166                             predicate.1,
 167                             span,
 168                             required_predicates,
 169                         );
 170                     }
 171                 }
 172
 173                 // Check if the type has any explicit predicates that need
 174                 // to be added to `required_predicates`
 175                 // let _: () = substs.region_at(0);
 176                 check_explicit_predicates(
 177                     tcx,
 178                     def.did,
 179                     substs,
 180                     required_predicates,
 181                     explicit_map,
 182                     None,
 183                 );
 184             }
 185
 186             ty::Dynamic(obj, ..) => {
 187                 // This corresponds to `dyn Trait<..>`. In this case, we should
 188                 // use the explicit predicates as well.
 189
 190                 debug!("Dynamic");
 191                 debug!("field_ty = {}", &field_ty);
 192                 debug!("ty in field = {}", &ty);
 193                 if let Some(ex_trait_ref) = obj.principal() {
 194                     // Here, we are passing the type `usize` as a
 195                     // placeholder value with the function
 196                     // `with_self_ty`, since there is no concrete type
 197                     // `Self` for a `dyn Trait` at this
 198                     // stage. Therefore when checking explicit
 199                     // predicates in `check_explicit_predicates` we
 200                     // need to ignore checking the explicit_map for
 201                     // Self type.
 202                     let substs =
 203                         ex_trait_ref.with_self_ty(tcx, tcx.types.usize).skip_binder().substs;
 204                     check_explicit_predicates(
 205                         tcx,
 206                         ex_trait_ref.skip_binder().def_id,
 207                         substs,
 208                         required_predicates,
 209                         explicit_map,
 210                         Some(tcx.types.self_param),
 211                     );
 212                 }
 213             }
 214
 215             ty::Projection(obj) => {
 216                 // This corresponds to `<T as Foo<'a>>::Bar`. In this case, we should use the
 217                 // explicit predicates as well.
 218                 debug!("Projection");
 219                 check_explicit_predicates(
 220                     tcx,
 221                     tcx.associated_item(obj.item_def_id).container.id(),
 222                     obj.substs,
 223                     required_predicates,
 224                     explicit_map,
 225                     None,
 226                 );
 227             }
 228
 229             _ => {}
 230         }
 231     }
 232 }
 233
 234 /// We also have to check the explicit predicates
 235 /// declared on the type.
 236 ///
 237 ///     struct Foo<'a, T> {
 238 ///         field1: Bar<T>
 239 ///     }
 240 ///
 241 ///     struct Bar<U> where U: 'static, U: Foo {
 242 ///         ...
 243 ///     }
 244 ///
 245 /// Here, we should fetch the explicit predicates, which
 246 /// will give us `U: 'static` and `U: Foo`. The latter we
 247 /// can ignore, but we will want to process `U: 'static`,
 248 /// applying the substitution as above.
 249 pub fn check_explicit_predicates<'tcx>(
 250     tcx: TyCtxt<'tcx>,
 251     def_id: DefId,
 252     substs: &[GenericArg<'tcx>],
 253     required_predicates: &mut RequiredPredicates<'tcx>,
 254     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
 255     ignored_self_ty: Option<Ty<'tcx>>,
 256 ) {
 257     debug!(
 258         "check_explicit_predicates(def_id={:?}, \
 259          substs={:?}, \
 260          explicit_map={:?}, \
 261          required_predicates={:?}, \
 262          ignored_self_ty={:?})",
 263         def_id, substs, explicit_map, required_predicates, ignored_self_ty,
 264     );
 265     let explicit_predicates = explicit_map.explicit_predicates_of(tcx, def_id);
 266
 267     for (outlives_predicate, &span) in explicit_predicates {
 268         debug!("outlives_predicate = {:?}", &outlives_predicate);
 269
 270         // Careful: If we are inferring the effects of a `dyn Trait<..>`
 271         // type, then when we look up the predicates for `Trait`,
 272         // we may find some that reference `Self`. e.g., perhaps the
 273         // definition of `Trait` was:
 274         //
 275         // ```
 276         // trait Trait<'a, T> where Self: 'a  { .. }
 277         // ```
 278         //
 279         // we want to ignore such predicates here, because
 280         // there is no type parameter for them to affect. Consider
 281         // a struct containing `dyn Trait`:
 282         //
 283         // ```
 284         // struct MyStruct<'x, X> { field: Box<dyn Trait<'x, X>> }
 285         // ```
 286         //
 287         // The `where Self: 'a` predicate refers to the *existential, hidden type*
 288         // that is represented by the `dyn Trait`, not to the `X` type parameter
 289         // (or any other generic parameter) declared on `MyStruct`.
 290         //
 291         // Note that we do this check for self **before** applying `substs`. In the
 292         // case that `substs` come from a `dyn Trait` type, our caller will have
 293         // included `Self = usize` as the value for `Self`. If we were
 294         // to apply the substs, and not filter this predicate, we might then falsely
 295         // conclude that e.g., `X: 'x` was a reasonable inferred requirement.
 296         //
 297         // Another similar case is where we have a inferred
 298         // requirement like `<Self as Trait>::Foo: 'b`. We presently
 299         // ignore such requirements as well (cc #54467)-- though
 300         // conceivably it might be better if we could extract the `Foo
 301         // = X` binding from the object type (there must be such a
 302         // binding) and thus infer an outlives requirement that `X:
 303         // 'b`.
 304         if let Some(self_ty) = ignored_self_ty {
 305             if let GenericArgKind::Type(ty) = outlives_predicate.0.unpack() {
 306                 if ty.walk().any(|ty| ty == self_ty) {
 307                     debug!("skipping self ty = {:?}", &ty);
 308                     continue;
 309                 }
 310             }
 311         }
 312
 313         let predicate = outlives_predicate.subst(tcx, substs);
 314         debug!("predicate = {:?}", &predicate);
 315         insert_outlives_predicate(tcx, predicate.0.into(), predicate.1, span, required_predicates);
 316     }
 317 }