compiler/rustc_typeck/src/coherence/inherent_impls_overlap.rs

   1 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
   2 use rustc_errors::struct_span_err;
   3 use rustc_hir as hir;
   4 use rustc_hir::def_id::{CrateNum, DefId, LOCAL_CRATE};
   5 use rustc_hir::itemlikevisit::ItemLikeVisitor;
   6 use rustc_middle::ty::{self, TyCtxt};
   7 use rustc_span::Symbol;
   8 use rustc_trait_selection::traits::{self, SkipLeakCheck};
   9 use smallvec::SmallVec;
  10 use std::collections::hash_map::Entry;
  11
  12 pub fn crate_inherent_impls_overlap_check(tcx: TyCtxt<'_>, crate_num: CrateNum) {
  13     assert_eq!(crate_num, LOCAL_CRATE);
  14     let krate = tcx.hir().krate();
  15     krate.visit_all_item_likes(&mut InherentOverlapChecker { tcx });
  16 }
  17
  18 struct InherentOverlapChecker<'tcx> {
  19     tcx: TyCtxt<'tcx>,
  20 }
  21
  22 impl InherentOverlapChecker<'tcx> {
  23     /// Checks whether any associated items in impls 1 and 2 share the same identifier and
  24     /// namespace.
  25     fn impls_have_common_items(
  26         &self,
  27         impl_items1: &ty::AssocItems<'_>,
  28         impl_items2: &ty::AssocItems<'_>,
  29     ) -> bool {
  30         let mut impl_items1 = &impl_items1;
  31         let mut impl_items2 = &impl_items2;
  32
  33         // Performance optimization: iterate over the smaller list
  34         if impl_items1.len() > impl_items2.len() {
  35             std::mem::swap(&mut impl_items1, &mut impl_items2);
  36         }
  37
  38         for item1 in impl_items1.in_definition_order() {
  39             let collision = impl_items2
  40                 .filter_by_name_unhygienic(item1.ident.name)
  41                 .any(|item2| self.compare_hygienically(item1, item2));
  42
  43             if collision {
  44                 return true;
  45             }
  46         }
  47
  48         false
  49     }
  50
  51     fn compare_hygienically(&self, item1: &ty::AssocItem, item2: &ty::AssocItem) -> bool {
  52         // Symbols and namespace match, compare hygienically.
  53         item1.kind.namespace() == item2.kind.namespace()
  54             && item1.ident.normalize_to_macros_2_0() == item2.ident.normalize_to_macros_2_0()
  55     }
  56
  57     fn check_for_common_items_in_impls(
  58         &self,
  59         impl1: DefId,
  60         impl2: DefId,
  61         overlap: traits::OverlapResult<'_>,
  62     ) {
  63         let impl_items1 = self.tcx.associated_items(impl1);
  64         let impl_items2 = self.tcx.associated_items(impl2);
  65
  66         for item1 in impl_items1.in_definition_order() {
  67             let collision = impl_items2
  68                 .filter_by_name_unhygienic(item1.ident.name)
  69                 .find(|item2| self.compare_hygienically(item1, item2));
  70
  71             if let Some(item2) = collision {
  72                 let name = item1.ident.normalize_to_macros_2_0();
  73                 let mut err = struct_span_err!(
  74                     self.tcx.sess,
  75                     self.tcx.span_of_impl(item1.def_id).unwrap(),
  76                     E0592,
  77                     "duplicate definitions with name `{}`",
  78                     name
  79                 );
  80                 err.span_label(
  81                     self.tcx.span_of_impl(item1.def_id).unwrap(),
  82                     format!("duplicate definitions for `{}`", name),
  83                 );
  84                 err.span_label(
  85                     self.tcx.span_of_impl(item2.def_id).unwrap(),
  86                     format!("other definition for `{}`", name),
  87                 );
  88
  89                 for cause in &overlap.intercrate_ambiguity_causes {
  90                     cause.add_intercrate_ambiguity_hint(&mut err);
  91                 }
  92
  93                 if overlap.involves_placeholder {
  94                     traits::add_placeholder_note(&mut err);
  95                 }
  96
  97                 err.emit();
  98             }
  99         }
 100     }
 101
 102     fn check_for_overlapping_inherent_impls(&self, impl1_def_id: DefId, impl2_def_id: DefId) {
 103         traits::overlapping_impls(
 104             self.tcx,
 105             impl1_def_id,
 106             impl2_def_id,
 107             // We go ahead and just skip the leak check for
 108             // inherent impls without warning.
 109             SkipLeakCheck::Yes,
 110             |overlap| {
 111                 self.check_for_common_items_in_impls(impl1_def_id, impl2_def_id, overlap);
 112                 false
 113             },
 114             || true,
 115         );
 116     }
 117 }
 118
 119 impl ItemLikeVisitor<'v> for InherentOverlapChecker<'tcx> {
 120     fn visit_item(&mut self, item: &'v hir::Item<'v>) {
 121         match item.kind {
 122             hir::ItemKind::Enum(..)
 123             | hir::ItemKind::Struct(..)
 124             | hir::ItemKind::Trait(..)
 125             | hir::ItemKind::Union(..) => {
 126                 let impls = self.tcx.inherent_impls(item.def_id);
 127
 128                 // If there is only one inherent impl block,
 129                 // there is nothing to overlap check it with
 130                 if impls.len() <= 1 {
 131                     return;
 132                 }
 133
 134                 let impls_items = impls
 135                     .iter()
 136                     .map(|impl_def_id| (impl_def_id, self.tcx.associated_items(*impl_def_id)))
 137                     .collect::<SmallVec<[_; 8]>>();
 138
 139                 // Perform a O(n^2) algorithm for small n,
 140                 // otherwise switch to an allocating algorithm with
 141                 // faster asymptotic runtime.
 142                 const ALLOCATING_ALGO_THRESHOLD: usize = 500;
 143                 if impls.len() < ALLOCATING_ALGO_THRESHOLD {
 144                     for (i, &(&impl1_def_id, impl_items1)) in impls_items.iter().enumerate() {
 145                         for &(&impl2_def_id, impl_items2) in &impls_items[(i + 1)..] {
 146                             if self.impls_have_common_items(impl_items1, impl_items2) {
 147                                 self.check_for_overlapping_inherent_impls(
 148                                     impl1_def_id,
 149                                     impl2_def_id,
 150                                 );
 151                             }
 152                         }
 153                     }
 154                 } else {
 155                     // Build a set of connected regions of impl blocks.
 156                     // Two impl blocks are regarded as connected if they share
 157                     // an item with the same unhygienic identifier.
 158                     // After we have assembled the connected regions,
 159                     // run the O(n^2) algorithm on each connected region.
 160                     // This is advantageous to running the algorithm over the
 161                     // entire graph when there are many connected regions.
 162
 163                     struct ConnectedRegion {
 164                         idents: SmallVec<[Symbol; 8]>,
 165                         impl_blocks: FxHashSet<usize>,
 166                     }
 167                     // Highest connected region id
 168                     let mut highest_region_id = 0;
 169                     let mut connected_region_ids = FxHashMap::default();
 170                     let mut connected_regions = FxHashMap::default();
 171
 172                     for (i, &(&_impl_def_id, impl_items)) in impls_items.iter().enumerate() {
 173                         if impl_items.len() == 0 {
 174                             continue;
 175                         }
 176                         // First obtain a list of existing connected region ids
 177                         let mut idents_to_add = SmallVec::<[Symbol; 8]>::new();
 178                         let ids = impl_items
 179                             .in_definition_order()
 180                             .filter_map(|item| {
 181                                 let entry = connected_region_ids.entry(item.ident.name);
 182                                 if let Entry::Occupied(e) = &entry {
 183                                     Some(*e.get())
 184                                 } else {
 185                                     idents_to_add.push(item.ident.name);
 186                                     None
 187                                 }
 188                             })
 189                             .collect::<FxHashSet<usize>>();
 190                         match ids.len() {
 191                             0 | 1 => {
 192                                 let id_to_set = if ids.len() == 0 {
 193                                     // Create a new connected region
 194                                     let region = ConnectedRegion {
 195                                         idents: idents_to_add,
 196                                         impl_blocks: std::iter::once(i).collect(),
 197                                     };
 198                                     connected_regions.insert(highest_region_id, region);
 199                                     (highest_region_id, highest_region_id += 1).0
 200                                 } else {
 201                                     // Take the only id inside the list
 202                                     let id_to_set = *ids.iter().next().unwrap();
 203                                     let region = connected_regions.get_mut(&id_to_set).unwrap();
 204                                     region.impl_blocks.insert(i);
 205                                     region.idents.extend_from_slice(&idents_to_add);
 206                                     id_to_set
 207                                 };
 208                                 let (_id, region) = connected_regions.iter().next().unwrap();
 209                                 // Update the connected region ids
 210                                 for ident in region.idents.iter() {
 211                                     connected_region_ids.insert(*ident, id_to_set);
 212                                 }
 213                             }
 214                             _ => {
 215                                 // We have multiple connected regions to merge.
 216                                 // In the worst case this might add impl blocks
 217                                 // one by one and can thus be O(n^2) in the size
 218                                 // of the resulting final connected region, but
 219                                 // this is no issue as the final step to check
 220                                 // for overlaps runs in O(n^2) as well.
 221
 222                                 // Take the smallest id from the list
 223                                 let id_to_set = *ids.iter().min().unwrap();
 224
 225                                 // Sort the id list so that the algorithm is deterministic
 226                                 let mut ids = ids.into_iter().collect::<SmallVec<[_; 8]>>();
 227                                 ids.sort();
 228
 229                                 let mut region = connected_regions.remove(&id_to_set).unwrap();
 230                                 region.idents.extend_from_slice(&idents_to_add);
 231                                 region.impl_blocks.insert(i);
 232
 233                                 for &id in ids.iter() {
 234                                     if id == id_to_set {
 235                                         continue;
 236                                     }
 237                                     let r = connected_regions.remove(&id).unwrap();
 238                                     // Update the connected region ids
 239                                     for ident in r.idents.iter() {
 240                                         connected_region_ids.insert(*ident, id_to_set);
 241                                     }
 242                                     region.idents.extend_from_slice(&r.idents);
 243                                     region.impl_blocks.extend(r.impl_blocks);
 244                                 }
 245                                 connected_regions.insert(id_to_set, region);
 246                             }
 247                         }
 248                     }
 249
 250                     debug!(
 251                         "churning through {} components (sum={}, avg={}, var={}, max={})",
 252                         connected_regions.len(),
 253                         impls.len(),
 254                         impls.len() / connected_regions.len(),
 255                         {
 256                             let avg = impls.len() / connected_regions.len();
 257                             let s = connected_regions
 258                                 .iter()
 259                                 .map(|r| r.1.impl_blocks.len() as isize - avg as isize)
 260                                 .map(|v| v.abs() as usize)
 261                                 .sum::<usize>();
 262                             s / connected_regions.len()
 263                         },
 264                         connected_regions.iter().map(|r| r.1.impl_blocks.len()).max().unwrap()
 265                     );
 266                     // List of connected regions is built. Now, run the overlap check
 267                     // for each pair of impl blocks in the same connected region.
 268                     for (_id, region) in connected_regions.into_iter() {
 269                         let mut impl_blocks =
 270                             region.impl_blocks.into_iter().collect::<SmallVec<[_; 8]>>();
 271                         impl_blocks.sort();
 272                         for (i, &impl1_items_idx) in impl_blocks.iter().enumerate() {
 273                             let &(&impl1_def_id, impl_items1) = &impls_items[impl1_items_idx];
 274                             for &impl2_items_idx in impl_blocks[(i + 1)..].iter() {
 275                                 let &(&impl2_def_id, impl_items2) = &impls_items[impl2_items_idx];
 276                                 if self.impls_have_common_items(impl_items1, impl_items2) {
 277                                     self.check_for_overlapping_inherent_impls(
 278                                         impl1_def_id,
 279                                         impl2_def_id,
 280                                     );
 281                                 }
 282                             }
 283                         }
 284                     }
 285                 }
 286             }
 287             _ => {}
 288         }
 289     }
 290
 291     fn visit_trait_item(&mut self, _trait_item: &hir::TraitItem<'v>) {}
 292
 293     fn visit_impl_item(&mut self, _impl_item: &hir::ImplItem<'v>) {}
 294
 295     fn visit_foreign_item(&mut self, _foreign_item: &hir::ForeignItem<'v>) {}
 296 }