Implement only where const generic equality holds

I've got two structs:

struct Size<const N: usize>;

struct Select<
    const A: bool, 
    const B: bool, 
    // ...
    const F: bool
>;

Is a macro the right way (without nightly, I guess?) to implement for only the various valid combinations, such as:

struct ArrayDef<Dim, Sel>;

impl ValidType for ArrayDef<Size<3>, Select<true, true, false, false, false, true>> {
    type Array = [(); 3];
}

i.e. for all instances where N == {A as usize + B as usize + ... + F as usize}?

One way that can often be more convenient to work with is to skip const generics and use types, so that using trait bounds, and trait based operations, can be an option. For example using typenum - Rust which has an unsigned integer type as well as a bit type (the latter can be used like a boolean).

Here’s a quick demonstration…

#![allow(unused)]

use core::ops::*;
use generic_array::*;
use typenum::*;

use core::marker::PhantomData;

struct Size<N: Unsigned>(PhantomData<N>);

struct Select<A: Bit, B: Bit, C: Bit, D: Bit, E: Bit, F: Bit>(PhantomData<(A, B, C, D, E, F)>);

struct ArrayDef<Dim, Sel>(PhantomData<Dim>, PhantomData<Sel>);

trait ValidType {
    type Array;
}

impl<A, B, C, D, E, F, N> ValidType for ArrayDef<Size<N>, Select<A, B, C, D, E, F>>
where
    A: Bit,
    B: Bit,
    C: Bit,
    D: Bit,
    E: Bit,
    F: Bit,
    N: ArrayLength,
    UTerm: Add<A>,
    op!(UTerm + A): Add<B>,
    op!(UTerm + A + B): Add<C>,
    op!(UTerm + A + B + C): Add<D>,
    op!(UTerm + A + B + C + D): Add<E>,
    op!(UTerm + A + B + C + D + E): Add<F>,
    op!(UTerm + A + B + C + D + E + F): Same<N>,
{
    type Array = GenericArray<(), N>;
}

type Test1 = ArrayDef<Size<U3>, Select<True, True, False, False, False, True>>;
type Test2 = ArrayDef<Size<U4>, Select<True, False, True, False, True, True>>;
type Test3 = ArrayDef<Size<U4>, Select<True, False, False, False, True, True>>;

fn valid<T: ValidType>() {}
fn test() {
    valid::<Test1>();
    valid::<Test2>();
    // should fail:
    // valid::<Test3>();
}

Rust Playground

2 Likes

Ahh, typenum still, ok. Though I quite like that op! macro for assembling the <A as Add<B>>::Output type-chaining. That's something I've had different battle with, and I hadn't seen that approach yet. I'll probably try borrowing that later.

But, it is still quite a lot on the where bounds, and I'm not sure what it gains... My other option, which I might like better, is to just name the fixed iter/filter type:

enum Set { A, B, C, D, E, F }

const ALL: [Set; 6] = [Set::X, Set::Y, Set::Z, Set::RX, Set::RY, Set::RZ];

trait Axes {
    fn axes() -> Filter<IntoIter<Dir, 6>, fn(&Dir) -> bool>;

    const N: usize;
}

Am I correct to think that a static method on entirely const values would end up optimizing similarly well? I'm fine only being able to try_into() a fixed array at runtime, or just working straight with the iterator. Any thoughts?
[playground, reduced to 3 for brevity]

Could also use -> impl Iterator<Item = Set> here nowadays.

Anyways, it seems it doesn’t optimize fully, if you want to produce the whole array, even with arrayvec in place of a Vec.

For comparison, an even easier example use case where I’m just summing the values still creates a whole loop

pub fn create_a_sum() -> usize {
    let mut n = 0;
    for i in NamedSelection::axes() {
        n += i as usize;
    }
    n
}
example::create_a_sum:
        mov     qword ptr [rsp - 16], 3
        mov     word ptr [rsp - 8], 256
        mov     byte ptr [rsp - 6], 2
        xor     ecx, ecx
        xor     eax, eax
.LBB0_1:
        mov     rdx, rcx
.LBB0_2:
        cmp     rdx, 3
        je      .LBB0_5
        lea     rcx, [rdx + 1]
        mov     qword ptr [rsp - 24], rcx
        movzx   esi, byte ptr [rsp + rdx - 8]
        mov     rdx, rcx
        cmp     rsi, 1
        je      .LBB0_2
        add     rax, rsi
        jmp     .LBB0_1
.LBB0_5:
        ret

On the other hand, with a different iterator operation, it seems to work out…

pub fn create_a_sum_2() -> usize {
    NamedSelection::axes().map(|n| n as usize).sum()
}
example::create_a_sum_2:
        mov     eax, 2
        ret

so maybe not all hope is lost…

maybe let’s try to work with for_each on an array-creating version, too…

pub fn create_an_array() -> [Set; NamedSelection::N] {
    let mut array = [Set::A; NamedSelection::N];
    NamedSelection::axes().enumerate().for_each(|(i, v)| array[i] = v);
    array
}

oh, yeah, that works out great!

example::create_an_array:
        mov     ax, 512
        ret
3 Likes

Nice stuff, thank you!!

Very interesting what it takes to optimize away what can only be a single compile time knowable return value. It seems if you don't start with a declared size and do a correctly aligned map/for_each then the const pattern matches leak through?

Really I'm just looking for the right way around "error: generic parameters may not be used in const operations" / "cannot perform const operation using Self" as I do want a self-contained trait.

Perhaps I should try a const AXES: [Option<usize>; 6] in the trait instead? Then the checks are all in one place? [playground]

Well, since it gets all the birds with one stone, here is a playground with a minimal implementation in the style of typenum. On the whole it's not THAT bad and I think I can be happy with this in for now until const generics get there. Thanks again for the help!

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.