Bug in specialization?

Hi! In attempt to implement HList with unique types via specialization I ran upon a strange error:

error[E0308]: mismatched types
  --> src/main.rs:34:5
   |
34 | /     assert_type_eq!(
35 | |         <Continue<i32, Start<i64>, frunk::indices::Here> as Test>::List,
36 | |         HCons<i32, HCons<i64, HNil>>
37 | |     );
   | |      ^
   | |      |
   | |______expected associated type, found struct `frunk::HCons`
   |        this expression has type `MatchingType<<Continue<i32, Start<i64>, Here> as Test>::List>`
   |
   = note: expected struct `MatchingType<<Continue<i32, Start<i64>, Here> as Test>::List>`
              found struct `MatchingType<frunk::HCons<i32, frunk::HCons<i64, frunk::HNil>>>`
   = help: consider constraining the associated type `<Continue<i32, Start<i64>, Here> as Test>::List` to `frunk::HCons<i32, frunk::HCons<i64, frunk::HNil>>` or calling a method that returns `<Continue<i32, Start<i64>, Here> as Test>::List`

This happens if I try to specialize over different Test trait impls, one for when type is present in HList
by provided index, and one for when it doesn't (default impl).
When trying to use default keyword not on associated type, but rather on whole impl block, I got a different error:

error[E0275]: overflow evaluating the requirement `Continue<_, _, _>: Test`
  |
  = help: consider adding a `#![recursion_limit="256"]` attribute to your crate (`yay`)
  = note: required because of the requirements on the impl of `Test` for `Continue<_, _, _>`
  = note: 127 redundant requirements hidden
  = note: required because of the requirements on the impl of `Test` for `Continue<_, _, _>`

Removing specialization as a whole (leaving only impl without Selector bound) leads to successful compilation (comment in code).

Is this my mistake or an issue with specialization?

Code:

#![feature(specialization)]

use assert_type_eq::assert_type_eq;
use frunk::{HCons, HNil, hlist::Selector};

trait Test {
    type List;
}

struct Start<Item>(Item);

impl<Item> Test for Start<Item> {
    type List = HCons<Item, HNil>;
}

struct Continue<Item, Inner, HListIndex>(Item, Inner, HListIndex);

impl<Item, Inner, HListIndex> Test for Continue<Item, Inner, HListIndex>
where
    Inner: Test
{
    default type List = HCons<Item, Inner::List>;
}

impl<Item, Inner, HListIndex> Test for Continue<Item, Inner, HListIndex>
where
    Inner: Test,
    <Inner as Test>::List: Selector<Item, HListIndex>
{
    type List = Inner::List;
}

fn main() {
    // Compiles if specialized impl is removed, and `default` keyword removed too
    assert_type_eq!(
        <Continue<i32, Start<i64>, frunk::indices::Here> as Test>::List,
        HCons<i32, HCons<i64, HNil>>
    );
}

Dependencies:

[dependencies]
assert-type-eq = "0.1"
frunk = "0.3"

rustc version: rustc 1.54.0-nightly (e4ca1662f 2021-05-22)

You shouldn't use #![feature(specialization)] as it has soundness holes. Prefer #![feature(min_specialization)]. This is what I get with min_specialization though:

error[E0658]: specialization is unstable
  --> src/main.rs:22:5
   |
22 |     default type List = HCons<Item, Inner::List>;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: see issue #31844 <https://github.com/rust-lang/rust/issues/31844> for more information
   = help: add `#![feature(specialization)]` to the crate attributes to enable

error: cannot specialize on trait `Selector`
  --> src/main.rs:25:1
   |
25 | / impl<Item, Inner, HListIndex> Test for Continue<Item, Inner, HListIndex>
26 | | where
27 | |     Inner: Test,
28 | |     <Inner as Test>::List: Selector<Item, HListIndex>
29 | | {
30 | |     type List = Inner::List;
31 | | }
   | |_^

error: aborting due to 2 previous errors
2 Likes

I tried to use min_specialization at first, but after seeing that error (for which I have no idea how to apply any fix) I decided to stick with specialization (just to give it a shot)

Sooo… let’s try to walk through this. I hope I’m not making any mistakes, so here we go!

= note: expected struct `MatchingType<<Continue<i32, Start<i64>, Here> as Test>::List>`
           found struct `MatchingType<frunk::HCons<i32, frunk::HCons<i64, frunk::HNil>>>`

means a mismatch between

<Continue<i32, Start<i64>, Here> as Test>::List

and

HCons<i32, HCons<i64, HNil>>

Now what is the former? Let’s see

impl<Item, Inner, HListIndex> Test for Continue<Item, Inner, HListIndex>
where
    Inner: Test
{
    default type List = HCons<Item, Inner::List>;
}

impl<Item, Inner, HListIndex> Test for Continue<Item, Inner, HListIndex>
where
    Inner: Test,
    <Inner as Test>::List: Selector<Item, HListIndex>
{
    type List = Inner::List;
}

okay, so apparently <Continue<i32, Start<i64>, Here> as Test>::List can be

HCons<i32, <Start<i64> as Test>::List>

as long as the specialized implementation doesn’t kick in… let’s quickly check on <Start<i64> as Test>::List>, well…

impl<Item> Test for Start<Item> {
    type List = HCons<Item, HNil>;
}

allright, looks like we all agree that

<Start<i64> as Test>::List == HCons<i64, HNil>

no problems or disagreement there :grinning_face_with_smiling_eyes:. So right now we know that:

<Continue<i32, Start<i64>, Here> as Test>::List

is

  • equal to

    HCons<i32,  HCons<i64, HNil>>
    

    if the general trait implementation applies, or

  • equal to

    HCons<i64, HNil>
    

    if the specialized impl applies, i.e. if and only if

    <Start<i64> as Test>::List: Selector<i32, Here>
    

Let’s see about <Start<i64> as Test>::List: Selector<i32, Here> we already figured out and all agreed about

<Start<i64> as Test>::List == HCons<i64, HNil>

so the question becomes: Does the following trait implementation hold true or is it false?

HCons<i64, HNil>: Selector<i32, Here>

Now, if it’s true than your types wouldn’t match, alright, and if it’s false, then they should match. Without knowing anything about the underlying crate frunk myself, I guess there is no implementation for

HCons<i64, HNil>: Selector<i32, Here>

but it does appear that the HCons and HNil and Here types as well as the Selector trait all come from frunk and you do seem to expect there to be no implementation of the above trait constraits, otherwise you probably wouldn’t complain about the error message. Also the error message would most likely look different if there was such an implementation. (At least I would expect some mismatch between HCons<i32, HCons<i64, HNil>> and HCons<i64, HNil> in this case.)

But the simple question of “is this trait implementation present” is actually a bit more nuanced than I presented above. First of all, we’re trying to rely on a default SomeAssociatedType = … definition in a specialized trait, so we always must account for downstream implementations aswell. In this case this is not an issue, the type in question, Continue<i32, Start<i64>, Here>, is a foreign type for every downstream crate, the trait Test doesn’t have any additional parameters either, so downstream crates are fine, they cannot create any additional impls due to orphan rules. This test is important in general for soundness, after all we can’t rely on the associated type List to always be the default one in a generic setting, otherwise we might assume incorrect things. Type safety is memory safety, and memory safety is important.

What’s also important for Rust? Stability! Ah, and there’s this pesky little detail in Rust’s semver conventions that adding trait implementations that aren’t blanket implementations is a non-breaking change. The compiler helps a bit at enforcing this convention by things like orphan rules. And specialization seems to hook right into this kind of system; or maybe it does its own special thing to intentionally ensure this behavior, I don’t know, either way, long story short:

the frunk crate is allowed to add an impl for HCons<i64, HNil>: Selector<i32, Here> in the future

Let’s recapitulate. The problem we have: we can only be sure that the types the compiler complains about are actually the same if we know that HCons<i64, HNil>: Selector<i32, Here> is not implemented. But this trait constraint/bound is such that orphan rules allow the upstream frunk crate to add this concrete implementation without using a blanked impl. (In particular it doesn’t contain any local types of ours, just frunk and std ones.) So all we can ever know for sure about HCons<i64, HNil>: Selector<i32, Here> if semver/stability rules are taken into account is either that it’s true of that it’s currently false but may potentially become true in the future. We don’t know for sure that it’s false and hence you get the type mismatch error that you get.

7 Likes

By the way, whenever some sound version of specialization is stabilized, your example could indeed constitute a bug, that is, a diagnostics bug. I would 100% expect Rust to eventually give (a short form of) the explanation I gave above to explain the problem. In particular it should present the conclusion that upstream crates might implement HCons<i64, HNil>: Selector<i32, Here>. This would be similar to what we already have with potential-overlap errors.


a few minutes later…

I was going to give this example hoping for such an error

use frunk::{HCons, HNil, hlist::Selector, indices::Here};

trait Test {
    type List;
}

struct Start<Item>(Item);

impl<Item> Test for Start<Item> {
    type List = HCons<Item, HNil>;
}

struct Continue<Item, Inner, HListIndex>(Item, Inner, HListIndex);

impl<Item, Inner, HListIndex> Test for Continue<Item, Inner, HListIndex>
where
    Inner: Test,
    <Inner as Test>::List: Selector<Item, HListIndex>,
{
    type List = Inner::List;
}

impl Test for Continue<i32, Start<i64>, Here> {
    type List = HCons<i32, <Start<i64> as Test>::List>;
}

but I didn’t get one… and also this doesn’t compile either!?

use frunk::{hlist::Selector, HCons, HNil};

trait Test {
    type List;
}

struct Start<Item>(Item);

impl<Item> Test for Start<Item> {
    type List = HCons<Item, HNil>;
}

struct Continue<Item, Inner, HListIndex>(Item, Inner, HListIndex);

impl<Item, Inner, HListIndex> Test for Continue<Item, Inner, HListIndex>
where
    Inner: Test,
    <Inner as Test>::List: Selector<Item, HListIndex>,
{
    type List = Inner::List;
}
struct NotActuallyHere;

impl Test for Continue<i32, Start<i64>, NotActuallyHere> {
    type List = HCons<i32, <Start<i64> as Test>::List>;
}
error[E0119]: conflicting implementations of trait `Test` for type `Continue<i32, Start<i64>, NotActuallyHere>`
   --> src/main.rs:24:1
    |
 15 | / impl<Item, Inner, HListIndex> Test for Continue<Item, Inner, HListIndex>
 16 | | where
 17 | |     Inner: Test,
 18 | |     <Inner as Test>::List: Selector<Item, HListIndex>,
 19 | | {
 20 | |     type List = Inner::List;
 21 | | }
    | |_- first implementation here
 ...
 24 |   impl Test for Continue<i32, Start<i64>, NotActuallyHere> {
    |   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `Continue<i32, Start<i64>, NotActuallyHere>`

That’s kind-of weird actually…

Also… the conflict can only happen if Inner == Start<SomeItem> but narrowing the first impl down to

impl<Item, SomeItem, HListIndex> Test for Continue<Item, Start<SomeItem>, HListIndex>
where
    Start<SomeItem>: Test, // <- kind-of redundant, but doesn’t hurt
    <Start<SomeItem> as Test>::List: Selector<Item, HListIndex>,
{
    type List = <Start<SomeItem> as Test>::List; // need more explicit syntax here now
}

makes the conflict go away! I hope I’m not missing anything obvious here that would explain all of this; I think the compiler might just be somewhat limited in its reasoning here. So while my previous post’s explanation is probably true in theory, in practice rustc might just not be smart enough and might just think it does directly see some “possible overlap” – or rather – “applicability of the specialized impl”, in the case of your code example.


Not that that’s settled, back to my example error message I was trying to get to. With the limited version of the generic impl in place, we finally can get the desired error message if NotActuallyHere is changed back to Here

use frunk::{HCons, HNil, hlist::Selector, indices::Here};

trait Test {
    type List;
}

struct Start<Item>(Item);

impl<Item> Test for Start<Item> {
    type List = HCons<Item, HNil>;
}

struct Continue<Item, Inner, HListIndex>(Item, Inner, HListIndex);

impl<Item, SomeItem, HListIndex> Test for Continue<Item, Start<SomeItem>, HListIndex>
where
    Start<SomeItem>: Test, // <- kind-of redundant, but doesn’t hurt
    <Start<SomeItem> as Test>::List: Selector<Item, HListIndex>,
{
    type List = <Start<SomeItem> as Test>::List; // need more explicit syntax here now
}

impl Test for Continue<i32, Start<i64>, Here> {
    type List = HCons<i32, <Start<i64> as Test>::List>;
}
error[E0119]: conflicting implementations of trait `Test` for type `Continue<i32, Start<i64>, frunk::indices::Here>`
   --> src/main.rs:23:1
    |
 15 | / impl<Item, SomeItem, HListIndex> Test for Continue<Item, Start<SomeItem>, HListIndex>
 16 | | where
 17 | |     Start<SomeItem>: Test, // <- kind-of redundant, but doesn’t hurt
 18 | |     <Start<SomeItem> as Test>::List: Selector<Item, HListIndex>,
 19 | | {
 20 | |     type List = <Start<SomeItem> as Test>::List; // need more explicit syntax here now
 21 | | }
    | |_- first implementation here
 22 | 
 23 |   impl Test for Continue<i32, Start<i64>, Here> {
    |   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `Continue<i32, Start<i64>, frunk::indices::Here>`
    |
    = note: upstream crates may add a new impl of trait `frunk::hlist::Selector<i32, frunk::indices::Here>` for type `frunk::HCons<i64, frunk::HNil>` in future versions

Pay attention to the very last line of the error message, that’s what I was looking for :upside_down_face:

4 Likes

Wow. Thanks for such a detailed explanation!