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