src/librustc_typeck/coherence/mod.rs

   1 // Copyright 2014 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 // Coherence phase
  12 //
  13 // The job of the coherence phase of typechecking is to ensure that
  14 // each trait has at most one implementation for each type. This is
  15 // done by the orphan and overlap modules. Then we build up various
  16 // mappings. That mapping code resides here.
  17
  18 use hir::def_id::DefId;
  19 use middle::lang_items::UnsizeTraitLangItem;
  20 use rustc::ty::subst::Subst;
  21 use rustc::ty::{self, TyCtxt, TypeFoldable};
  22 use rustc::traits::{self, Reveal};
  23 use rustc::ty::{ImplOrTraitItemId, ConstTraitItemId};
  24 use rustc::ty::{MethodTraitItemId, TypeTraitItemId, ParameterEnvironment};
  25 use rustc::ty::{Ty, TyBool, TyChar, TyEnum, TyError};
  26 use rustc::ty::{TyParam, TyRawPtr};
  27 use rustc::ty::{TyRef, TyStruct, TyTrait, TyNever, TyTuple};
  28 use rustc::ty::{TyStr, TyArray, TySlice, TyFloat, TyInfer, TyInt};
  29 use rustc::ty::{TyUint, TyClosure, TyBox, TyFnDef, TyFnPtr};
  30 use rustc::ty::{TyProjection, TyAnon};
  31 use rustc::ty::util::CopyImplementationError;
  32 use middle::free_region::FreeRegionMap;
  33 use CrateCtxt;
  34 use rustc::infer::{self, InferCtxt, TypeOrigin};
  35 use std::cell::RefCell;
  36 use std::rc::Rc;
  37 use syntax_pos::Span;
  38 use util::nodemap::{DefIdMap, FnvHashMap};
  39 use rustc::dep_graph::DepNode;
  40 use rustc::hir::map as hir_map;
  41 use rustc::hir::intravisit;
  42 use rustc::hir::{Item, ItemImpl};
  43 use rustc::hir;
  44
  45 mod orphan;
  46 mod overlap;
  47 mod unsafety;
  48
  49 struct CoherenceChecker<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
  50     crate_context: &'a CrateCtxt<'a, 'gcx>,
  51     inference_context: InferCtxt<'a, 'gcx, 'tcx>,
  52     inherent_impls: RefCell<DefIdMap<Rc<RefCell<Vec<DefId>>>>>,
  53 }
  54
  55 struct CoherenceCheckVisitor<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
  56     cc: &'a CoherenceChecker<'a, 'gcx, 'tcx>
  57 }
  58
  59 impl<'a, 'gcx, 'tcx, 'v> intravisit::Visitor<'v> for CoherenceCheckVisitor<'a, 'gcx, 'tcx> {
  60     fn visit_item(&mut self, item: &Item) {
  61         if let ItemImpl(..) = item.node {
  62             self.cc.check_implementation(item)
  63         }
  64     }
  65 }
  66
  67 impl<'a, 'gcx, 'tcx> CoherenceChecker<'a, 'gcx, 'tcx> {
  68
  69     // Returns the def ID of the base type, if there is one.
  70     fn get_base_type_def_id(&self, span: Span, ty: Ty<'tcx>) -> Option<DefId> {
  71         match ty.sty {
  72             TyEnum(def, _) |
  73             TyStruct(def, _) => {
  74                 Some(def.did)
  75             }
  76
  77             TyTrait(ref t) => {
  78                 Some(t.principal.def_id())
  79             }
  80
  81             TyBox(_) => {
  82                 self.inference_context.tcx.lang_items.owned_box()
  83             }
  84
  85             TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
  86             TyStr | TyArray(..) | TySlice(..) | TyFnDef(..) | TyFnPtr(_) |
  87             TyTuple(..) | TyParam(..) | TyError | TyNever |
  88             TyRawPtr(_) | TyRef(_, _) | TyProjection(..) => {
  89                 None
  90             }
  91
  92             TyInfer(..) | TyClosure(..) | TyAnon(..) => {
  93                 // `ty` comes from a user declaration so we should only expect types
  94                 // that the user can type
  95                 span_bug!(
  96                     span,
  97                     "coherence encountered unexpected type searching for base type: {}",
  98                     ty);
  99             }
 100         }
 101     }
 102
 103     fn check(&self) {
 104         // Check implementations and traits. This populates the tables
 105         // containing the inherent methods and extension methods. It also
 106         // builds up the trait inheritance table.
 107         self.crate_context.tcx.visit_all_items_in_krate(
 108             DepNode::CoherenceCheckImpl,
 109             &mut CoherenceCheckVisitor { cc: self });
 110
 111         // Copy over the inherent impls we gathered up during the walk into
 112         // the tcx.
 113         let mut tcx_inherent_impls =
 114             self.crate_context.tcx.inherent_impls.borrow_mut();
 115         for (k, v) in self.inherent_impls.borrow().iter() {
 116             tcx_inherent_impls.insert((*k).clone(),
 117                                       Rc::new((*v.borrow()).clone()));
 118         }
 119
 120         // Populate the table of destructors. It might seem a bit strange to
 121         // do this here, but it's actually the most convenient place, since
 122         // the coherence tables contain the trait -> type mappings.
 123         self.populate_destructors();
 124
 125         // Check to make sure implementations of `Copy` are legal.
 126         self.check_implementations_of_copy();
 127
 128         // Check to make sure implementations of `CoerceUnsized` are legal
 129         // and collect the necessary information from them.
 130         self.check_implementations_of_coerce_unsized();
 131     }
 132
 133     fn check_implementation(&self, item: &Item) {
 134         let tcx = self.crate_context.tcx;
 135         let impl_did = tcx.map.local_def_id(item.id);
 136         let self_type = tcx.lookup_item_type(impl_did);
 137
 138         // If there are no traits, then this implementation must have a
 139         // base type.
 140
 141         let impl_items = self.create_impl_from_item(item);
 142
 143         if let Some(trait_ref) = self.crate_context.tcx.impl_trait_ref(impl_did) {
 144             debug!("(checking implementation) adding impl for trait '{:?}', item '{}'",
 145                    trait_ref,
 146                    item.name);
 147
 148             // Skip impls where one of the self type is an error type.
 149             // This occurs with e.g. resolve failures (#30589).
 150             if trait_ref.references_error() {
 151                 return;
 152             }
 153
 154             enforce_trait_manually_implementable(self.crate_context.tcx,
 155                                                  item.span,
 156                                                  trait_ref.def_id);
 157             self.add_trait_impl(trait_ref, impl_did);
 158         } else {
 159             // Skip inherent impls where the self type is an error
 160             // type. This occurs with e.g. resolve failures (#30589).
 161             if self_type.ty.references_error() {
 162                 return;
 163             }
 164
 165             // Add the implementation to the mapping from implementation to base
 166             // type def ID, if there is a base type for this implementation and
 167             // the implementation does not have any associated traits.
 168             if let Some(base_def_id) = self.get_base_type_def_id(item.span, self_type.ty) {
 169                 self.add_inherent_impl(base_def_id, impl_did);
 170             }
 171         }
 172
 173         tcx.impl_items.borrow_mut().insert(impl_did, impl_items);
 174     }
 175
 176     fn add_inherent_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
 177         if let Some(implementation_list) = self.inherent_impls.borrow().get(&base_def_id) {
 178             implementation_list.borrow_mut().push(impl_def_id);
 179             return;
 180         }
 181
 182         self.inherent_impls.borrow_mut().insert(
 183             base_def_id,
 184             Rc::new(RefCell::new(vec!(impl_def_id))));
 185     }
 186
 187     fn add_trait_impl(&self, impl_trait_ref: ty::TraitRef<'gcx>, impl_def_id: DefId) {
 188         debug!("add_trait_impl: impl_trait_ref={:?} impl_def_id={:?}",
 189                impl_trait_ref, impl_def_id);
 190         let trait_def = self.crate_context.tcx.lookup_trait_def(impl_trait_ref.def_id);
 191         trait_def.record_local_impl(self.crate_context.tcx, impl_def_id, impl_trait_ref);
 192     }
 193
 194     // Converts an implementation in the AST to a vector of items.
 195     fn create_impl_from_item(&self, item: &Item) -> Vec<ImplOrTraitItemId> {
 196         match item.node {
 197             ItemImpl(_, _, _, _, _, ref impl_items) => {
 198                 impl_items.iter().map(|impl_item| {
 199                     let impl_def_id = self.crate_context.tcx.map.local_def_id(impl_item.id);
 200                     match impl_item.node {
 201                         hir::ImplItemKind::Const(..) => {
 202                             ConstTraitItemId(impl_def_id)
 203                         }
 204                         hir::ImplItemKind::Method(..) => {
 205                             MethodTraitItemId(impl_def_id)
 206                         }
 207                         hir::ImplItemKind::Type(_) => {
 208                             TypeTraitItemId(impl_def_id)
 209                         }
 210                     }
 211                 }).collect()
 212             }
 213             _ => {
 214                 span_bug!(item.span, "can't convert a non-impl to an impl");
 215             }
 216         }
 217     }
 218
 219     //
 220     // Destructors
 221     //
 222
 223     fn populate_destructors(&self) {
 224         let tcx = self.crate_context.tcx;
 225         let drop_trait = match tcx.lang_items.drop_trait() {
 226             Some(id) => id, None => { return }
 227         };
 228         tcx.populate_implementations_for_trait_if_necessary(drop_trait);
 229         let drop_trait = tcx.lookup_trait_def(drop_trait);
 230
 231         let impl_items = tcx.impl_items.borrow();
 232
 233         drop_trait.for_each_impl(tcx, |impl_did| {
 234             let items = impl_items.get(&impl_did).unwrap();
 235             if items.is_empty() {
 236                 // We'll error out later. For now, just don't ICE.
 237                 return;
 238             }
 239             let method_def_id = items[0];
 240
 241             let self_type = tcx.lookup_item_type(impl_did);
 242             match self_type.ty.sty {
 243                 ty::TyEnum(type_def, _) |
 244                 ty::TyStruct(type_def, _) => {
 245                     type_def.set_destructor(method_def_id.def_id());
 246                 }
 247                 _ => {
 248                     // Destructors only work on nominal types.
 249                     if let Some(impl_node_id) = tcx.map.as_local_node_id(impl_did) {
 250                         match tcx.map.find(impl_node_id) {
 251                             Some(hir_map::NodeItem(item)) => {
 252                                 let span = match item.node {
 253                                     ItemImpl(_, _, _, _, ref ty, _) => {
 254                                         ty.span
 255                                     },
 256                                     _ => item.span
 257                                 };
 258                                 struct_span_err!(tcx.sess, span, E0120,
 259                                     "the Drop trait may only be implemented on structures")
 260                                     .span_label(span,
 261                                                 &format!("implementing Drop requires a struct"))
 262                                     .emit();
 263                             }
 264                             _ => {
 265                                 bug!("didn't find impl in ast map");
 266                             }
 267                         }
 268                     } else {
 269                         bug!("found external impl of Drop trait on \
 270                               something other than a struct");
 271                     }
 272                 }
 273             }
 274         });
 275     }
 276
 277     /// Ensures that implementations of the built-in trait `Copy` are legal.
 278     fn check_implementations_of_copy(&self) {
 279         let tcx = self.crate_context.tcx;
 280         let copy_trait = match tcx.lang_items.copy_trait() {
 281             Some(id) => id,
 282             None => return,
 283         };
 284         tcx.populate_implementations_for_trait_if_necessary(copy_trait);
 285         let copy_trait = tcx.lookup_trait_def(copy_trait);
 286
 287         copy_trait.for_each_impl(tcx, |impl_did| {
 288             debug!("check_implementations_of_copy: impl_did={:?}",
 289                    impl_did);
 290
 291             let impl_node_id = if let Some(n) = tcx.map.as_local_node_id(impl_did) {
 292                 n
 293             } else {
 294                 debug!("check_implementations_of_copy(): impl not in this \
 295                         crate");
 296                 return
 297             };
 298
 299             let self_type = tcx.lookup_item_type(impl_did);
 300             debug!("check_implementations_of_copy: self_type={:?} (bound)",
 301                    self_type);
 302
 303             let span = tcx.map.span(impl_node_id);
 304             let param_env = ParameterEnvironment::for_item(tcx, impl_node_id);
 305             let self_type = self_type.ty.subst(tcx, &param_env.free_substs);
 306             assert!(!self_type.has_escaping_regions());
 307
 308             debug!("check_implementations_of_copy: self_type={:?} (free)",
 309                    self_type);
 310
 311             match param_env.can_type_implement_copy(tcx, self_type, span) {
 312                 Ok(()) => {}
 313                 Err(CopyImplementationError::InfrigingField(name)) => {
 314                        struct_span_err!(tcx.sess, span, E0204,
 315                                  "the trait `Copy` may not be implemented for \
 316                                  this type")
 317                            .span_label(span, &format!(
 318                                  "field `{}` does not implement `Copy`", name)
 319                                )
 320                            .emit()
 321
 322                 }
 323                 Err(CopyImplementationError::InfrigingVariant(name)) => {
 324                     let item = tcx.map.expect_item(impl_node_id);
 325                     let span = if let ItemImpl(_, _, _, Some(ref tr), _, _) = item.node {
 326                         tr.path.span
 327                     } else {
 328                         span
 329                     };
 330
 331                     struct_span_err!(tcx.sess, span, E0205,
 332                                      "the trait `Copy` may not be implemented for this type")
 333                         .span_label(span, &format!("variant `{}` does not implement `Copy`",
 334                                                    name))
 335                         .emit()
 336                 }
 337                 Err(CopyImplementationError::NotAnAdt) => {
 338                     let item = tcx.map.expect_item(impl_node_id);
 339                     let span = if let ItemImpl(_, _, _, _, ref ty, _) = item.node {
 340                         ty.span
 341                     } else {
 342                         span
 343                     };
 344
 345                     struct_span_err!(tcx.sess, span, E0206,
 346                                      "the trait `Copy` may not be implemented for this type")
 347                         .span_label(span, &format!("type is not a structure or enumeration"))
 348                         .emit();
 349                 }
 350                 Err(CopyImplementationError::HasDestructor) => {
 351                     struct_span_err!(tcx.sess, span, E0184,
 352                               "the trait `Copy` may not be implemented for this type; \
 353                                the type has a destructor")
 354                         .span_label(span, &format!("Copy not allowed on types with destructors"))
 355                         .emit();
 356                 }
 357             }
 358         });
 359     }
 360
 361     /// Process implementations of the built-in trait `CoerceUnsized`.
 362     fn check_implementations_of_coerce_unsized(&self) {
 363         let tcx = self.crate_context.tcx;
 364         let coerce_unsized_trait = match tcx.lang_items.coerce_unsized_trait() {
 365             Some(id) => id,
 366             None => return,
 367         };
 368         let unsize_trait = match tcx.lang_items.require(UnsizeTraitLangItem) {
 369             Ok(id) => id,
 370             Err(err) => {
 371                 tcx.sess.fatal(&format!("`CoerceUnsized` implementation {}", err));
 372             }
 373         };
 374
 375         let trait_def = tcx.lookup_trait_def(coerce_unsized_trait);
 376
 377         trait_def.for_each_impl(tcx, |impl_did| {
 378             debug!("check_implementations_of_coerce_unsized: impl_did={:?}",
 379                    impl_did);
 380
 381             let impl_node_id = if let Some(n) = tcx.map.as_local_node_id(impl_did) {
 382                 n
 383             } else {
 384                 debug!("check_implementations_of_coerce_unsized(): impl not \
 385                         in this crate");
 386                 return;
 387             };
 388
 389             let source = tcx.lookup_item_type(impl_did).ty;
 390             let trait_ref = self.crate_context.tcx.impl_trait_ref(impl_did).unwrap();
 391             let target = trait_ref.substs.type_at(1);
 392             debug!("check_implementations_of_coerce_unsized: {:?} -> {:?} (bound)",
 393                    source, target);
 394
 395             let span = tcx.map.span(impl_node_id);
 396             let param_env = ParameterEnvironment::for_item(tcx, impl_node_id);
 397             let source = source.subst(tcx, &param_env.free_substs);
 398             let target = target.subst(tcx, &param_env.free_substs);
 399             assert!(!source.has_escaping_regions());
 400
 401             debug!("check_implementations_of_coerce_unsized: {:?} -> {:?} (free)",
 402                    source, target);
 403
 404             tcx.infer_ctxt(None, Some(param_env), Reveal::ExactMatch).enter(|infcx| {
 405                 let origin = TypeOrigin::Misc(span);
 406                 let check_mutbl = |mt_a: ty::TypeAndMut<'gcx>, mt_b: ty::TypeAndMut<'gcx>,
 407                                    mk_ptr: &Fn(Ty<'gcx>) -> Ty<'gcx>| {
 408                     if (mt_a.mutbl, mt_b.mutbl) == (hir::MutImmutable, hir::MutMutable) {
 409                         infcx.report_mismatched_types(origin, mk_ptr(mt_b.ty),
 410                                                       target, ty::error::TypeError::Mutability);
 411                     }
 412                     (mt_a.ty, mt_b.ty, unsize_trait, None)
 413                 };
 414                 let (source, target, trait_def_id, kind) = match (&source.sty, &target.sty) {
 415                     (&ty::TyBox(a), &ty::TyBox(b)) => (a, b, unsize_trait, None),
 416
 417                     (&ty::TyRef(r_a, mt_a), &ty::TyRef(r_b, mt_b)) => {
 418                         infcx.sub_regions(infer::RelateObjectBound(span), r_b, r_a);
 419                         check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ref(r_b, ty))
 420                     }
 421
 422                     (&ty::TyRef(_, mt_a), &ty::TyRawPtr(mt_b)) |
 423                     (&ty::TyRawPtr(mt_a), &ty::TyRawPtr(mt_b)) => {
 424                         check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ptr(ty))
 425                     }
 426
 427                     (&ty::TyStruct(def_a, substs_a), &ty::TyStruct(def_b, substs_b)) => {
 428                         if def_a != def_b {
 429                             let source_path = tcx.item_path_str(def_a.did);
 430                             let target_path = tcx.item_path_str(def_b.did);
 431                             span_err!(tcx.sess, span, E0377,
 432                                       "the trait `CoerceUnsized` may only be implemented \
 433                                        for a coercion between structures with the same \
 434                                        definition; expected {}, found {}",
 435                                       source_path, target_path);
 436                             return;
 437                         }
 438
 439                         let fields = &def_a.struct_variant().fields;
 440                         let diff_fields = fields.iter().enumerate().filter_map(|(i, f)| {
 441                             let (a, b) = (f.ty(tcx, substs_a), f.ty(tcx, substs_b));
 442
 443                             if f.unsubst_ty().is_phantom_data() {
 444                                 // Ignore PhantomData fields
 445                                 None
 446                             } else if infcx.sub_types(false, origin, b, a).is_ok() {
 447                                 // Ignore fields that aren't significantly changed
 448                                 None
 449                             } else {
 450                                 // Collect up all fields that were significantly changed
 451                                 // i.e. those that contain T in coerce_unsized T -> U
 452                                 Some((i, a, b))
 453                             }
 454                         }).collect::<Vec<_>>();
 455
 456                         if diff_fields.is_empty() {
 457                             span_err!(tcx.sess, span, E0374,
 458                                       "the trait `CoerceUnsized` may only be implemented \
 459                                        for a coercion between structures with one field \
 460                                        being coerced, none found");
 461                             return;
 462                         } else if diff_fields.len() > 1 {
 463                             let item = tcx.map.expect_item(impl_node_id);
 464                             let span = if let ItemImpl(_, _, _, Some(ref t), _, _) = item.node {
 465                                 t.path.span
 466                             } else {
 467                                 tcx.map.span(impl_node_id)
 468                             };
 469
 470                             let mut err = struct_span_err!(tcx.sess, span, E0375,
 471                                       "implementing the trait `CoerceUnsized` \
 472                                        requires multiple coercions");
 473                             err.note("`CoerceUnsized` may only be implemented for \
 474                                       a coercion between structures with one field being coerced");
 475                             err.note(&format!("currently, {} fields need coercions: {}",
 476                                              diff_fields.len(),
 477                                              diff_fields.iter().map(|&(i, a, b)| {
 478                                                 format!("{} ({} to {})", fields[i].name, a, b)
 479                                              }).collect::<Vec<_>>().join(", ") ));
 480                             err.span_label(span, &format!("requires multiple coercions"));
 481                             err.emit();
 482                             return;
 483                         }
 484
 485                         let (i, a, b) = diff_fields[0];
 486                         let kind = ty::adjustment::CustomCoerceUnsized::Struct(i);
 487                         (a, b, coerce_unsized_trait, Some(kind))
 488                     }
 489
 490                     _ => {
 491                         span_err!(tcx.sess, span, E0376,
 492                                   "the trait `CoerceUnsized` may only be implemented \
 493                                    for a coercion between structures");
 494                         return;
 495                     }
 496                 };
 497
 498                 let mut fulfill_cx = traits::FulfillmentContext::new();
 499
 500                 // Register an obligation for `A: Trait<B>`.
 501                 let cause = traits::ObligationCause::misc(span, impl_node_id);
 502                 let predicate = tcx.predicate_for_trait_def(cause, trait_def_id, 0,
 503                                                             source, &[target]);
 504                 fulfill_cx.register_predicate_obligation(&infcx, predicate);
 505
 506                 // Check that all transitive obligations are satisfied.
 507                 if let Err(errors) = fulfill_cx.select_all_or_error(&infcx) {
 508                     infcx.report_fulfillment_errors(&errors);
 509                 }
 510
 511                 // Finally, resolve all regions.
 512                 let mut free_regions = FreeRegionMap::new();
 513                 free_regions.relate_free_regions_from_predicates(
 514                     &infcx.parameter_environment.caller_bounds);
 515                 infcx.resolve_regions_and_report_errors(&free_regions, impl_node_id);
 516
 517                 if let Some(kind) = kind {
 518                     tcx.custom_coerce_unsized_kinds.borrow_mut().insert(impl_did, kind);
 519                 }
 520             });
 521         });
 522     }
 523 }
 524
 525 fn enforce_trait_manually_implementable(tcx: TyCtxt, sp: Span, trait_def_id: DefId) {
 526     if tcx.sess.features.borrow().unboxed_closures {
 527         // the feature gate allows all of them
 528         return
 529     }
 530     let did = Some(trait_def_id);
 531     let li = &tcx.lang_items;
 532
 533     let trait_name = if did == li.fn_trait() {
 534         "Fn"
 535     } else if did == li.fn_mut_trait() {
 536         "FnMut"
 537     } else if did == li.fn_once_trait() {
 538         "FnOnce"
 539     } else {
 540         return // everything OK
 541     };
 542     let mut err = struct_span_err!(tcx.sess,
 543                                    sp,
 544                                    E0183,
 545                                    "manual implementations of `{}` are experimental",
 546                                    trait_name);
 547     help!(&mut err, "add `#![feature(unboxed_closures)]` to the crate attributes to enable");
 548     err.emit();
 549 }
 550
 551 pub fn check_coherence(ccx: &CrateCtxt) {
 552     let _task = ccx.tcx.dep_graph.in_task(DepNode::Coherence);
 553     ccx.tcx.infer_ctxt(None, None, Reveal::ExactMatch).enter(|infcx| {
 554         CoherenceChecker {
 555             crate_context: ccx,
 556             inference_context: infcx,
 557             inherent_impls: RefCell::new(FnvHashMap()),
 558         }.check();
 559     });
 560     unsafety::check(ccx.tcx);
 561     orphan::check(ccx.tcx);
 562     overlap::check(ccx.tcx);
 563 }