Recursive trait bounds not working as expected

I would expect the following to work:


struct A{}
struct B{}
struct C{}

pub trait SmallestUpgrade<T> {
    type LCM;
    fn upgrade(self) -> Self::LCM;
}

impl<T, U> SmallestUpgrade<T> for U
where
    T: SmallestUpgrade<U, LCM = U>,
{
    type LCM = U;
    fn upgrade(self) -> Self::LCM {
        self
    }
}

impl SmallestUpgrade<A> for B{
    type LCM=C;
    fn upgrade(self)->Self::LCM{
        C{}
    }
}

impl SmallestUpgrade<B> for A{
    type LCM=C;
    fn upgrade(self)->Self::LCM{
        C{}
    }
}

fn main() {

    
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0275]: overflow evaluating the requirement `B: SmallestUpgrade<A>`
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`playground`)
note: required for `A` to implement `SmallestUpgrade<B>`
  --> src/main.rs:11:12
   |
11 | impl<T, U> SmallestUpgrade<T> for U
   |            ^^^^^^^^^^^^^^^^^^     ^
12 | where
13 |     T: SmallestUpgrade<U, LCM = U>,
   |                           ------- unsatisfied trait bound introduced here
   = note: 126 redundant requirements hidden
   = note: required for `A` to implement `SmallestUpgrade<B>`

For more information about this error, try `rustc --explain E0275`.
error: could not compile `playground` (bin "playground") due to previous error

Any Idea if this is normal?

The new trait solver at least does not recurse but still considers these conflicting implementations:

error[E0119]: conflicting implementations of trait `SmallestUpgrade<A>` for type `B`
  --> src/main.rs:20:1
   |
10 | / impl<T, U> SmallestUpgrade<T> for U
11 | | where
12 | |     T: SmallestUpgrade<U, LCM = U>,
   | |___________________________________- first implementation here
...
20 |   impl SmallestUpgrade<A> for B {
   |   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `B`

error[E0119]: conflicting implementations of trait `SmallestUpgrade<B>` for type `A`
  --> src/main.rs:27:1
   |
10 | / impl<T, U> SmallestUpgrade<T> for U
11 | | where
12 | |     T: SmallestUpgrade<U, LCM = U>,
   | |___________________________________- first implementation here
...
27 |   impl SmallestUpgrade<B> for A {
   |   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `A`

I don't have time to explore in this moment, but it's probably normal and is perhaps something to do with coinduction. See here if you want to check my first impression guess on your own.

Well if I change the associated type to a type parameter it actually compiles. I don't see why the same isn't true for the associated type. I'm not so sure it has to do with coinduction

See here: Rust Playground

The conflict for a trait with an associated type but not a generic is to be expected: playground

If you could implement both Add<B, Output = Foo> for A and Add<B, Output = Bar> for A, how would the compiler know which to choose for a + b?

I really like the concept of implementation bounded by associated type, and I'm guessing there'll be a neat answer here, but I'm not following the purpose of this implementation. The bounds restrict it some, but it really just makes a U able to upgrade() into itself. Sort of a long way to go to get From<T> for T.

I suppose intended as a fallback for if no type given for the upgrade/LCM path? It seems like you're trying to encode how types combine/broadcast between themselves. If you know all the internal matches that will be implemented, you can "hide" them by naming them all [playground]

The idea is to have some sort of least common multiple for types. A bit more generic than from. For example the LCM for an f64 and an Complex<i8> is neither type, but is Complex<f64>. The generic impl is to cover the case where I have impl SmallestUpgrade<Complex<f64>> for f64, which does the conversion to Complex<f64>. If such an implementation exists, then the reverse should just be what I've written generically: The smallest upgrade between complex and float, for complex, given that I can upgrade one to the other, must just be complex, I.e. self.

Is this what you're after? [playground]

It gives the basic no-op case as a blanket implementation:

impl<U> Common<U> for U {
    type LCM = Self;
    
    fn upgrade(self) -> Self::LCM { self }
}

No I was trying to find a wider blanket impl! I was trying to avoid as much code repetition, and the trait bounds I tried to set are wider and contain more meaning than just implementing on identical pairs.

So there are multiple 'ranks' and multiple possible equivalent types within a rank? What about adding a second trait denoting equivalency to allow you to implement for different A/B types while still requiring a common associated type bound? Something like:

trait Equivalent<B> {
    type Preferred;
    fn as_equivalent(self) -> Self::Preferred;
}

impl<A, B> Common<B> for A
where
    A: Equivalent<B, Preferred = A>,
{
    todo!()
}

Actually I am still confused. My trait should only ever conflict if I implement smallestUpgrade<A> for B and set the LCM=A. In my case I implement a different associated type, so the blanket implementation shouldn't actually implement anything, because no types satisfy the trait bound.

How does this help, it seems like a very similar trait just de-duped? Can you give me an example with Complex<i32> and f64?

I believe this is the relevant issue: Can't write non-overlapping blanket impls that involve associated type bindings · Issue #20400 · rust-lang/rust · GitHub

The compiler just doesn't consider associated types when checking for conflicting implementations. It may in the future, but I don't know when. Just looking at the issue, it doesn't seem like there's been any progress since it was created in 2015, but maybe there's someone working on it.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.