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_duplicate_items_in_impl(&self, impl_: DefId) {
  62         let impl_items = self.tcx.associated_items(impl_);
  63
  64         let mut seen_items = FxHashMap::default();
  65         for impl_item in impl_items.in_definition_order() {
  66             let span = self.tcx.def_span(impl_item.def_id);
  67             let ident = impl_item.ident(self.tcx);
  68
  69             let norm_ident = ident.normalize_to_macros_2_0();
  70             match seen_items.entry(norm_ident) {
  71                 Entry::Occupied(entry) => {
  72                     let former = entry.get();
  73                     let mut err = struct_span_err!(
  74                         self.tcx.sess,
  75                         span,
  76                         E0592,
  77                         "duplicate definitions with name `{}`",
  78                         ident,
  79                     );
  80                     err.span_label(span, format!("duplicate definitions for `{}`", ident));
  81                     err.span_label(*former, format!("other definition for `{}`", ident));
  82
  83                     err.emit();
  84                 }
  85                 Entry::Vacant(entry) => {
  86                     entry.insert(span);
  87                 }
  88             }
  89         }
  90     }
  91
  92     fn check_for_common_items_in_impls(
  93         &self,
  94         impl1: DefId,
  95         impl2: DefId,
  96         overlap: traits::OverlapResult<'_>,
  97     ) {
  98         let impl_items1 = self.tcx.associated_items(impl1);
  99         let impl_items2 = self.tcx.associated_items(impl2);
 100
 101         for item1 in impl_items1.in_definition_order() {
 102             let collision = impl_items2
 103                 .filter_by_name_unhygienic(item1.name)
 104                 .find(|item2| self.compare_hygienically(item1, item2));
 105
 106             if let Some(item2) = collision {
 107                 let name = item1.ident(self.tcx).normalize_to_macros_2_0();
 108                 let mut err = struct_span_err!(
 109                     self.tcx.sess,
 110                     self.tcx.def_span(item1.def_id),
 111                     E0592,
 112                     "duplicate definitions with name `{}`",
 113                     name
 114                 );
 115                 err.span_label(
 116                     self.tcx.def_span(item1.def_id),
 117                     format!("duplicate definitions for `{}`", name),
 118                 );
 119                 err.span_label(
 120                     self.tcx.def_span(item2.def_id),
 121                     format!("other definition for `{}`", name),
 122                 );
 123
 124                 for cause in &overlap.intercrate_ambiguity_causes {
 125                     cause.add_intercrate_ambiguity_hint(&mut err);
 126                 }
 127
 128                 if overlap.involves_placeholder {
 129                     traits::add_placeholder_note(&mut err);
 130                 }
 131
 132                 err.emit();
 133             }
 134         }
 135     }
 136
 137     fn check_for_overlapping_inherent_impls(
 138         &self,
 139         overlap_mode: OverlapMode,
 140         impl1_def_id: DefId,
 141         impl2_def_id: DefId,
 142     ) {
 143         traits::overlapping_impls(
 144             self.tcx,
 145             impl1_def_id,
 146             impl2_def_id,
 147             // We go ahead and just skip the leak check for
 148             // inherent impls without warning.
 149             SkipLeakCheck::Yes,
 150             overlap_mode,
 151         )
 152         .map_or(true, |overlap| {
 153             self.check_for_common_items_in_impls(impl1_def_id, impl2_def_id, overlap);
 154             false
 155         });
 156     }
 157
 158     fn check_item(&mut self, id: hir::ItemId) {
 159         let def_kind = self.tcx.def_kind(id.owner_id);
 160         if !matches!(def_kind, DefKind::Enum | DefKind::Struct | DefKind::Trait | DefKind::Union) {
 161             return;
 162         }
 163
 164         let impls = self.tcx.inherent_impls(id.owner_id);
 165
 166         let overlap_mode = OverlapMode::get(self.tcx, id.owner_id.to_def_id());
 167
 168         let impls_items = impls
 169             .iter()
 170             .map(|impl_def_id| (impl_def_id, self.tcx.associated_items(*impl_def_id)))
 171             .collect::<SmallVec<[_; 8]>>();
 172
 173         // Perform a O(n^2) algorithm for small n,
 174         // otherwise switch to an allocating algorithm with
 175         // faster asymptotic runtime.
 176         const ALLOCATING_ALGO_THRESHOLD: usize = 500;
 177         if impls.len() < ALLOCATING_ALGO_THRESHOLD {
 178             for (i, &(&impl1_def_id, impl_items1)) in impls_items.iter().enumerate() {
 179                 self.check_for_duplicate_items_in_impl(impl1_def_id);
 180
 181                 for &(&impl2_def_id, impl_items2) in &impls_items[(i + 1)..] {
 182                     if self.impls_have_common_items(impl_items1, impl_items2) {
 183                         self.check_for_overlapping_inherent_impls(
 184                             overlap_mode,
 185                             impl1_def_id,
 186                             impl2_def_id,
 187                         );
 188                     }
 189                 }
 190             }
 191         } else {
 192             // Build a set of connected regions of impl blocks.
 193             // Two impl blocks are regarded as connected if they share
 194             // an item with the same unhygienic identifier.
 195             // After we have assembled the connected regions,
 196             // run the O(n^2) algorithm on each connected region.
 197             // This is advantageous to running the algorithm over the
 198             // entire graph when there are many connected regions.
 199
 200             rustc_index::newtype_index! {
 201                 #[custom_encodable]
 202                 pub struct RegionId {}
 203             }
 204
 205             struct ConnectedRegion {
 206                 idents: SmallVec<[Symbol; 8]>,
 207                 impl_blocks: FxHashSet<usize>,
 208             }
 209             let mut connected_regions: IndexVec<RegionId, _> = Default::default();
 210             // Reverse map from the Symbol to the connected region id.
 211             let mut connected_region_ids = FxHashMap::default();
 212
 213             for (i, &(&_impl_def_id, impl_items)) in impls_items.iter().enumerate() {
 214                 if impl_items.len() == 0 {
 215                     continue;
 216                 }
 217                 // First obtain a list of existing connected region ids
 218                 let mut idents_to_add = SmallVec::<[Symbol; 8]>::new();
 219                 let mut ids = impl_items
 220                     .in_definition_order()
 221                     .filter_map(|item| {
 222                         let entry = connected_region_ids.entry(item.name);
 223                         if let Entry::Occupied(e) = &entry {
 224                             Some(*e.get())
 225                         } else {
 226                             idents_to_add.push(item.name);
 227                             None
 228                         }
 229                     })
 230                     .collect::<SmallVec<[RegionId; 8]>>();
 231                 // Sort the id list so that the algorithm is deterministic
 232                 ids.sort_unstable();
 233                 ids.dedup();
 234                 let ids = ids;
 235                 match &ids[..] {
 236                     // Create a new connected region
 237                     [] => {
 238                         let id_to_set = connected_regions.next_index();
 239                         // Update the connected region ids
 240                         for ident in &idents_to_add {
 241                             connected_region_ids.insert(*ident, id_to_set);
 242                         }
 243                         connected_regions.insert(
 244                             id_to_set,
 245                             ConnectedRegion {
 246                                 idents: idents_to_add,
 247                                 impl_blocks: std::iter::once(i).collect(),
 248                             },
 249                         );
 250                     }
 251                     // Take the only id inside the list
 252                     &[id_to_set] => {
 253                         let region = connected_regions[id_to_set].as_mut().unwrap();
 254                         region.impl_blocks.insert(i);
 255                         region.idents.extend_from_slice(&idents_to_add);
 256                         // Update the connected region ids
 257                         for ident in &idents_to_add {
 258                             connected_region_ids.insert(*ident, id_to_set);
 259                         }
 260                     }
 261                     // We have multiple connected regions to merge.
 262                     // In the worst case this might add impl blocks
 263                     // one by one and can thus be O(n^2) in the size
 264                     // of the resulting final connected region, but
 265                     // this is no issue as the final step to check
 266                     // for overlaps runs in O(n^2) as well.
 267                     &[id_to_set, ..] => {
 268                         let mut region = connected_regions.remove(id_to_set).unwrap();
 269                         region.impl_blocks.insert(i);
 270                         region.idents.extend_from_slice(&idents_to_add);
 271                         // Update the connected region ids
 272                         for ident in &idents_to_add {
 273                             connected_region_ids.insert(*ident, id_to_set);
 274                         }
 275
 276                         // Remove other regions from ids.
 277                         for &id in ids.iter() {
 278                             if id == id_to_set {
 279                                 continue;
 280                             }
 281                             let r = connected_regions.remove(id).unwrap();
 282                             for ident in r.idents.iter() {
 283                                 connected_region_ids.insert(*ident, id_to_set);
 284                             }
 285                             region.idents.extend_from_slice(&r.idents);
 286                             region.impl_blocks.extend(r.impl_blocks);
 287                         }
 288
 289                         connected_regions.insert(id_to_set, region);
 290                     }
 291                 }
 292             }
 293
 294             debug!(
 295                 "churning through {} components (sum={}, avg={}, var={}, max={})",
 296                 connected_regions.len(),
 297                 impls.len(),
 298                 impls.len() / connected_regions.len(),
 299                 {
 300                     let avg = impls.len() / connected_regions.len();
 301                     let s = connected_regions
 302                         .iter()
 303                         .flatten()
 304                         .map(|r| r.impl_blocks.len() as isize - avg as isize)
 305                         .map(|v| v.abs() as usize)
 306                         .sum::<usize>();
 307                     s / connected_regions.len()
 308                 },
 309                 connected_regions.iter().flatten().map(|r| r.impl_blocks.len()).max().unwrap()
 310             );
 311             // List of connected regions is built. Now, run the overlap check
 312             // for each pair of impl blocks in the same connected region.
 313             for region in connected_regions.into_iter().flatten() {
 314                 let mut impl_blocks =
 315                     region.impl_blocks.into_iter().collect::<SmallVec<[usize; 8]>>();
 316                 impl_blocks.sort_unstable();
 317                 for (i, &impl1_items_idx) in impl_blocks.iter().enumerate() {
 318                     let &(&impl1_def_id, impl_items1) = &impls_items[impl1_items_idx];
 319                     self.check_for_duplicate_items_in_impl(impl1_def_id);
 320
 321                     for &impl2_items_idx in impl_blocks[(i + 1)..].iter() {
 322                         let &(&impl2_def_id, impl_items2) = &impls_items[impl2_items_idx];
 323                         if self.impls_have_common_items(impl_items1, impl_items2) {
 324                             self.check_for_overlapping_inherent_impls(
 325                                 overlap_mode,
 326                                 impl1_def_id,
 327                                 impl2_def_id,
 328                             );
 329                         }
 330                     }
 331                 }
 332             }
 333         }
 334     }
 335 }