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 metadata::cstore::LOCAL_CRATE;
  15 use middle::def_id::DefId;
  16 use middle::traits;
  17 use middle::ty;
  18 use middle::infer::{self, new_infer_ctxt};
  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         let trait_def_id = trait_def.trait_ref.def_id;
  69
  70         // Conflicts can only occur between a blanket impl and another impl,
  71         // or between 2 non-blanket impls of the same kind.
  72
  73         for (i, &impl1_def_id) in blanket_impls.iter().enumerate() {
  74             for &impl2_def_id in &blanket_impls[(i+1)..] {
  75                 self.check_if_impls_overlap(trait_def_id,
  76                                             impl1_def_id,
  77                                             impl2_def_id);
  78             }
  79
  80             for v in nonblanket_impls.values() {
  81                 for &impl2_def_id in v {
  82                     self.check_if_impls_overlap(trait_def_id,
  83                                                 impl1_def_id,
  84                                                 impl2_def_id);
  85                 }
  86             }
  87         }
  88
  89         for impl_group in nonblanket_impls.values() {
  90             for (i, &impl1_def_id) in impl_group.iter().enumerate() {
  91                 for &impl2_def_id in &impl_group[(i+1)..] {
  92                     self.check_if_impls_overlap(trait_def_id,
  93                                                 impl1_def_id,
  94                                                 impl2_def_id);
  95                 }
  96             }
  97         }
  98     }
  99
 100     // We need to coherently pick which impl will be displayed
 101     // as causing the error message, and it must be the in the current
 102     // crate. Just pick the smaller impl in the file.
 103     fn order_impls(&self, impl1_def_id: DefId, impl2_def_id: DefId)
 104             -> Option<(DefId, DefId)> {
 105         if impl1_def_id.krate != LOCAL_CRATE {
 106             if impl2_def_id.krate != LOCAL_CRATE {
 107                 // we don't need to check impls if both are external;
 108                 // that's the other crate's job.
 109                 None
 110             } else {
 111                 Some((impl2_def_id, impl1_def_id))
 112             }
 113         } else if impl2_def_id.krate != LOCAL_CRATE {
 114             Some((impl1_def_id, impl2_def_id))
 115         } else if impl1_def_id < impl2_def_id {
 116             Some((impl1_def_id, impl2_def_id))
 117         } else {
 118             Some((impl2_def_id, impl1_def_id))
 119         }
 120     }
 121
 122
 123     fn check_if_impls_overlap(&self,
 124                               trait_def_id: DefId,
 125                               impl1_def_id: DefId,
 126                               impl2_def_id: DefId)
 127     {
 128         if let Some((impl1_def_id, impl2_def_id)) = self.order_impls(
 129             impl1_def_id, impl2_def_id)
 130         {
 131             debug!("check_if_impls_overlap({:?}, {:?}, {:?})",
 132                    trait_def_id,
 133                    impl1_def_id,
 134                    impl2_def_id);
 135
 136             let infcx = infer::new_infer_ctxt(self.tcx, &self.tcx.tables, None, false);
 137             if traits::overlapping_impls(&infcx, impl1_def_id, impl2_def_id) {
 138                 self.report_overlap_error(trait_def_id, impl1_def_id, impl2_def_id);
 139             }
 140         }
 141     }
 142
 143     fn report_overlap_error(&self, trait_def_id: DefId,
 144                             impl1: DefId, impl2: DefId) {
 145
 146         span_err!(self.tcx.sess, self.span_of_impl(impl1), E0119,
 147                   "conflicting implementations for trait `{}`",
 148                   self.tcx.item_path_str(trait_def_id));
 149
 150         self.report_overlap_note(impl2);
 151     }
 152
 153     fn report_overlap_note(&self, impl2: DefId) {
 154
 155         if impl2.is_local() {
 156             span_note!(self.tcx.sess, self.span_of_impl(impl2),
 157                        "note conflicting implementation here");
 158         } else {
 159             let crate_store = &self.tcx.sess.cstore;
 160             let cdata = crate_store.get_crate_data(impl2.krate);
 161             self.tcx.sess.note(&format!("conflicting implementation in crate `{}`", cdata.name));
 162         }
 163     }
 164
 165     fn span_of_impl(&self, impl_did: DefId) -> Span {
 166         let node_id = self.tcx.map.as_local_node_id(impl_did).unwrap();
 167         self.tcx.map.span(node_id)
 168     }
 169 }
 170
 171
 172 impl<'cx, 'tcx,'v> intravisit::Visitor<'v> for OverlapChecker<'cx, 'tcx> {
 173     fn visit_item(&mut self, item: &'v hir::Item) {
 174         match item.node {
 175             hir::ItemDefaultImpl(_, _) => {
 176                 // look for another default impl; note that due to the
 177                 // general orphan/coherence rules, it must always be
 178                 // in this crate.
 179                 let impl_def_id = self.tcx.map.local_def_id(item.id);
 180                 let trait_ref = self.tcx.impl_trait_ref(impl_def_id).unwrap();
 181                 let prev_default_impl = self.default_impls.insert(trait_ref.def_id, item.id);
 182                 match prev_default_impl {
 183                     Some(prev_id) => {
 184                         self.report_overlap_error(trait_ref.def_id,
 185                                                   impl_def_id,
 186                                                   self.tcx.map.local_def_id(prev_id));
 187                     }
 188                     None => { }
 189                 }
 190             }
 191             hir::ItemImpl(_, _, _, Some(_), ref self_ty, _) => {
 192                 let impl_def_id = self.tcx.map.local_def_id(item.id);
 193                 let trait_ref = self.tcx.impl_trait_ref(impl_def_id).unwrap();
 194                 let trait_def_id = trait_ref.def_id;
 195                 match trait_ref.self_ty().sty {
 196                     ty::TyTrait(ref data) => {
 197                         // This is something like impl Trait1 for Trait2. Illegal
 198                         // if Trait1 is a supertrait of Trait2 or Trait2 is not object safe.
 199
 200                         if !traits::is_object_safe(self.tcx, data.principal_def_id()) {
 201                             // FIXME(#27579). This just means the
 202                             // self-ty is illegal; WF will report this
 203                             // error. But it will do so as a warning
 204                             // for a release or two.  For backwards
 205                             // compat reasons, then, we continue to
 206                             // report it here so that things which
 207                             // were errors remain errors.
 208                             span_err!(self.tcx.sess, self_ty.span, E0372,
 209                                       "the trait `{}` cannot be made into an object",
 210                                       self.tcx.item_path_str(data.principal_def_id()));
 211                         } else {
 212                             let mut supertrait_def_ids =
 213                                 traits::supertrait_def_ids(self.tcx, data.principal_def_id());
 214                             if supertrait_def_ids.any(|d| d == trait_def_id) {
 215                                 span_err!(self.tcx.sess, item.span, E0371,
 216                                           "the object type `{}` automatically \
 217                                            implements the trait `{}`",
 218                                           trait_ref.self_ty(),
 219                                           self.tcx.item_path_str(trait_def_id));
 220                             }
 221                         }
 222                     }
 223                     _ => { }
 224                 }
 225             }
 226             _ => {
 227             }
 228         }
 229     }
 230 }