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