src/librustc_typeck/coherence/overlap.rs

   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.
   4 //
   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.
  10
  11 //! Overlap: No two impls for the same trait are implemented for the
  12 //! same type.
  13
  14 use middle::traits;
  15 use middle::ty;
  16 use middle::infer::{self, new_infer_ctxt};
  17 use syntax::ast::DefId;
  18 use syntax::ast::LOCAL_CRATE;
  19 use syntax::ast;
  20 use syntax::ast_util;
  21 use syntax::visit;
  22 use syntax::codemap::Span;
  23 use util::nodemap::DefIdMap;
  24 use util::ppaux::Repr;
  25
  26 pub fn check(tcx: &ty::ctxt) {
  27     let mut overlap = OverlapChecker { tcx: tcx, default_impls: DefIdMap() };
  28     overlap.check_for_overlapping_impls();
  29
  30     // this secondary walk specifically checks for impls of defaulted
  31     // traits, for which additional overlap rules exist
  32     visit::walk_crate(&mut overlap, tcx.map.krate());
  33 }
  34
  35 struct OverlapChecker<'cx, 'tcx:'cx> {
  36     tcx: &'cx ty::ctxt<'tcx>,
  37
  38     // maps from a trait def-id to an impl id
  39     default_impls: DefIdMap<ast::NodeId>,
  40 }
  41
  42 impl<'cx, 'tcx> OverlapChecker<'cx, 'tcx> {
  43     fn check_for_overlapping_impls(&self) {
  44         debug!("check_for_overlapping_impls");
  45
  46         // Collect this into a vector to avoid holding the
  47         // refcell-lock during the
  48         // check_for_overlapping_impls_of_trait() check, since that
  49         // check can populate this table further with impls from other
  50         // crates.
  51         let trait_def_ids: Vec<(ast::DefId, Vec<ast::DefId>)> =
  52             self.tcx.trait_impls.borrow().iter().map(|(&k, v)| {
  53                 // FIXME -- it seems like this method actually pushes
  54                 // duplicate impls onto the list
  55                 ty::populate_implementations_for_trait_if_necessary(self.tcx, k);
  56                 (k, v.borrow().clone())
  57             }).collect();
  58
  59         for &(trait_def_id, ref impls) in &trait_def_ids {
  60             self.check_for_overlapping_impls_of_trait(trait_def_id, impls);
  61         }
  62     }
  63
  64     fn check_for_overlapping_impls_of_trait(&self,
  65                                             trait_def_id: ast::DefId,
  66                                             trait_impls: &Vec<ast::DefId>)
  67     {
  68         debug!("check_for_overlapping_impls_of_trait(trait_def_id={})",
  69                trait_def_id.repr(self.tcx));
  70
  71         for (i, &impl1_def_id) in trait_impls.iter().enumerate() {
  72             if impl1_def_id.krate != ast::LOCAL_CRATE {
  73                 // we don't need to check impls if both are external;
  74                 // that's the other crate's job.
  75                 continue;
  76             }
  77
  78             for &impl2_def_id in &trait_impls[(i+1)..] {
  79                 self.check_if_impls_overlap(trait_def_id,
  80                                             impl1_def_id,
  81                                             impl2_def_id);
  82             }
  83         }
  84     }
  85
  86     fn check_if_impls_overlap(&self,
  87                               trait_def_id: ast::DefId,
  88                               impl1_def_id: ast::DefId,
  89                               impl2_def_id: ast::DefId)
  90     {
  91         assert_eq!(impl1_def_id.krate, ast::LOCAL_CRATE);
  92
  93         debug!("check_if_impls_overlap({}, {}, {})",
  94                trait_def_id.repr(self.tcx),
  95                impl1_def_id.repr(self.tcx),
  96                impl2_def_id.repr(self.tcx));
  97
  98         let infcx = infer::new_infer_ctxt(self.tcx);
  99         if !traits::overlapping_impls(&infcx, impl1_def_id, impl2_def_id) {
 100             return;
 101         }
 102
 103         self.report_overlap_error(trait_def_id, impl1_def_id, impl2_def_id);
 104     }
 105
 106     fn report_overlap_error(&self, trait_def_id: ast::DefId,
 107                             impl1: ast::DefId, impl2: ast::DefId) {
 108
 109         span_err!(self.tcx.sess, self.span_of_impl(impl1), E0119,
 110                   "conflicting implementations for trait `{}`",
 111                   ty::item_path_str(self.tcx, trait_def_id));
 112
 113         self.report_overlap_note(impl1, impl2);
 114     }
 115
 116     fn report_overlap_note(&self, impl1: ast::DefId, impl2: ast::DefId) {
 117
 118         if impl2.krate == ast::LOCAL_CRATE {
 119             span_note!(self.tcx.sess, self.span_of_impl(impl2),
 120                        "note conflicting implementation here");
 121         } else {
 122             let crate_store = &self.tcx.sess.cstore;
 123             let cdata = crate_store.get_crate_data(impl2.krate);
 124             span_note!(self.tcx.sess, self.span_of_impl(impl1),
 125                        "conflicting implementation in crate `{}`",
 126                        cdata.name);
 127         }
 128     }
 129
 130     fn span_of_impl(&self, impl_did: ast::DefId) -> Span {
 131         assert_eq!(impl_did.krate, ast::LOCAL_CRATE);
 132         self.tcx.map.span(impl_did.node)
 133     }
 134 }
 135
 136
 137 impl<'cx, 'tcx,'v> visit::Visitor<'v> for OverlapChecker<'cx, 'tcx> {
 138     fn visit_item(&mut self, item: &'v ast::Item) {
 139         match item.node {
 140             ast::ItemDefaultImpl(_, _) => {
 141                 // look for another default impl; note that due to the
 142                 // general orphan/coherence rules, it must always be
 143                 // in this crate.
 144                 let impl_def_id = ast_util::local_def(item.id);
 145                 let trait_ref = ty::impl_trait_ref(self.tcx, impl_def_id).unwrap();
 146                 let prev_default_impl = self.default_impls.insert(trait_ref.def_id, item.id);
 147                 match prev_default_impl {
 148                     Some(prev_id) => {
 149                         self.report_overlap_error(trait_ref.def_id,
 150                                                   impl_def_id,
 151                                                   ast_util::local_def(prev_id));
 152                     }
 153                     None => { }
 154                 }
 155             }
 156             _ => {}
 157         }
 158     }
 159 }