Order on types for type level programming

Question

I've dived into type-level programming in Rust, as it could be very helpful to me in one of my projects. However, I am still struggling a little bit with what is possible or not.

Especially, I would like to implement an order on types to sort tuples. This will allow me to use tuples which are "vector" of types as "sets" of types.

So far, I have found how to implement linked list in type level programming, and I can use macros to convert tuples to linked list (and back):

trait LinkedList {}
// empty list
struct EmptyList;
// list: a head, (element in the list) and tail (rest of the list)
struct ListElem<Head, Tail: List>(PhantomData<(Head, Tail)>);
// empty list is a list
impl LinkedList for EmptyList {}
// list element is a list as well
impl<H, T: List> LinkedList for ListElem<H, T> {}

And my conversions: (shown for 2 elements, but I will use macros to generate as many as I want)

trait TupleToList {
    type List;
}
trait ListToTuple {
    type Tuple;
}
// this can easily be done with macros, for tuples up to a lot
impl<A, B> TupleToList for (A, B) {
    type List = ListElem<A, ListElem<B, EmptyList>>;
}
impl<A, B> ListToTuple for ListElem<A, ListElem<B, EmptyList>> {
    type Tuple = (A, B);
}

Now, This article shows type-level buble sort, but for this I need an order on my types, which can be written as :

struct CompareEQ;
struct CompareLT;
struct CompareGT;
// order between types
trait CompareTypes<T> {
    type Result;
}
// handy shortcut
type TypeOrder<T, U> = <T as CompareTypes<U>>::Result;

(As I want a set of types, I could remove the EQ operator as any tuples with duplicate types would be rejected)

My issue is that I have no idea how to order my types. With unstable features such as const traits, const type id I can write an const function that order types, but it is not type level :

const fn bigger_type_id<T: 'static, U: 'static>() -> bool {
    let t = unsafe {std::mem::transmute::<_, u128>(TypeId::of::<T>()) };
    let u = unsafe {std::mem::transmute::<_, u128>(TypeId::of::<U>()) };
    t < u
}

If I want to use this, I need to somehow convert back from value level to type level, something that would look like so:

impl<T, U> CompareTypes<U> for T {
    type Result = if bigger_type_id<T, U>() { GT } else { LT };
} 

(This syntax is not valid)

Also, I could take all types I want to sort and write another macro that write the order for them, but this application is intended for a library, where the user can define it's own types. This means that I would need him to invoke this macro, which I'm not a fan of.

What are my alternatives to implement type-level order on types ?

EDIT:

I've tried this out, where I use const generics and compute them with my function:

#![feature(generic_const_exprs)]

trait BiggerThan<T, const IS_IT: bool> {}

impl<T: 'static, U: 'static> BiggerThan<U, { bigger_type_id::<T, U>() }> for T {}

trait ActuallyBiggerThan<T> {
    type SomeType;
}

impl<T, U: BiggerThan<T, true>> ActuallyBiggerThan<T> for U {
    // Only for some tests
    type SomeType = &'static str;
}

type DoesItWorkOnce = <u8 as ActuallyBiggerThan<bool>>::SomeType;
type DoesItWorkTwice = <bool as ActuallyBiggerThan<u8>>::SomeType;

I tried it out with this :

pub fn func() {
    let v1: DoesItWorkOnce = "Hello";
    let v2: DoesItWorkTwice = "World";
}

Unfortunately, both types throw me the error :

"mismatched types expected constant true found constant false"

Which I believe, means that this does not work for some reason ?

I also get a feature warning : "the feature generic_const_exprs is incomplete and may not be safe to use and/or cause compiler crashes" so maybe the feature does not work properly ?

EDIT 2:

I made a typo in my first edit, I was asking for U to implement BiggerThan instead of BiggerThan.

Turns out my solution actually works ! (I fixed the typo in the first edit)

Answer 1

I have succeeded to sort tuples, and I'll post my solution here:

The core question was how to use const fn to implement trait, and the trick I found was to use #![feature(generic_const_exprs)]:

const fn t_greater_than_u<T: 'static, U: 'static>() -> bool {
    let t = unsafe {std::mem::transmute::<_, u128>(std::any::TypeId::of::<T>()) };
    let u = unsafe {std::mem::transmute::<_, u128>(std::any::TypeId::of::<U>()) };
    t > u
}

/// Defines an order on types.
trait TypeComparaison<T> {
    const GREATER: bool;
}

impl<T: 'static, U: 'static> TypeComparaison<U> for T {
    const GREATER: bool = { t_greater_than_u::<T, U>() };
}

Now, I'll post the rest of the code as a resources for anyone who want to implement sorting in type-level programming:

First define a list structure:

pub(crate)  trait List {}
pub(crate)  struct Nil;
pub(crate)  struct Cons<Head, Tail: List>(std::marker::PhantomData<(Head, Tail)>);
impl List for Nil {}
impl<H, T: List> List for Cons<H, T> {}

Then, we will expand our comparaison to compare a value with a list (with the head of the list) :

trait CompareTypeList<L: List> {
    const GREATER: bool;
}
impl<T> CompareTypeList<Nil> for T {
    const GREATER: bool = false;
}
impl<T: 'static, Head: 'static, L: List> CompareTypeList<Cons<Head, L>> for T {
    const GREATER: bool = <T as TypeComparaison<Head>>::GREATER;
}

We will then define usefull traits (that are functions in type level programming) :

Insertion will allow to insert a type in our list, preserving any order:

pub(crate) trait Insert<T, const TYPE_GT: bool> { type Output: List; }
impl<T> Insert<T, true> for Nil { type Output = Cons<T, Nil>; }
impl<T> Insert<T, false> for Nil { type Output = Cons<T, Nil>; }
impl<T, Head, L: List> Insert<T, false> for Cons<Head, L> {
    type Output = Cons<T, Cons<Head, L>>;
}
// I'm going to write comments about this : 
// T is the type we want to insert in the list. We implement insert for T on Cons<Head, L>, where T > Head.
// So, we need to create a list where Head is first element, and recursively insert T in the tail of the list.
// for this, T must me comparable with the list L, and L must be insertable with T.
// there we have all our trait bound explained !
impl<T: CompareTypeList<L>, Head, L: List + Insert<T, {<T as CompareTypeList<L>>::GREATER}>> Insert<T, true> for Cons<Head, L> {
    type Output = Cons<Head, <L as Insert<T, {<T as CompareTypeList<L>>::GREATER}>>::Output>;
}

We can now sort our List by recursively inserting all elements:

pub(crate) trait SortList { type SortedList: List; }
// how easy it is to sort an empty list !
impl SortList for Nil { type SortedList = Nil; }
impl<Head, L: List + SortList> SortList for Cons<Head, L>
    where
        Head: CompareTypeList<<L as SortList>::SortedList>, 
        <L as SortList>::SortedList: Insert<Head, {<Head as CompareTypeList<<L as SortList>::SortedList>>::GREATER}>
{
    type SortedList = <<L as SortList>::SortedList as Insert<Head, {<Head as CompareTypeList<<L as SortList>::SortedList>>::GREATER}>>::Output;
}

Finally, we need some conversion tuple <=> List. we will simply do this with macros, that will implement a trait that looks like this:

pub(crate) trait TupleToList { type List; }
pub(crate) trait ListToTuple { type Tuple; }

impl<A, B> TupleToList for (A, B) { type List = Cons<A, Cons<B, Nil>>; }
impl<A, B> ListToTuple for Cons<A, Cons<B, Nil>> { type Tuple = (A, B); }

(I've shown the impl for 2 elems so it's clear, but a macro can implement this for all tuples up to some length)

Finally, we can write our sorting generic:

pub(crate) trait TupleSortTrait {
    type Sorted;
}

impl<T> TupleSortTrait for T
where T: TupleToList,
      <T as TupleToList>::List: SortList,
      <<T as TupleToList>::List as SortList>::SortedList: ListToTuple, 
{
    type Sorted = <<<T as TupleToList>::List as SortList>::SortedList as ListToTuple>::Tuple;
}

pub(crate) type TupleSort<T> = <T as TupleSortTrait>::Sorted;

This whole thing definitively need some clean up, and as mentionned in the comments I'll try to find a better solution for type ordering than TypeId.

But this works, and we can write this kind of things:

let v = vec![
    <(u8, String, bool) as Default>::default(),
    <TupleSort<(String, bool, u8)> as Default>::default(),
    <TupleSort<(bool, String, u8)> as Default>::default(),
];