typenum inside a trait

[mkeeter]

I'm trying to use typenum to create a trait that includes both N and 1 << N (to create trees with fanout that's set at compiler-time):

extern crate typenum;
use typenum::{U1, Unsigned, Shleft};

use std::marker::PhantomData;

pub trait Log2Sized
{
    type Log2Size : Unsigned;
    type Size : Unsigned;
}

pub struct InternalNode<N>
{
    _phantom: PhantomData<N>,
}

impl<N: Unsigned> Log2Sized for InternalNode<N>
{
    type Log2Size = N;
    type Size = Shleft<U1, N>;
}

This blows up with recursive compiler errors:

error: overflow evaluating the requirement `<typenum::UInt<_, _> as std::ops::Sub<typenum::B1>>::Output` [E0275]
note: consider adding a `#![recursion_limit="16"]` attribute to your crate
note: required because of the requirements on the impl of `std::ops::Shl<typenum::UInt<_, _>>` for `typenum::UInt<typenum::UInt<typenum::UInt<typenum::UInt<typenum::UInt<typenum::UInt<typenum::UInt<typenum::UTerm, typenum::B1>, typenum::B0>, typenum::B0>, typenum::B0>, typenum::B0>, typenum::B0>, typenum::B0>`
note: required because of the requirements on the impl of `std::ops::Shl<typenum::UInt<_, _>>` for `typenum::UInt<typenum::UInt<typenum::UInt<typenum::UInt<typenum::UInt<typenum::UInt<typenum::UTerm, typenum::B1>, typenum::B0>, typenum::B0>, typenum::B0>, typenum::B0>, typenum::B0>`
...

Any thoughts on where I'm going wrong? I'm fairly new to Rust and type-level programming, so I may be making an obvious mistake...

[paholg]

It does not appear to me that you are doing anything wrong, but that the compiler is trying to evaluate types too eagerly.

It is possible that changing some of the internals of typenum will fix this for you. In particular, instituting the work-around used here just might do it.

I'm pretty busy this week, but will hopefully be able to work on it starting early next week.

In the meantime, a workaround may be to have a caller perform the Shleft. That is, instead of using InternalNode::Size, you could get rid of the associated type Size and use Shleft<U1, InternalNode::Log2Size>, assuming that is appropriate for your use case.

[mkeeter]

Darn, I was hoping there was an obvious error.

Moving the shift to the caller has the same issue, with code that looks like

pub trait Log2Sized
{
    type Log2Size : Unsigned;
}

pub struct InternalNode<T, N>
    where N: Unsigned
{
    data: GenericArray<Box<T>, Shleft<U1, <InternalNode<T, N> as Log2Sized>::Log2Size>>,
}

impl<T, N: Unsigned> Log2Sized for InternalNode<T, N>
{
    type Log2Size = N;
}

(the end goal is to have GenericArrays that are specified at compile-time.

This is so easy in C++ with integer template parameters – I'll dig through a few of the libraries that use typenum and see if there's anything clever to borrow.

[paholg]

Aha! I got it to work, although without the Log2Sized trait. Looking at your second example, there may be an issue with calling the implementation of Log2Sized trait for InternalNode in the definition of InternalNode.

In any case, the main issue is with the compiler not giving useful error messages; it gets stuck in an infinite loop instead of telling you that you need to specify trait implementations in where clauses. You can get better messages by using Add instead of Shl, and then switching back to Shl once all the errors are taken care of.

Anyway, this works:

pub struct InternalNode<T, N> where
    U1: Shl<N>,
    Shleft<U1, N>: Unsigned + ArrayLength<Box<T>>,
{
    data: GenericArray<Box<T>, Shleft<U1, N>>,
}

[mkeeter]

Awesome – from that pattern, I've put together a more complete system that compiles just fine:

pub trait Log2Sized
{
    /// This node subdivides into 2^Size subtrees on each axis
    type Log2Size : Unsigned;
    /// This node contains 2^Accum voxels on each axis
    type Log2Accum : Unsigned;
    /// Size = 2^Log2Size
    type Size : Unsigned;
    /// Voxels = 2^Log2Accum
    type Voxels : Unsigned;
}

pub struct InternalNode<T, N>
    where U1: Shl<Prod<N, U3>>,
          Shleft<U1, Prod<N, U3>>: ArrayLength<Box<T>> + ArrayLength<bool>,
          N: Unsigned + Mul<U3>,
{
    data: GenericArray<Box<T>, Shleft<U1, Prod<N, U3>>>,
    value_mask: GenericArray<bool, Shleft<U1, Prod<N, U3>>>,
    child_mask: GenericArray<bool, Shleft<U1, Prod<N, U3>>>,
}

impl<T, N> Log2Sized for InternalNode<T, N>
    where T: Log2Sized,
          U1: Shl<N> + Shl<Prod<N, U3>> + Shl<Sum<N, <T as Log2Sized>::Log2Accum>>,
          Shleft<U1, N>: Unsigned,
          Shleft<U1, Prod<N, U3>>: ArrayLength<Box<T>> + ArrayLength<bool>,
          Shleft<U1, Sum<N, <T as Log2Sized>::Log2Accum>>: Unsigned,
          N: Unsigned + Mul<U3> + Add<<T as Log2Sized>::Log2Accum>,
          Sum<N, <T as Log2Sized>::Log2Accum>: Unsigned,
{
    type Log2Size = N;
    type Log2Accum = Sum<N, <T as Log2Sized>::Log2Accum>;

    type Size = Shleft<U1, N>;
    type Voxels = Shleft<U1, Sum<N, <T as Log2Sized>::Log2Accum>>;
}

Thanks for the help!