Trait ensuring unique tuple types

[schell]

I'd really like to be able to ensure at the type level that the element types in a tuple are unique - that is to say that each element in the tuple is of a different type from the others. I've tried a number of type level tricks but have hit a dead end with each. It seems to boil down to the fact that there's just no way to assert at the type level that two types are not equal.

I think it could be done with #[feature(specialization)] but I don't want my crate to require that. Am I just out of luck or is there a known method for accomplishing this?

pub struct TyTrue;
pub struct TyFalse;

pub trait TyEq<A> {
    type Output;
}

impl<A> TyEq<A> for A
{
    type Output = TyTrue;
}

//impl<A, B> TyEq<B> for A {
//    type Output = TyFalse;
//}

fn tys_not_equal<A, B>()
where
    A: TyEq<B, Output = TyFalse>,
{
}

fn go() {
    tys_not_equal::<f32, u32>(); // compiler should not err
    tys_not_equal::<f32, f32>(); // compiler should err
}

[quinedot]

Defining exactly what type inequality means can be tricky in the presence of lifetimes (subtypes and higher-ranked types), and as far as I know there's no stable way to do this generically yet. (There are even some existing problems with type equality.)

There might be another way on nightly if it's specialization specifically you want to avoid.

If you know the set of types you're working with, you can implement some trait for every non-equal pair.

[schell]

Thank you I'm trying to allow my library to be built with stable - but I am already using GATs, so I can allow GATs. I don't know the set of types I'm working with, but I do know that they are all 'static and Sized.

[tczajka]

Why does your code not support equal types? What is the bigger problem you are trying to solve?

[schell]

@tczajka that's a good question.

I've built an entity component system (apecs) that stores tuples of components in type-erased archetypes. An archetype is a "bundle" of unique types. In order to pack them efficiently the components must be sorted by their type (so they match another archetype that may have been inserted with elements in a different order) and it simply doesn't make sense to allow duplicate types.

Currently the type uniqueness check happens at runtime and I'd like to offload that computation to the compiler since all the info needed is available at compile time.

Another benefit of this would be that functions that take "bundles" will fail to compile if duplicate element types are used instead of panicking at runtime, which is the current behavior.

[schell]

@tczajka
Here is an example of a function that would benefit from this trait.

[schell]

I might be onto something here (it's at least interesting):

pub trait TyEq<A, B, const C: bool> {}

impl<A> TyEq<A, A, true> for A {}
impl<A, B> TyEq<A, B, false> for B {}

fn ty_eq<A, B>()
where
    A: TyEq<A, B, true>,
{
}

fn ty_neq<A, B>()
where
    A: TyEq<A, B, false>,
{
}

fn go() {
    ty_eq::<f32, f32>();
    // fails to compile, which is good!
    // ty_eq::<u32, f32>();

    ty_neq::<f32, f32>(); // unfortunately this still compiles
}

Unfortunately this doesn't help with type inequality. I'm guessing it's because the impl for TyEq<A, B, false> matches even when A == B.

[quinedot]

That is why.

Type equality is directly supported in associated type bounds.

[schell]

Thanks @quinedot

I imagine there are a number of ways this may work in the future - specialization, negative traits (not sure what it's called - basically !Trait). As for now I won't worry about it - thanks for sussing it out with me.

[scottmcm]

@schell

not sure what it's called - basically !Trait

GitHub - rust-lang/negative-impls-initiative: Lang team negative impls...

[2e71828]

@schell

An archetype is a "bundle" of unique types. In order to pack them efficiently the components must be sorted by their type (so they match another archetype that may have been inserted with elements in a different order) and it simply doesn't make sense to allow duplicate types.

If you can require every component to implement a particular trait, this is possible in safe Rust. It gets quite complicated, though— It's the bulk of the work I had to do when implementing compile-time relational algebra.

The trick is to store a unique id as an associated type on the trait (using typenum or similar), and then make all of your type-level decisions based on that. I ensured uniqueness by writing a proc macro that encodes a UUID as a typenum, but you can probably get away with a documented uniqueness requirement. The type bounds get quite complicated with this sort of setup, though, which both blows up the compile time and makes the code hard to read & write. There was also a bug in the trait solver a couple of years ago that would sometimes put the compiler into an infinite loop when trying to compile my code, and I don't know if it's been fixed.