src/librustc_typeck/outlives/implicit_infer.rs

   1 use rustc::hir::{self, Node};
   2 use rustc::hir::def_id::DefId;
   3 use rustc::hir::itemlikevisit::ItemLikeVisitor;
   4 use rustc::ty::subst::{GenericArg, Subst, GenericArgKind};
   5 use rustc::ty::{self, Ty, TyCtxt};
   6 use rustc::util::nodemap::FxHashMap;
   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         let mut visitor = InferVisitor {
  32             tcx: tcx,
  33             global_inferred_outlives: &mut global_inferred_outlives,
  34             predicates_added: &mut predicates_added,
  35             explicit_map: explicit_map,
  36         };
  37
  38         // Visit all the crates and infer predicates
  39         tcx.hir().krate().visit_all_item_likes(&mut visitor);
  40     }
  41
  42     global_inferred_outlives
  43 }
  44
  45 pub struct InferVisitor<'cx, 'tcx> {
  46     tcx: TyCtxt<'tcx>,
  47     global_inferred_outlives: &'cx mut FxHashMap<DefId, RequiredPredicates<'tcx>>,
  48     predicates_added: &'cx mut bool,
  49     explicit_map: &'cx mut ExplicitPredicatesMap<'tcx>,
  50 }
  51
  52 impl<'cx, 'tcx> ItemLikeVisitor<'tcx> for InferVisitor<'cx, 'tcx> {
  53     fn visit_item(&mut self, item: &hir::Item) {
  54         let item_did = self.tcx.hir().local_def_id(item.hir_id);
  55
  56         debug!("InferVisitor::visit_item(item={:?})", item_did);
  57
  58         let hir_id = self
  59             .tcx
  60             .hir()
  61             .as_local_hir_id(item_did)
  62             .expect("expected local def-id");
  63         let item = match self.tcx.hir().get(hir_id) {
  64             Node::Item(item) => item,
  65             _ => bug!(),
  66         };
  67
  68         let mut item_required_predicates = RequiredPredicates::default();
  69         match item.node {
  70             hir::ItemKind::Union(..) | hir::ItemKind::Enum(..) | hir::ItemKind::Struct(..) => {
  71                 let adt_def = self.tcx.adt_def(item_did);
  72
  73                 // Iterate over all fields in item_did
  74                 for field_def in adt_def.all_fields() {
  75                     // Calculating the predicate requirements necessary
  76                     // for item_did.
  77                     //
  78                     // For field of type &'a T (reference) or Adt
  79                     // (struct/enum/union) there will be outlive
  80                     // requirements for adt_def.
  81                     let field_ty = self.tcx.type_of(field_def.did);
  82                     insert_required_predicates_to_be_wf(
  83                         self.tcx,
  84                         field_ty,
  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 = self
 102             .global_inferred_outlives
 103             .get(&item_did)
 104             .map(|p| p.len())
 105             .unwrap_or(0);
 106         if item_required_predicates.len() > item_predicates_len {
 107             *self.predicates_added = true;
 108             self.global_inferred_outlives
 109                 .insert(item_did, item_required_predicates);
 110         }
 111     }
 112
 113     fn visit_trait_item(&mut self, _trait_item: &'tcx hir::TraitItem) {}
 114
 115     fn visit_impl_item(&mut self, _impl_item: &'tcx hir::ImplItem) {}
 116 }
 117
 118 fn insert_required_predicates_to_be_wf<'tcx>(
 119     tcx: TyCtxt<'tcx>,
 120     field_ty: Ty<'tcx>,
 121     global_inferred_outlives: &FxHashMap<DefId, RequiredPredicates<'tcx>>,
 122     required_predicates: &mut RequiredPredicates<'tcx>,
 123     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
 124 ) {
 125     for ty in field_ty.walk() {
 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, 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 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                             required_predicates,
 171                         );
 172                     }
 173                 }
 174
 175                 // Check if the type has any explicit predicates that need
 176                 // to be added to `required_predicates`
 177                 // let _: () = substs.region_at(0);
 178                 check_explicit_predicates(
 179                     tcx,
 180                     def.did,
 181                     substs,
 182                     required_predicates,
 183                     explicit_map,
 184                     None,
 185                 );
 186             }
 187
 188             ty::Dynamic(obj, ..) => {
 189                 // This corresponds to `dyn Trait<..>`. In this case, we should
 190                 // use the explicit predicates as well.
 191
 192                 debug!("Dynamic");
 193                 debug!("field_ty = {}", &field_ty);
 194                 debug!("ty in field = {}", &ty);
 195                 if let Some(ex_trait_ref) = obj.principal() {
 196                     // Here, we are passing the type `usize` as a
 197                     // placeholder value with the function
 198                     // `with_self_ty`, since there is no concrete type
 199                     // `Self` for a `dyn Trait` at this
 200                     // stage. Therefore when checking explicit
 201                     // predicates in `check_explicit_predicates` we
 202                     // need to ignore checking the explicit_map for
 203                     // Self type.
 204                     let substs = ex_trait_ref
 205                         .with_self_ty(tcx, tcx.types.usize)
 206                         .skip_binder()
 207                         .substs;
 208                     check_explicit_predicates(
 209                         tcx,
 210                         ex_trait_ref.skip_binder().def_id,
 211                         substs,
 212                         required_predicates,
 213                         explicit_map,
 214                         Some(tcx.types.self_param),
 215                     );
 216                 }
 217             }
 218
 219             ty::Projection(obj) => {
 220                 // This corresponds to `<T as Foo<'a>>::Bar`. In this case, we should use the
 221                 // explicit predicates as well.
 222                 debug!("Projection");
 223                 check_explicit_predicates(
 224                     tcx,
 225                     tcx.associated_item(obj.item_def_id).container.id(),
 226                     obj.substs,
 227                     required_predicates,
 228                     explicit_map,
 229                     None,
 230                 );
 231             }
 232
 233             _ => {}
 234         }
 235     }
 236 }
 237
 238 /// We also have to check the explicit predicates
 239 /// declared on the type.
 240 ///
 241 ///     struct Foo<'a, T> {
 242 ///         field1: Bar<T>
 243 ///     }
 244 ///
 245 ///     struct Bar<U> where U: 'static, U: Foo {
 246 ///         ...
 247 ///     }
 248 ///
 249 /// Here, we should fetch the explicit predicates, which
 250 /// will give us `U: 'static` and `U: Foo`. The latter we
 251 /// can ignore, but we will want to process `U: 'static`,
 252 /// applying the substitution as above.
 253 pub fn check_explicit_predicates<'tcx>(
 254     tcx: TyCtxt<'tcx>,
 255     def_id: DefId,
 256     substs: &[GenericArg<'tcx>],
 257     required_predicates: &mut RequiredPredicates<'tcx>,
 258     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
 259     ignored_self_ty: Option<Ty<'tcx>>,
 260 ) {
 261     debug!(
 262         "check_explicit_predicates(def_id={:?}, \
 263          substs={:?}, \
 264          explicit_map={:?}, \
 265          required_predicates={:?}, \
 266          ignored_self_ty={:?})",
 267         def_id,
 268         substs,
 269         explicit_map,
 270         required_predicates,
 271         ignored_self_ty,
 272     );
 273     let explicit_predicates = explicit_map.explicit_predicates_of(tcx, def_id);
 274
 275     for outlives_predicate in explicit_predicates.iter() {
 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(|ty| ty == self_ty) {
 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.into(), predicate.1, required_predicates);
 324     }
 325 }