Incorrect expected type for associated type with `specialization`

[justinlovinger]

The following code:

#![feature(specialization)]

#[derive(Clone, Copy, Debug)]
struct Cons<Item, Tail>(pub Item, pub Tail);

#[derive(Clone, Copy, Debug)]
struct Nil;

trait GetInternal<Item> {
    type Item;

    fn get(self) -> Self::Item;
}

impl<Item, Other, Tail> GetInternal<Item> for Cons<Other, Tail>
where
    Tail: GetInternal<Item>,
{
    default type Item = Tail::Item;

    fn get(self) -> Self::Item {
        self.1.get()
    }
}

Results in the following error:

   Compiling playground v0.0.1 (/playground)
warning: the feature `specialization` is incomplete and may not be safe to use and/or cause compiler crashes
 --> src/lib.rs:1:12
  |
1 | #![feature(specialization)]
  |            ^^^^^^^^^^^^^^
  |
  = note: see issue #31844 <https://github.com/rust-lang/rust/issues/31844> for more information
  = help: consider using `min_specialization` instead, which is more stable and complete
  = note: `#[warn(incomplete_features)]` on by default

error[E0308]: mismatched types
  --> src/lib.rs:22:9
   |
15 | impl<Item, Other, Tail> GetInternal<Item> for Cons<Other, Tail>
   |                   ---- found this type parameter
...
21 |     fn get(self) -> Self::Item {
   |                     ---------- expected `<Cons<Other, Tail> as GetInternal<Item>>::Item` because of return type
22 |         self.1.get()
   |         ^^^^^^^^^^^^ expected `Cons<Other, Tail>`, found type parameter `Tail`
   |
   = note: expected associated type `<Cons<Other, Tail> as GetInternal<Item>>::Item`
              found associated type `<Tail as GetInternal<Item>>::Item`
   = note: an associated type was expected, but a different one was found

For more information about this error, try `rustc --explain E0308`.
warning: `playground` (lib) generated 1 warning
error: could not compile `playground` (lib) due to 1 previous error; 1 warning emitted

However, the expected associated type should be <Tail as GetInternal<Item>>::Item, not <Cons<Other, Tail> as GetInternal<Item>>::Item. The error disappears if specialization is removed.

The error occurs with min_specialization as well, but min_specialization also gives an error about trying to specialize an associated type, so I assume min_specialization is not supposed to support specializing associated types.

P.S. This example was pared down from a larger example, so the reason for specialization is no longer present.

Meta

rustc --version --verbose:

rustc 1.84.0-nightly (59cec72a5 2024-11-08)
binary: rustc
commit-hash: 59cec72a57af178767a7b8e7f624b06cc50f1087
commit-date: 2024-11-08
host: x86_64-unknown-linux-gnu
release: 1.84.0-nightly
LLVM version: 19.1.3

[compiler-errors]

This is not a bug. You marked the associated type as default, so it may be specialized, and thus the compiler must treat is as-if it cannot normalize <Cons<Other, Tail> as GetInternal<Item>>::Item (i.e. Self::Item) to Tail::Item.

[justinlovinger]

This is not a bug. You marked the associated type as default, so it may be specialized, and thus the compiler must treat is as-if it cannot normalize <Cons<Other, Tail> as GetInternal<Item>>::Item (i.e. Self::Item) to Tail::Item.

Self::Item is not <Cons<Other, Tail> as GetInternal<Item>>::Item. Self::Item is Tail::Item.

[compiler-errors]

Self::Item is by definition <Cons<Other, Tail> as GetInternal<Item>>::Item until it is finalized, i.e. until it is specialized by an implementation that provides a non-default type Item, or until we know for certain that such an implementation may not exist.

[justinlovinger]

The trait is private, so we should already know all the implementations for certain.

[compiler-errors]

Neither specialization nor coherence for that matter use privacy to prove that things cannot conflict.

Frankly, I don't think you've actually showed why you need specialization in this case. If you have a specializing implementation in your crate, and that implementation provides a different type for type Item, then this code is unsound. If you don't have a specializing implementation, then why have you marked your type Item as default?

[justinlovinger]

As noted in the opening post, the example was pared down. Here is the full example:

#![feature(specialization)]

#[derive(Clone, Copy, Debug)]
struct Cons<Item, Tail>(pub Item, pub Tail);

#[derive(Clone, Copy, Debug)]
struct Nil;

pub trait Get<Item> {
    fn get(self) -> Item;
}

impl<Item, L> Get<Item> for L
where
    L: GetInternal<Item, Item = Item>,
{
    fn get(self) -> Item {
        GetInternal::get(self)
    }
}

trait GetInternal<Item> {
    type Item;

    fn get(self) -> Self::Item;
}

impl<Item, Tail> GetInternal<Item> for Cons<Item, Tail>
where
    Tail: GetInternal<Item>,
{
    type Item = Item;

    fn get(self) -> Self::Item {
        self.0
    }
}

impl<Item, Other, Tail> GetInternal<Item> for Cons<Other, Tail>
where
    Tail: GetInternal<Item>,
{
    default type Item = Tail::Item;

    default fn get(self) -> Self::Item {
        self.1.get()
    }
}

struct Missing;
impl<Item> GetInternal<Item> for Nil {
    type Item = Missing;

    fn get(self) -> Self::Item {
        Missing
    }
}

I since refactored to work around the error:

#![feature(specialization)]

pub use self::{contains::Contains, get::Get};

#[derive(Clone, Copy, Debug)]
struct Cons<Item, Tail>(pub Item, pub Tail);

#[derive(Clone, Copy, Debug)]
struct Nil;

mod contains {
    use super::*;

    pub trait Contains<Item> {}

    impl<Item, T> Contains<Item> for T where T: ContainsInternal<Item, Contains = True> {}

    struct True;
    struct False;

    trait ContainsInternal<Item> {
        type Contains;
    }

    impl<Item, Tail> ContainsInternal<Item> for Cons<Item, Tail>
    where
        Tail: ContainsInternal<Item>,
    {
        type Contains = True;
    }

    impl<Item, Other, Tail> ContainsInternal<Item> for Cons<Other, Tail>
    where
        Tail: ContainsInternal<Item>,
    {
        default type Contains = Tail::Contains;
    }

    impl<Item> ContainsInternal<Item> for Nil {
        type Contains = False;
    }
}

mod get {
    use super::*;

    pub trait Get<Item> {
        fn get(self) -> Item;
    }

    impl<Item, L> Get<Item> for L
    where
        L: Contains<Item> + GetInternal<Item>,
    {
        fn get(self) -> Item {
            GetInternal::get(self)
        }
    }

    trait GetInternal<Item> {
        fn get(self) -> Item;
    }

    impl<Item, Tail> GetInternal<Item> for Cons<Item, Tail>
    where
        Tail: GetInternal<Item>,
    {
        fn get(self) -> Item {
            self.0
        }
    }

    impl<Item, Other, Tail> GetInternal<Item> for Cons<Other, Tail>
    where
        Tail: GetInternal<Item>,
    {
        default fn get(self) -> Item {
            self.1.get()
        }
    }

    impl<Item> GetInternal<Item> for Nil {
        fn get(self) -> Item {
            unreachable!()
        }
    }
}

However, I am now realizing this implementation fails in practice because type Contains = Tail::Contains is treated like a black-box by the compiler, instead of resolving to a concrete type.

Note, this is part of an implementation for a heterogeneous list that will be used for threading arguments through abstract representations of functions, as part of a framework for abstract representations of computations. You can think of it like a more advanced symbolic math library, one that works with computations instead of equations. Or you can think of it like a domain-specific language with compilers written as traits. It is kind of like TensorFlow, but more flexible. Here is some pseudocode of how the heterogeneous list may be used to ensure that a function can only be constructed if it defines all the arguments in its body with the right types:

struct Function<Names, Args, Body>
where
    (Names, Args): Zip,
    (Body::Names, Body::Args): Zip,
    (Names, Args)::Zip: ContainsAll<(Body::Names, Body::Args)::Zip>
{
    names: Names,
    args: Args,
    body: Body,
}

[justinlovinger]

Note, I actually care little about specialization in the sense of creating a more specialized implementation of a trait. What I really need is overlapping implementations for private traits, so I can create type-level "if-else statements". Explicit ordering would be ideal for my use-case. Something like,

ordered trait Foo { ... }

impl<A> Foo<A> for Bar<A> { ... }

impl<A, B> Foo<A> for Bar<B> { ... }

impl<A, T> Foo<A> for T { ... }

Where the first implementation that matches a type is used, and an ordered trait cannot be implemented outside the module it is defined in.

However, I understand there is a drive in Rust to focus on doing more with fewer constructs, and I appreciate that. At the very least, perhaps privacy of traits should be considered when determining what can be done with implementations.