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