diff options
5 files changed, 208 insertions, 1 deletions
diff --git a/compiler/rustc_typeck/src/coherence/inherent_impls_overlap.rs b/compiler/rustc_typeck/src/coherence/inherent_impls_overlap.rs index 4efb2a6273b..50d88674328 100644 --- a/compiler/rustc_typeck/src/coherence/inherent_impls_overlap.rs +++ b/compiler/rustc_typeck/src/coherence/inherent_impls_overlap.rs @@ -140,7 +140,8 @@ impl ItemLikeVisitor<'v> for InherentOverlapChecker<'tcx> { // Perform a O(n^2) algorithm for small n, // otherwise switch to an allocating algorithm with // faster asymptotic runtime. - if impls.len() < 30 { + 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) { diff --git a/src/test/ui/inherent-impls-overlap-check/auxiliary/repeat.rs b/src/test/ui/inherent-impls-overlap-check/auxiliary/repeat.rs new file mode 100644 index 00000000000..42ed5d19deb --- /dev/null +++ b/src/test/ui/inherent-impls-overlap-check/auxiliary/repeat.rs @@ -0,0 +1,54 @@ +// force-host +// no-prefer-dynamic + +#![crate_type = "proc-macro"] + +extern crate proc_macro; +use proc_macro::{Ident, Group, TokenStream, TokenTree as Tt}; + +// This constant has to be above the ALLOCATING_ALGO_THRESHOLD +// constant in inherent_impls_overlap.rs +const REPEAT_COUNT: u32 = 501; + +#[proc_macro] +/// Repeats the input many times, while replacing idents +/// named "IDENT" with "id_$v", where v is a counter. +pub fn repeat_with_idents(input: TokenStream) -> TokenStream { + let mut res = Vec::new(); + fn visit_stream(res: &mut Vec<Tt>, stream :TokenStream, v: u32) { + let mut stream_iter = stream.into_iter(); + while let Some(tt) = stream_iter.next() { + match tt { + Tt::Group(group) => { + let tt = Tt::Group(visit_group(group, v)); + res.push(tt); + }, + Tt::Ident(id) => { + let id = if &id.to_string() == "IDENT" { + Ident::new(&format!("id_{}", v), id.span()) + } else { + id + }; + res.push(Tt::Ident(id)); + }, + Tt::Punct(p) => { + res.push(Tt::Punct(p)); + }, + Tt::Literal(lit) => { + res.push(Tt::Literal(lit)); + }, + } + } + } + fn visit_group(group :Group, v: u32) -> Group { + let mut res = Vec::new(); + visit_stream(&mut res, group.stream(), v); + let stream = res.into_iter().collect(); + let delim = group.delimiter(); + Group::new(delim, stream) + } + for v in 0 .. REPEAT_COUNT { + visit_stream(&mut res, input.clone(), v) + } + res.into_iter().collect() +} diff --git a/src/test/ui/inherent-impls-overlap-check/no-overlap.rs b/src/test/ui/inherent-impls-overlap-check/no-overlap.rs new file mode 100644 index 00000000000..341bfc7b605 --- /dev/null +++ b/src/test/ui/inherent-impls-overlap-check/no-overlap.rs @@ -0,0 +1,34 @@ +// run-pass +// aux-build:repeat.rs + +// This tests the allocating algo branch of the +// inherent impls overlap checker. +// This branch was added by PR: +// https://github.com/rust-lang/rust/pull/78317 +// In this test, we repeat many impl blocks +// to trigger the allocating branch. + +#![allow(unused)] + +extern crate repeat; + +// Simple case where each impl block is distinct + +struct Foo {} + +repeat::repeat_with_idents!(impl Foo { fn IDENT() {} }); + +// There are overlapping impl blocks but due to generics, +// they may overlap. + +struct Bar<T>(T); + +struct A; +struct B; + +repeat::repeat_with_idents!(impl Bar<A> { fn IDENT() {} }); + +impl Bar<A> { fn foo() {} } +impl Bar<B> { fn foo() {} } + +fn main() {} diff --git a/src/test/ui/inherent-impls-overlap-check/overlap.rs b/src/test/ui/inherent-impls-overlap-check/overlap.rs new file mode 100644 index 00000000000..6f2801197e9 --- /dev/null +++ b/src/test/ui/inherent-impls-overlap-check/overlap.rs @@ -0,0 +1,71 @@ +// aux-build:repeat.rs + +#![allow(unused)] + +// This tests the allocating algo branch of the +// inherent impls overlap checker. +// This branch was added by PR: +// https://github.com/rust-lang/rust/pull/78317 +// In this test, we repeat many impl blocks +// to trigger the allocating branch. + +// Simple overlap + +extern crate repeat; + +struct Foo {} + +repeat::repeat_with_idents!(impl Foo { fn IDENT() {} }); + +impl Foo { fn hello() {} } //~ERROR duplicate definitions with name `hello` +impl Foo { fn hello() {} } + +// Transitive overlap + +struct Foo2 {} + +repeat::repeat_with_idents!(impl Foo2 { fn IDENT() {} }); + +impl Foo2 { + fn bar() {} + fn hello2() {} //~ERROR duplicate definitions with name `hello2` +} + +impl Foo2 { + fn baz() {} + fn hello2() {} +} + +// Slightly stronger transitive overlap + +struct Foo3 {} + +repeat::repeat_with_idents!(impl Foo3 { fn IDENT() {} }); + +impl Foo3 { + fn bar() {} //~ERROR duplicate definitions with name `bar` + fn hello3() {} //~ERROR duplicate definitions with name `hello3` +} + +impl Foo3 { + fn bar() {} + fn hello3() {} +} + +// Generic overlap + +struct Bar<T>(T); + +struct A; +struct B; + +repeat::repeat_with_idents!(impl Bar<A> { fn IDENT() {} }); + +impl Bar<A> { fn foo() {} fn bar2() {} } +impl Bar<B> { + fn foo() {} + fn bar2() {} //~ERROR duplicate definitions with name `bar2` +} +impl Bar<B> { fn bar2() {} } + +fn main() {} diff --git a/src/test/ui/inherent-impls-overlap-check/overlap.stderr b/src/test/ui/inherent-impls-overlap-check/overlap.stderr new file mode 100644 index 00000000000..3dd2793712f --- /dev/null +++ b/src/test/ui/inherent-impls-overlap-check/overlap.stderr @@ -0,0 +1,47 @@ +error[E0592]: duplicate definitions with name `hello` + --> $DIR/overlap.rs:20:12 + | +LL | impl Foo { fn hello() {} } + | ^^^^^^^^^^ duplicate definitions for `hello` +LL | impl Foo { fn hello() {} } + | ---------- other definition for `hello` + +error[E0592]: duplicate definitions with name `hello2` + --> $DIR/overlap.rs:31:5 + | +LL | fn hello2() {} + | ^^^^^^^^^^^ duplicate definitions for `hello2` +... +LL | fn hello2() {} + | ----------- other definition for `hello2` + +error[E0592]: duplicate definitions with name `bar` + --> $DIR/overlap.rs:46:5 + | +LL | fn bar() {} + | ^^^^^^^^ duplicate definitions for `bar` +... +LL | fn bar() {} + | -------- other definition for `bar` + +error[E0592]: duplicate definitions with name `hello3` + --> $DIR/overlap.rs:47:5 + | +LL | fn hello3() {} + | ^^^^^^^^^^^ duplicate definitions for `hello3` +... +LL | fn hello3() {} + | ----------- other definition for `hello3` + +error[E0592]: duplicate definitions with name `bar2` + --> $DIR/overlap.rs:67:5 + | +LL | fn bar2() {} + | ^^^^^^^^^ duplicate definitions for `bar2` +LL | } +LL | impl Bar<B> { fn bar2() {} } + | --------- other definition for `bar2` + +error: aborting due to 5 previous errors + +For more information about this error, try `rustc --explain E0592`. |