Rust: Use const generics for array impls

[varkor]

Currently, we generate array impls for every size up to 32 manually using macros, but with const generics at a suitable level of implementation, we can switch to properly parameterising over all lengths.

• [x] Replace most manual impls with const generic impls (PR: https://github.com/rust-lang/rust/pull/62435)
• [ ] Replace Default impl with const generic impl (more difficult due to https://github.com/rust-lang/rust/pull/60466#discussion_r280989938).
• [ ] Reimplement impls removed due to bloat using const generic impls (see https://github.com/rust-lang/rust/blob/7840a0b753a065a41999f1fb6028f67d33e3fdd5/src/libcore/array.rs#L221-L227 and https://github.com/rust-lang/rust/blob/bfdfa85e73186ef96f082980113f7ace8561efd2/src/liballoc/vec.rs#L2199-L2204)

[Centril]

As I noted in https://github.com/rust-lang/rust/pull/60466#issuecomment-490228264 and https://github.com/rust-lang/rust/pull/60466#issuecomment-490250491 I will not sign off on using const generics in stable Rust until such time that const generics are stable. However, we can provide unstable wrapper types meanwhile.

[petrochenkov]

We can probably both keep the exact observable behavior (impls for 0-32) and reduce metadata bloat by using a trick similar to https://github.com/rust-lang/rust/pull/60466#discussion_r282368369 (an empty marker trait implemented using macros + the real impl using const generics and a where clause with the marker trait).

This way const generics would be an implementation detail, so their stabilization wouldn't be required.

[varkor]

The results from the crater run and perf run for using const generics for array impls are in (https://github.com/rust-lang/rust/pull/60466).

• cargo check performance is increased: https://github.com/rust-lang/rust/pull/60466#issuecomment-497911806. Otherwise, unchanged.
• No regressions: https://github.com/rust-lang/rust/pull/60466#issuecomment-498405814. (Actually fixes a couple of crates that were relying on impls for larger arrays 😄)

I think there's good reason to go with @petrochenkov's suggestion (https://github.com/rust-lang/rust/issues/61415#issuecomment-497922482) and potentially consider lifting the restriction for array sizes.

[pnkfelix]

does T-compiler actually need to be tagged on this issue? Unless its exposing bugs for const generics themselves, I would think this is solely a T-libs issue, maybe T-lang, but not T-compiler?

[alexcrichton]

This libs team discussed this yesterday and agreed that we do not want to expand the stable surface API of the standard library, but changing implementaitons to use const generics seems fine so long as it doesn't expand the surface area of what's exposed (e.g. via @petrochenkov's idea)

[nikomatsakis]

The @rust-lang/lang team discussed this and we agree with the libs team. =)

[scottmcm]

No-expanded-surface area (https://github.com/rust-lang/rust/issues/61415#issuecomment-497922482) PR up at https://github.com/rust-lang/rust/pull/62435

[RalfJung]

Turns out using const generics inside the actual code (which currently only try_from does) breaks Miri. @oli-obk will hopefully be able to look into this next week, but until then it would be great if we couldn't land more PRs that use const generic in this way in libstd.

[eddyb]

@RalfJung Can you trigger that from CTFE, or does it require runtime features?
It would be nice to have a issue with a testcase that ICEs/errors from miri.

[RalfJung]

ICE from Miri is easy:

use std::convert::TryFrom;

fn main() {
    const N: usize = 16;
    type Array = [u8; N];
    let array: Array = [0; N];
    let slice: &[u8] = &array[..];

    let result = <&Array>::try_from(slice);
    assert_eq!(&array, result.unwrap());
}

Here is a self-contained version.

[eddyb]

If I try to make fn len a const fn I get this:

error: const parameters are not permitted in `const fn`

So I'd suggest fixing that first (seems like an unnecessary limitation while const generics are unstable - worst case it can just get its own feature gate).

After that, the entire repro is this:

#![feature(const_generics)]
const fn len<T, const N: usize>(_: [T; N]) -> usize { N }
const FOO: usize = len([0]);

My guess is that miri isn't monomorphizing ("substituting"?) Operand::Constants.

[RalfJung]

My guess is that miri isn't monomorphizing ("substituting"?) Operand::Constants.

Indeed, and I have a patch for that but it ICEs. See https://github.com/rust-lang/rust/pull/61041#issuecomment-511113320.

[eddyb]

@RalfJung I left a comment, you shouldn't be able to trigger that ICE that easily.

[alex]

As of #74060 these are now being used on a bunch of traits -- possibly everywhere except Default, which is challenging for reasons discussed (but is being expiremented with in #74254)

[MikailBag]

TL;DR there are two problems with my PR:
1) If we want that Default impls play nicely with the rest of compiler, we have to use marker traits + specialization. It seems they are not going to be stable in the enar future. There were other approaches proposed, but they have problems with trait selection, type inference and similar stuff. AFAIK this problem waits for a T-lang decision.
2) Current implementation suffers from codegen issue https://github.com/rust-lang/rust/issues/74267: generated code is worse than with current macro-generated impls, which leads to performance loss.