src/librustc/middle/typeck/coherence.rs

   1 // Copyright 2012-2013 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 each trait
  14 // has at most one implementation for each type. Then we build a mapping from
  15 // each trait in the system to its implementations.
  16
  17
  18 use metadata::csearch::{each_impl, get_impl_trait, each_implementation_for_trait};
  19 use metadata::csearch;
  20 use middle::ty::get;
  21 use middle::ty::{ImplContainer, lookup_item_type, subst};
  22 use middle::ty::{substs, t, ty_bool, ty_char, ty_bot, ty_box, ty_enum, ty_err};
  23 use middle::ty::{ty_str, ty_vec, ty_float, ty_infer, ty_int, ty_nil};
  24 use middle::ty::{ty_param, ty_param_bounds_and_ty, ty_ptr};
  25 use middle::ty::{ty_rptr, ty_self, ty_struct, ty_trait, ty_tup};
  26 use middle::ty::{ty_uint, ty_uniq, ty_bare_fn, ty_closure};
  27 use middle::ty::type_is_ty_var;
  28 use middle::subst::Subst;
  29 use middle::ty;
  30 use middle::typeck::CrateCtxt;
  31 use middle::typeck::infer::combine::Combine;
  32 use middle::typeck::infer::InferCtxt;
  33 use middle::typeck::infer::{new_infer_ctxt, resolve_ivar, resolve_type};
  34 use middle::typeck::infer;
  35 use util::ppaux::Repr;
  36 use syntax::ast::{Crate, DefId, DefStruct, DefTy};
  37 use syntax::ast::{Item, ItemEnum, ItemImpl, ItemMod, ItemStruct};
  38 use syntax::ast::{LOCAL_CRATE, TraitRef, TyPath};
  39 use syntax::ast;
  40 use syntax::ast_map::NodeItem;
  41 use syntax::ast_map;
  42 use syntax::ast_util::{def_id_of_def, local_def};
  43 use syntax::codemap::Span;
  44 use syntax::owned_slice::OwnedSlice;
  45 use syntax::parse::token;
  46 use syntax::visit;
  47
  48 use collections::HashSet;
  49 use std::cell::RefCell;
  50 use std::rc::Rc;
  51
  52 struct UniversalQuantificationResult {
  53     monotype: t,
  54     type_variables: Vec<ty::t> ,
  55     type_param_defs: Rc<Vec<ty::TypeParameterDef> >
  56 }
  57
  58 fn get_base_type(inference_context: &InferCtxt,
  59                  span: Span,
  60                  original_type: t)
  61                  -> Option<t> {
  62     let resolved_type;
  63     match resolve_type(inference_context,
  64                        original_type,
  65                        resolve_ivar) {
  66         Ok(resulting_type) if !type_is_ty_var(resulting_type) => {
  67             resolved_type = resulting_type;
  68         }
  69         _ => {
  70             inference_context.tcx.sess.span_fatal(span,
  71                                                   "the type of this value must be known in order \
  72                                                    to determine the base type");
  73         }
  74     }
  75
  76     match get(resolved_type).sty {
  77         ty_enum(..) | ty_trait(..) | ty_struct(..) => {
  78             debug!("(getting base type) found base type");
  79             Some(resolved_type)
  80         }
  81
  82         ty_nil | ty_bot | ty_bool | ty_char | ty_int(..) | ty_uint(..) | ty_float(..) |
  83         ty_str(..) | ty_vec(..) | ty_bare_fn(..) | ty_closure(..) | ty_tup(..) |
  84         ty_infer(..) | ty_param(..) | ty_self(..) | ty_err |
  85         ty_box(_) | ty_uniq(_) | ty_ptr(_) | ty_rptr(_, _) => {
  86             debug!("(getting base type) no base type; found {:?}",
  87                    get(original_type).sty);
  88             None
  89         }
  90     }
  91 }
  92
  93 fn type_is_defined_in_local_crate(original_type: t) -> bool {
  94     /*!
  95      *
  96      * For coherence, when we have `impl Trait for Type`, we need to
  97      * guarantee that `Type` is "local" to the
  98      * crate.  For our purposes, this means that it must contain
  99      * some nominal type defined in this crate.
 100      */
 101
 102     let mut found_nominal = false;
 103     ty::walk_ty(original_type, |t| {
 104         match get(t).sty {
 105             ty_enum(def_id, _) |
 106             ty_trait(box ty::TyTrait { def_id, .. }) |
 107             ty_struct(def_id, _) => {
 108                 if def_id.krate == ast::LOCAL_CRATE {
 109                     found_nominal = true;
 110                 }
 111             }
 112
 113             _ => { }
 114         }
 115     });
 116     return found_nominal;
 117 }
 118
 119 // Returns the def ID of the base type, if there is one.
 120 fn get_base_type_def_id(inference_context: &InferCtxt,
 121                         span: Span,
 122                         original_type: t)
 123                         -> Option<DefId> {
 124     match get_base_type(inference_context, span, original_type) {
 125         None => {
 126             return None;
 127         }
 128         Some(base_type) => {
 129             match get(base_type).sty {
 130                 ty_enum(def_id, _) |
 131                 ty_struct(def_id, _) |
 132                 ty_trait(box ty::TyTrait { def_id, .. }) => {
 133                     return Some(def_id);
 134                 }
 135                 _ => {
 136                     fail!("get_base_type() returned a type that wasn't an \
 137                            enum, struct, or trait");
 138                 }
 139             }
 140         }
 141     }
 142 }
 143
 144 struct CoherenceChecker<'a> {
 145     crate_context: &'a CrateCtxt<'a>,
 146     inference_context: InferCtxt<'a>,
 147 }
 148
 149 struct CoherenceCheckVisitor<'a> {
 150     cc: &'a CoherenceChecker<'a>
 151 }
 152
 153 impl<'a> visit::Visitor<()> for CoherenceCheckVisitor<'a> {
 154     fn visit_item(&mut self, item: &Item, _: ()) {
 155
 156         //debug!("(checking coherence) item '{}'", token::get_ident(item.ident));
 157
 158         match item.node {
 159             ItemImpl(_, ref opt_trait, _, _) => {
 160                 match opt_trait.clone() {
 161                     Some(opt_trait) => {
 162                         self.cc.check_implementation(item, [opt_trait]);
 163                     }
 164                     None => self.cc.check_implementation(item, [])
 165                 }
 166             }
 167             _ => {
 168                 // Nothing to do.
 169             }
 170         };
 171
 172         visit::walk_item(self, item, ());
 173     }
 174 }
 175
 176 struct PrivilegedScopeVisitor<'a> { cc: &'a CoherenceChecker<'a> }
 177
 178 impl<'a> visit::Visitor<()> for PrivilegedScopeVisitor<'a> {
 179     fn visit_item(&mut self, item: &Item, _: ()) {
 180
 181         match item.node {
 182             ItemMod(ref module_) => {
 183                 // Then visit the module items.
 184                 visit::walk_mod(self, module_, ());
 185             }
 186             ItemImpl(_, None, ast_ty, _) => {
 187                 if !self.cc.ast_type_is_defined_in_local_crate(ast_ty) {
 188                     // This is an error.
 189                     let session = &self.cc.crate_context.tcx.sess;
 190                     session.span_err(item.span,
 191                                      "cannot associate methods with a type outside the \
 192                                      crate the type is defined in; define and implement \
 193                                      a trait or new type instead");
 194                 }
 195             }
 196             ItemImpl(_, Some(ref trait_ref), _, _) => {
 197                 // `for_ty` is `Type` in `impl Trait for Type`
 198                 let for_ty =
 199                     ty::node_id_to_type(self.cc.crate_context.tcx,
 200                                         item.id);
 201                 if !type_is_defined_in_local_crate(for_ty) {
 202                     // This implementation is not in scope of its base
 203                     // type. This still might be OK if the trait is
 204                     // defined in the same crate.
 205
 206                     let trait_def_id =
 207                         self.cc.trait_ref_to_trait_def_id(trait_ref);
 208
 209                     if trait_def_id.krate != LOCAL_CRATE {
 210                         let session = &self.cc.crate_context.tcx.sess;
 211                         session.span_err(item.span,
 212                                 "cannot provide an extension implementation \
 213                                 where both trait and type are not defined in this crate");
 214                     }
 215                 }
 216
 217                 visit::walk_item(self, item, ());
 218             }
 219             _ => {
 220                 visit::walk_item(self, item, ());
 221             }
 222         }
 223     }
 224 }
 225
 226 impl<'a> CoherenceChecker<'a> {
 227     fn check(&self, krate: &Crate) {
 228         // Check implementations and traits. This populates the tables
 229         // containing the inherent methods and extension methods. It also
 230         // builds up the trait inheritance table.
 231         let mut visitor = CoherenceCheckVisitor { cc: self };
 232         visit::walk_crate(&mut visitor, krate, ());
 233
 234         // Check that there are no overlapping trait instances
 235         self.check_implementation_coherence();
 236
 237         // Check whether traits with base types are in privileged scopes.
 238         self.check_privileged_scopes(krate);
 239
 240         // Bring in external crates. It's fine for this to happen after the
 241         // coherence checks, because we ensure by construction that no errors
 242         // can happen at link time.
 243         self.add_external_crates();
 244
 245         // Populate the table of destructors. It might seem a bit strange to
 246         // do this here, but it's actually the most convenient place, since
 247         // the coherence tables contain the trait -> type mappings.
 248         self.populate_destructor_table();
 249     }
 250
 251     fn check_implementation(&self, item: &Item,
 252                             associated_traits: &[TraitRef]) {
 253         let tcx = self.crate_context.tcx;
 254         let impl_did = local_def(item.id);
 255         let self_type = ty::lookup_item_type(tcx, impl_did);
 256
 257         // If there are no traits, then this implementation must have a
 258         // base type.
 259
 260         if associated_traits.len() == 0 {
 261             debug!("(checking implementation) no associated traits for item '{}'",
 262                    token::get_ident(item.ident));
 263
 264             match get_base_type_def_id(&self.inference_context,
 265                                        item.span,
 266                                        self_type.ty) {
 267                 None => {
 268                     let session = &self.crate_context.tcx.sess;
 269                     session.span_err(item.span,
 270                                      "no base type found for inherent implementation; \
 271                                       implement a trait or new type instead");
 272                 }
 273                 Some(_) => {
 274                     // Nothing to do.
 275                 }
 276             }
 277         }
 278
 279         let impl_methods = self.create_impl_from_item(item);
 280
 281         for associated_trait in associated_traits.iter() {
 282             let trait_ref = ty::node_id_to_trait_ref(
 283                 self.crate_context.tcx, associated_trait.ref_id);
 284             debug!("(checking implementation) adding impl for trait '{}', item '{}'",
 285                    trait_ref.repr(self.crate_context.tcx),
 286                    token::get_ident(item.ident));
 287
 288             self.add_trait_impl(trait_ref.def_id, impl_did);
 289         }
 290
 291         // Add the implementation to the mapping from implementation to base
 292         // type def ID, if there is a base type for this implementation and
 293         // the implementation does not have any associated traits.
 294         match get_base_type_def_id(&self.inference_context,
 295                                    item.span,
 296                                    self_type.ty) {
 297             None => {
 298                 // Nothing to do.
 299             }
 300             Some(base_type_def_id) => {
 301                 // FIXME: Gather up default methods?
 302                 if associated_traits.len() == 0 {
 303                     self.add_inherent_impl(base_type_def_id, impl_did);
 304                 }
 305             }
 306         }
 307
 308         tcx.impl_methods.borrow_mut().insert(impl_did, impl_methods);
 309     }
 310
 311     // Creates default method IDs and performs type substitutions for an impl
 312     // and trait pair. Then, for each provided method in the trait, inserts a
 313     // `ProvidedMethodInfo` instance into the `provided_method_sources` map.
 314     fn instantiate_default_methods(&self, impl_id: DefId,
 315                                    trait_ref: &ty::TraitRef,
 316                                    all_methods: &mut Vec<DefId>) {
 317         let tcx = self.crate_context.tcx;
 318         debug!("instantiate_default_methods(impl_id={:?}, trait_ref={})",
 319                impl_id, trait_ref.repr(tcx));
 320
 321         let impl_poly_type = ty::lookup_item_type(tcx, impl_id);
 322
 323         let prov = ty::provided_trait_methods(tcx, trait_ref.def_id);
 324         for trait_method in prov.iter() {
 325             // Synthesize an ID.
 326             let new_id = tcx.sess.next_node_id();
 327             let new_did = local_def(new_id);
 328
 329             debug!("new_did={:?} trait_method={}", new_did, trait_method.repr(tcx));
 330
 331             // Create substitutions for the various trait parameters.
 332             let new_method_ty =
 333                 Rc::new(subst_receiver_types_in_method_ty(
 334                     tcx,
 335                     impl_id,
 336                     trait_ref,
 337                     new_did,
 338                     &**trait_method,
 339                     Some(trait_method.def_id)));
 340
 341             debug!("new_method_ty={}", new_method_ty.repr(tcx));
 342             all_methods.push(new_did);
 343
 344             // construct the polytype for the method based on the method_ty
 345             let new_generics = ty::Generics {
 346                 type_param_defs:
 347                     Rc::new(Vec::from_slice(impl_poly_type.generics.type_param_defs()).append(
 348                             new_method_ty.generics.type_param_defs())),
 349                 region_param_defs:
 350                     Rc::new(Vec::from_slice(impl_poly_type.generics.region_param_defs()).append(
 351                             new_method_ty.generics.region_param_defs()))
 352             };
 353             let new_polytype = ty::ty_param_bounds_and_ty {
 354                 generics: new_generics,
 355                 ty: ty::mk_bare_fn(tcx, new_method_ty.fty.clone())
 356             };
 357             debug!("new_polytype={}", new_polytype.repr(tcx));
 358
 359             tcx.tcache.borrow_mut().insert(new_did, new_polytype);
 360             tcx.methods.borrow_mut().insert(new_did, new_method_ty);
 361
 362             // Pair the new synthesized ID up with the
 363             // ID of the method.
 364             self.crate_context.tcx.provided_method_sources.borrow_mut()
 365                 .insert(new_did, trait_method.def_id);
 366         }
 367     }
 368
 369     fn add_inherent_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
 370         let tcx = self.crate_context.tcx;
 371         match tcx.inherent_impls.borrow().find(&base_def_id) {
 372             Some(implementation_list) => {
 373                 implementation_list.borrow_mut().push(impl_def_id);
 374                 return;
 375             }
 376             None => {}
 377         }
 378
 379         tcx.inherent_impls.borrow_mut().insert(base_def_id,
 380                                                Rc::new(RefCell::new(vec!(impl_def_id))));
 381     }
 382
 383     fn add_trait_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
 384         ty::record_trait_implementation(self.crate_context.tcx,
 385                                         base_def_id,
 386                                         impl_def_id);
 387     }
 388
 389     fn check_implementation_coherence(&self) {
 390         for &trait_id in self.crate_context.tcx.trait_impls.borrow().keys() {
 391             self.check_implementation_coherence_of(trait_id);
 392         }
 393     }
 394
 395     fn check_implementation_coherence_of(&self, trait_def_id: DefId) {
 396         // Unify pairs of polytypes.
 397         self.iter_impls_of_trait_local(trait_def_id, |impl_a| {
 398             let polytype_a =
 399                 self.get_self_type_for_implementation(impl_a);
 400
 401             // "We have an impl of trait <trait_def_id> for type <polytype_a>,
 402             // and that impl is <impl_a>"
 403             self.iter_impls_of_trait(trait_def_id, |impl_b| {
 404
 405                 // An impl is coherent with itself
 406                 if impl_a != impl_b {
 407                     let polytype_b = self.get_self_type_for_implementation(
 408                             impl_b);
 409
 410                     if self.polytypes_unify(polytype_a.clone(), polytype_b) {
 411                         let session = &self.crate_context.tcx.sess;
 412                         session.span_err(
 413                             self.span_of_impl(impl_a),
 414                             format!("conflicting implementations for trait `{}`",
 415                                  ty::item_path_str(self.crate_context.tcx,
 416                                                    trait_def_id)));
 417                         if impl_b.krate == LOCAL_CRATE {
 418                             session.span_note(self.span_of_impl(impl_b),
 419                                               "note conflicting implementation here");
 420                         } else {
 421                             let crate_store = &self.crate_context.tcx.sess.cstore;
 422                             let cdata = crate_store.get_crate_data(impl_b.krate);
 423                             session.note(
 424                                 "conflicting implementation in crate `" + cdata.name + "`");
 425                         }
 426                     }
 427                 }
 428             })
 429         })
 430     }
 431
 432     fn iter_impls_of_trait(&self, trait_def_id: DefId, f: |DefId|) {
 433         self.iter_impls_of_trait_local(trait_def_id, |x| f(x));
 434
 435         if trait_def_id.krate == LOCAL_CRATE {
 436             return;
 437         }
 438
 439         let crate_store = &self.crate_context.tcx.sess.cstore;
 440         csearch::each_implementation_for_trait(crate_store, trait_def_id, |impl_def_id| {
 441             // Is this actually necessary?
 442             let _ = lookup_item_type(self.crate_context.tcx, impl_def_id);
 443             f(impl_def_id);
 444         });
 445     }
 446
 447     fn iter_impls_of_trait_local(&self, trait_def_id: DefId, f: |DefId|) {
 448         match self.crate_context.tcx.trait_impls.borrow().find(&trait_def_id) {
 449             Some(impls) => {
 450                 for &impl_did in impls.borrow().iter() {
 451                     f(impl_did);
 452                 }
 453             }
 454             None => { /* no impls? */ }
 455         }
 456     }
 457
 458     fn polytypes_unify(&self,
 459                        polytype_a: ty_param_bounds_and_ty,
 460                        polytype_b: ty_param_bounds_and_ty)
 461                        -> bool {
 462         let universally_quantified_a =
 463             self.universally_quantify_polytype(polytype_a);
 464         let universally_quantified_b =
 465             self.universally_quantify_polytype(polytype_b);
 466
 467         return self.can_unify_universally_quantified(
 468             &universally_quantified_a, &universally_quantified_b) ||
 469             self.can_unify_universally_quantified(
 470             &universally_quantified_b, &universally_quantified_a);
 471     }
 472
 473     // Converts a polytype to a monotype by replacing all parameters with
 474     // type variables. Returns the monotype and the type variables created.
 475     fn universally_quantify_polytype(&self, polytype: ty_param_bounds_and_ty)
 476                                      -> UniversalQuantificationResult {
 477         let region_parameters =
 478             polytype.generics.region_param_defs().iter()
 479             .map(|d| self.inference_context.next_region_var(
 480                 infer::BoundRegionInCoherence(d.name)))
 481             .collect();
 482
 483         let bounds_count = polytype.generics.type_param_defs().len();
 484         let type_parameters = self.inference_context.next_ty_vars(bounds_count);
 485
 486         let substitutions = substs {
 487             regions: ty::NonerasedRegions(region_parameters),
 488             self_ty: None,
 489             tps: type_parameters
 490         };
 491         let monotype = subst(self.crate_context.tcx,
 492                              &substitutions,
 493                              polytype.ty);
 494
 495         UniversalQuantificationResult {
 496             monotype: monotype,
 497             type_variables: substitutions.tps,
 498             type_param_defs: polytype.generics.type_param_defs.clone()
 499         }
 500     }
 501
 502     fn can_unify_universally_quantified<'a>(&self,
 503                                             a: &'a UniversalQuantificationResult,
 504                                             b: &'a UniversalQuantificationResult)
 505                                             -> bool {
 506         infer::can_mk_subty(&self.inference_context,
 507                             a.monotype,
 508                             b.monotype).is_ok()
 509     }
 510
 511     fn get_self_type_for_implementation(&self, impl_did: DefId)
 512                                         -> ty_param_bounds_and_ty {
 513         self.crate_context.tcx.tcache.borrow().get_copy(&impl_did)
 514     }
 515
 516     // Privileged scope checking
 517     fn check_privileged_scopes(&self, krate: &Crate) {
 518         let mut visitor = PrivilegedScopeVisitor{ cc: self };
 519         visit::walk_crate(&mut visitor, krate, ());
 520     }
 521
 522     fn trait_ref_to_trait_def_id(&self, trait_ref: &TraitRef) -> DefId {
 523         let def_map = &self.crate_context.tcx.def_map;
 524         let trait_def = def_map.borrow().get_copy(&trait_ref.ref_id);
 525         let trait_id = def_id_of_def(trait_def);
 526         return trait_id;
 527     }
 528
 529     /// For coherence, when we have `impl Type`, we need to guarantee that
 530     /// `Type` is "local" to the crate. For our purposes, this means that it
 531     /// must precisely name some nominal type defined in this crate.
 532     fn ast_type_is_defined_in_local_crate(&self, original_type: &ast::Ty) -> bool {
 533         match original_type.node {
 534             TyPath(_, _, path_id) => {
 535                 match self.crate_context.tcx.def_map.borrow().get_copy(&path_id) {
 536                     DefTy(def_id) | DefStruct(def_id) => {
 537                         if def_id.krate != LOCAL_CRATE {
 538                             return false;
 539                         }
 540
 541                         // Make sure that this type precisely names a nominal
 542                         // type.
 543                         match self.crate_context.tcx.map.find(def_id.node) {
 544                             None => {
 545                                 self.crate_context.tcx.sess.span_bug(
 546                                     original_type.span,
 547                                     "resolve didn't resolve this type?!");
 548                             }
 549                             Some(NodeItem(item)) => {
 550                                 match item.node {
 551                                     ItemStruct(..) | ItemEnum(..) => true,
 552                                     _ => false,
 553                                 }
 554                             }
 555                             Some(_) => false,
 556                         }
 557                     }
 558                     _ => false
 559                 }
 560             }
 561             _ => false
 562         }
 563     }
 564
 565     // Converts an implementation in the AST to a vector of methods.
 566     fn create_impl_from_item(&self, item: &Item) -> Vec<DefId> {
 567         match item.node {
 568             ItemImpl(_, ref trait_refs, _, ref ast_methods) => {
 569                 let mut methods: Vec<DefId> = ast_methods.iter().map(|ast_method| {
 570                     local_def(ast_method.id)
 571                 }).collect();
 572
 573                 for trait_ref in trait_refs.iter() {
 574                     let ty_trait_ref = ty::node_id_to_trait_ref(
 575                         self.crate_context.tcx,
 576                         trait_ref.ref_id);
 577
 578                     self.instantiate_default_methods(local_def(item.id),
 579                                                      &*ty_trait_ref,
 580                                                      &mut methods);
 581                 }
 582
 583                 methods
 584             }
 585             _ => {
 586                 self.crate_context.tcx.sess.span_bug(item.span,
 587                                                      "can't convert a non-impl to an impl");
 588             }
 589         }
 590     }
 591
 592     fn span_of_impl(&self, impl_did: DefId) -> Span {
 593         assert_eq!(impl_did.krate, LOCAL_CRATE);
 594         self.crate_context.tcx.map.span(impl_did.node)
 595     }
 596
 597     // External crate handling
 598
 599     fn add_external_impl(&self,
 600                          impls_seen: &mut HashSet<DefId>,
 601                          impl_def_id: DefId) {
 602         let tcx = self.crate_context.tcx;
 603         let methods = csearch::get_impl_methods(&tcx.sess.cstore, impl_def_id);
 604
 605         // Make sure we don't visit the same implementation multiple times.
 606         if !impls_seen.insert(impl_def_id) {
 607             // Skip this one.
 608             return
 609         }
 610         // Good. Continue.
 611
 612         let _ = lookup_item_type(tcx, impl_def_id);
 613         let associated_traits = get_impl_trait(tcx, impl_def_id);
 614
 615         // Do a sanity check.
 616         assert!(associated_traits.is_some());
 617
 618         // Record all the trait methods.
 619         for trait_ref in associated_traits.iter() {
 620             self.add_trait_impl(trait_ref.def_id, impl_def_id);
 621         }
 622
 623         // For any methods that use a default implementation, add them to
 624         // the map. This is a bit unfortunate.
 625         for &method_def_id in methods.iter() {
 626             for &source in ty::method(tcx, method_def_id).provided_source.iter() {
 627                 tcx.provided_method_sources.borrow_mut().insert(method_def_id, source);
 628             }
 629         }
 630
 631         tcx.impl_methods.borrow_mut().insert(impl_def_id, methods);
 632     }
 633
 634     // Adds implementations and traits from external crates to the coherence
 635     // info.
 636     fn add_external_crates(&self) {
 637         let mut impls_seen = HashSet::new();
 638
 639         let crate_store = &self.crate_context.tcx.sess.cstore;
 640         crate_store.iter_crate_data(|crate_number, _crate_metadata| {
 641             each_impl(crate_store, crate_number, |def_id| {
 642                 assert_eq!(crate_number, def_id.krate);
 643                 self.add_external_impl(&mut impls_seen, def_id)
 644             })
 645         })
 646     }
 647
 648     //
 649     // Destructors
 650     //
 651
 652     fn populate_destructor_table(&self) {
 653         let tcx = self.crate_context.tcx;
 654         let drop_trait = match tcx.lang_items.drop_trait() {
 655             Some(id) => id, None => { return }
 656         };
 657
 658         let impl_methods = tcx.impl_methods.borrow();
 659         let trait_impls = match tcx.trait_impls.borrow().find_copy(&drop_trait) {
 660             None => return, // No types with (new-style) dtors present.
 661             Some(found_impls) => found_impls
 662         };
 663
 664         for &impl_did in trait_impls.borrow().iter() {
 665             let methods = impl_methods.get(&impl_did);
 666             if methods.len() < 1 {
 667                 // We'll error out later. For now, just don't ICE.
 668                 continue;
 669             }
 670             let method_def_id = *methods.get(0);
 671
 672             let self_type = self.get_self_type_for_implementation(impl_did);
 673             match ty::get(self_type.ty).sty {
 674                 ty::ty_enum(type_def_id, _) |
 675                 ty::ty_struct(type_def_id, _) => {
 676                     tcx.destructor_for_type.borrow_mut().insert(type_def_id,
 677                                                                 method_def_id);
 678                     tcx.destructors.borrow_mut().insert(method_def_id);
 679                 }
 680                 _ => {
 681                     // Destructors only work on nominal types.
 682                     if impl_did.krate == ast::LOCAL_CRATE {
 683                         {
 684                             match tcx.map.find(impl_did.node) {
 685                                 Some(ast_map::NodeItem(item)) => {
 686                                     tcx.sess.span_err((*item).span,
 687                                                       "the Drop trait may \
 688                                                        only be implemented \
 689                                                        on structures");
 690                                 }
 691                                 _ => {
 692                                     tcx.sess.bug("didn't find impl in ast \
 693                                                   map");
 694                                 }
 695                             }
 696                         }
 697                     } else {
 698                         tcx.sess.bug("found external impl of Drop trait on \
 699                                       something other than a struct");
 700                     }
 701                 }
 702             }
 703         }
 704     }
 705 }
 706
 707 pub fn make_substs_for_receiver_types(tcx: &ty::ctxt,
 708                                       impl_id: ast::DefId,
 709                                       trait_ref: &ty::TraitRef,
 710                                       method: &ty::Method)
 711                                       -> ty::substs {
 712     /*!
 713      * Substitutes the values for the receiver's type parameters
 714      * that are found in method, leaving the method's type parameters
 715      * intact.  This is in fact a mildly complex operation,
 716      * largely because of the hokey way that we concatenate the
 717      * receiver and method generics.
 718      */
 719
 720     let impl_polytype = ty::lookup_item_type(tcx, impl_id);
 721     let num_impl_tps = impl_polytype.generics.type_param_defs().len();
 722     let num_impl_regions = impl_polytype.generics.region_param_defs().len();
 723     let meth_tps: Vec<ty::t> =
 724         method.generics.type_param_defs().iter().enumerate()
 725               .map(|(i, t)| ty::mk_param(tcx, i + num_impl_tps, t.def_id))
 726               .collect();
 727     let meth_regions: Vec<ty::Region> =
 728         method.generics.region_param_defs().iter().enumerate()
 729               .map(|(i, l)| ty::ReEarlyBound(l.def_id.node, i + num_impl_regions, l.name))
 730               .collect();
 731     let mut combined_tps = trait_ref.substs.tps.clone();
 732     combined_tps.push_all_move(meth_tps);
 733     let combined_regions = match &trait_ref.substs.regions {
 734         &ty::ErasedRegions =>
 735             fail!("make_substs_for_receiver_types: unexpected ErasedRegions"),
 736
 737         &ty::NonerasedRegions(ref rs) => {
 738             let mut rs = rs.clone().into_vec();
 739             rs.push_all_move(meth_regions);
 740             ty::NonerasedRegions(OwnedSlice::from_vec(rs))
 741         }
 742     };
 743
 744     ty::substs {
 745         regions: combined_regions,
 746         self_ty: trait_ref.substs.self_ty,
 747         tps: combined_tps
 748     }
 749 }
 750
 751 fn subst_receiver_types_in_method_ty(tcx: &ty::ctxt,
 752                                      impl_id: ast::DefId,
 753                                      trait_ref: &ty::TraitRef,
 754                                      new_def_id: ast::DefId,
 755                                      method: &ty::Method,
 756                                      provided_source: Option<ast::DefId>)
 757                                      -> ty::Method {
 758
 759     let combined_substs = make_substs_for_receiver_types(
 760         tcx, impl_id, trait_ref, method);
 761
 762     ty::Method::new(
 763         method.ident,
 764
 765         // method types *can* appear in the generic bounds
 766         method.generics.subst(tcx, &combined_substs),
 767
 768         // method types *can* appear in the fty
 769         method.fty.subst(tcx, &combined_substs),
 770
 771         method.explicit_self,
 772         method.vis,
 773         new_def_id,
 774         ImplContainer(impl_id),
 775         provided_source
 776     )
 777 }
 778
 779 pub fn check_coherence(crate_context: &CrateCtxt, krate: &Crate) {
 780     CoherenceChecker {
 781         crate_context: crate_context,
 782         inference_context: new_infer_ctxt(crate_context.tcx),
 783     }.check(krate);
 784 }