search

rust-lang / rust

Empowering everyone to build reliable and efficient software.
https://www.rust-lang.org
Other
97.92k stars 12.68k forks source link

Use const generics for array `Default` impl #61415

Open varkor opened 5 years ago

varkor commented 5 years ago

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.

Centril commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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

scottmcm commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

@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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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

alex commented 4 years ago

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 commented 4 years ago

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.

joshtriplett commented 2 years ago

@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 commented 2 years ago

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 commented 4 months ago

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

Skgland commented 2 months ago

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] {...}