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 #![allow(unused)]
  12
  13 use rustc::hir;
  14 use rustc::hir::def::{CtorKind, Def};
  15 use rustc::hir::def_id::{self, CrateNum, DefId, LOCAL_CRATE};
  16 use rustc::hir::itemlikevisit::ItemLikeVisitor;
  17 use rustc::hir::map as hir_map;
  18 use rustc::ty::Slice;
  19 use rustc::ty::maps::Providers;
  20 use rustc::ty::outlives::Component;
  21 use rustc::ty::subst::{Kind, Subst, UnpackedKind};
  22 use rustc::ty::{self, AdtKind, CratePredicatesMap, Region, RegionKind, ReprOptions,
  23                 ToPolyTraitRef, ToPredicate, Ty, TyCtxt};
  24 use rustc::util::nodemap::{FxHashMap, FxHashSet};
  25 use rustc_data_structures::sync::Lrc;
  26 use rustc_target::spec::abi;
  27 use syntax::ast;
  28 use syntax_pos::{Span, DUMMY_SP};
  29
  30 /// Infer predicates for the items in the crate.
  31 ///
  32 /// global_inferred_outlives: this is initially the empty map that
  33 ///     was generated by walking the items in the crate. This will
  34 ///     now be filled with inferred predicates.
  35 pub fn infer_predicates<'tcx>(
  36     tcx: TyCtxt<'_, 'tcx, 'tcx>,
  37     explicit_map: &FxHashMap<DefId, Lrc<Vec<ty::Predicate<'tcx>>>>,
  38 ) -> FxHashMap<DefId, RequiredPredicates<'tcx>> {
  39     debug!("infer_predicates");
  40
  41     let mut predicates_added = true;
  42
  43     let mut global_inferred_outlives = FxHashMap::default();
  44
  45     // If new predicates were added then we need to re-calculate
  46     // all crates since there could be new implied predicates.
  47     while predicates_added {
  48         predicates_added = false;
  49
  50         let mut visitor = InferVisitor {
  51             tcx: tcx,
  52             global_inferred_outlives: &mut global_inferred_outlives,
  53             predicates_added: &mut predicates_added,
  54             explicit_map: explicit_map,
  55         };
  56
  57         // Visit all the crates and infer predicates
  58         tcx.hir.krate().visit_all_item_likes(&mut visitor);
  59     }
  60
  61     global_inferred_outlives
  62 }
  63
  64 pub struct InferVisitor<'cx, 'tcx: 'cx> {
  65     tcx: TyCtxt<'cx, 'tcx, 'tcx>,
  66     global_inferred_outlives: &'cx mut FxHashMap<DefId, RequiredPredicates<'tcx>>,
  67     predicates_added: &'cx mut bool,
  68     explicit_map: &'cx FxHashMap<DefId, Lrc<Vec<ty::Predicate<'tcx>>>>,
  69 }
  70
  71 /// Tracks the `T: 'a` or `'a: 'a` predicates that we have inferred
  72 /// must be added to the struct header.
  73 type RequiredPredicates<'tcx> = FxHashSet<ty::OutlivesPredicate<Kind<'tcx>, ty::Region<'tcx>>>;
  74
  75 impl<'cx, 'tcx> ItemLikeVisitor<'tcx> for InferVisitor<'cx, 'tcx> {
  76     fn visit_item(&mut self, item: &hir::Item) {
  77         let item_did = self.tcx.hir.local_def_id(item.id);
  78
  79         debug!("InferVisitor::visit_item(item={:?})", item_did);
  80
  81         let node_id = self.tcx
  82             .hir
  83             .as_local_node_id(item_did)
  84             .expect("expected local def-id");
  85         let item = match self.tcx.hir.get(node_id) {
  86             hir::map::NodeItem(item) => item,
  87             _ => bug!(),
  88         };
  89
  90         let mut item_required_predicates = RequiredPredicates::default();
  91         match item.node {
  92             hir::ItemUnion(..) | hir::ItemEnum(..) | hir::ItemStruct(..) => {
  93                 let adt_def = self.tcx.adt_def(item_did);
  94
  95                 // Iterate over all fields in item_did
  96                 for field_def in adt_def.all_fields() {
  97                     // Calculating the predicate requirements necessary
  98                     // for item_did.
  99                     //
 100                     // For field of type &'a T (reference) or TyAdt
 101                     // (struct/enum/union) there will be outlive
 102                     // requirements for adt_def.
 103                     let field_ty = self.tcx.type_of(field_def.did);
 104                     insert_required_predicates_to_be_wf(
 105                         self.tcx,
 106                         field_ty,
 107                         self.global_inferred_outlives,
 108                         &mut item_required_predicates,
 109                         self.explicit_map,
 110                     );
 111                 }
 112             }
 113
 114             _ => {}
 115         };
 116
 117         // If new predicates were added (`local_predicate_map` has more
 118         // predicates than the `global_inferred_outlives`), the new predicates
 119         // might result in implied predicates for their parent types.
 120         // Therefore mark `predicates_added` as true and which will ensure
 121         // we walk the crates again and re-calculate predicates for all
 122         // items.
 123         let item_predicates_len: usize = self.global_inferred_outlives
 124             .get(&item_did)
 125             .map(|p| p.len())
 126             .unwrap_or(0);
 127         if item_required_predicates.len() > item_predicates_len {
 128             *self.predicates_added = true;
 129             self.global_inferred_outlives
 130                 .insert(item_did, item_required_predicates);
 131         }
 132     }
 133
 134     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {}
 135
 136     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {}
 137 }
 138
 139 fn insert_required_predicates_to_be_wf<'tcx>(
 140     tcx: TyCtxt<'_, 'tcx, 'tcx>,
 141     field_ty: Ty<'tcx>,
 142     global_inferred_outlives: &FxHashMap<DefId, RequiredPredicates<'tcx>>,
 143     required_predicates: &mut RequiredPredicates<'tcx>,
 144     explicit_map: &FxHashMap<DefId, Lrc<Vec<ty::Predicate<'tcx>>>>,
 145 ) {
 146     for ty in field_ty.walk() {
 147         match ty.sty {
 148             // The field is of type &'a T which means that we will have
 149             // a predicate requirement of T: 'a (T outlives 'a).
 150             //
 151             // We also want to calculate potential predicates for the T
 152             ty::TyRef(region, rty, _) => {
 153                 insert_outlives_predicate(tcx, rty.into(), region, required_predicates);
 154             }
 155
 156             // For each TyAdt (struct/enum/union) type `Foo<'a, T>`, we
 157             // can load the current set of inferred and explicit
 158             // predicates from `global_inferred_outlives` and filter the
 159             // ones that are TypeOutlives.
 160             //
 161             ty::TyAdt(def, substs) => {
 162                 // First check the inferred predicates
 163                 //
 164                 // Example 1:
 165                 //
 166                 //     struct Foo<'a, T> {
 167                 //         field1: Bar<'a, T>
 168                 //     }
 169                 //
 170                 //     struct Bar<'b, U> {
 171                 //         field2: &'b U
 172                 //     }
 173                 //
 174                 // Here, when processing the type of `field1`, we would
 175                 // request the set of implicit predicates computed for `Bar`
 176                 // thus far. This will initially come back empty, but in next
 177                 // round we will get `U: 'b`. We then apply the substitution
 178                 // `['b => 'a, U => T]` and thus get the requirement that `T:
 179                 // 'a` holds for `Foo`.
 180                 if let Some(unsubstituted_predicates) = global_inferred_outlives.get(&def.did) {
 181                     for unsubstituted_predicate in unsubstituted_predicates {
 182                         // `unsubstituted_predicate` is `U: 'b` in the
 183                         // example above.  So apply the substitution to
 184                         // get `T: 'a` (or `predicate`):
 185                         let predicate = unsubstituted_predicate.subst(tcx, substs);
 186                         insert_outlives_predicate(
 187                             tcx,
 188                             predicate.0,
 189                             predicate.1,
 190                             required_predicates,
 191                         );
 192                     }
 193                 }
 194
 195                 // Check if the type has any explicit predicates that need
 196                 // to be added to `required_predicates`
 197                 // let _: () = substs.region_at(0);
 198                 check_explicit_predicates(tcx, &def.did, substs, required_predicates, explicit_map);
 199             }
 200
 201             ty::TyDynamic(obj, region) => {
 202                 // FIXME This corresponds to `dyn Trait<..>`. In this
 203                 // case, we should use the explicit predicates as
 204                 // well.
 205                 if let Some(p) = obj.principal() {
 206                     check_explicit_predicates(
 207                         tcx,
 208                         &p.skip_binder().def_id,
 209                         &[region.into()],
 210                         required_predicates,
 211                         explicit_map,
 212                     );
 213                 }
 214             }
 215
 216             ty::TyProjection(obj) => {
 217                 // FIXME This corresponds to `<T as Foo<'a>>::Bar`. In this case, we should use the
 218                 // explicit predicates as well.
 219                 check_explicit_predicates(
 220                     tcx,
 221                     &obj.item_def_id,
 222                     obj.substs,
 223                     required_predicates,
 224                     explicit_map,
 225                 );
 226             }
 227
 228             _ => {}
 229         }
 230     }
 231 }
 232
 233 /// We also have to check the explicit predicates
 234 /// declared on the type.
 235 ///
 236 ///     struct Foo<'a, T> {
 237 ///         field1: Bar<T>
 238 ///     }
 239 ///
 240 ///     struct Bar<U> where U: 'static, U: Foo {
 241 ///         ...
 242 ///     }
 243 ///
 244 /// Here, we should fetch the explicit predicates, which
 245 /// will give us `U: 'static` and `U: Foo`. The latter we
 246 /// can ignore, but we will want to process `U: 'static`,
 247 /// applying the substitution as above.
 248 fn check_explicit_predicates<'tcx>(
 249     tcx: TyCtxt<'_, 'tcx, 'tcx>,
 250     def_id: &DefId,
 251     substs: &[Kind<'tcx>],
 252     required_predicates: &mut RequiredPredicates<'tcx>,
 253     explicit_map: &FxHashMap<DefId, Lrc<Vec<ty::Predicate<'tcx>>>>,
 254 ) {
 255     if let Some(general_predicates) = explicit_map.get(def_id) {
 256         for general_predicate in general_predicates.iter() {
 257             match general_predicate {
 258                 // `poly` is `PolyTypeOutlivesPredicate<OutlivesPredicate<Ty>>`
 259                 // where OutlivesPredicate<type1, region1> is the predicate
 260                 // we want to add.
 261                 ty::Predicate::TypeOutlives(poly) => {
 262                     let predicate = poly.skip_binder().subst(tcx, substs);
 263                     insert_outlives_predicate(
 264                         tcx,
 265                         predicate.0.into(),
 266                         predicate.1,
 267                         required_predicates,
 268                     );
 269                 }
 270
 271                 // `poly` is `PolyRegionOutlivesPredicate<OutlivesPredicate<Ty>>`
 272                 // where OutlivesPredicate<region1, region2> is the predicate
 273                 // we want to add.
 274                 ty::Predicate::RegionOutlives(poly) => {
 275                     let predicate = poly.skip_binder().subst(tcx, substs);
 276                     insert_outlives_predicate(
 277                         tcx,
 278                         predicate.0.into(),
 279                         predicate.1,
 280                         required_predicates,
 281                     );
 282                 }
 283
 284                 ty::Predicate::Trait(..)
 285                 | ty::Predicate::Projection(..)
 286                 | ty::Predicate::WellFormed(..)
 287                 | ty::Predicate::ObjectSafe(..)
 288                 | ty::Predicate::ClosureKind(..)
 289                 | ty::Predicate::Subtype(..)
 290                 | ty::Predicate::ConstEvaluatable(..) => (),
 291             }
 292         }
 293     }
 294 }
 295
 296 /// Given a requirement `T: 'a` or `'b: 'a`, deduce the
 297 /// outlives_component and add it to `required_predicates`
 298 fn insert_outlives_predicate<'tcx>(
 299     tcx: TyCtxt<'_, 'tcx, 'tcx>,
 300     kind: Kind<'tcx>,
 301     outlived_region: Region<'tcx>,
 302     required_predicates: &mut RequiredPredicates<'tcx>,
 303 ) {
 304     // If the `'a` region is bound within the field type itself, we
 305     // don't want to propagate this constraint to the header.
 306     if !is_free_region(outlived_region) {
 307         return;
 308     }
 309
 310     match kind.unpack() {
 311         UnpackedKind::Type(ty) => {
 312             // `T: 'outlived_region` for some type `T`
 313             // But T could be a lot of things:
 314             // e.g., if `T = &'b u32`, then `'b: 'outlived_region` is
 315             // what we want to add.
 316             //
 317             // Or if within `struct Foo<U>` you had `T = Vec<U>`, then
 318             // we would want to add `U: 'outlived_region`
 319             for component in tcx.outlives_components(ty) {
 320                 match component {
 321                     Component::Region(r) => {
 322                         // This would arise from something like:
 323                         //
 324                         // ```
 325                         // struct Foo<'a, 'b> {
 326                         //    x:  &'a &'b u32
 327                         // }
 328                         // ```
 329                         //
 330                         // Here `outlived_region = 'a` and `kind = &'b
 331                         // u32`.  Decomposing `&'b u32` into
 332                         // components would yield `'b`, and we add the
 333                         // where clause that `'b: 'a`.
 334                         insert_outlives_predicate(
 335                             tcx,
 336                             r.into(),
 337                             outlived_region,
 338                             required_predicates,
 339                         );
 340                     }
 341
 342                     Component::Param(param_ty) => {
 343                         // param_ty: ty::ParamTy
 344                         // This would arise from something like:
 345                         //
 346                         // ```
 347                         // struct Foo<'a, U> {
 348                         //    x:  &'a Vec<U>
 349                         // }
 350                         // ```
 351                         //
 352                         // Here `outlived_region = 'a` and `kind =
 353                         // Vec<U>`.  Decomposing `Vec<U>` into
 354                         // components would yield `U`, and we add the
 355                         // where clause that `U: 'a`.
 356                         let ty: Ty<'tcx> = tcx.mk_ty_param(param_ty.idx, param_ty.name);
 357                         required_predicates
 358                             .insert(ty::OutlivesPredicate(ty.into(), outlived_region));
 359                     }
 360
 361                     Component::Projection(proj_ty) => {
 362                         // This would arise from something like:
 363                         //
 364                         // ```
 365                         // struct Foo<'a, T: Iterator> {
 366                         //    x:  &'a <T as Iterator>::Item
 367                         // }
 368                         // ```
 369                         //
 370                         // Here we want to add an explicit `where <T as Iterator>::Item: 'a`.
 371                         let ty: Ty<'tcx> = tcx.mk_projection(proj_ty.item_def_id, proj_ty.substs);
 372                         required_predicates
 373                             .insert(ty::OutlivesPredicate(ty.into(), outlived_region));
 374                     }
 375
 376                     Component::EscapingProjection(_) => {
 377                         // As above, but the projection involves
 378                         // late-bound regions.  Therefore, the WF
 379                         // requirement is not checked in type definition
 380                         // but at fn call site, so ignore it.
 381                         //
 382                         // ```
 383                         // struct Foo<'a, T: Iterator> {
 384                         //    x: for<'b> fn(<&'b T as Iterator>::Item)
 385                         //              //  ^^^^^^^^^^^^^^^^^^^^^^^^^
 386                         // }
 387                         // ```
 388                         //
 389                         // Since `'b` is not in scope on `Foo`, can't
 390                         // do anything here, ignore it.
 391                     }
 392
 393                     Component::UnresolvedInferenceVariable(_) => bug!("not using infcx"),
 394                 }
 395             }
 396         }
 397
 398         UnpackedKind::Lifetime(r) => {
 399             if !is_free_region(r) {
 400                 return;
 401             }
 402             required_predicates.insert(ty::OutlivesPredicate(kind, outlived_region));
 403         }
 404     }
 405 }
 406
 407 fn is_free_region(region: Region<'_>) -> bool {
 408     // First, screen for regions that might appear in a type header.
 409     match region {
 410         // *These* correspond to `T: 'a` relationships where `'a` is
 411         // either declared on the type or `'static`:
 412         //
 413         //     struct Foo<'a, T> {
 414         //         field: &'a T, // this would generate a ReEarlyBound referencing `'a`
 415         //         field2: &'static T, // this would generate a ReStatic
 416         //     }
 417         //
 418         // We care about these, so fall through.
 419         RegionKind::ReStatic | RegionKind::ReEarlyBound(_) => true,
 420
 421         // Late-bound regions can appear in `fn` types:
 422         //
 423         //     struct Foo<T> {
 424         //         field: for<'b> fn(&'b T) // e.g., 'b here
 425         //     }
 426         //
 427         // The type above might generate a `T: 'b` bound, but we can
 428         // ignore it.  We can't put it on the struct header anyway.
 429         RegionKind::ReLateBound(..) => false,
 430
 431         // These regions don't appear in types from type declarations:
 432         RegionKind::ReEmpty
 433         | RegionKind::ReErased
 434         | RegionKind::ReClosureBound(..)
 435         | RegionKind::ReCanonical(..)
 436         | RegionKind::ReScope(..)
 437         | RegionKind::ReVar(..)
 438         | RegionKind::ReSkolemized(..)
 439         | RegionKind::ReFree(..) => {
 440             bug!("unexpected region in outlives inference: {:?}", region);
 441         }
 442     }
 443 }