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