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