src/librustc_typeck/coherence/mod.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 // Coherence phase
  12 //
  13 // The job of the coherence phase of typechecking is to ensure that
  14 // each trait has at most one implementation for each type. This is
  15 // done by the orphan and overlap modules. Then we build up various
  16 // mappings. That mapping code resides here.
  17
  18
  19 use middle::def_id::{DefId, LOCAL_CRATE};
  20 use middle::lang_items::UnsizeTraitLangItem;
  21 use middle::subst::{self, Subst};
  22 use middle::traits;
  23 use middle::ty::RegionEscape;
  24 use middle::ty::{ImplContainer, ImplOrTraitItemId, ConstTraitItemId};
  25 use middle::ty::{MethodTraitItemId, TypeTraitItemId, ParameterEnvironment};
  26 use middle::ty::{Ty, TyBool, TyChar, TyEnum, TyError};
  27 use middle::ty::{TyParam, TypeScheme, TyRawPtr};
  28 use middle::ty::{TyRef, TyStruct, TyTrait, TyTuple};
  29 use middle::ty::{TyStr, TyArray, TySlice, TyFloat, TyInfer, TyInt};
  30 use middle::ty::{TyUint, TyClosure, TyBox, TyBareFn};
  31 use middle::ty::TyProjection;
  32 use middle::ty;
  33 use middle::free_region::FreeRegionMap;
  34 use CrateCtxt;
  35 use middle::infer::{self, InferCtxt, new_infer_ctxt};
  36 use std::cell::RefCell;
  37 use std::rc::Rc;
  38 use syntax::codemap::Span;
  39 use syntax::parse::token;
  40 use util::nodemap::{DefIdMap, FnvHashMap};
  41 use rustc::front::map as hir_map;
  42 use rustc::front::map::NodeItem;
  43 use rustc_front::visit;
  44 use rustc_front::hir::{Item, ItemImpl,Crate};
  45 use rustc_front::hir;
  46
  47 mod orphan;
  48 mod overlap;
  49 mod unsafety;
  50
  51 // Returns the def ID of the base type, if there is one.
  52 fn get_base_type_def_id<'a, 'tcx>(inference_context: &InferCtxt<'a, 'tcx>,
  53                                   span: Span,
  54                                   ty: Ty<'tcx>)
  55                                   -> Option<DefId> {
  56     match ty.sty {
  57         TyEnum(def, _) |
  58         TyStruct(def, _) => {
  59             Some(def.did)
  60         }
  61
  62         TyTrait(ref t) => {
  63             Some(t.principal_def_id())
  64         }
  65
  66         TyBox(_) => {
  67             inference_context.tcx.lang_items.owned_box()
  68         }
  69
  70         TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
  71         TyStr(..) | TyArray(..) | TySlice(..) | TyBareFn(..) | TyTuple(..) |
  72         TyParam(..) | TyError |
  73         TyRawPtr(_) | TyRef(_, _) | TyProjection(..) => {
  74             None
  75         }
  76
  77         TyInfer(..) | TyClosure(..) => {
  78             // `ty` comes from a user declaration so we should only expect types
  79             // that the user can type
  80             inference_context.tcx.sess.span_bug(
  81                 span,
  82                 &format!("coherence encountered unexpected type searching for base type: {}",
  83                          ty));
  84         }
  85     }
  86 }
  87
  88 struct CoherenceChecker<'a, 'tcx: 'a> {
  89     crate_context: &'a CrateCtxt<'a, 'tcx>,
  90     inference_context: InferCtxt<'a, 'tcx>,
  91     inherent_impls: RefCell<DefIdMap<Rc<RefCell<Vec<DefId>>>>>,
  92 }
  93
  94 struct CoherenceCheckVisitor<'a, 'tcx: 'a> {
  95     cc: &'a CoherenceChecker<'a, 'tcx>
  96 }
  97
  98 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CoherenceCheckVisitor<'a, 'tcx> {
  99     fn visit_item(&mut self, item: &Item) {
 100         if let ItemImpl(..) = item.node {
 101             self.cc.check_implementation(item)
 102         }
 103
 104         visit::walk_item(self, item);
 105     }
 106 }
 107
 108 impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
 109     fn check(&self, krate: &Crate) {
 110         // Check implementations and traits. This populates the tables
 111         // containing the inherent methods and extension methods. It also
 112         // builds up the trait inheritance table.
 113         let mut visitor = CoherenceCheckVisitor { cc: self };
 114         visit::walk_crate(&mut visitor, krate);
 115
 116         // Copy over the inherent impls we gathered up during the walk into
 117         // the tcx.
 118         let mut tcx_inherent_impls =
 119             self.crate_context.tcx.inherent_impls.borrow_mut();
 120         for (k, v) in self.inherent_impls.borrow().iter() {
 121             tcx_inherent_impls.insert((*k).clone(),
 122                                       Rc::new((*v.borrow()).clone()));
 123         }
 124
 125         // Populate the table of destructors. It might seem a bit strange to
 126         // do this here, but it's actually the most convenient place, since
 127         // the coherence tables contain the trait -> type mappings.
 128         self.populate_destructor_table();
 129
 130         // Check to make sure implementations of `Copy` are legal.
 131         self.check_implementations_of_copy();
 132
 133         // Check to make sure implementations of `CoerceUnsized` are legal
 134         // and collect the necessary information from them.
 135         self.check_implementations_of_coerce_unsized();
 136     }
 137
 138     fn check_implementation(&self, item: &Item) {
 139         let tcx = self.crate_context.tcx;
 140         let impl_did = DefId::local(item.id);
 141         let self_type = tcx.lookup_item_type(impl_did);
 142
 143         // If there are no traits, then this implementation must have a
 144         // base type.
 145
 146         let impl_items = self.create_impl_from_item(item);
 147
 148         if let Some(trait_ref) = self.crate_context.tcx.impl_trait_ref(impl_did) {
 149             debug!("(checking implementation) adding impl for trait '{:?}', item '{}'",
 150                    trait_ref,
 151                    item.ident);
 152
 153             enforce_trait_manually_implementable(self.crate_context.tcx,
 154                                                  item.span,
 155                                                  trait_ref.def_id);
 156             self.add_trait_impl(trait_ref, impl_did);
 157         } else {
 158             // Add the implementation to the mapping from implementation to base
 159             // type def ID, if there is a base type for this implementation and
 160             // the implementation does not have any associated traits.
 161             if let Some(base_type_def_id) = get_base_type_def_id(
 162                     &self.inference_context, item.span, self_type.ty) {
 163                 self.add_inherent_impl(base_type_def_id, impl_did);
 164             }
 165         }
 166
 167         tcx.impl_items.borrow_mut().insert(impl_did, impl_items);
 168     }
 169
 170     // Creates default method IDs and performs type substitutions for an impl
 171     // and trait pair. Then, for each provided method in the trait, inserts a
 172     // `ProvidedMethodInfo` instance into the `provided_method_sources` map.
 173     fn instantiate_default_methods(
 174             &self,
 175             impl_id: DefId,
 176             trait_ref: &ty::TraitRef<'tcx>,
 177             all_impl_items: &mut Vec<ImplOrTraitItemId>) {
 178         let tcx = self.crate_context.tcx;
 179         debug!("instantiate_default_methods(impl_id={:?}, trait_ref={:?})",
 180                impl_id, trait_ref);
 181
 182         let impl_type_scheme = tcx.lookup_item_type(impl_id);
 183
 184         let prov = tcx.provided_trait_methods(trait_ref.def_id);
 185         for trait_method in &prov {
 186             // Synthesize an ID.
 187             let new_id = tcx.sess.next_node_id();
 188             let new_did = DefId::local(new_id);
 189
 190             debug!("new_did={:?} trait_method={:?}", new_did, trait_method);
 191
 192             // Create substitutions for the various trait parameters.
 193             let new_method_ty =
 194                 Rc::new(subst_receiver_types_in_method_ty(
 195                     tcx,
 196                     impl_id,
 197                     &impl_type_scheme,
 198                     trait_ref,
 199                     new_did,
 200                     &**trait_method,
 201                     Some(trait_method.def_id)));
 202
 203             debug!("new_method_ty={:?}", new_method_ty);
 204             all_impl_items.push(MethodTraitItemId(new_did));
 205
 206             // construct the polytype for the method based on the
 207             // method_ty.  it will have all the generics from the
 208             // impl, plus its own.
 209             let new_polytype = ty::TypeScheme {
 210                 generics: new_method_ty.generics.clone(),
 211                 ty: tcx.mk_fn(Some(new_did),
 212                               tcx.mk_bare_fn(new_method_ty.fty.clone()))
 213             };
 214             debug!("new_polytype={:?}", new_polytype);
 215
 216             tcx.register_item_type(new_did, new_polytype);
 217             tcx.predicates.borrow_mut().insert(new_did, new_method_ty.predicates.clone());
 218             tcx.impl_or_trait_items
 219                .borrow_mut()
 220                .insert(new_did, ty::MethodTraitItem(new_method_ty));
 221
 222             // Pair the new synthesized ID up with the
 223             // ID of the method.
 224             self.crate_context.tcx.provided_method_sources.borrow_mut()
 225                 .insert(new_did, trait_method.def_id);
 226         }
 227     }
 228
 229     fn add_inherent_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
 230         match self.inherent_impls.borrow().get(&base_def_id) {
 231             Some(implementation_list) => {
 232                 implementation_list.borrow_mut().push(impl_def_id);
 233                 return;
 234             }
 235             None => {}
 236         }
 237
 238         self.inherent_impls.borrow_mut().insert(
 239             base_def_id,
 240             Rc::new(RefCell::new(vec!(impl_def_id))));
 241     }
 242
 243     fn add_trait_impl(&self, impl_trait_ref: ty::TraitRef<'tcx>, impl_def_id: DefId) {
 244         debug!("add_trait_impl: impl_trait_ref={:?} impl_def_id={:?}",
 245                impl_trait_ref, impl_def_id);
 246         let trait_def = self.crate_context.tcx.lookup_trait_def(impl_trait_ref.def_id);
 247         trait_def.record_impl(self.crate_context.tcx, impl_def_id, impl_trait_ref);
 248     }
 249
 250     // Converts an implementation in the AST to a vector of items.
 251     fn create_impl_from_item(&self, item: &Item) -> Vec<ImplOrTraitItemId> {
 252         match item.node {
 253             ItemImpl(_, _, _, _, _, ref impl_items) => {
 254                 let mut items: Vec<ImplOrTraitItemId> =
 255                         impl_items.iter().map(|impl_item| {
 256                     match impl_item.node {
 257                         hir::ConstImplItem(..) => {
 258                             ConstTraitItemId(DefId::local(impl_item.id))
 259                         }
 260                         hir::MethodImplItem(..) => {
 261                             MethodTraitItemId(DefId::local(impl_item.id))
 262                         }
 263                         hir::TypeImplItem(_) => {
 264                             TypeTraitItemId(DefId::local(impl_item.id))
 265                         }
 266                     }
 267                 }).collect();
 268
 269                 let def_id = DefId::local(item.id);
 270                 if let Some(trait_ref) = self.crate_context.tcx.impl_trait_ref(def_id) {
 271                     self.instantiate_default_methods(def_id, &trait_ref, &mut items);
 272                 }
 273
 274                 items
 275             }
 276             _ => {
 277                 self.crate_context.tcx.sess.span_bug(item.span,
 278                                                      "can't convert a non-impl \
 279                                                       to an impl");
 280             }
 281         }
 282     }
 283
 284     //
 285     // Destructors
 286     //
 287
 288     fn populate_destructor_table(&self) {
 289         let tcx = self.crate_context.tcx;
 290         let drop_trait = match tcx.lang_items.drop_trait() {
 291             Some(id) => id, None => { return }
 292         };
 293         tcx.populate_implementations_for_trait_if_necessary(drop_trait);
 294         let drop_trait = tcx.lookup_trait_def(drop_trait);
 295
 296         let impl_items = tcx.impl_items.borrow();
 297
 298         drop_trait.for_each_impl(tcx, |impl_did| {
 299             let items = impl_items.get(&impl_did).unwrap();
 300             if items.is_empty() {
 301                 // We'll error out later. For now, just don't ICE.
 302                 return;
 303             }
 304             let method_def_id = items[0];
 305
 306             let self_type = tcx.lookup_item_type(impl_did);
 307             match self_type.ty.sty {
 308                 ty::TyEnum(type_def, _) |
 309                 ty::TyStruct(type_def, _) => {
 310                     type_def.set_destructor(method_def_id.def_id());
 311                     tcx.destructors
 312                        .borrow_mut()
 313                        .insert(method_def_id.def_id());
 314                 }
 315                 _ => {
 316                     // Destructors only work on nominal types.
 317                     if impl_did.is_local() {
 318                         {
 319                             match tcx.map.find(impl_did.node) {
 320                                 Some(hir_map::NodeItem(item)) => {
 321                                     span_err!(tcx.sess, item.span, E0120,
 322                                         "the Drop trait may only be implemented on structures");
 323                                 }
 324                                 _ => {
 325                                     tcx.sess.bug("didn't find impl in ast \
 326                                                   map");
 327                                 }
 328                             }
 329                         }
 330                     } else {
 331                         tcx.sess.bug("found external impl of Drop trait on \
 332                                       something other than a struct");
 333                     }
 334                 }
 335             }
 336         });
 337     }
 338
 339     /// Ensures that implementations of the built-in trait `Copy` are legal.
 340     fn check_implementations_of_copy(&self) {
 341         let tcx = self.crate_context.tcx;
 342         let copy_trait = match tcx.lang_items.copy_trait() {
 343             Some(id) => id,
 344             None => return,
 345         };
 346         tcx.populate_implementations_for_trait_if_necessary(copy_trait);
 347         let copy_trait = tcx.lookup_trait_def(copy_trait);
 348
 349         copy_trait.for_each_impl(tcx, |impl_did| {
 350             debug!("check_implementations_of_copy: impl_did={:?}",
 351                    impl_did);
 352
 353             if impl_did.krate != LOCAL_CRATE {
 354                 debug!("check_implementations_of_copy(): impl not in this \
 355                         crate");
 356                 return
 357             }
 358
 359             let self_type = tcx.lookup_item_type(impl_did);
 360             debug!("check_implementations_of_copy: self_type={:?} (bound)",
 361                    self_type);
 362
 363             let span = tcx.map.span(impl_did.node);
 364             let param_env = ParameterEnvironment::for_item(tcx, impl_did.node);
 365             let self_type = self_type.ty.subst(tcx, &param_env.free_substs);
 366             assert!(!self_type.has_escaping_regions());
 367
 368             debug!("check_implementations_of_copy: self_type={:?} (free)",
 369                    self_type);
 370
 371             match param_env.can_type_implement_copy(self_type, span) {
 372                 Ok(()) => {}
 373                 Err(ty::FieldDoesNotImplementCopy(name)) => {
 374                        span_err!(tcx.sess, span, E0204,
 375                                  "the trait `Copy` may not be \
 376                                           implemented for this type; field \
 377                                           `{}` does not implement `Copy`",
 378                                          name)
 379                 }
 380                 Err(ty::VariantDoesNotImplementCopy(name)) => {
 381                        span_err!(tcx.sess, span, E0205,
 382                                  "the trait `Copy` may not be \
 383                                           implemented for this type; variant \
 384                                           `{}` does not implement `Copy`",
 385                                          name)
 386                 }
 387                 Err(ty::TypeIsStructural) => {
 388                        span_err!(tcx.sess, span, E0206,
 389                                  "the trait `Copy` may not be implemented \
 390                                   for this type; type is not a structure or \
 391                                   enumeration")
 392                 }
 393                 Err(ty::TypeHasDestructor) => {
 394                     span_err!(tcx.sess, span, E0184,
 395                               "the trait `Copy` may not be implemented for this type; \
 396                                the type has a destructor");
 397                 }
 398             }
 399         });
 400     }
 401
 402     /// Process implementations of the built-in trait `CoerceUnsized`.
 403     fn check_implementations_of_coerce_unsized(&self) {
 404         let tcx = self.crate_context.tcx;
 405         let coerce_unsized_trait = match tcx.lang_items.coerce_unsized_trait() {
 406             Some(id) => id,
 407             None => return,
 408         };
 409         let unsize_trait = match tcx.lang_items.require(UnsizeTraitLangItem) {
 410             Ok(id) => id,
 411             Err(err) => {
 412                 tcx.sess.fatal(&format!("`CoerceUnsized` implementation {}", err));
 413             }
 414         };
 415
 416         let trait_def = tcx.lookup_trait_def(coerce_unsized_trait);
 417
 418         trait_def.for_each_impl(tcx, |impl_did| {
 419             debug!("check_implementations_of_coerce_unsized: impl_did={:?}",
 420                    impl_did);
 421
 422             if impl_did.krate != LOCAL_CRATE {
 423                 debug!("check_implementations_of_coerce_unsized(): impl not \
 424                         in this crate");
 425                 return;
 426             }
 427
 428             let source = tcx.lookup_item_type(impl_did).ty;
 429             let trait_ref = self.crate_context.tcx.impl_trait_ref(impl_did).unwrap();
 430             let target = *trait_ref.substs.types.get(subst::TypeSpace, 0);
 431             debug!("check_implementations_of_coerce_unsized: {:?} -> {:?} (bound)",
 432                    source, target);
 433
 434             let span = tcx.map.span(impl_did.node);
 435             let param_env = ParameterEnvironment::for_item(tcx, impl_did.node);
 436             let source = source.subst(tcx, &param_env.free_substs);
 437             let target = target.subst(tcx, &param_env.free_substs);
 438             assert!(!source.has_escaping_regions());
 439
 440             debug!("check_implementations_of_coerce_unsized: {:?} -> {:?} (free)",
 441                    source, target);
 442
 443             let infcx = new_infer_ctxt(tcx, &tcx.tables, Some(param_env), true);
 444
 445             let check_mutbl = |mt_a: ty::TypeAndMut<'tcx>, mt_b: ty::TypeAndMut<'tcx>,
 446                                mk_ptr: &Fn(Ty<'tcx>) -> Ty<'tcx>| {
 447                 if (mt_a.mutbl, mt_b.mutbl) == (hir::MutImmutable, hir::MutMutable) {
 448                     infcx.report_mismatched_types(span, mk_ptr(mt_b.ty),
 449                                                   target, &ty::TypeError::Mutability);
 450                 }
 451                 (mt_a.ty, mt_b.ty, unsize_trait, None)
 452             };
 453             let (source, target, trait_def_id, kind) = match (&source.sty, &target.sty) {
 454                 (&ty::TyBox(a), &ty::TyBox(b)) => (a, b, unsize_trait, None),
 455
 456                 (&ty::TyRef(r_a, mt_a), &ty::TyRef(r_b, mt_b)) => {
 457                     infer::mk_subr(&infcx, infer::RelateObjectBound(span), *r_b, *r_a);
 458                     check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ref(r_b, ty))
 459                 }
 460
 461                 (&ty::TyRef(_, mt_a), &ty::TyRawPtr(mt_b)) |
 462                 (&ty::TyRawPtr(mt_a), &ty::TyRawPtr(mt_b)) => {
 463                     check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ptr(ty))
 464                 }
 465
 466                 (&ty::TyStruct(def_a, substs_a), &ty::TyStruct(def_b, substs_b)) => {
 467                     if def_a != def_b {
 468                         let source_path = tcx.item_path_str(def_a.did);
 469                         let target_path = tcx.item_path_str(def_b.did);
 470                         span_err!(tcx.sess, span, E0377,
 471                                   "the trait `CoerceUnsized` may only be implemented \
 472                                    for a coercion between structures with the same \
 473                                    definition; expected {}, found {}",
 474                                   source_path, target_path);
 475                         return;
 476                     }
 477
 478                     let origin = infer::Misc(span);
 479                     let fields = &def_a.struct_variant().fields;
 480                     let diff_fields = fields.iter().enumerate().filter_map(|(i, f)| {
 481                         let (a, b) = (f.ty(tcx, substs_a), f.ty(tcx, substs_b));
 482                         if infcx.sub_types(false, origin, b, a).is_ok() {
 483                             None
 484                         } else {
 485                             Some((i, a, b))
 486                         }
 487                     }).collect::<Vec<_>>();
 488
 489                     if diff_fields.is_empty() {
 490                         span_err!(tcx.sess, span, E0374,
 491                                   "the trait `CoerceUnsized` may only be implemented \
 492                                    for a coercion between structures with one field \
 493                                    being coerced, none found");
 494                         return;
 495                     } else if diff_fields.len() > 1 {
 496                         span_err!(tcx.sess, span, E0375,
 497                                   "the trait `CoerceUnsized` may only be implemented \
 498                                    for a coercion between structures with one field \
 499                                    being coerced, but {} fields need coercions: {}",
 500                                    diff_fields.len(), diff_fields.iter().map(|&(i, a, b)| {
 501                                         let name = fields[i].name;
 502                                         format!("{} ({} to {})",
 503                                                 if name == token::special_names::unnamed_field {
 504                                                     i.to_string()
 505                                                 } else {
 506                                                     name.to_string()
 507                                                 }, a, b)
 508                                    }).collect::<Vec<_>>().join(", "));
 509                         return;
 510                     }
 511
 512                     let (i, a, b) = diff_fields[0];
 513                     let kind = ty::CustomCoerceUnsized::Struct(i);
 514                     (a, b, coerce_unsized_trait, Some(kind))
 515                 }
 516
 517                 _ => {
 518                     span_err!(tcx.sess, span, E0376,
 519                               "the trait `CoerceUnsized` may only be implemented \
 520                                for a coercion between structures");
 521                     return;
 522                 }
 523             };
 524
 525             let mut fulfill_cx = infcx.fulfillment_cx.borrow_mut();
 526
 527             // Register an obligation for `A: Trait<B>`.
 528             let cause = traits::ObligationCause::misc(span, impl_did.node);
 529             let predicate = traits::predicate_for_trait_def(tcx, cause, trait_def_id,
 530                                                             0, source, vec![target]);
 531             fulfill_cx.register_predicate_obligation(&infcx, predicate);
 532
 533             // Check that all transitive obligations are satisfied.
 534             if let Err(errors) = fulfill_cx.select_all_or_error(&infcx) {
 535                 traits::report_fulfillment_errors(&infcx, &errors);
 536             }
 537
 538             // Finally, resolve all regions.
 539             let mut free_regions = FreeRegionMap::new();
 540             free_regions.relate_free_regions_from_predicates(tcx, &infcx.parameter_environment
 541                                                                         .caller_bounds);
 542             infcx.resolve_regions_and_report_errors(&free_regions, impl_did.node);
 543
 544             if let Some(kind) = kind {
 545                 tcx.custom_coerce_unsized_kinds.borrow_mut().insert(impl_did, kind);
 546             }
 547         });
 548     }
 549 }
 550
 551 fn enforce_trait_manually_implementable(tcx: &ty::ctxt, sp: Span, trait_def_id: DefId) {
 552     if tcx.sess.features.borrow().unboxed_closures {
 553         // the feature gate allows all of them
 554         return
 555     }
 556     let did = Some(trait_def_id);
 557     let li = &tcx.lang_items;
 558
 559     let trait_name = if did == li.fn_trait() {
 560         "Fn"
 561     } else if did == li.fn_mut_trait() {
 562         "FnMut"
 563     } else if did == li.fn_once_trait() {
 564         "FnOnce"
 565     } else {
 566         return // everything OK
 567     };
 568     span_err!(tcx.sess, sp, E0183, "manual implementations of `{}` are experimental", trait_name);
 569     fileline_help!(tcx.sess, sp,
 570                "add `#![feature(unboxed_closures)]` to the crate attributes to enable");
 571 }
 572
 573 fn subst_receiver_types_in_method_ty<'tcx>(tcx: &ty::ctxt<'tcx>,
 574                                            impl_id: DefId,
 575                                            impl_type_scheme: &ty::TypeScheme<'tcx>,
 576                                            trait_ref: &ty::TraitRef<'tcx>,
 577                                            new_def_id: DefId,
 578                                            method: &ty::Method<'tcx>,
 579                                            provided_source: Option<DefId>)
 580                                            -> ty::Method<'tcx>
 581 {
 582     let combined_substs = tcx.make_substs_for_receiver_types(trait_ref, method);
 583
 584     debug!("subst_receiver_types_in_method_ty: combined_substs={:?}",
 585            combined_substs);
 586
 587     let method_predicates = method.predicates.subst(tcx, &combined_substs);
 588     let mut method_generics = method.generics.subst(tcx, &combined_substs);
 589
 590     // replace the type parameters declared on the trait with those
 591     // from the impl
 592     for &space in &[subst::TypeSpace, subst::SelfSpace] {
 593         method_generics.types.replace(
 594             space,
 595             impl_type_scheme.generics.types.get_slice(space).to_vec());
 596         method_generics.regions.replace(
 597             space,
 598             impl_type_scheme.generics.regions.get_slice(space).to_vec());
 599     }
 600
 601     debug!("subst_receiver_types_in_method_ty: method_generics={:?}",
 602            method_generics);
 603
 604     let method_fty = method.fty.subst(tcx, &combined_substs);
 605
 606     debug!("subst_receiver_types_in_method_ty: method_ty={:?}",
 607            method.fty);
 608
 609     ty::Method::new(
 610         method.name,
 611         method_generics,
 612         method_predicates,
 613         method_fty,
 614         method.explicit_self,
 615         method.vis,
 616         new_def_id,
 617         ImplContainer(impl_id),
 618         provided_source
 619     )
 620 }
 621
 622 pub fn check_coherence(crate_context: &CrateCtxt) {
 623     CoherenceChecker {
 624         crate_context: crate_context,
 625         inference_context: new_infer_ctxt(crate_context.tcx, &crate_context.tcx.tables, None, true),
 626         inherent_impls: RefCell::new(FnvHashMap()),
 627     }.check(crate_context.tcx.map.krate());
 628     unsafety::check(crate_context.tcx);
 629     orphan::check(crate_context.tcx);
 630     overlap::check(crate_context.tcx);
 631 }