Associated types are ambiguous to impl coherence

help
1

Hi everyone,

Have anyone ever encountered an apparent limitation of the trait solver, where impl coherence check fails due to use of associated types?

Consider the following code:

use std::ops::{Add, Mul};

pub struct Generic<A>(A);

impl<A, B> Mul<Generic<B>> for Generic<A>
where
    A: Add<B>,
{
    type Output = Generic<<A as Add<B>>::Output>;

    fn mul(self, rhs: Generic<B>) -> Self::Output {
        Generic(self.0.add(rhs.0))
    }
}

type A = <Generic<i32> as Mul<Generic<i32>>>::Output;
type B = <Generic<u32> as Mul<Generic<u32>>>::Output;

trait Trait {}

impl Trait for A {}

impl Trait for B {}

My understanding is that associated types are essentially type-level functions. They map some type to an another type. In context where all the inputs are known the output can be computed.
In the case above, both the receiver and the generic parameter of the trait are known, so the fully-qualified type alias is not ambiguous in any way, and as such compiler can determine the exact concrete type to which it resolves (Generic<i32> and Generic<u32> in the example). Yet still, this code fails to compile with rather unhelpful error message:

error[E0119]: conflicting implementations of trait `Trait` for type `<Generic<i32> as Mul>::Output`
  --> src/mini.rs:23:1
   |
21 | impl Trait for A {}
   | ---------------- first implementation here
22 |
23 | impl Trait for B {}
   | ^^^^^^^^^^^^^^^^ conflicting implementation for `<Generic<i32> as Mul>::Output`

playgound

Am I assuming something about associated type semantics that is not entirely correct here or is this a bug or some sort of limitation? I been having tough time finding any online discussion regarding that specific issue, the closest I've got was #99940, which does not match my problem description exactly.

I've been stomped by this for few weeks now and would really appreciate some help with understanding whats going on.

Edit:

I've posted a bug report on rust's repo, you can find it here.

2

Yup, this is well known. T: Iterator<Item = i32> and T: Iterator<Item = u32> are disjoint, but the compiler doesn't let you take advantage of that fact today.

3

Right, I'm familiar with the notion of impls disjoint on associated types. However, this usually refers to a case of two generic impls falsely overlapping. On the contrary my case its as simple as "looking up" what type aliases resolve to which seems like a slightly different problem - no actual constraint solving required.

4

I think it's issue 51445, with a bit of indirection. Your aliases can be rewritten/partially normalized as

type A = Generic<<i32 as Add<i32>>::Output>;
type B = Generic<<u32 as Add<u32>>::Output>;

(which also fails), so it can still be an "associated type from foreign impl considered to overlap with any other type" situation.

1 Like
5

I agree with @quinedot. The code compiles once at least one of the following is true:

  • Change core::ops::Add to a trait in the same crate
  • Change i32 and u32 to types in the same crate

This compiles:

use core::ops::{Add, Mul};
pub struct Generic<A>(A);
pub struct Foo;
pub struct Bar;
impl Add<Self> for Foo {
    type Output = Self;
    fn add(self, _: Self) -> Self::Output {
        self
    }
}
impl Add<Self> for Bar {
    type Output = Self;
    fn add(self, _: Self) -> Self::Output {
        self
    }
}
impl<A, B> Mul<Generic<B>> for Generic<A>
where
    A: Add<B>,
{
    type Output = Generic<<A as Add<B>>::Output>;

    fn mul(self, rhs: Generic<B>) -> Self::Output {
        Generic(self.0.add(rhs.0))
    }
}
type A = <Generic<Foo> as Mul<Generic<Foo>>>::Output;
type B = <Generic<Bar> as Mul<Generic<Bar>>>::Output;
trait Trait {}
impl Trait for A {}
impl Trait for B {}

So does this:

use core::ops::Mul;
pub struct Generic<A>(A);
pub trait Add<Rhs = Self> {
    type Output;
    fn add(self, rhs: Rhs) -> Self::Output;
}
impl Add<Self> for i32 {
    type Output = Self;
    fn add(self, _: Self) -> Self::Output {
        self
    }
}
impl Add<Self> for u32 {
    type Output = Self;
    fn add(self, _: Self) -> Self::Output {
        self
    }
}
impl<A, B> Mul<Generic<B>> for Generic<A>
where
    A: Add<B>,
{
    type Output = Generic<<A as Add<B>>::Output>;
    fn mul(self, rhs: Generic<B>) -> Self::Output {
        Generic(self.0.add(rhs.0))
    }
}
type A = <Generic<i32> as Mul<Generic<i32>>>::Output;
type B = <Generic<u32> as Mul<Generic<u32>>>::Output;
trait Trait {}
impl Trait for A {}
impl Trait for B {}
1 Like
6

Oh I see, so it is indeed the issue of external / traits I didn't notice that.
I've originally encountered this issue while trying to extend uom to support algebraic operations on si unit types (multiplication and division) instead of having to create nominal types for each quantity.

Its an extension of the typing scheme used by Quantities in uom, to unit types. I've been using typenum to represent the unit's dimensions in terms of base units and got the same error there, which with typenum being an external crate now makes sense. In this minimised example here I used both external trait and types by an accident.

I've got to see if its possible to somehow still use the typenum's counters with std's Add / Sub.

Thank you all so much for help!