Pre-RFC: Integer Templating


#1

Summary

Implement generics over integers, similar to integer templates in C++ (template<int n>). The point of this RFC is to just implement the bare essentials underneath a feature flag, and then flesh out the design with further RFCs.

Motivation

  • Algebraic Types: Matrices, Vectors, would all benefit from compile time integer generics. Matrix<2, 2> + Matrix<3, 3> doesn’t make any sense, and it’d be great to have a compile time error for that.
  • Compile Time Sizes: Like the StackVec example below; we have examples, mostly using typenum, but that’s a hack of the typesystem. It would be really nice to be able to write these without resorting to these kinds of crates.
  • Arrays: Our arrays are kind of terrible, this would make them slightly better. impling Clone for all arrays where T: Clone will fix an annoying ICE as well.
  • Physical Units: Saying that a kilometer is, at compile time, 1000 meters is a nice bonus.

Detailed Design

Basic Syntax

This utilizes the syntax of generics. It’s fairly simple.

fn adder<const n: u32>(m: u32) -> u32 {
    n + m
}

// There are better ways to implement this, but it's an example
struct StackVec<T, const n: usize> where T: Default{
    store: [T; n],
    len: usize,
}

impl<T, const n: usize> StackVec<T, const n> where T: Default {
    pub fn new() -> StackVec<T, n> {
        StackVec {
            store: [Default::default(); n],
            len: 0,
        }
    }
}

which will be called as

println!("{}", adder::<const 4>(5)) // '9'
// or
let v = StackVec::<_, const 16>::new();

however, if you have a type

struct Wrapper<const n: usize>(pub [u8; n]);

then Rust will be able to unify the following

let w = Wrapper([u8; 15]);

to be a Wrapper<const 15>.

Ordering

The ordering of generic arguments shall be lifetime, type, constants.

struct BorrowedArray<'a, T, const n: usize>(&'a [T; n]);

Allowed Types

At first, we shall allow integer types of any size. This will likely be implemented in the compiler as a u64 for any constant. However, if there is demand later, we will be able to expand this system to full dependent types. This RFC does not cover that scope.

Where Clauses

Where clauses are not implemented by this RFC. If they are felt necessary, they can be added later, backwards compatibly.

Drawbacks

More complexity

Alternatives

We see alternatives like typenum. These are ingenious, but an unfortunate and ugly outcropping of us not having a necessary feature.

Unresolved Questions

  • Should we allow integers of any size? Or perhaps we should do like C++ does, and only have usize.
  • Should we only write const once per generic list? It gets annoying after a while to keep writing the same word over, and over.
impl<const n, const m> std::ops::Add<Matrix<const n, const m>>
        for Matrix<const n, const m> {
    type Output = Matrix<const n, const m>;
}

// versus

impl<const n, m> std::ops::Add<Matrix<const n, m>> for Matrix<const n, m> {
    type Output = Matrix<const n, m>;
}

#2

Please, let’s get something like this in Rust already. It’ll make so many things much easier.


#3

Run time variables do not make sense for generics so I’d just say that all value level parameters are implied const instead of requiring to specify it all over the place.


#4

@yigal100 The issue is the parser. I don’t fully understand it, but people who do have told me that it’s necessary.


#5

Could the parser use case to differentiate this? We already warn if a generic parameter is lowercase; couldn’t we transition that to a hard error after a release cycle, and then use it for integer parameters?

What about #n? Is # used anywhere else besides raw string literals? I know we’re trying to be as light on sigils as possible, but I think it would be sensible here.


#6

I’d rather not differentiate on case. I would be okay with using # though to indicate such things.


#7

I think const introduces a conceptual link which makes this easier to understand to users for whom this feature is not at hand.


#9

Should we allow integers of any size? Or perhaps we should do like C++ does, and only have usize.

AFAIK, C++ allows any integer type?

Why not omit const from the declaration entirely? Can’t it be implied that a generic parameter must be const?

EDIT: Oh and a massive +1 for this feature.


#10

Let’s start even smaller. Let’s just allow usize for now. You can always cast to the other types. There are some flukes with the const evaluator regarding the different integer types.


Please make the constants uppercase, normal constants are already uppercase.


This RFC duplicates a lot of work of https://github.com/rust-lang/rfcs/pull/1062. Maybe this one should be postponed until the other RFC is merged, because then this RFC can simply be sugar for desugaring the following

fn adder<const N: usize>(m: usize) -> usize { N + m }
fn main() {
    assert_eq!(adder<42>(66), 108);
}

to that

trait UnnamedTrait {
    const N: usize,
}
fn adder<T: UnnamedTrait>(m: usize) -> usize {
    T::N + m
}

fn main() {
    struct UnnamedDummy42;
    impl UnnamedTrait {
        const N: usize = 42;
    }
    assert_eq!(adder<UnnamedDummy42>(66), 108);
}


#11

If we go down this route then we could avoid the need for const to differentiate between types and values for generic parameters. Instead, a keyword could be used to turn a constant expression into a type that contains the resulting value as an associated constant, similar to std::integral_constant in C++.

Example:

trait<T> Const  {
    const VALUE: T,
}
fn adder<N: Const<usize>>(m: usize) -> usize { N::VALUE + m }
fn main() {
    assert_eq!(adder<const_usize!(42)>(66), 108);
}

#12

I understand why it may be necessary to distinct types from variables, but is it necessary for literals too? I’m not expert with the compiler, but shouldn’t it be able to know literals are not types?


#13

I think it should be possible to special-case integer literals to avoid the necessity for the const keyword when using the type.

Also, identifiers/paths are allowed both in type syntax and expression syntax, so we could parse those and then later (during typeck) decide whether they represent a type or a constant value.

These two special cases would allow the use of StackVec<T, 32> and StackVec<T, n>. Only complex cases like StackVec<T, const n+1> would still require the const keyword.


#14

Would this eventually incorporate function specialization similar to c++ ? Something I’ve been missing in Rust is the ability to specialize a function for certain values of the type (I think Rust’s algebraic types would be very powerful here). If we had the ability to template by an enum, the compiler could easily tell that all utilized cases have been met, either by a default implementation or by specializing for every possible value like what is currently done with the match statement. It would also be very helpful if we could calculate const values inside the function which would be calculated at compile time [like here] (https://github.com/mcostalba/Stockfish/blob/ONE_PLY/src/movegen.cpp#L101).

I agree that having const specified for each template is clearly implied and having the extra specifier would be very verbose for little gain.


#15

Rust is getting specialization.


#16

I believe this is the GitHub issue for this feature: https://github.com/rust-lang/rfcs/issues/1038


#17

I know someone previously proposed separating the const parameters and type parameters using a semicolon. So your examples look like this:

fn adder<; n: u32>(m: u32) -> u32 {
    n + m
}

// There are better ways to implement this, but it's an example
struct StackVec<T; n: usize> where T: Default{
    store: [T; n],
    len: usize,
}

impl<T; n: usize> StackVec<T; n> where T: Default {
    pub fn new() -> StackVec<T, n> {
        StackVec {
            store: [Default::default(); n],
            len: 0,
        }
    }
}
println!("{}", adder::<; 4>(5)) // '9'
// or
let v = StackVec::<_; 16>::new();

#18

this is pretty cool due to the symmetry to [T; N] types


#19

Why not just:

impl<const N, const M> std::opts::Add<Matrix<N, M>> for Matrix<N, M> {
    type Output = Matrix<N, M>
}

That is, introducing the constants requires qualifying them with const to indicate those are values instead of types, but do we really need to make this distinction when using them afterward?

As a parallel, when I compute at run-time I:

  • specify the type of the variable when declaring it
  • but not when using it

Of course, it means that as far as the AST is concerned, in Matrix<N, M> the N is some generic parameter with no clue about whether it’s a type or value.

Does it really matter?


#20

[quote=“matthieum, post:19, topic:2974”] Of course, it means that as far as the AST is concerned, in Matrix<N, M> the N is some generic parameter with no clue about whether it’s a type or value.

Does it really matter?[/quote]

Actually, yes, because rustc checks that symbols are declared before type checking. This means that, at the time it needs to check that the symbol exists, it can’t check type definitions to figure out what namespace it’s supposed to be in (Rust allows types and variables to have the same name with no ambiguity).

http://is.gd/QfvaBj


#21

Ah, I was fearing the namespace issue.

The problem is that as much as I find the “;” nifty I am afraid it’s a bit too smart:

  • it’s close to being undiscoverable for a newcomer
  • it’s close to being unsearchable

It’s a general issues about symbols; keywords are just much easier to search for.

Does discoverability matters?