Recursively counting target type offset within type stack


#1

So i was experimenting with the type system.
My idea is to build a stack of types which could also be queried, allowing for some combination of dynamic programming and compile time optimizations.
I’m currently struggling with calculating the offset of a target type within a type stack, example provided

Stack<Stack<Stack<Stack<(), u32>, i32>, usize>, f32>

(I’m not considering cases when the target type occurs multiple times within the stack)

So far i have iterated a few times on my design to solve encountered issues. Resulting code can be found here (this requires the typenum crate, which is NOT within the top-100 crates on crates.io).
Compiling this fragment causes an evaluation overflow, which seems to be my brick wall.
The implementation for offset calculation currently uses methods and specialization to get it working, but the intention is to push the offset itself also within an associated type (onto the StackOffset trait) The lack of termination and branching makes it hard to carry a specific value over between types.

Is it even possible what i’m trying to achieve? Does anyone have any ideas on how to make this compile?

** My intention is to apply this concept within a Resource type, which is generic over this stack. The idea is to query resource values by their specific type. The resource values themselves are stored within a statically sized array and their index is bound to the offset within the stack of types.


#2

Answering my own question; i figured it out.

The new code can be found here. Note that i have renamed and restructured code since the original post.
This code still depends on the typenum crate.

So what are the key points of my implementation?

Compile time cons: A recursive list-like “type” that allows for appending more types. The actual implementation happens on a custom struct called Stack<Tail, Head>. Like a cons list this type recurses into itself as the Tail argument. The CTCons trait contains type parameters which act as an interface for manipulating the list.

Compile time counter: The trait CTCounter can be implemented for Stack to recursively count the amount of types/items it contains.
The implementation of CTCons for Stack has a constraint on the Tail part to implement CTCounter, this constraint is used to report the amount of items within the list as size.

Compile time if: I mentioned in the original post “The lack of termination and branching makes it hard to carry […]”. Branching is actually solvable within the type system, using a trait and type parameters to match on equality of types. Implemented like this

trait CTIf<Condition, OptionTrue, OptionFalse> {
    type Result: CTBool;
    type Path;
}

CTBool is a trait i used to encode True and False into the typesystem, but both are unused at the moment.
The interesting thing are the generic parameters, Condition defines the type on which is matched, OptionTrue/OptionFalse are types which must be returned depending on the match result of the condition. Path type parameter gets assigned one of the generic options depending on the match result. Path then holds the type which we want to substitute into our implementation of CTOffset.
So how are conditions actually checked?

struct CTIfCheck<X> {
    _marker: PhantomData<X>,
}

impl<X, CondFail, OptionTrue, OptionFalse> CTIf<CondFail, OptionTrue, OptionFalse> for CTIfCheck<X> 
{
    default type Result = CTFalse;
    default type Path = OptionFalse;
}

By implementing the CTIf trait for the CTIfCheck<X> structure we can control what should happen when generic argument X happens to match the provided generic argument Condition. Utilization is used to default to the False case, where X does NOT match the Condition.

<CTIfCheck<SubjectType> as CTIf<TargetType, Tail::Counter, Tail::Offset>>::Path

This snippet is how the if check is actually called upon. CTIfCheck type is built and cast to trait CTIf to perform the match. If SubjectType IS TargetType, if both their TypeId are equal so to speak, Tail::Counter is returned as Path.
The resulting functionality is the ability to pass the offset of the requested type throughout the cons-list.

This leaves two issues which are currently worked around.

  1. There is no type level termination, a number-type representing INVALID must be passed along when the requested type is not present. eg u32 is not found within (((), i32), i64).
    typenum::U1024 is used at the termination of the cons-list to bootstrap the recursion. I imagine nobody will actually build a cons-list of 1024 (different) types. I wished for this example to cause a compile time error but we can’t have everything at the moment… maybe in the future.

  2. CTIf must be specialized to each use case. This is a requirement when you use the trait to fill in a constrained type parameter, like type Offset: typenum::Unsigned + typenum::Add. Let’s look at the actual implementation.

trait CTIfOffset<Condition, OptionTrue, OptionFalse> {
    type Result: CTBool;
    type Path: Unsigned + Add<U1>;
}

trait CTOffset<Target> {
    type Offset: Unsigned + Add<U1>;
}

impl<Target, Tail, Head> CTOffset<Target> for Stack<Tail, Head>
where
    Tail: CTOffset<Target> + CTCounter,
    <CTIfCheck<Head> as CTIfOffset<Target, Tail::Counter, Tail::Offset>>::Path: Unsigned + Add<U1>,
{
    type Offset = <CTIfCheck<Head> as CTIfOffset<Target, Tail::Counter, Tail::Offset>>::Path;
}

If trait CTIf was used instead of CTIfOffset, the compiler cannot verify that Path is valid for the constraint Unsigned + Add<U1>. CTIfOffset can be implemented for CTIfCheck so no new structure is required.

  1. Using the same type multiple times within the cons-list will not result in correct offsets. The offset of the last encountered type will be returned.
    Only having unique types within the cons-list is taken on as precondition so no work-around is in place to handle the mentioned use-case.

Next up is utilizing this concept to create a Resource type and a matching Builder structure which should hide (most of) the types related to constructing the Resource type.
Maybe i’ll build a crate around this idea…


#3

I’ve not looked into the details, but on the surface it reminds me a bit of https://beachape.com/blog/2017/03/12/gentle-intro-to-type-level-recursion-in-Rust-from-zero-to-frunk-hlist-sculpting/.

Are you able to solve your case without requiring specialization? I’m not sure what its status is at the moment, but I’d probably avoid it for the meantime until its future is a bit clearer.

Nice work though! I’m always interested to see clever uses of Rust’s type system.


#4

Woah, thanks for the pointer! The described concepts peeked my interest.
Luckily my intentions are orthogonal on the Frunk crate so i don’t have to “just give up and use Frunk”. Altough it seems i could learn some things from its code.

Regarding specialization, i could probably remove that requirement if i can rewrite the offset calculation. A variation of what’s described in the mentioned post will probably work.
I’d be happy to drop that requirement actually so i could compile on stable as well.


#5

I have no idea what is going on here or even what you’re trying to do.

Thankyou, this will be interesting.