👋🏽 Const Generics Project Group

The const generics project group implements and designs the const_generics feature. Please refer to our charter for more information on our goals and current scope.

Examples:

struct Foo<const N: usize> {
    field: [u8; N],
}

fn foo<const N: usize>() -> Foo<N> {
    Foo {
        field: [0; N],
    }
}

fn main() {
    match foo::<3>().field {
        [0, 0, 0] => {} // ok
        [_x, _y, _z] => panic!(),
    }
}

Welcome to the repository for the Const Generics Project Group! This is the repository we use to organise our work. Please refer to our charter as well as our github pages website for more information on our goals and current scope.

How Can I Get Involved?

You can find a list of the current members available on rust-lang/team.

If you’d like to participate be sure to check out the relevant stream on zulip, feel free to introduce yourself over there and ask us any questions you have.

Building Documentation

This repository is also an mdbook project. You can view and build it using the following command.

mdbook serve

📜 Const Generics Charter

The goal of this group is to both improve and extend the support for const generics.

Goals

Improving the user experience when using and working on const generics. This includes both improvements to diagnostics for the already stabilized parts as well as adding new features:

• more const param types, most importantly user defined types and &'static str
• allowing complex generic operations in constants

Constraints And Considerations

At least for the near future, we will mostly focus on the items mentioned above.

🔮 The vision

What is this

This section lays out a general vision and set of goals for Const Generics in Rust.

Status and schedule

This document is currently being formed.

This is a group effort

As the leads of the Const Generics group, Niko and lcnr are driving and organizing this document. But writing it and shaping it is a group effort. If you think there is a part of the const generics experience that is not reflected here, we want to hear from you! Check out the How to vision doc for more details on how to contribute.

Why compile time evaluation?

This section is, in many ways, the most important. It aims to clarify the reasoning about any future decisions about const generics and const evaluation.

Why do we want to evaluate things at compile time?

People already precompute certain data structures, lookup tables, and so on, at compile time. For example the crate regex could be able to compile a regex at compile time, improving the performance when using regex and even removing the need for runtime allocations. Const evaluation is also very useful to assert correctness requirements at compile time, instead of using a runtime panic.

Without good const evaluation support, is often easier to just use a build.rs file for this or compute it externally and generate the result outside of the ordinary compilation process. This is both worse for the user, as they essentially have to learn yet another meta language, and also negatively impacts the compilation speed and incremental compilation. If that isn’t possible or sensible, one often just requires the computation to happen at runtime, negatively impacting startup performance.

Computing things outside without using const eval makes it at lot more cumbersome to use and prevents the input for that computation to simply be a generic or function parameter.

Why const generics?

Const evaluation by itself is good enough unless it should influence the type system.

This is needed when computing the layout of types, most often by using arrays. Using arrays instead of dynamic allocations or slices can improve performance, reduces the dynamic memory footprint and can remove runtime checks and implicit invariants.

Another reason is to be generic over configurations or to move certain conditions to compile time. Consider image handles in rust-gpu or TODO: example for state machines.

What are our goals?

Consistent: “just add const”

Writing code that works at compile time should at most require manually adding the needed const annotations at suggested places (or even automatically using rustfix or IDE support) until everything compiles. One should not be required to avoid large parts of the language to do this. Adding and using const parameters should be straight forward without weird restrictions or a lot required knowledge. Using const generic items from different libraries should work without issues.

Approachable: “what is [u8; my_expr]:, and why is it needed”

Reading or writing code which can be used at compile time should ideally not be more complex than writing other code. Requiring a lot of weird trait bounds or other hacks should be avoided as much as possible. Supporting compile time evaluation should not worsen the experience of users, especially for beginners.

Reliable: “if it passes cargo check, it works”

Const evaluation failures should be detected as early as possible, even when using cargo check. When writing library code, incorrect constants should cause warnings and errors whenever possible.

🙋‍♀️ Cast of characters

What is this?

We’ve created four characters that we use to guide our thinking. These characters are the protagonists of our status quo and shiny future stories, and they help us to think about the different kinds of priorities and expectations that people bring when using Const Generics in rust. Having names and personalities also makes the stories more fun and approachable.

The characters

• Alan: the experienced “GC’d language” developer, new to Rust
  • Top priority: performance – that’s what he is not getting from current GC’d language
  • Expectations: absence of memory safety bugs (he gets that now from his GC), strong ecosystem, great tooling
• Grace: the systems programming expert, new to Rust
  • Top priority: memory safety – that’s what she is not getting from C/C++
  • Expectations: able to do all the things she’s used to from C/C++
• Niklaus: new programmer from an unconventional background
  • Top priority: accessibility – he’s learning a lot of new things at once
  • Expectations: community – the community enabled him to have early success, and he is excited to have it support him and him grow more
• Barbara: the experienced Rust developer
  • Top priority: overall productivity and long-term maintenance – she loves Rust, and wants to see it extended to new areas; she has an existing code base to maintain
  • Expectations: elegance and craftsmanship, fits well with Rust

🤔 Frequently Asked Questions

Where do the names come from?

Famous programming language designers and theorists. Alan Turing, Grace Hopper, Niklaus Wirth, and Barbara Liskov.

I don’t see myself in these characters. What should I do?

Come to Zulip (#project-const-generics) and talk to us about it! Maybe they need to be adjusted!

I see myself in more than one of these characters!

Yeah, me too.

😱 Status quo stories

What is this

The “status quo” stores are here to state our “theory of the case”. That is, they present (and prove) our hypotheses as to what the various challenges are for users of Const Generics in Rust. These hypotheses are presented in narrative form, by telling the story of a specific character as they try (and typically fail in dramatic fashion) to achieve their goals.

Based on a true story

These stories are not made up. They are always based on real-life experiences of actual people. Each story contains a “Frequently Asked Questions” section, and that will include notes the sources used to create the story. In some cases, it may link to notes or summaries in the conversations section, though that is not required. The “Frequently Asked Questions” section also contains a summary of what the “morals” of the story are (i.e., what are the key takeaways), along with answers to questions that people have raised along the way.

The stories provide data we use to prioritize, not a prioritization itself

Just because a user story is represented here doesn’t mean we’re going to be able to fix it right now. Some of these user stories will indicate more severe problems than others. As we consider the stories, we’ll select some subset to try and address; that choice is reflected in the roadmap.

Help wanted!

This is not a static document! There are lots of ways you can help to expand it! Take a look at the How to Vision Doc for more details.

😱 Status quo story: Barbara wants to implement Default for all array lengths

Barbara is working on std. She wants to implement Default for all array types. Currently, it is implemented for N <= 32 using a macro (link)

She thinks “Ah, I can use min-const-generics for this!” and goes to write

#![allow(unused)]
fn main() {
impl<T, const N: usize> Default for [T; N]
where
    T: Default,
{
    fn default() -> Self {
        
    }

}
}

So far so good, but then she realizes she can’t figure out what to write in the body. At first she tries:

#![allow(unused)]
fn main() {
impl<T, const N: usize> Default for [T; N]
where
    T: Default,
{
    fn default() -> Self {
        [T::default(); N]
    }

}
}

but this won’t compile:

error[E0277]: the trait bound `T: Copy` is not satisfied
  --> src/lib.rs:10:9
   |
10 |         [T::default(); N]
   |         ^^^^^^^^^^^^^^^^^ the trait `Copy` is not implemented for `T`
   |
   = note: the `Copy` trait is required because the repeated element will be copied
help: consider further restricting this bound
   |
7  |     T: MyDefault + Copy,
   |                  ^^^^^^

“Ah,” she realizes, “this would be cloning a single value of T, but I want to make N distinct values. How can I do that?”

She asks on Zulip and lcnr tells her that there is this map function defined on arrays. She could write:

#![allow(unused)]
fn main() {
impl<T, const N: usize> Default for [T; N]
where
    T: Default,
{
    fn default() -> Self {
        [(); N].map(|()| T::default())
    }
}
}

“That code will build,” lcnr warns her, “but we’re not going to be able to ship it. Test it and see.” Barbara runs the tests and finds she is getting a failure. The following test no longer builds:

#![allow(unused)]
fn main() {
fn generic<T>() -> [T; 0] {
    Default::default()
}
}

“Ah,” she says, “I see that Default is implemented for any type [T; 0], regardless of whether T: Default. That makes sense. Argh!”

Next she tries (this already relies on a nightly feature)

#![allow(unused)]
fn main() {
impl<T: Trait, const N: usize> Default for [T; N]
where
    T: Default,
    N != 0, // nightly feature!
{
    fn default() -> Self {
        [(); N].map(|()| T::default())
    }
}

impl<T> Trait for [T; 0] {
    // ...
}
}

While this does seem to compile, when trying to use it, it causes an unexpected error.

#![allow(unused)]
fn main() {
fn foo<T: Trait, const N: usize>() -> [u8; N] {
    <[T; N] as Trait>::ASSOC //~ ERROR `[T; N]` does not implement `Trait`
}
}

The compiler can’t tell that N == 0 || N != 0 is true for all possible N, so it can’t infer [T; N]: Trait from T: Trait.

Frustrated, Barbara gives up and goes looking for another issue to fix.

Even worse, Barbara notices the same problem for serde::Deserialize and decides to abandon backwards compatibility in favor of a brighter future.

😱 Status quo: Array split first method

Barbara is working on her project. She has the idea to write a split_first function that will allow her to split out the first item from a fixed-length array; naturally, the array must be non-empty. It looks something like this:

#![allow(unused)]
fn main() {
// Note: this method has an implied where clause that `N - 1` evaluates without 
// erroring because `N - 1` is in the function signature
fn split_first<T, const N: usize>(arr: [T; N]) -> (T; [T; N - 1]) {
    // ...
    let tail: [T; N - 1] = // ...
    (head, tail)
}
}

Next she wants to write a function that uses split_first:

#![allow(unused)]
fn main() {
fn some_method<const N: usize>(arr: [u8; N]) {
    let (first, rest) = split_first(arr);
    for i in rest {
        // ...
    }
}
}

The compiler gives her a compile error:

error: the constant expression `N-1` is not known to be evaluatable
2 |     let (first, rest) = split_first(arr);
  |                         ^^^^^^^^^^^ `N-1` not known to be evaluatable
info: N may underflow
help: add a where clause to `some_method`
  | fn some_method<const N: usize>(arr: [u8; N]) where [(); {N - 1}]:

Barbara hits the ‘quick fix’ button in her IDE and it inserts the where clause for her- she immediately gets a compile error at another spot because she was calling some_method with an empty array:

error: integer underflow evaluating constant expression
22 |     some_method([])
   |     ^^^^^^^^^^^^^^^ `0-1` is not evaluatable
info: `0-1` must be evaluatable because of this where clause
  | fn some_method<const N: usize>(arr: [u8; N]) where [(); { N - 1}]:
  |                                                    ---------------

She also gets a compile error at another spot with a [(); { N - 2; }]: where clause in scope

#![allow(unused)]
fn main() {
fn some_other_method<const N: usize>(arr: [u8; N]) where [(); { N - 2; }]: {
    // ...
    let (first, rest) = split_first(arr);
    // ...
}
}

error: the constant expression `N-1` is not known to be evaluatable
2 |     let (first, rest) = split_first(arr);
  |                         ^^^^^^^^^^^ `N-1` not known to be evaluatable
info: N may underflow
help: add a where clause to `some_method`
  | fn some_method<const N: usize>(arr: [u8; N]) where [(); { N - 2; }}:, [(); { N - 1; }];, {

“What!!! That’s silly”- Barbara sighs, hitting the quick fix button and moving on

(rustc is not currently smart enough to know that N - 2 being evaluatable implies N - 1)

Alt Universe with post-mono errors

Barbara is working on her project. She has the idea to write a split_first function that will allow her to split out the first item from a fixed-length array; naturally, the array must be non-empty. It looks something like this:

#![allow(unused)]
fn main() {
// Note: this method has no implied where clause that `N - 1` evaluates
fn split_first<T, const N: usize>(arr: [T; N]) -> (T; [T; N - 1]) {
    // ...
    let tail: [T; N - 1] = // ...
    (head, tail)
}
}

Next she wants to write a function that uses split_first:

#![allow(unused)]
fn main() {
fn some_method<const N: usize>(arr: [u8; N]) {
    let (first, rest) = split_first(arr);
    for i in rest {
        // ...
    }
}
}

Everything seems fine when she runs cargo check. Then later she runs cargo test and sees a compilation error:

error: const evaluation error occurred
22 |    let tail: [T; N - 1] = // ...
   |                  ^^^^^ integer underflow, cannot subtract `1` from `0`
info: this const evaluation was required by `some_other_method`, which contains:
22 |     some_method([])
info: `some_method` contains:
22 |    let (first, rest) = split_first(arr);
info: `split_first` contains:
22 |    let tail: [T; N - 1] = // ...

😱 Status quo: nalgebra

a huge thanks to Andreas Borgen Longva and Sébastien Crozet for the help with figuring this out

nalgebra is a linear algebra library. At the core of that library is a type struct Matrix<T, R, C, S> where T is the components scalar type, R and C represents the number of rows and columns and S represents the type of the buffer containing the data.

Relevant for const generics are the parameters R and C. These are instantiated using one of the following types:

#![allow(unused)]
fn main() {
// For matrices of know size.
pub struct Const<const R: usize>;
// For matrices with a size only known at runtime.
pub struct Dynamic { value: usize }
}

The authors of nalgebra then introduce a type alias

#![allow(unused)]
fn main() {
pub struct ArrayStorage<T, const R: usize, const C: usize>(pub [[T; R]; C]);
/// A matrix of statically know size.
pub type SMatrix<T, const R: usize, const C: usize> =
    Matrix<T, Const<R>, Const<C>, ArrayStorage<T, R, C>>;
}

To deal with the lack of generic const expressions, they add a trait for conversions from and to typenum for all Const up to size 127 (source).

Whenever they now need some computation using Const<N>, they convert it to type nums, evaluate the computation using the trait system, and then convert the result back to some Const<M>.

Disadvantages

While this mostly works fine, there are some disadvantages.

Annoying ToTypenum bounds

Most notably this adds a lot of unnecessary bounds, consider the following impl:

#![allow(unused)]
fn main() {
impl<T, const R1: usize, const C1: usize, const R2: usize, const C2: usize>
    ReshapableStorage<T, Const<R1>, Const<C1>, Const<R2>, Const<C2>> for ArrayStorage<T, R1, C1>
where
    T: Scalar,
    Const<R1>: ToTypenum,
    Const<C1>: ToTypenum,
    Const<R2>: ToTypenum,
    Const<C2>: ToTypenum,
    <Const<R1> as ToTypenum>::Typenum: Mul<<Const<C1> as ToTypenum>::Typenum>,
    <Const<R2> as ToTypenum>::Typenum: Mul<
        <Const<C2> as ToTypenum>::Typenum,
        Output = typenum::Prod<
            <Const<R1> as ToTypenum>::Typenum,
            <Const<C1> as ToTypenum>::Typenum,
        >,
    >,
{
    type Output = ArrayStorage<T, R2, C2>;

    fn reshape_generic(self, _: Const<R2>, _: Const<C2>) -> Self::Output {
        unsafe {
            let data: [[T; R2]; C2] = mem::transmute_copy(&self.0);
            mem::forget(self.0);
            ArrayStorage(data)
        }
    }
}
}

As these bounds infect the public API, they are also a large backwards compatability concern.

ToTypenum is only implemented up to fixed size

That’s annoying. ✨

Cannot use associated constants

It is currently also not possible to have the size of a matrix depend on associated constants:

#![allow(unused)]
fn main() {
trait MyDimensions {
   const ROWS: usize;
   const COLS: usize;
}

fn foo<Dims: MyDimensions>() {
    // Not possible!
    let matrix: SMatrix<f64, Dims::ROWS, Dims::COLS> = SMatrix::zeros();
}
}

While this can be avoided by going to back to typenum and using associated types, this adds a lot of unnecessary bounds and inpacts all of the code dealing with it.

Generic parameters aren’t exhaustive

Because R and C are generic parameters and not constants, the compiler doesn’t know that DefaultAllocator: Allocator<T, R, C> holds for all R and C, leaking implementation defaults and causing signatures to be far less readable than necessary.

Wishlist

Ideally, Matrix could be changed to the following:

#![allow(unused)]
fn main() {
enum Dim {
    Const(usize),
    Dynamic,
}

struct Matrix<T, const R: Dim, const C: Dim, S> { ... }

type SMatrix<T, const R: usize, const C: usize> =
    Matrix<T, Dim::Const(R), Dim::Const(C), ArrayStorage<T, R, C>>;
}

For this to work well there have a bunch of requirements for const generics:

User-defined types as const parameter types

We have to be able to use Dim as a const param type

Consider injective expressions to bind generic params

With this change, nalgebra needs impls like the following

#![allow(unused)]
fn main() {
impl<T, const R: usize, const C: usize> for SMatrix<T, R, C> {
    // ...
}
}

For this impl to bind R and C, the expression Dim::Const(N) has to bind N. This is sound as constructors are injective. It seems very desirable to at least enable this for expressions using constructors.

Without this, one gets an error message like the following:

error[E0207]: the const parameter `R` is not constrained by the impl trait, self type, or predicates
 --> src/lib.rs:5:12
  |
5 | impl<T, const R: usize, const C: usize> for SMatrix<T, R, C> {
  |               ^ unconstrained const parameter
  |
  = note: expressions using a const parameter must map each value to a distinct output value
  = note: only used in the expression `Dim::Const(R)`
  = note: proving the result of expressions other than the parameter are unique is not supported

Merge partial impls to be exhaustive

By adding one trait impl impl for Dim::Dynamic and one for Dim::Const(N), it should be enough to consider that trait to be implemented for all Dim.

Ideally, the compiler should figure this out by itself, or it can be emulated using specialization by manually adding an impl for all Dim which always gets overridden.

Generic const expressions

For example when computing the Kronecker product which has the following simplified signature:

#![allow(unused)]
fn main() {
pub fn kronecker<T, const R1: Dim, const C1: Dim, const R2: Dim, const C2: Dim>(
    lhs: &Matrix<T, R1, C2>,
    rhs: &Matrix<T, R2, C2>,
) -> Matrix<T, R1 * R2, C1 * C2> {
    ...
}
}

For this generic const expressions have to be supported.

const Trait implementations

For R1 * R2 to work we need const trait impls, otherwise this can be written using mul_dim(R1, R2) or something.

Default for arrays

nalgebra currently has to work around Default not being implemented for all arrays where T: Default.

✨ Shiny future: Where we want to get to

The “shiny future” is here to tell you what we are trying to build over the next 2-3 years. That is, it presents our “best guess” as to what will look like a few years from now. When describing specific features, it also embeds links to design notes that describe the constraints and general plans around that feature.

Predicting the future is a tricky business! Many of the things described in the “shiny future” doc have a lot of uncertainty. We fully expect that the designs and narratives described in this document will change as we work towards realizing them. When there are areas of particular uncertainty, we use the Frequently Asked Questions and the design docs to call them out.

✨ Shiny future story: Barbara implements Default for all array lengths

Shiny future of status quo story

Barbara is working on std. She saw that the newest version of rustc has had some improvements to const generics and decides to try implementing Default for all array lengths. She goes to write:

#![allow(unused)]
fn main() {
impl<T, const N: usize> Default for [T; N]
where
    T: Default,
{
    fn default() -> Self {
        /* snip */
    }
}
}

The code builds just fine but then she sees a test failing:

#![allow(unused)]
fn main() {
fn generic<T>() -> [T; 0] {
    Default::default()
}
}

“Ah,” she says, “I see that Default is implemented for any type [T; 0], regardless of whether T: Default. That makes sense. Argh!”

Next she tries to write:

#![allow(unused)]
fn main() {
impl<T, const N: usize> Default for [T; N]
where
    T: Default,
    { N > 0 },
{
    fn default() -> Self {
        /* snip */
    }
}

impl<T> Default for [T; 0] {
    fn default() -> Self {
        []
    }
}
}

This compiles just fine and the test is passing. She decides to submit a PR where her reviewer asks her to add a test to make sure that [T; N]: Default holds when T: Default as this didn’t used to work

#![allow(unused)]
fn main() {
fn exhaustive_default_impl<T: Default, const N: usize>() -> [T; N] {
    <[T; N] as Default>::default()
}
}

This test passes just fine, “yay const generics ✨” she says

✨ Shiny future story: Array split first method

Shiny future of status quo story

Barbara is working on her project. She has the idea to write a split_first function that will allow her to split out the first item from a fixed-length array; naturally, the array must be non-empty. It looks something like this:

#![allow(unused)]
fn main() {
// Note: this method has an implied where clause that `N - 1` evaluates without 
// erroring because `N - 1` is in the function signature
fn split_first<T, const N: usize>(arr: [T; N]) -> (T; [T; N - 1]) {
    // ...
    let tail: [T; N - 1] = // ...
    (head, tail)
}
}

Next she wants to write a function that uses split_first:

#![allow(unused)]
fn main() {
fn some_method<const N: usize>(arr: [u8; N]) {
    let (first, rest) = split_first(arr);
    for i in rest {
        // ...
    }
}
}

The compiler gives her a compile error:

error: the constant expression `N - 1` is not known to evaluate without underflowing
2 |     let (first, rest) = split_first(arr);
  |                         ^^^^^^^^^^^ `N - 1` not known to be evaluatable without underflowing
note: required by this expression in `split_first`'s function signature
5 |     fn split_first<T, const N: usize>(arr: [T; N]) -> (T; [T; N - 1]) {
  |                                                               ^^^^^
help: add a where clause to `some_method`
  | fn some_method<const N: usize>(arr: [u8; N]) where { N > 0; }

Barbara hits the ‘quick fix’ button in her IDE and it inserts the where clause for her- she immediately gets a compile error at another spot because she was calling some_method with an empty array:

error: the constant `0` is not greater than `0`
22 |     some_method([])
info: `0` must be greater than `0` because of this where clause
  | fn some_method<const N: usize>(arr: [u8; N]) where { N > 0; }
  |                                                    ----------

Barbara has no more compile errors, even the following code is compiling:

#![allow(unused)]
fn main() {
fn some_other_method<const N: usize>(arr: [u8; N]) where { N > 1; } {
    // ...
    let (first, rest) = split_first(arr);
    // ...
}
}

✨ Shiny future story: Image type in rust-gpu

Barbara is working on rust-gpu. In that project, she has a struct Image that represents GPU images. There are a number of constant parameters allowing this type to be heavily customized in a number of ways. In some cases, helper methods are only available for images with particular formats. She writes the struct declaration:

#![allow(unused)]
fn main() {
struct Image<
    SampledType: SampleType<FORMAT>,
    const DIM: Dimensionality,
    const DEPTH: ImageDepth,
    const ARRAYED: Arrayed,
    const MULTISAMPLED: Multisampled,
    const SAMPLED: Sampled,
    const FORMAT: ImageFormat,
    const ACCESS_QUALIFIER: Option<AccessQualifier>,
>(PhantomData<SampledType>);
}

Barbara gets a few compile errors about her types used as a const param not implementing StructuralEq so she derives that and moves on. She then wants to write some methods that only work for images in some specific formats:

#![allow(unused)]
fn main() {
impl<
    SampledType: SampleType<FORMAT>,
    const DIM: Dimensionality,
    const DEPTH: ImageDepth,
    const ARRAYED: Arrayed,
    const MULTISAMPLED: Multisampled,
    const SAMPLED: Sampled,
    const FORMAT: ImageFormat,
    const ACCESS_QUALIFIER: Option<AccessQualifier>,
> Image<SampledType, DIM, DEPTH, ARRAYED, MULTISAMPLED, SAMPLED, FORMAT, ACCESS_QUALIFIER> {
    pub fn example_method(/* snip */)
    where
        { some_condition(DEPTH, MULTISAMPLED) }
    { /* snip */ }
}

const fn some_condition(a: ImageDepth, m: Multisampled) -> bool {
    match (a, m) {
        /* snip */
    }
}
}

This compiles just fine and Barbara moves on to more complicated things

📅 The roadmap: what we’re doing in 2021

This page describes the current plans for 2021. It is updated on a monthly basis.

Key

Roadmap items

❓ How to vision doc

This page describes the process for contributing to the vision doc.

Who owns this document?

This document is owned and maintained by the leads of the project-const-generics group. They decide what content to accept or reject. This decision is made in consultation with the Rust teams that will be making the ultimate decisions. For example, if a design doc or part of the shiny future is describing a new language feature, the leads ought to discuss that with the language design team, since that team will ultimately have to approve the RFCs for its design.

How to participate

For now, you have to join our weekly meetings.

Meetings

This folder contains the minutes of all the recorded meetings that have happened so far.

Check them out on github.

✏️ RFC drafts

This folder contains drafts of RFCs that the group is preparing to submit.

📁 Documents

This folder might contain various documents that are not RFCs or vision, but still are relevant for the project and worth keeping.

The plan for min_generic_const_args

Note

This document was written back in 2024 and has not been updated since. It may contain dated/incorrect information.

Where does min_const_generics fall short

The min_const_generics feature was stabilized at the end of 2020 with a few significant limitations. These limitations are explained nicely in WithoutBoats’ blog post titled Shipping Const Generics in 2020 and is reccomended reading before continuing.

The focus of this document is on allowing more complex expressions involving generic parameters to be used as const arguments, “No complex expressions based on generic types or consts” as titled in boats’ blog post.

This document intends to explain:

• Why it is hard to allow arbitrary expressions involving generic parameters to be used in the type system
• What design the const generics project group intends to pursue in order to allow more complex expressions involving generic parameters.
• How the proposed design avoids pitfalls encountered by previous experimentation in this area.

Why does generic_const_exprs not work

Allowing complex expressions involving generic parameters has been experimented with under the generic_const_exprs feature gate for the past few years. In short it allows writing code such as [u8; <T as Trait>::ASSOC] or where Foo<{ N + 1 }>: Other<M>; arbitrary expressions are supported as const arguments regardless of whether they involve generic parameters or not.

Background implementation details

Currently const arguments (even under min_const_generics) are implemented by desugaring the const argument to a const item (called anonymous constants) and then referring to it. For example under min_const_generics:

#![allow(unused)]
fn main() {
fn foo<T: Trait>(arg: T) -> [T; MY_CONST + 2] {
    /* ... */
}

// gets desugared to:

const ANON: usize = MY_CONST + 2;
fn foo<T: Trait>(arg: T) -> [T; ANON] {
    /* ... */
}
}

The implementation strategy for generic_const_exprs is that the implicitly created ANON has the same generics and where clauses defined on it as foo. Additionally we also implicitly create terminates { ... } where clauses for any const arguments used in the signature (more on this later).

The previous example with the generic_const_exprs feature gate enabled would be desugared like so:

#![allow(unused)]
#![feature(generic_const_exprs)]

fn main() {
fn foo<T: Trait>(arg: T) -> [T; MY_CONST + 2] {
    /* ... */
}

// gets desugared to:

const ANON<T: Trait>: usize = MY_CONST + 2
where
    terminates { ANON::<T> };
fn foo<T: Trait>(arg: T) -> [T; ANON]
where
    terminates { ANON::<T> }
{
    /* ... */
}
}

With all that covered we can begin to talk about the issues with the current design of generic_const_exprs.

Const arguments that fail to evaluate

In Rust not all expressions are guaranteed to terminate and return a value, they can loop forever, panic, encounter UB, etc. This introduces some complexity for const generics as we must decide on how to handle a const argument such as Foo<{ usize::MAX + 1 }> or Foo<{ loop {} }>.

While the previous examples are relatively easy to determine that they will panic and loop forever respectively, it is not so easy in the general case. This is quite literally the halting problem.

A conservative analysis is, in general, possible in order to guarantee termination of functions (a lot of functional programming languages implement this). Implementing this would require another function modifier, e.g. const terminates fn foo() -> usize; and generally complicate the language significantly.

The (stabilized) min_const_generics feature handles this by requiring any complex expressions to not use generic parameters, this means it is always possible to try to evaluate the expression. If it fails to evaluate then we error, otherwise we have a value.

As generic_const_exprs supports arbitrary expressions that do use generic parameters, such as Foo<{ N + 1 }>, it is no longer always possible to evaluate a const argument as it may involve generic parameters that are only known after monomorphization.

Given the example of Foo<{ N + 1 }> it would panic when usize::MAX is provided as the value of N. Some ways this could potentially be handled, one of which was already mentioned, would be:

• Introduce a terminates function modifier and have an addition function that is guaranteed to terminate if the type system can prove N < usize::MAX
• Post monomorphization errors for when generic arguments are provided to N that would happen to cause it to fail to evaluate
• Require the caller to prove that { N + 1 } will terminate

The last option is what generic_const_exprs implements, to give a concrete example:

#![feature(generic_const_exprs)]

fn foo<const N: usize>() -> [u8; N] {
    /* ... */
}

fn bar<const N: usize>()
where
    terminates { N + 1 },
{
    // fine, caller has checked that `{ N + 1}` will terminate
    foo::<{ N + 1 }>();
}

fn baz() {
    // fine, `{ 10 + 1 }` terminates
    bar::<10>();    
    
    // ERROR: `{ { usize::MAX } + 1 }` will panic
    bar::<{ usize::MAX }>();
}

fn bar_caller_2<const N: usize>()
where
    terminates { { N * 2 } + 1 },
{
    // fine, caller has checked that `{ { N * 2 } + 1 }` will terminate
    bar::<{ N * 2 }>();
}

fn main() {
    baz();
    
    // fine, `{ { 10 * 2 } + 1 }` terminates
    bar_caller_2::<10>();
    
    // ERROR: `{ { { usize::MAX - 100} * 2 } + 1 }` will panic
    bar_caller_2::<{ usize::MAX - 100 }>();
}

Sidenote: In the actual implementation these bounds are not written as they are in the example. I opted to use terminates { ... } syntax as it is significantly more readable than what is actually implemented.

These terminates bounds are a huge design issue with the current feature as they require putting large amounts of implementation details of the function in its public API. I would not expect us to want to stabilize anything with this solution.

Unrecoverable CTFE errors

In general the trait system should be able to fail in arbitrary ways without causing compilation to fail. This requirement comes from a few places:

• Coherence evaluates where clauses and if they fail to hold use that information to consider impls to not overlap.
• During type checking/trait solving we often speculatively try some inference constraints and if they succeed great, otherwise we try other inference constraints

In these cases we can wind up evaluating generic constants with generic arguments that would cause evaluation failures. For example the following example:

#![allow(unused)]
fn main() {
trait Trait<const N: usize> {
    type Assoc;
}
impl<const N: usize> Trait<N> for [u8; N - 1]
where
    terminates { N - 1 }
{
    type Assoc = u32;
}
impl Trait<0> for [u8; 0] {
    type Assoc = u64;
}
}

In this example coherence attempts to check whether the two impls are overlapping or not. In order to do this we wind up inferring N=0 and then trying to prove all of the where clauses on the generic impl.

The generic impl has only one where clause:terminates { N - 1 }, with generic arguments applied this is actually terminates { 0 - 1 }. Evaluating 0 - 1 panics which emits a hard error by the const eval machinery.

As hard errors are unrecoverable we wind up erroring on this code with the message that evaluating 0 - 1 failed even though in theory this ought to succeed compilation.

While terminates bounds were used in this example as it is a very simple demonstration of the issue, they are not strictly required to demonstrate this and so removing terminates bounds would not solve this.

Changing const eval to not emit a hard error when failing to evaluate constants is undesirable as the current setup prevents a lot of potential issues that could arise from forgetting to emit an error in other cases.

Any design for generic const arguments needs to be able to avoid evaluating constants that might not succeed or else there will be weird behaviour and error messages in coherence and trait solving.

Checking equality of generic consts causes query cycles

The type system representation of constants must be able to represent the actual expressions written not just a usage of an anon const. This is so that two separate { N + 1 } expressions are considered to be equal.

For example the following code should compile even though N + 1 is written in two different places and would result in two diferent anon consts:

#![allow(unused)]
#![feature(generic_const_exprs)]

fn main() {
fn foo<const N: usize>(a: Bar<{ N + 1 }>)
where
    Bar<{ N + 1 }>: Trait,
{
    baz(a)
}

fn baz<T: Trait>(_: T) { }
}

The way that generic_const_exprs handles this is by looking at the THIR (post-typeck hir) of anon consts and then lowering it to a new AST specifically for type level expressions.

The requirement that we first type check the anon const before being able to represent its normalized form in the type system causes a lot of query cycle isues when anon consts are used in where clauses.

These cycles tend to look something like the following:

• Try to type check an anon const in a where clause
• Type checking that anon const requires doing trait solving
• Trait solving tries to use a where clause containing the original anon const
• We try to type check the original anon const again

A concrete example of this kind of thing would be the following code:

#![allow(unused)]
#![feature(generic_const_exprs)]

fn main() {
trait Trait<const N: usize> {
    const ASSOC: usize;
}

fn foo<T, U, V, const N: usize>()
where
    T: Trait<{ N + 1 }>,
    T: Trait<{ <T as Trait<{ N + 1 }>>::ASSOC }>,
{
    
}
}

In this example we might encounter a cycle like so:

• We try to type check { <T as Trait<{ N + 1 }>>::ASSOC }
• This requires proving T: Trait<{ N + 1 }>
• There are 2 possible where clauses that from the trait solvers POV could be used:
  • T: Trait<{ N + 1 }>
  • T: Trait<{ <T as Trait<{ N + 1 }>>::ASSOC }>
    • From the trait solvers POV { <T as Trait<{ N + 1 }>>::ASSOC } is potentially normalizeable to { N + 1 } in which case this would be a valid way of proving T: Trait<{ N + 1 }>
• Trying to determine if { N + 1 } is equal to { <T as Trait<{ N + 1 }>>::ASSOC } requires type checking both anon consts. As we are already type checking { N + 1 } we have reached a cycle.

Attempting to represent type system constants through a lowering step after type checking therefore seems like a dead end to me as this is code that we should support (equivalent code written with associated types compiles fine).

Unused generic parameters

The current desugaring can easily result in an anon const having more generics defined on it than are actually used by the body. Take the following example:

#![allow(unused)]
fn main() {
struct Foo<T, U, const N: usize> {
    arr: [u64; N + 1],
    ...
}

// desugars to:

const ANON<T, U, const N: usize>: usize = { N + 1 }
where
    terminates { ANON::<T, U, N> };
struct Foo<T, U, const N: usize>
where
    terminates { ANON::<T, U, N> }
{
    arr: [u64; ANON::<T, U, N>],
    ...
}
}

The type [u64; ANON::<T, U, N>] “uses” all of the generic parameters in scope which causes a number of issues:

• All generic parameters on the struct are invariant due to them all being used in a const alias
• Causes issues with object safety as an anon const would be considered to “use” the Self type
• Breaks with defaulted generic parameters as the anon const is considered to use all parameters even forward declared parameters

Evaluating constants with where clauses that do not hold

Const eval should generally not be run on bodies that do not type check as doing so can easily cause ICEs. Attempting to change const eval to support running on bodies that do not type check would introduce a large amount of complexity to const eval machinery and is undesirable.

Unfortunately the current implementation of generic_const_exprs does not check that where clauses on anon consts hold before evaluating them. This results in const eval ICEing sometimes when using complex expressions with generic parameters in where clauses.

In theory it would be simple to ensure that the where clauses hold before evaluating a constant. In practice this would drastically worsen the previous issue about query cycles to the point where evaluating any anon const in a where clause would cause a query cycle.

This is caused by the fact that anon consts are desugared to having all of the where clauses in scope (similar to how they have more generics than is strictly necessary). This means that an anon const inside of a where clause, would be desugared to having that same where clause. Example:

#![allow(unused)]
fn main() {
fn foo<T, const N: usize>()
where
    T: Trait<{ N + 1 }>,
{}

// desugars to:

const ANON<T, const N: usize>: usize = { N + 1 }
where
    T: Trait<ANON::<T, N>>,
    terminates { ANON::<T, N> };
fn foo<T, const N: usize>()
where
    T: Trait<{ ANON::<T, N> }>,
    terminates { ANON::<T, N> },
}

Attempting to evaluate ANON::<concrete, concrete> would first require proving terminates { ANON::<concrete, concrete> }, which is proven by evaluating ANON::<concrete, concrete>.

Any design for supporting complex expressions involving generic parameters needs to be able to only evaluate constants when they are wellformed.

Can we fix generic_const_exprs?

Having highlighted the core issues with the current implementation of the feature it’s worth trying to figure out if we can just solve these and then stabilize it. To summarize the requirements above we would wind up with:

1. How do we represent type system consts without requiring a hir body that first need to be type checked
2. How to make sure constants only use the “right” amount of generic parameters
3. How do we make sure its possible that constants be checked for wellformedness before evaluating them
4. How to avoid evaluating constants that might not terminate
   • I am combining the two headers of “how to handle N + 1 where N=usize::MAX” and “how to avoid hitting unrecoverable CTFE errors” as these wind up being incredibly similar problems

To start with we would have to stop using the current desugaring with creating const items- it’s fundamentally incompatible with wanting to represent type system constants without requiring type checking a body first.

Instead we need to have a new kind of AST for representing expressions in the type system. There are a number of concerns here:

• We would have an entire second way of type checking expressions
• How do we handle evaluating this AST
• What expressions do we support? method calls such as a.foo(N) would add a significant amount of complexity to the type system which is undesirable, so we cant just say “all of them”.

Regardless, this would solve issues 1, 2, and 3. The new desugaring would result in only syntactically used generic parameters being present in the AST. Additionally the minimal required where clauses to hold for the const argument to be wellformed can be derived from the AST.

For the next issue (4) I can see a couple possible solutions:

• Simply accept that the type system will be buggy and error on your code for little to no reason, and you have to work around it
• Introduce a simplistic termination checker to rust used by generic_const_exprs and only permit calls to functions that are statically known to terminate

Simply accepting a buggy type system implementation seems out of the question to me. It is not a good look for the language to decide to stabilize something with bugs without any plan for how they could ever be resolved.

As an additional point, if we accepted the buggy behaviour we would still need to decide how to handle N + 1 as an argument when a concrete value of usize::MAX was provided for N. Post monomorphization errors are an “obvious” solution to this that would work from a technical standpoint.

Introducing a termination checker is a significant undertaking that would take a long time to fully work out the design of- let alone have it in a stabilizable state. I imagine this would take many years and also significantly increase the complexity of the language.

In conclusion while there is potentially a path here to having everything work, there is a large number of open questions and issues with those potential solutions. Regardless of what is decided it would potentially take years to get something into a stabilizable state, and that assumes that this will actually work out.

While generic_const_exprs itself might be a rather long way off, it should be possible to carve out a subset of the feature that is possible to get working nicely in a much shorter timeframe, e.g. a min_generic_const_args feature.

What is min_generic_const_args

On stable there are limitations to what a const generic parameter can have as its argument, concretely this is:

• A single parameter { N }
• An arbitrary expression that does not mention any generic parameters, e.g. { foo() + 10 / 2 }

The min_generic_const_args will extend this to also support:

• A usage of an associated constant with arbitrary generic parameters, e.g. <T as Trait<N>>::ASSOC so long as the definition is marked #[type_system_constant].

Similar to how uses of const parameters does not require explicit braces, the same is true of uses of associated constants. Foo<<T as Trait>::ASSOC> is legal without requiring it to be written as FOO<{ <T as Trait>::ASSOC }>. (maybe, might get cut, but it seems nice)

In order for an associated constant to be usable with generic parameters as an argument to a const generic parameter it must be marked with #[type_system_constant] on the trait definition. This attribute will require all trait implementations to specify a valid const generic argument as the value of the associated constant instead of an arbitrary unrestricted expression.

Example:

#![allow(unused)]
fn main() {
trait Trait {
    const ASSOC: usize;
}

impl<const N: usize> Trait for Foo<N> {
    const ASSOC: usize = N;
}

fn foo<const N: usize>() {}

fn bar<T: Trait>() {
    // ERROR: `Trait::ASSOC` is not marked as `#[type_system_constant]` and so
    // cannot be used in the type system as a const argument.
    foo::<<T as Trait>::ASSOC>();
}
}

If trait definition was rewritten to to use the #[type_system_constant] attribute then this would compile:

#![allow(unused)]
fn main() {
trait Trait {
    #[type_system_constant]
    const ASSOC: usize;
}
}

This restriction is required to ensure that implementors of Trait are not able to write arbitrary expressions as the value of the associated constant, instead a valid const generic argument must be written. For example:

#![allow(unused)]
fn main() {
impl<const N: usize> Trait for Foo<N> {
    // ERROR: `N + 1` is not a valid expression in the type system 
    const ASSOC: usize = N + 1;
}
}

Does this actually fix the original problems?

Reusing the list of issues from earlier:

1. How do we represent type system consts without requiring a hir body that first need to be type checked
2. How to make sure constants only use the “right” amount of generic parameters
3. How do we make sure its possible that constants be checked for wellformedness before evaluating them
4. How to avoid evaluating constants that might not terminate

The first problem is easy to solve with associated constants as they have an obvious representation, a DefId + list of generic args (the same as we do for associated types). This also does not introduce any of the complexities with trying to represent arbitrary expressions:

• Evaluating associated constants is trivial as the compiler already has the machinery for this
• There is no need to figure out how to type check or borrow check arbitrary type system expressions as associated constants have simple rules around wellformedness already present in the compiler, and they just inherently don’t need borrow checking.

It is also trivial to tell what generic parameters a const argument uses as they are explicitly defined on the trait, the same as how associated types are handled in the compiler which has been shown to work adequately.

The requirement that all associated constants in the type system are defined as being equal to a valid const argument means that ensuring all constants in the type system terminate is as easy as it is under min_const_generics. An associated constant can either be assumed to terminate successfully or simply be evaluated and then error if that fails.

This also means that it is trivial to avoid evaluating constants that might not terminate as every const generic argument will have already been checked somewhere that it can be evaluated without issues, e.g. in the caller or in an associated const’s definition.

Determining that const arguments are well formed before evaluating them is also trivial as we do not wind up with such recursive where clauses as all where clauses are explicitly written by the user on the trait or the associated const itself.

Future extensions to min_generic_const_args

• Support struct/enum construction for when arbitrary types are allowed as const generics.
• Special case size_of/align_of to be permitted too?
• Experiment with permitting arbitrary expressions as described in Can we fix generic_const_exprs or by allowing arbitrary expressions to be used for associated consts in the type system
• Introducing where clauses that allow bounding generic parameters, e.g. a hypothetical where N is 1..?