๐๐ฝ 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-skill-tree install && 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.
Skill tree for const generics features
๐ฑ 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
Emoji | Meaning |
---|---|
๐ฅฌ | "Healthy" -- on track with the plan as described in the doc |
โ๏ธ | "Planning" -- Still figuring out the plan |
๐ค | "Worried" -- things are looking a bit tricky, plans aren't working out |
๐๏ธ | "On vacation" -- taking a break right now |
โฐ๏ธ | We gave up on this idea =) |
Roadmap items
Plan | Owner | Status | Last updated |
---|
โ 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.