Use const generics for array Default impl

[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.

• Replace most manual impls with const generic impls (PR: Use const generics for array impls [part 1] #62435)
• Replace Default impl with const generic impl (more difficult due to Switch libcore array implementations to const generics. #60466 (comment)).
• Reimplement impls removed due to bloat using const generic impls (see

  rust/src/libcore/array.rs

  Lines 221 to 227 in 7840a0b

  	// NOTE: some less important impls are omitted to reduce code bloat
  	__impl_slice_eq1! { [A; $N], [B; $N] }
  	__impl_slice_eq2! { [A; $N], [B] }
  	__impl_slice_eq2! { [A; $N], &'b [B] }
  	__impl_slice_eq2! { [A; $N], &'b mut [B] }
  	// __impl_slice_eq2! { [A; $N], &'b [B; $N] }
  	// __impl_slice_eq2! { [A; $N], &'b mut [B; $N] }

  and

  rust/src/liballoc/vec.rs

  Lines 2199 to 2204 in bfdfa85

  	// NOTE: some less important impls are omitted to reduce code bloat
  	// FIXME(Centril): Reconsider this?
  	//__impl_slice_eq1! { [const N: usize] Vec<A>, &mut [B; N], [B; N]: LengthAtMost32 }
  	//__impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, [B; N], [B; N]: LengthAtMost32 }
  	//__impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, &[B; N], [B; N]: LengthAtMost32 }
  	//__impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, &mut [B; N], [B; N]: LengthAtMost32 }

  )

[Centril]

As I noted in #60466 (comment) and #60466 (comment) 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 #60466 (comment) (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 (#60466).

• cargo check performance is increased: Switch libcore array implementations to const generics. #60466 (comment). Otherwise, unchanged.
• No regressions: Switch libcore array implementations to const generics. #60466 (comment). (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 (#61415 (comment)) 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 (#61415 (comment)) PR up at #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 #61041 (comment).

[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 MaybeUninit::assume_init optimizes poorly #74267: generated code is worse than with current macro-generated impls, which leads to performance loss.

[joshtriplett]

@oli-obk @rust-lang/wg-const-eval @rust-lang/types Is there any potential future change on the horizon that would allow handling "either T: Default or N == 0" without needing full overlapping implementations?

[oli-obk]

Not that I know of. Though I would love to be able to specify patterns like in matches to restrict const generic impls to something that we already know how to check for overlap (or lack thereof)

[ryoqun]

dumb question. Can this be fixed for the edition 2024?

[Skgland]

I think the problem of the overlapping impl where T: Default and N == 0 is still open.

impl <T> Default for [T; 0] {...}
impl <T, const N: usize> Default for [T; N] {...}