Without boats, dreams dry up

Shipping Const Generics in 2020

It’s hard to believe that its been more than 3 years since I opened RFC 2000, which defined the const generics for Rust. At the same time, reading the RFC thread, there’s also been a huge amount of change in this area: for one thing, at the time the RFC was written, const fns weren’t stable, and consts weren’t even being evaluated using miri yet. There’s been a lot of work over the years on the const generics feature, but still nothing has shipped. However, I think we have defined a very useful subset of const generics which is stable enough to ship in the near term.

For those who don’t know, const generics refers to generics that are constant values, rather than types. This allows types to be parameterized by, for example, specific integer values. In stable Rust, only the special array type - [T; N] - has a const parameter (the length of the array), and there is no way to be abstract over all values of N, even for arrays. Const generics will allow creating new types parameterized by values, as well as implementing traits and functions that are abstract over those values. For example:

// This is a custom type which is parameterized by a `usize`
pub struct Foo<const N: usize> { 
    bytes: [u8; N],
}


// This is a trait which has been implemented for arrays of
// any length.
impl<T: Debug, const N: usize> Debug for [T; N] {
}

We’ve been using the const generics feature to implement traits for arrays for over a year, artificially limiting the implementations to arrays of length 32. We are planning to lift that limitation on those impls in an upcoming release. By stabilizing const generics, we could start to allow external crates to implement traits for all arrays as well, and many other interesting use cases. There will be two important limitations, however.

Only integral primitive types for const generics

The initial types that a const generic can have will be limited to the integral primitive types. That means the signed and unsigned integer types, booleans, and chars. For now, no compound or user-defined types will be allowed, and no references (meaning no strings as well). This is a relatively easy shortcoming of the current implementation to fix, and user defined types for const generics will be possible in the nearer, rather than longer term.

I want to mention, since a lot of people aren’t aware of this, that not any type can be used as a const parameter, even setting aside the current limitations of rustc. Importantly, in order for Rust’s type system to be sound, equality between two types must be deterministic, reflexive, symmetric, and so on. That is, if your custom type implements equality by flipping a coin, two values of that type will sometimes be equal to one another and sometimes not. This will mean, two types parameterized by those values will sometimes be the same type and sometimes a different type. This would be quite troubling for the type system.

(As a concrete example, floating point numbers present challenges with the fact that Foo<NaN>, for example, would not be considered the same type as itself, because NaN is not equal to itself.)

The long term solution to this is a notion of “structural equality,” which is a strictly correct subset of Eq types that meet the properties needed for use in the type system. Rust already uses this structural equality property when implementing matching. If you derive Eq and PartialEq for your type and all its members, it should meet the structural equality property needed to be used in matches and const generics.

No complex expressions based on generic types or consts

The other limitation will be that only two kinds of expressions can be used to fill in a const generic position:

  1. A const generic parameter. For example, in an impl<const N: usize>, where an const generic has been introduced, that value can be used literally to fill a const generic.
  2. An expression that can be used in a const context which does not depend on any type or const parameters. This means literals, math equations, using consts, calling const fns, etc, as long as no free generics are involved.

This limits a lot of the more exotic and interesting things users want to do with const generics. You can’t, for example, combine two array lengths together to form an array with type [T; N + M], or even double an array length with [T; N * 2]. You basically can’t have a type that depends on computation that depends on other generics. Implementing this behavior soundly and correctly is really the hard part of implementing const generics, and while work is ongoing, it isn’t ready yet.

This also means that const generics can’t be filled in based on associated types, associated consts, or generic methods. No functions that return [u8; mem::size_of::<T>()], no use of Self like [u8; Self::LEN], etc.

This will mean, for example, that use cases like cryptographic hash traits which allow each implementation to specify a different length for the hash they output will still be out of scope for the MVP. This is a shame, but this feature will come eventually.

What you will be able to do

All of these restrictions might sound like the feature is pretty limited, but I think users will find a lot of really powerful use cases for it once they can play around with it. For one thing, traits that today might be implemented only by some array types, or not at all, will begin to be implemented by all arrays, making arrays a much more first class part of the language. And we’re already finding awesome use cases. Look at this code sample.

let data = [1, 2, 3, 4, 5, 6];

let sum1 = data.array_chunks().map(|&[x, y]| x * y).sum::<i32>();
assert_eq!(sum1, (1 * 2) + (3 * 4) + (5 * 6));

let sum2 = data.array_chunks().map(|&[x, y, z]| x * y * z).sum::<i32>();
assert_eq!(sum2, (1 * 2 * 3) + (4 * 5 * 6));

Based on the pattern passed to the map function, the compiler figures out that the first call to array_chunks should chunk the data into an iterator of arrays with length 2, and in the second call it should be an iterator of arrays with length 3. It’s so cool!

Next steps

Now that we’ve worked out what we could stabilize in the near future, I am working up hype and consensus aroud the vision of stabilizing this feature - that’s what this blog post is for! The next steps will be for someone to carve out a feature gate which is this limited set of const generics (as opposed to the existing whole const_generics feature gate) and then for us to go through the standard procedure for documenting and stabilizing that feature gate.

Credit

My own involvement in const generics between the RFC and now has been minimal to non-existent. Essentially, my role (both in the RFC and now) has been to identify a scope we can get consensus on moving forward with. However, the hard work of implementing const generics has been going on for years in between then, and I want to credit especially the contributors eddyb, varkor, lcnr, and oli-obk for their work on implementing this highly requested feature.