It's Time to Get Hyped About Const Generics in Rust

One of the most interesting emergent properties of the Rust language has been the desire and ability to push more and more information into the type system. Other programming languages allow this, but Rust’s combination of speed, safety, and extremely powerful compile-time computation through both types and macros, have lead to a large ecosystem of highly capable libraries that do much of their work before the program ever runs.

Recent developments in the type system are making it easier than ever for programmers to take advantage of that power, and things are only going to get more interesting.

Constant Generic Parameters

In Rust 1.51, the “const generics MVP” was stabilized into the language, enabling tons of API and performance improvements. These so-called “const generics”, or “constant generic parameters”, permit values of integral types to used as parameters to generic types, traits, and functions, like this example from my nslice crate:

/// A region of memory containing at least `N` `T`s.
pub struct MinSlice<T, const N: usize> {
    /// The bounded region of memory. Exactly `N` `T`s.
    pub head: [T; N],
    /// Zero or more remaining `T`s after the `N` in the bounded region.
    pub tail: [T],
}

Here, T is a normal type parameter, but N is a constant generic parameter, meaning that the minimum number of elements in the MinSlice is encoded in its type; a MinSlice<_, 16> isn’t the same as a MinSlice<_, 32>, for instance.

Const Generics Reduce Runtime Complexity

This is great, and lets us avoid some runtime checks. Whereas a normal slice means getting an Option (or a possible panic) every time we read from it, even if we know the size:

let slice: &[u8] = b"Hello, world";
let reference: Option<&u8> = slice.get(6);
// We know this value is `Some(b' ')`,
// but the compiler can't know that.
assert!(reference.is_some())

With a MinSlice, we can perform the length check one time and get a compile-time guarantee that future accesses will succeed:

let slice: &[u8] = b"Hello, world";
// Length check is performed when we construct a MinSlice,
// and it's known at compile time to be of length 12.
// If the `unwrap()` succeeds, no more checks are needed
// throughout the `MinSlice`'s lifetime.
let minslice = MinSlice::<u8, 12>::from_slice(slice).unwrap();
let value: u8 = minslice.head[6];
assert_eq!(value, b' ')

This is powerful, but the current implementation of const generics is quite limited, on purpose. There are remaining design questions around a lot of aspects of the world of type-level computation in Rust, such as error handling and even syntax for default values.

Generic Constant Expressions

One important feature that’s not yet available on stable is the ability to do computations on constant generics at compile time, beyond very simple combinations of literals. That is, you can write MinSlice::<_, 3 + 4>, but you can’t (yet) write something like:

impl <T, const N: usize> MinSlice<T, N> {
    /// Returns a longer `MinSlice` if enough elements
    /// are available in `tail`.
    fn <const M: usize> extend(&self) -> Option(&MinSlice<T, N + M>) 
}

Arithmetic and comparisons that work with literals aren’t available with constant generic parameters.

All of that changes, however, when we enable the feature generic_const_exprs. This feature still has many design questions, and likely won’t be stabilized for a long time, but when it is, we’ll be able to put a great deal of information in the type system that could previously be computed only at runtime.

Conditional Implementation

Obviously computing the lengths of arrays at compile time is convenient, but we can do even better. For example, Rust already has a way to conditionally implement traits on types; it’s just that the only condition available is whether that type implements another trait already.

impl<T> MyTrait for MyType<T> where MyType<T>: Copy {}

We can even make chains of inference using generic parameters, like this:

impl<T> Copy for MyType<T> where T: Copy {}

Now, whenever we construct a MyType<T> for a T that is Copy, that automatically implements both Copy and MyTrait. So, MyType<u32> is Copy and MyTrait, but MyType<String> is neither.

Const Implementation Bounds

Let’s say we’re working on a piece of embedded software running in a real-time environment, and it’s become clear that cloning values that are too large could lead to violations of our real-time constraints. That is, taking the time to loop through and copy 32 or 64 values is fine, but if we’re spending time copying 128 values from place to place, we’ll infringe on our sensor polling or something.

(Yeah, it’s contrived - but it’s just an example.)

Ideally, we’d be able to enforce this at compile time, and indeed with just a little bit of infrastructure, we can conditionally implement traits based on the values of compile-time expressions encoded entirely in the type system.

Specifically, we need a trait that is implemented only if some condition is met. Enter Assert and IsTrue:

struct Assert<const COND: bool> {}

trait IsTrue {}

impl IsTrue for Assert<true> {}

These empty types and traits, of course, vanish during compilation, but they do give us enough infrastructure to make some compile-time assertions:

let _: Assert<false> = Assert::<{10 > 11}> {};

If all of our data is wrapped in a custom type, like this:

/// The struct we're going to conditionally implement for
#[derive(Clone, Debug)]
struct Foo<const N: usize>{ inner: [usize; N] }

We can then go ahead and make a conditional implementation based on size:

impl<const N: usize> Copy for Foo<N> where Assert::<{N < 128}>: IsTrue {}

Now, it’s ergonomic to copy around arrays of any size up to 127, like so:

let my_foo = Foo::<16> { inner: [0; 16] };
let foo_too = my_foo;  
println!("{:?}", foo_too);
do_something(my_foo);

But, as soon as they get too big, the compiler will stop us:

let my_copynt_foo = Foo::<128> { inner: [0; 128] };
let foo_moved = my_copynt_foo;
println!("{:?}", my_copynt_foo);
// ERROR: borrow of moved value
// move occurs because `my_copynt_foo` has type `Foo<128_usize>`,
// which does not implement the `Copy` trait

This is a fairly ergonomic form of almost-not-quite dependent types, and it’s all encoded in the familiar language of traits and generics that Rustaceans use daily.

Moving Forward

As I mentioned, there are many hurdles ahead in the implementation and stabilization of these features in the language, and their subsequent use in the library ecosystem. It’s also worth mentioning that there is already a library that provides many of these features on stable, called typenum. It’s a useful library if you need these features today, but it inherently has poor compile times and is somewhat limited in terms of its integration into the compiler and overall ecosystem in a way that first-class const generics are not.

Nonetheless, I think it’s time to get excited about constant generics in Rust; start figuring out how you want to use them and how they can help you solve problems, and give feedback to the Rust project about what you’d like to see as the full-fledged constant generic implementation begins to unfold.