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.
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.
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.
19 use middle::lang_items::UnsizeTraitLangItem;
20 use middle::subst::{self, Subst};
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;
32 use middle::free_region::FreeRegionMap;
34 use middle::infer::{self, InferCtxt, new_infer_ctxt};
35 use rustc::ast_map::{self, NodeItem};
36 use std::cell::RefCell;
38 use syntax::ast::{Crate, DefId};
39 use syntax::ast::{Item, ItemImpl};
40 use syntax::ast::{LOCAL_CRATE};
42 use syntax::ast_util::local_def;
43 use syntax::codemap::Span;
44 use syntax::parse::token;
46 use util::nodemap::{DefIdMap, FnvHashMap};
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>,
59 TyStruct(def_id, _) => {
64 Some(t.principal_def_id())
68 inference_context.tcx.lang_items.owned_box()
71 TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
72 TyStr(..) | TyArray(..) | TySlice(..) | TyBareFn(..) | TyTuple(..) |
73 TyParam(..) | TyError |
74 TyRawPtr(_) | TyRef(_, _) | TyProjection(..) => {
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(
83 &format!("coherence encountered unexpected type searching for base type: {}",
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>>>>>,
95 struct CoherenceCheckVisitor<'a, 'tcx: 'a> {
96 cc: &'a CoherenceChecker<'a, 'tcx>
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)
105 visit::walk_item(self, item);
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);
117 // Copy over the inherent impls we gathered up during the walk into
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()));
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();
131 // Check to make sure implementations of `Copy` are legal.
132 self.check_implementations_of_copy();
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();
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 = tcx.lookup_item_type(impl_did);
144 // If there are no traits, then this implementation must have a
147 let impl_items = self.create_impl_from_item(item);
149 if let Some(trait_ref) = self.crate_context.tcx.impl_trait_ref(impl_did) {
150 debug!("(checking implementation) adding impl for trait '{:?}', item '{}'",
154 enforce_trait_manually_implementable(self.crate_context.tcx,
157 self.add_trait_impl(trait_ref, impl_did);
159 // Add the implementation to the mapping from implementation to base
160 // type def ID, if there is a base type for this implementation and
161 // the implementation does not have any associated traits.
162 if let Some(base_type_def_id) = get_base_type_def_id(
163 &self.inference_context, item.span, self_type.ty) {
164 self.add_inherent_impl(base_type_def_id, impl_did);
168 tcx.impl_items.borrow_mut().insert(impl_did, impl_items);
171 // Creates default method IDs and performs type substitutions for an impl
172 // and trait pair. Then, for each provided method in the trait, inserts a
173 // `ProvidedMethodInfo` instance into the `provided_method_sources` map.
174 fn instantiate_default_methods(
177 trait_ref: &ty::TraitRef<'tcx>,
178 all_impl_items: &mut Vec<ImplOrTraitItemId>) {
179 let tcx = self.crate_context.tcx;
180 debug!("instantiate_default_methods(impl_id={:?}, trait_ref={:?})",
183 let impl_type_scheme = tcx.lookup_item_type(impl_id);
185 let prov = tcx.provided_trait_methods(trait_ref.def_id);
186 for trait_method in &prov {
188 let new_id = tcx.sess.next_node_id();
189 let new_did = local_def(new_id);
191 debug!("new_did={:?} trait_method={:?}", new_did, trait_method);
193 // Create substitutions for the various trait parameters.
195 Rc::new(subst_receiver_types_in_method_ty(
202 Some(trait_method.def_id)));
204 debug!("new_method_ty={:?}", new_method_ty);
205 all_impl_items.push(MethodTraitItemId(new_did));
207 // construct the polytype for the method based on the
208 // method_ty. it will have all the generics from the
209 // impl, plus its own.
210 let new_polytype = ty::TypeScheme {
211 generics: new_method_ty.generics.clone(),
212 ty: tcx.mk_fn(Some(new_did),
213 tcx.mk_bare_fn(new_method_ty.fty.clone()))
215 debug!("new_polytype={:?}", new_polytype);
217 tcx.register_item_type(new_did, new_polytype);
218 tcx.predicates.borrow_mut().insert(new_did, new_method_ty.predicates.clone());
219 tcx.impl_or_trait_items
221 .insert(new_did, ty::MethodTraitItem(new_method_ty));
223 // Pair the new synthesized ID up with the
225 self.crate_context.tcx.provided_method_sources.borrow_mut()
226 .insert(new_did, trait_method.def_id);
230 fn add_inherent_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
231 match self.inherent_impls.borrow().get(&base_def_id) {
232 Some(implementation_list) => {
233 implementation_list.borrow_mut().push(impl_def_id);
239 self.inherent_impls.borrow_mut().insert(
241 Rc::new(RefCell::new(vec!(impl_def_id))));
244 fn add_trait_impl(&self, impl_trait_ref: ty::TraitRef<'tcx>, impl_def_id: DefId) {
245 debug!("add_trait_impl: impl_trait_ref={:?} impl_def_id={:?}",
246 impl_trait_ref, impl_def_id);
247 let trait_def = self.crate_context.tcx.lookup_trait_def(impl_trait_ref.def_id);
248 trait_def.record_impl(self.crate_context.tcx, impl_def_id, impl_trait_ref);
251 // Converts an implementation in the AST to a vector of items.
252 fn create_impl_from_item(&self, item: &Item) -> Vec<ImplOrTraitItemId> {
254 ItemImpl(_, _, _, _, _, ref impl_items) => {
255 let mut items: Vec<ImplOrTraitItemId> =
256 impl_items.iter().map(|impl_item| {
257 match impl_item.node {
258 ast::ConstImplItem(..) => {
259 ConstTraitItemId(local_def(impl_item.id))
261 ast::MethodImplItem(..) => {
262 MethodTraitItemId(local_def(impl_item.id))
264 ast::TypeImplItem(_) => {
265 TypeTraitItemId(local_def(impl_item.id))
267 ast::MacImplItem(_) => {
268 self.crate_context.tcx.sess.span_bug(impl_item.span,
274 let def_id = local_def(item.id);
275 if let Some(trait_ref) = self.crate_context.tcx.impl_trait_ref(def_id) {
276 self.instantiate_default_methods(def_id, &trait_ref, &mut items);
282 self.crate_context.tcx.sess.span_bug(item.span,
283 "can't convert a non-impl \
293 fn populate_destructor_table(&self) {
294 let tcx = self.crate_context.tcx;
295 let drop_trait = match tcx.lang_items.drop_trait() {
296 Some(id) => id, None => { return }
298 tcx.populate_implementations_for_trait_if_necessary(drop_trait);
299 let drop_trait = tcx.lookup_trait_def(drop_trait);
301 let impl_items = tcx.impl_items.borrow();
303 drop_trait.for_each_impl(tcx, |impl_did| {
304 let items = impl_items.get(&impl_did).unwrap();
305 if items.is_empty() {
306 // We'll error out later. For now, just don't ICE.
309 let method_def_id = items[0];
311 let self_type = tcx.lookup_item_type(impl_did);
312 match self_type.ty.sty {
313 ty::TyEnum(type_def_id, _) |
314 ty::TyStruct(type_def_id, _) |
315 ty::TyClosure(type_def_id, _) => {
316 tcx.destructor_for_type
318 .insert(type_def_id, method_def_id.def_id());
321 .insert(method_def_id.def_id());
324 // Destructors only work on nominal types.
325 if impl_did.krate == ast::LOCAL_CRATE {
327 match tcx.map.find(impl_did.node) {
328 Some(ast_map::NodeItem(item)) => {
329 span_err!(tcx.sess, item.span, E0120,
330 "the Drop trait may only be implemented on structures");
333 tcx.sess.bug("didn't find impl in ast \
339 tcx.sess.bug("found external impl of Drop trait on \
340 something other than a struct");
347 /// Ensures that implementations of the built-in trait `Copy` are legal.
348 fn check_implementations_of_copy(&self) {
349 let tcx = self.crate_context.tcx;
350 let copy_trait = match tcx.lang_items.copy_trait() {
354 tcx.populate_implementations_for_trait_if_necessary(copy_trait);
355 let copy_trait = tcx.lookup_trait_def(copy_trait);
357 copy_trait.for_each_impl(tcx, |impl_did| {
358 debug!("check_implementations_of_copy: impl_did={:?}",
361 if impl_did.krate != ast::LOCAL_CRATE {
362 debug!("check_implementations_of_copy(): impl not in this \
367 let self_type = tcx.lookup_item_type(impl_did);
368 debug!("check_implementations_of_copy: self_type={:?} (bound)",
371 let span = tcx.map.span(impl_did.node);
372 let param_env = ParameterEnvironment::for_item(tcx, impl_did.node);
373 let self_type = self_type.ty.subst(tcx, ¶m_env.free_substs);
374 assert!(!self_type.has_escaping_regions());
376 debug!("check_implementations_of_copy: self_type={:?} (free)",
379 match param_env.can_type_implement_copy(self_type, span) {
381 Err(ty::FieldDoesNotImplementCopy(name)) => {
382 span_err!(tcx.sess, span, E0204,
383 "the trait `Copy` may not be \
384 implemented for this type; field \
385 `{}` does not implement `Copy`",
386 token::get_name(name))
388 Err(ty::VariantDoesNotImplementCopy(name)) => {
389 span_err!(tcx.sess, span, E0205,
390 "the trait `Copy` may not be \
391 implemented for this type; variant \
392 `{}` does not implement `Copy`",
393 token::get_name(name))
395 Err(ty::TypeIsStructural) => {
396 span_err!(tcx.sess, span, E0206,
397 "the trait `Copy` may not be implemented \
398 for this type; type is not a structure or \
401 Err(ty::TypeHasDestructor) => {
402 span_err!(tcx.sess, span, E0184,
403 "the trait `Copy` may not be implemented for this type; \
404 the type has a destructor");
410 /// Process implementations of the built-in trait `CoerceUnsized`.
411 fn check_implementations_of_coerce_unsized(&self) {
412 let tcx = self.crate_context.tcx;
413 let coerce_unsized_trait = match tcx.lang_items.coerce_unsized_trait() {
417 let unsize_trait = match tcx.lang_items.require(UnsizeTraitLangItem) {
420 tcx.sess.fatal(&format!("`CoerceUnsized` implementation {}", err));
424 let trait_def = tcx.lookup_trait_def(coerce_unsized_trait);
426 trait_def.for_each_impl(tcx, |impl_did| {
427 debug!("check_implementations_of_coerce_unsized: impl_did={:?}",
430 if impl_did.krate != ast::LOCAL_CRATE {
431 debug!("check_implementations_of_coerce_unsized(): impl not \
436 let source = tcx.lookup_item_type(impl_did).ty;
437 let trait_ref = self.crate_context.tcx.impl_trait_ref(impl_did).unwrap();
438 let target = *trait_ref.substs.types.get(subst::TypeSpace, 0);
439 debug!("check_implementations_of_coerce_unsized: {:?} -> {:?} (bound)",
442 let span = tcx.map.span(impl_did.node);
443 let param_env = ParameterEnvironment::for_item(tcx, impl_did.node);
444 let source = source.subst(tcx, ¶m_env.free_substs);
445 let target = target.subst(tcx, ¶m_env.free_substs);
446 assert!(!source.has_escaping_regions());
448 debug!("check_implementations_of_coerce_unsized: {:?} -> {:?} (free)",
451 let infcx = new_infer_ctxt(tcx, &tcx.tables, Some(param_env), true);
453 let check_mutbl = |mt_a: ty::mt<'tcx>, mt_b: ty::mt<'tcx>,
454 mk_ptr: &Fn(Ty<'tcx>) -> Ty<'tcx>| {
455 if (mt_a.mutbl, mt_b.mutbl) == (ast::MutImmutable, ast::MutMutable) {
456 infcx.report_mismatched_types(span, mk_ptr(mt_b.ty),
457 target, &ty::terr_mutability);
459 (mt_a.ty, mt_b.ty, unsize_trait, None)
461 let (source, target, trait_def_id, kind) = match (&source.sty, &target.sty) {
462 (&ty::TyBox(a), &ty::TyBox(b)) => (a, b, unsize_trait, None),
464 (&ty::TyRef(r_a, mt_a), &ty::TyRef(r_b, mt_b)) => {
465 infer::mk_subr(&infcx, infer::RelateObjectBound(span), *r_b, *r_a);
466 check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ref(r_b, ty))
469 (&ty::TyRef(_, mt_a), &ty::TyRawPtr(mt_b)) |
470 (&ty::TyRawPtr(mt_a), &ty::TyRawPtr(mt_b)) => {
471 check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ptr(ty))
474 (&ty::TyStruct(def_id_a, substs_a), &ty::TyStruct(def_id_b, substs_b)) => {
475 if def_id_a != def_id_b {
476 let source_path = tcx.item_path_str(def_id_a);
477 let target_path = tcx.item_path_str(def_id_b);
478 span_err!(tcx.sess, span, E0377,
479 "the trait `CoerceUnsized` may only be implemented \
480 for a coercion between structures with the same \
481 definition; expected {}, found {}",
482 source_path, target_path);
486 let origin = infer::Misc(span);
487 let fields = tcx.lookup_struct_fields(def_id_a);
488 let diff_fields = fields.iter().enumerate().filter_map(|(i, f)| {
489 let ty = tcx.lookup_field_type_unsubstituted(def_id_a, f.id);
490 let (a, b) = (ty.subst(tcx, substs_a), ty.subst(tcx, substs_b));
491 if infcx.sub_types(false, origin, b, a).is_ok() {
496 }).collect::<Vec<_>>();
498 if diff_fields.is_empty() {
499 span_err!(tcx.sess, span, E0374,
500 "the trait `CoerceUnsized` may only be implemented \
501 for a coercion between structures with one field \
502 being coerced, none found");
504 } else if diff_fields.len() > 1 {
505 span_err!(tcx.sess, span, E0375,
506 "the trait `CoerceUnsized` may only be implemented \
507 for a coercion between structures with one field \
508 being coerced, but {} fields need coercions: {}",
509 diff_fields.len(), diff_fields.iter().map(|&(i, a, b)| {
510 let name = fields[i].name;
511 format!("{} ({} to {})",
512 if name == token::special_names::unnamed_field {
517 }).collect::<Vec<_>>().join(", "));
521 let (i, a, b) = diff_fields[0];
522 let kind = ty::CustomCoerceUnsized::Struct(i);
523 (a, b, coerce_unsized_trait, Some(kind))
527 span_err!(tcx.sess, span, E0376,
528 "the trait `CoerceUnsized` may only be implemented \
529 for a coercion between structures");
534 let mut fulfill_cx = infcx.fulfillment_cx.borrow_mut();
536 // Register an obligation for `A: Trait<B>`.
537 let cause = traits::ObligationCause::misc(span, impl_did.node);
538 let predicate = traits::predicate_for_trait_def(tcx, cause, trait_def_id,
539 0, source, vec![target]);
540 fulfill_cx.register_predicate_obligation(&infcx, predicate);
542 // Check that all transitive obligations are satisfied.
543 if let Err(errors) = fulfill_cx.select_all_or_error(&infcx) {
544 traits::report_fulfillment_errors(&infcx, &errors);
547 // Finally, resolve all regions.
548 let mut free_regions = FreeRegionMap::new();
549 free_regions.relate_free_regions_from_predicates(tcx, &infcx.parameter_environment
551 infcx.resolve_regions_and_report_errors(&free_regions, impl_did.node);
553 if let Some(kind) = kind {
554 tcx.custom_coerce_unsized_kinds.borrow_mut().insert(impl_did, kind);
560 fn enforce_trait_manually_implementable(tcx: &ty::ctxt, sp: Span, trait_def_id: ast::DefId) {
561 if tcx.sess.features.borrow().unboxed_closures {
562 // the feature gate allows all of them
565 let did = Some(trait_def_id);
566 let li = &tcx.lang_items;
568 let trait_name = if did == li.fn_trait() {
570 } else if did == li.fn_mut_trait() {
572 } else if did == li.fn_once_trait() {
575 return // everything OK
577 span_err!(tcx.sess, sp, E0183, "manual implementations of `{}` are experimental", trait_name);
578 fileline_help!(tcx.sess, sp,
579 "add `#![feature(unboxed_closures)]` to the crate attributes to enable");
582 fn subst_receiver_types_in_method_ty<'tcx>(tcx: &ty::ctxt<'tcx>,
584 impl_type_scheme: &ty::TypeScheme<'tcx>,
585 trait_ref: &ty::TraitRef<'tcx>,
586 new_def_id: ast::DefId,
587 method: &ty::Method<'tcx>,
588 provided_source: Option<ast::DefId>)
591 let combined_substs = tcx.make_substs_for_receiver_types(trait_ref, method);
593 debug!("subst_receiver_types_in_method_ty: combined_substs={:?}",
596 let method_predicates = method.predicates.subst(tcx, &combined_substs);
597 let mut method_generics = method.generics.subst(tcx, &combined_substs);
599 // replace the type parameters declared on the trait with those
601 for &space in &[subst::TypeSpace, subst::SelfSpace] {
602 method_generics.types.replace(
604 impl_type_scheme.generics.types.get_slice(space).to_vec());
605 method_generics.regions.replace(
607 impl_type_scheme.generics.regions.get_slice(space).to_vec());
610 debug!("subst_receiver_types_in_method_ty: method_generics={:?}",
613 let method_fty = method.fty.subst(tcx, &combined_substs);
615 debug!("subst_receiver_types_in_method_ty: method_ty={:?}",
623 method.explicit_self,
626 ImplContainer(impl_id),
631 pub fn check_coherence(crate_context: &CrateCtxt) {
633 crate_context: crate_context,
634 inference_context: new_infer_ctxt(crate_context.tcx, &crate_context.tcx.tables, None, true),
635 inherent_impls: RefCell::new(FnvHashMap()),
636 }.check(crate_context.tcx.map.krate());
637 unsafety::check(crate_context.tcx);
638 orphan::check(crate_context.tcx);
639 overlap::check(crate_context.tcx);