Generate static arrays during build time

Update 2022-09-27

It's more than two years since I've published this article and Rust and its ecosystem has improved a lot. Unfortunately I will not update or correct this article in the near to mid future, maybe never. However I believe that most of the things I wrote are still correct. However due to the improvements in Rust and its ecosystems, some of the limitations I identified two years ago have improved as well. The following items have caught my attention in the last two years:

• A lot more const fn in the standard and core library. This could improve the const fn option.
• The [env] attribute that can be defined in Cargo.toml, find more information about this here. This could improve the build.rs solution if the necessary environment variables could be fixed (if fixable) in a downstream dependency of the crate that requires these environment variables.

I haven't checked these options in more detail.

Introduction

Memory usage and management is crucial in embedded systems software. Dynamic memory is often not available or avoided to reduce the risk of runtime errors (e.g. out-of-memory errors). Therefore the to-be-used memory is often defined and allocated during compile time. For example, one could define and allocate a buffer used to temporarily store a received message:

static mut MESSAGE_BUFFER:[u8;200] = [0;200];

Such a buffer would be reserved in volatile memory, in order to be modifiable during runtime (in the end it is mutable).
Data that is constant during runtime can be defined as const (when its small) or static (when its larger) in Rust. This gives the compiler the opportunity to reserve space for this data at a specific memory location, see the Rust language reference, chapter 6.10, Static Items:

A static item is similar to a constant, except that it represents a precise memory location in the program.

Each constant is usually inlined by the compiler according to the Rust language reference, chapter 6.9, Constant Items:

Constants are essentially inlined wherever they are used, meaning that they are copied directly into the relevant context when used

This means, when a large array is needed as constant, it makes sense to define it as static instead of const. For example,
you don't want to inline a byte array with 64000 bytes each and anytime you use it in your source code. This would unnecessary bloat your binary code.

Oftentimes embedded software, that requires non-trivial but constant data during runtime, this data is generated as source code and compiled together with rest of the source code. For this, more or less sophisticated tools are used to define the code and generate it. This is, for certain use cases, unavoidable. For example if the data required is to be define by the user of the software to fulfill a project-specific use case. However, what if the data can be generated during compile, since there is an algorithm to do this that requires little input by the user?

For my use case (described below), I did explore this idea: Generate an array (potentially thousands of f64) during compile time with the size of the array as a constant literal input (by this, I mean something like 1206 in your source code).
However, I want to hide this generation step as much as possible for the users of a potential library, for two reasons:

1. The array I generate is only used internally, users do not need to know this, nor should they be bothered to generate the array themselves (however, the runtime impact, this means the static memory size used, should be communicated openly)
2. I want an interface, so that a user can configure a cargo feature in order to decide which specific implementation they want, without changing their source code

For this a tried to solve my problem by exploring four different options:

• Constant functions and constant generics
• Macro rules macros
• Build scripts
• Procedural macros

This article will shortly introduce and skim-through these options to identify if they can solve my specific problem, their advantages and disadvantages from my point of view. All of these options are much more complex as I can describe them in this already long article, but I added as much references for more in-depth introduction as I did find.

Short disclaimer about the source code that is in this article: It usually lacks proper error handling (yeah, I know) and is more often than not un-idiomatic Rust (sorry). The source code is intended to explain the specific solution but is not written perfectly. Do not copy and paste it for your projects. I do appreciate everyone who can point me to a better, more idiomatic solution.

TL;DR

Constant functions & constant generics (with Rust 1.46), procedural macros (ideally with 1.45) and build scripts do work but all have drawbacks. Macro rules macros may work but are complex.

The use case

I'll be honest with you, my use case is not a traditional embedded use case. It is rather a challenge for myself to solve a problem with #[no_std] that perfectly can be solved using dynamic memory. So the idea is: I want to generate so called quasi-random numbers. The name is misleading, since quasi-random numbers have a clear structure and are not really random. That's why they are more correctly termed as low discrepancy sequences.
But what's the difference between pseudo random numbers and a quasi random numbers? (As an aside: a pseudo random number generator generates random numbers with an algorithm this means deterministically. Hence the name pseudo.)
See below pseudo random numbers (as 2D points) generated with the randomizecrate and plotted with the plotlib crate:

As you can see the points seem to distributed pretty randomly. They are clustered at certain spots while other areas in the plot are rather empty.

Below a plot of a quasi-random sequence:

The points are pretty evenly distributed in the complete area. There are no clusters. There seems to be a real structure. I would not call this random at all. The quasi random numbers were generated by my own crate, which I hopefully will publish in the future. Plotted again with the plotlib crate crate. The sequence that was generated was the R2 sequence which is brilliantly introduced in this article:

The Unreasonable Effectiveness of Quasi random Sequences

So for what is this useful? For example for Monte Carlo Simulations. This is a numerical integration technique which uses random numbers. For some integrations, especially in multi-dimensions, it is beneficial to use quasi random numbers over pseudo random numbers since then the Monte Carlo simulation converges faster or simplified said, you need less program runtime to get your result. There are obviously bounds that prove this mathematically (see Quasi Monte Carlo method as a starter) but there is also my layman's explanation: When you want to integrate a function in a space, you want to sample the space as uniformly as possible to evaluate your function in every part of the space evenly. With clusters you may shift the average value of your function evaluations towards these clusters, hence your average value is somehow "biassed" towards these random clusters. This can be overcome by using more samples so that clusters lose their importance. Or you use a random sequence that is so non-random that it fills the space up more evenly: quasi random numbers.

What does this have to do with generating static arrays? There are two sequences I am focusing on at the moment. The Rd sequence, which is a generalization of the R2 sequence mentioned above, but with d dimensions. And the Sobol sequence. Both have in common, that the sequence is constructed by one or more constants per dimension. For the Rd sequence, there is one f64 value per dimension (can be u64 as well, as an aside). These can be called alphas or alpha values. For Sobol there are 32 u32 per dimension which are called direction numbers. As mentioned above, these numbers are constant and can be arranged into an array (at least it makes sense to do so). Since I want to implement this #[no_std] I cannot allocate these during runtime without providing an allocator. Therefore it makes sense to generate this array during compile time since usually the dimension is constant as well.
If the dimension is large (>1000) these arrays should be static as I mentioned above.
Additionally I want to put both sequences behind one interface (i.e. a trait):

pub trait LowDiscrepancySequence {
    fn element(&self, n: usize, dim: usize) -> f64
}

This means the user of my library can choose the sequence with by selecting a cargo feature (either "rd" or "sobol") and the dimension at compile time and gets the sequence without needing to know too much implementation details:

// defined and implemented in my crate
pub fn create_sequence(dimension: usize) -> impl LowDiscrepancySequence {
    // ...
}

// usage
use qrand_core::create_sequence;
let sequence:LowDiscrepancySequence = create_sequence(2);

This means, if there is a need to change the sequence (e.g. from Rd to Sobol), then the source code needs not to be changed: the implementation details of the sequence is hidden from the user. This is my perfect world. However there are these aforementioned arrays and they differ significantly between these two sequences. Therefore I want to hide them as much as possible from the user as possible. This may not be necessary, however I find this problem interesting and so I went out to try to solve it.

Before I go through the options I evaluated I want to shortly introduce what needs to be calculated on compile time.

For the Rd low discrepancy sequence, we need alpha values, one for each dimension we plan to use. This means, we hold an array that contains these alpha values. Each of the alpha value is calculated from one start value, called phi. This phi is specific for a dimension and can be calculated as follows:

fn calculate_phi(dimension: usize) -> f64 {
    let mut phi: f64 = 2.0;
    // power is always 1 / (dimension + 1)
    let power: f64 = f64::from(dimension as u32 + 1).recip();
       // phi is approximated, I loop 25 times to get a reasonable approximation on my machine
    for _ in 0..25 {
        phi = phi + 1.0;
        phi = phi.powf(power);
    }
    phi
}

For this article it is not so much important what and how this is calculated but it is important that I need a loop to calculate phi (see the aforementioned article The Unreasonable Effectiveness of Quasi random Sequences and its references for more details on why and how to calculate phi).

The alphas can then be calculated like:

fn create_alphas(dimension: usize) -> Vec<f64> {
    let mut alphas: Vec<f64> = Vec::with_capacity(dimension);
    let phi = calculate_phi(dimension);
    let inv_g = phi.recip();
    let dim = dimension as u32;
    for i in 0..dim {
        alphas.push(inv_g.powf(f64::from(i + 1)).fract());
    }
    alphas
}

Again, it is not that much important how, but that I need to loop through the dimensions. I use a vector here since it is not possible to return an array with the size given as a parameter. For example the following code does not compile:

// does not compile
fn create_array(size: usize) -> [f64; size] {
    [0.0; size]
}

You get error E0435 saying that you tried to use a non-constant value in a constant. There is a way to do this, which will be explained in the constant function section below.

I do not present how the direction numbers for the Sobol Sequence, since it would be worth an own article. I may write this article, but for the moment, the alphas of the Rd sequence suffice to explain the use case.

Finally, as I mentioned above, there are two reasons, why this is not a good embedded use case. The first reason is, that for large dimensions a large amount of (constant) memory is required. For example, if we use the Rd sequence for 1000 dimension we need 8000 bytes of memory for the array. For the Sobol sequence this is 64000 bytes. Although it is part of the program memory, since compiled into the binary, it still makes a huge binary, at least for embedded systems. The other reason is even more important: I don't have a good use case for quasi random numbers (or Monte-Carlo simulation) required in an embedded device (maybe someone can add some in the comments). Still, as mentioned above, I did like the challenge to solve this problem with #[no_std] and did learn a lot trying it. And my idea was to share some of the key points I learned with you.

Option 1: constant functions

Using constant evaluations looks like a promising idea for my use case of generating large, static arrays during compile time. But there are several problems. I will get into these step-by-step. However, before I do so, I will shortly introduce constant evaluations and constant functions.

A constant evaluation is ...

... the process of computing the result of expressions during compilation.

(see The Rust Reference - Constant evaluation)

This means, a result is computed during compilation. This can be a simple expression or the initialization of a constant value, like:

const PI:f64 = 3.14;

But also the execution of constant functions. The relevant part I am interested in, is stated at The Rust Reference - Functions - Const Functions:

When called from a const context, the function is interpreted by the compiler at compile time.

A simple example of a constant function could be:

const fn divide_by_two(value:u64) -> u64 {
    value >> 1
}
const CONSTANT:u64 = divide_by_two(32); // 16

Nice to know as well: A const function can also be called outside of a constant context. But this also means, the constant function will be part of your final binary.

But there a limitations what a constant function can do, in the The Rust Reference - Functions - Const Functions there is a list of permitted structures in const functions, which is even more restrictive than what you can do in regular constants. And this was one of the reasons why constant functions did not solve my problem, at least until Rust 1.46. With Rust 1.46, constant functions were improved, by adding, beyond other improvements, the possibility to use while and loop loops (see The Rust Blog - Announcing Rust 1.46.0 - const fn improvements). Unfortunately for loops are not supported.

However while and loop are already pretty powerful so that the following code does work with 1.46:

// constant functions is an unstable feature, I needs to be activated to use it
#![feature(const_fn)]

const fn sum(array:&[f64]) -> f64 {
    let mut i = 0;
    let mut sum = 0.0;
    while i < array.len() {
        sum += array[i];
        i += 1;
    }
    sum
}

I want to point out, that I need to enable constant functions as feature, otherwise it won't compile. That is why I added the #![feature(const_fn)] and will do so for every constant function I present.

I presented above code that calculated phi using a for loop, As mentioned above, this code does not compile if defined as const function:

// constant functions is an unstable feature, I needs to be activated to use it
#![feature(const_fn)]

// does not compile
const fn calculate_phi(dimension: usize) -> f64 {
    let mut phi: f64 = 2.0;
    // power is always 1 / (dimension + 1)
    let power: f64 = f64::from(dimension as u32 + 1).recip();
       // phi is approximated, I loop 25 times to get a reasonable approximation on my machine
    for _ in 0..25 {
        phi += 1.0;
        phi = phi.powf(power);
    }
    phi
}

The Rust compiler rejects this code with error E0744:

error[E0744]: `for` is not allowed in a `const fn`
  --> const_rd_alphas/src/lib.rs:7:5
   |
   | /     for _ in 0..25 {
   | |         phi += 1.0;
   | |         phi = phi.powf(power);
   | |     }
   | |_____^

But, instead of using a for loop, I can now use a while loop:

// constant functions is an unstable feature, I needs to be activated to use it
#![feature(const_fn)]

const fn calculate_phi_for(dimension: usize) -> f64 {
    let mut phi: f64 = 2.0;
    // power is always 1 / (dimension + 1)
    let power: f64 = f64::from(dimension as u32 + 1).recip();
    // phi is approximated, I loop 25 times to get a reasonable approximation on my machine
    let mut i = 0;
    while i < 25 {
        phi += 1.0;
        phi = phi.powf(power);
        i += 1;
    }
    phi
}

But here I get several E0015 errors, for example:

error[E0015]: calls in constant functions are limited to constant functions, tuple structs and tuple variants
  --> const_rd_alphas/src/lib.rs:42:15
   |
42 |         phi = phi.powf(power);
   |               ^^^^^^^^^^^^^^^

Which means I can only call other constant functions from a constant function, which makes totally sense. If you want to use constant function a in a constant context and this function uses function b then b must also be constant. However, this means I need to implement all the non-constant standard library functions I need to use. This would be the functions powf and recip for floating point values (f64). And instead of using f64::from I can cast with the as keyword. Then the calculate_phi code looks like this:

// constant functions is an unstable feature, I needs to be activated to use it
#![feature(const_fn)]

fn calculate_phi(dimension: usize) -> f64 {
    let mut phi: f64 = 2.0;
    // power is always 1 / (dimension + 1)
    let power: f64 = recip((dimension + 1) as f64);
    let mut i = 0;
    // phi is approximated, I loop 25 times to get a reasonable approximation on my machine
    while i < 25 {
        phi = phi + 1.0;
        phi = powf(phi, power);
        i += 1;
    }
    phi
}

But let's pause for one moment: recip is trivial to implement (it's basically f(x)=1/x but I guess it makes sense to implement it carefully, robust and efficient). But it is a different story for powf: This is not that trivial since you need to implement f(x,y)=x^y with y being a floating point number (it is easier with an unsigned integer exponent, though). If I want to implement this in software, I need approximate the value numerically and this needs to be well enough. It is possible to do so (maybe even worth another article how to do it) but I did not do it for this article since it is not important for this article how this is done, but that I would have to do it, if I want to use constant functions for my use case. I find that the necessity to implement these functions is inconvenient at best, although I assume that more and more functions of the standard library will be implemented as const so this should be a temporary temporary issue.

But let's go on with constant functions and assume, my calculate_phi and all the other functions are correctly implement as constant functions. I still need to create an array instead of a vector (as I did above). For this I need to use the constant generic feature. Constant generics are a way to define a generic parameter that is constant and has a "trait bound". For example, the create_array method mentioned above can be defined like this:

#![feature(const_fn)]
#![feature(const_generics)]

const fn create_array<const DIM: usize>() -> [f64; DIM] {
    [0.0; DIM]
}

However, constant generics are not only an unstable feature but it is incomplete. This means you need the nightly compiler. So you need to install the nightly compiler with rustup:

rustup install nightly

And build with +nightly flag using cargo:

cargo +nightly build

(There are more options to use the nightly compiler, I just presented my favorite.)

Back to creating the alphas. The code for this could look like below:

#![feature(const_fn)]
#![feature(const_generics)]

const fn create_alphas<const DIM: usize>() -> [f64; DIM] {
    let dimension = DIM as u32;
    let mut array: [f64; DIM] = [0.0; DIM];
    let phi = calculate_phi(DIM);
    let inv_g = recip(phi);
    let mut i = 0;
    while i < dimension {
        array[i as usize] = fract(powu(inv_g, i as usize + 1));
        i += 1;
    }
    array
}

I also added a powu function, a power function with unsigned exponent (which is a lot easier then powf) and also a fract implementation, which returns the fractional part of a floating point number.
THis means I can finally implement my create_sequence function like this:

#![feature(const_fn)]
#![feature(const_generics)]

use const_rd_alphas::create_alphas;
use low_discrepancy_sequence::LowDiscrepancySequence;

mod rd;
use rd::new_sequence;

pub const fn create_sequence<const DIM: usize>() -> impl LowDiscrepancySequence {
    static ALPHAS: [f64; DIM] = create_alphas::<DIM>();
    new_sequence(&ALPHAS)
}

Not so fast, there are two more problems:

1. Constant functions cannot refer to static parameters
2. Usage of the outer constant generic parameter

It is not allowed to refer to a static from a constant function. This is compile error E0013. We can change it to a constant instead of a static, but remember, constant may be inlined (as I already mentioned above). This means if the constant is used at several locations, it may be copied at each of these positions and then be may lead to code bloat.

As to the second problem: I cannot use the DIM constant generic from my create_sequence function in the create_alphas function. This means I use the generic parameter from my outer function (here create_sequence) in my inner function (here create_alphas) which is not allowed. This is error E0401.
I could split up the creation of the alphas and the creation of the sequence into two methods. But then I am not hiding the implementation details anymore, and switching from Rd to Sobol sequence would at least mean changing the internal data types from f64 to u32. And users of my library need to call two methods in the right order to generate the quasi random numbers. This means the code could look something like this:

// qrand_core/src/lib.rs
pub fn create_sequence_data<const DIM:usize>() -> [f64;DIM] /* would be an u32 array in case of Sobol */ {
    // ...
}

pub fn create_sequence(data: &'static [f64] ) -> impl LowDiscrepancySequence {
    // ...
}

// user_application/src/main.rs
// usage
static sequence_data:[f64;2] = create_sequence_data<2>();
fn main() {
    let sequence = create_sequence(&sequence_data);
}

However, I can hide this behind a macro_rules macro (below is more information on how to do this). In some of the other options, it is also required to call two functions in correct order (and hiding this detail in a macro_rules macro). But it solves the first problem (referring to a static in a constant function, E0013). And it also means that using constant functions and constant generics do work to generate large arrays during compile time, with some "small print".

Conclusion using constant functions

Using constant functions and constant generics enable creating large arrays during compile time. However there are some drawbacks: All non const functions I use from the standard library need to be implemented by either myself or I wait for the standard library to support them as constant functions. Implementing these functions myself may be challenging and error-prone in some cases (that's why I am usually pretty happy, for the functions already implemented in the standard library). Another drawback is using the nightly compiler to enable constant generics. No showstopper but I like to stick on stable and I guess it makes sense especially for embedded use cases. The last drawback I see, is that constant functions are part of the final binary, since they can be used during runtime and not only during compile time. This results in a larger binary which can be critical for an embedded use case. Especially if I already generate large arrays into the binary. Finally I still leak some implementation detail, since a user must call create_sequence_data and then create_sequence before using the sequence. This can be hidden in a macro_rules macro (see below) but still is not ideal, from my point of view.

Option 2: macro_rules macros

Another option I looked into are macro_rules macros. These macros match expressions and expand to code during runtime. The below example can be used to hide the necessity of calling the two functions above (create_sequence_data & create_sequence) in correct order by packing them into such a macro:

#[macro_export]
macro_rules! create_seq {
    ($dimension:expr) => {{
        use constant_function::{create_sequence, create_sequence_data};
        const ALPHAS: [f64; $dimension] = create_sequence_data::<$dimension>();
        let sequence = create_sequence(&ALPHAS);
        sequence
    }};
}

The macro is called create_seq and works like a function like macro. It can be called like a function but an exclamation mark ! must be added to its name. Here is an example usage:

let sequence = create_seq!(2);
let element = sequence.element(0, 0).unwrap_or(1.1);

As "argument" one can give an expression to the create_seq macro. In Rust, expressions can be several things, in The Rust Reference - Expressions you can find a much better explanation what expressions can be. In my case, I use the expression called $dimension as an constant usize value, for example to create the ALPHAS array. This means, it works with a literal that can be a constant usize like 2 or const dim:usize = 2; but does not work for something like const dim:&str = "2"; obviously.

As mentioned above, macros first match the given argument or arguments and expand the code. The match part is everything before the arrow => while the expanding part is everything behind the arrow. You can define several branches in your match. For example:

#[macro_export]
macro_rules! create_seq {
    ($dimension:expr) => {{
        use constant_function::{create_sequence, create_sequence_data};
        const ALPHAS: [f64; $dimension] = create_sequence_data::<$dimension>();
        let sequence = create_sequence(&ALPHAS);
        sequence
    }};
    () => {{
        create_seq! {1}
    }};
}

This is the macro from above, but its second branch is used whenever the macro create_seq is called without any argument at all. It then calls the macro again with the argument 1 instead. This means, one can create a sequence like this:

let sequence = create_seq!();
let element = sequence.element(0, 0).unwrap_or(1.1);

Now I want to come to the expansion part of the macro. The very helpful tool cargo-expand helps to expand macros, to help debugging etc.. For example the following call to the macro:

let sequence = create_seq!();

expands to the following code:

let seq = {
    use constant_function::{create_sequence, create_sequence_data};
    const ALPHAS: [f64; 1] = create_sequence_data::<1>();
    let sequence = create_sequence(&ALPHAS);
    sequence
};

macro_rules macros are very powerful and can do a lot of more than what I showed above. Better and more complex examples for macro_rules macros can be found at The Little Book of Rust Macros and Non-trivial macros.

I have only developed a basic idea how I could create the array I need with a macro_rules macro but did not implement it. The reason is that it's too complex, for me at least. However, if someone is more familiar with macro_rules macros I can recommend writing an article about the process to get to the solution. I would be very happy to reference it here.

From my point of view there are two relevant patterns of macros that can be used to generate the array during compile time. The first one is incremental TT munching, brilliantly described at The Little Book of Rust Macros - Incremental TT munchers. Here the input is processed incrementally and recursively. The second pattern is push-down accumulation, see again The Little Book of Rust Macros - Push-down Accumulation for more details. Here a token sequence can be build up incrementally from incomplete constructs.

So if the macro_rules macro would basically look and be used like this:

macro_rules! create_sequence_data {
    // here the magic happens ;)
}

// usage
create_sequence_data(2);

// which expands to something like this
static ALPHAS:[f64;2] = [0.7548776662466927, 0.5698402909980532];

The macro implementation needs to calculate the phi value required for the given dimension value literal. Then the macro would somehow deconstruct the given usize literal dimension value into a sequence or recursion of the usize values 0..dimension. For each of the dimensions, the alpha values would be calculated using the before calculated phi value and combines these values together into the final array. Obviously it makes sense to split up the macro into "smaller" macros, called by the create_sequence_data macro, for example:

• One calculates phi
• One deconstructs the given dimension value
• One calculate an alpha value given phi and an usize value of the range 0..dimension
• One combines the alpha values into the array

Conclusion using macro_rules macros

Besides the fact, that I only presented an idea using macro_rules macros there are two more issues with this option, why I would not use it. The first is these quotes from The Little Book of Rust Macros - Counting:

This is a fine option for smallish numbers, but will likely crash the compiler with inputs of around 500 or so tokens [...]
The compiler must parse this into an AST, which will produce what is effectively a perfectly unbalanced binary tree 500+ levels deep. [...]
This particular formulation will work up to ~1,200 tokens.

From my understanding the counting use case described above is similar to my use case, this means it could be possible that generating a larger array may lead to a compiler crash. This is very unlucky.

The other issue I have is with the complexity. I am obviously still learning Rust but I find complex macro_rules macros hard to read and write. They are hard to debug and hard to modify. They are also hard to test. This is from my perspective not an ideal solution.

Option 3: Build scripts

The next option I (successfully) tried is using build scripts (see The Rust Reference - Build Scripts). This enables executing a more or less complex program during compiling the crate. This means I can create the array I need during the build step, simply as another rs file and use this module in another module of my crate. This means the array, its content etc. is completely hidden for the user. For example, my build script build.rs could look like this:

// qrand_core/build.rs

// used to generate the alpha values
use rd_alphas::create_alphas;
// primarily used for writing the file
use std::{env, fs, path::Path};

fn main() {
    // I need a way to get the dimension during compile time.
    // Here, for simplicity reasons, I hard-coded it to be 2.
    // See below, how to get the dimension during compile time.
    let dimension: usize = 2;

    // creating a string with the alpha values
    let mut array_string = String::from("static ALPHAS:[f64; ");
    array_string.push_str(dimension.to_string().as_str());
    array_string.push_str("] = [\r\n");
    let alphas = create_alphas(dimension);
    for alpha in &alphas {
        // a little bit of formatting is happening as well
        array_string.push_str("\u{20}\u{20}\u{20}\u{20}");
        array_string.push_str(alpha.to_string().as_str());
        array_string.push_str(",\r\n");
    }
    array_string.push_str("];\r\n");

    // write the string to a file. OUT_DIR environment variable is defined by cargo
    let out_dir = env::var("OUT_DIR").unwrap();
    let dest_path = Path::new(&out_dir).join("alphas.rs");
    fs::write(&dest_path, array_string).unwrap();
}

The build.rs file is usually placed at the top level of a crate (this means parallel to Cargo.toml, src, etc.). One can also add build specific dependencies, which is great. These dependencies are only used during build time and do not end up in the final binary. For example, I added my own crate rd_alphas as build dependencies:

[build-dependencies]
rd_alphas = {path="../rd_alphas"}

I don't need the code to create alphas during runtime, one of the reasons I want to create large static arrays during compile time. So this is great.

But how do I access this generated file in my library source code? The answer are the include, concat and env macros. include parses a file as an expression or an item. In our case our file contains: static ALPHAS:[f64;2] = [0.7548776662466927, 0.5698402909980532]; which will then be added as expression in our library source code. concat concatenates literals into a string slice. This will help us to create the path to our generated alpha.rs file. env will finally inspect an environment variable during compile time and expand it to a &'static str. This means, to include our generated alpha.rs file we need to add the following line to our library source code:

include!(concat!(env!("OUT_DIR"), "/alphas.rs"));

This will include the content of alpha.rs during compile time as an expression (static ALPHAS:[f64;2] = [0.7548776662466927, 0.5698402909980532];) to our source code from the path given by the environment variable OUT_DIR and my file name for my alpha values (alphas.rs). OUT_DIR is an environment variable set and used by cargo and it defines the directory in which all output is created. This is where the alphas.rs file is written to. This means it is part of the target folder. It is written before the library is compiled and therefore found during compile time of the library. The included alphas.rs enables me to use the static variable ALPHAS just like I added it to the source code. However its contents are generated during compile time. So my interface (create_sequence) can be implemented in the following way:

// qrand_core/src/lib.rs

// the crate which defines the interface for LowDiscrepancySequences
use low_discrepancy_sequence::LowDiscrepancySequence;

// my internal, non-public module for the Rd sequence
mod rd;
use rd::new_sequence;

// including the generated alphas.rs
include!(concat!(env!("OUT_DIR"), "/alphas.rs"));

// my public interface which hides all the details about the alphas
pub fn create_sequence() -> impl LowDiscrepancySequence {
    new_sequence(&ALPHAS)
}

I can even omit the dimension argument, since this argument would not be used anyways. The dimension is defined by the size of the ALPHAS static variable which is created in the build script.

In the above example build script the dimension was hard coded to 2, which is not exactly what I want. I want that the user can set an arbitrary dimension during build time, but how? The solution I came up with, is using an environment variable. This means, when my library is build, the user sets the DIMENSION environment variable before calling cargo build, for example like this:

DIMENSION=1000 cargo build

Then my build script can use this environment variable to generate the array in the given size:

// src/main.rs

// used to generate the alpha values
use rd_alphas::create_alphas;
// primarily used for writing the file
use std::{env, fs, path::Path};

fn main() {
    // get the DIMENSION environment variable or panic
    let dimension = usize::from_str_radix(env::var("DIMENSION").unwrap().as_str(), 10).unwrap();

    // creating a string with the alpha values
    let mut array_string = String::from("static ALPHAS:[f64; ");
    array_string.push_str(dimension.to_string().as_str());
    array_string.push_str("] = [\r\n");
    let alphas = create_alphas(dimension);
    for alpha in &alphas {
        // a little bit of formatting is happening as well
        array_string.push_str("\u{20}\u{20}\u{20}\u{20}");
        array_string.push_str(alpha.to_string().as_str());
        array_string.push_str(",\r\n");
    }
    array_string.push_str("];\r\n");

    // write the string to a file. OUT_DIR environment variable is defined by cargo
    let out_dir = env::var("OUT_DIR").unwrap();
    let dest_path = Path::new(&out_dir).join("alphas.rs");
    fs::write(&dest_path, array_string).unwrap();

    // set reasons to rebuild
    println!("cargo:rerun-if-env-changed=DIMENSION");
}

There is one further important detail in the last line of the main function:

println!("cargo:rerun-if-env-changed=DIMENSION");

This println instructs cargo to re-execute the build script whenever the DIMENSION environment variable has changed. This means when the variable is changed, the build script is called again with the new value. This is called change detection, which makes sense to only let cargo execute the build script if necessary. The possibilities to define rerun can be found at The Cargo Book - Build Scripts - Change Detection. Without this, the build script would not be re-executed even when the DIMENSION environment variable would change. So if a user defines this variable to be 1000, but later finds out that the dimension should be 2000, the build script would not have created the array with dimension 2000. But with the instruction cargo:rerun-if-env-changed=DIMENSION. This means, using build scripts does work, enabling the creation of arbitrarily large arrays during compile time and a clear abstraction of this fact from the user.

However, what I don't like about this solution is, that every user of my library must compile its own application with the environment variable set (for example as shown above or using other ways). This is not a showstopper but it is definitely not very common. Unfortunately I did not find a better option than using the environment variables, but there are only two options for inputs to the build script, see The Cargo Reference - Build Scripts - Inputs to Build Script:

When the build script is run, there are a number of inputs to the build script, all passed in the form of environment variables.

In addition to environment variables, the build script’s current directory is the source directory of the build script’s package.

So the first option is using environment variables, which I find uncommon and therefore suboptimal. The second option is to access files in the directory of the build scripts. This is a great solution for an application where this file can be changed. I don't see it possible to be used in a crate to change files in the directory of a crate that is used as a dependency (nor should it be possible if one thinks about it).

I originally thought, that a user of my library could use a build script to emit an environment variable (analog to DIMENSION) which is then used by my build script to generate the array with the defined dimension. This idea is similar to the idea of the openssl-sys crate which is described at The Cargo Reference - Build Scripts Examples - Conditional Compilation. The build script of this crate identifies the installed OpenSSL version and "communicates" it to the rust-openssl crate which uses it for conditional compilation. However this only works for a dependency to its dependent(s). And this makes sense: A dependency is usually build before its dependents and hence its build scripts are executed before the build scripts of the dependents. But this means, this idea (a build script in the dependent application or crate) does not work, at least at the moment.

Conclusion build scripts

I like this solution a lot. The array is clearly generated during build time. The code to generate the array is not part of the binary since it is called during the build. The array is very much "hidden" from the user: It is an implementation detail. But as mentioned above, the usage of an environment variable to build a library is a drawback for me. I am also not so sure if I really appreciate the fact that no dimension argument is needed to create the sequence, at least from a user standpoint. For me it feels a little bit like magic.

Option 4: procedural macros

The last option I tried out (successfully) were procedural macros. Procedural macros come in three different kinds: function-like macros, derive macros and attribute macros (see The Rust Reference - Procedural Macros). Function-like macros are the kind of macro relevant for my use case. They are, from a conceptional standpoint, pretty similar to the macro_rules macros option: There is a macro, which is called like a function, and this macro generates the array and expands it into the source code during compile time. However, procedural macros are implemented differently then macro_rules macros. The first difference is, that procedural macros are created in their own crate. This is indicated in the procedural macro crates Cargo.toml file in this way:

# Cargo.toml
[package]
# ...

[lib]
proc-macro = true

[dependencies]
# ...

A function like macro is then implemented like a normal public function, but with a #[proc_macro] attribute. This function has a TokenStream input and output. A TokenStream is a representation of

an abstract stream of tokens, or, more specifically, a sequence of token trees.

(See Rust API documentation - TokenStream)

Simplified said, a TokenStream represents the Rust source code that is passed to the macro function during compile time. A simple example can be a Derive attribute (see The Rust Reference - Derive). A #[derive(Debug)] on a struct will enable debug information through the ? formatting (see also Rust API Documentation - Debug). The TokenStream which is passed to the derive macro function is the representation of the struct. The output TokenStream then also contains a representation of Rust source code. This means for the #[derive(Debug)] example, that the implementations of all functions required by the Debug trait. Parsing the input TokenStream and creating the output TokenStream is obviously not trivial. If you have complex TokenStream input, then thesyn crate is ideal to help parsing it. Its congenial partner is the quote crate which simplifies generating the output TokenStream.
Fortunately, parsing and generating the source code is trivial for my use case, especially the parse function from str is of help (see Rust API documentation - str - parse. It can parse a string into a TokenStream. Additionally my macro can only accept literals of unsigned values (like 2 or 1000). Since the input to a procedural function like macro is a TokenStream, this TokenStream can only represent what is given as argument. Assume you defined a constant (like const dim:usize = 1000;) and then called the macro (create_sequence(dim)), then the TokenStream is actually, and rightfully so, just dim with no option (at least to my knowing) to extract the value of dim from the TokenStream (here 1000). Therefore my macro is pretty straight-forward (especially since I omitted better error handling):

// rd_proc_macro/src/lib.rs

// I need the TokenStream, since it is required by
// the definitions of the procedural macro.
use proc_macro::TokenStream;
// I created another crate which creates the alphas for me.
// I plan to re-use this crate for other use cases.
use rd_alphas::create_alphas;

// Convert the dimension TokenStream to a string and then parse this into an usize
fn parse_dimension(dimension: TokenStream) -> usize {
    // parse the token stream as usize literal or panic
    let dim_string = dimension.to_string();
    dim_string.parse::<usize>().unwrap()
}

// create the static alphas array as Rust source code string
fn create_rd_alphas_array(dim: usize) -> String {
    // create a string from the alpha values
    let mut array_string = String::from("static ALPHAS:[f64; ");
    array_string.push_str(dim.to_string().as_str());
    array_string.push_str("] = [\r\n");
    let alphas = create_alphas(dim);
    for alpha in &alphas {
        // a little bit of formatting here.
        array_string.push_str("\u{20}\u{20}\u{20}\u{20}");
        array_string.push_str(alpha.to_string().as_str());
        array_string.push_str(",\r\n");
    }
    array_string.push_str("];\r\n");
    array_string
}

#[proc_macro]
pub fn create_rd_alphas(dimension: TokenStream) -> TokenStream {
    let dim = parse_dimension(dimension);

    let array_string = create_rd_alphas_array(dim);

    // create the TokenStream output
    array_string.parse().unwrap()
}

And I can use this macro by, for example, calling create_rd_alphas!(2), to create a static, two dimensional array during compile time. For example, one of my integration tests could look like:

#[cfg(test)]
mod integration_tests {
    use rd_proc_macro::create_rd_alphas;

    #[test]
    fn test_proc_macro() {
        create_rd_alphas!(2);

        assert_eq!(0.7548776662466927, ALPHAS[0]);
        assert_eq!(0.5698402909980532, ALPHAS[1]);
    }
}

Important to note is, that the above code does only work with Rust 1.45, since before that, procedural function like macros could not be used as a statement. Fortunately this changed, see The Rust Blog - Rust-1.45.0 - Stabilizing function like procedural macros in expressions patterns and statements. This is a great improvement because otherwise a user of my library would first needed to call the macro (create_rd_alphas) in an item position and then create the sequence with another macro. Example:

// application_using_qrand_core/main.rs

// This can be done with a re-export.
// I will demonstrate re-exports below a little bit more
use qrand_core::create_rd_alphas;
// the create sequence macro, which "knows" that there is a static array named "ALPHAS"
use qrand_core::create_sequence;
// The trait which is the public interface of my sequence
use qrand_core::LowDiscrepancySequence;

// alphas are created in an item position
create_rd_alphas(5);
// I could also re-export and change the name to something less specific like create_sequence_data

fn main() {
    let sequence = create_sequence!();
    // sequence is used ...
}

This is error-prone, although errors would be caught by the compiler. And I would leak more implementation detail that I want to, mainly that I need to create these alphas first (or at least create some kind of sequence data if I rename the re-export from the procedural macro crate). Fortunately Rust 1.45 enables using procedural macros as statements, but currently I only have a procedural macro which helps creating the alphas and I still want to hide this as an implementation detail. I can do this with re-exports in my library which has the procedural macro as dependency. I then have two options. The first option is to use a macro_rules macro, to create the array with the procedural macro and then the sequence. This would look like this:

// qrand_core/src/lib.rs
// I need to re-export the LowDiscrepancySequence so that its functions can be used
pub use low_discrepancy_sequence::LowDiscrepancySequence;

// The procedural macro must also be re-exported
// so that it can be used in the macro_rules macro
pub use rd_proc_macro::create_rd_alphas;

// my internal, non-public module for the Rd sequence
mod rd;
use rd::new_sequence;

// The public interface that wraps the actual implementation of the Rd sequence.
// This is also needed in the macro.
pub fn create_seq(alphas: &'static [f64]) -> impl LowDiscrepancySequence {
    new_sequence(&alphas)
}

// the macro_rules macro
#[macro_export]
macro_rules! create_sequence {
    ($dimension:expr) => {{
        // usage of the re-exported procedural macro
        $crate::create_rd_alphas!($dimension);
        // creation of the sequence
        $crate::create_seq(&ALPHAS)
    }};
    () => {
        create_sequence! {1}
    };
}

As you can see, I need to re-export the create_rd_alphas macro and need to set the create_seq function public, which does expose, that we need a static reference to a slice of f64. Although the usage of the create_sequence macro does then hide all details, I still need to expose these two interfaces and therefore my intention to hide these details is only partially fulfilled. Someone could use these interfaces directly instead of the macro. In the worst case, this someone uses them incorrectly.

However, there is a second option, that is slightly better regarding exposing these interfaces. I could change my procedural macro library, so that there is a macro which does already create the sequence. This could look like this:

// rd_proc_macro/src/lib.rs

// I need the TokenStream, since it is required by
// the definitions of the procedural macro.
use proc_macro::TokenStream;
// I created another crate which creates the alphas for me.
// I plan to re-use this crate for other use cases.
use rd_alphas::create_alphas;

// Convert the dimension TokenStream to a string and then parse this into an usize
fn parse_dimension(dimension: TokenStream) -> usize {
    // parse the token stream as usize literal or panic
    let dim_string = dimension.to_string();
    dim_string.parse::<usize>().unwrap()
}

// create the static alphas array as Rust source code string
fn create_rd_alphas_array(dim: usize) -> String {
    // create a string from the alpha values
    let mut array_string = String::from("static ALPHAS:[f64; ");
    array_string.push_str(dim.to_string().to_string().as_str());
    array_string.push_str("] = [\r\n");
    let alphas = create_alphas(dim);
    for alpha in &alphas {
        // A little bit of formatting
        array_string.push_str("\u{20}\u{20}\u{20}\u{20}");
        array_string.push_str(alpha.to_string().as_str());
        array_string.push_str(",\r\n");
    }
    array_string.push_str("];\r\n");
    array_string
}

#[proc_macro]
pub fn create_sequence(dimension: TokenStream) -> TokenStream {
    let dim = parse_dimension(dimension);

    // I want to return the sequence and therefore I need a { block
    let mut code = String::from("{\r\n");

    // the array is created inside the block
    code.push_str(create_rd_alphas_array(dim).as_str());

    code.push_str("\r\n");

    // I then create sequence and it is returned
    code.push_str("rd_proc_macro_user_lib::create_seq(&ALPHAS)");

    // end of the block
    code.push_str("}\r\n");
    // This means the block looks like this for dimension=2:
    // {
    // static alphas:[f64;2] = [0.7548776662466927, 0.5698402909980532];
    // rd_proc_macro_user_lib::create_seq(&ALPHAS) // this returns an impl LowDiscrepancySequence
    // }

    // create the TokenStream output
    code.parse().unwrap()
}

My library then re-exports the macro as well which could look like this:

// qrand_core/src/lib.rs

// I need to re-export the LowDiscrepancySequence so that its functions can be used
pub use low_discrepancy_sequence::LowDiscrepancySequence;

// The re-export of the macro
pub use rd_proc_macro::create_sequence;

// my internal, non-public module for the Rd sequence
mod rd;
use rd::new_sequence;

// The public interface that wraps the actual implementation of the Rd sequence.
// This is also needed in the macro.
pub fn create_seq(alphas: &'static [f64]) -> impl LowDiscrepancySequence {
    new_sequence(&alphas)
}

This means, the macro create_sequence is now re-exported and needed and the only implementation detail leaked is the public interface create_seq which requires a static reference to f64 slice. This is better from a implementation hiding point of view. But I have another problem with this solution: The procedural macro crate rd_proc_macro is indirectly dependent on its dependent crate qrand_core, since the create_seq function is used (as a string literal) inside the macro. This is not a catastrophe, but it means that the crate can only be used in conjunction with its dependent crate qrand_core and this feels limiting and strange. Therefore I would prefer the first option, where more implementation details are leaked.

Conclusion using procedural macros

This option works. The macros are pretty straightforward to write in comparison to using macro_rules macros. They are more straightforward to use then requiring an environment variable to be set when compiling. However some implementation details are leaked, since the macro needs access to the functions that actually create the sequence. It's not a huge problem but it may be confusing or someone may use these public interface in a wrong way.

Conclusion

I introduced and skimmed through 4 options I tried out, for generating large arrays during compile time:

• Using const functions and const generics do require using the nightly compiler and I need to implement some of the standard library functions myself. The need to use the nightly compiler is the reason I wouldn't use this option, at least for now. And I don't like, that the constant functions are part of the final binary, since I don't use them during runtime.
• macro_rules macros may work, but I could only outline how they may work. At least for me this option is too complicated and may crash the compiler if an array is too large.
• Build scripts do work but require, at least for the moment, the usage of environment variables during compile time.
• Procedural function like macros do also work, but leak a little bit more implementation detail as I prefer.

So there are obviously only two options left for my use case: build scripts or procedural macros. I like that build scripts do hide the array completely from the user as an implementation detail. I don't like that a user must set an environment variable to compile my library. Procedural macros are very close to the ideal solution, especially since, with 1.45, they can be used in statements and expressions. However, I don't like that some functions need to be made public that leak implementation detail. These may not be used by the user and a good documentation may fix most of the issues I have, but still it's sub-optimal.

So for me, there is no clear-cut winner here. At the moment I prefer using build scripts, mainly due to their better hiding of the array as an implementation detail.

Let me know what you think in the comments below. Also I appreciate comments, critique, correction of errors I made. I will try to update the article appropriately. Thank you for reading.