1 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
2 use rustc_errors::struct_span_err;
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;
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);
21 struct InherentOverlapChecker<'tcx> {
25 impl<'tcx> InherentOverlapChecker<'tcx> {
26 /// Checks whether any associated items in impls 1 and 2 share the same identifier and
28 fn impls_have_common_items(
30 impl_items1: &ty::AssocItems<'_>,
31 impl_items2: &ty::AssocItems<'_>,
33 let mut impl_items1 = &impl_items1;
34 let mut impl_items2 = &impl_items2;
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);
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));
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()
61 fn check_for_duplicate_items_in_impl(&self, impl_: DefId) {
62 let impl_items = self.tcx.associated_items(impl_);
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);
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!(
77 "duplicate definitions with name `{}`",
80 err.span_label(span, format!("duplicate definitions for `{}`", ident));
81 err.span_label(*former, format!("other definition for `{}`", ident));
85 Entry::Vacant(entry) => {
92 fn check_for_common_items_in_impls(
96 overlap: traits::OverlapResult<'_>,
98 let impl_items1 = self.tcx.associated_items(impl1);
99 let impl_items2 = self.tcx.associated_items(impl2);
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));
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!(
110 self.tcx.def_span(item1.def_id),
112 "duplicate definitions with name `{}`",
116 self.tcx.def_span(item1.def_id),
117 format!("duplicate definitions for `{}`", name),
120 self.tcx.def_span(item2.def_id),
121 format!("other definition for `{}`", name),
124 for cause in &overlap.intercrate_ambiguity_causes {
125 cause.add_intercrate_ambiguity_hint(&mut err);
128 if overlap.involves_placeholder {
129 traits::add_placeholder_note(&mut err);
137 fn check_for_overlapping_inherent_impls(
139 overlap_mode: OverlapMode,
143 traits::overlapping_impls(
147 // We go ahead and just skip the leak check for
148 // inherent impls without warning.
152 .map_or(true, |overlap| {
153 self.check_for_common_items_in_impls(impl1_def_id, impl2_def_id, overlap);
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) {
164 let impls = self.tcx.inherent_impls(id.owner_id);
166 let overlap_mode = OverlapMode::get(self.tcx, id.owner_id.to_def_id());
168 let impls_items = impls
170 .map(|impl_def_id| (impl_def_id, self.tcx.associated_items(*impl_def_id)))
171 .collect::<SmallVec<[_; 8]>>();
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);
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(
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.
200 rustc_index::newtype_index! {
201 pub struct RegionId {
205 struct ConnectedRegion {
206 idents: SmallVec<[Symbol; 8]>,
207 impl_blocks: FxHashSet<usize>,
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();
213 for (i, &(&_impl_def_id, impl_items)) in impls_items.iter().enumerate() {
214 if impl_items.len() == 0 {
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()
222 let entry = connected_region_ids.entry(item.name);
223 if let Entry::Occupied(e) = &entry {
226 idents_to_add.push(item.name);
230 .collect::<SmallVec<[RegionId; 8]>>();
231 // Sort the id list so that the algorithm is deterministic
236 // Create a new connected region
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);
243 connected_regions.insert(
246 idents: idents_to_add,
247 impl_blocks: std::iter::once(i).collect(),
251 // Take the only id inside the list
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);
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);
276 // Remove other regions from ids.
277 for &id in ids.iter() {
281 let r = connected_regions.remove(id).unwrap();
282 for ident in r.idents.iter() {
283 connected_region_ids.insert(*ident, id_to_set);
285 region.idents.extend_from_slice(&r.idents);
286 region.impl_blocks.extend(r.impl_blocks);
289 connected_regions.insert(id_to_set, region);
295 "churning through {} components (sum={}, avg={}, var={}, max={})",
296 connected_regions.len(),
298 impls.len() / connected_regions.len(),
300 let avg = impls.len() / connected_regions.len();
301 let s = connected_regions
304 .map(|r| r.impl_blocks.len() as isize - avg as isize)
305 .map(|v| v.abs() as usize)
307 s / connected_regions.len()
309 connected_regions.iter().flatten().map(|r| r.impl_blocks.len()).max().unwrap()
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);
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(