# Const Generics Big Pictures

This is a rough outline of a variety of possible "big picture" designs for const generics. Not focusing too much on impl details or minutea but just generally how things can fit together in the long term.

## Minimal Present for Const Generics

The current stable design

### Design

The types `uN`, `iN`, `char` and `bool` can be used as the type of a Const Generic Parameter. Put another way, when writing `fn foo<const N: Ty>` the compiler will check that `Ty` is one of the above types.

---

Const Generic Arguments are allowed to be a path to a Const Generic Parameter:

fn path() -> [(); N] {

Const Generic Arguemnts are allowed to be an arbitrary non-generic expression:

fn non_generic_expr<const N: usize>() -> [(); 1 + 1] { ... }
// illegal as `N + 1` uses generic parameters and doesn't match any
// of the other forms of accepted expressions
fn generic_expr<const N: usize>() -> [(); N + 1] { ... }

Note: there is technically an extra rule to handle the length of array repeat expressions but that isn't intended to exist as an actual thing in the type system. It is FCW'd and will be removed eventually: https://github.com/rust-lang/rust/issues/76200

### Unsolved Use Cases

Most of them

## Slightly Sparkly Future for Const Generics

A potential future state that doesn't solve all use cases but is cohesive, implementable, and a large step forwards. The design here is largely implemented as the following set of features:
- `min_generic_const_args` (all the type const stuff)
- `min_adt_const_params` (the `ConstParamTy` stuff)
- `generic_const_parameter_types` (the ability to write `const N: T`)
- `generic_const_items` (being able to make type consts be generic)

### Design

If a type implements the `ConstParamTy` trait it can be used as the type of a Const Generic Parameter. Put another way, when writing `fn foo<const N: Ty>` the compiler will check that `Ty: ConstParamTy` holds.

It follows from this that generic parameters can be used as the type of a Const Generic Parameter if there is a `T: ConstParamTy` where clause: `fn foo<T: ConstParamTy, const N: T>`.

The following builtin types implement the `ConstParamTy` trait:
- `bool`
- `char`
- `iN` and `uN`
- `[T; N] where T: ConstParamTy`
- `(...T) where ...T: ConstParamTy`
- all(?) function item types

For an implementation of `ConstParamTy` to be accepted, the types of all fields must themselves implement `ConstParamTy`. For structs/enums all fields must be as public as the struct/enum itself, and the struct/variants must not be marked `non_exhaustive`.

---

A new kind of item is introduced, `typeconst` which is an *alias* to a Const Generic Argument: `typeconst $ident: $ty = $constarg;`. `typeconst` items may have generic parameters and where clauses.

typeconst FOO<const N: usize>: usize = N; // legal

// illegal as `fn_call(N)` is not a valid Const Generic Argument
typeconst BAR<const N: usize>: usize = fn_call(N);

The type of a `typeconst` item must implement `ConstParamTy`.

If a trait definition has an associated `typeconst` then the trait impl must also implement the associated `typeconst`.

Associated `typeconst`s don't make a trait dyn incompatible. A trait object whose trait has associated `typeconst`s must specify all the values of the `typeconst`s.

Associated type consts can be bounded via associated const bindings (similar to that of types).

trait Trait { typeconst ASSOC: usize }
fn foo<T: Trait<ASSOC = 10>>() {}

---

Const Generic Arguments are allowed to be a path to a Const Generic Parameter[^1]:

typeconst FOO<const N: usize>: usize = N;

Const Generic Arguments are allowed to be paths to `typeconst` items and these paths may involve generic parameters:

typeconst BAZ<const N: usize>: usize = FOO::<N>;
fn foo<const N: usize>() -> [(); BAZ::<N>] { ... }

Const Generic Arguments are allowed to be struct/variant expressions and struct/variant tuple constructor calls. All sub-expressions must be valid Const Generic Arguments (potentially involving generic parameters):

#[derive(ConstParamTy, Eq, PartialEq)]
struct Foo { field: usize }
#[derive(ConstParamTy, Eq, PartialEq)]
struct TupleFoo(usize);

typeconst FOO<const N: usize>: Foo = Foo { field: N };
// illegal as `N + 1` is not a valid Const Generic Argument
typeconst FOO_ILLEGAL<const N: usize>: Foo = Foo { field: N + 1 };

typeconst TUPLE_FOO<const N: usize>: TupleFoo = TupleFoo(N);
// illegal as `N + 1` is not a valid Const Generic Argument
typeconst TUPLE_FOO_ILLEGAL<const N: usize>: TupleFoo = TupleFoo(N + 1);

Const Generic Arguments are allowed to be tuple/array/repeat expressions. All sub-expressions must be valid Const Generic Arguments (potentially involving generic parameters):

typeconst ARR<const N: u8, T: Trait>: [u8; 3] 
    = [N, 1_u8, <T as Trait>::ASSOC];
// illegal as `N + 1` is not a valid Const Generic Argument
typeconst ARR_ILLEGAL<const N: u8, T: Trait>: [u8; 3] 
    = [N + 1, 1_u8, <T as Trait>::ASSOC];


typeconst ARR_REPEAT<const N: u8>: [u8; N] = [N; N];
// illegal as `N + 1` is not a valid Const Generic Argument
typeconst ARR_REPEAT_ILLEGAL<const N: u8>: [u8; N] = [N + 1; N + 1];

typeconst TUPLE<const N: Foo, T: Trait>: (Foo, u8, bool) 
    = (N, <T as Trait>::ASSOC, true);
// illegal as `N + 1` is not a valid Const Generic Argument
typeconst TUPLE_ILLEGAL<const N: Foo, T: Trait>: (Foo, u8, bool) 
    = (N + 1, <T as Trait>::ASSOC, true);

Const Generic Arguemnts are allowed to be an arbitrary non-generic expression[^2]:

typeconst NON_GENERIC_EXPR<const N: usize>: usize = 1 + 1;
// illegal as `N + 1` uses generic parameters and doesn't match any
// of the other forms of accepted expressions
typeconst GENERIC_EXPR<const N: usize>: usize = N + 1;

### Misc Design Thoughts

This design has a few desirable properties:
- No post mono errors
- All types supported in const generics work "equally" well
- Equality of type level expressions is "intuitive"/has one obvious behaviour
- Equality of type level *values* is "intuitive"/has one obvious behaviour

Because we special case "basic" constructor expressions we restrict the set of types allowed in const generics to only be those which can always be constructed via a "basic" constructor expression. This ensures that *all* types supported under this design work "equally" well.

If we allowed, for example, structs with `non_exhaustive` then they would no longer be constructable via a struct expression in all scopes. Now it would not be possible to generically construct a value of such a type:

pub mod foo {
    #[derive(ConstParamTy, Eq, PartialEq)]
    #[non_exhaustive]
    pub struct Foo<T> {
        field: T,
    }
    
    pub fn bar<T: ConstParamTy, const F: Foo<T>>() {}
    
    pub fn constructor<T>(field: T) -> Foo<T> {
        Foo {
            field,
        }
    }
}
use foo::*;

fn example<T: ConstParamTy, const N: T>() {
    // illegal as function calls involving generic parameters
    // are not valid const generic arguments
    bar::<T, { constructor(N) }>();
    
    // illegal as `Foo` is `non_exhaustive` but otherwise would
    // be legal
    bar::<T, { Foo { field: N }}>();
    
    // there is no way for the user to make the above work
}

### Unsolved Use Cases

- Arithmetic on user defined types, e.g. vector/matrix math
- Types with private fields, e.g. `Layout`
- Types with safety invariants, e.g. `str` or `NonZeroX`
- floats/fnptrs/references/other builtin types.
- `unsafe fn` ptrs can't use the `const F: impl FnOnce(...)` workaround
- Closures cant be used, if we do implement `ConstParamTy` then we have classic "unused parameters" problems...

It's unclear to me if the ability to "destructure" types via `match`/field projections/array indexing is a "necessity" for "reasonable" support for these types.

Supporting field projections for structs/tuples is relativelt trivial. But supporting match expressions and array indexing is tricky...

Match expressions have somewhat confusing type level equality because some users may expect match arms to be reorderable, it also involves introducing binders into const generics which is some impl work but doable. Array indexing is fallible and likely means post mono errors :<

It's probably best to leave out destructuring types from the "slightly sparkly future". However, some limited form of destructuring *is* possible via impl matching:

impl<const N: usize> Trait<{ Some(N) }> for () { ... }

allows to match a `const N: Option<usize>` against `Some(n)`... sort of...

## Const Item Generic Const Args

This is an extension to the "slightly sparkly" future previously outlined. This should be fairly easily implementable (though blocked on the new trait solver) and allows significantly more in const generics (though at the const of monomorphization time errors).

### Design

Const Generic Arguments are now allowed to be paths to non-type const items as long as the type of the const item implements `ConstParamTy`. These paths may involve generic parameters.

trait Trait { const ASSOC: usize }
fn foo<T: Trait>() -> [(); T::ASSOC] { ... }

Equality of paths to non-type const items can be determined in two ways:
1. Paths to non-type const items can be evaluated by const eval to a value and then the final values compared
2. Two uses of the same non-type const item with the same generic arguments are considered equal

fn foo<T>() {
    const FREE: usize = 1;
    const FREE2: usize = 1;
    
    // FREE and FREE2 are known equal due to rule 1
    let a: [(); FREE] = [(); FREE2];
    
    const GENERIC<T>: usize = size_of::<T>();
    
    // GENERIC and GENERIC2 are known equal due to rule 2
    // rule 1 does not apply as const eval does not know the
    // size of `T`
    let a: [(); GENERIC<T>] = [(); GENERIC<T>];
    
    const GENERIC2<T>: usize = size_of::<T>();
    
    // neither rule 1 or 2 applies so we error even though
    // as humans we "know" the lengths to be equal
    let a: [(); GENERIC<T>] = [(); GENERIC2<T>];
}

Associated non-type consts can be bounded with associated const bindings (similar to that of types) as long as the type of const implements `ConstParamTy`.

trait Trait { const ASSOC: usize }
fn foo<T: Trait<ASSOC = 10>>() {}

trait Other { const INVALID_TY: f32 }
// errors: `f32: ConstParamTy` does not hold
fn bar<T: Other<INVALID_TY = 1.0>>() {}

Traits with associated non-type consts are dyn compatible if the types of the associated consts implement `ConstParamTy`.

trait Trait { const ASSOC: usize; }
fn foo(my_trait: &dyn Trait<ASSOC = 10>) {}

trait Other { const INVALID_TY: f32 }
// errors: `Other` is not dyn compatible
fn bar(my_trait: &dyn Other<INVALID_TY = 1.0>>) {}

When implementing a trait with associated non-type consts, the associated consts may be implemented as associated type consts for better equality behaviour when the impl is known.

trait Trait { const ASSOC<const N: usize>: usize }
impl Trait for () {
    const ASSOC<const N: usize>: usize = N;
}
impl Trait for u32 {
    typeconst ASSOC<const N: usize>: usize = N;
}

fn foo<const N: usize>() {
    // errors as `<()>::ASSOC` is a non-type const item and neither of
    // the rules for non-type const item equality apply. i.e. it cannot
    // be evaluated by const eval, and `N` is not a path to a const item
    let a: [(); <() as Trait>::ASSOC<N>] = [(); N]
    
    // compiles as we can resolve the typeconst item to the const argument
    // it is an alias to.
    let b: [(); <u32 as Trait>::ASSOC<N>] = [(); N];
}

Defining associated constants in a trait as `typeconst` does nothing.

### Design Thoughts

Mono-time errors are really unfortunate. From speaking with users at conferences I've gotten very strong feedback that people **do not** want them.

Treating const items in const generics somewhat "opaquely" (i.e. not determining equality based off the body of the const item) poses some risks to the ecosystem.

This design encourages people to write things like `const ADD_ONE<const N: usize> = N + 1;` and then use that everywhere arithmetic is required. Without a "main" crate with all such const items we risk there being multiple incompatible definitions of arithmetic operators in the ecosystem causing crates which both "add one" to be unable to compose properly.

There is probably room for other extensions supporting more kinds of expressions directly in const arguments without going through an 'opaque' const item to mitigate this problem somewhat. (e.g. how the minimally shiny future supports struct expressions natively)

This certainly should exist *unstably* as a well of figuring out use cases for const generics and allowing people to experiment with const generics. Actually stabilizing this feels very dubious to me.

### Unsolved Use Cases

unsure if there's stuff other than extending the set of *types* we support having values of in the type system

## Placeholder Syntax for Direct Const Args

TODO

### Design

### Design Thoughts

### Unsolved Use Cases

## Post Mono Future for Const Generics

Yeah this is very much a WIP and I need to finish this section and is very outdated right now. No point reading from this point onwards

### Design

:woman-shrugging: I need to think more about where we can get to past the "Slightly Sparkly" future

- privacy/non_exhaustive/safety invariants are allowed on types implementing `ConstParamTy`
- just assuming we can make safety invariants work somehow :thinking_face: worst case we can require constructing them to be behind a function/method call xd
- typeconsts are gone in favour of normal const items
- associated consts no longer make a trait dyn incompatible?
- arbitrary expressions using generics are allowed but are treated "opaquely" to the type system. only equal to itself by definition-based equality rather than syntactic equality. only allowed as the rhs of a const item so that there is a name associated with the expression
- introduces post mono errors
- support function calls/method calls as Const Generic Arguments.
- post mono errors
- requires very involved const eval changes or *something* but we can figure something out maybe...
- function calls are effectively now "opaque type consts" in that the type system doesnt look inside function bodies. actually kinda nice design wise?
- this also probably isnt shiny enough
- coercions work:tm: somehow
- coercions (also from method lookup/autoref/deref) have weird interactions with type level expression equality which may be *weird*. potentially we'd want this to only ever be opaque
- what even are the complete set of expressions we'd support without opaqueness?
- should go through `hir::ExprKind`
- drop half the adt_const_params ideals on the floor:
- support `fn` in const generics
- support floats with picking a singular NaN representation and having it be equal to itself and `-0`/``+0` being unequal
- support raw pointers with Per-Value reject for pointers without a known address, and lossy conversion for its provenance

### Design Thoughts

We now have post mono errors, makes it not *that* shiny future but there is a huge increase in expressiveness. Users **really** do not want post mono errors.

We can support basically every type in const generics so long as it doesn't have safety invariants which conflict with the Lossy Conversions. We lose some nice hypothetical properties but the expressiveness is meaningful.

Allowing post mono errors and having the "opaque" escape hatch means that most things are going to be possible with const generics at this point.

The opaque escape hatch has the downside that it may cause ecossytem problems. E.g. if we don't support function calls as a first class type level expression, then different crates will have to define their own opaque `const FUNCTION_CALL<const F: impl Fn(...), const ARGS: (...)>` which won't iterop with eachother very nicely.

By accepting post mono errors and treating function calls as a first class expr we *do* allow for ADTs with field privacy to be "just as well supported" as fully publicly constructable ADTs.

## Unsolved Use Cases

...ideally none :>

[^1]: Note this rule exists on stable
[^2]: Note this rule exists on stable