Why doesn't the user-defined type encounter the "upstream may add new impl" diagnostic

Consider this example

struct Wrap<T>(T);
trait IntoBytes<T>{
    fn bytes(self)->Vec<u8>;
}

impl<T:Into<Vec<u8>>> IntoBytes<T> for T{
    fn bytes(self)->Vec<u8>{
        self.into()
    }
}

impl<T:IntoBytes<U>,U> IntoBytes<U> for Wrap<T>{
    fn bytes(self)->Vec<u8>{
        self.0.bytes()
    }
}

impl IntoBytes<&String> for Wrap<Wrap<&String>>{  // #2
    fn bytes(self)->Vec<u8>{
        self.0.0.to_owned().into_bytes()
    }
}

The compiler will report an error that

conflicting implementations of trait IntoBytes<&String> for type Wrap<Wrap<&String>>
upstream crates may add a new impl of trait std::convert::From<&std::string::String> for type std::vec::Vec<u8> in future versions

However, if I change the type &String to a customized type, such as struct SS;, it won't have that similar error, except that the compiler will report the conflicting error if impl From<SS> for Vec<u8>.

Is this caused by the compiler having a special treatment for the internal type?

What matters is that &String is a type made entirely of parts that already exist "upstream" (& is a language primitive and String is from std), which is not the case for any type you define in the same crate. If you define your struct SS in a crate that this crate depends on, you'd get the same error.

2 Likes

It's local types that have the special behavior.

It's not supposed to be a (major) breaking change to add non-blanket impl Traits for your local types; e.g. for std to

impl From<&String> for Vec<u8>

After which

&String: Into<Vec<u8>>                      // Foreign blanket impl
&String: IntoBytes<&String>                 // Your impl #0
Wrap<&String>: IntoBytes<&String>           // Your impl #1
Wrap<Wrap<&String>>: IntoBytes<&String>     // Your impl #1

So the compiler can't allow your impl #2, as it would cause a coherence error (overlapping implementations) should std make that change -- it makes adding that impl a major breaking change.

But with a local SS, you are in control of both the implementing type and the potentially conflicting blanket implementation, so the compiler lets you do it. It's a limited form of negative reasoning; usually negative reasoning isn't employed because it makes things too fragile (makes it a breaking change to implement new things), but negative reasoning is allowed within a single crate[1] where you control everything.

RFC 1023:

Furthermore, we limit the use of negative reasoning to obey the orphan rules. That is, just as a crate cannot define an impl Type: Trait unless Type or Trait is local, it cannot rely that Type: !Trait holds unless Type or Trait is local.

(More here.)

((RFC 1023 was amended by RFC 2451.))


  1. roughly speaking ↩︎

2 Likes

I see. I wonder how a compiler generally determines whether two implementations are conflicting. I suppose it is based on whether there are multiple available implementations for the same type, right? For example, in my #1 and #2 imp, they will both the valid implementation for Wrap<Wrap<&String>>(if &String:Into<Vec<u8>> is satisfied).

However, I used to see the compiler also reports an error that

multiple impls satisfying xxx

Specifically, consider this concrete example

struct Tuple<T,U>(T,U);
struct Searched;
struct Searching<Result>(Result);
trait Search<T, Result> {
   type TakeRemainder;
   fn take_out(self) -> (T, Self::TakeRemainder);
}

impl<First, Other> Search<First, Searched> for Tuple<First, Other>  // #00
{
    type TakeRemainder = Other;

    fn take_out(self) -> (First, Self::TakeRemainder) {
        (self.0, self.1)
    }
}

impl<T> Search<T,Searched> for (){
    type TakeRemainder = ();

    fn take_out(self) -> (T, Self::TakeRemainder) {
        todo!()
    }
}

impl<First, Other, T, Result> Search<T, Searching<Result>> for Tuple<First, Other> // #11
where
    Other: Search<T, Result>,
{
    type TakeRemainder = Tuple<First, Other::TakeRemainder>;

    fn take_out(self) -> (T, Self::TakeRemainder) {
        let (value, remainder) = self.1.take_out();
        (value, Tuple(self.0, remainder))
    }
 
}
fn main(){
    let t = Tuple(1f64,Tuple("abc",Tuple(2,Tuple(0u8,()))));
    let r:(i32,_) = t.take_out();  // #8
}

In this case both #00 and #11 are valid implementations for type Tuple<i32, Tuple<u8, ()>>, however, it does not report #00 and #11 are conflicting implementations, rather, the compiler says multiple impls satisfying Tuple<i32, Tuple<u8, ()>>: Search<i32, _> found at #8.

what is the difference between conflicting and multiple implementations?

I didn't see a write-up in the dev guide off-hand, but here could be a place to start exploring the implementation if you wanted to.

I didn't try to unravel that code, but it's not disallowing any implementations, like what happened in your OP. It couldn't tell which implementation applies; as far as it could tell, either of the two highlighted implementations could apply; it needs to know which one does apply.[1] Figuring out which applies is known as trait solving.

It's never the case that one type implements the same trait more than once.[2] That's known as coherence (and why the possibility of overlapping impls is rejected).

I haven't memorized every diagnostic output, but from this, probably "conflicting" is a coherence/orphan-rule violation, where as "multiple" is a trait solving ambiguity.

(The fact that either implementation might apply doesn't mean there's more than one implementation of the same trait for the type of t. The trait implemented can differ between the implementations due to the different types manifested in the generic parameters of the trait.)


  1. Maybe both do or maybe it just failed to figure out which one does. ↩︎

  2. modulo compiler bugs and some specialization-ish niche cases ↩︎

Seems that conflicting implementations refer to that there are multiple valid implementations for the same trait(after substituting all type parameters) for the same type, while multiple impls refer to that there are multiple implementations for the same type with different traits

trait Conflicting<T>{}
impl<T> Conflicting<T> for T{}  // #1
impl Conflicting<()> for (){}  // #2

#1 and #2 are conflicting since there are multiple valid implementations for type () with trait Conflicting<()>.

trait Multiple<T>{ fn call(self){}}
impl<T> Multiple<T> for T{}
impl Multiple<i32> for (){}

In this case, there can exist multiple implementations for the type (), however, the implementations are for different traits, one is Multiple<()> and another is Multiple<i32>, so, they are not conflicting but they can cause ambiguous () using call.

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.