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 metadata::csearch::{each_impl, get_impl_trait};
  20 use metadata::csearch;
  21 use middle::subst::{self, Subst};
  22 use middle::ty::RegionEscape;
  23 use middle::ty::{ImplContainer, ImplOrTraitItemId, ConstTraitItemId};
  24 use middle::ty::{MethodTraitItemId, TypeTraitItemId};
  25 use middle::ty::{ParameterEnvironment, lookup_item_type};
  26 use middle::ty::{Ty, ty_bool, ty_char, ty_enum, ty_err};
  27 use middle::ty::{ty_param, TypeScheme, ty_ptr};
  28 use middle::ty::{ty_rptr, ty_struct, ty_trait, ty_tup};
  29 use middle::ty::{ty_str, ty_vec, ty_float, ty_infer, ty_int};
  30 use middle::ty::{ty_uint, ty_closure, ty_uniq, ty_bare_fn};
  31 use middle::ty::ty_projection;
  32 use middle::ty;
  33 use CrateCtxt;
  34 use middle::infer::InferCtxt;
  35 use middle::infer::new_infer_ctxt;
  36 use std::collections::HashSet;
  37 use std::cell::RefCell;
  38 use std::rc::Rc;
  39 use syntax::ast::{Crate, DefId};
  40 use syntax::ast::{Item, ItemImpl};
  41 use syntax::ast::{LOCAL_CRATE, TraitRef};
  42 use syntax::ast;
  43 use syntax::ast_map::NodeItem;
  44 use syntax::ast_map;
  45 use syntax::ast_util::local_def;
  46 use syntax::codemap::Span;
  47 use syntax::parse::token;
  48 use syntax::visit;
  49 use util::nodemap::{DefIdMap, FnvHashMap};
  50 use util::ppaux::Repr;
  51
  52 mod orphan;
  53 mod overlap;
  54 mod unsafety;
  55
  56 // Returns the def ID of the base type, if there is one.
  57 fn get_base_type_def_id<'a, 'tcx>(inference_context: &InferCtxt<'a, 'tcx>,
  58                                   span: Span,
  59                                   ty: Ty<'tcx>)
  60                                   -> Option<DefId> {
  61     match ty.sty {
  62         ty_enum(def_id, _) |
  63         ty_struct(def_id, _) => {
  64             Some(def_id)
  65         }
  66
  67         ty_trait(ref t) => {
  68             Some(t.principal_def_id())
  69         }
  70
  71         ty_uniq(_) => {
  72             inference_context.tcx.lang_items.owned_box()
  73         }
  74
  75         ty_bool | ty_char | ty_int(..) | ty_uint(..) | ty_float(..) |
  76         ty_str(..) | ty_vec(..) | ty_bare_fn(..) | ty_tup(..) |
  77         ty_param(..) | ty_err |
  78         ty_ptr(_) | ty_rptr(_, _) | ty_projection(..) => {
  79             None
  80         }
  81
  82         ty_infer(..) | ty_closure(..) => {
  83             // `ty` comes from a user declaration so we should only expect types
  84             // that the user can type
  85             inference_context.tcx.sess.span_bug(
  86                 span,
  87                 &format!("coherence encountered unexpected type searching for base type: {}",
  88                         ty.repr(inference_context.tcx)));
  89         }
  90     }
  91 }
  92
  93 struct CoherenceChecker<'a, 'tcx: 'a> {
  94     crate_context: &'a CrateCtxt<'a, 'tcx>,
  95     inference_context: InferCtxt<'a, 'tcx>,
  96     inherent_impls: RefCell<DefIdMap<Rc<RefCell<Vec<ast::DefId>>>>>,
  97 }
  98
  99 struct CoherenceCheckVisitor<'a, 'tcx: 'a> {
 100     cc: &'a CoherenceChecker<'a, 'tcx>
 101 }
 102
 103 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CoherenceCheckVisitor<'a, 'tcx> {
 104     fn visit_item(&mut self, item: &Item) {
 105
 106         //debug!("(checking coherence) item '{}'", token::get_ident(item.ident));
 107
 108         if let ItemImpl(_, _, _, ref opt_trait, _, _) = item.node {
 109             self.cc.check_implementation(item, opt_trait.as_ref())
 110         }
 111
 112         visit::walk_item(self, item);
 113     }
 114 }
 115
 116 impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
 117     fn check(&self, krate: &Crate) {
 118         // Check implementations and traits. This populates the tables
 119         // containing the inherent methods and extension methods. It also
 120         // builds up the trait inheritance table.
 121         let mut visitor = CoherenceCheckVisitor { cc: self };
 122         visit::walk_crate(&mut visitor, krate);
 123
 124         // Copy over the inherent impls we gathered up during the walk into
 125         // the tcx.
 126         let mut tcx_inherent_impls =
 127             self.crate_context.tcx.inherent_impls.borrow_mut();
 128         for (k, v) in &*self.inherent_impls.borrow() {
 129             tcx_inherent_impls.insert((*k).clone(),
 130                                       Rc::new((*v.borrow()).clone()));
 131         }
 132
 133         // Bring in external crates. It's fine for this to happen after the
 134         // coherence checks, because we ensure by construction that no errors
 135         // can happen at link time.
 136         self.add_external_crates();
 137
 138         // Populate the table of destructors. It might seem a bit strange to
 139         // do this here, but it's actually the most convenient place, since
 140         // the coherence tables contain the trait -> type mappings.
 141         self.populate_destructor_table();
 142
 143         // Check to make sure implementations of `Copy` are legal.
 144         self.check_implementations_of_copy();
 145     }
 146
 147     fn check_implementation(&self, item: &Item, opt_trait: Option<&TraitRef>) {
 148         let tcx = self.crate_context.tcx;
 149         let impl_did = local_def(item.id);
 150         let self_type = ty::lookup_item_type(tcx, impl_did);
 151
 152         // If there are no traits, then this implementation must have a
 153         // base type.
 154
 155         let impl_items = self.create_impl_from_item(item);
 156
 157         if opt_trait.is_some() {
 158             let trait_ref = ty::impl_id_to_trait_ref(self.crate_context.tcx, item.id);
 159             debug!("(checking implementation) adding impl for trait '{}', item '{}'",
 160                    trait_ref.repr(self.crate_context.tcx),
 161                    token::get_ident(item.ident));
 162
 163             enforce_trait_manually_implementable(self.crate_context.tcx,
 164                                                  item.span,
 165                                                  trait_ref.def_id);
 166             self.add_trait_impl(trait_ref.def_id, impl_did);
 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         match get_base_type_def_id(&self.inference_context,
 173                                    item.span,
 174                                    self_type.ty) {
 175             None => {
 176                 // Nothing to do.
 177             }
 178             Some(base_type_def_id) => {
 179                 // FIXME: Gather up default methods?
 180                 if opt_trait.is_none() {
 181                     self.add_inherent_impl(base_type_def_id, impl_did);
 182                 }
 183             }
 184         }
 185
 186         tcx.impl_items.borrow_mut().insert(impl_did, impl_items);
 187     }
 188
 189     // Creates default method IDs and performs type substitutions for an impl
 190     // and trait pair. Then, for each provided method in the trait, inserts a
 191     // `ProvidedMethodInfo` instance into the `provided_method_sources` map.
 192     fn instantiate_default_methods(
 193             &self,
 194             impl_id: DefId,
 195             trait_ref: &ty::TraitRef<'tcx>,
 196             all_impl_items: &mut Vec<ImplOrTraitItemId>) {
 197         let tcx = self.crate_context.tcx;
 198         debug!("instantiate_default_methods(impl_id={:?}, trait_ref={})",
 199                impl_id, trait_ref.repr(tcx));
 200
 201         let impl_type_scheme = ty::lookup_item_type(tcx, impl_id);
 202
 203         let prov = ty::provided_trait_methods(tcx, trait_ref.def_id);
 204         for trait_method in &prov {
 205             // Synthesize an ID.
 206             let new_id = tcx.sess.next_node_id();
 207             let new_did = local_def(new_id);
 208
 209             debug!("new_did={:?} trait_method={}", new_did, trait_method.repr(tcx));
 210
 211             // Create substitutions for the various trait parameters.
 212             let new_method_ty =
 213                 Rc::new(subst_receiver_types_in_method_ty(
 214                     tcx,
 215                     impl_id,
 216                     &impl_type_scheme,
 217                     trait_ref,
 218                     new_did,
 219                     &**trait_method,
 220                     Some(trait_method.def_id)));
 221
 222             debug!("new_method_ty={}", new_method_ty.repr(tcx));
 223             all_impl_items.push(MethodTraitItemId(new_did));
 224
 225             // construct the polytype for the method based on the
 226             // method_ty.  it will have all the generics from the
 227             // impl, plus its own.
 228             let new_polytype = ty::TypeScheme {
 229                 generics: new_method_ty.generics.clone(),
 230                 ty: ty::mk_bare_fn(tcx, Some(new_did),
 231                                    tcx.mk_bare_fn(new_method_ty.fty.clone()))
 232             };
 233             debug!("new_polytype={}", new_polytype.repr(tcx));
 234
 235             tcx.tcache.borrow_mut().insert(new_did, new_polytype);
 236             tcx.predicates.borrow_mut().insert(new_did, new_method_ty.predicates.clone());
 237             tcx.impl_or_trait_items
 238                .borrow_mut()
 239                .insert(new_did, ty::MethodTraitItem(new_method_ty));
 240
 241             // Pair the new synthesized ID up with the
 242             // ID of the method.
 243             self.crate_context.tcx.provided_method_sources.borrow_mut()
 244                 .insert(new_did, trait_method.def_id);
 245         }
 246     }
 247
 248     fn add_inherent_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
 249         match self.inherent_impls.borrow().get(&base_def_id) {
 250             Some(implementation_list) => {
 251                 implementation_list.borrow_mut().push(impl_def_id);
 252                 return;
 253             }
 254             None => {}
 255         }
 256
 257         self.inherent_impls.borrow_mut().insert(
 258             base_def_id,
 259             Rc::new(RefCell::new(vec!(impl_def_id))));
 260     }
 261
 262     fn add_trait_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
 263         debug!("add_trait_impl: base_def_id={:?} impl_def_id={:?}",
 264                base_def_id, impl_def_id);
 265         ty::record_trait_implementation(self.crate_context.tcx,
 266                                         base_def_id,
 267                                         impl_def_id);
 268     }
 269
 270     fn get_self_type_for_implementation(&self, impl_did: DefId)
 271                                         -> TypeScheme<'tcx> {
 272         self.crate_context.tcx.tcache.borrow().get(&impl_did).unwrap().clone()
 273     }
 274
 275     // Converts an implementation in the AST to a vector of items.
 276     fn create_impl_from_item(&self, item: &Item) -> Vec<ImplOrTraitItemId> {
 277         match item.node {
 278             ItemImpl(_, _, _, ref opt_trait, _, ref impl_items) => {
 279                 let mut items: Vec<ImplOrTraitItemId> =
 280                         impl_items.iter().map(|impl_item| {
 281                     match impl_item.node {
 282                         ast::ConstImplItem(..) => {
 283                             ConstTraitItemId(local_def(impl_item.id))
 284                         }
 285                         ast::MethodImplItem(..) => {
 286                             MethodTraitItemId(local_def(impl_item.id))
 287                         }
 288                         ast::TypeImplItem(_) => {
 289                             TypeTraitItemId(local_def(impl_item.id))
 290                         }
 291                         ast::MacImplItem(_) => {
 292                             self.crate_context.tcx.sess.span_bug(impl_item.span,
 293                                                                  "unexpanded macro");
 294                         }
 295                     }
 296                 }).collect();
 297
 298                 if opt_trait.is_some() {
 299                     let trait_ref = ty::impl_id_to_trait_ref(self.crate_context.tcx,
 300                                                              item.id);
 301
 302                     self.instantiate_default_methods(local_def(item.id),
 303                                                      &*trait_ref,
 304                                                      &mut items);
 305                 }
 306
 307                 items
 308             }
 309             _ => {
 310                 self.crate_context.tcx.sess.span_bug(item.span,
 311                                                      "can't convert a non-impl to an impl");
 312             }
 313         }
 314     }
 315
 316     // External crate handling
 317
 318     fn add_external_impl(&self,
 319                          impls_seen: &mut HashSet<DefId>,
 320                          impl_def_id: DefId) {
 321         let tcx = self.crate_context.tcx;
 322         let impl_items = csearch::get_impl_items(&tcx.sess.cstore,
 323                                                  impl_def_id);
 324
 325         // Make sure we don't visit the same implementation multiple times.
 326         if !impls_seen.insert(impl_def_id) {
 327             // Skip this one.
 328             return
 329         }
 330         // Good. Continue.
 331
 332         let _ = lookup_item_type(tcx, impl_def_id);
 333         let associated_traits = get_impl_trait(tcx, impl_def_id);
 334
 335         // Do a sanity check.
 336         assert!(associated_traits.is_some());
 337
 338         // Record all the trait items.
 339         if let Some(trait_ref) = associated_traits {
 340             self.add_trait_impl(trait_ref.def_id, impl_def_id);
 341         }
 342
 343         // For any methods that use a default implementation, add them to
 344         // the map. This is a bit unfortunate.
 345         for item_def_id in &impl_items {
 346             let impl_item = ty::impl_or_trait_item(tcx, item_def_id.def_id());
 347             match impl_item {
 348                 ty::MethodTraitItem(ref method) => {
 349                     if let Some(source) = method.provided_source {
 350                         tcx.provided_method_sources
 351                            .borrow_mut()
 352                            .insert(item_def_id.def_id(), source);
 353                     }
 354                 }
 355                 _ => {}
 356             }
 357         }
 358
 359         tcx.impl_items.borrow_mut().insert(impl_def_id, impl_items);
 360     }
 361
 362     // Adds implementations and traits from external crates to the coherence
 363     // info.
 364     fn add_external_crates(&self) {
 365         let mut impls_seen = HashSet::new();
 366
 367         let crate_store = &self.crate_context.tcx.sess.cstore;
 368         crate_store.iter_crate_data(|crate_number, _crate_metadata| {
 369             each_impl(crate_store, crate_number, |def_id| {
 370                 assert_eq!(crate_number, def_id.krate);
 371                 self.add_external_impl(&mut impls_seen, def_id)
 372             })
 373         })
 374     }
 375
 376     //
 377     // Destructors
 378     //
 379
 380     fn populate_destructor_table(&self) {
 381         let tcx = self.crate_context.tcx;
 382         let drop_trait = match tcx.lang_items.drop_trait() {
 383             Some(id) => id, None => { return }
 384         };
 385
 386         let impl_items = tcx.impl_items.borrow();
 387         let trait_impls = match tcx.trait_impls.borrow().get(&drop_trait).cloned() {
 388             None => return, // No types with (new-style) dtors present.
 389             Some(found_impls) => found_impls
 390         };
 391
 392         for &impl_did in &*trait_impls.borrow() {
 393             let items = impl_items.get(&impl_did).unwrap();
 394             if items.is_empty() {
 395                 // We'll error out later. For now, just don't ICE.
 396                 continue;
 397             }
 398             let method_def_id = items[0];
 399
 400             let self_type = self.get_self_type_for_implementation(impl_did);
 401             match self_type.ty.sty {
 402                 ty::ty_enum(type_def_id, _) |
 403                 ty::ty_struct(type_def_id, _) |
 404                 ty::ty_closure(type_def_id, _) => {
 405                     tcx.destructor_for_type
 406                        .borrow_mut()
 407                        .insert(type_def_id, method_def_id.def_id());
 408                     tcx.destructors
 409                        .borrow_mut()
 410                        .insert(method_def_id.def_id());
 411                 }
 412                 _ => {
 413                     // Destructors only work on nominal types.
 414                     if impl_did.krate == ast::LOCAL_CRATE {
 415                         {
 416                             match tcx.map.find(impl_did.node) {
 417                                 Some(ast_map::NodeItem(item)) => {
 418                                     span_err!(tcx.sess, item.span, E0120,
 419                                         "the Drop trait may only be implemented on structures");
 420                                 }
 421                                 _ => {
 422                                     tcx.sess.bug("didn't find impl in ast \
 423                                                   map");
 424                                 }
 425                             }
 426                         }
 427                     } else {
 428                         tcx.sess.bug("found external impl of Drop trait on \
 429                                       something other than a struct");
 430                     }
 431                 }
 432             }
 433         }
 434     }
 435
 436     /// Ensures that implementations of the built-in trait `Copy` are legal.
 437     fn check_implementations_of_copy(&self) {
 438         let tcx = self.crate_context.tcx;
 439         let copy_trait = match tcx.lang_items.copy_trait() {
 440             Some(id) => id,
 441             None => return,
 442         };
 443
 444         let trait_impls = match tcx.trait_impls
 445                                    .borrow()
 446                                    .get(&copy_trait)
 447                                    .cloned() {
 448             None => {
 449                 debug!("check_implementations_of_copy(): no types with \
 450                         implementations of `Copy` found");
 451                 return
 452             }
 453             Some(found_impls) => found_impls
 454         };
 455
 456         // Clone first to avoid a double borrow error.
 457         let trait_impls = trait_impls.borrow().clone();
 458
 459         for &impl_did in &trait_impls {
 460             debug!("check_implementations_of_copy: impl_did={}",
 461                    impl_did.repr(tcx));
 462
 463             if impl_did.krate != ast::LOCAL_CRATE {
 464                 debug!("check_implementations_of_copy(): impl not in this \
 465                         crate");
 466                 continue
 467             }
 468
 469             let self_type = self.get_self_type_for_implementation(impl_did);
 470             debug!("check_implementations_of_copy: self_type={} (bound)",
 471                    self_type.repr(tcx));
 472
 473             let span = tcx.map.span(impl_did.node);
 474             let param_env = ParameterEnvironment::for_item(tcx, impl_did.node);
 475             let self_type = self_type.ty.subst(tcx, &param_env.free_substs);
 476             assert!(!self_type.has_escaping_regions());
 477
 478             debug!("check_implementations_of_copy: self_type={} (free)",
 479                    self_type.repr(tcx));
 480
 481             match ty::can_type_implement_copy(&param_env, span, self_type) {
 482                 Ok(()) => {}
 483                 Err(ty::FieldDoesNotImplementCopy(name)) => {
 484                        span_err!(tcx.sess, span, E0204,
 485                                  "the trait `Copy` may not be \
 486                                           implemented for this type; field \
 487                                           `{}` does not implement `Copy`",
 488                                          token::get_name(name))
 489                 }
 490                 Err(ty::VariantDoesNotImplementCopy(name)) => {
 491                        span_err!(tcx.sess, span, E0205,
 492                                  "the trait `Copy` may not be \
 493                                           implemented for this type; variant \
 494                                           `{}` does not implement `Copy`",
 495                                          token::get_name(name))
 496                 }
 497                 Err(ty::TypeIsStructural) => {
 498                        span_err!(tcx.sess, span, E0206,
 499                                  "the trait `Copy` may not be implemented \
 500                                   for this type; type is not a structure or \
 501                                   enumeration")
 502                 }
 503                 Err(ty::TypeHasDestructor) => {
 504                     span_err!(tcx.sess, span, E0184,
 505                               "the trait `Copy` may not be implemented for this type; \
 506                                the type has a destructor");
 507                 }
 508             }
 509         }
 510     }
 511 }
 512
 513 fn enforce_trait_manually_implementable(tcx: &ty::ctxt, sp: Span, trait_def_id: ast::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     span_err!(tcx.sess, sp, E0183, "manual implementations of `{}` are experimental", trait_name);
 531     fileline_help!(tcx.sess, sp,
 532                "add `#![feature(unboxed_closures)]` to the crate attributes to enable");
 533 }
 534
 535 fn subst_receiver_types_in_method_ty<'tcx>(tcx: &ty::ctxt<'tcx>,
 536                                            impl_id: ast::DefId,
 537                                            impl_type_scheme: &ty::TypeScheme<'tcx>,
 538                                            trait_ref: &ty::TraitRef<'tcx>,
 539                                            new_def_id: ast::DefId,
 540                                            method: &ty::Method<'tcx>,
 541                                            provided_source: Option<ast::DefId>)
 542                                            -> ty::Method<'tcx>
 543 {
 544     let combined_substs = ty::make_substs_for_receiver_types(tcx, trait_ref, method);
 545
 546     debug!("subst_receiver_types_in_method_ty: combined_substs={}",
 547            combined_substs.repr(tcx));
 548
 549     let method_predicates = method.predicates.subst(tcx, &combined_substs);
 550     let mut method_generics = method.generics.subst(tcx, &combined_substs);
 551
 552     // replace the type parameters declared on the trait with those
 553     // from the impl
 554     for &space in &[subst::TypeSpace, subst::SelfSpace] {
 555         method_generics.types.replace(
 556             space,
 557             impl_type_scheme.generics.types.get_slice(space).to_vec());
 558         method_generics.regions.replace(
 559             space,
 560             impl_type_scheme.generics.regions.get_slice(space).to_vec());
 561     }
 562
 563     debug!("subst_receiver_types_in_method_ty: method_generics={}",
 564            method_generics.repr(tcx));
 565
 566     let method_fty = method.fty.subst(tcx, &combined_substs);
 567
 568     debug!("subst_receiver_types_in_method_ty: method_ty={}",
 569            method.fty.repr(tcx));
 570
 571     ty::Method::new(
 572         method.name,
 573         method_generics,
 574         method_predicates,
 575         method_fty,
 576         method.explicit_self,
 577         method.vis,
 578         new_def_id,
 579         ImplContainer(impl_id),
 580         provided_source
 581     )
 582 }
 583
 584 pub fn check_coherence(crate_context: &CrateCtxt) {
 585     CoherenceChecker {
 586         crate_context: crate_context,
 587         inference_context: new_infer_ctxt(crate_context.tcx),
 588         inherent_impls: RefCell::new(FnvHashMap()),
 589     }.check(crate_context.tcx.map.krate());
 590     unsafety::check(crate_context.tcx);
 591     orphan::check(crate_context.tcx);
 592     overlap::check(crate_context.tcx);
 593 }