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.
18 use hir::def_id::DefId;
19 use middle::lang_items::UnsizeTraitLangItem;
20 use rustc::ty::subst::Subst;
21 use rustc::ty::{self, TyCtxt, TypeFoldable};
22 use rustc::traits::{self, Reveal};
23 use rustc::ty::{ImplOrTraitItemId, ConstTraitItemId};
24 use rustc::ty::{MethodTraitItemId, TypeTraitItemId, ParameterEnvironment};
25 use rustc::ty::{Ty, TyBool, TyChar, TyEnum, TyError};
26 use rustc::ty::{TyParam, TyRawPtr};
27 use rustc::ty::{TyRef, TyStruct, TyTrait, TyNever, TyTuple};
28 use rustc::ty::{TyStr, TyArray, TySlice, TyFloat, TyInfer, TyInt};
29 use rustc::ty::{TyUint, TyClosure, TyBox, TyFnDef, TyFnPtr};
30 use rustc::ty::{TyProjection, TyAnon};
31 use rustc::ty::util::CopyImplementationError;
32 use middle::free_region::FreeRegionMap;
34 use rustc::infer::{self, InferCtxt, TypeOrigin};
35 use std::cell::RefCell;
38 use util::nodemap::{DefIdMap, FnvHashMap};
39 use rustc::dep_graph::DepNode;
40 use rustc::hir::map as hir_map;
41 use rustc::hir::intravisit;
42 use rustc::hir::{Item, ItemImpl};
49 struct CoherenceChecker<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
50 crate_context: &'a CrateCtxt<'a, 'gcx>,
51 inference_context: InferCtxt<'a, 'gcx, 'tcx>,
52 inherent_impls: RefCell<DefIdMap<Rc<RefCell<Vec<DefId>>>>>,
55 struct CoherenceCheckVisitor<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
56 cc: &'a CoherenceChecker<'a, 'gcx, 'tcx>
59 impl<'a, 'gcx, 'tcx, 'v> intravisit::Visitor<'v> for CoherenceCheckVisitor<'a, 'gcx, 'tcx> {
60 fn visit_item(&mut self, item: &Item) {
61 if let ItemImpl(..) = item.node {
62 self.cc.check_implementation(item)
67 impl<'a, 'gcx, 'tcx> CoherenceChecker<'a, 'gcx, 'tcx> {
69 // Returns the def ID of the base type, if there is one.
70 fn get_base_type_def_id(&self, span: Span, ty: Ty<'tcx>) -> Option<DefId> {
78 Some(t.principal.def_id())
82 self.inference_context.tcx.lang_items.owned_box()
85 TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
86 TyStr | TyArray(..) | TySlice(..) | TyFnDef(..) | TyFnPtr(_) |
87 TyTuple(..) | TyParam(..) | TyError | TyNever |
88 TyRawPtr(_) | TyRef(_, _) | TyProjection(..) => {
92 TyInfer(..) | TyClosure(..) | TyAnon(..) => {
93 // `ty` comes from a user declaration so we should only expect types
94 // that the user can type
97 "coherence encountered unexpected type searching for base type: {}",
104 // Check implementations and traits. This populates the tables
105 // containing the inherent methods and extension methods. It also
106 // builds up the trait inheritance table.
107 self.crate_context.tcx.visit_all_items_in_krate(
108 DepNode::CoherenceCheckImpl,
109 &mut CoherenceCheckVisitor { cc: self });
111 // Copy over the inherent impls we gathered up during the walk into
113 let mut tcx_inherent_impls =
114 self.crate_context.tcx.inherent_impls.borrow_mut();
115 for (k, v) in self.inherent_impls.borrow().iter() {
116 tcx_inherent_impls.insert((*k).clone(),
117 Rc::new((*v.borrow()).clone()));
120 // Populate the table of destructors. It might seem a bit strange to
121 // do this here, but it's actually the most convenient place, since
122 // the coherence tables contain the trait -> type mappings.
123 self.populate_destructors();
125 // Check to make sure implementations of `Copy` are legal.
126 self.check_implementations_of_copy();
128 // Check to make sure implementations of `CoerceUnsized` are legal
129 // and collect the necessary information from them.
130 self.check_implementations_of_coerce_unsized();
133 fn check_implementation(&self, item: &Item) {
134 let tcx = self.crate_context.tcx;
135 let impl_did = tcx.map.local_def_id(item.id);
136 let self_type = tcx.lookup_item_type(impl_did);
138 // If there are no traits, then this implementation must have a
141 let impl_items = self.create_impl_from_item(item);
143 if let Some(trait_ref) = self.crate_context.tcx.impl_trait_ref(impl_did) {
144 debug!("(checking implementation) adding impl for trait '{:?}', item '{}'",
148 // Skip impls where one of the self type is an error type.
149 // This occurs with e.g. resolve failures (#30589).
150 if trait_ref.references_error() {
154 enforce_trait_manually_implementable(self.crate_context.tcx,
157 self.add_trait_impl(trait_ref, impl_did);
159 // Skip inherent impls where the self type is an error
160 // type. This occurs with e.g. resolve failures (#30589).
161 if self_type.ty.references_error() {
165 // Add the implementation to the mapping from implementation to base
166 // type def ID, if there is a base type for this implementation and
167 // the implementation does not have any associated traits.
168 if let Some(base_def_id) = self.get_base_type_def_id(item.span, self_type.ty) {
169 self.add_inherent_impl(base_def_id, impl_did);
173 tcx.impl_items.borrow_mut().insert(impl_did, impl_items);
176 fn add_inherent_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
177 if let Some(implementation_list) = self.inherent_impls.borrow().get(&base_def_id) {
178 implementation_list.borrow_mut().push(impl_def_id);
182 self.inherent_impls.borrow_mut().insert(
184 Rc::new(RefCell::new(vec!(impl_def_id))));
187 fn add_trait_impl(&self, impl_trait_ref: ty::TraitRef<'gcx>, impl_def_id: DefId) {
188 debug!("add_trait_impl: impl_trait_ref={:?} impl_def_id={:?}",
189 impl_trait_ref, impl_def_id);
190 let trait_def = self.crate_context.tcx.lookup_trait_def(impl_trait_ref.def_id);
191 trait_def.record_local_impl(self.crate_context.tcx, impl_def_id, impl_trait_ref);
194 // Converts an implementation in the AST to a vector of items.
195 fn create_impl_from_item(&self, item: &Item) -> Vec<ImplOrTraitItemId> {
197 ItemImpl(_, _, _, _, _, ref impl_items) => {
198 impl_items.iter().map(|impl_item| {
199 let impl_def_id = self.crate_context.tcx.map.local_def_id(impl_item.id);
200 match impl_item.node {
201 hir::ImplItemKind::Const(..) => {
202 ConstTraitItemId(impl_def_id)
204 hir::ImplItemKind::Method(..) => {
205 MethodTraitItemId(impl_def_id)
207 hir::ImplItemKind::Type(_) => {
208 TypeTraitItemId(impl_def_id)
214 span_bug!(item.span, "can't convert a non-impl to an impl");
223 fn populate_destructors(&self) {
224 let tcx = self.crate_context.tcx;
225 let drop_trait = match tcx.lang_items.drop_trait() {
226 Some(id) => id, None => { return }
228 tcx.populate_implementations_for_trait_if_necessary(drop_trait);
229 let drop_trait = tcx.lookup_trait_def(drop_trait);
231 let impl_items = tcx.impl_items.borrow();
233 drop_trait.for_each_impl(tcx, |impl_did| {
234 let items = impl_items.get(&impl_did).unwrap();
235 if items.is_empty() {
236 // We'll error out later. For now, just don't ICE.
239 let method_def_id = items[0];
241 let self_type = tcx.lookup_item_type(impl_did);
242 match self_type.ty.sty {
243 ty::TyEnum(type_def, _) |
244 ty::TyStruct(type_def, _) => {
245 type_def.set_destructor(method_def_id.def_id());
248 // Destructors only work on nominal types.
249 if let Some(impl_node_id) = tcx.map.as_local_node_id(impl_did) {
250 match tcx.map.find(impl_node_id) {
251 Some(hir_map::NodeItem(item)) => {
252 let span = match item.node {
253 ItemImpl(_, _, _, _, ref ty, _) => {
258 struct_span_err!(tcx.sess, span, E0120,
259 "the Drop trait may only be implemented on structures")
261 &format!("implementing Drop requires a struct"))
265 bug!("didn't find impl in ast map");
269 bug!("found external impl of Drop trait on \
270 something other than a struct");
277 /// Ensures that implementations of the built-in trait `Copy` are legal.
278 fn check_implementations_of_copy(&self) {
279 let tcx = self.crate_context.tcx;
280 let copy_trait = match tcx.lang_items.copy_trait() {
284 tcx.populate_implementations_for_trait_if_necessary(copy_trait);
285 let copy_trait = tcx.lookup_trait_def(copy_trait);
287 copy_trait.for_each_impl(tcx, |impl_did| {
288 debug!("check_implementations_of_copy: impl_did={:?}",
291 let impl_node_id = if let Some(n) = tcx.map.as_local_node_id(impl_did) {
294 debug!("check_implementations_of_copy(): impl not in this \
299 let self_type = tcx.lookup_item_type(impl_did);
300 debug!("check_implementations_of_copy: self_type={:?} (bound)",
303 let span = tcx.map.span(impl_node_id);
304 let param_env = ParameterEnvironment::for_item(tcx, impl_node_id);
305 let self_type = self_type.ty.subst(tcx, ¶m_env.free_substs);
306 assert!(!self_type.has_escaping_regions());
308 debug!("check_implementations_of_copy: self_type={:?} (free)",
311 match param_env.can_type_implement_copy(tcx, self_type, span) {
313 Err(CopyImplementationError::InfrigingField(name)) => {
314 struct_span_err!(tcx.sess, span, E0204,
315 "the trait `Copy` may not be implemented for \
317 .span_label(span, &format!(
318 "field `{}` does not implement `Copy`", name)
323 Err(CopyImplementationError::InfrigingVariant(name)) => {
324 let item = tcx.map.expect_item(impl_node_id);
325 let span = if let ItemImpl(_, _, _, Some(ref tr), _, _) = item.node {
331 struct_span_err!(tcx.sess, span, E0205,
332 "the trait `Copy` may not be implemented for this type")
333 .span_label(span, &format!("variant `{}` does not implement `Copy`",
337 Err(CopyImplementationError::NotAnAdt) => {
338 let item = tcx.map.expect_item(impl_node_id);
339 let span = if let ItemImpl(_, _, _, _, ref ty, _) = item.node {
345 struct_span_err!(tcx.sess, span, E0206,
346 "the trait `Copy` may not be implemented for this type")
347 .span_label(span, &format!("type is not a structure or enumeration"))
350 Err(CopyImplementationError::HasDestructor) => {
351 struct_span_err!(tcx.sess, span, E0184,
352 "the trait `Copy` may not be implemented for this type; \
353 the type has a destructor")
354 .span_label(span, &format!("Copy not allowed on types with destructors"))
361 /// Process implementations of the built-in trait `CoerceUnsized`.
362 fn check_implementations_of_coerce_unsized(&self) {
363 let tcx = self.crate_context.tcx;
364 let coerce_unsized_trait = match tcx.lang_items.coerce_unsized_trait() {
368 let unsize_trait = match tcx.lang_items.require(UnsizeTraitLangItem) {
371 tcx.sess.fatal(&format!("`CoerceUnsized` implementation {}", err));
375 let trait_def = tcx.lookup_trait_def(coerce_unsized_trait);
377 trait_def.for_each_impl(tcx, |impl_did| {
378 debug!("check_implementations_of_coerce_unsized: impl_did={:?}",
381 let impl_node_id = if let Some(n) = tcx.map.as_local_node_id(impl_did) {
384 debug!("check_implementations_of_coerce_unsized(): impl not \
389 let source = tcx.lookup_item_type(impl_did).ty;
390 let trait_ref = self.crate_context.tcx.impl_trait_ref(impl_did).unwrap();
391 let target = trait_ref.substs.type_at(1);
392 debug!("check_implementations_of_coerce_unsized: {:?} -> {:?} (bound)",
395 let span = tcx.map.span(impl_node_id);
396 let param_env = ParameterEnvironment::for_item(tcx, impl_node_id);
397 let source = source.subst(tcx, ¶m_env.free_substs);
398 let target = target.subst(tcx, ¶m_env.free_substs);
399 assert!(!source.has_escaping_regions());
401 debug!("check_implementations_of_coerce_unsized: {:?} -> {:?} (free)",
404 tcx.infer_ctxt(None, Some(param_env), Reveal::ExactMatch).enter(|infcx| {
405 let origin = TypeOrigin::Misc(span);
406 let check_mutbl = |mt_a: ty::TypeAndMut<'gcx>, mt_b: ty::TypeAndMut<'gcx>,
407 mk_ptr: &Fn(Ty<'gcx>) -> Ty<'gcx>| {
408 if (mt_a.mutbl, mt_b.mutbl) == (hir::MutImmutable, hir::MutMutable) {
409 infcx.report_mismatched_types(origin, mk_ptr(mt_b.ty),
410 target, ty::error::TypeError::Mutability);
412 (mt_a.ty, mt_b.ty, unsize_trait, None)
414 let (source, target, trait_def_id, kind) = match (&source.sty, &target.sty) {
415 (&ty::TyBox(a), &ty::TyBox(b)) => (a, b, unsize_trait, None),
417 (&ty::TyRef(r_a, mt_a), &ty::TyRef(r_b, mt_b)) => {
418 infcx.sub_regions(infer::RelateObjectBound(span), r_b, r_a);
419 check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ref(r_b, ty))
422 (&ty::TyRef(_, mt_a), &ty::TyRawPtr(mt_b)) |
423 (&ty::TyRawPtr(mt_a), &ty::TyRawPtr(mt_b)) => {
424 check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ptr(ty))
427 (&ty::TyStruct(def_a, substs_a), &ty::TyStruct(def_b, substs_b)) => {
429 let source_path = tcx.item_path_str(def_a.did);
430 let target_path = tcx.item_path_str(def_b.did);
431 span_err!(tcx.sess, span, E0377,
432 "the trait `CoerceUnsized` may only be implemented \
433 for a coercion between structures with the same \
434 definition; expected {}, found {}",
435 source_path, target_path);
439 let fields = &def_a.struct_variant().fields;
440 let diff_fields = fields.iter().enumerate().filter_map(|(i, f)| {
441 let (a, b) = (f.ty(tcx, substs_a), f.ty(tcx, substs_b));
443 if f.unsubst_ty().is_phantom_data() {
444 // Ignore PhantomData fields
446 } else if infcx.sub_types(false, origin, b, a).is_ok() {
447 // Ignore fields that aren't significantly changed
450 // Collect up all fields that were significantly changed
451 // i.e. those that contain T in coerce_unsized T -> U
454 }).collect::<Vec<_>>();
456 if diff_fields.is_empty() {
457 span_err!(tcx.sess, span, E0374,
458 "the trait `CoerceUnsized` may only be implemented \
459 for a coercion between structures with one field \
460 being coerced, none found");
462 } else if diff_fields.len() > 1 {
463 let item = tcx.map.expect_item(impl_node_id);
464 let span = if let ItemImpl(_, _, _, Some(ref t), _, _) = item.node {
467 tcx.map.span(impl_node_id)
470 let mut err = struct_span_err!(tcx.sess, span, E0375,
471 "implementing the trait `CoerceUnsized` \
472 requires multiple coercions");
473 err.note("`CoerceUnsized` may only be implemented for \
474 a coercion between structures with one field being coerced");
475 err.note(&format!("currently, {} fields need coercions: {}",
477 diff_fields.iter().map(|&(i, a, b)| {
478 format!("{} ({} to {})", fields[i].name, a, b)
479 }).collect::<Vec<_>>().join(", ") ));
480 err.span_label(span, &format!("requires multiple coercions"));
485 let (i, a, b) = diff_fields[0];
486 let kind = ty::adjustment::CustomCoerceUnsized::Struct(i);
487 (a, b, coerce_unsized_trait, Some(kind))
491 span_err!(tcx.sess, span, E0376,
492 "the trait `CoerceUnsized` may only be implemented \
493 for a coercion between structures");
498 let mut fulfill_cx = traits::FulfillmentContext::new();
500 // Register an obligation for `A: Trait<B>`.
501 let cause = traits::ObligationCause::misc(span, impl_node_id);
502 let predicate = tcx.predicate_for_trait_def(cause, trait_def_id, 0,
504 fulfill_cx.register_predicate_obligation(&infcx, predicate);
506 // Check that all transitive obligations are satisfied.
507 if let Err(errors) = fulfill_cx.select_all_or_error(&infcx) {
508 infcx.report_fulfillment_errors(&errors);
511 // Finally, resolve all regions.
512 let mut free_regions = FreeRegionMap::new();
513 free_regions.relate_free_regions_from_predicates(
514 &infcx.parameter_environment.caller_bounds);
515 infcx.resolve_regions_and_report_errors(&free_regions, impl_node_id);
517 if let Some(kind) = kind {
518 tcx.custom_coerce_unsized_kinds.borrow_mut().insert(impl_did, kind);
525 fn enforce_trait_manually_implementable(tcx: TyCtxt, sp: Span, trait_def_id: DefId) {
526 if tcx.sess.features.borrow().unboxed_closures {
527 // the feature gate allows all of them
530 let did = Some(trait_def_id);
531 let li = &tcx.lang_items;
533 let trait_name = if did == li.fn_trait() {
535 } else if did == li.fn_mut_trait() {
537 } else if did == li.fn_once_trait() {
540 return // everything OK
542 let mut err = struct_span_err!(tcx.sess,
545 "manual implementations of `{}` are experimental",
547 help!(&mut err, "add `#![feature(unboxed_closures)]` to the crate attributes to enable");
551 pub fn check_coherence(ccx: &CrateCtxt) {
552 let _task = ccx.tcx.dep_graph.in_task(DepNode::Coherence);
553 ccx.tcx.infer_ctxt(None, None, Reveal::ExactMatch).enter(|infcx| {
556 inference_context: infcx,
557 inherent_impls: RefCell::new(FnvHashMap()),
560 unsafety::check(ccx.tcx);
561 orphan::check(ccx.tcx);
562 overlap::check(ccx.tcx);