Using a macro to initialize a big array of non-Cop

问题:

I'm trying to initialize a big array of elements with the same initializer. 64 elements is just an example — I want to make it at least 16k. Unfortunately a simple

let array : [AllocatedMemory<u8>; 64] = [AllocatedMemory::<u8>{mem:&mut []};64];

won't work because the AllocatedMemory struct does not implement Copy

error: the trait `core::marker::Copy` is not implemented for the type `AllocatedMemory<'_, u8>` [E0277]
let array : [AllocatedMemory<u8>; 64] = [AllocatedMemory::<u8>{mem:&mut []}; 64];
                                        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

So I tried macros to no avail:

struct AllocatedMemory<'a, T: 'a> {
    mem: &'a mut [T],
}

macro_rules! init_memory_helper {
    (1, $T : ty) => { AllocatedMemory::<$T>{mem: &mut []} };
    (2, $T : ty) => { init_memory_helper!(1, $T), init_memory_helper!(1, $T) };
    (4, $T : ty) => { init_memory_helper!(2, $T), init_memory_helper!(2, $T) };
    (8, $T : ty) => { init_memory_helper!(4, $T), init_memory_helper!(4, $T) };
    (16, $T : ty) => { init_memory_helper!(8, $T), init_memory_helper!(8, $T) };
    (32, $T : ty) => { init_memory_helper!(16, $T), init_memory_helper!(16, $T) };
    (64, $T : ty) => { init_memory_helper!(32, $T), init_memory_helper!(32, $T) };
}

macro_rules! init_memory {
    (1, $T : ty) => { [init_memory_helper!(1, $T)] };
    (2, $T : ty) => { [init_memory_helper!(2, $T)] };
    (4, $T : ty) => { [init_memory_helper!(4, $T)] };
    (8, $T : ty) => { [init_memory_helper!(8, $T)] };
    (16, $T : ty) => { [init_memory_helper!(16, $T)] };
    (32, $T : ty) => { [init_memory_helper!(32, $T)] };
    (64, $T : ty) => { [init_memory_helper!(64, $T)] };
}

fn main() {
    let array: [AllocatedMemory<u8>; 64] = init_memory!(64, u8);
    println!("{:?}", array[0].mem.len());
}

The error message is

error: macro expansion ignores token `,` and any following
    (64, $T : ty) => { init_memory_helper!(32, $T), init_memory_helper!(32, $T) };
note: caused by the macro expansion here; the usage of `init_memory_helper!` is likely invalid in expression context

Is there any way to initialize this array without cut and pasting every initializer?

回答1:

The problem is that the expansion of a macro absolutely must be a complete and independently valid grammar element. You can't expand to a, b any more than you can expand to 42 +. There is also no way to (statically) concatenate or cons arrays in Rust; the entire array initialiser must be expanded to in one step.

This can be done using macros with push-down accumulation. The trick is that you pass the not-yet-syntactically-valid partial array expression down the recursion, instead of constructing on the way back out. When you reach the bottom of the expansion, you emit the now complete expression all at once.

Here's a macro that supports arrays of length 0 through 8, and powers of 2 up to 64:

macro_rules! array {
    (@accum (0, $($_es:expr),*) -> ($($body:tt)*))
        => {array!(@as_expr [$($body)*])};
    (@accum (1, $($es:expr),*) -> ($($body:tt)*))
        => {array!(@accum (0, $($es),*) -> ($($body)* $($es,)*))};
    (@accum (2, $($es:expr),*) -> ($($body:tt)*))
        => {array!(@accum (0, $($es),*) -> ($($body)* $($es,)* $($es,)*))};
    (@accum (3, $($es:expr),*) -> ($($body:tt)*))
        => {array!(@accum (2, $($es),*) -> ($($body)* $($es,)*))};
    (@accum (4, $($es:expr),*) -> ($($body:tt)*))
        => {array!(@accum (2, $($es,)* $($es),*) -> ($($body)*))};
    (@accum (5, $($es:expr),*) -> ($($body:tt)*))
        => {array!(@accum (4, $($es),*) -> ($($body)* $($es,)*))};
    (@accum (6, $($es:expr),*) -> ($($body:tt)*))
        => {array!(@accum (4, $($es),*) -> ($($body)* $($es,)* $($es,)*))};
    (@accum (7, $($es:expr),*) -> ($($body:tt)*))
        => {array!(@accum (4, $($es),*) -> ($($body)* $($es,)* $($es,)* $($es,)*))};
    (@accum (8, $($es:expr),*) -> ($($body:tt)*))
        => {array!(@accum (4, $($es,)* $($es),*) -> ($($body)*))};
    (@accum (16, $($es:expr),*) -> ($($body:tt)*))
        => {array!(@accum (8, $($es,)* $($es),*) -> ($($body)*))};
    (@accum (32, $($es:expr),*) -> ($($body:tt)*))
        => {array!(@accum (16, $($es,)* $($es),*) -> ($($body)*))};
    (@accum (64, $($es:expr),*) -> ($($body:tt)*))
        => {array!(@accum (32, $($es,)* $($es),*) -> ($($body)*))};

    (@as_expr $e:expr) => {$e};

    [$e:expr; $n:tt] => { array!(@accum ($n, $e) -> ()) };
}

fn main() {
    let ones: [i32; 64] = array![1; 64];
    println!("{:?}", &ones[..]);
}

The strategy here is to multiply the size of the input on powers of two, and add the remainder for non-powers of two. This is to stave off the macro recursion limit (I believe the default is 64) by making sure $n drops in value quickly.

Just to forestall the frequent follow-up question: no, you can't simplify this with arithmetic; you can't do arithmetic in macros. :)

Addendum: If you're not sure how this works, you can pass -Z trace-macros to rustc when compiling and see each macro invocation that gets expanded. Using array![1; 6] as an example, you get something like this:

array! { 1 ; 6 }
array! { @ accum ( 6 , 1 ) -> (  ) }
array! { @ accum ( 4 , 1 ) -> ( 1 , 1 , ) }
array! { @ accum ( 2 , 1 , 1 ) -> ( 1 , 1 , ) }
array! { @ accum ( 0 , 1 , 1 ) -> ( 1 , 1 , 1 , 1 , 1 , 1 , ) }
array! { @ as_expr [ 1 , 1 , 1 , 1 , 1 , 1 , ] }

回答2:

The problem with these macros is that the former one does not produce valid syntactic forms in Rust - two expressions combined by a comma is not a valid form by itself. The fact that it is "injected" into square brackets in another macro is irrelevant.

Frankly, I don't know how to do it properly with regular arrays. Absence of numbers as generic parameters is a well-known problem which precludes lots of useful patterns. If they were supported, for example, it would be possible to have a function like this one:

fn make_array<T, N: usize, F>(f: F) -> [T; N] where F: FnMut() -> T

which creates an array of arbitrary size, filling it with the result of function invocation:

let array: [_; 64] = make_array(|| AllocatedMemory::<u8>{ mem: &mut [] })

But alas, no such thing is available in Rust yet. You have to use dynamic structures like Vec instead. You can also try arrayvec, which provides a Vec-like API for some fixed-size arrays; using it you can do something like this:

let mut array = ArrayVec::<[_; 64]>::new();
for _ in 0..array.len() {
    array.push(AllocatedMemory::<u8>{ mem: &mut [] });
}
let array = array.into_inner();  // array: [AllocatedMemory<u8>; 64]