Metaprogramming: TypeId Equal For Different Types and Mutually Recursive Traits

ambiso · May 19, 2022, 6:19pm

Hi!

tl;dr: I have two types that are equal according to TypeId but are not equal according to trait resolution.
It looks like I'm breaking something in the type-system with mutual trait-recursion and the specialization feature.

Lengthy details of what I'm trying to achieve

I'm trying to write a compile-time dictionary/map that can map types to integers. I want to be able to add these, element wise. So Dict(A => 3) + Dict(A => 1, B => 2) = Dict(A => 4, B => 2). For that I'm trying to first find the union of all keys: {A, B} and then write a trait/function that can obtain the sum for each key from both dicts to create the final result.

This must be done at compile-time because I want to get compile-time guarantees from it. Specifically I'm looking for something like the uom or dimensioned crate, but with the ability to add quantities/dimensions to a system of quantities without changing all other dimension definitions.
The uom and dimensioned crates realize units using a type a bit like like this:

type Meter = Dimensioned<f64, Length=1, Mass=0, Time=0>;
type Kilogram = Dimensioned<f64, Length=0, Mass=1, Time=0>;
type Time = Dimensioned<f64, Length=0, Mass=0, Time=1>;
type Acceleration = Dimensioned<f64, Length=1, Mass=0, Time=-2>;

When multiplying two numbers you add their dimensions, so acceleration = m/(s^2) = Meter - Time - Time.

I want to achieve the same, but I don't want to fix a specific number of dimensions beforehand, so users can extend the dimensions from outside of the crate, without needing to re-define the entire system of quantities again.

To do that I want to implement essentially a dictionary at a type-system level (with a crappy O(n^2) complexity of adding two dictionaries).

Here's the code.

There's two errors:

from test case 4 where it fails to compute Test4ListResult because a trait bound is not satisfied.

In this error it mentions that

the trait bound <TArr<B, TArrEnd> as RemoveTypeFromList<A>>::Output: Dedup is not satisfied

However, it does implement Dedup! The linked playground compiles and runs without errors, which means:
a) Test4IntermediateResult and Test4IntermediateExpectedResult are the same type according to TypeId
b) Test4IntermediateExpectedResult implements Dedup
(where Test4IntermediateResult = <TArr<B, TArrEnd> as RemoveTypeFromList<A>>::Output, from the error message above).

the other error is that Test4IntermediateResult (which is supposed to be equal to Test4IntermediateExpectedResult and implements Dedup) does not implement Dedup

I get that the specializations feature is not ready, but is there anything that can be done here?

What's the reason for this mismatch?

Does the rust compiler not fully evaluate the type of Test4IntermediateResult? Can I tell it to?

Can I achieve my dream of a compile-time dict in a different way?

Thanks for reading, and thanks for any replies and comments in advance!

ambiso

I think I might want something like Zig's comptime in Rust? Having access to, and being able to compute on types in something like a proc-macro.

H2CO3 · May 19, 2022, 6:41pm

You state that the end goal is mapping types to integers at compile time. Isn't that achieved more simply via an associated const?

ambiso · May 19, 2022, 6:46pm

Well, I think you will only be able to associate a single integer with each type. However I want to be able to have collections of types with their associated integers, and be able to add these collections element wise, so the integer associated with a type can change per instance of the collection.

If you read the Lengthy details of what I'm trying to achieve (you can click on it to expand it) in the original post you will get a better idea of it than from just reading the code, I think.

jakubdabek · May 19, 2022, 7:36pm

I think the problem is that there is no Dedup impl with bounds not on the head type, so maybe something like

// T and U are different
impl<T, U, Rest: RemoveTypeFromList<U>> Dedup for TArr<T, Rest>
where
    <Rest as RemoveTypeFromList<U>>::Output: Dedup,
{
    default type Output = TArr<T, <<Rest as RemoveTypeFromList<U>>::Output as Dedup>::Output>;
}

That doesn't work, because "the type parameter U is not constrained by the impl trait, self type, or predicates".
The frunk crate has similar design and from what I've seen the Here and There types are a workaround for that, e.g. for the Plucker and Sculptor traits (src), but haven't dived deep enough to know exactly how to use that.

steffahn · May 19, 2022, 7:58pm

Played around with it, and this seems to – at least mostly – work…

#![feature(generic_const_exprs, specialization)]
#![allow(unused_macros, dead_code, incomplete_features)]

// Array of types, a bit like the typenum crate, but not actually capable of storing the data
struct TArrEnd;
struct TArr<T, Rest> {
    _t: std::marker::PhantomData<fn(T) -> ()>,
    _d: std::marker::PhantomData<fn(Rest) -> ()>,
}

// This is the end goal: basically a HashMap<Type, i32> but evaluated compile time
// Want to be able to add two of these together: like an impl Add<HashMap<Type, i32>> for HashMap<Type, i32>
// These two structs are not relevant for the rest of the code.
struct TDictEnd;
struct TDict<Key, const VALUE: i32, Rest> {
    _key: std::marker::PhantomData<fn(Key) -> ()>,
    _rest: std::marker::PhantomData<fn(Rest) -> ()>,
}

trait RemoveTypesAndDedup<Removals, AllRemovals> {
    type Output;
}

impl<AllRemovals> RemoveTypesAndDedup<TArrEnd, AllRemovals> for TArrEnd {
    type Output = TArrEnd;
}

impl<R, RRest, AllRemovals> RemoveTypesAndDedup<TArr<R, RRest>, AllRemovals> for TArrEnd {
    type Output = TArrEnd;
}

impl<T, TRest, AllRemovals> RemoveTypesAndDedup<TArrEnd, AllRemovals> for TArr<T, TRest>
where
    TRest: RemoveTypesAndDedup<TArr<T, AllRemovals>, TArr<T, AllRemovals>>,
{
    type Output = TArr<T, TRest::Output>;
}

impl<R, RRest, T, TRest, AllRemovals> RemoveTypesAndDedup<TArr<R, RRest>, AllRemovals>
    for TArr<T, TRest>
where
    Self: RemoveTypesAndDedup<RRest, AllRemovals>,
    TRest: RemoveTypesAndDedup<TArr<T, AllRemovals>, TArr<T, AllRemovals>>,
{
    default type Output = <Self as RemoveTypesAndDedup<RRest, AllRemovals>>::Output;
}

impl<R, RRest, TRest, AllRemovals> RemoveTypesAndDedup<TArr<R, RRest>, AllRemovals>
    for TArr<R, TRest>
where
    Self: RemoveTypesAndDedup<RRest, AllRemovals>,
    TRest: RemoveTypesAndDedup<TArr<R, AllRemovals>, TArr<R, AllRemovals>>,
{
    type Output = TRest::Output;
}

trait Dedup {
    type Output;
}

impl<T: RemoveTypesAndDedup<TArrEnd, TArrEnd>> Dedup for T {
    type Output = <Self as RemoveTypesAndDedup<TArrEnd, TArrEnd>>::Output;
}

#[macro_export]
macro_rules! tvec {
    () => {
        TArrEnd
    };
    ($x:ty, $($xs:ty),*) => {
        TArr<$x, tvec!($($xs),*)>
    };

    ($x:ty) => {
        TArr<$x, TArrEnd>
    };
}

#[cfg(test)]
mod test {
    struct A;
    struct B;
    struct C;

    use super::*;

    #[test]
    fn test1() {
        // type Test1ListInput = tvec![A];
        // type Test1ListExpectedResult = tvec![A];
        // type Test1ListResult = <Test1ListInput as RemoveTypeFromList<B>>::Output;
        // assert_eq!(
        //     std::any::TypeId::of::<Test1ListExpectedResult>(),
        //     std::any::TypeId::of::<Test1ListResult>()
        // );

        // type Test2ListInput = tvec![A, B, B, C];
        // type Test2ListExpectedResult = tvec![A, C];
        // type Test2ListResult = <Test2ListInput as RemoveTypeFromList<B>>::Output;
        // assert_eq!(
        //     std::any::TypeId::of::<Test2ListExpectedResult>(),
        //     std::any::TypeId::of::<Test2ListResult>()
        // );

        type Test3ListInput = tvec![A];
        type Test3ListExpectedResult = tvec![A];
        type Test3ListResult = <Test3ListInput as Dedup>::Output;
        assert_eq!(
            std::any::TypeId::of::<Test3ListExpectedResult>(),
            std::any::TypeId::of::<Test3ListResult>()
        );

        type Test4ListInput = tvec![A, B];
        type Test4ListExpectedResult = tvec![A, B];
        type Test4ListResult = <Test4ListInput as Dedup>::Output;
        assert_eq!(
            std::any::TypeId::of::<Test4ListExpectedResult>(),
            std::any::TypeId::of::<Test4ListResult>() // ERROR!
        );


        // type Test4IntermediateResult = <TArr<B, TArrEnd> as RemoveTypeFromList<A>>::Output;
        // type Test4IntermediateExpectedResult = tvec![B];
        // assert_eq!(
        //     std::any::TypeId::of::<Test4IntermediateResult>(),
        //     std::any::TypeId::of::<Test4IntermediateExpectedResult>()
        // ); // Types are the same!

        // fn is_dedup<T: Dedup>() {}
        // is_dedup::<Test4IntermediateResult>(); // ERROR!
        // is_dedup::<Test4IntermediateExpectedResult>(); // Works! This type is Dedup

        // More extended Dedup test case - if you got it working, try it with test #5! :-)
        type Test5ListInput = tvec![A, B, B, C, A];
        type Test5ListExpectedResult = tvec![A, B, C];
        type Test5ListResult = <Test5ListInput as Dedup>::Output;
        assert_eq!(
            std::any::TypeId::of::<Test5ListExpectedResult>(),
            std::any::TypeId::of::<Test5ListResult>()
        );

    }
}

samuelpilz · May 19, 2022, 8:02pm

I don't understand why this could work without adding trait bounds to the Output specialized associated type, because the compiler seems to do no expansion of it at all. See this minimal example playground

#![feature(specialization)]
#![allow(incomplete_features)]

struct S1;
struct S2;

trait M {} // some marker trait
impl M for S1 {}
impl M for S2 {}

trait T { // some transformation trait with output type S
    type S;
    // FIX: declare trait bound M
    // type S : M;
}
impl<X> T for X {
    default type S = S1;
}
impl T for S2 {
    type S = S2;
}
fn is_m<S: M>() {}
fn test() {
    is_m::<<S1 as T>::S>; // ERROR
}

ambiso · May 20, 2022, 10:11am

Amazing! I don't completely understand your solution, could you try to explain what lead you to use this helper trait? What are Removals and AllRemovals?

Why does it only "mostly" work? Are there any cases where it falls apart?

Why does my original code fail?

Thanks!!

steffahn · May 20, 2022, 10:27am

Yeah, it didn’t seem to like it when it wasn’t about TypeId being equal but actual types needing to be equal at compile time. E.g.

let x: PhantomData<Test5ListExpectedResult> = PhantomData;
let y: PhantomData<Test5ListResult> = x;

fails for some reason.

The idea was that I’d write a trait for removing multiple things at once, also presented as a type list. It operates by going through the list of items-to-remove until it’s empty, or the current item was indeed found; then I added AllRemovals because it needs to reset the list to move on to the next one. E.g. the operation should proceed roughly as follows

<tvec![A, B, B, C, A] as Dedup>::Output


<tvec![A, B, B, C, A] as RemoveTypesAndDedup<tvec![], tvec![]>::Output
// Removals empty                                 ^^

TArr<A, <tvec![B, B, C, A] as RemoveTypesAndDedup<tvec![A], tvec![A]>::Output>
// no match    ^                                        ^
TArr<A, <tvec![B, B, C, A] as RemoveTypesAndDedup<tvec![], tvec![A]>::Output>
// Removals empty                                      ^^

TArr<A, TArr<B, <tvec![B, C, A] as RemoveTypesAndDedup<tvec![B, A], tvec![B, A]>::Output>>
// matches             ^                                     ^


TArr<A, TArr<B, <tvec![C, A] as RemoveTypesAndDedup<tvec![B, B, A], tvec![B, B, A]>::Output>>
// no match            ^                                  ^
TArr<A, TArr<B, <tvec![C, A] as RemoveTypesAndDedup<tvec![B, A], tvec![B, B, A]>::Output>>
// no match            ^                                  ^
TArr<A, TArr<B, <tvec![C, A] as RemoveTypesAndDedup<tvec![A], tvec![B, B, A]>::Output>>
// no match            ^                                  ^
TArr<A, TArr<B, <tvec![C, A] as RemoveTypesAndDedup<tvec![], tvec![B, B, A]>::Output>>
// Removals empty                                        ^^

TArr<A, TArr<B, TArr<C, <tvec![A] as RemoveTypesAndDedup<tvec![C, B, B, A], tvec![C, B, B, A]>::Output>>>
// no match                    ^                               ^
TArr<A, TArr<B, TArr<C, <tvec![A] as RemoveTypesAndDedup<tvec![B, B, A], tvec![C, B, B, A]>::Output>>>
// no match                    ^                               ^
TArr<A, TArr<B, TArr<C, <tvec![A] as RemoveTypesAndDedup<tvec![B, A], tvec![C, B, B, A]>::Output>>>
// no match                    ^                               ^
TArr<A, TArr<B, TArr<C, <tvec![A] as RemoveTypesAndDedup<tvec![A], tvec![C, B, B, A]>::Output>>>
// matches                     ^                               ^

TArr<A, TArr<B, TArr<C, <tvec![] as RemoveTypesAndDedup<tvec![A, C, B, B, A], tvec![A, C, B, B, A]>::Output>>>
// Self empty                 ^^

TArr<A, TArr<B, TArr<C, TArrEnd>>>

So for each idem, the Removals list is gone through one-by-one, once it’s empty, or a match is found, the AllRemovals list is used to restore all the Removals (and the current item is also added).

Adding the current item is technically redundant in case there was a matching item found, ~~but it simplifies the trait bounds for the specialized impl~~ actually, I double-checked just now so… nevermind, this works just fine, too, with no downsides: Rust Playground

ambiso · May 26, 2022, 8:28am

Thanks a lot for your explanation!

I've been trying to make the full dictionary addition work

the expected behavior would be something like:

<TDict<A, 2, TDict<B, 1, TDictEnd>> as Add<TDict<A, 1, TDictEnd>>>::Output
==
TDict<A, 3, TDict<B, 1, TDictEnd>>

However, I can't get it to work and I am once again asking for your non-financial support

Here's the code.

I implemented the Add trait using the AddDicts, TypeListify, GatherCountsForType and Dedup traits.

AddDicts takes as a parameter the deduplicated list of types and then finds the count of each type in both dicts simultaneously.

TypeListify which converts two dicts into a list of the types they contain;
e.g.

<TDict<A, 1, TDictEnd> as TypeListify<TDict<A, 2, TDict<B, 1, TDict,End>>>>::Output
==
tarr![A, A, B]

GatherCountsForType will take a type (e.g. A) and two dicts and sum up all the numbers corresponding to the provided type in both dicts.

There's also a convenience tdict![A => 1, B => 2] macro now.

The problem seems to be that it cannot resolve all the trait requirements that are needed for the Add impl. I believe the traits should be implemented for the types, but that the trait resolution just can't see that.

Specifically it looks like it's not expanding the following type in the example that doesn't compile:

<TArr<A, TArr<C, TArrEnd>> as RemoveTypesAndDedup<TArr<C, TArrEnd>, TArr<C, TArrEnd>>>::Output

This should expand to a TArr<K, KRest> and then one of the AddDicts impls should match, but it does not match any of the impls.

I tried annotating the Output types of the traits with TDictType (which TDict and TDictEnd implement) and with TArrType (which TArr and TArrEnd implement) in hopes that it would maybe help the compiler see that AddDicts should be implemented but it didn't help.

Do you have any ideas?

Topic		Replies	Views
Design patterns for composability with traits (i.e. typeclasses)? help	133	17212	May 3, 2016
Understanding how to add functionnality help	20	589	July 1, 2025
How to get the type name from `TypeId`? help	39	9490	May 17, 2022
Building more intuition for `MyType<T>` and `MyTrait<U>` help	7	1189	June 21, 2023
Trait Constructors	21	4093	January 2, 2021

Metaprogramming: TypeId Equal For Different Types and Mutually Recursive Traits

Related topics