Compiler detects conflicting implementations of a trait where there are none

[QuaternionsRock]

Stable 1.59.0 and nightly 2022-03-06 have shown no differences in this issue in my testing.

I seem to have discovered a situation where the compiler claims there are two conflicting implementations of a trait when the bounds don't actually intersect? Type theory can be tricky, so it's possible this behavior is actually correct.

Minimum Reproducible Example: (playground)

// Extracts the element type of an arbitrarily nested array (or a scalar)
trait NDArrayType<T> {}

// Identity case: Every T is a 0D array (a scalar) of type T.
impl<T> NDArrayType<T> for T {}

// Array case: Every [U; N] is a >=1D array of type T.
// The previous impl allows U to be a 0D array of type T.
// This impl allows U to be a >=1D array of type T.
impl<T, U: NDArrayType<T>, const N: usize> NDArrayType<T> for [U; N] {}

Compiler Error:

error[E0119]: conflicting implementations of trait `NDArrayType<[_; _]>` for type `[_; _]`
  --> src/lib.rs:10:1
   |
5  | impl<T> NDArrayType<T> for T {}
   | ---------------------------- first implementation here
...
10 | impl<T, U: NDArrayType<T>, const N: usize> NDArrayType<T> for [U; N] {}
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `[_; _]`

For more information about this error, try `rustc --explain E0119`.

The best way I can think of to demonstrate this is incorrect is a simple brute-force replacement of the first implementation with concrete types, which compiles just fine, even for scalar types that are arrays themselves (which was the stated cause of the previous compiler error):

// Extracts the element type of an arbitrarily nested array (or a scalar)
trait NDArrayType<T> {}

// Identity cases:
// Two arbitrary types to implement
type T0 = i32;
type T1 = u64;
// T0 and T1 are scalars of themselves.
impl NDArrayType<T0> for T0 {}
impl NDArrayType<T1> for T1 {}
// [T0; N] and [T1; N] are scalars of themselves.
impl<const N: usize> NDArrayType<[T0; N]> for [T0; N] {}
impl<const N: usize> NDArrayType<[T1; N]> for [T1; N] {}
// [[T0; M]; N] and [[T1; M]; N] are scalars of themselves.
impl<const N: usize, const M: usize> NDArrayType<[[T0; M]; N]> for [[T0; M]; N] {}
impl<const N: usize, const M: usize> NDArrayType<[[T1; M]; N]> for [[T1; M]; N] {}

// Array case: Every [U; N] is a >=1D array of type T.
// The previous impl allows U to be a 0D array of type T.
// This impl allows U to be a >=1D array of type T.
impl<T, U: NDArrayType<T>, const N: usize> NDArrayType<T> for [U; N] {}

[plazmoid]

They are actually intersect.

impl<T> NDArrayType<T> for T {}

Type T could be any type that presented in rust, i.e. [U; 1] or (). Lack of const-genericness in impl block doesn't mean that the trait wouldn't be implemented for arrays.

Try it yourself:

trait Trait<T> {
    fn do_stuff(&self) {}
}

impl<T> Trait<T> for T {}

fn main() {
    [1,2,3].do_stuff(); // this method works, so all [U; N] types are already covered
    ().do_stuff();
}

[QuaternionsRock]

@plazmoid that is actually by design. As I tried to demonstrate in the "brute force" example, NDArrayType<[T; N]> is supposed to be implemented for [T; N] in this way. As an example, the following traits should be implemented for every type [[T; M]; N]:

• NDArrayType<[[T; M]; N]> (by the first impl), because [[T; M]; N] is technically a scalar (0D array) of itself in the sense that [[[T; M]; N]; O] is a 1D array of type [[T; M]; N].
• NDArrayType<[T; M]> (by the second impl), because it is implemented for [T; M] by the first impl. Again, this is correct because [[T; M]; N] is a 1D array of type [T; M].
• NDArrayType<T> (again by the second impl), because it is implemented for [T; M] by the second impl, which does so because NDArrayType<T> is implemented for T by the first impl. After all, [[T; M]; N] is a 2D array of T.

The intersection you are alluding to would only be possible if the any of the of the NDArray types are not dependent on the type being implemented, e.g. impl<T, U> NDArrayType<T> for U, which would allow it to conflict with the second impl's implementation of NDarrayType<T> for [T; N].

[QuaternionsRock]

Going back to the example -

If I had to guess, I would say that the type relationship of the identity impl is not being properly evaluated by compiler when it tries to deduce the bounds of U in the array impl. I would expect it to see that there is an impl<T> NDArrayType<T> and take that to mean that every type implements NDArrayType<T>, which makes it no different from impl<T, U> NDArrayType<T> for U.

Also, its worth noting that this has nothing to do with the presence of const generics. The following example produces a compiler error for the exact same reason as the first example on stable as well as nightly: (playground)

// Extracts the value type of an arbitrarily nested tuple
trait NestedTupleType<T> {}

// Identity case: Every T is the innermost type of a nested tuple of type T.

// Examples:
// i32 is a 0-deep nested tuple of value type i32
// (i32,) is a 0-deep nested tuple of value type (i32,)
// ((i32,),) is a 0-deep nested tuple of value type ((i32,),)
// (((i32,),),) is a 0-deep nested tuple of value type (((i32,),),)
// etc.

impl<T> NestedTupleType<T> for T {}

// Nested case: Every (U,) is a >=1D array of type T.
// In other words, (U,) must be one of (T,); ((T,),); (((T,),),); etc.

// Examples:
//
// (i32,) is a 1-deep nested tuple of value type i32
//
// ((i32,),) is 1-deep nested tuple of value type (i32,)
// ((i32,),) is also a 2-deep nested tuple of value type i32
//
// (((i32,),),) is a 1-deep nested tuple of value type ((i32,),)
// (((i32,),),) is also a 2-deep nested tuple of value type (i32,)
// (((i32,),),) is *also* a 3-deep nested tuple of value type i32
//
// etc.

impl<T, U: NestedTupleType<T>> NestedTupleType<T> for (U,) {}

[jackh726]

Let's look at this a bit.

For the second impl, let's simplify to N=1. So, we have

impl<X> NDArrayType<X> for X {}
impl<T, U: NDArrayType<T>> NDArrayType<T> for [U; 1] {}

Now, we have to find some substs where these impls overlap. So, they overlap when X == [U; 1] and X == T. In theory, this only really matters in the case where both apply, so T == [U; 1]. Next, we need to verify that the bounds on all impls can hold under these substs, so U: NDArrayType<[U; 1]>. If we have some type A, then in theory there could be an impl NDArrayType<[A; 1]> for A {}. Now we can set U = A, and we have overlapping impls.

impl<[A; 1]> NDArrayType<[A; 1]> for [A; 1] {}
impl<[A; 1], A: NDArrayType<[A; 1]>> NDArrayType<[A; 1]> for [A; 1] {}

Of course, this only is okay if our new impl is okay. You can work through this a bit, but it is.

Now, to simplify a bit, I don't think the coherence algorithm is quite this "complete"; but, as you see, they do overlap.

I'm going to close this. Feel free to reopen if it seems like I've missed something.

[QuaternionsRock]

@jackh726, I gave some thought to that explanation as well. I understand what you're saying about the global requirements of the generic impl, but nonetheless I feel it may be worthy of being considered a bug. Above all else, it is definitely inconsistent behavior: whether or not it will compile depends only on the identity impl being concrete or generic. I tried to demonstrate this in the second example: replacing the generic impl with any number of concrete impls will compile without issue, despite "overlapping" in much the same way. Take the impl of NDArrayType<[i32, N]> for [i32; N] defined there. Substituting this impl into your explanation, it says:

For the second impl, let's simplify to N=1. So, we have

impl/*<[i32; 1]>*/ NDArrayType<[i32; 1]> for [i32; 1] {}
impl<T, U: NDArrayType<T>> NDArrayType<T> for [U; 1] {}

Now, we have to find some substs where these impls overlap. So, they overlap when [i32; 1] == [U; 1] and [i32; 1] == T. In theory, this only really matters in the case where both apply, so T == [U; 1]. Next, we need to verify that the bounds on all impls can hold under these substs, so U: NDArrayType<[U; 1]>. If we have some type i32, then in theory there could be an impl NDArrayType<[i32; 1]> for i32 {}. Now we can set U = i32, and we have overlapping impls.

impl/*<[i32; 1]>*/ NDArrayType<[i32; 1]> for [i32; 1] {}
impl<[i32; 1], i32: NDArrayType<[i32; 1]>> NDArrayType<[i32; 1]> for [i32; 1] {}

If it were truly any safer, I would be okay with it, but the reality is that it's just as easy to break: all it takes is an impl NDArrayType<[i32; 1]> for i32 {} somewhere for everything to come crashing down.

[QuaternionsRock]

Yeah, I'm going to have to ask that you reopen this issue, @jackh726 (I cannot do so myself). At the end of the day, we are discussing a trait implementation conflict that is contingent upon another impl that doesn't exist. Perhaps the majority will agree with your stance, but I personally cannot get myself to agree this is not a bug.

[jackh726]

Above all else, it is definitely inconsistent behavior: whether or not it will compile depends only on the identity impl being concrete or generic.

This isn't inconsistent behavior. The impl over all T includes downstream types as well. The concrete impls do not. They are not the same.

Take the impl of NDArrayType<[i32, N]> for [i32; N] defined there.

Again, these aren't the same. In this case because of the orphan rule. Because i32 is defined upstream and NDArrayType is defined in the current crate, no new impl can ever exist. So, these two impls cannot overlap.

If it were truly any safer, I would be okay with it, but the reality is that it's just as easy to break: all it takes is an impl NDArrayType<[i32; 1]> for i32 {} somewhere for everything to come crashing down.

Yes; if you add that impl it will break. But downstream crates can't add it.

At the end of the day, we are discussing a trait implementation conflict that is contingent upon another impl that doesn't exist.

This is how Rust works. The coherence and orphan rules work together to ensure only one impl can exist for a trait with given substs for a given type. When a downstream crate can write new types and impls that could cause two impls to overlap, that isn't allowed.

Perhaps the majority will agree with your stance, but I personally cannot get myself to agree this is not a bug.

There isn't an "agreement" here. For this issue to be reopened, you need to show one of a few things: 1) The logic I used to show that you can make a downstream type that causes overlapping impls in wrong. 2) In your concrete case, there is also a downstream impl that can be added that will cause overlapping impls. With a test please.

[QuaternionsRock]

@jackh726 I'm starting to understand what you're saying now, thank you for that explanation. So, if my understanding is now correct, if the coherence algorithm were smarter, this would be considered acceptable? All the more reason to properly implement sealed traits, I suppose.

[jackh726]

I think that still runs into the same problems. You've implemented NDArrayTypeBase for all T (even downstream types). So downstream crates can still impl NDArrayType