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