Making a type level type function with `typenum` crate

I am the author of sosecrets-rs where right now, I am trying to write a RTSecret<T, MEC: typenum::Unsigned> struct where T is any type and MEC is an unsigned integer at the type level from the typenum crate (e.g. U69), etc. The crate counts the number of times (tracked by an internal counter of type UnsafeCell<SomeUIntType>) the secret is revealed and returns an Error or panic if it is revealed more than MEC - materialized as runtime value - number of times.

I have an internal counter of type UnsafeCell<SomeUIntType>, because the user of my crate at his compile time will fill in the type argument for the type parameter MEC, e.g.

// How a user will use this `RTSecret` at his compile time.
let runtime_secret = RTSecret::<i32, typenum::consts::U69>::new(69);

and since the user of my crate let 'MEC' to be equal to U69, that means u8 would suffice as my internal counter, e.g. of type UnsafeCell<u8> since the internal counter will always starts from 0 and counting up by 1 until it reaches 69.

So I want to be able to derive the minimally representable unsigned integer type, supporting only u8, u16, u32 and u64 (and not usize or u128) from the type parameter MEC: Unsigned only. I have a working solution that uses two type parameters, MEC and SIZE, SIZE allows users to specify the exact type that they want the counter to be, e.g. SIZE = U8 -> type of internal counter is u8, etc. See here.

I tried writing a type function (i.e. a trait) call CalcMinUIntType<V: Unsigned + NonZero, B: ...> (see Playground link later) but it gives me the StackOverflow error at compile time, meaning the evaluation of the type level recursion does not end.

Here is my implementation of the trait (Playground).

I need to constrain B to be 'at least U8 and at most U64' to have the base cases but I am not sure how to do it at the type level, lol.

Implementation pasted below for convenience:

/*
[dependencies]
typenum = "1.17.0"
*/
#![recursion_limit = "4000"]
fn main() {
    use core::{
        marker::PhantomData,
        ops::{Add, Shl},
    };
    use typenum::{
        consts::{U0, U1, U16, U2, U254, U32, U365, U64, U66, U8},
        Bit, False, IsGreaterOrEqual, IsLess, IsLessOrEqual, NonZero, PowerOfTwo, Prod, Sum, True,
        Unsigned,
    };

    trait If<Cond: Bit> {
        type Outcome;
    }

    trait MinimallyRepresentableAsUInt:
        Unsigned
        + NonZero
        + IsLessOrEqual<U64, Output = True>
        + IsGreaterOrEqual<U8, Output = True>
        + PowerOfTwo
    {
    }

    impl MinimallyRepresentableAsUInt for U8 {}
    impl MinimallyRepresentableAsUInt for U16 {}
    impl MinimallyRepresentableAsUInt for U32 {}
    impl MinimallyRepresentableAsUInt for U64 {}

    struct Either<L: Unsigned + NonZero, R: MinimallyRepresentableAsUInt>(PhantomData<(L, R)>);

    impl<L: Unsigned + NonZero, R: MinimallyRepresentableAsUInt> If<False> for Either<L, R> {
        type Outcome = L;
    }

    impl<L: Unsigned + NonZero, R: MinimallyRepresentableAsUInt> If<True> for Either<L, R> {
        type Outcome = R;
    }

    trait CalcMinUIntType<V: Unsigned + NonZero, B: MinimallyRepresentableAsUInt> {
        type Outcome: MinimallyRepresentableAsUInt;
    }

    type U1LeftShift<Bits> = <U1 as Shl<Bits>>::Output;

    // println!("{:?}", U1LeftShift::<U16>::USIZE); // OK
    // println!("{:?}", Prod::<U8, U2>::USIZE); // OK
    // type MinUIntType = <() as CalcMinUIntType<V, B>>::Outcome
    // println!("{:?}", <U66 as IsLess<U1LeftShift<U8>>>::Output::BOOL); // OK

    // impl<V: Unsigned + NonZero> CalcMinUIntType<V, U64> for () {
    //     type Outcome = U64;
    // }

    impl<V: Unsigned + NonZero, B: MinimallyRepresentableAsUInt> CalcMinUIntType<V, B> for () {
        type Outcome = <Either<<() as CalcMinUIntType<V, Prod<B, U2>>>::Outcome, B> as If<
            <V as IsLess<U1LeftShift<B>>>::Output,
        >>::Outcome;
    }
}

The type level function is modeled after the following runtime function given by ChatGPT, of course, when bits = 0, it will recurse forever and when value is larger than u64::MAX it might overflow if your pointer width is 64 bits (or rather whenever the value is larger than your CPU pointer width, it overflows or wrapped in released mode).

fn min_unsigned_type(value: usize, bits: usize) -> usize {
    if value < (1 << bits) {
        bits
    } else {
        min_unsigned_type(value, bits * 2)
    }
}
1 Like

As the error message says, a stack overflow error in rustc is considered a bug. Have you filed an issue in Issues · rust-lang/rust · GitHub?

1 Like

Does this not work?

type CalcMinUIntType<N> = Shleft<U1, Add1<Log2<Length<N>>>>;
assert_type_eq!(CalcMinUIntType<U69>, U8);
2 Likes

It's possible write a macro that implements this as a lookup table on the number of bits in the typenum representation:

use typenum::uint::{UTerm, UInt};

trait ChooseInt {
    type Output;
}

impl ChooseInt for UTerm {
    type Output = u8;
}

macro_rules! impl_choose_int {
    // Entry point
    ($($arg:ident => $out:ty;)*) => {
        impl_choose_int! {
            @prev_args ();
            @prev_num UTerm;
            @rest_args ($($arg,)*);
            @rest_out ($($out;)*);
        }
    };
    
    // Implement one
    (
        @prev_args ($($prev_args:ident,)*);
        @prev_num $prev_num:ty;
        @rest_args ($arg:ident, $($rest_args:ident,)*);
        @rest_out ($out:ty; $($rest_out:ty;)*);
    )
    => {
        impl<$($prev_args,)* $arg> ChooseInt for UInt<$prev_num, $arg> {
            type Output = $out;
        }
        impl_choose_int!{
            @prev_args ($($prev_args,)* $arg,);
            @prev_num UInt<$prev_num, $arg>;
            @rest_args ($($rest_args,)*);
            @rest_out ($($rest_out;)*);
        }
    };
    
    // Base case; stop iteration
    (
        @prev_args ($($prev_args:ident,)*);
        @prev_num $prev_num:ty;
        @rest_args ();
        @rest_out ();
    ) => {};
}
3 Likes

AFAIK the type level code you showed is not equivalent to the one on the bottom due to your type level code having to compute all types that appear in your definition, even those that end up being discarded in the unpicked branch. So it's more like equivalent to:

fn min_unsigned_type(value: usize, bits: usize) -> usize {
    let true_branch = bits;
    let false_branch = min_unsigned_type(value, bits * 2);

    if value < (1 << bits) {
        true_branch 
    } else {
        false_branch 
    }
}

And this of course ends up in a stack overflow if you execute it. (Though the fact that rustc actually crashes due to a stack overflow is still bad, it should report an overflow when computing the types/solving trait obligations).

1 Like

The trait bounds to allow it to compile in a generic context will fairly ugly, but once you have the number of bytes, the smallest sufficient int type is a single trait with an associated type and nine impls away. (Or include yet another length projection to get it down to five impls, plus one more for u128.)

Sketched:

trait IntSelect { type Output; }
type FittedInt<N> = <Quot<Length<N>, U8> as IntSelect>::Output;
// has off-by-one error for you to fix smile
// wants a ceil-div instead of floor-div
impl IntSelect for U0 { type Output = (); }
impl IntSelect for U1 { type Output = u8; }
impl IntSelect for U2 { type Output = u16; }
impl IntSelect for U3 { type Output = u32; }
impl IntSelect for U4 { type Output = u32; }
// etc

But, question: what percentage of the time will any consumer be protecting a secret which is less aligned than u32, or support an exposure count ≥232? If it's sufficiently rare, you're adding in additional complexity for marginal benefit at best. A user who is that memory/performance conscious is just going to use T instead of Secret<T>, because minimal overhead is still more than no overhead.

Also on the usage of UnsafeCell for the counter: don't, use Cell<uN> or AtomicUN instead, depending on whether you want Sync. (The radium crate allows you to be generic over that axis, if desired.) These types capture the counter semantics, don't require unsafe, and have zero overhead over (soundly) doing it manually, including providing get_mut for when you have &mut and don't want to rely on the optimizer.

2 Likes

Hi @CAD97

Thank you for your response. I want to be able to expose the secret using just an immutable reference, hence the UnsafeCell. Such a semantics is because from the user perspective, he should be able to view the secret with an immutable reference, afterall, he is not mutating the secret. It also makes the API a little easier to use I guess.

Hi @2e71828, this is a brute force solution to my problem which I absolutely love!

Just wondering, how about B08 and B09? They seem to be missing and should be mapped to u16 right?

Also, for B33 onwards, they should be mapped to u64 instead of u32 still, am I right? Thank you.

@CAD97 Hi

Thank you for your response and your exercise.

CellDiv would then be FloorDiv + 1?

Those are just arbitrary identifiers used as generic type parameters, so the numbers are completely arbitrary— The macro only pays real attention to the order the output types are listed in.

As the numbers didn't really matter, I ended up with an octal instead of decimal representation while streamlining my copy+paste+edit routine to write the table.

Apologies @2e71828, I studied your macro diligently.

Can you explain why

    B20 => u32;
    B21 => u32;
    B22 => u32;
    B23 => u32;
    B24 => u32;
    B25 => u32;
    B26 => u32;
    B27 => u32;

    B30 => u32;
    B31 => u32;
    B32 => u32;
    B33 => u32;
    B34 => u32;
    B35 => u32;
    B36 => u32;
    B37 => u32;

Two segments of 8 bits is mapped to u32 but four segments are mapped to u64?

Thank you.

p.s. I came from a Python background without any formal education in computer science.

Hi @jendrikw

Thank you for your response. I think your solution is still wrong.

Consider:

assert_type_eq!(CalcMinUIntType<U255>, U8);

This should compile but it doesn't.

This is still not a valid reason to use UnsafeCell. Cell and the Atomic types will also allow you to mutate the counter with an immutable reference.

1 Like

Hi @2e71828

I studied your macro with the Rust Playground and cargo expand. I think I can understand it, you basically understood how typenum works in generating the type-level unsigned integers.

For example:

impl<B00, B01, B02, B03, B04, B05, B06, B07> ChooseInt for UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B00>, B01>, B02>, B03>, B04>, B05>, B06>, B07> {
    type Output = u8;
}

Your macro expanded to such a code figment which is an implementation of ChooseInt trait where its associated type Output is u8. And the key is, UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B00>, B01>, B02>, B03>, B04>, B05>, B06>, B07> is basically all type-level unsigned integers that can be represented by 8 type-level bits (although each B0* does not implement the trait typenum::bits::Bit but that's fine), each slot B0*, e.g. B00 being the most significant bit which can either be typenum::B1 (1 bit at the type level) or typenum::B0 since it is generic and not bounded by any traits.

Please let me know if I am right.

1 Like

That’s essentially correct, but there’s one subtlety to typenum’s internal representation that you don’t mention: Leading zeroes are banned in favor of a shorter overall type.

So, the particular impl you picked as an example covers only the integers between 128 and 255; the prior impls produced by the macro cover 1-127, and the manual impl for UTerm covers 0.

3 Likes

Leading zeroes are banned in favor of a shorter overall type.

Would you mind elaborating more on this? @2e71828

Do you mean because UInt<UTerm, B00> is the first bit which can either be 0 or 1 and UInt<UInt<UTerm, B00>, B01> represents two bits with the first bit set, i.e. 1 -> 01 or 11; 0 -> 10, 00?

And because UInt<UTerm, B00> is a different type from UInt<UInt<UTerm, B00>, B01>, they all need a separate impl?

So, the particular impl you picked as an example covers only the integers between 128 and 255; the prior impl s produced by the macro cover 1-127, and the manual impl for UTerm covers 0.

I don't think I understand this fully but let me try to get the snippet from cargo expand to understand it more.

impl<B00> ChooseInt for UInt<UTerm, B00> {
    type Output =
        u8;
}
impl<B00, B01> ChooseInt for UInt<UInt<UTerm, B00>, B01> {
    type Output = u8;
}
impl<B00, B01, B02> ChooseInt for UInt<UInt<UInt<UTerm, B00>, B01>, B02> {
    type Output = u8;
}
impl<B00, B01, B02, B03> ChooseInt for
    UInt<UInt<UInt<UInt<UTerm, B00>, B01>, B02>, B03> {
    type Output = u8;
}
impl<B00, B01, B02, B03, B04> ChooseInt for
    UInt<UInt<UInt<UInt<UInt<UTerm, B00>, B01>, B02>, B03>, B04> {
    type Output = u8;
}
impl<B00, B01, B02, B03, B04, B05> ChooseInt for
    UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B00>, B01>, B02>, B03>, B04>, B05> {
    type Output = u8;
}
impl<B00, B01, B02, B03, B04, B05, B06> ChooseInt for
    UInt<UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B00>, B01>, B02>, B03>, B04>,
    B05>, B06> {
    type Output = u8;
}
impl<B00, B01, B02, B03, B04, B05, B06, B07> ChooseInt for
    UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B00>, B01>, B02>, B03>,
    B04>, B05>, B06>, B07> {
    type Output = u8;
}
impl<B00, B01, B02, B03, B04, B05, B06, B07, B10> ChooseInt for
    UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B00>, B01>, B02>,
    B03>, B04>, B05>, B06>, B07>, B10> {
    type Output =
        u16;
}

The snippet below covers the first bit. 0 and 1.

impl<B00> ChooseInt for UInt<UTerm, B00> {
    type Output =
        u8;
}

The snippet below covers the second bit but not the first bit because that is covered by impl<B00> ChooseInt for UInt<UTerm, B00> {...}, so it covers 3 and 4.

impl<B00, B01> ChooseInt for UInt<UInt<UTerm, B00>, B01> {
    type Output = u8;
}

The snippet below covers only the third bit, not the second, not the first, because these are covered by the previous two impls. So it covers, 5, 6, 7 and 8.

impl<B00, B01, B02> ChooseInt for UInt<UInt<UInt<UTerm, B00>, B01>, B02> {
    type Output = u8;
}

Fast forward to the end...

The below snippet covers only the 8-th bit, hence 2^7 (128) to (2^8 -1) (255).

impl<B00, B01, B02, B03, B04, B05, B06, B07> ChooseInt for
    UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B00>, B01>, B02>, B03>,
    B04>, B05>, B06>, B07> {
    type Output = u8;
}

Am I right?

1 Like

Not quite; see u32::div_floor and u32::div_ceil. For nonnegative integers, when n ≡ 0 mod m, ⌈n/m⌉ ≡ ⌊n/m⌋ ≡ n/m, otherwise ⌈n/m⌉ ≡ ⌊n/m⌋ + 1. (Integer division involving negative integers is more complicated and irrelevant here.) Thus constructing it is more complicated than a simple +1.

So, just like how you can clone Rc with a shared reference, despite doing so requiring mutation of the reference count? (Yes.) Then you want Cell::get and set, not UnsafeCell.

How many more bits are in u64 than u32? Therein lies the answer.

2 Likes

Hi good day to you @SkiFire13,

Would you mind sharing how would you 'constrain' the branches at the type level? I agree with you that the type function also computes the 'false' branch and hence resulting in an overflow, it is akin to the compiler attempting to calculate the feasibility of the trait implementation for every type that is typenum::Unsigned.

I'm not sure how you would do that, but generally I would try to write recursive functions in a way such that no matter which branch is picked, the computation will always end.

This is also how typenum's operators are implemented, so you could just use them. For example:

use typenum::{Add1, Log2, Maximum, Shleft, U1, U8};

type NextPow2<N> = Shleft<U1, Add1<Log2<Maximum<U1, N>>>>;
type CalcMinUIntType<N> = Maximum<U8, NextPow2<Log2<N>>>;

fn main() {
    use typenum::{assert_type_eq, U16, U64, U128, U255, U256};
    
    assert_type_eq!(CalcMinUIntType<U1>, U8);
    assert_type_eq!(CalcMinUIntType<U255>, U8);
    assert_type_eq!(CalcMinUIntType<U256>, U16);
}
1 Like

This is so genius!

Hi @SkiFire13, thank you for sharing with me your solution, I think this is an excellent solution.

Would you mind sharing / elaborating on your thought processes as you go about solving this problem? More than getting solutions to my problems on this forum, I also wish to learn from people like you, so that I can contribute more in the future.