Const-fn freezing to immutable data structures?

I am experimenting with the usage of const-fn to precompute few things in my code, and the results are good enough. This is an example of computing a small table of primes below 1000 (it computes the primes two times, the first time counts them in the interval, and then uses that result to define a fixed-size array, so it's a two phase computation):

const fn count_primes<const LIMIT: usize>() -> usize {
    let mut is_prime = [true; LIMIT];
    let mut count = 0;
    ...
    count
}

const fn primes_array<const LEN: usize>() -> [u32; LEN] {
    let mut result = [0; LEN];
    ...
    result
}

const PRIMES: [u32; count_primes::<1000>()] = primes_array();

But in similar situations I'd like a way to allocate on the heap in a const-fn and then convert the heap data structure into fixed size data structure. With some limitations this is possible in D language:

int[] foo(uint n)() {
   return new int[n];
}
// Implicit cast from compile-time heap to fixed size array:
enum int[5] DATA = foo!(5)();
void main() {}

You can even do this if you want:

int[] foo(uint n)() {
   return new int[n];
}
enum int[] DATA = foo!(5)();
enum uint LEN = DATA.length;
enum int[LEN] DATA2 = DATA;
void main() {}

Rust language is thankfully more principled, and you need to be more principled if you want to do something like that for arbitrary data structures (like a HashMap).

A solutions is to introduce a freezing function that returns a different immutable heap-allocated data struture (that lacks mutating accessors).

1 Like

I believe it's always been intended that we'd somehow eventually allow compile-time heap allocations to be transformed into fixed runtime memory. I assume it hasn't been very visible to "the Rust public" lately because it's orthogonal to all of the other const fn and const generics issues blocking stabilization, will have to be something added on top of those "core const features" regardless, and the big challenge right now appears to be ensuring soundness of all of the various const features, not bikeshedding syntax/APIs for it.

See https://github.com/rust-lang/const-eval/issues/20 for the most recent discussion / tracking that I'm aware of. I think strawmen of this go back as far as the first ever compiler team discussions for MIRI integration, maybe even the first ever conference talks announcing MIRI's existence.

2 Likes

Indeed, this is definitely a feature that we all want. But it's hard to get right. The underlying const-eval engine can already handle heap allocations and all sorts of crazy pointer stuff, but making sure that nothing goes wrong when pre-computing such things and using them later is a subtle art. In particular, we have to ensure that (in safe code) the user cannot drop and thus deallocate such a "compile-time created heap allocation".

The people pushing const-eval forward have still been busy with more basic features. As a result of that, it looks like we'll soon finally get basic control flow operators in consts. :smiley:

@leonardo I assume you used a bunch of nightly features as I don't think you could implement your prime search otherwise? The focus recently has been more on making those features available on stable, rather than adding more features to nightly.

2 Likes