Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Tracking issue for const generics (RFC 2000) #44580

Closed
3 of 16 tasks
withoutboats opened this issue Sep 14, 2017 · 206 comments
Closed
3 of 16 tasks

Tracking issue for const generics (RFC 2000) #44580

withoutboats opened this issue Sep 14, 2017 · 206 comments
Assignees
Labels
A-const-eval Area: Constant evaluation, covers all const contexts (static, const fn, ...) A-const-generics Area: const generics (parameters and arguments) A-type-system Area: Type system B-RFC-approved Blocker: Approved by a merged RFC but not yet implemented. C-tracking-issue Category: An issue tracking the progress of sth. like the implementation of an RFC F-const_generics `#![feature(const_generics)]` requires-nightly This issue requires a nightly compiler in some way. S-tracking-impl-incomplete Status: The implementation is incomplete. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. T-lang Relevant to the language team, which will review and decide on the PR/issue.

Comments

@withoutboats
Copy link
Contributor

withoutboats commented Sep 14, 2017

Tracking issue for rust-lang/rfcs#2000

Updates:

If you want to help out, take a look at the open const generics issues and feel free to ping @varkor, @eddyb, @yodaldevoid, @oli-obk or @lcnr for help in getting started!


Blocking stabilization:

  • Design:
    • Resolving ordering of const and type parameters, with default parameters
    • Decide what the best UX / implementation cost balance is for unifying abstract const expressions.
    • How we determine well formedness of const expressions.
  • Implementation
  • Documentation
    • rustc guide

Remaining implementation issues:

  • Resolve various FIXME(const_generics) comments.
  • Resolve concerns with canonicalisation / lazy normalisation.
  • Investigate handling of const parameters in patterns.
  • Add more tests.
  • Implement defaults for const parameters (FIXME(const_generics_defaults)).
  • Fix other A-const-generics issues.
  • Audit uses of has_infer_types.
  • Forbid complex expressions for const arguments involving parameters (for now), e.g. {X * 2}.
  • Audit diagnostics (e.g. Add help note to unconstrained const parameter #76401 (comment)).
@withoutboats withoutboats added A-const-fn A-type-system Area: Type system B-RFC-approved Blocker: Approved by a merged RFC but not yet implemented. C-tracking-issue Category: An issue tracking the progress of sth. like the implementation of an RFC T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. T-lang Relevant to the language team, which will review and decide on the PR/issue. labels Sep 14, 2017
@eddyb
Copy link
Member

eddyb commented Sep 15, 2017

#44275 added a ConstEvaluatable predicate, and WF([T; expr]) now requires ConstEvaluatable(expr), as expr is lazily evaluated (even if it's just an integer literal). Fulfilling this predicate requires the expression to evaluate successfully, while normalization ignores the error and simply leaves the Unevaluated expression it found, untouched, which is more or less what happens with associated type projections. I expect the same system to scale to const generics.

@EpicatSupercell has expressed interest in working on this, I'll mentor them through the initial implementation. However, we can't go too far because of the limitations described in #44275.

That is, we need @nikomatsakis' lazy normalization to allow constant expressions embedded in types to observe the bounds in scope (from the function / type definition / impl / etc. item they're in), without producing cyclic dependencies half the time.

@eddyb
Copy link
Member

eddyb commented Sep 18, 2017

Implementation waypoints (for more direct mentoring, seek @eddyb on Gitter or eddyb on IRC):

  • Declaration / Syntax:
  • Declaration / Semantics
    • Data structures: ty::Generics - add const parameters alongside type ones
    • Conversion from HIR: generics_of - create ty::ConstParameterDef from hir::ConstParam
  • Use / Name Resolution
    • Data structures: Def - add a variant for const parameters
    • Name resolution pass: with_type_parameter_rib - support both type and const generics
  • Use / Semantics
    • ConstVal - add Param variant akin to ty::TyParam
    • Conversion from HIR: TyArray with a length that's an ExprPath that resolved to Def::ConstParam should use ConstVal::Param instead of ConstVal::Unevaluated - in a similar fashion to how Def::TyParam turns into ty::TyParam
    • subst::Kind - support &ty::Const and check as_const as well in where places where as_type and as_region are checked
  • Inference

Note that all of this should allow impl<T, const N: usize> Trait for [T; N] {...}, but not actually passing a constant expression to a type/function, e.g. ArrayVec<T, 3>.

@eddyb eddyb added the E-mentor Call for participation: This issue has a mentor. Use #t-compiler/help on Zulip for discussion. label Sep 18, 2017
@eddyb eddyb self-assigned this Sep 18, 2017
@jplatte
Copy link
Contributor

jplatte commented Sep 18, 2017

I'd like to take a stab at this :)

@samsartor
Copy link

@jplatte @eddyb Any news on this?

@jplatte
Copy link
Contributor

jplatte commented Oct 26, 2017

@samsartor there was a refactoring that had to be done before the main implementation work. That is now almost done (I'm waiting for feedback currently). I don't actually know how much work there is after that. Parsing const params was what I started with initially, before the refactoring. It's not done but I should be able to get that done relatively soon.

@EdorianDark
Copy link
Contributor

@jplatte It would be nice, if you could link the pull request. I was not able to find it.

@jplatte
Copy link
Contributor

jplatte commented Nov 6, 2017

There is no PR yet. All my work can be found here.

@RobertWHurst
Copy link

Nice work so far @jplatte 🍻

@jplatte
Copy link
Contributor

jplatte commented Nov 11, 2017

There is now a PR for the groundwork (Generics refactoring): #45930

@huhlig
Copy link

huhlig commented Nov 17, 2017

I think this is already included but it would be good to handle the C++ style folding for handling linear algebra style n dimensional arrays with varying lengths, I.E. a 4x4 [[f64;4];4]or a 4x3x5x6 dimensional array [[[[f64;6];5];3];4] and be able to properly wrap and generate specialized methods for both it AND proper trait implementations for scalars properly dimensioned vectors, etc. See https://gist.github.com/huhlig/8b21850b54a75254be4b093551f8c2cb for a rudamentary example.

@Ixrec
Copy link
Contributor

Ixrec commented Nov 18, 2017

I don't recall anyone proposing fold expressions for Rust before, much less as part of this RFC. But since this is Rust, is there any reason we couldn't implement fold expressions as an ordinary macro, rather than new dedicated syntax?

@varkor
Copy link
Member

varkor commented Oct 19, 2019

You would typically move it out to a function, except the following won't work because certain values that are used in pattern matching have become variables:

This seems like a use-case that is more readily addressed by allowing the values of bound variables to be used in patterns (not just consts), with some new syntax. The fact that consts are currently allowed in patterns is counter-intuitive and, as far as I'm aware, historical.

@mark-i-m
Copy link
Member

@mqudsi Forgive me if this is a silly question, but I don't see anything wrong about the example you gave. It looks like a perfectly valid use case for const generics to me: having a definition that is generalized to work with arbitrary values as the max/min. I don't really see the benefits of const arguments over const generics. They seem equivalent to me; that is, const arguments could just be implemented as a desugaring to const generics. Could you elaborate more on what's wrong with this design pattern?

@varkor
Copy link
Member

varkor commented Oct 19, 2019

Here's a summary of the work on const generics since the last update. Last time, it was all about the core implementation: making sure everything fitted together and getting some of the basic test cases passing. Since then, the effort has been focused on making const generics more reliable: fixing cases that crashed the compiler, or didn't work unexpectedly, or improving diagnostics. We're getting closer to something that works reliably, though there's still a way to go.


Additionally, other work on the compiler ended up fixing some of the other issues relating to const generics.

We've also started using const generics inside the compiler itself: array trait implementations now use const generics thanks to the work of @crlf0710 and @scottmcm (#60466, #62435), which led to performance improvements, and which will also allow us to unrestrict array trait implementations in the future (when const generics is stabilised). @Centril used the same approach to improve VecDeque (#63061).


Many of the particularly common bugs with const generics have been fixed in the past few months. @nikomatsakis is investigating lazy normalisation, which should fix a host of the remaining issues, while @jplatte is looking into fixing the disambiguation of const parameters from type parameters (so you'll no longer have to type {X} for a const argument).

I also want to thank @eddyb for all their mentoring and reviewing for const generics throughout development, which has been invaluable.

There are still quite a number of other issues to address and, as before, we could use all the help we can get — if you're interested in tackling any of the remaining issues, feel free to ping me on the issue, or on Discord or Zulip for pointers on getting started.

@PvdBerg1998

This comment has been minimized.

@mark-i-m

This comment has been minimized.

@hadronized

This comment has been minimized.

@newpavlov

This comment has been minimized.

@rpjohnst

This comment has been minimized.

@hadronized

This comment has been minimized.

@rpjohnst

This comment has been minimized.

@hadronized

This comment has been minimized.

@hadronized

This comment has been minimized.

@tema3210

This comment has been minimized.

@rpjohnst

This comment has been minimized.

@RustyYato

This comment has been minimized.

@bstrie
Copy link
Contributor

bstrie commented Oct 20, 2019

I would like to request that we reserve the discussion of such a significant syntactic change for either a thread on internals or an issue (or amending PR) on the RFCs repo. This issue's comment section is already quite long and the syntax in question seems unnecessary for a usable MVP of const generics.

@eddyb
Copy link
Member

eddyb commented Oct 20, 2019

If we could move comments we probably would. We might want to lock the issue to @rust-lang team members and hide all the offtopic comments?

All design discussion should happen on the RFC repo and all bug reports should be in separate issues.

cc @rust-lang/moderation Is there precedent for doing this?

@rust-lang rust-lang locked as off-topic and limited conversation to collaborators Oct 20, 2019
@Manishearth
Copy link
Member

You can convert a comment to an issue, but not move comments. Locking is fine, and i'd just hide off topic comments.

@varkor
Copy link
Member

varkor commented Jan 2, 2020

With the start of the new year, I thought it would be good to give another update on where we are now with const generics. It's been a little over 2 years since the const generics RFC was accepted. In the first year (roughly 2018), a series of large refactoring efforts were undertaken to facilitate const generics by improving the handling of generic parameters generally throughout the compiler. In the second year (roughly 2019), work began on implementing const generics itself: first by getting the bare minimum working, and then by slowing improving the integrity of the feature. People also started to experiment with using const generics in the compiler itself. More detailed descriptions of these efforts are in the first two update posts: [1], [2].


There's been good progress in the last couple of months since the last update.

A big thanks to everyone who has been helping out with const generics!


What's next? The biggest blocker for const generics at the moment is lazy normalisation, which is required for certain kinds of const generic bounds (such as in arrays). @Skinny121 is currently investigating lazy normalisation, continuing their fantastic efforts taking down the big bugs in const generics. This would address many of the present issues with const generics.

Lazy normalisation aside, there are still a sizeable number of bugs and papercuts we'd like to address. If you're interested in tackling any of the remaining issues, feel free to ping me on the issue, or on Discord or Zulip for pointers on getting started. I'm confident we can make good headway in 2020 and hopefully approach a point where stabilisation becomes a viable discussion!

@withoutboats
Copy link
Contributor Author

Is there a subset of const generics that doesn't hit lazy normalization and doesn't have many bugs and papercuts, but which can express a good amount of useful code? I notice that std's impls of many traits for arrays seem to work just fine. Maybe there's a narrowing that would allow other crates to write the kind of impls we have in std for their own traits, even though they don't support all the fancier functionality?

@varkor
Copy link
Member

varkor commented Jul 22, 2020

We're now more than halfway through the year, so I'll briefly summarise the work that has been going on. There have been lots of people involved in improving const generics support in the last 6 months, so thank you to everyone who's helped in some way! I especially want to thank @Skinny121 and @lcnr, who have both tackled some large features that const generics has been lacking for a while: lazy normalisation for constants and const argument support in method calls, as well as fixing numerous difficult bugs. Their efforts are evident from the summary below.

Const generics is now being used in several places throughout the compiler, and there's already experimentation with traits and functions making use of const generics, e.g. slice::array_chunks and IntoIterator and FromIterator for [T; N] (#65819, #69985). The length 32 restriction for array trait implementations is also finally being prepped for removal.

We're currently discussing stabilising a subset of const generics that should cover a wide range of use cases (though there are still some issues left to address before const generics can be fully stabilised).



While const generics has already come a long way, there are still bugs and sharp edges. If you're interested in tackling any of the remaining issues, feel free to ping me, @lcnr or @eddyb on the issue, or on Zulip, for pointers on getting started. Thank you!

@lcnr
Copy link
Contributor

lcnr commented Nov 17, 2020

Now that we're looking to stabilize #![feature(min_const_generics)] in #79135 let's once again summarize all the amazing work that's been going on since the last update. A lot of new people have come and helped out with getting #![feature(min_const_generics)] ready for stabilization as well as improving other parts of const generics. A huge thanks to everyone who spend their valuable time helping out here, no matter how small your contributions might have been!

I want to use this comment to especially highlight and thank @varkor! They not only fixed some large and complicated issues but also do a lot of less visible work by mentoring and helping others as well as collecting and triaging the remaining issues. While so many amazing people are responsible for where we are now, I do not believe this would have been possible without @varkor.

On other news, with #74060 now being merged, many traits are now implemented for arrays of any size, greatly improving the experience of working with them. This is available on stable since version 1.47 🎉


While they have not opened any pull requests themselves since the last update, I also want to thank @petrochenkov, @nikomatsakis and @oli-obk for reviewing and helping with many of the more complicated changes seen above.


While we have come a long way over the last 3 years, this is still far from over. Even just for #![feature(min_const_generics)] there will always be diagnostics to add, bugs to fix and performances to improve. Looking a bit further into the future, there is even more work to do, some of which is explored in the future work section of #79135. If you are interested in helping out with any of this, feel free to either join the project group on zulip, comment on the relevant issues or directly reach out to either me or @varkor.

@lcnr lcnr self-assigned this Dec 18, 2020
@lcnr
Copy link
Contributor

lcnr commented Dec 11, 2021

A year has passed and we're finally stabilizing the next feature related to const generics:

feature(const_generics_defaults)

With this, I am going to once again summarize the progress made here. This summary was written by @lcnr and therefore overrepresents parts I have been involved with while not giving other areas the focus they deserve.

Generic const arguments

Soon after the stabilization of feature(min_const_generics) we started to focus on supporting generic expressions as const arguments. While doing so, we encountered quite a few major obstacles, because of which @rust-lang/project-const-generics started to have some weekly meetings in February. The current status can be tested using #![feature(generic_const_exprs)].

While we believe that we now know most of the remaining blockers, we also know that these are sadly very difficult to deal with.
Because of this, feature(generic_const_exprs) is still really far away from stabilization. @BoxyUwU and I recently discussed a potential #[feature(min_generic_const_exprs)] which can be more easily stabilized while still allowing computations in generic const arguments.

We still have to take these ideas to the rest of @rust-lang/project-const-generics, but there should hopefully be some news about this during the next year.

as the work on this feature has been greatly influenced by me experiencing burnout, here's a quick reminder that you should take regular breaks from any open source work you might do. always being available is incredibly unhealthy and is not desirable or praiseworthy

Valtrees

Right now, constant values used as arguments for const parameters are represented using "allocations", this makes checking them for equality somewhat difficult, as comparing allocations directly does not consider two different &3 to be equal to each other and causes some other annoyances.

To deal with this, we (mostly @oli-obk and @RalfJung) introduced the concept of valtrees, which represents constant values in the type system as simple trees with integer leaves. Checking equality of valtrees is fairly trivial and using them avoids some other, more subtle issues as well. @oli-obk started to implement this in #82936 and while progress has recently stalled due to a lack of time, this is definitely something to look forward to.

Const parameter defaults

In #75384 @JulianKnodt began implementing const parameter defaults, with the initial PR taking more than 7 months and racking up a total of over 200 comments. Using this as a starting point, fixing the remaining issues was fairly straightforward, allowing us to stabilize this feature in #90207.

Generic arguments in patterns

After stabilizing feature(min_const_generics) in #79135, @CraftSpider opened #80531, showing that specifying the argument for const parameters in patterns is not supported. To my knowledge, nobody noticed this before, which is especially worrying considering that const generics was already stable on nightly at that time. The PR which fixed this is #80551.

match Some(Default::default()) {
   Some::<u8>(a) => assert_eq!(a, 0),
   None => {}
}

The same issue also existed for trait methods with incorrect const parameter types which has been fixed in #86843.

This shows that even though const generics has been used a lot while unstable and we took a lot of effort to improve our test coverage before stabilizing feature(min_const_generics), there were still some pretty simple bugs we've missed.

Pull Requests

Finally, an overview of most pull requests related to const generics which have been merged since the last update. As const generics is now stable and "infects" large parts of the compiler, and const parameters are fairly frequently used, there are many changes related to const generics which I did not mention here.

The decisions on which PRs to mention and which ones to ignore were made in mere seconds and are not well thought out. There are also changes I've simply missed while searching for them. If you see a pull request which should be mentioned here please either edit this comment yourself or pm me on zulip.

While this does highlight people working with and on const generics, there are many people whose contribution to const generics is not reflected below. Thank you to everyone who contributed.

@joshtriplett joshtriplett added the S-tracking-impl-incomplete Status: The implementation is incomplete. label Feb 9, 2022
@joshtriplett
Copy link
Member

Thanks to @lcnr for the ongoing excellent summaries!

@lcnr
Copy link
Contributor

lcnr commented Mar 21, 2022

All remaining const generics features are tracked in separate issues:

For more than 2 years now this issue has been pretty much exclusively used for update posts by either @varkor or myself. I intend to keep posting these updates but don't think this issue is necessarily the right place for them. I currently intend to post them to the Inside Rust blog, but I will try to link to the first of these posts here once the time has come.

Once again a huge thanks to everyone who has contributed to const generics over the last 5 years.

@lcnr lcnr closed this as completed Mar 21, 2022
@RalfJung RalfJung added the A-const-eval Area: Constant evaluation, covers all const contexts (static, const fn, ...) label Dec 1, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
A-const-eval Area: Constant evaluation, covers all const contexts (static, const fn, ...) A-const-generics Area: const generics (parameters and arguments) A-type-system Area: Type system B-RFC-approved Blocker: Approved by a merged RFC but not yet implemented. C-tracking-issue Category: An issue tracking the progress of sth. like the implementation of an RFC F-const_generics `#![feature(const_generics)]` requires-nightly This issue requires a nightly compiler in some way. S-tracking-impl-incomplete Status: The implementation is incomplete. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. T-lang Relevant to the language team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests