[rustc.git] / compiler / rustc_typeck / src / coherence / inherent_impls_overlap.rs

use rustc_data_structures::fx::{FxHashMap, FxHashSet};
use rustc_errors::struct_span_err;
use rustc_hir as hir;
use rustc_hir::def_id::DefId;
use rustc_hir::itemlikevisit::ItemLikeVisitor;
use rustc_index::vec::IndexVec;
use rustc_middle::ty::{self, TyCtxt};
use rustc_span::Symbol;
use rustc_trait_selection::traits::{self, SkipLeakCheck};
use smallvec::SmallVec;
use std::collections::hash_map::Entry;

pub fn crate_inherent_impls_overlap_check(tcx: TyCtxt<'_>, (): ()) {
    tcx.hir().visit_all_item_likes(&mut InherentOverlapChecker { tcx });
}

struct InherentOverlapChecker<'tcx> {
    tcx: TyCtxt<'tcx>,
}

impl InherentOverlapChecker<'tcx> {
    /// Checks whether any associated items in impls 1 and 2 share the same identifier and
    /// namespace.
    fn impls_have_common_items(
        &self,
        impl_items1: &ty::AssocItems<'_>,
        impl_items2: &ty::AssocItems<'_>,
    ) -> bool {
        let mut impl_items1 = &impl_items1;
        let mut impl_items2 = &impl_items2;

        // Performance optimization: iterate over the smaller list
        if impl_items1.len() > impl_items2.len() {
            std::mem::swap(&mut impl_items1, &mut impl_items2);
        }

        for item1 in impl_items1.in_definition_order() {
            let collision = impl_items2
                .filter_by_name_unhygienic(item1.ident.name)
                .any(|item2| self.compare_hygienically(item1, item2));

            if collision {
                return true;
            }
        }

        false
    }

    fn compare_hygienically(&self, item1: &ty::AssocItem, item2: &ty::AssocItem) -> bool {
        // Symbols and namespace match, compare hygienically.
        item1.kind.namespace() == item2.kind.namespace()
            && item1.ident.normalize_to_macros_2_0() == item2.ident.normalize_to_macros_2_0()
    }

    fn check_for_common_items_in_impls(
        &self,
        impl1: DefId,
        impl2: DefId,
        overlap: traits::OverlapResult<'_>,
    ) {
        let impl_items1 = self.tcx.associated_items(impl1);
        let impl_items2 = self.tcx.associated_items(impl2);

        for item1 in impl_items1.in_definition_order() {
            let collision = impl_items2
                .filter_by_name_unhygienic(item1.ident.name)
                .find(|item2| self.compare_hygienically(item1, item2));

            if let Some(item2) = collision {
                let name = item1.ident.normalize_to_macros_2_0();
                let mut err = struct_span_err!(
                    self.tcx.sess,
                    self.tcx.span_of_impl(item1.def_id).unwrap(),
                    E0592,
                    "duplicate definitions with name `{}`",
                    name
                );
                err.span_label(
                    self.tcx.span_of_impl(item1.def_id).unwrap(),
                    format!("duplicate definitions for `{}`", name),
                );
                err.span_label(
                    self.tcx.span_of_impl(item2.def_id).unwrap(),
                    format!("other definition for `{}`", name),
                );

                for cause in &overlap.intercrate_ambiguity_causes {
                    cause.add_intercrate_ambiguity_hint(&mut err);
                }

                if overlap.involves_placeholder {
                    traits::add_placeholder_note(&mut err);
                }

                err.emit();
            }
        }
    }

    fn check_for_overlapping_inherent_impls(&self, impl1_def_id: DefId, impl2_def_id: DefId) {
        traits::overlapping_impls(
            self.tcx,
            impl1_def_id,
            impl2_def_id,
            // We go ahead and just skip the leak check for
            // inherent impls without warning.
            SkipLeakCheck::Yes,
            |overlap| {
                self.check_for_common_items_in_impls(impl1_def_id, impl2_def_id, overlap);
                false
            },
            || true,
        );
    }
}

impl ItemLikeVisitor<'v> for InherentOverlapChecker<'tcx> {
    fn visit_item(&mut self, item: &'v hir::Item<'v>) {
        match item.kind {
            hir::ItemKind::Enum(..)
            | hir::ItemKind::Struct(..)
            | hir::ItemKind::Trait(..)
            | hir::ItemKind::Union(..) => {
                let impls = self.tcx.inherent_impls(item.def_id);

                // If there is only one inherent impl block,
                // there is nothing to overlap check it with
                if impls.len() <= 1 {
                    return;
                }

                let impls_items = impls
                    .iter()
                    .map(|impl_def_id| (impl_def_id, self.tcx.associated_items(*impl_def_id)))
                    .collect::<SmallVec<[_; 8]>>();

                // Perform a O(n^2) algorithm for small n,
                // otherwise switch to an allocating algorithm with
                // faster asymptotic runtime.
                const ALLOCATING_ALGO_THRESHOLD: usize = 500;
                if impls.len() < ALLOCATING_ALGO_THRESHOLD {
                    for (i, &(&impl1_def_id, impl_items1)) in impls_items.iter().enumerate() {
                        for &(&impl2_def_id, impl_items2) in &impls_items[(i + 1)..] {
                            if self.impls_have_common_items(impl_items1, impl_items2) {
                                self.check_for_overlapping_inherent_impls(
                                    impl1_def_id,
                                    impl2_def_id,
                                );
                            }
                        }
                    }
                } else {
                    // Build a set of connected regions of impl blocks.
                    // Two impl blocks are regarded as connected if they share
                    // an item with the same unhygienic identifier.
                    // After we have assembled the connected regions,
                    // run the O(n^2) algorithm on each connected region.
                    // This is advantageous to running the algorithm over the
                    // entire graph when there are many connected regions.

                    rustc_index::newtype_index! {
                        pub struct RegionId {
                            ENCODABLE = custom
                        }
                    }
                    struct ConnectedRegion {
                        idents: SmallVec<[Symbol; 8]>,
                        impl_blocks: FxHashSet<usize>,
                    }
                    let mut connected_regions: IndexVec<RegionId, _> = Default::default();
                    // Reverse map from the Symbol to the connected region id.
                    let mut connected_region_ids = FxHashMap::default();

                    for (i, &(&_impl_def_id, impl_items)) in impls_items.iter().enumerate() {
                        if impl_items.len() == 0 {
                            continue;
                        }
                        // First obtain a list of existing connected region ids
                        let mut idents_to_add = SmallVec::<[Symbol; 8]>::new();
                        let mut ids = impl_items
                            .in_definition_order()
                            .filter_map(|item| {
                                let entry = connected_region_ids.entry(item.ident.name);
                                if let Entry::Occupied(e) = &entry {
                                    Some(*e.get())
                                } else {
                                    idents_to_add.push(item.ident.name);
                                    None
                                }
                            })
                            .collect::<SmallVec<[RegionId; 8]>>();
                        // Sort the id list so that the algorithm is deterministic
                        ids.sort_unstable();
                        ids.dedup();
                        let ids = ids;
                        match &ids[..] {
                            // Create a new connected region
                            [] => {
                                let id_to_set = connected_regions.next_index();
                                // Update the connected region ids
                                for ident in &idents_to_add {
                                    connected_region_ids.insert(*ident, id_to_set);
                                }
                                connected_regions.insert(
                                    id_to_set,
                                    ConnectedRegion {
                                        idents: idents_to_add,
                                        impl_blocks: std::iter::once(i).collect(),
                                    },
                                );
                            }
                            // Take the only id inside the list
                            &[id_to_set] => {
                                let region = connected_regions[id_to_set].as_mut().unwrap();
                                region.impl_blocks.insert(i);
                                region.idents.extend_from_slice(&idents_to_add);
                                // Update the connected region ids
                                for ident in &idents_to_add {
                                    connected_region_ids.insert(*ident, id_to_set);
                                }
                            }
                            // We have multiple connected regions to merge.
                            // In the worst case this might add impl blocks
                            // one by one and can thus be O(n^2) in the size
                            // of the resulting final connected region, but
                            // this is no issue as the final step to check
                            // for overlaps runs in O(n^2) as well.
                            &[id_to_set, ..] => {
                                let mut region = connected_regions.remove(id_to_set).unwrap();
                                region.impl_blocks.insert(i);
                                region.idents.extend_from_slice(&idents_to_add);
                                // Update the connected region ids
                                for ident in &idents_to_add {
                                    connected_region_ids.insert(*ident, id_to_set);
                                }

                                // Remove other regions from ids.
                                for &id in ids.iter() {
                                    if id == id_to_set {
                                        continue;
                                    }
                                    let r = connected_regions.remove(id).unwrap();
                                    for ident in r.idents.iter() {
                                        connected_region_ids.insert(*ident, id_to_set);
                                    }
                                    region.idents.extend_from_slice(&r.idents);
                                    region.impl_blocks.extend(r.impl_blocks);
                                }

                                connected_regions.insert(id_to_set, region);
                            }
                        }
                    }

                    debug!(
                        "churning through {} components (sum={}, avg={}, var={}, max={})",
                        connected_regions.len(),
                        impls.len(),
                        impls.len() / connected_regions.len(),
                        {
                            let avg = impls.len() / connected_regions.len();
                            let s = connected_regions
                                .iter()
                                .flatten()
                                .map(|r| r.impl_blocks.len() as isize - avg as isize)
                                .map(|v| v.abs() as usize)
                                .sum::<usize>();
                            s / connected_regions.len()
                        },
                        connected_regions
                            .iter()
                            .flatten()
                            .map(|r| r.impl_blocks.len())
                            .max()
                            .unwrap()
                    );
                    // List of connected regions is built. Now, run the overlap check
                    // for each pair of impl blocks in the same connected region.
                    for region in connected_regions.into_iter().flatten() {
                        let mut impl_blocks =
                            region.impl_blocks.into_iter().collect::<SmallVec<[usize; 8]>>();
                        impl_blocks.sort_unstable();
                        for (i, &impl1_items_idx) in impl_blocks.iter().enumerate() {
                            let &(&impl1_def_id, impl_items1) = &impls_items[impl1_items_idx];
                            for &impl2_items_idx in impl_blocks[(i + 1)..].iter() {
                                let &(&impl2_def_id, impl_items2) = &impls_items[impl2_items_idx];
                                if self.impls_have_common_items(impl_items1, impl_items2) {
                                    self.check_for_overlapping_inherent_impls(
                                        impl1_def_id,
                                        impl2_def_id,
                                    );
                                }
                            }
                        }
                    }
                }
            }
            _ => {}
        }
    }

    fn visit_trait_item(&mut self, _trait_item: &hir::TraitItem<'v>) {}

    fn visit_impl_item(&mut self, _impl_item: &hir::ImplItem<'v>) {}

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