Make std::array::from_fn a const fn

[dead-claudia]

Proposal

Problem statement

I want to create a repeated array of a non-copiable, non-cloneable type in a generic const context, and I want to be able to convert one array to another within it.

Motivation, use-cases

I've got constants like this:

// `Vec::from_iter(1..=MAX_KEY_LEN_DECODED)`, but static.
static KEY_LENGTHS: &[usize] = &[
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
    26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48,
    49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71,
    72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94,
    95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113,
    114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128,
];

// `Vec::from_iter(1..=MAX_NAME_LEN)`, but static.
static NAME_LENGTHS: &[usize] = &[
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
    26, 27, 28, 29, 30, 31, 32,
];

Also, certain lookup tables where the mapping is less trivial come to mind, like the one used for optimized CRC32 implementations.

// This implements the CRC32 variant as described in
// https://www.w3.org/TR/png/#samplecrc among others.
static CRC_TABLE: [u32; 256] = {
    let mut table = [0; 256];
    let mut n = 0;

    while n < 256 {
        let mut c = n;
        let mut k = 0;

        while k < 8 {
            if c & 1 != 0 {
                c = 0xEDB88320 ^ (c >> 1);
            } else {
                c >>= 1;
            }
			k += 1;
        }

        table[n] = c;

        n += 1;
    }

    table
};

pub struct Crc32 {
    current: u32,
}

impl Crc32 {
    pub const fn new() -> Crc32 {
        Crc32 { current: !0 }
    }

    pub fn update(&mut self, buf: &[u8]) {
        let mut c = self.current;
        for byte in buf {
            c = CRC_TABLE[((c as usize) ^ (*byte as usize)) & 0xFF] ^ (c >> 8)
        }
        self.current = c;
    }

    pub fn current(&self) -> u32 {
        !self.current
    }
}

In non-const contexts, the above explicitly written tables could be easily simplified to the following, and wouldn't even need the comments to explain their intent:

let key_lengths = std::array::from_fn::<usize, MAX_KEY_LEN_DECODED>(|i| i + 1);

let name_lengths = std::array::from_fn::<usize, MAX_NAME_LEN>(|i| i + 1);

The CRC32 table could be simplified to just the following:

let crc32_table = std::array::from_fn::<u32, 256>(|c| {
    let mut c = c as u32;
    let mut k = 0;

    while k < 8 {
        if c & 1 != 0 {
            c = 0xEDB88320 ^ (c >> 1);
        } else {
            c >>= 1;
        }
		k += 1;
    }

    c
});

Solution sketches

Title says it all. Making std::array::from_fn a const fn would allow the simplified versions to just be used for initializing static variables.

Links and related work

Obviously https://doc.rust-lang.org/std/array/fn.from_fn.html is prior art. Also, this has been requested in rust-lang/rust#89379, though I didn't find that until after writing this up.

What happens now?

This issue is part of the libs-api team API change proposal process. Once this issue is filed the libs-api team will review open proposals in its weekly meeting. You should receive feedback within a week or two.

[scottmcm]

I think this needs const traits to be figured out to be able to take a const closure, so it can't really happen yet? (Well, maybe there's something on nightly, but definitely not stable yet.)

[Amanieu]

We discussed this in the libs-api meeting today. We're happy to have those once the language is capable of supporting this. Currently this is not possible due to the lack of const traits and const closures.