14 KiB

Raw Permalink Blame History

Feature Name: const_generics
Start Date: 2017-05-01
RFC PR: rust-lang/rfcs#2000
Rust Issue: rust-lang/rust#44580

Summary

Allow types to be generic over constant values; among other things this will allow users to write impls which are abstract over all array types.

Motivation

Rust currently has one type which is parametric over constants: the built-in array type [T; LEN]. However, because const generics are not a first class feature, users cannot define their own types which are generic over constant values, and cannot implement traits for all arrays.

As a result of this limitation, the standard library only contains trait implementations for arrays up to a length of 32; as a result, arrays are often treated as a second-class language feature. Even if the length of an array might be statically known, it is more common to heap allocate it using a vector than to use an array type (which has certain performance trade offs).

Const parameters can also be used to allow users to more naturally specify variants of a generic type which are more accurately reflected as values, rather than types. For example, if a type takes a name as a parameter for configuration or other reasons, it may make more sense to take a &'static str than take a unit type which provides the name (through an associated const or function). This can simplify APIs.

Lastly, consts can be used as parameters to make certain values determined at typecheck time. By limiting which values a trait is implemented over, the orphan rules can enable a crate to ensure that only some safe values are used, with the check performed at compile time (this is especially relevant to cryptographic libraries for example).

Detailed design

Today, types in Rust can be parameterized by two kinds: types and lifetimes. We will additionally allow types to be parameterized by values, so long as those values can be computed at compile time. A single constant parameter must be of a single, particular type, and can be validly substituted with any value of that type which can be computed at compile time and the type meets the equality requirements laid out later in this RFC.

(Exactly which expressions are evaluable at compile time is orthogonal to this RFC. For our purposes we assume that integers and their basic arithmetic operations can be computed at compile time, and we will use them in all examples.)

Glossary

Const (constant, const value): A Rust value which is guaranteed to be fully evaluated at compile time. Unlike statics, consts will be inlined at their use sites rather than existing in the data section of the compiled binary.
Const parameter (generic const): A const which a type or function is abstract over; this const is input to the concrete type of the item, such as the length parameter of a static array.
Associated const: A const associated with a trait, similar to an associated type. Unlike a const parameter, an associated const is determined by a type.
Const variable: Either a const parameter or an associated const, contrast with concrete const; a const which is undetermined in this context (prior to monomorphization).
Concrete const: In contrast to a const variable, a const which has a known and singular value in this context.
Const expression: An expression which evaluates to a const. This may be an identity expression or a more complex expression, so long as it can be evaluated by Rust's const system.
Abstract const expression: A const expression which involves a const variable (and therefore the value that it evaluates to cannot be determined until after monomorphization).
Const projection: The value of an abstract const expression (which cannot be determined in a generic context because it is dependent on a const variable).
Identity expression: An expression which cannot be evaluated further except by substituting it with names in scope. This includes all literals as well all idents - e.g. 3, "Hello, world", foo_bar.

Declaring a const parameter

In any sequence of type parameter declarations (such as in the definition of a type or on the impl header of an impl block) const parameters can also be declared. Const parameters declarations take the form const $ident: $ty:

struct RectangularArray<T, const WIDTH: usize, const HEIGHT: usize> {
    array: [[T; WIDTH]; HEIGHT],
}

The idents declared are the names used for these const parameters (interchangeably called "const variables" in this RFC text), and all values must be of the type ascribed to it. Which types can be ascribed to const parameters is restricted later in this RFC.

The const parameter is in scope for the entire body of the item (type, impl, function, method, etc) in which it is declared.

Applying a const as a parameter

Any const expression of the type ascribed to a const parameter can be applied as that parameter. When applying an expression as const parameter (except for arrays), which is not an identity expression, the expression must be contained within a block. This syntactic restriction is necessary to avoid requiring infinite lookahead when parsing an expression inside of a type.

const X: usize = 7;

let x: RectangularArray<i32, 2, 4>;
let y: RectangularArray<i32, X, {2 * 2}>;

Arrays

Arrays have a special construction syntax: [T; CONST]. In array syntax, braces are not needed around any const expressions; [i32; N * 2] is a syntactically valid type.

When a const variable can be used

A const variable can be used as a const in any of these contexts:

As an applied const to any type which forms a part of the signature of the item in question: fn foo<const N: usize>(arr: [i32; N]).
As part of a const expression used to define an associated const, or as a parameter to an associated type.
As a value in any runtime expression in the body of any functions in the item.
As a parameter to any type used in the body of any functions in the item, as in let x: [i32; N] or <[i32; N] as Foo>::bar().
As a part of the type of any fields in the item (as in struct Foo<const N: usize>([i32; N]);).

In general, a const variable can be used where a const can. There is one significant exception: const variables cannot be used in the construction of consts, statics, functions, or types inside a function body. That is, these are invalid:

fn foo<const X: usize>() {
    const Y: usize = X * 2;
    static Z: (usize, usize)= (X, X);

    struct Foo([i32; X]);
}

This restriction can be analogized to the restriction on using type variables in types constructed in the body of functions - all of these declarations, though private to this item, must be independent of it, and do not have any of its parameters in scope.

Theory of equality for type equality of two consts

During unification and the overlap check, it is essential to determine when two types are equivalent or not. Because types can now be dependent on consts, we must define how we will compare the equality of two constant expressions.

For most cases, the equality of two consts follows the same reasoning you would expect - two constant values are equal if they are equal to one another. But there are some particular caveats.

Structural equality

Const equality is determined according to the definition of structural equality defined in RFC 1445. Only types which have the "structural match" property can be used as const parameters. This would exclude floats, for example.

The structural match property is intended as a stopgap until a final solution for matching against consts has been arrived at. It is important for the purposes of type equality that whatever solution const parameters use will guarantee that the equality is reflexive, so that a type is always the same type as itself. (The standard definition of equality for floating point numbers is not reflexive.)

This may diverge someday from the definition used by match; it is not necessary that matching and const parameters use the same definition of equality, but the definition of equality used by match today is good enough for our purposes.

Because consts must have the structural match property, and this property cannot be enforced for a type variable, it is not possible to introduce a const parameter which is ascribed to a type variable (Foo<T, const N: T> is not valid).

Equality of two abstract const expressions

When comparing the equality of two abstract const expressions (that is, those that depend on a variable) we cannot compare the equality of their values because their values are determined by a const variable, the value of which is unknown prior to monomorphization.

For this reason we will (initially, at least) treat the return value of const expressions as projections - values determined by the input, but which are not themselves known. This is similar to how we treat associated types today. When comparing the evaluation of an abstract const expression - which we'll call a const projection - to another const of the same type, its equality is always unknown.

Each const expression generates a new projection, which is inherently anonymous. It is not possible to unify two anonymous projections (imagine two associated types on a generic - T::Assoc and T::Item: you can't prove or disprove that they are the same type). For this reason, const expressions do not unify with one another unless they are literally references to the same AST node. That means that one instance of N + 1 does not unify with another instance of N + 1 in a type.

To be clearer, this does not typecheck, because N + 1 appears in two different types:

fn foo<const N: usize>() -> [i32; N + 1] {
    let x: [i32; N + 1] = [0; N + 1];
    x
}

But this does, because it appears only once:

type Foo<const N: usize> = [i32; N + 1];

fn foo<const N: usize>() -> Foo<N> {
    let x: Foo<N> = Default::default();
    x
}

Future extensions

Someday we could introduce knowledge of the basic properties of some operations

such as the commutativity of addition and multiplication - to begin making smarter judgments on the equality of const projections. However, this RFC does not proposing building any knowledge of that sort into the language and doing so would require a future RFC.

Specialization on const parameters

It is also necessary for specialization that const parameters have a defined ordering of specificity. For this purpose, literals are defined as more specific than other expressions, otherwise expressions have an indeterminate ordering.

Just as we could some day support more advanced notions of equality between const projections, we could some day support more advanced definitions of specificity. For example, given the type (i32, i32), we could determine that (0, PARAM2) is more specific than (PARAM1, PARAM2) - roughly the analog of understanding that (i32, U) is more specific than the type (T, U). We could also someday support intersectional and other more advanced definitions of specialization on constants.

How We Teach This

Const generics is a large feature, and will require significant educational materials - it will need to be documented in both the book and the reference, and will probably need its own section in the book. Documenting const generics will be a big project in itself.

However, const generics should be treated as an advanced feature, and it should not be something we expose to new users early in their use of Rust.

Drawbacks

This feature adds a significant amount of complexity to the type system, allowing types to be determined by constants. It requires determining the rules around abstract const equality, which result in surprising edge cases. It adds a lot of syntax to the language. The language would definitely be simpler if we don't adopt this feature.

However, we have already introduced a type which is determined by a constant - the array type. Generalizing this feature seems natural and even inevitable given that early decision.

Alternatives

There are not really alternatives other than not doing this, or staging it differently.

We could limit const generics to the type usize, but this would not make the implementation simpler.

We could move more quickly to more complex notions of equality between consts, but this would make the implementation more complex up front.

We could choose a slightly different syntax, such as separating consts from types with a semicolon.

Unresolved questions

Unification of abstract const expressions: This RFC performs the most minimal unification of abstract const expressions possible - it essentially doesn't unify them. Possibly this will be an unacceptable UX for stabilization and we will want to perform some more advanced unification before we stabilize this feature.
Well formedness of const expressions: Types should be considered well formed only if during monomorphization they will not panic. This is tricky for overflow and out of bound array access. However, we can only actually provide well formedness constraints of expressions in the signature of functions; what to do about abstract const expressions appearing in function bodies in regards to well formedness is currently unclear & is delayed to implementation.
Ordering and default parameters: Do all const parameters come last, or can they be mixed with types? Do all parameters with defaults have to come after parameters without defaults? We delay this decision to implementation of the grammar.

14 KiB Raw Permalink Blame History