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}
;
24 use middle
::ty
::RegionEscape
;
25 use middle
::ty
::{ImplOrTraitItemId, ConstTraitItemId}
;
26 use middle
::ty
::{MethodTraitItemId, TypeTraitItemId, ParameterEnvironment}
;
27 use middle
::ty
::{Ty, TyBool, TyChar, TyEnum, TyError}
;
28 use middle
::ty
::{TyParam, TyRawPtr}
;
29 use middle
::ty
::{TyRef, TyStruct, TyTrait, TyTuple}
;
30 use middle
::ty
::{TyStr, TyArray, TySlice, TyFloat, TyInfer, TyInt}
;
31 use middle
::ty
::{TyUint, TyClosure, TyBox, TyBareFn}
;
32 use middle
::ty
::TyProjection
;
33 use middle
::ty
::util
::CopyImplementationError
;
34 use middle
::free_region
::FreeRegionMap
;
36 use middle
::infer
::{self, InferCtxt, new_infer_ctxt}
;
37 use std
::cell
::RefCell
;
39 use syntax
::codemap
::Span
;
40 use syntax
::parse
::token
;
41 use util
::nodemap
::{DefIdMap, FnvHashMap}
;
42 use rustc
::front
::map
as hir_map
;
43 use rustc
::front
::map
::NodeItem
;
44 use rustc_front
::visit
;
45 use rustc_front
::hir
::{Item, ItemImpl,Crate}
;
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
>,
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
<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_destructors();
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
= tcx
.map
.local_def_id(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 fn add_inherent_impl(&self, base_def_id
: DefId
, impl_def_id
: DefId
) {
172 match self.inherent_impls
.borrow().get(&base_def_id
) {
173 Some(implementation_list
) => {
174 implementation_list
.borrow_mut().push(impl_def_id
);
180 self.inherent_impls
.borrow_mut().insert(
182 Rc
::new(RefCell
::new(vec
!(impl_def_id
))));
185 fn add_trait_impl(&self, impl_trait_ref
: ty
::TraitRef
<'tcx
>, impl_def_id
: DefId
) {
186 debug
!("add_trait_impl: impl_trait_ref={:?} impl_def_id={:?}",
187 impl_trait_ref
, impl_def_id
);
188 let trait_def
= self.crate_context
.tcx
.lookup_trait_def(impl_trait_ref
.def_id
);
189 trait_def
.record_impl(self.crate_context
.tcx
, impl_def_id
, impl_trait_ref
);
192 // Converts an implementation in the AST to a vector of items.
193 fn create_impl_from_item(&self, item
: &Item
) -> Vec
<ImplOrTraitItemId
> {
195 ItemImpl(_
, _
, _
, _
, _
, ref impl_items
) => {
196 impl_items
.iter().map(|impl_item
| {
197 let impl_def_id
= self.crate_context
.tcx
.map
.local_def_id(impl_item
.id
);
198 match impl_item
.node
{
199 hir
::ConstImplItem(..) => {
200 ConstTraitItemId(impl_def_id
)
202 hir
::MethodImplItem(..) => {
203 MethodTraitItemId(impl_def_id
)
205 hir
::TypeImplItem(_
) => {
206 TypeTraitItemId(impl_def_id
)
212 self.crate_context
.tcx
.sess
.span_bug(item
.span
,
213 "can't convert a non-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 span_err
!(tcx
.sess
, item
.span
, E0120
,
253 "the Drop trait may only be implemented on structures");
256 tcx
.sess
.bug("didn't find impl in ast \
261 tcx
.sess
.bug("found external impl of Drop trait on \
262 something other than a struct");
269 /// Ensures that implementations of the built-in trait `Copy` are legal.
270 fn check_implementations_of_copy(&self) {
271 let tcx
= self.crate_context
.tcx
;
272 let copy_trait
= match tcx
.lang_items
.copy_trait() {
276 tcx
.populate_implementations_for_trait_if_necessary(copy_trait
);
277 let copy_trait
= tcx
.lookup_trait_def(copy_trait
);
279 copy_trait
.for_each_impl(tcx
, |impl_did
| {
280 debug
!("check_implementations_of_copy: impl_did={:?}",
283 let impl_node_id
= if let Some(n
) = tcx
.map
.as_local_node_id(impl_did
) {
286 debug
!("check_implementations_of_copy(): impl not in this \
291 let self_type
= tcx
.lookup_item_type(impl_did
);
292 debug
!("check_implementations_of_copy: self_type={:?} (bound)",
295 let span
= tcx
.map
.span(impl_node_id
);
296 let param_env
= ParameterEnvironment
::for_item(tcx
, impl_node_id
);
297 let self_type
= self_type
.ty
.subst(tcx
, ¶m_env
.free_substs
);
298 assert
!(!self_type
.has_escaping_regions());
300 debug
!("check_implementations_of_copy: self_type={:?} (free)",
303 match param_env
.can_type_implement_copy(self_type
, span
) {
305 Err(CopyImplementationError
::InfrigingField(name
)) => {
306 span_err
!(tcx
.sess
, span
, E0204
,
307 "the trait `Copy` may not be \
308 implemented for this type; field \
309 `{}` does not implement `Copy`",
312 Err(CopyImplementationError
::InfrigingVariant(name
)) => {
313 span_err
!(tcx
.sess
, span
, E0205
,
314 "the trait `Copy` may not be \
315 implemented for this type; variant \
316 `{}` does not implement `Copy`",
319 Err(CopyImplementationError
::NotAnAdt
) => {
320 span_err
!(tcx
.sess
, span
, E0206
,
321 "the trait `Copy` may not be implemented \
322 for this type; type is not a structure or \
325 Err(CopyImplementationError
::HasDestructor
) => {
326 span_err
!(tcx
.sess
, span
, E0184
,
327 "the trait `Copy` may not be implemented for this type; \
328 the type has a destructor");
334 /// Process implementations of the built-in trait `CoerceUnsized`.
335 fn check_implementations_of_coerce_unsized(&self) {
336 let tcx
= self.crate_context
.tcx
;
337 let coerce_unsized_trait
= match tcx
.lang_items
.coerce_unsized_trait() {
341 let unsize_trait
= match tcx
.lang_items
.require(UnsizeTraitLangItem
) {
344 tcx
.sess
.fatal(&format
!("`CoerceUnsized` implementation {}", err
));
348 let trait_def
= tcx
.lookup_trait_def(coerce_unsized_trait
);
350 trait_def
.for_each_impl(tcx
, |impl_did
| {
351 debug
!("check_implementations_of_coerce_unsized: impl_did={:?}",
354 let impl_node_id
= if let Some(n
) = tcx
.map
.as_local_node_id(impl_did
) {
357 debug
!("check_implementations_of_coerce_unsized(): impl not \
362 let source
= tcx
.lookup_item_type(impl_did
).ty
;
363 let trait_ref
= self.crate_context
.tcx
.impl_trait_ref(impl_did
).unwrap();
364 let target
= *trait_ref
.substs
.types
.get(subst
::TypeSpace
, 0);
365 debug
!("check_implementations_of_coerce_unsized: {:?} -> {:?} (bound)",
368 let span
= tcx
.map
.span(impl_node_id
);
369 let param_env
= ParameterEnvironment
::for_item(tcx
, impl_node_id
);
370 let source
= source
.subst(tcx
, ¶m_env
.free_substs
);
371 let target
= target
.subst(tcx
, ¶m_env
.free_substs
);
372 assert
!(!source
.has_escaping_regions());
374 debug
!("check_implementations_of_coerce_unsized: {:?} -> {:?} (free)",
377 let infcx
= new_infer_ctxt(tcx
, &tcx
.tables
, Some(param_env
), true);
379 let check_mutbl
= |mt_a
: ty
::TypeAndMut
<'tcx
>, mt_b
: ty
::TypeAndMut
<'tcx
>,
380 mk_ptr
: &Fn(Ty
<'tcx
>) -> Ty
<'tcx
>| {
381 if (mt_a
.mutbl
, mt_b
.mutbl
) == (hir
::MutImmutable
, hir
::MutMutable
) {
382 infcx
.report_mismatched_types(span
, mk_ptr(mt_b
.ty
),
383 target
, &ty
::error
::TypeError
::Mutability
);
385 (mt_a
.ty
, mt_b
.ty
, unsize_trait
, None
)
387 let (source
, target
, trait_def_id
, kind
) = match (&source
.sty
, &target
.sty
) {
388 (&ty
::TyBox(a
), &ty
::TyBox(b
)) => (a
, b
, unsize_trait
, None
),
390 (&ty
::TyRef(r_a
, mt_a
), &ty
::TyRef(r_b
, mt_b
)) => {
391 infer
::mk_subr(&infcx
, infer
::RelateObjectBound(span
), *r_b
, *r_a
);
392 check_mutbl(mt_a
, mt_b
, &|ty
| tcx
.mk_imm_ref(r_b
, ty
))
395 (&ty
::TyRef(_
, mt_a
), &ty
::TyRawPtr(mt_b
)) |
396 (&ty
::TyRawPtr(mt_a
), &ty
::TyRawPtr(mt_b
)) => {
397 check_mutbl(mt_a
, mt_b
, &|ty
| tcx
.mk_imm_ptr(ty
))
400 (&ty
::TyStruct(def_a
, substs_a
), &ty
::TyStruct(def_b
, substs_b
)) => {
402 let source_path
= tcx
.item_path_str(def_a
.did
);
403 let target_path
= tcx
.item_path_str(def_b
.did
);
404 span_err
!(tcx
.sess
, span
, E0377
,
405 "the trait `CoerceUnsized` may only be implemented \
406 for a coercion between structures with the same \
407 definition; expected {}, found {}",
408 source_path
, target_path
);
412 let origin
= infer
::Misc(span
);
413 let fields
= &def_a
.struct_variant().fields
;
414 let diff_fields
= fields
.iter().enumerate().filter_map(|(i
, f
)| {
415 let (a
, b
) = (f
.ty(tcx
, substs_a
), f
.ty(tcx
, substs_b
));
417 if f
.unsubst_ty().is_phantom_data() {
418 // Ignore PhantomData fields
420 } else if infcx
.sub_types(false, origin
, b
, a
).is_ok() {
421 // Ignore fields that aren't significantly changed
424 // Collect up all fields that were significantly changed
425 // i.e. those that contain T in coerce_unsized T -> U
428 }).collect
::<Vec
<_
>>();
430 if diff_fields
.is_empty() {
431 span_err
!(tcx
.sess
, span
, E0374
,
432 "the trait `CoerceUnsized` may only be implemented \
433 for a coercion between structures with one field \
434 being coerced, none found");
436 } else if diff_fields
.len() > 1 {
437 span_err
!(tcx
.sess
, span
, E0375
,
438 "the trait `CoerceUnsized` may only be implemented \
439 for a coercion between structures with one field \
440 being coerced, but {} fields need coercions: {}",
441 diff_fields
.len(), diff_fields
.iter().map(|&(i
, a
, b
)| {
442 let name
= fields
[i
].name
;
443 format
!("{} ({} to {})",
444 if name
== token
::special_names
::unnamed_field
{
449 }).collect
::<Vec
<_
>>().join(", "));
453 let (i
, a
, b
) = diff_fields
[0];
454 let kind
= ty
::adjustment
::CustomCoerceUnsized
::Struct(i
);
455 (a
, b
, coerce_unsized_trait
, Some(kind
))
459 span_err
!(tcx
.sess
, span
, E0376
,
460 "the trait `CoerceUnsized` may only be implemented \
461 for a coercion between structures");
466 let mut fulfill_cx
= infcx
.fulfillment_cx
.borrow_mut();
468 // Register an obligation for `A: Trait<B>`.
469 let cause
= traits
::ObligationCause
::misc(span
, impl_node_id
);
470 let predicate
= traits
::predicate_for_trait_def(tcx
, cause
, trait_def_id
,
471 0, source
, vec
![target
]);
472 fulfill_cx
.register_predicate_obligation(&infcx
, predicate
);
474 // Check that all transitive obligations are satisfied.
475 if let Err(errors
) = fulfill_cx
.select_all_or_error(&infcx
) {
476 traits
::report_fulfillment_errors(&infcx
, &errors
);
479 // Finally, resolve all regions.
480 let mut free_regions
= FreeRegionMap
::new();
481 free_regions
.relate_free_regions_from_predicates(tcx
, &infcx
.parameter_environment
483 infcx
.resolve_regions_and_report_errors(&free_regions
, impl_node_id
);
485 if let Some(kind
) = kind
{
486 tcx
.custom_coerce_unsized_kinds
.borrow_mut().insert(impl_did
, kind
);
492 fn enforce_trait_manually_implementable(tcx
: &ty
::ctxt
, sp
: Span
, trait_def_id
: DefId
) {
493 if tcx
.sess
.features
.borrow().unboxed_closures
{
494 // the feature gate allows all of them
497 let did
= Some(trait_def_id
);
498 let li
= &tcx
.lang_items
;
500 let trait_name
= if did
== li
.fn_trait() {
502 } else if did
== li
.fn_mut_trait() {
504 } else if did
== li
.fn_once_trait() {
507 return // everything OK
509 span_err
!(tcx
.sess
, sp
, E0183
, "manual implementations of `{}` are experimental", trait_name
);
510 fileline_help
!(tcx
.sess
, sp
,
511 "add `#![feature(unboxed_closures)]` to the crate attributes to enable");
514 pub fn check_coherence(crate_context
: &CrateCtxt
) {
516 crate_context
: crate_context
,
517 inference_context
: new_infer_ctxt(crate_context
.tcx
, &crate_context
.tcx
.tables
, None
, true),
518 inherent_impls
: RefCell
::new(FnvHashMap()),
519 }.check(crate_context
.tcx
.map
.krate());
520 unsafety
::check(crate_context
.tcx
);
521 orphan
::check(crate_context
.tcx
);
522 overlap
::check(crate_context
.tcx
);