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::def_id::DefId;
20 use middle::lang_items::UnsizeTraitLangItem;
21 use middle::subst::{self, Subst};
23 use middle::ty::{self, TypeFoldable};
24 use middle::ty::{ImplOrTraitItemId, ConstTraitItemId};
25 use middle::ty::{MethodTraitItemId, TypeTraitItemId, ParameterEnvironment};
26 use middle::ty::{Ty, TyBool, TyChar, TyEnum, TyError};
27 use middle::ty::{TyParam, TyRawPtr};
28 use middle::ty::{TyRef, TyStruct, TyTrait, TyTuple};
29 use middle::ty::{TyStr, TyArray, TySlice, TyFloat, TyInfer, TyInt};
30 use middle::ty::{TyUint, TyClosure, TyBox, TyBareFn};
31 use middle::ty::TyProjection;
32 use middle::ty::util::CopyImplementationError;
33 use middle::free_region::FreeRegionMap;
35 use middle::infer::{self, InferCtxt, TypeOrigin, new_infer_ctxt};
36 use std::cell::RefCell;
38 use syntax::codemap::Span;
39 use syntax::parse::token;
40 use util::nodemap::{DefIdMap, FnvHashMap};
41 use rustc::dep_graph::DepNode;
42 use rustc::front::map as hir_map;
43 use rustc_front::intravisit;
44 use rustc_front::hir::{Item, ItemImpl};
51 // Returns the def ID of the base type, if there is one.
52 fn get_base_type_def_id<'a, 'tcx>(inference_context: &InferCtxt<'a, 'tcx>,
63 Some(t.principal_def_id())
67 inference_context.tcx.lang_items.owned_box()
70 TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
71 TyStr | TyArray(..) | TySlice(..) | TyBareFn(..) | TyTuple(..) |
72 TyParam(..) | TyError |
73 TyRawPtr(_) | TyRef(_, _) | TyProjection(..) => {
77 TyInfer(..) | TyClosure(..) => {
78 // `ty` comes from a user declaration so we should only expect types
79 // that the user can type
80 inference_context.tcx.sess.span_bug(
82 &format!("coherence encountered unexpected type searching for base type: {}",
88 struct CoherenceChecker<'a, 'tcx: 'a> {
89 crate_context: &'a CrateCtxt<'a, 'tcx>,
90 inference_context: InferCtxt<'a, 'tcx>,
91 inherent_impls: RefCell<DefIdMap<Rc<RefCell<Vec<DefId>>>>>,
94 struct CoherenceCheckVisitor<'a, 'tcx: 'a> {
95 cc: &'a CoherenceChecker<'a, 'tcx>
98 impl<'a, 'tcx, 'v> intravisit::Visitor<'v> for CoherenceCheckVisitor<'a, 'tcx> {
99 fn visit_item(&mut self, item: &Item) {
100 if let ItemImpl(..) = item.node {
101 self.cc.check_implementation(item)
106 impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
108 // Check implementations and traits. This populates the tables
109 // containing the inherent methods and extension methods. It also
110 // builds up the trait inheritance table.
111 self.crate_context.tcx.visit_all_items_in_krate(
112 DepNode::CoherenceCheckImpl,
113 &mut CoherenceCheckVisitor { cc: self });
115 // Copy over the inherent impls we gathered up during the walk into
117 let mut tcx_inherent_impls =
118 self.crate_context.tcx.inherent_impls.borrow_mut();
119 for (k, v) in self.inherent_impls.borrow().iter() {
120 tcx_inherent_impls.insert((*k).clone(),
121 Rc::new((*v.borrow()).clone()));
124 // Populate the table of destructors. It might seem a bit strange to
125 // do this here, but it's actually the most convenient place, since
126 // the coherence tables contain the trait -> type mappings.
127 self.populate_destructors();
129 // Check to make sure implementations of `Copy` are legal.
130 self.check_implementations_of_copy();
132 // Check to make sure implementations of `CoerceUnsized` are legal
133 // and collect the necessary information from them.
134 self.check_implementations_of_coerce_unsized();
137 fn check_implementation(&self, item: &Item) {
138 let tcx = self.crate_context.tcx;
139 let impl_did = tcx.map.local_def_id(item.id);
140 let self_type = tcx.lookup_item_type(impl_did);
142 // If there are no traits, then this implementation must have a
145 let impl_items = self.create_impl_from_item(item);
147 if let Some(trait_ref) = self.crate_context.tcx.impl_trait_ref(impl_did) {
148 debug!("(checking implementation) adding impl for trait '{:?}', item '{}'",
152 // Skip impls where one of the self type is an error type.
153 // This occurs with e.g. resolve failures (#30589).
154 if trait_ref.references_error() {
158 enforce_trait_manually_implementable(self.crate_context.tcx,
161 self.add_trait_impl(trait_ref, impl_did);
163 // Skip inherent impls where the self type is an error
164 // type. This occurs with e.g. resolve failures (#30589).
165 if self_type.ty.references_error() {
169 // Add the implementation to the mapping from implementation to base
170 // type def ID, if there is a base type for this implementation and
171 // the implementation does not have any associated traits.
172 if let Some(base_type_def_id) = get_base_type_def_id(
173 &self.inference_context, item.span, self_type.ty) {
174 self.add_inherent_impl(base_type_def_id, impl_did);
178 tcx.impl_items.borrow_mut().insert(impl_did, impl_items);
181 fn add_inherent_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
182 match self.inherent_impls.borrow().get(&base_def_id) {
183 Some(implementation_list) => {
184 implementation_list.borrow_mut().push(impl_def_id);
190 self.inherent_impls.borrow_mut().insert(
192 Rc::new(RefCell::new(vec!(impl_def_id))));
195 fn add_trait_impl(&self, impl_trait_ref: ty::TraitRef<'tcx>, impl_def_id: DefId) {
196 debug!("add_trait_impl: impl_trait_ref={:?} impl_def_id={:?}",
197 impl_trait_ref, impl_def_id);
198 let trait_def = self.crate_context.tcx.lookup_trait_def(impl_trait_ref.def_id);
199 trait_def.record_impl(self.crate_context.tcx, impl_def_id, impl_trait_ref);
202 // Converts an implementation in the AST to a vector of items.
203 fn create_impl_from_item(&self, item: &Item) -> Vec<ImplOrTraitItemId> {
205 ItemImpl(_, _, _, _, _, ref impl_items) => {
206 impl_items.iter().map(|impl_item| {
207 let impl_def_id = self.crate_context.tcx.map.local_def_id(impl_item.id);
208 match impl_item.node {
209 hir::ImplItemKind::Const(..) => {
210 ConstTraitItemId(impl_def_id)
212 hir::ImplItemKind::Method(..) => {
213 MethodTraitItemId(impl_def_id)
215 hir::ImplItemKind::Type(_) => {
216 TypeTraitItemId(impl_def_id)
222 self.crate_context.tcx.sess.span_bug(item.span,
223 "can't convert a non-impl \
233 fn populate_destructors(&self) {
234 let tcx = self.crate_context.tcx;
235 let drop_trait = match tcx.lang_items.drop_trait() {
236 Some(id) => id, None => { return }
238 tcx.populate_implementations_for_trait_if_necessary(drop_trait);
239 let drop_trait = tcx.lookup_trait_def(drop_trait);
241 let impl_items = tcx.impl_items.borrow();
243 drop_trait.for_each_impl(tcx, |impl_did| {
244 let items = impl_items.get(&impl_did).unwrap();
245 if items.is_empty() {
246 // We'll error out later. For now, just don't ICE.
249 let method_def_id = items[0];
251 let self_type = tcx.lookup_item_type(impl_did);
252 match self_type.ty.sty {
253 ty::TyEnum(type_def, _) |
254 ty::TyStruct(type_def, _) => {
255 type_def.set_destructor(method_def_id.def_id());
258 // Destructors only work on nominal types.
259 if let Some(impl_node_id) = tcx.map.as_local_node_id(impl_did) {
260 match tcx.map.find(impl_node_id) {
261 Some(hir_map::NodeItem(item)) => {
262 span_err!(tcx.sess, item.span, E0120,
263 "the Drop trait may only be implemented on structures");
266 tcx.sess.bug("didn't find impl in ast \
271 tcx.sess.bug("found external impl of Drop trait on \
272 something other than a struct");
279 /// Ensures that implementations of the built-in trait `Copy` are legal.
280 fn check_implementations_of_copy(&self) {
281 let tcx = self.crate_context.tcx;
282 let copy_trait = match tcx.lang_items.copy_trait() {
286 tcx.populate_implementations_for_trait_if_necessary(copy_trait);
287 let copy_trait = tcx.lookup_trait_def(copy_trait);
289 copy_trait.for_each_impl(tcx, |impl_did| {
290 debug!("check_implementations_of_copy: impl_did={:?}",
293 let impl_node_id = if let Some(n) = tcx.map.as_local_node_id(impl_did) {
296 debug!("check_implementations_of_copy(): impl not in this \
301 let self_type = tcx.lookup_item_type(impl_did);
302 debug!("check_implementations_of_copy: self_type={:?} (bound)",
305 let span = tcx.map.span(impl_node_id);
306 let param_env = ParameterEnvironment::for_item(tcx, impl_node_id);
307 let self_type = self_type.ty.subst(tcx, ¶m_env.free_substs);
308 assert!(!self_type.has_escaping_regions());
310 debug!("check_implementations_of_copy: self_type={:?} (free)",
313 match param_env.can_type_implement_copy(self_type, span) {
315 Err(CopyImplementationError::InfrigingField(name)) => {
316 span_err!(tcx.sess, span, E0204,
317 "the trait `Copy` may not be \
318 implemented for this type; field \
319 `{}` does not implement `Copy`",
322 Err(CopyImplementationError::InfrigingVariant(name)) => {
323 span_err!(tcx.sess, span, E0205,
324 "the trait `Copy` may not be \
325 implemented for this type; variant \
326 `{}` does not implement `Copy`",
329 Err(CopyImplementationError::NotAnAdt) => {
330 span_err!(tcx.sess, span, E0206,
331 "the trait `Copy` may not be implemented \
332 for this type; type is not a structure or \
335 Err(CopyImplementationError::HasDestructor) => {
336 span_err!(tcx.sess, span, E0184,
337 "the trait `Copy` may not be implemented for this type; \
338 the type has a destructor");
344 /// Process implementations of the built-in trait `CoerceUnsized`.
345 fn check_implementations_of_coerce_unsized(&self) {
346 let tcx = self.crate_context.tcx;
347 let coerce_unsized_trait = match tcx.lang_items.coerce_unsized_trait() {
351 let unsize_trait = match tcx.lang_items.require(UnsizeTraitLangItem) {
354 tcx.sess.fatal(&format!("`CoerceUnsized` implementation {}", err));
358 let trait_def = tcx.lookup_trait_def(coerce_unsized_trait);
360 trait_def.for_each_impl(tcx, |impl_did| {
361 debug!("check_implementations_of_coerce_unsized: impl_did={:?}",
364 let impl_node_id = if let Some(n) = tcx.map.as_local_node_id(impl_did) {
367 debug!("check_implementations_of_coerce_unsized(): impl not \
372 let source = tcx.lookup_item_type(impl_did).ty;
373 let trait_ref = self.crate_context.tcx.impl_trait_ref(impl_did).unwrap();
374 let target = *trait_ref.substs.types.get(subst::TypeSpace, 0);
375 debug!("check_implementations_of_coerce_unsized: {:?} -> {:?} (bound)",
378 let span = tcx.map.span(impl_node_id);
379 let param_env = ParameterEnvironment::for_item(tcx, impl_node_id);
380 let source = source.subst(tcx, ¶m_env.free_substs);
381 let target = target.subst(tcx, ¶m_env.free_substs);
382 assert!(!source.has_escaping_regions());
384 debug!("check_implementations_of_coerce_unsized: {:?} -> {:?} (free)",
387 let infcx = new_infer_ctxt(tcx, &tcx.tables, Some(param_env));
389 let check_mutbl = |mt_a: ty::TypeAndMut<'tcx>, mt_b: ty::TypeAndMut<'tcx>,
390 mk_ptr: &Fn(Ty<'tcx>) -> Ty<'tcx>| {
391 if (mt_a.mutbl, mt_b.mutbl) == (hir::MutImmutable, hir::MutMutable) {
392 infcx.report_mismatched_types(span, mk_ptr(mt_b.ty),
393 target, &ty::error::TypeError::Mutability);
395 (mt_a.ty, mt_b.ty, unsize_trait, None)
397 let (source, target, trait_def_id, kind) = match (&source.sty, &target.sty) {
398 (&ty::TyBox(a), &ty::TyBox(b)) => (a, b, unsize_trait, None),
400 (&ty::TyRef(r_a, mt_a), &ty::TyRef(r_b, mt_b)) => {
401 infer::mk_subr(&infcx, infer::RelateObjectBound(span), *r_b, *r_a);
402 check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ref(r_b, ty))
405 (&ty::TyRef(_, mt_a), &ty::TyRawPtr(mt_b)) |
406 (&ty::TyRawPtr(mt_a), &ty::TyRawPtr(mt_b)) => {
407 check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ptr(ty))
410 (&ty::TyStruct(def_a, substs_a), &ty::TyStruct(def_b, substs_b)) => {
412 let source_path = tcx.item_path_str(def_a.did);
413 let target_path = tcx.item_path_str(def_b.did);
414 span_err!(tcx.sess, span, E0377,
415 "the trait `CoerceUnsized` may only be implemented \
416 for a coercion between structures with the same \
417 definition; expected {}, found {}",
418 source_path, target_path);
422 let origin = TypeOrigin::Misc(span);
423 let fields = &def_a.struct_variant().fields;
424 let diff_fields = fields.iter().enumerate().filter_map(|(i, f)| {
425 let (a, b) = (f.ty(tcx, substs_a), f.ty(tcx, substs_b));
427 if f.unsubst_ty().is_phantom_data() {
428 // Ignore PhantomData fields
430 } else if infcx.sub_types(false, origin, b, a).is_ok() {
431 // Ignore fields that aren't significantly changed
434 // Collect up all fields that were significantly changed
435 // i.e. those that contain T in coerce_unsized T -> U
438 }).collect::<Vec<_>>();
440 if diff_fields.is_empty() {
441 span_err!(tcx.sess, span, E0374,
442 "the trait `CoerceUnsized` may only be implemented \
443 for a coercion between structures with one field \
444 being coerced, none found");
446 } else if diff_fields.len() > 1 {
447 span_err!(tcx.sess, span, E0375,
448 "the trait `CoerceUnsized` may only be implemented \
449 for a coercion between structures with one field \
450 being coerced, but {} fields need coercions: {}",
451 diff_fields.len(), diff_fields.iter().map(|&(i, a, b)| {
452 let name = fields[i].name;
453 format!("{} ({} to {})",
454 if name == token::special_names::unnamed_field {
459 }).collect::<Vec<_>>().join(", "));
463 let (i, a, b) = diff_fields[0];
464 let kind = ty::adjustment::CustomCoerceUnsized::Struct(i);
465 (a, b, coerce_unsized_trait, Some(kind))
469 span_err!(tcx.sess, span, E0376,
470 "the trait `CoerceUnsized` may only be implemented \
471 for a coercion between structures");
476 let mut fulfill_cx = traits::FulfillmentContext::new();
478 // Register an obligation for `A: Trait<B>`.
479 let cause = traits::ObligationCause::misc(span, impl_node_id);
480 let predicate = traits::predicate_for_trait_def(tcx, cause, trait_def_id,
481 0, source, vec![target]);
482 fulfill_cx.register_predicate_obligation(&infcx, predicate);
484 // Check that all transitive obligations are satisfied.
485 if let Err(errors) = fulfill_cx.select_all_or_error(&infcx) {
486 traits::report_fulfillment_errors(&infcx, &errors);
489 // Finally, resolve all regions.
490 let mut free_regions = FreeRegionMap::new();
491 free_regions.relate_free_regions_from_predicates(tcx, &infcx.parameter_environment
493 infcx.resolve_regions_and_report_errors(&free_regions, impl_node_id);
495 if let Some(kind) = kind {
496 tcx.custom_coerce_unsized_kinds.borrow_mut().insert(impl_did, kind);
502 fn enforce_trait_manually_implementable(tcx: &ty::ctxt, sp: Span, trait_def_id: DefId) {
503 if tcx.sess.features.borrow().unboxed_closures {
504 // the feature gate allows all of them
507 let did = Some(trait_def_id);
508 let li = &tcx.lang_items;
510 let trait_name = if did == li.fn_trait() {
512 } else if did == li.fn_mut_trait() {
514 } else if did == li.fn_once_trait() {
517 return // everything OK
519 let mut err = struct_span_err!(tcx.sess,
522 "manual implementations of `{}` are experimental",
524 fileline_help!(&mut err, sp,
525 "add `#![feature(unboxed_closures)]` to the crate attributes to enable");
529 pub fn check_coherence(crate_context: &CrateCtxt) {
530 let _task = crate_context.tcx.dep_graph.in_task(DepNode::Coherence);
531 let infcx = new_infer_ctxt(crate_context.tcx, &crate_context.tcx.tables, None);
533 crate_context: crate_context,
534 inference_context: infcx,
535 inherent_impls: RefCell::new(FnvHashMap()),
537 unsafety::check(crate_context.tcx);
538 orphan::check(crate_context.tcx);
539 overlap::check(crate_context.tcx);