1 // Copyright 2012-2013 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 each trait
14 // has at most one implementation for each type. Then we build a mapping from
15 // each trait in the system to its implementations.
18 use metadata::csearch::{each_impl, get_impl_trait, each_implementation_for_trait};
19 use metadata::csearch;
21 use middle::subst::{Substs};
23 use middle::ty::{ImplContainer, ImplOrTraitItemId, MethodTraitItemId};
24 use middle::ty::{lookup_item_type};
25 use middle::ty::{t, ty_bool, ty_char, ty_bot, ty_box, ty_enum, ty_err};
26 use middle::ty::{ty_str, ty_vec, ty_float, ty_infer, ty_int, ty_nil, ty_open};
27 use middle::ty::{ty_param, Polytype, ty_ptr};
28 use middle::ty::{ty_rptr, ty_struct, ty_trait, ty_tup};
29 use middle::ty::{ty_uint, ty_unboxed_closure, ty_uniq, ty_bare_fn};
30 use middle::ty::{ty_closure};
31 use middle::ty::type_is_ty_var;
32 use middle::subst::Subst;
34 use middle::typeck::CrateCtxt;
35 use middle::typeck::infer::combine::Combine;
36 use middle::typeck::infer::InferCtxt;
37 use middle::typeck::infer::{new_infer_ctxt, resolve_ivar, resolve_type};
38 use middle::typeck::infer;
39 use util::ppaux::Repr;
40 use middle::def::{DefStruct, DefTy};
41 use syntax::ast::{Crate, DefId};
42 use syntax::ast::{Item, ItemEnum, ItemImpl, ItemMod, ItemStruct};
43 use syntax::ast::{LOCAL_CRATE, TraitRef, TyPath};
45 use syntax::ast_map::NodeItem;
47 use syntax::ast_util::{local_def};
48 use syntax::codemap::{Span, DUMMY_SP};
49 use syntax::parse::token;
52 use std::collections::HashSet;
53 use std::cell::RefCell;
56 struct UniversalQuantificationResult {
60 fn get_base_type(inference_context: &InferCtxt,
64 let resolved_type = match resolve_type(inference_context,
68 Ok(resulting_type) if !type_is_ty_var(resulting_type) => resulting_type,
70 inference_context.tcx.sess.span_fatal(span,
71 "the type of this value must be known in order \
72 to determine the base type");
76 match get(resolved_type).sty {
77 ty_enum(..) | ty_struct(..) | ty_unboxed_closure(..) => {
78 debug!("(getting base type) found base type");
82 _ if ty::type_is_trait(resolved_type) => {
83 debug!("(getting base type) found base type (trait)");
87 ty_nil | ty_bot | ty_bool | ty_char | ty_int(..) | ty_uint(..) | ty_float(..) |
88 ty_str(..) | ty_vec(..) | ty_bare_fn(..) | ty_closure(..) | ty_tup(..) |
89 ty_infer(..) | ty_param(..) | ty_err | ty_open(..) |
90 ty_box(_) | ty_uniq(_) | ty_ptr(_) | ty_rptr(_, _) => {
91 debug!("(getting base type) no base type; found {:?}",
92 get(original_type).sty);
95 ty_trait(..) => fail!("should have been caught")
99 fn type_is_defined_in_local_crate(tcx: &ty::ctxt, original_type: t) -> bool {
102 * For coherence, when we have `impl Trait for Type`, we need to
103 * guarantee that `Type` is "local" to the
104 * crate. For our purposes, this means that it must contain
105 * some nominal type defined in this crate.
108 let mut found_nominal = false;
109 ty::walk_ty(original_type, |t| {
112 ty_struct(def_id, _) |
113 ty_unboxed_closure(def_id, _) => {
114 if def_id.krate == ast::LOCAL_CRATE {
115 found_nominal = true;
118 ty_trait(box ty::TyTrait { def_id, .. }) => {
119 if def_id.krate == ast::LOCAL_CRATE {
120 found_nominal = true;
124 match tcx.lang_items.owned_box() {
125 Some(did) if did.krate == ast::LOCAL_CRATE => {
126 found_nominal = true;
132 match tcx.lang_items.gc() {
133 Some(did) if did.krate == ast::LOCAL_CRATE => {
134 found_nominal = true;
143 return found_nominal;
146 // Returns the def ID of the base type, if there is one.
147 fn get_base_type_def_id(inference_context: &InferCtxt,
151 match get_base_type(inference_context, span, original_type) {
154 match get(base_type).sty {
156 ty_struct(def_id, _) |
157 ty_unboxed_closure(def_id, _) => {
160 ty_ptr(ty::mt {ty, ..}) |
161 ty_rptr(_, ty::mt {ty, ..}) |
163 match ty::get(ty).sty {
164 ty_trait(box ty::TyTrait { def_id, .. }) => {
168 fail!("get_base_type() returned a type that wasn't an \
169 enum, struct, or trait");
173 ty_trait(box ty::TyTrait { def_id, .. }) => {
177 fail!("get_base_type() returned a type that wasn't an \
178 enum, struct, or trait");
185 struct CoherenceChecker<'a, 'tcx: 'a> {
186 crate_context: &'a CrateCtxt<'a, 'tcx>,
187 inference_context: InferCtxt<'a, 'tcx>,
190 struct CoherenceCheckVisitor<'a, 'tcx: 'a> {
191 cc: &'a CoherenceChecker<'a, 'tcx>
194 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CoherenceCheckVisitor<'a, 'tcx> {
195 fn visit_item(&mut self, item: &Item) {
197 //debug!("(checking coherence) item '{}'", token::get_ident(item.ident));
200 ItemImpl(_, ref opt_trait, _, _) => {
201 match opt_trait.clone() {
203 self.cc.check_implementation(item, [opt_trait]);
205 None => self.cc.check_implementation(item, [])
213 visit::walk_item(self, item);
217 struct PrivilegedScopeVisitor<'a, 'tcx: 'a> {
218 cc: &'a CoherenceChecker<'a, 'tcx>
221 impl<'a, 'tcx, 'v> visit::Visitor<'v> for PrivilegedScopeVisitor<'a, 'tcx> {
222 fn visit_item(&mut self, item: &Item) {
225 ItemMod(ref module_) => {
226 // Then visit the module items.
227 visit::walk_mod(self, module_);
229 ItemImpl(_, None, ref ast_ty, _) => {
230 if !self.cc.ast_type_is_defined_in_local_crate(&**ast_ty) {
232 let session = &self.cc.crate_context.tcx.sess;
233 span_err!(session, item.span, E0116,
234 "cannot associate methods with a type outside the \
235 crate the type is defined in; define and implement \
236 a trait or new type instead");
239 ItemImpl(_, Some(ref trait_ref), _, _) => {
240 let tcx = self.cc.crate_context.tcx;
241 // `for_ty` is `Type` in `impl Trait for Type`
242 let for_ty = ty::node_id_to_type(tcx, item.id);
243 if !type_is_defined_in_local_crate(tcx, for_ty) {
244 // This implementation is not in scope of its base
245 // type. This still might be OK if the trait is
246 // defined in the same crate.
249 self.cc.trait_ref_to_trait_def_id(trait_ref);
251 if trait_def_id.krate != LOCAL_CRATE {
252 let session = &self.cc.crate_context.tcx.sess;
253 span_err!(session, item.span, E0117,
254 "cannot provide an extension implementation \
255 where both trait and type are not defined in this crate");
259 visit::walk_item(self, item);
262 visit::walk_item(self, item);
268 impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
269 fn check(&self, krate: &Crate) {
270 // Check implementations and traits. This populates the tables
271 // containing the inherent methods and extension methods. It also
272 // builds up the trait inheritance table.
273 let mut visitor = CoherenceCheckVisitor { cc: self };
274 visit::walk_crate(&mut visitor, krate);
276 // Check that there are no overlapping trait instances
277 self.check_implementation_coherence();
279 // Check whether traits with base types are in privileged scopes.
280 self.check_privileged_scopes(krate);
282 // Bring in external crates. It's fine for this to happen after the
283 // coherence checks, because we ensure by construction that no errors
284 // can happen at link time.
285 self.add_external_crates();
287 // Populate the table of destructors. It might seem a bit strange to
288 // do this here, but it's actually the most convenient place, since
289 // the coherence tables contain the trait -> type mappings.
290 self.populate_destructor_table();
293 fn check_implementation(&self, item: &Item,
294 associated_traits: &[TraitRef]) {
295 let tcx = self.crate_context.tcx;
296 let impl_did = local_def(item.id);
297 let self_type = ty::lookup_item_type(tcx, impl_did);
299 // If there are no traits, then this implementation must have a
302 if associated_traits.len() == 0 {
303 debug!("(checking implementation) no associated traits for item '{}'",
304 token::get_ident(item.ident));
306 match get_base_type_def_id(&self.inference_context,
310 let session = &self.crate_context.tcx.sess;
311 span_err!(session, item.span, E0118,
312 "no base type found for inherent implementation; \
313 implement a trait or new type instead");
321 let impl_items = self.create_impl_from_item(item);
323 for associated_trait in associated_traits.iter() {
324 let trait_ref = ty::node_id_to_trait_ref(
325 self.crate_context.tcx, associated_trait.ref_id);
326 debug!("(checking implementation) adding impl for trait '{}', item '{}'",
327 trait_ref.repr(self.crate_context.tcx),
328 token::get_ident(item.ident));
330 self.add_trait_impl(trait_ref.def_id, impl_did);
333 // Add the implementation to the mapping from implementation to base
334 // type def ID, if there is a base type for this implementation and
335 // the implementation does not have any associated traits.
336 match get_base_type_def_id(&self.inference_context,
342 Some(base_type_def_id) => {
343 // FIXME: Gather up default methods?
344 if associated_traits.len() == 0 {
345 self.add_inherent_impl(base_type_def_id, impl_did);
350 tcx.impl_items.borrow_mut().insert(impl_did, impl_items);
353 // Creates default method IDs and performs type substitutions for an impl
354 // and trait pair. Then, for each provided method in the trait, inserts a
355 // `ProvidedMethodInfo` instance into the `provided_method_sources` map.
356 fn instantiate_default_methods(
359 trait_ref: &ty::TraitRef,
360 all_impl_items: &mut Vec<ImplOrTraitItemId>) {
361 let tcx = self.crate_context.tcx;
362 debug!("instantiate_default_methods(impl_id={:?}, trait_ref={})",
363 impl_id, trait_ref.repr(tcx));
365 let impl_poly_type = ty::lookup_item_type(tcx, impl_id);
367 let prov = ty::provided_trait_methods(tcx, trait_ref.def_id);
368 for trait_method in prov.iter() {
370 let new_id = tcx.sess.next_node_id();
371 let new_did = local_def(new_id);
373 debug!("new_did={:?} trait_method={}", new_did, trait_method.repr(tcx));
375 // Create substitutions for the various trait parameters.
377 Rc::new(subst_receiver_types_in_method_ty(
384 Some(trait_method.def_id)));
386 debug!("new_method_ty={}", new_method_ty.repr(tcx));
387 all_impl_items.push(MethodTraitItemId(new_did));
389 // construct the polytype for the method based on the
390 // method_ty. it will have all the generics from the
391 // impl, plus its own.
392 let new_polytype = ty::Polytype {
393 generics: new_method_ty.generics.clone(),
394 ty: ty::mk_bare_fn(tcx, new_method_ty.fty.clone())
396 debug!("new_polytype={}", new_polytype.repr(tcx));
398 tcx.tcache.borrow_mut().insert(new_did, new_polytype);
399 tcx.impl_or_trait_items
401 .insert(new_did, ty::MethodTraitItem(new_method_ty));
403 // Pair the new synthesized ID up with the
405 self.crate_context.tcx.provided_method_sources.borrow_mut()
406 .insert(new_did, trait_method.def_id);
410 fn add_inherent_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
411 let tcx = self.crate_context.tcx;
412 match tcx.inherent_impls.borrow().find(&base_def_id) {
413 Some(implementation_list) => {
414 implementation_list.borrow_mut().push(impl_def_id);
420 tcx.inherent_impls.borrow_mut().insert(base_def_id,
421 Rc::new(RefCell::new(vec!(impl_def_id))));
424 fn add_trait_impl(&self, base_def_id: DefId, impl_def_id: DefId) {
425 ty::record_trait_implementation(self.crate_context.tcx,
430 fn check_implementation_coherence(&self) {
431 for trait_id in self.crate_context.tcx.trait_impls.borrow().keys() {
432 self.check_implementation_coherence_of(*trait_id);
436 fn check_implementation_coherence_of(&self, trait_def_id: DefId) {
437 // Unify pairs of polytypes.
438 self.iter_impls_of_trait_local(trait_def_id, |impl_a| {
440 self.get_self_type_for_implementation(impl_a);
442 // "We have an impl of trait <trait_def_id> for type <polytype_a>,
443 // and that impl is <impl_a>"
444 self.iter_impls_of_trait(trait_def_id, |impl_b| {
446 // An impl is coherent with itself
447 if impl_a != impl_b {
448 let polytype_b = self.get_self_type_for_implementation(
451 if self.polytypes_unify(polytype_a.clone(), polytype_b) {
452 let session = &self.crate_context.tcx.sess;
453 span_err!(session, self.span_of_impl(impl_a), E0119,
454 "conflicting implementations for trait `{}`",
455 ty::item_path_str(self.crate_context.tcx, trait_def_id));
456 if impl_b.krate == LOCAL_CRATE {
457 span_note!(session, self.span_of_impl(impl_b),
458 "note conflicting implementation here");
460 let crate_store = &self.crate_context.tcx.sess.cstore;
461 let cdata = crate_store.get_crate_data(impl_b.krate);
462 span_note!(session, self.span_of_impl(impl_a),
463 "conflicting implementation in crate `{}`",
472 fn iter_impls_of_trait(&self, trait_def_id: DefId, f: |DefId|) {
473 self.iter_impls_of_trait_local(trait_def_id, |x| f(x));
475 if trait_def_id.krate == LOCAL_CRATE {
479 let crate_store = &self.crate_context.tcx.sess.cstore;
480 csearch::each_implementation_for_trait(crate_store, trait_def_id, |impl_def_id| {
481 // Is this actually necessary?
482 let _ = lookup_item_type(self.crate_context.tcx, impl_def_id);
487 fn iter_impls_of_trait_local(&self, trait_def_id: DefId, f: |DefId|) {
488 match self.crate_context.tcx.trait_impls.borrow().find(&trait_def_id) {
490 for &impl_did in impls.borrow().iter() {
494 None => { /* no impls? */ }
498 fn polytypes_unify(&self,
499 polytype_a: Polytype,
500 polytype_b: Polytype)
502 let universally_quantified_a =
503 self.universally_quantify_polytype(polytype_a);
504 let universally_quantified_b =
505 self.universally_quantify_polytype(polytype_b);
507 return self.can_unify_universally_quantified(
508 &universally_quantified_a, &universally_quantified_b) ||
509 self.can_unify_universally_quantified(
510 &universally_quantified_b, &universally_quantified_a);
513 // Converts a polytype to a monotype by replacing all parameters with
514 // type variables. Returns the monotype and the type variables created.
515 fn universally_quantify_polytype(&self, polytype: Polytype)
516 -> UniversalQuantificationResult
519 self.inference_context.fresh_substs_for_type(DUMMY_SP,
521 let monotype = polytype.ty.subst(self.crate_context.tcx, &substitutions);
523 UniversalQuantificationResult {
528 fn can_unify_universally_quantified<'a>(&self,
529 a: &'a UniversalQuantificationResult,
530 b: &'a UniversalQuantificationResult)
533 infer::can_mk_subty(&self.inference_context,
538 fn get_self_type_for_implementation(&self, impl_did: DefId)
540 self.crate_context.tcx.tcache.borrow().get_copy(&impl_did)
543 // Privileged scope checking
544 fn check_privileged_scopes(&self, krate: &Crate) {
545 let mut visitor = PrivilegedScopeVisitor{ cc: self };
546 visit::walk_crate(&mut visitor, krate);
549 fn trait_ref_to_trait_def_id(&self, trait_ref: &TraitRef) -> DefId {
550 let def_map = &self.crate_context.tcx.def_map;
551 let trait_def = def_map.borrow().get_copy(&trait_ref.ref_id);
552 let trait_id = trait_def.def_id();
556 /// For coherence, when we have `impl Type`, we need to guarantee that
557 /// `Type` is "local" to the crate. For our purposes, this means that it
558 /// must precisely name some nominal type defined in this crate.
559 fn ast_type_is_defined_in_local_crate(&self, original_type: &ast::Ty) -> bool {
560 match original_type.node {
561 TyPath(_, _, path_id) => {
562 match self.crate_context.tcx.def_map.borrow().get_copy(&path_id) {
563 DefTy(def_id) | DefStruct(def_id) => {
564 if def_id.krate != LOCAL_CRATE {
568 // Make sure that this type precisely names a nominal
570 match self.crate_context.tcx.map.find(def_id.node) {
572 self.crate_context.tcx.sess.span_bug(
574 "resolve didn't resolve this type?!");
576 Some(NodeItem(item)) => {
578 ItemStruct(..) | ItemEnum(..) => true,
592 // Converts an implementation in the AST to a vector of items.
593 fn create_impl_from_item(&self, item: &Item) -> Vec<ImplOrTraitItemId> {
595 ItemImpl(_, ref trait_refs, _, ref ast_items) => {
596 let mut items: Vec<ImplOrTraitItemId> =
600 ast::MethodImplItem(ast_method) => {
602 local_def(ast_method.id))
607 for trait_ref in trait_refs.iter() {
608 let ty_trait_ref = ty::node_id_to_trait_ref(
609 self.crate_context.tcx,
612 self.instantiate_default_methods(local_def(item.id),
620 self.crate_context.tcx.sess.span_bug(item.span,
621 "can't convert a non-impl to an impl");
626 fn span_of_impl(&self, impl_did: DefId) -> Span {
627 assert_eq!(impl_did.krate, LOCAL_CRATE);
628 self.crate_context.tcx.map.span(impl_did.node)
631 // External crate handling
633 fn add_external_impl(&self,
634 impls_seen: &mut HashSet<DefId>,
635 impl_def_id: DefId) {
636 let tcx = self.crate_context.tcx;
637 let impl_items = csearch::get_impl_items(&tcx.sess.cstore,
640 // Make sure we don't visit the same implementation multiple times.
641 if !impls_seen.insert(impl_def_id) {
647 let _ = lookup_item_type(tcx, impl_def_id);
648 let associated_traits = get_impl_trait(tcx, impl_def_id);
650 // Do a sanity check.
651 assert!(associated_traits.is_some());
653 // Record all the trait items.
654 for trait_ref in associated_traits.iter() {
655 self.add_trait_impl(trait_ref.def_id, impl_def_id);
658 // For any methods that use a default implementation, add them to
659 // the map. This is a bit unfortunate.
660 for item_def_id in impl_items.iter() {
661 let impl_item = ty::impl_or_trait_item(tcx, item_def_id.def_id());
663 ty::MethodTraitItem(ref method) => {
664 for &source in method.provided_source.iter() {
665 tcx.provided_method_sources
667 .insert(item_def_id.def_id(), source);
673 tcx.impl_items.borrow_mut().insert(impl_def_id, impl_items);
676 // Adds implementations and traits from external crates to the coherence
678 fn add_external_crates(&self) {
679 let mut impls_seen = HashSet::new();
681 let crate_store = &self.crate_context.tcx.sess.cstore;
682 crate_store.iter_crate_data(|crate_number, _crate_metadata| {
683 each_impl(crate_store, crate_number, |def_id| {
684 assert_eq!(crate_number, def_id.krate);
685 self.add_external_impl(&mut impls_seen, def_id)
694 fn populate_destructor_table(&self) {
695 let tcx = self.crate_context.tcx;
696 let drop_trait = match tcx.lang_items.drop_trait() {
697 Some(id) => id, None => { return }
700 let impl_items = tcx.impl_items.borrow();
701 let trait_impls = match tcx.trait_impls.borrow().find_copy(&drop_trait) {
702 None => return, // No types with (new-style) dtors present.
703 Some(found_impls) => found_impls
706 for &impl_did in trait_impls.borrow().iter() {
707 let items = impl_items.get(&impl_did);
709 // We'll error out later. For now, just don't ICE.
712 let method_def_id = *items.get(0);
714 let self_type = self.get_self_type_for_implementation(impl_did);
715 match ty::get(self_type.ty).sty {
716 ty::ty_enum(type_def_id, _) |
717 ty::ty_struct(type_def_id, _) |
718 ty::ty_unboxed_closure(type_def_id, _) => {
719 tcx.destructor_for_type
721 .insert(type_def_id, method_def_id.def_id());
724 .insert(method_def_id.def_id());
727 // Destructors only work on nominal types.
728 if impl_did.krate == ast::LOCAL_CRATE {
730 match tcx.map.find(impl_did.node) {
731 Some(ast_map::NodeItem(item)) => {
732 span_err!(tcx.sess, item.span, E0120,
733 "the Drop trait may only be implemented on structures");
736 tcx.sess.bug("didn't find impl in ast \
742 tcx.sess.bug("found external impl of Drop trait on \
743 something other than a struct");
751 pub fn make_substs_for_receiver_types(tcx: &ty::ctxt,
752 trait_ref: &ty::TraitRef,
757 * Substitutes the values for the receiver's type parameters
758 * that are found in method, leaving the method's type parameters
762 let meth_tps: Vec<ty::t> =
763 method.generics.types.get_slice(subst::FnSpace)
765 .map(|def| ty::mk_param_from_def(tcx, def))
767 let meth_regions: Vec<ty::Region> =
768 method.generics.regions.get_slice(subst::FnSpace)
770 .map(|def| ty::ReEarlyBound(def.def_id.node, def.space,
771 def.index, def.name))
773 trait_ref.substs.clone().with_method(meth_tps, meth_regions)
776 fn subst_receiver_types_in_method_ty(tcx: &ty::ctxt,
778 impl_poly_type: &ty::Polytype,
779 trait_ref: &ty::TraitRef,
780 new_def_id: ast::DefId,
782 provided_source: Option<ast::DefId>)
785 let combined_substs = make_substs_for_receiver_types(tcx, trait_ref, method);
787 debug!("subst_receiver_types_in_method_ty: combined_substs={}",
788 combined_substs.repr(tcx));
790 let mut method_generics = method.generics.subst(tcx, &combined_substs);
792 // replace the type parameters declared on the trait with those
794 for &space in [subst::TypeSpace, subst::SelfSpace].iter() {
795 method_generics.types.replace(
797 Vec::from_slice(impl_poly_type.generics.types.get_slice(space)));
798 method_generics.regions.replace(
800 Vec::from_slice(impl_poly_type.generics.regions.get_slice(space)));
803 debug!("subst_receiver_types_in_method_ty: method_generics={}",
804 method_generics.repr(tcx));
806 let method_fty = method.fty.subst(tcx, &combined_substs);
808 debug!("subst_receiver_types_in_method_ty: method_ty={}",
809 method.fty.repr(tcx));
815 method.explicit_self,
818 ImplContainer(impl_id),
823 pub fn check_coherence(crate_context: &CrateCtxt, krate: &Crate) {
825 crate_context: crate_context,
826 inference_context: new_infer_ctxt(crate_context.tcx),