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