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