Failed to specialize `impl for Associated::Type` with `impl for Concrete`

help
#1

[playground]

pub trait IntoOwner<Borrowed, Owner>: Sized + Borrow<Borrowed>
where
    Borrowed: ?Sized,
    Owner: Borrow<Borrowed>,
{
    fn into_owner(self) -> Owner;
}

// e.g. into_owner(&T) -> T::Owned
impl<Borrower, Borrowed> IntoOwner<Borrowed, Borrowed::Owned> for Borrower
where
    Borrower: Borrow<Borrowed>,
    Borrowed: ?Sized + ToOwned,
{
    default fn into_owner(self) -> Borrowed::Owned {
        self.borrow().to_owned()
    }
}

// e.g. into_owner(String) -> String
impl<Borrowed> IntoOwner<Borrowed, Borrowed::Owned> for Borrowed::Owned
where
    Borrowed: ?Sized + ToOwned,
{
    default fn into_owner(self) -> Borrowed::Owned {
        self
    }
}

// specializes `for Borrowed::Owned`?
impl<Borrowed> IntoOwner<Borrowed, Borrowed::Owned> for Cow<'_, Borrowed>
where
    Borrowed: ?Sized + ToOwned,
{
    fn into_owner(self) -> Borrowed::Owned {
        self.into_owned()
    }
}

error[E0119]: conflicting implementations of trait `IntoOwner<_, _>` for type `std::borrow::Cow<'_, _>`
  --> src/lib.rs:36:1
   |
26 | impl<Borrowed> IntoOwner<Borrowed, Borrowed::Owned> for Borrowed::Owned
   | ----------------------------------------------------------------------- first implementation here
...
36 | impl<Borrowed> IntoOwner<Borrowed, Borrowed::Owned> for Cow<'_, Borrowed>
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `std::borrow::Cow<'_, _>`

Is there a real conflict here that I'm overlooking, or is this just a limitation of the currently incomplete #![feature(specialization)]? It feels like the impl ... for Cow should be more specific than the impl<Borrowed> ... for Borrowed::Owned.

Also I'm pretty sure that the type which both impls would apply to is impossible to define, as it would require a recursive, infinitely sized Cow<'_, X> to have X: ToOwned<Owned=Cow<X>>.

#2

Your question seems contradictory. In order for the implementations to be okay, they must either not overlap, or one must be more specific than the other.

Here you argue that one is more specific than the other

Here you argue that they don’t overlap

Given that something like Borrowed = &'static () makes

  • the impl ... for Cow impl apply and instantiate to impl IntoOwner<&'static (), ()> for Cow<'_, ()>
  • this is instantiation is not a case of the impl<Borrowed> ... for Borrowed::Owned because this would require
    • the “Borrowed” types of both impls to be the same, &'static (), since they’re both the first type argument to IntoOwner
    • but <&'static ()>::ToOwned == (), and () is different from Cow<'_, ()>

Hence the two implementations are required to be overlap-free, since one is not more specific than the other.

In order for the two impls to overlap

  • the “Borrowed” types of both impls have to be the same because they both appear as the first type argument to IntoOwner
  • we need Borrowed::Owned == Cow<'_, Borrowed> for the Self type to be the same

so we’d need some type Foo = Borrowed and lifetime 'a = '_ such that

  • Foo: ToOwned<Owned = Cow<'a, Foo>>

In this case, I agree that you will, in practice, alway get a overflow evaluating the requirement Cow<'static, Foo>: Sized error, since the type Cow<'a, Foo> will contain a Owned(Foo::ToOwned) variant, i.e. Owned(Cow<'a, Foo>).

Arguably, one could imagine a future where that’s not the case though. If Foo is uninhabited. (E.g. enum Foo {}.) and the compiler was able to accept types such as struct Foo(Foo); because they can be zero-sized despite the infinite recursion, and the enum layout optimizations were guaranteed to make

pub enum Cow<'a, B> 
where
    B: 'a + ToOwned + ?Sized, 
 {
    Borrowed(&'a B),
    Owned(<B as ToOwned>::Owned),
}

for uninhabited enum Foo {} skip the first variant entirely, then Cow<'static, Foo> could be allowed, I believe.

IMO it’s thus a good thing that Rust does not figure out instances are non-overlapping merely based on the practicalities of current rules about what kinds of types can or cannot be layed out without requiring infinite size, because this allows future changes to these rules (i.e. changing the rules to allow more types to be “valid”).

2 Likes
#3

+1, I was going to write exactly the same. The fact that a type isn't representable in memory is a very fragile property, and a low-level implementation detail. Deciding impl overlaps based on such low-level details would be a highly leaky abstraction, and it would be surprising to get errors because the compiler got smarter and gained the ability to materialize previously "impossible" types (I'm specifically thinking about by-value unsized types).

#4

In order to express what you want you'd need to use something which specialization doesn't allow yet:

  1. given A and B which may overlap but with each not being a subset of the other,
  2. if you were able to express with traits the region C of their overlap,
  3. then you could specialize each of A and B with an impl for C.

This would be unambiguous, and in your case, would require adding a last impl for that in-practice-currently-unreachable case:

impl<'lt, Borrowed : ?Sized>
    IntoOwner<Borrowed, Borrowed::Owned>
for
    Borrowed::Owned /* = Cow<'lt, Borrowed> */
where
    Cow<'lt, Borrowed> : Sized, // <- likely unreachable, but w/e
    Borrowed : ToOwned<Owned = Cow<'lt, Borrowed>>,
{
    fn into_owner(self) -> Borrowed::Owned {
        self
    }
}

But this is not supported by specialization yet.

1 Like
#5

This is what I hadn't internalized yet; I was presuming that C being well-formed would mean that the overlap of a not-further-specializable impl could already be said to specialize the specializable impl.

Requiring the program author to explicitly resolve the overlap with an always applicable C is reasonable, though. (Ideally, once this is possible, the compiler could give a hint to resolve the conflict by further specializing the overlap.)

1 Like