src/librustc_typeck/coherence/builtin.rs

   1 // Copyright 2016 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 //! Check properties that are required by built-in traits and set
  12 //! up data structures required by type-checking/codegen.
  13
  14 use rustc::infer::SuppressRegionErrors;
  15 use rustc::infer::outlives::env::OutlivesEnvironment;
  16 use rustc::middle::region;
  17 use rustc::middle::lang_items::UnsizeTraitLangItem;
  18
  19 use rustc::traits::{self, TraitEngine, ObligationCause};
  20 use rustc::ty::{self, Ty, TyCtxt};
  21 use rustc::ty::TypeFoldable;
  22 use rustc::ty::adjustment::CoerceUnsizedInfo;
  23 use rustc::ty::util::CopyImplementationError;
  24 use rustc::infer;
  25
  26 use rustc::hir::def_id::DefId;
  27 use hir::Node;
  28 use rustc::hir::{self, ItemKind};
  29
  30 pub fn check_trait<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, trait_def_id: DefId) {
  31     Checker { tcx, trait_def_id }
  32         .check(tcx.lang_items().drop_trait(), visit_implementation_of_drop)
  33         .check(tcx.lang_items().copy_trait(), visit_implementation_of_copy)
  34         .check(tcx.lang_items().coerce_unsized_trait(), visit_implementation_of_coerce_unsized)
  35         .check(tcx.lang_items().dispatch_from_dyn_trait(),
  36             visit_implementation_of_dispatch_from_dyn);
  37 }
  38
  39 struct Checker<'a, 'tcx: 'a> {
  40     tcx: TyCtxt<'a, 'tcx, 'tcx>,
  41     trait_def_id: DefId
  42 }
  43
  44 impl<'a, 'tcx> Checker<'a, 'tcx> {
  45     fn check<F>(&self, trait_def_id: Option<DefId>, mut f: F) -> &Self
  46         where F: FnMut(TyCtxt<'a, 'tcx, 'tcx>, DefId)
  47     {
  48         if Some(self.trait_def_id) == trait_def_id {
  49             for &impl_id in self.tcx.hir().trait_impls(self.trait_def_id) {
  50                 let impl_def_id = self.tcx.hir().local_def_id(impl_id);
  51                 f(self.tcx, impl_def_id);
  52             }
  53         }
  54         self
  55     }
  56 }
  57
  58 fn visit_implementation_of_drop<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, impl_did: DefId) {
  59     if let ty::Adt(..) = tcx.type_of(impl_did).sty {
  60         /* do nothing */
  61     } else {
  62         // Destructors only work on nominal types.
  63         if let Some(impl_node_id) = tcx.hir().as_local_node_id(impl_did) {
  64             if let Some(Node::Item(item)) = tcx.hir().find(impl_node_id) {
  65                 let span = match item.node {
  66                     ItemKind::Impl(.., ref ty, _) => ty.span,
  67                     _ => item.span,
  68                 };
  69                 struct_span_err!(tcx.sess,
  70                                  span,
  71                                  E0120,
  72                                  "the Drop trait may only be implemented on \
  73                                   structures")
  74                     .span_label(span, "implementing Drop requires a struct")
  75                     .emit();
  76             } else {
  77                 bug!("didn't find impl in ast map");
  78             }
  79         } else {
  80             bug!("found external impl of Drop trait on \
  81                   something other than a struct");
  82         }
  83     }
  84 }
  85
  86 fn visit_implementation_of_copy<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, impl_did: DefId) {
  87     debug!("visit_implementation_of_copy: impl_did={:?}", impl_did);
  88
  89     let impl_node_id = if let Some(n) = tcx.hir().as_local_node_id(impl_did) {
  90         n
  91     } else {
  92         debug!("visit_implementation_of_copy(): impl not in this crate");
  93         return;
  94     };
  95
  96     let self_type = tcx.type_of(impl_did);
  97     debug!("visit_implementation_of_copy: self_type={:?} (bound)",
  98            self_type);
  99
 100     let span = tcx.hir().span(impl_node_id);
 101     let param_env = tcx.param_env(impl_did);
 102     assert!(!self_type.has_escaping_bound_vars());
 103
 104     debug!("visit_implementation_of_copy: self_type={:?} (free)",
 105            self_type);
 106
 107     match param_env.can_type_implement_copy(tcx, self_type) {
 108         Ok(()) => {}
 109         Err(CopyImplementationError::InfrigingFields(fields)) => {
 110             let item = tcx.hir().expect_item(impl_node_id);
 111             let span = if let ItemKind::Impl(.., Some(ref tr), _, _) = item.node {
 112                 tr.path.span
 113             } else {
 114                 span
 115             };
 116
 117             let mut err = struct_span_err!(tcx.sess,
 118                                            span,
 119                                            E0204,
 120                                            "the trait `Copy` may not be implemented for this type");
 121             for span in fields.iter().map(|f| tcx.def_span(f.did)) {
 122                 err.span_label(span, "this field does not implement `Copy`");
 123             }
 124             err.emit()
 125         }
 126         Err(CopyImplementationError::NotAnAdt) => {
 127             let item = tcx.hir().expect_item(impl_node_id);
 128             let span = if let ItemKind::Impl(.., ref ty, _) = item.node {
 129                 ty.span
 130             } else {
 131                 span
 132             };
 133
 134             struct_span_err!(tcx.sess,
 135                              span,
 136                              E0206,
 137                              "the trait `Copy` may not be implemented for this type")
 138                 .span_label(span, "type is not a structure or enumeration")
 139                 .emit();
 140         }
 141         Err(CopyImplementationError::HasDestructor) => {
 142             struct_span_err!(tcx.sess,
 143                              span,
 144                              E0184,
 145                              "the trait `Copy` may not be implemented for this type; the \
 146                               type has a destructor")
 147                 .span_label(span, "Copy not allowed on types with destructors")
 148                 .emit();
 149         }
 150     }
 151 }
 152
 153 fn visit_implementation_of_coerce_unsized<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, impl_did: DefId) {
 154     debug!("visit_implementation_of_coerce_unsized: impl_did={:?}",
 155            impl_did);
 156
 157     // Just compute this for the side-effects, in particular reporting
 158     // errors; other parts of the code may demand it for the info of
 159     // course.
 160     if impl_did.is_local() {
 161         let span = tcx.def_span(impl_did);
 162         tcx.at(span).coerce_unsized_info(impl_did);
 163     }
 164 }
 165
 166 fn visit_implementation_of_dispatch_from_dyn<'a, 'tcx>(
 167     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 168     impl_did: DefId,
 169 ) {
 170     debug!("visit_implementation_of_dispatch_from_dyn: impl_did={:?}",
 171            impl_did);
 172     if impl_did.is_local() {
 173         let dispatch_from_dyn_trait = tcx.lang_items().dispatch_from_dyn_trait().unwrap();
 174
 175         let impl_node_id = tcx.hir().as_local_node_id(impl_did).unwrap();
 176         let span = tcx.hir().span(impl_node_id);
 177
 178         let source = tcx.type_of(impl_did);
 179         assert!(!source.has_escaping_bound_vars());
 180         let target = {
 181             let trait_ref = tcx.impl_trait_ref(impl_did).unwrap();
 182             assert_eq!(trait_ref.def_id, dispatch_from_dyn_trait);
 183
 184             trait_ref.substs.type_at(1)
 185         };
 186
 187         debug!("visit_implementation_of_dispatch_from_dyn: {:?} -> {:?}",
 188             source,
 189             target);
 190
 191         let param_env = tcx.param_env(impl_did);
 192
 193         let create_err = |msg: &str| {
 194             struct_span_err!(tcx.sess, span, E0378, "{}", msg)
 195         };
 196
 197         tcx.infer_ctxt().enter(|infcx| {
 198             let cause = ObligationCause::misc(span, impl_node_id);
 199
 200             use ty::TyKind::*;
 201             match (&source.sty, &target.sty) {
 202                 (&Ref(r_a, _, mutbl_a), Ref(r_b, _, mutbl_b))
 203                     if infcx.at(&cause, param_env).eq(r_a, r_b).is_ok()
 204                     && mutbl_a == *mutbl_b => (),
 205                 (&RawPtr(tm_a), &RawPtr(tm_b))
 206                     if tm_a.mutbl == tm_b.mutbl => (),
 207                 (&Adt(def_a, substs_a), &Adt(def_b, substs_b))
 208                     if def_a.is_struct() && def_b.is_struct() =>
 209                 {
 210                     if def_a != def_b {
 211                         let source_path = tcx.item_path_str(def_a.did);
 212                         let target_path = tcx.item_path_str(def_b.did);
 213
 214                         create_err(
 215                             &format!(
 216                                 "the trait `DispatchFromDyn` may only be implemented \
 217                                 for a coercion between structures with the same \
 218                                 definition; expected `{}`, found `{}`",
 219                                 source_path, target_path,
 220                             )
 221                         ).emit();
 222
 223                         return
 224                     }
 225
 226                     if def_a.repr.c() || def_a.repr.packed() {
 227                         create_err(
 228                             "structs implementing `DispatchFromDyn` may not have \
 229                              `#[repr(packed)]` or `#[repr(C)]`"
 230                         ).emit();
 231                     }
 232
 233                     let fields = &def_a.non_enum_variant().fields;
 234
 235                     let coerced_fields = fields.iter().filter_map(|field| {
 236                         if tcx.type_of(field.did).is_phantom_data() {
 237                             // ignore PhantomData fields
 238                             return None
 239                         }
 240
 241                         let ty_a = field.ty(tcx, substs_a);
 242                         let ty_b = field.ty(tcx, substs_b);
 243                         if let Ok(ok) = infcx.at(&cause, param_env).eq(ty_a, ty_b) {
 244                             if ok.obligations.is_empty() {
 245                                 create_err(
 246                                     "the trait `DispatchFromDyn` may only be implemented \
 247                                      for structs containing the field being coerced, \
 248                                      `PhantomData` fields, and nothing else"
 249                                 ).note(
 250                                     &format!(
 251                                         "extra field `{}` of type `{}` is not allowed",
 252                                         field.ident, ty_a,
 253                                     )
 254                                 ).emit();
 255
 256                                 return None;
 257                             }
 258                         }
 259
 260                         Some(field)
 261                     }).collect::<Vec<_>>();
 262
 263                     if coerced_fields.is_empty() {
 264                         create_err(
 265                             "the trait `DispatchFromDyn` may only be implemented \
 266                             for a coercion between structures with a single field \
 267                             being coerced, none found"
 268                         ).emit();
 269                     } else if coerced_fields.len() > 1 {
 270                         create_err(
 271                             "implementing the `DispatchFromDyn` trait requires multiple coercions",
 272                         ).note(
 273                             "the trait `DispatchFromDyn` may only be implemented \
 274                                 for a coercion between structures with a single field \
 275                                 being coerced"
 276                         ).note(
 277                             &format!(
 278                                 "currently, {} fields need coercions: {}",
 279                                 coerced_fields.len(),
 280                                 coerced_fields.iter().map(|field| {
 281                                     format!("`{}` (`{}` to `{}`)",
 282                                         field.ident,
 283                                         field.ty(tcx, substs_a),
 284                                         field.ty(tcx, substs_b),
 285                                     )
 286                                 }).collect::<Vec<_>>()
 287                                 .join(", ")
 288                             )
 289                         ).emit();
 290                     } else {
 291                         let mut fulfill_cx = TraitEngine::new(infcx.tcx);
 292
 293                         for field in coerced_fields {
 294
 295                             let predicate = tcx.predicate_for_trait_def(
 296                                 param_env,
 297                                 cause.clone(),
 298                                 dispatch_from_dyn_trait,
 299                                 0,
 300                                 field.ty(tcx, substs_a),
 301                                 &[field.ty(tcx, substs_b).into()]
 302                             );
 303
 304                             fulfill_cx.register_predicate_obligation(&infcx, predicate);
 305                         }
 306
 307                         // Check that all transitive obligations are satisfied.
 308                         if let Err(errors) = fulfill_cx.select_all_or_error(&infcx) {
 309                             infcx.report_fulfillment_errors(&errors, None, false);
 310                         }
 311
 312                         // Finally, resolve all regions.
 313                         let region_scope_tree = region::ScopeTree::default();
 314                         let outlives_env = OutlivesEnvironment::new(param_env);
 315                         infcx.resolve_regions_and_report_errors(
 316                             impl_did,
 317                             &region_scope_tree,
 318                             &outlives_env,
 319                             SuppressRegionErrors::default(),
 320                         );
 321                     }
 322                 }
 323                 _ => {
 324                     create_err(
 325                         "the trait `DispatchFromDyn` may only be implemented \
 326                         for a coercion between structures"
 327                     ).emit();
 328                 }
 329             }
 330         })
 331     }
 332 }
 333
 334 pub fn coerce_unsized_info<'a, 'gcx>(gcx: TyCtxt<'a, 'gcx, 'gcx>,
 335                                      impl_did: DefId)
 336                                      -> CoerceUnsizedInfo {
 337     debug!("compute_coerce_unsized_info(impl_did={:?})", impl_did);
 338     let coerce_unsized_trait = gcx.lang_items().coerce_unsized_trait().unwrap();
 339
 340     let unsize_trait = gcx.lang_items().require(UnsizeTraitLangItem).unwrap_or_else(|err| {
 341         gcx.sess.fatal(&format!("`CoerceUnsized` implementation {}", err));
 342     });
 343
 344     // this provider should only get invoked for local def-ids
 345     let impl_node_id = gcx.hir().as_local_node_id(impl_did).unwrap_or_else(|| {
 346         bug!("coerce_unsized_info: invoked for non-local def-id {:?}", impl_did)
 347     });
 348
 349     let source = gcx.type_of(impl_did);
 350     let trait_ref = gcx.impl_trait_ref(impl_did).unwrap();
 351     assert_eq!(trait_ref.def_id, coerce_unsized_trait);
 352     let target = trait_ref.substs.type_at(1);
 353     debug!("visit_implementation_of_coerce_unsized: {:?} -> {:?} (bound)",
 354            source,
 355            target);
 356
 357     let span = gcx.hir().span(impl_node_id);
 358     let param_env = gcx.param_env(impl_did);
 359     assert!(!source.has_escaping_bound_vars());
 360
 361     let err_info = CoerceUnsizedInfo { custom_kind: None };
 362
 363     debug!("visit_implementation_of_coerce_unsized: {:?} -> {:?} (free)",
 364            source,
 365            target);
 366
 367     gcx.infer_ctxt().enter(|infcx| {
 368         let cause = ObligationCause::misc(span, impl_node_id);
 369         let check_mutbl = |mt_a: ty::TypeAndMut<'gcx>,
 370                            mt_b: ty::TypeAndMut<'gcx>,
 371                            mk_ptr: &dyn Fn(Ty<'gcx>) -> Ty<'gcx>| {
 372             if (mt_a.mutbl, mt_b.mutbl) == (hir::MutImmutable, hir::MutMutable) {
 373                 infcx.report_mismatched_types(&cause,
 374                                               mk_ptr(mt_b.ty),
 375                                               target,
 376                                               ty::error::TypeError::Mutability)
 377                     .emit();
 378             }
 379             (mt_a.ty, mt_b.ty, unsize_trait, None)
 380         };
 381         let (source, target, trait_def_id, kind) = match (&source.sty, &target.sty) {
 382             (&ty::Ref(r_a, ty_a, mutbl_a), &ty::Ref(r_b, ty_b, mutbl_b)) => {
 383                 infcx.sub_regions(infer::RelateObjectBound(span), r_b, r_a);
 384                 let mt_a = ty::TypeAndMut { ty: ty_a, mutbl: mutbl_a };
 385                 let mt_b = ty::TypeAndMut { ty: ty_b, mutbl: mutbl_b };
 386                 check_mutbl(mt_a, mt_b, &|ty| gcx.mk_imm_ref(r_b, ty))
 387             }
 388
 389             (&ty::Ref(_, ty_a, mutbl_a), &ty::RawPtr(mt_b)) => {
 390                 let mt_a = ty::TypeAndMut { ty: ty_a, mutbl: mutbl_a };
 391                 check_mutbl(mt_a, mt_b, &|ty| gcx.mk_imm_ptr(ty))
 392             }
 393
 394             (&ty::RawPtr(mt_a), &ty::RawPtr(mt_b)) => {
 395                 check_mutbl(mt_a, mt_b, &|ty| gcx.mk_imm_ptr(ty))
 396             }
 397
 398             (&ty::Adt(def_a, substs_a), &ty::Adt(def_b, substs_b)) if def_a.is_struct() &&
 399                                                                       def_b.is_struct() => {
 400                 if def_a != def_b {
 401                     let source_path = gcx.item_path_str(def_a.did);
 402                     let target_path = gcx.item_path_str(def_b.did);
 403                     span_err!(gcx.sess,
 404                               span,
 405                               E0377,
 406                               "the trait `CoerceUnsized` may only be implemented \
 407                                for a coercion between structures with the same \
 408                                definition; expected `{}`, found `{}`",
 409                               source_path,
 410                               target_path);
 411                     return err_info;
 412                 }
 413
 414                 // Here we are considering a case of converting
 415                 // `S<P0...Pn>` to S<Q0...Qn>`. As an example, let's imagine a struct `Foo<T, U>`,
 416                 // which acts like a pointer to `U`, but carries along some extra data of type `T`:
 417                 //
 418                 //     struct Foo<T, U> {
 419                 //         extra: T,
 420                 //         ptr: *mut U,
 421                 //     }
 422                 //
 423                 // We might have an impl that allows (e.g.) `Foo<T, [i32; 3]>` to be unsized
 424                 // to `Foo<T, [i32]>`. That impl would look like:
 425                 //
 426                 //   impl<T, U: Unsize<V>, V> CoerceUnsized<Foo<T, V>> for Foo<T, U> {}
 427                 //
 428                 // Here `U = [i32; 3]` and `V = [i32]`. At runtime,
 429                 // when this coercion occurs, we would be changing the
 430                 // field `ptr` from a thin pointer of type `*mut [i32;
 431                 // 3]` to a fat pointer of type `*mut [i32]` (with
 432                 // extra data `3`).  **The purpose of this check is to
 433                 // make sure that we know how to do this conversion.**
 434                 //
 435                 // To check if this impl is legal, we would walk down
 436                 // the fields of `Foo` and consider their types with
 437                 // both substitutes. We are looking to find that
 438                 // exactly one (non-phantom) field has changed its
 439                 // type, which we will expect to be the pointer that
 440                 // is becoming fat (we could probably generalize this
 441                 // to multiple thin pointers of the same type becoming
 442                 // fat, but we don't). In this case:
 443                 //
 444                 // - `extra` has type `T` before and type `T` after
 445                 // - `ptr` has type `*mut U` before and type `*mut V` after
 446                 //
 447                 // Since just one field changed, we would then check
 448                 // that `*mut U: CoerceUnsized<*mut V>` is implemented
 449                 // (in other words, that we know how to do this
 450                 // conversion). This will work out because `U:
 451                 // Unsize<V>`, and we have a builtin rule that `*mut
 452                 // U` can be coerced to `*mut V` if `U: Unsize<V>`.
 453                 let fields = &def_a.non_enum_variant().fields;
 454                 let diff_fields = fields.iter()
 455                     .enumerate()
 456                     .filter_map(|(i, f)| {
 457                         let (a, b) = (f.ty(gcx, substs_a), f.ty(gcx, substs_b));
 458
 459                         if gcx.type_of(f.did).is_phantom_data() {
 460                             // Ignore PhantomData fields
 461                             return None;
 462                         }
 463
 464                         // Ignore fields that aren't changed; it may
 465                         // be that we could get away with subtyping or
 466                         // something more accepting, but we use
 467                         // equality because we want to be able to
 468                         // perform this check without computing
 469                         // variance where possible. (This is because
 470                         // we may have to evaluate constraint
 471                         // expressions in the course of execution.)
 472                         // See e.g., #41936.
 473                         if let Ok(ok) = infcx.at(&cause, param_env).eq(a, b) {
 474                             if ok.obligations.is_empty() {
 475                                 return None;
 476                             }
 477                         }
 478
 479                         // Collect up all fields that were significantly changed
 480                         // i.e., those that contain T in coerce_unsized T -> U
 481                         Some((i, a, b))
 482                     })
 483                     .collect::<Vec<_>>();
 484
 485                 if diff_fields.is_empty() {
 486                     span_err!(gcx.sess,
 487                               span,
 488                               E0374,
 489                               "the trait `CoerceUnsized` may only be implemented \
 490                                for a coercion between structures with one field \
 491                                being coerced, none found");
 492                     return err_info;
 493                 } else if diff_fields.len() > 1 {
 494                     let item = gcx.hir().expect_item(impl_node_id);
 495                     let span = if let ItemKind::Impl(.., Some(ref t), _, _) = item.node {
 496                         t.path.span
 497                     } else {
 498                         gcx.hir().span(impl_node_id)
 499                     };
 500
 501                     let mut err = struct_span_err!(gcx.sess,
 502                                                    span,
 503                                                    E0375,
 504                                                    "implementing the trait \
 505                                                     `CoerceUnsized` requires multiple \
 506                                                     coercions");
 507                     err.note("`CoerceUnsized` may only be implemented for \
 508                               a coercion between structures with one field being coerced");
 509                     err.note(&format!("currently, {} fields need coercions: {}",
 510                                       diff_fields.len(),
 511                                       diff_fields.iter()
 512                                           .map(|&(i, a, b)| {
 513                                               format!("`{}` (`{}` to `{}`)", fields[i].ident, a, b)
 514                                           })
 515                                           .collect::<Vec<_>>()
 516                                           .join(", ")));
 517                     err.span_label(span, "requires multiple coercions");
 518                     err.emit();
 519                     return err_info;
 520                 }
 521
 522                 let (i, a, b) = diff_fields[0];
 523                 let kind = ty::adjustment::CustomCoerceUnsized::Struct(i);
 524                 (a, b, coerce_unsized_trait, Some(kind))
 525             }
 526
 527             _ => {
 528                 span_err!(gcx.sess,
 529                           span,
 530                           E0376,
 531                           "the trait `CoerceUnsized` may only be implemented \
 532                            for a coercion between structures");
 533                 return err_info;
 534             }
 535         };
 536
 537         let mut fulfill_cx = TraitEngine::new(infcx.tcx);
 538
 539         // Register an obligation for `A: Trait<B>`.
 540         let cause = traits::ObligationCause::misc(span, impl_node_id);
 541         let predicate = gcx.predicate_for_trait_def(param_env,
 542                                                     cause,
 543                                                     trait_def_id,
 544                                                     0,
 545                                                     source,
 546                                                     &[target.into()]);
 547         fulfill_cx.register_predicate_obligation(&infcx, predicate);
 548
 549         // Check that all transitive obligations are satisfied.
 550         if let Err(errors) = fulfill_cx.select_all_or_error(&infcx) {
 551             infcx.report_fulfillment_errors(&errors, None, false);
 552         }
 553
 554         // Finally, resolve all regions.
 555         let region_scope_tree = region::ScopeTree::default();
 556         let outlives_env = OutlivesEnvironment::new(param_env);
 557         infcx.resolve_regions_and_report_errors(
 558             impl_did,
 559             &region_scope_tree,
 560             &outlives_env,
 561             SuppressRegionErrors::default(),
 562         );
 563
 564         CoerceUnsizedInfo {
 565             custom_kind: kind
 566         }
 567     })
 568 }