search

rust-lang / rust

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

Tracking issue for const generics (RFC 2000) #44580

Closed withoutboats closed 2 years ago

withoutboats commented 7 years ago

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:

Remaining implementation issues:

eddyb commented 7 years ago

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

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

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

jplatte commented 7 years ago

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

samsartor commented 7 years ago

@jplatte @eddyb Any news on this?

jplatte commented 7 years ago

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

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

jplatte commented 7 years ago

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

RobertWHurst commented 7 years ago

Nice work so far @jplatte 🍻

jplatte commented 7 years ago

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

huhlig commented 7 years ago

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

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?

kjetilkjeka commented 6 years ago

What are the next steps now that #45930 is merged? @jplatte

jplatte commented 6 years ago

@kjaleshire The next step is to implement parsing of const generics (see @eddyb's comment further up). I've already started work on this before it became clear that the refactoring in the refactoring would be necessary. My existing work on that can be found here; it hasn't yet been rebased since the refactoring PR was merged though.

kjaleshire commented 6 years ago

@jplatte I believe you meant to mention @kjetilkjeka.

kjetilkjeka commented 6 years ago

Thanks for the update! I'm sure I'm far from the only one looking forward to this feature. Keep up the good work!

est31 commented 6 years ago

@jplatte not wanting to be impatient, but has there been any work on this? Do you need help? Should someone help out?

jplatte commented 6 years ago

@est31 Sorry. Haven't had time to work on this in a while, and I'm not entirely sure when I will have the time. Maybe it's best for someone else to continue where I left off. I think the parsing part is mostly done. There are two places in the code where I wasn't sure what to do in the case of a generic param being a const param:

There also aren't any tests for the parsing of const generics yet (and for the pretty-printing code that I updated at the same time). Not sure what other information I can provide that would be needed / helpful for someone else to continue working on this, but feel free to ping me if something is unclear about my code.

eddyb commented 6 years ago

@jplatte ~None in the first and nothing in the second~~ (cc @pnkfelix @nikomatsakis)

EDIT: nothing to do in either case.

yodaldevoid commented 6 years ago

@eddyb For the first linked snippet are you sure that None should be returned? I may not understand what is going on here, but it seems to me that nothing should be done. If None is returned other params that might be unsafe will be skipped.

eddyb commented 6 years ago

@yodaldevoid Sorry, you're right, I didn't realize this was on Generics.

yodaldevoid commented 6 years ago

I would like to pick this up where @jplatte left off. I've been working away at this for a couple days now, going through @eddyb's mentoring instructions as I've had time just to see if I could get anywhere. I've gotten down to the "Use / Semantics" section at this point. I'll probably swing by one of the chats soon enough to ask questions.

alexreg commented 6 years ago

@yodaldevoid Great to hear. I don't know about the Gitter, but you'll definitely get plenty of guidance on #rustc and/or #rust-internals on IRC!

varkor commented 6 years ago

@yodaldevoid: would you be up for some collaboration? I've also been doing some investigation into this issue (😅) — perhaps we could fill in the gaps in each other's work. (You can see what I've done so far here.) Maybe we could chat on IRC (#rustc or #rust-internals) about it?

yodaldevoid commented 6 years ago

@varkor It looks like you are further ahead than I got. I would certainly be willing to collaborate. I'll try to grab you on IRC at some point and in the mean time see if I've gotten anything done that you haven't already.

qwerty19106 commented 6 years ago

Is there any progress in this? I'm writing code for embedded, and I really need const generics.

yodaldevoid commented 6 years ago

@qwerty19106 Progress is being made on this, though slowly. @varkor and I have been working on this off and on as we had time. I made some progress this week and we are seeing the light at the end of the tunnel for basic usage.

Beyond just implementing const generics, we (varkor) have done some cleanup to make this all possible (see #48149 and #48523). I believe the current plan is to wait for those two pull requests to go through before pulling in const generics, but varkor can speak more to that.

I really understand your need for const generics for embedded work. I started on this because I too really want const generics so I can clean up and make type safe large swathes of embedded code.

TL;DR: Progress is going, but this is complex. I feel you on the embedded front.

mark-i-m commented 6 years ago

For the "documentation" checkbox, it would be great to get something in the rustc guide.

qwerty19106 commented 6 years ago

Thanks @yodaldevoid for your reply. I will look forward for the end of your work.

mark-i-m commented 6 years ago

Update for those curious (since I was also curious). Re: the two PRs mentioned above: #48523 has merged and #48149 is steadily making progress.

alexreg commented 6 years ago

@mark-i-m Good stuff! Nice work by @varkor. When's ETA roughly, do you know? :-)

flip111 commented 6 years ago

@alexreg https://github.com/rust-lang/rust/issues/51192#issuecomment-394126083

alexreg commented 6 years ago

Cheers, @flip111.

nikic commented 6 years ago

Looks like the second big refactoring PR #48149 got merged :)

Restioson commented 6 years ago

/cc me

est31 commented 6 years ago

Next @varkor PR #51880

varkor commented 6 years ago

Just wanted to give a quick update, as I know some people have been asking about the progress with const generics.

To give some context, in March , @yodaldevoid and I had an initial implementation that was almost working (the bulk of the implementation seemed to be done, and we were just cleaning up some remaining crashes). However, the branch we were working on was pre-miri. When miri was merged (and in a number of subsequent PRs), the code for dealing with constant evaluation changed significantly, meaning a lot of what we had done became outdated.

On top of that, it was decided that the generic parameters code needed to be cleaned up in general before tacking const generics on, both to improve readability, but also to make mistakes where we forgot to deal with const generics in a certain case harder to make. This was done in https://github.com/rust-lang/rust/pull/48523, https://github.com/rust-lang/rust/pull/48149 and will be completed in https://github.com/rust-lang/rust/pull/51880. These were a little more involved than I initially expected, and they've taken a little longer to push through than estimated.

In the meantime, @yodaldevoid and I have been working on making our original implementation compatible with all the subsequent changes in rustc. It's taken a while, but we're getting there (though there's the perennial problem of never having as much time as you expected). I hope we'll have some good news soon on that front. (Meanwhile, https://github.com/rust-lang-nursery/chalk has been making good progress, which should address some of the difficulties @eddyb originally described.)

Some people have asked how they can help: I think at this stage, it's going to be easier for us to try to finish off the initial implementation, and then see which parts need attention. Once that's ready, we're going to need a lot of tests, utilising const generics in different places (including invalid ones, for error messages), so that's definitely somewhere we could do with a lot of help! We'll let you know when that happens!

c-cube commented 6 years ago

Sorry if it's not the appropriate place for that, but I have a suggestion regarding equality of abstract const expressions. In general it directly reduces to full dependent typing and undecidable territory. However, in rust everything is eventually instantiated with concrete values/types, so we can assert some equalities and postpone their checking to monomorphic instances.

What I mean is that a relatively simple way of checking the equality of abstract const expressions is the following:

The pros of this method is that there isn't a need for a theorem prover, SMT solver, or arithmetic rewriter in rustc itself. "Only" a syntactic equality check of types, modulo aliases and modulo a set of equations provided by the user. The cons is that it's more manual for the user since seemingly obvious equalities like M+N=N+M have to be added explicitly.

Example:

/// this works directly because of syntactic checks
fn add_end<T:Copy, const N: usize>(a: &[T;N], b: T) -> [T;N+1] {
  let x : [T;N+1] = [b;N+1];
  x[0..N] = a;
  x
}

/// this should work already
fn append<T:Copy, const M:usize, const N:usize>(a: &[T;M], b: &[T;N])
  -> [T;{M+N}]
{ … }

/// Here the equation M+M==N must be carried over or checked whenever this function is used
fn sum_pairwise_append<const M: usize, const N: usize>(a: &[i32, M],b: &[i32;N])-> [T;N]
  where M+M == N {
  let mut res : [i32; N] = append(a,a);
  for i in 0 .. N { res[i] += b[i] };
  res
} 

fn main() {
  let a: [i32; 2] = [1;2];
  let b: [i32; 4] = [2;4];
  let _ = sum_pairwise_append(a, b);  // need to check 2+2=4 
}

Equations as axioms

This means that e1 == e2 should always be true, so it's not really a where constraint but more like a assert_eq!(e1,e2) that can be used by the type checker. Here the implementor makes a promise that this is always true, and exposes her users to compilation errors if they provide parameter that refute the equation.

Equations as constraints

Here a clause where e1 == e2 is a constraint that must be satisfied for the successful use of this parametrized trait/function. That means that e1 == e2 doesn't have to always hold, which may be interesting for equations only true over a domain, such as (x*y) / z == (y*x) / z which would fail to instantiate for z==0.

eddyb commented 6 years ago

@c-cube We already have a system for "implicit where clauses", at least for functions, derived from "WF (well-formedness) rules", i.e. if you define a fn foo<'a, 'b>(x: &'a &'b i32) {} then it requires callers to satisfy 'b: 'a (as a result of needing WF(&'a &'b i32) -> &'b i32: 'a -> 'b: 'a).

We can reuse that system (in fact this is already implemented) to push constraints given by the signature (of the form "this constant expression evaluates successfully") up to the callers, whereas anything used only inside the body would still need where clauses.

Most of everything else you're describing seems close to what's planned (including a form of "syntactic equality"), but we don't want "monomorphization-time" checks, we can instead have ways (either implicit or through where clauses) to "propagate constraints to instantiators", and then we produce errors where constraints are "still too generic" (so unknown if they hold), or otherwise if we can evaluate them and they don't happen to hold.

flip111 commented 6 years ago

Most of everything else you're describing seems close to what's planned

@eddyb do you know any reference posts that discusses these plans?

eddyb commented 6 years ago

@flip111 Probably some of the RFCs. Maybe @withoutboats knows better.

mark-i-m commented 6 years ago

51880 is done :tada: :tada:

eddyb commented 6 years ago

@withoutboats @oli-obk What do you think about blocking proper unification of expressions like N + 1 (from e.g. [T; N + 1]) on getting some basic form of symbolic evaluation in miri?

I think we'd already have a mechanism to encode it, when @varkor adds ConstValue::{Infer,Param}, we can use that to track "(shallowly) valid but unknown" (symbolic) values, and then also include value (mainly integers) operations and calls on top of that.

Any non-assert control-flow decisions would still require known values, but assert itself could perhaps be reified as AssertThen(condition, assert message, success value). (Both the condition and the success value could be symbolic!)

Being able to export the symbolic values into ty::Const means we can implement some of the unification outside miri, treating (most?) operations as opaque.

We have to be careful not to assume anything of inference variables, but for e.g. N + 1 I think we can support unifying two Add(Param(N), Bits(1)) together.

eddyb commented 6 years ago

@varkor A test-case I think should work with just lazy normalization, no unification:

/*const*/ fn append<const N: usize, T>(xs: [T; N - 1], x: T) -> [T; N] {
    let new = MaybeUninit::<[T; N]>::uninitialized();
    unsafe {
        let p = new.as_mut_ptr() as *mut T;
        (p as *mut _).write(xs);
        p.add(N - 1).write(x);
    }
    new.into_inner()
}

That would only work because:

So overall, we can probably rely on WF rules to force "validation" of const expressions onto the users, but we'd still want unification for other things (including not needing hacks like ArrayWithoutLast).

mark-i-m commented 6 years ago

53645

newpavlov commented 6 years ago

Small question which originates from discussion of Units of Measure. What should we do if type generic over constant does not directly depend on it? For example:

struct Foo<T, const N: usize> {
    a: T,
    // Will such array be "the way" to handle this problem?
    // Or do we want some kind of `std:marker::PhantomConstData`? (which can be a simple
    // type alias to the same array)
    // Or maybe make `PhantomData` to accept constants?
    _phantom: [(), N],
}
cuviper commented 6 years ago

_phantom: [(), N],

I assume you meant [(); N], but this will only work for usize.

I think it would make sense to have a special marker::PhantomConst allowing any const type.

Ekleog commented 6 years ago

Hmm… Re-reading the RFC with the latest comments in mind, I'm wondering: would something like this be allowed?

struct Foo<T, const V: T> {
    _phantom: PhantomConst<T, V>,
}

I can't see it being banned anywhere, but would have thought it'd deserve at least an example.

varkor commented 6 years ago

@Ekleog: as far as I'm aware, const parameter types may not depend on type parameters initially (though it would definitely make sense for an extension). (The implementation is trickier if we allow this, so it makes sense to start with the simplest version.)

wbogocki commented 6 years ago

How is the progress on this? Do we know an approximate time when this should hit nightly?

GabrielMajeri commented 6 years ago

@Zauberklavier As soon as this pull request is done. To quote from it:

There's a long way to go