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