src/librustc_typeck/outlives/implicit_infer.rs

   1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use rustc::hir;
  12 use hir::Node;
  13 use rustc::hir::def_id::DefId;
  14 use rustc::hir::itemlikevisit::ItemLikeVisitor;
  15 use rustc::ty::subst::{Kind, Subst, UnpackedKind};
  16 use rustc::ty::{self, Ty, TyCtxt};
  17 use rustc::util::nodemap::FxHashMap;
  18
  19 use super::explicit::ExplicitPredicatesMap;
  20 use super::utils::*;
  21
  22 /// Infer predicates for the items in the crate.
  23 ///
  24 /// global_inferred_outlives: this is initially the empty map that
  25 ///     was generated by walking the items in the crate. This will
  26 ///     now be filled with inferred predicates.
  27 pub fn infer_predicates<'tcx>(
  28     tcx: TyCtxt<'_, 'tcx, 'tcx>,
  29     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
  30 ) -> FxHashMap<DefId, RequiredPredicates<'tcx>> {
  31     debug!("infer_predicates");
  32
  33     let mut predicates_added = true;
  34
  35     let mut global_inferred_outlives = FxHashMap::default();
  36
  37     // If new predicates were added then we need to re-calculate
  38     // all crates since there could be new implied predicates.
  39     while predicates_added {
  40         predicates_added = false;
  41
  42         let mut visitor = InferVisitor {
  43             tcx: tcx,
  44             global_inferred_outlives: &mut global_inferred_outlives,
  45             predicates_added: &mut predicates_added,
  46             explicit_map: explicit_map,
  47         };
  48
  49         // Visit all the crates and infer predicates
  50         tcx.hir.krate().visit_all_item_likes(&mut visitor);
  51     }
  52
  53     global_inferred_outlives
  54 }
  55
  56 pub struct InferVisitor<'cx, 'tcx: 'cx> {
  57     tcx: TyCtxt<'cx, 'tcx, 'tcx>,
  58     global_inferred_outlives: &'cx mut FxHashMap<DefId, RequiredPredicates<'tcx>>,
  59     predicates_added: &'cx mut bool,
  60     explicit_map: &'cx mut ExplicitPredicatesMap<'tcx>,
  61 }
  62
  63 impl<'cx, 'tcx> ItemLikeVisitor<'tcx> for InferVisitor<'cx, 'tcx> {
  64     fn visit_item(&mut self, item: &hir::Item) {
  65         let item_did = self.tcx.hir.local_def_id(item.id);
  66
  67         debug!("InferVisitor::visit_item(item={:?})", item_did);
  68
  69         let node_id = self
  70             .tcx
  71             .hir
  72             .as_local_node_id(item_did)
  73             .expect("expected local def-id");
  74         let item = match self.tcx.hir.get(node_id) {
  75             Node::Item(item) => item,
  76             _ => bug!(),
  77         };
  78
  79         let mut item_required_predicates = RequiredPredicates::default();
  80         match item.node {
  81             hir::ItemKind::Union(..) | hir::ItemKind::Enum(..) | hir::ItemKind::Struct(..) => {
  82                 let adt_def = self.tcx.adt_def(item_did);
  83
  84                 // Iterate over all fields in item_did
  85                 for field_def in adt_def.all_fields() {
  86                     // Calculating the predicate requirements necessary
  87                     // for item_did.
  88                     //
  89                     // For field of type &'a T (reference) or Adt
  90                     // (struct/enum/union) there will be outlive
  91                     // requirements for adt_def.
  92                     let field_ty = self.tcx.type_of(field_def.did);
  93                     insert_required_predicates_to_be_wf(
  94                         self.tcx,
  95                         field_ty,
  96                         self.global_inferred_outlives,
  97                         &mut item_required_predicates,
  98                         &mut self.explicit_map,
  99                     );
 100                 }
 101             }
 102
 103             _ => {}
 104         };
 105
 106         // If new predicates were added (`local_predicate_map` has more
 107         // predicates than the `global_inferred_outlives`), the new predicates
 108         // might result in implied predicates for their parent types.
 109         // Therefore mark `predicates_added` as true and which will ensure
 110         // we walk the crates again and re-calculate predicates for all
 111         // items.
 112         let item_predicates_len: usize = self
 113             .global_inferred_outlives
 114             .get(&item_did)
 115             .map(|p| p.len())
 116             .unwrap_or(0);
 117         if item_required_predicates.len() > item_predicates_len {
 118             *self.predicates_added = true;
 119             self.global_inferred_outlives
 120                 .insert(item_did, item_required_predicates);
 121         }
 122     }
 123
 124     fn visit_trait_item(&mut self, _trait_item: &'tcx hir::TraitItem) {}
 125
 126     fn visit_impl_item(&mut self, _impl_item: &'tcx hir::ImplItem) {}
 127 }
 128
 129 fn insert_required_predicates_to_be_wf<'tcx>(
 130     tcx: TyCtxt<'_, 'tcx, 'tcx>,
 131     field_ty: Ty<'tcx>,
 132     global_inferred_outlives: &FxHashMap<DefId, RequiredPredicates<'tcx>>,
 133     required_predicates: &mut RequiredPredicates<'tcx>,
 134     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
 135 ) {
 136     for ty in field_ty.walk() {
 137         match ty.sty {
 138             // The field is of type &'a T which means that we will have
 139             // a predicate requirement of T: 'a (T outlives 'a).
 140             //
 141             // We also want to calculate potential predicates for the T
 142             ty::Ref(region, rty, _) => {
 143                 debug!("Ref");
 144                 insert_outlives_predicate(tcx, rty.into(), region, required_predicates);
 145             }
 146
 147             // For each Adt (struct/enum/union) type `Foo<'a, T>`, we
 148             // can load the current set of inferred and explicit
 149             // predicates from `global_inferred_outlives` and filter the
 150             // ones that are TypeOutlives.
 151             ty::Adt(def, substs) => {
 152                 // First check the inferred predicates
 153                 //
 154                 // Example 1:
 155                 //
 156                 //     struct Foo<'a, T> {
 157                 //         field1: Bar<'a, T>
 158                 //     }
 159                 //
 160                 //     struct Bar<'b, U> {
 161                 //         field2: &'b U
 162                 //     }
 163                 //
 164                 // Here, when processing the type of `field1`, we would
 165                 // request the set of implicit predicates computed for `Bar`
 166                 // thus far. This will initially come back empty, but in next
 167                 // round we will get `U: 'b`. We then apply the substitution
 168                 // `['b => 'a, U => T]` and thus get the requirement that `T:
 169                 // 'a` holds for `Foo`.
 170                 debug!("Adt");
 171                 if let Some(unsubstituted_predicates) = global_inferred_outlives.get(&def.did) {
 172                     for unsubstituted_predicate in unsubstituted_predicates {
 173                         // `unsubstituted_predicate` is `U: 'b` in the
 174                         // example above.  So apply the substitution to
 175                         // get `T: 'a` (or `predicate`):
 176                         let predicate = unsubstituted_predicate.subst(tcx, substs);
 177                         insert_outlives_predicate(
 178                             tcx,
 179                             predicate.0,
 180                             predicate.1,
 181                             required_predicates,
 182                         );
 183                     }
 184                 }
 185
 186                 // Check if the type has any explicit predicates that need
 187                 // to be added to `required_predicates`
 188                 // let _: () = substs.region_at(0);
 189                 check_explicit_predicates(
 190                     tcx,
 191                     &def.did,
 192                     substs,
 193                     required_predicates,
 194                     explicit_map,
 195                     IgnoreSelfTy(false),
 196                 );
 197             }
 198
 199             ty::Dynamic(obj, ..) => {
 200                 // This corresponds to `dyn Trait<..>`. In this case, we should
 201                 // use the explicit predicates as well.
 202
 203                 debug!("Dynamic");
 204                 debug!("field_ty = {}", &field_ty);
 205                 debug!("ty in field = {}", &ty);
 206                 let ex_trait_ref = obj.principal();
 207                 // Here, we are passing the type `usize` as a
 208                 // placeholder value with the function
 209                 // `with_self_ty`, since there is no concrete type
 210                 // `Self` for a `dyn Trait` at this
 211                 // stage. Therefore when checking explicit
 212                 // predicates in `check_explicit_predicates` we
 213                 // need to ignore checking the explicit_map for
 214                 // Self type.
 215                 let substs = ex_trait_ref
 216                     .with_self_ty(tcx, tcx.types.usize)
 217                     .skip_binder()
 218                     .substs;
 219                 check_explicit_predicates(
 220                     tcx,
 221                     &ex_trait_ref.skip_binder().def_id,
 222                     substs,
 223                     required_predicates,
 224                     explicit_map,
 225                     IgnoreSelfTy(true),
 226                 );
 227             }
 228
 229             ty::Projection(obj) => {
 230                 // This corresponds to `<T as Foo<'a>>::Bar`. In this case, we should use the
 231                 // explicit predicates as well.
 232                 debug!("Projection");
 233                 check_explicit_predicates(
 234                     tcx,
 235                     &tcx.associated_item(obj.item_def_id).container.id(),
 236                     obj.substs,
 237                     required_predicates,
 238                     explicit_map,
 239                     IgnoreSelfTy(false),
 240                 );
 241             }
 242
 243             _ => {}
 244         }
 245     }
 246 }
 247
 248 pub struct IgnoreSelfTy(bool);
 249
 250 /// We also have to check the explicit predicates
 251 /// declared on the type.
 252 ///
 253 ///     struct Foo<'a, T> {
 254 ///         field1: Bar<T>
 255 ///     }
 256 ///
 257 ///     struct Bar<U> where U: 'static, U: Foo {
 258 ///         ...
 259 ///     }
 260 ///
 261 /// Here, we should fetch the explicit predicates, which
 262 /// will give us `U: 'static` and `U: Foo`. The latter we
 263 /// can ignore, but we will want to process `U: 'static`,
 264 /// applying the substitution as above.
 265 pub fn check_explicit_predicates<'tcx>(
 266     tcx: TyCtxt<'_, 'tcx, 'tcx>,
 267     def_id: &DefId,
 268     substs: &[Kind<'tcx>],
 269     required_predicates: &mut RequiredPredicates<'tcx>,
 270     explicit_map: &mut ExplicitPredicatesMap<'tcx>,
 271     ignore_self_ty: IgnoreSelfTy,
 272 ) {
 273     debug!("def_id = {:?}", &def_id);
 274     debug!("substs = {:?}", &substs);
 275     debug!("explicit_map =  {:?}", explicit_map);
 276     debug!("required_predicates = {:?}", required_predicates);
 277     let explicit_predicates = explicit_map.explicit_predicates_of(tcx, *def_id);
 278
 279     for outlives_predicate in explicit_predicates.iter() {
 280         debug!("outlives_predicate = {:?}", &outlives_predicate);
 281
 282         // Careful: If we are inferring the effects of a `dyn Trait<..>`
 283         // type, then when we look up the predicates for `Trait`,
 284         // we may find some that reference `Self`. e.g., perhaps the
 285         // definition of `Trait` was:
 286         //
 287         // ```
 288         // trait Trait<'a, T> where Self: 'a  { .. }
 289         // ```
 290         //
 291         // we want to ignore such predicates here, because
 292         // there is no type parameter for them to affect. Consider
 293         // a struct containing `dyn Trait`:
 294         //
 295         // ```
 296         // struct MyStruct<'x, X> { field: Box<dyn Trait<'x, X>> }
 297         // ```
 298         //
 299         // The `where Self: 'a` predicate refers to the *existential, hidden type*
 300         // that is represented by the `dyn Trait`, not to the `X` type parameter
 301         // (or any other generic parameter) declared on `MyStruct`.
 302         //
 303         // Note that we do this check for self **before** applying `substs`. In the
 304         // case that `substs` come from a `dyn Trait` type, our caller will have
 305         // included `Self = dyn Trait<'x, X>` as the value for `Self`. If we were
 306         // to apply the substs, and not filter this predicate, we might then falsely
 307         // conclude that e.g. `X: 'x` was a reasonable inferred requirement.
 308         if let UnpackedKind::Type(ty) = outlives_predicate.0.unpack() {
 309             if ty.is_self() && ignore_self_ty.0 {
 310                 debug!("skipping self ty = {:?}", &ty);
 311                 continue;
 312             }
 313         }
 314
 315         let predicate = outlives_predicate.subst(tcx, substs);
 316         debug!("predicate = {:?}", &predicate);
 317         insert_outlives_predicate(tcx, predicate.0.into(), predicate.1, required_predicates);
 318     }
 319 }