Stabilizing a const generics MVP

There is an MVP of const generics which has a solid implementation and a strong consensus on its design. We've been using it in std for over a year. We should stabilize it.

  1. The first step would be for us to define the specific boundaries of that subset, which this thread aims to do.
  2. The second step would be to create a new min_const_generics which enables only this subset of const generics.
  3. The third step would be to document, test and stabilize that feature.

I've attempted to summarize the subset here, @eddyb, @varkor, @oli-obk and @lcnr should review it to see if they agree that this is the correct subset.

What types can be const generics

This subset would include a const parameter of any type which has structural equality. This includes all of the primitive types except for floats and any type made of structurally equal fields that have the structural equality attribute (in practice on stable this means types which derive Eq and PartialEq). Types with open type parameters would not be a valid type for a const generic (so no Foo<T, const X: T>).

EDIT: Due to this issue, this may need to be restricted to just integral primitive types (ie the int types, bool, and char). Other types would probably be a nearer term addition beyond the MVP. https://github.com/rust-lang/compiler-team/issues/323

What expressions can be used in const generic position

Const parameters can be allowed as identity expressions. Otherwise, const generics can have any concrete expression that isn't based on open type or const parameters. That is, you can have [T; N], [T; 0], or [T; size_of::<u32>()], but you cannot have [T; T::ASSOC_CONST] or [T; size_of::<U>() or [T; N * 2]. In other words, no computation based on open type or const parameters is permitted.

This is limiting, and prevents a lot of cool CTFE tricks that people like to do with const parameters, but it still covers a huge range of use cases. The most important is that it allows implementing traits for all arrays for most use cases (as long as all the arrays in the trait body are the same size, basically). This will make arrays a lot easier to use, as traits will be implemented for arrays larger than 32, and without requiring any macro magic either.

Where const generics can be used

This I'm less clear about. In the associated zulip chat, @lcnr mentioned "no where bounds," but I'm not sure exactly what they meant by this. Would we need to not allow using const parameters in where clauses? Is there any other position in which we could not allow const parameters to be used?

37 Likes

no where bounds

I guess he meant code like this (i.e. an ability to encode constraints like "less than"). AFAIK it's not possible to express such bounds with current const generics.

Also we will not be able to use const generics in RustCrypto, while this issue is open.

@lcnr mentioned "no where bounds," but I'm not sure exactly what they meant by this.

My initial goal is to try and have the const generics MVP not depend on lazy_normalization_consts.

This causes cycle errors when const expressions are used in bounds:

#![feature(const_generics)]

pub trait Foo<const B: bool> {}
pub fn bar<T: Foo<{ true }>>() {}
//                ^^^^^^^^ cycle error

These cycle errors are really easy to hit and have horrible error messages, so I don't want them on stable.

The two solutions are probably to either to wait until lazy_normalization_consts is good enough to also get stabilized at the same time or forbid generics inside of consts inside of bounds.

We already probably have to restrict generics in this way in some other places, for example inside of type defaults. See the relevant zulip discussion for more details.

edit: we might actually have to first stabilize lazy norm here. I forgot this hack exists, will look a bit deeper into it this week. So restricting bounds this way might be unnecessary

second edit: it seems like we don't have to stabilize lazy norm first, see Stabilizing a const generics MVP - #9 by withoutboats for the relevant update

2 Likes

I think that an MVP with just integer constants gives us the largest effect (arrays!) while also being the safest thing to stabilize. We should do this in parallel to the already linked integer tree representation MCP Change `ty::Const` to a "value tree" representation · Issue #323 · rust-lang/compiler-team · GitHub. Integer trees will make it safe to use aggregates and I don't think we gain much by blocking min_const_generics on this.

Note that for const generics, unlike match patterns, we must require that Eq and PartialEq are derived recursively! All variants and fields of the type must have structural equality, not just the root type that you use for your constant.

13 Likes

Is that not the case for match patterns as well? For example, this fails to compile:

use std::cmp::{PartialEq, Eq};

struct Inner;

impl PartialEq for Inner {
    fn eq(&self, _: &Self) -> bool { false }
}

impl Eq for Inner {}

#[derive(PartialEq, Eq)]
struct Outer(Inner);

const OUTER: Outer = Outer(Inner);

fn f(o: Outer) {
    match o {
        OUTER => {}
    }
}
error: to use a constant of type `Inner` in a pattern, `Inner` must be annotated with `#[derive(PartialEq, Eq)]`
  --> src/lib.rs:18:9
   |
18 |         OUTER => {}
   |         ^^^^^
2 Likes

I wager that for the arrays use-case we hardly even need trait T<const N: $int>...

Maybe it would be a good idea to disallow const parameters as parameters to traits entirely? This is the main way they'll show up in where clauses, and might be a rule that is easier to intuit and learn than that they can't be used in where clauses. Maybe we'll also have to disallow them in types used in where clauses, but that will be encountered less often. With traits the main reason to use a trait is to use it in where clauses, after all.

As you can see in the error, it complains about Inner, even thought the constant is of type Outer. Inner may be a private implementation detail, and you can't tell that something is structurally matchable recursively except by the way you described.

oh, I didn't even think about that at all so far.

Yea, for the MVP definitely, I don't see an immediate large scale thing that they would unlock.

After talking to lcnr and eddyb, I have updated the proposal for the MVP. Feedback again requested.

Which types a const parameter can be

In the MVP, we will only allow the integral primitives to be const parameters: signed and unsigned integer types, booleans, and chars.

Extending to all types with structural equality would be a near-term extension after the MVP.

Which expressions can be applied as a const parameter

In the MVP, const parameters can only contain these two kinds of expressions:

  1. Const parameters as identity expressions - that is if N is a free const parameter, it can only be applied as a const parameter as the expression N.
  2. Const expressions containing no free type or const parameters.

We will implement this behavior by refusing to resolve const and type parameters when computing a const parameter expression, except to implement the first case.

Which locations a const parameter can be used in

There will be no limitation on where const parameters can be used - they can be used on any item a type parameter could be used on, and in constraints, and so on.

We had a good discussion about this in zulip and determined that it isn't necessary. Basically, without lazy normalization there are two problems. First, users sometimes get bizarre cycle errors that are actually incorrect, and lazy normalization will resolve correctly. Second, the current implementation actually allows some code that should not be allowed, because it resolves an associated item that should be ambiguous. This means lazy normalization will break some hypothetical code. For example:

trait Trait<T> {
    const ASSOC_CONST: usize = 0;
}

impl Trait<()> for u8 {}

// `u8::ASSOC_CONST` is resolved today, but will be ambiguous
// under lazy normalization
type Foo<T, U>
     where u8: Trait<T> + Trait<U>
= [(T, U); u8::ASSOC_CONST];

This is not great. However, these examples are not easy to hit under the restrictions we've identified above, are basically pathological, and (importantly) are already allowed on stable because we allow consts in all these positions on stable by way of allowing arrays in all these positions.

So we will not limit where consts are allowed, but we will also not block const generics on lazy normalization.

6 Likes

Does that mean that the eventual stabilized implementation of Lazy Normalization will then resolve potentially working code as ambiguous or does that mean that when Lazy Normalization is stabilized that issue will have been resolved first? In other words, is it believed that that problem has a workable solution eventually?

The sample should correctly be understood as ambiguous because multiple definitions of u8::ASSOC_CONST are in scope via the where clauses, but the compiler today incorrectly treats it as unambiguous. It's always possible to disambiguate examples like this by defining the full path (for example <u8 as Trait<()>>::ASSOC_CONST).

3 Likes

We would still need an WF constant value check that enforces the value is actually an integer (and not e.g. a CTFE "abstract memory address", or anything weirder). Presumably some of that is already enforced by the current implementation for integer types, but not ADTs?

To be clear, as a consequence of the above, would the following code be expected to work in the MVP?

trait K<const N: usize> {
  const ASSOC: usize = N;
}
// ...
fn foo<const N: usize, T: K<N>>() -> [u8; T::ASSOC];

Based on the above restrictions this seems to be the most complicated code allowed right now, but it can't hurt to check...

No. T::ASSOC would not be allowed in that position.

That doesn't work at all (see playground), due to #68436 which we don't have a solution yet.

(In short, there's no way for the compiler to know that T::ASSOC will always be a valid array length, it could just as well panic - because of that, the only constant expressions in types that can successfully "use" generics must not actually depend on said generics, for now, and the MVP would be even more restricted)

Oh, right... I forgot about that. =(

Does this affect only arrays (and types that depend on the constant to compute their layout) or does it also affect e.g.

struct L<const N: usize>;
fn foo<const N: usize, T: K<N>>() -> L<T::ASSOC>;

Mind, the "T::ASSOC is not allowed in that position" doesn't seem to immediately follow from the proposed subset above (i.e., the paragraphs after "There will be no limitations..."). I think the mention of associated constants in the code snippet above is confusing things. (Maybe it's worth clarifying that this is still not allowed?)

The restrictions are imposed by "Which expressions can be applied as a const parameter", which also apply to the length expressions of array types (this could/should be clarified in the MVP proposal).

T::ASSOC does not satisfy the "no free type or const parameters" requirement of "2. Const expressions containing no free type or const parameters.", and the only other kind of allowed expression is a plain const parameter (N), which it's clearly not.

To answer to your second example: yes, that also doesn't work - it's not about layout, but rather the well-formedness ("WF") of the type, and statically knowing that the expression will evaluate (before being able to, due to e.g. unknown types like T in T::ASSOC).


I guess "no limitation" in the paragraph below is confusing?

Maybe "used" is the wrong word? I believe this is referring to where const parameters can be declared, i.e. write const N: ... between <...> (and the answer is that they can be declared in all the same places type parameters can).

1 Like

I chose the sort of ambiguous "use" because there had initially been a concern about needing to block const params from appearing in types or traits used in where clauses.

1 Like

I think that the criteria for which expressions can be applied as const parameters is good here, specifically in the context of an MVP. It would be a win just by allowing the standard library to implement traits for any sized array.

Most of the interesting things that are necessary for simple linear algebra libraries are covered by this. I try to use this library as much as possible in order to beta-test const generics as much as possible. I have recently run into a build failure upon upgrading to a new nightly, as certain const expressions in type expressions became illegal: https://github.com/maplant/aljabar/blob/master/src/vector.rs#L225, which manifests as the error:

error: constant expression depends on a generic parameter
   --> src/vector.rs:173:30
    |
173 |     pub fn truncate(self) -> (TruncatedVector<T, { N }>, T) {
    |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: this may fail depending on what value the parameter takes

Although it would be nice to be able to express something like this eventually but it would require an update to the current const generics RFC. Additionally, the error message is very clear in indicating what is allowed and not allowed in const generic expressions, and it aligns with WithoutBoat's description of the MVP. Therefore, I think it is suitable for stabilization.

2 Likes

That's what boats' comment made me suspect. Thanks for clarifying. =)