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::cstore::{CrateStore, LOCAL_CRATE};
  15 use middle::def_id::DefId;
  16 use middle::traits;
  17 use middle::ty;
  18 use middle::infer;
  19 use syntax::ast;
  20 use syntax::codemap::Span;
  21 use rustc_front::hir;
  22 use rustc_front::intravisit;
  23 use util::nodemap::DefIdMap;
  24
  25 pub fn check(tcx: &ty::ctxt) {
  26     let mut overlap = OverlapChecker { tcx: tcx, default_impls: DefIdMap() };
  27     overlap.check_for_overlapping_impls();
  28
  29     // this secondary walk specifically checks for some other cases,
  30     // like defaulted traits, for which additional overlap rules exist
  31     tcx.map.krate().visit_all_items(&mut overlap);
  32 }
  33
  34 struct OverlapChecker<'cx, 'tcx:'cx> {
  35     tcx: &'cx ty::ctxt<'tcx>,
  36
  37     // maps from a trait def-id to an impl id
  38     default_impls: DefIdMap<ast::NodeId>,
  39 }
  40
  41 impl<'cx, 'tcx> OverlapChecker<'cx, 'tcx> {
  42     fn check_for_overlapping_impls(&self) {
  43         debug!("check_for_overlapping_impls");
  44
  45         // Collect this into a vector to avoid holding the
  46         // refcell-lock during the
  47         // check_for_overlapping_impls_of_trait() check, since that
  48         // check can populate this table further with impls from other
  49         // crates.
  50         let trait_defs: Vec<_> = self.tcx.trait_defs.borrow().values().cloned().collect();
  51
  52         for trait_def in trait_defs {
  53             self.tcx.populate_implementations_for_trait_if_necessary(trait_def.trait_ref.def_id);
  54             self.check_for_overlapping_impls_of_trait(trait_def);
  55         }
  56     }
  57
  58     fn check_for_overlapping_impls_of_trait(&self,
  59                                             trait_def: &'tcx ty::TraitDef<'tcx>)
  60     {
  61         debug!("check_for_overlapping_impls_of_trait(trait_def={:?})",
  62                trait_def);
  63
  64         // We should already know all impls of this trait, so these
  65         // borrows are safe.
  66         let blanket_impls = trait_def.blanket_impls.borrow();
  67         let nonblanket_impls = trait_def.nonblanket_impls.borrow();
  68
  69         // Conflicts can only occur between a blanket impl and another impl,
  70         // or between 2 non-blanket impls of the same kind.
  71
  72         for (i, &impl1_def_id) in blanket_impls.iter().enumerate() {
  73             for &impl2_def_id in &blanket_impls[(i+1)..] {
  74                 self.check_if_impls_overlap(impl1_def_id,
  75                                             impl2_def_id);
  76             }
  77
  78             for v in nonblanket_impls.values() {
  79                 for &impl2_def_id in v {
  80                     self.check_if_impls_overlap(impl1_def_id,
  81                                                 impl2_def_id);
  82                 }
  83             }
  84         }
  85
  86         for impl_group in nonblanket_impls.values() {
  87             for (i, &impl1_def_id) in impl_group.iter().enumerate() {
  88                 for &impl2_def_id in &impl_group[(i+1)..] {
  89                     self.check_if_impls_overlap(impl1_def_id,
  90                                                 impl2_def_id);
  91                 }
  92             }
  93         }
  94     }
  95
  96     // We need to coherently pick which impl will be displayed
  97     // as causing the error message, and it must be the in the current
  98     // crate. Just pick the smaller impl in the file.
  99     fn order_impls(&self, impl1_def_id: DefId, impl2_def_id: DefId)
 100             -> Option<(DefId, DefId)> {
 101         if impl1_def_id.krate != LOCAL_CRATE {
 102             if impl2_def_id.krate != LOCAL_CRATE {
 103                 // we don't need to check impls if both are external;
 104                 // that's the other crate's job.
 105                 None
 106             } else {
 107                 Some((impl2_def_id, impl1_def_id))
 108             }
 109         } else if impl2_def_id.krate != LOCAL_CRATE {
 110             Some((impl1_def_id, impl2_def_id))
 111         } else if impl1_def_id < impl2_def_id {
 112             Some((impl1_def_id, impl2_def_id))
 113         } else {
 114             Some((impl2_def_id, impl1_def_id))
 115         }
 116     }
 117
 118
 119     fn check_if_impls_overlap(&self,
 120                               impl1_def_id: DefId,
 121                               impl2_def_id: DefId)
 122     {
 123         if let Some((impl1_def_id, impl2_def_id)) = self.order_impls(
 124             impl1_def_id, impl2_def_id)
 125         {
 126             debug!("check_if_impls_overlap({:?}, {:?})",
 127                    impl1_def_id,
 128                    impl2_def_id);
 129
 130             let infcx = infer::new_infer_ctxt(self.tcx, &self.tcx.tables, None, false);
 131             if let Some(trait_ref) = traits::overlapping_impls(&infcx, impl1_def_id, impl2_def_id) {
 132                 self.report_overlap_error(impl1_def_id, impl2_def_id, trait_ref);
 133             }
 134         }
 135     }
 136
 137     fn report_overlap_error(&self,
 138                             impl1: DefId,
 139                             impl2: DefId,
 140                             trait_ref: ty::TraitRef)
 141     {
 142         // only print the Self type if it's concrete; otherwise, it's not adding much information.
 143         let self_type = {
 144             trait_ref.substs.self_ty().and_then(|ty| {
 145                 if let ty::TyInfer(_) = ty.sty {
 146                     None
 147                 } else {
 148                     Some(format!(" for type `{}`", ty))
 149                 }
 150             }).unwrap_or(String::new())
 151         };
 152
 153         span_err!(self.tcx.sess, self.span_of_impl(impl1), E0119,
 154                   "conflicting implementations of trait `{}`{}:",
 155                   trait_ref,
 156                   self_type);
 157
 158         if impl2.is_local() {
 159             span_note!(self.tcx.sess, self.span_of_impl(impl2),
 160                        "conflicting implementation is here:");
 161         } else {
 162             let cname = self.tcx.sess.cstore.crate_name(impl2.krate);
 163             self.tcx.sess.note(&format!("conflicting implementation in crate `{}`", cname));
 164         }
 165     }
 166
 167     fn span_of_impl(&self, impl_did: DefId) -> Span {
 168         let node_id = self.tcx.map.as_local_node_id(impl_did).unwrap();
 169         self.tcx.map.span(node_id)
 170     }
 171 }
 172
 173
 174 impl<'cx, 'tcx,'v> intravisit::Visitor<'v> for OverlapChecker<'cx, 'tcx> {
 175     fn visit_item(&mut self, item: &'v hir::Item) {
 176         match item.node {
 177             hir::ItemDefaultImpl(_, _) => {
 178                 // look for another default impl; note that due to the
 179                 // general orphan/coherence rules, it must always be
 180                 // in this crate.
 181                 let impl_def_id = self.tcx.map.local_def_id(item.id);
 182                 let trait_ref = self.tcx.impl_trait_ref(impl_def_id).unwrap();
 183                 let prev_default_impl = self.default_impls.insert(trait_ref.def_id, item.id);
 184                 match prev_default_impl {
 185                     Some(prev_id) => {
 186                         self.report_overlap_error(impl_def_id,
 187                                                   self.tcx.map.local_def_id(prev_id),
 188                                                   trait_ref);
 189                     }
 190                     None => { }
 191                 }
 192             }
 193             hir::ItemImpl(_, _, _, Some(_), _, _) => {
 194                 let impl_def_id = self.tcx.map.local_def_id(item.id);
 195                 let trait_ref = self.tcx.impl_trait_ref(impl_def_id).unwrap();
 196                 let trait_def_id = trait_ref.def_id;
 197                 match trait_ref.self_ty().sty {
 198                     ty::TyTrait(ref data) => {
 199                         // This is something like impl Trait1 for Trait2. Illegal
 200                         // if Trait1 is a supertrait of Trait2 or Trait2 is not object safe.
 201
 202                         if !traits::is_object_safe(self.tcx, data.principal_def_id()) {
 203                             // This is an error, but it will be
 204                             // reported by wfcheck.  Ignore it
 205                             // here. This is tested by
 206                             // `coherence-impl-trait-for-trait-object-safe.rs`.
 207                         } else {
 208                             let mut supertrait_def_ids =
 209                                 traits::supertrait_def_ids(self.tcx, data.principal_def_id());
 210                             if supertrait_def_ids.any(|d| d == trait_def_id) {
 211                                 span_err!(self.tcx.sess, item.span, E0371,
 212                                           "the object type `{}` automatically \
 213                                            implements the trait `{}`",
 214                                           trait_ref.self_ty(),
 215                                           self.tcx.item_path_str(trait_def_id));
 216                             }
 217                         }
 218                     }
 219                     _ => { }
 220                 }
 221             }
 222             _ => {
 223             }
 224         }
 225     }
 226 }