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