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