# cg vision doc
## motivating examples
* Writing an impl for all array types `[T; N]` for any `N`
* implement `[T; N]: Default` for all `N` :+1: (also an issue for `serde`)
* Make a compile-time expression template library.
* something that can express a tree at compilation time
* [Boost MPL](https://www.boost.org/doc/libs/1_76_0/libs/mpl/doc/index.html)
* Make an N-dimensional array library that uses the previous point to do lazy computations
* One can ideally materialize on demand and this would fuse all loops/do code-gen ish stuff and do the computation.
* The mode, and ideally the dimension sizes of the arrays can also be made const.
* e.g. [`xtensor`](https://github.com/xtensor-stack/xtensor).
* Writing a generic abstraction modifying arrays is still not possible if the abstraction needs to change array lengths (generic const expressions).
* for example `fn split_first<const N: usize>(a: [u8; N]) -> (u8; [u8; N - 1])`
* Cool things people can do in C++:
* XXX
## key points and questions
* associated constants in traits
* `trait Foo { const N: usize; }`
* const fn in traits (and then in impls)
* `trait Foo { const fn compute(&self) -> usize; }`
* See https://github.com/rust-lang/rfcs/pull/2632 for similar questions.
* const fn in impls
* `impl Something for Foo { const fn compute(&self); }`
* where the trait is not `const`?
* being able to say that a trait is implemented with const fn in a where clause
* equality and the limits thereof
* types parametric over functions `struct Foo<const F: fn()>` or `struct Foo<T: Fn()>` or something.
* range of expressions we expect to be legal in constants
* unsafe code?
* limits of promotion
* able to write impls for all constants
* checking that multiple impls are exhaustive together, e.g. `0` and `N > 0` (for unsigned integers).
* dealing with "things that might be const"
* e.g., ralf's [const-safe proposal](https://www.ralfj.de/blog/2018/07/19/const.html)
## status quo stories
### Alan/Grace/Barbara wants to parameterize her type with enums
https://rust-lang.zulipchat.com/#narrow/stream/260443-project-const-generics/topic/meeting.202021-04-27/near/236964582
### Alan wants a maths library using arrays
https://rust-lang.zulipchat.com/#narrow/stream/260443-project-const-generics/topic/meeting.202021-04-27/near/237079733
### Barbara wants to implement `Default` for all array types
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](https://doc.rust-lang.org/nightly/src/core/array/mod.rs.html#391))
She thinks "Ah, I can use min-const-generics for this!" and goes to write
```rust=
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:
```rust=
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](https://doc.rust-lang.org/std/primitive.array.html#method.map). She could write:
```rust=
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:
```rust=
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)
```rust=
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.
```rust=
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.
### Barbara wants to replace her uses of `typenum` with const generics
TODO: write this
- needs generic const operations
### Barbara extends rust-gpu with `Image` types
## shiny future stories
### Barbara wants to implement `Default` for all array types
Barbara is working on `libstd`. She wants to implement `Default` for all array types. Currently, it is implemented for `N <= 32` using a macro ([link](https://github.com/rust-lang/rust/blob/1919b3f22706fee0b2c6ac3d42316545900b7734/library/core/src/array/mod.rs#L369-L371))
She goes to write
```rust=
impl<T, const N: usize> Default for [T; N]
where
T: Default,
{ N != 0 },
{
// ...
}
impl<T> Default for [T; 0] {
// ...
}
```
or alternatively, uses specialization to write something like
```rust=
impl<T, const N: usize> Default for [T; N]
where
T: Default,
{
// ...
}
impl<T> Default for [T; 0] {
// ...
}
```
### rust-gpu shiny future
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 can represent at compilation time using associated constants:
```rust=
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(...)
where
{ some_condition(DEPTH, MULTISAMPLED) }
{ }
}
struct ImageDepth { value: u32 }
enum Multisampled { True, False }
const fn some_condition(a: ImageDepth, m: Multisampled) -> bool {
match (a, m) {
...
}
}
```
### Evaluatable
#### Version A: Evaluatable
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:
```rust=
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`:
```rust=
fn some_method<const N: usize>(arr: [u8; N]) {
let (first, rest) = split_first(arr);
for i in rest {
// ...
}
}
```
The compiler gives her an error message:
```
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 evaluatable { N - 1 }
```
Barbara hits the "quick fix" button in her IDE to add the where clause.She immediately gets an error at another spot:
```
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 evaluatable { N - 1 }
| ---------------------
```
**Notes:**
* `split_first` has an implied where clause based on its return type that `N-1` must be evaluatable.
* The compiler is very dumb and doesn't understand the semantics of expressions at all. It *can* see that the expression is known to be evaluatable though if *exactly* that expression appears in the where clause.
* as an example: having `N-2` in the bounds does not allow you to compute `N-1`, even though there are no failure conditions where `N-1` could fail but `N-2` couldn't
#### Version B: Smarter compiler
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:
```rust=
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`:
```rust=
fn some_method<const N: usize>(arr: [u8; N]) {
let (first, rest) = split_first(arr);
for i in rest {
// ...
}
}
```
The compiler gives her an error message:
```
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 > 0 }
```
Barbara hits the "quick fix" button in her IDE to add the where clause. She immediately gets an error at another spot:
```
error: where clause does not hold
22 | some_method([])
| ^^^^^^^^^^^^^^^ `0 > 0` is not true
info: `0 > 0` must be evaluatable because of this where clause
| fn some_method<const N: usize>(arr: [u8; N]) where { N > 0 }
| ---------
```
**Notes:**
* `split_first` has an implied where clause based on its return type that `N-1` must be evaluatable.
* The compiler is able to reason symbolically and determine that knowing `N > 0` is true allows `N - 1` to be evaluated.
* What are the limits on how smart it can get?
#### Version C: Monomorphization 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:
```rust=
fn split_first<T, const N: usize>(arr: [T; N]) -> (T; [T; N - 1]) {
// ...
let tail: [T; N - 1] = // ...
(head, tail)
}
```
Next she writes a function that uses `split_first`:
```rust=
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] = // ...
```
**Notes:**
* The failure to evaluate `N-1` is not detected until we monomorphize.
Google Drive
Gist
Clipboard
Sign in with Wallet
