search

rust-lang / rust

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

const fn tracking issue (RFC 911) #24111

Closed nikomatsakis closed 5 years ago

nikomatsakis commented 9 years ago

https://github.com/rust-lang/rust/issues/57563 | new meta tracking issue

Old content

Tracking issue for rust-lang/rfcs#911.

This issue has been closed in favor of more targeted issues:

Things to be done before stabilizing:

CTFE = https://en.wikipedia.org/wiki/Compile_time_function_execution

SoniEx2 commented 6 years ago

If only this worked on the playground... https://play.rust-lang.org/?gist=6c0a46ee8299e36202f959908e8189e6&version=stable

This is a non-portable (indeed, so non-portable that it works on my system but not on the playground - yet they're both linux) way of including the build time in the built program.

The portable way would be to allow SystemTime::now() in const evaluation.

(This is an argument for const/compile-time-eval of ANY function/expression, regardless of if it's const fn or not.)

oli-obk commented 6 years ago

That sounds to me like an argument for forbidding absolute paths in include_bytes 😃

If you allow SystemTime::now in const fn, const FOO: [u8; SystemTime::now()] = [42; SystemTime::now()]; would randomly error depending on your system perf, scheduler and Jupiter's position.

Even worse:

const TIME: SystemTime = SystemTime::now();

Does not mean the value of TIME is the same at all use sites, especially across compilations with incremental and across crates.

And even crazier is that you can screw up foo.clone() in very unsound ways, because you might end up selecting the clone impl from an array with length 3 but the return type might be an array of length 4.

So even if we allowed arbitrary functions to be called, we would never allow SystemTime::new() to successfully return, just like we would never allow true random number generators

leoschwarz commented 6 years ago

@SoniEx2 I guess this is a bit offtopic here, but you can implement something like that already today using a cargo build.rs file. See [Build Scripts](https://doc.rust-lang.org/cargo/reference/build- scripts.html) in the Cargo Book, specifically the section on the case study of code generation.

@oli-obk I think it's not completely the same issue because one is about versioning API safety while the other is about the build environment, however I do agree that they both can lead to ecosystem breakage if not applied with care.

joshtriplett commented 6 years ago

Please do not allow getting the current time in a const fn; we don't need to add more/easier ways to make builds non-reproducible.

solson commented 6 years ago

We can't allow any kind of non-determinism (like random numbers, the current time, etc) into const fn - allowing that leads to type system unsoundness since rustc assumes that constant expressions always evaluate to the same result given the same input. See here for a bit more explanation.

solson commented 6 years ago

A future method for handling cases like in https://github.com/rust-lang/rust/issues/24111#issuecomment-376352844 would be to use a simple procedural macro which gets the current time and emits it as a plain number or string token. Procedural macros are more-or-less completely unrestricted code that can get the time by any of the usual portable ways non-const Rust code would use.

oli-obk commented 6 years ago

@rfcbot fcp merge

I propose we merge this, because it is a somewhat sane option, is not a breaking change, prevents accidental breaking changes (changing a function in a way that makes it not const evaluable while other crates use the function in const contexts) and the only really bad thing about it is that we have to throw const before a bunch of function declarations.

nrc commented 6 years ago

@rfcbot fcp merge on behalf of @oli-obk - seems worth thinking about stabilisation and discussing the issues

rfcbot commented 6 years ago

Team member @nrc has proposed to merge this. The next step is review by the rest of the tagged teams:

Concerns:

Once a majority of reviewers approve (and none object), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

nrc commented 6 years ago

@rfcbot concern priority

We might want to punt on this until after the edition since I don't think we have the bandwidth to deal with any fallout.

@rfcbot concern everything-const

We end up in a bit of a C++ world where there is incentive to make every function you can const.

matklad commented 6 years ago

A summary of short discussion with @oli-obk:

  1. In the future, almost every function could be marked const. For example, everything on Vec could be const. In that world, it might make sense to get rid of const keyword altogether: almost everything can be const, and one will have to go out of one's way to change a function from const to non-const, so backwards compatability hazards about inferred constness probably wouldn't be terribly high.

  2. However, getting rid of const today is not feasible. Today's miri can't interpret everything, and it is not really thoroughly tested in production.

  3. It is actually backwards compatible to require const today, and then deprecate this keyword and swtich to inferred constness in the future.

Putting 1, 2 and 3 together, it seems a nice option to stabilize const keyword today, than expand the set of constant-evaluatable functions in future releses. After some time, we will have a thoroughly battle-tested hony badger constant evaluator, which can evaluate everything. At that point, we can switch to inferred const.

oli-obk commented 6 years ago

Wrt the fallout dangers: const fn has been wildly used on nightly, especially on embedded. Also, the const fn checker is the same checker as the one used for static initializers and constants (except for some static specific checks and function arguments).

The major disadvantage I see is that we're essentially advocating to spray const liberally across crates (for now, see @matklad 's post for future ideas

scottmcm commented 6 years ago

@rfcbot concern parallel-const-traits

It feels like stabilizing this will immediately result in a bunch of crates making a parallel trait hierarchy with Const at the front: ConstDefault, ConstFrom, ConstInto, ConstClone, ConstTryFrom, ConstTryInto, etc and asking for ConstIndex and such. That's not terrible -- we certainly have that a bit with Try today, though stabilizing TryFrom will help -- but I feel like it would be nice to at least have a sketch of the plan for solving it nicer. (Is that https://github.com/rust-lang/rfcs/pull/2237? I don't know).

(@nrc: It looks like the bot only registered one of your concerns)

oli-obk commented 6 years ago

Parallel-const-traits have the trivial solution in the hypothetical future const-all-the-things version. They'd just work.

In the const fn world you would not end up with trait duplication, as long as we don't allow const fn trait methods (which we don't atm), just because you can't. You could of course create associated constants (on nightly) which is kind of the situation the libstd was at a year ago, where we had a bunch of constants for initializing various types inside statics/constants, without exposing their private fields. But that's something that could already have been happening for a while and didn't.

solson commented 6 years ago

To be clear, ConstDefault is already possible today without const fn, and the rest of those examples (ConstFrom, ConstInto, ConstClone, ConstTryFrom, ConstTryInto) won't be possible even with this feature stabilized, since it doesn't add const trait methods as @oli-obk mentioned.

(ConstDefault is possible by using an associated const rather than an associated const fn, but it's equivalent in power as far as I know.)

eddyb commented 6 years ago

@scottmcm const fn in trait definitions is not possible today (oh @solson already mentioned it).

whitequark commented 6 years ago

@eddyb random idea: what if we made it possible to const impl a trait instead of adding const fn in trait definitions? (These two aren't mutually exclusive, too.)

solson commented 6 years ago

@whitequark https://github.com/rust-lang/rfcs/pull/2237 covers that idea, through a combination of const impl expanding to const fn on each fn in the impl, and allowing an impl with all const methods to satisfy a T: const Trait bound, without marking any of the methods const in the trait definition itself.

eddyb commented 6 years ago

@rfcbot concern design

We've historically punted on stabilizing any one specific const fn system for several reasons:

There are different design choices which would alleviate most or of all these problems (at the cost of introducing others), for example these are a couple of the ones that have come up:

aidanhs commented 6 years ago

Because this way your crate might end up depending on a function in another crate being compile time evaluable, and then the crate author changes something not affecting the function signature but preventing the function from being compile time evaluable.

@leoschwarz isn't this already a problem with auto traits? Maybe the solution to this is to integrate rust-semverver with cargo to detect this kind of unintended breakage.

That said, it's not clear to me what happens if miri has a evaluation time limit that you (as a library author) accidentally exceed, causing compilation failure downstream.

joshtriplett commented 6 years ago

@nrc I think "everything-const" is true, but not an issue. Yes, we'll end up marking a huge swath of things const.

durka commented 6 years ago

Just want to point out that I'm not sure I want everything inferred to be const. It's a decision about whether runtime or compile time is more important. Sometimes I think the compiler does quite enough computation at compile time!

On Wed, Mar 28, 2018 at 2:49 PM, Josh Triplett notifications@github.com wrote:

@nrc https://github.com/nrc I think "everything-const" is true, but not an issue. Yes, we'll end up marking a huge swath of things const.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/rust-lang/rust/issues/24111#issuecomment-376914220, or mute the thread https://github.com/notifications/unsubscribe-auth/AAC3ny9Wm9JK6p-fXf6gbaEgjFtBpMctks5ti6LigaJpZM4D66IA .

oli-obk commented 6 years ago

evaluation time limit

that limit is gone soon.

Just want to point out that I'm not sure I want everything inferred to be const.

Oh no, we're not going to randomly compute things at compile-time. Just allow random things to be computed in the body of statics, constants, enum variant discriminants and array lengths

scottmcm commented 6 years ago

@rfcbot resolved parallel-const-traits

Thanks for the corrections, folks!

aidanhs commented 6 years ago

that limit is gone soon.

Awesome. In that case, auto-const-fn (in combination with some integration of rust-semverver or similar to give information about breakage) sounds awesome, though the "add logging and cause breakage" could be problematic. Though you can bump version number I guess, it's not like they're finite.

oli-obk commented 6 years ago

Logging and printing are "fine" side effects in my model of constants. We'd be able to figure out a solution for that if everyone agrees. We could even write to files (not really, but act as if we did and throw away everything).

whitequark commented 6 years ago

I'm really concerned about silently throwing away side effects.

oli-obk commented 6 years ago

We can discuss that once we create an RFC around them. For now you just can't have "side effects" in constants. The topic is orthogonal to stabilizing const fn

durka commented 6 years ago

I'm a bit worried about the "just do a semver warning" approach to inferred constness. If a crate author who never thought about constness sees "warning: the change you just made makes it impossible to call foo() in const context, which was previously possible", will they just see that as a non-sequitur and silence it? Clearly, people in this issue frequently think about which functions can be const. And it would be nice if more people do that (once const_fn is stable). But is out-of-the-blue warnings the right way to encourage that?

On Thu, Mar 29, 2018 at 4:36 AM, Oliver Schneider notifications@github.com wrote:

We can discuss that once we create an RFC around them. For now you just can't have "side effects" in constants. The topic is orthogonal to stabilizing const fn

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/rust-lang/rust/issues/24111#issuecomment-377164275, or mute the thread https://github.com/notifications/unsubscribe-auth/AAC3n3MtmvrDF42Iy0nhZ2q8xC-QGcvXks5tjJ0ggaJpZM4D66IA .

leoschwarz commented 6 years ago

I think explicit const fn can be annoying and clutter many APIs however I think the alternative of implicitly assuming has way too many issues to be practicable:

However I really see the biggest problem in not making it explicit being that someone can accidentally break lots of code with a single change without even being aware of it. This is especially of concern with the long dependency graphs common in the Rust ecosystem. If it requires an explicit change to the function signature one will be aware of this being a breaking change more easily.

Maybe such a feature could be implemented as a crate level config flag that can be added at the root of the crate, #![infer_const_fn] or something like that, and stay opt-in forever. If the flag is added const fn would be inferred where possible in the crate and also reflected in the docs (and it would require that the called functions are const fn too), if a crate author adds this flag they sort of pledge to be cautious about versioning and maybe rust-semverver could even be forced.

SoniEx2 commented 6 years ago

What about doing it backwards?

Rather than having const fn, have side fn.

It's still explicit (you need to put side fn to call side fn, explicitly breaking compatibility), and removes clutter. (Some) intrinsics and anything with asm would be a side fn.

whitequark commented 6 years ago

That's not backwards compatible, though I guess it can be added in an edition?

On March 30, 2018 2:43:06 AM GMT+08:00, "Soni L." notifications@github.com wrote:

What about doing it backwards?

Rather than having const fn, have side fn.

It's still explicit (you need to put side fn to call side fn, explicitly breaking compatibility), and removes clutter. (Some) intrinsics and anything with asm would be a side fn.

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: https://github.com/rust-lang/rust/issues/24111#issuecomment-377333542

-- Sent from my Android device with K-9 Mail. Please excuse my brevity.

mark-i-m commented 6 years ago

I think the bigger problem is that it would be a real shock to beginners, since that's not what most programming languages do.

eddyb commented 6 years ago

@whitequark I disagree with anything that just does that ("throw away side-effects"), I think @oli-obk was talking about a future extension but from the discussions I was in, I know the following

EDIT: just so the discussion doesn't derail, e.g.:

Throwing away side effects can lead to code behaving differently (say write and then read a file) if it's called const or non const.

We can (probably?) all assume @oli-obk misspoke regarding throwing away side-effects like that.

eddyb commented 6 years ago

Maybe such a feature could be implemented as a crate level config flag that can be added at the root of the crate

That's a subset of the second example of past suggestions, from https://github.com/rust-lang/rust/issues/24111#issuecomment-376829588. If we have a scoped "config flag", the user should be able to choose more fine-grained scopes IMO.

What about doing it backwards? Rather than having const fn, have side fn. It's still explicit (you need to put side fn to call side fn, explicitly breaking compatibility), and removes clutter. (Some) intrinsics and anything with asm would be a side fn.

In https://github.com/rust-lang/rust/issues/24111#issuecomment-376829588 I tried to point out that entire libraries could be "all const fn" or "all side fn". If it wasn't on function declarations, but rather scoped, it could maybe work in a future edition. However, without "infer from body" semantics you have to design the trait interactions even for the opt-in side fn, so you're not gaining anything and you're introducing potentially massive friction.

eternaleye commented 6 years ago

Section 3.3 of Kenton Varda's "Singletons considered harmful" writeup seems relevant here (honestly, the whole thing is well worth reading).

What about debug logging?

In practice, everyone acknowledges that debug logging should be available to every piece of code. We make an exception for it. The exact theoretical basis for this exception, for those who care, can be provided in a few ways.

From a security standpoint, debug logging is a benign singleton. It cannot be used as a communication channel because it is write-only. And it is clearly impossible to cause any sort of damage by writing to a debug log, since debug logging is not a factor in the program's correctness. Even if a malicious module "spams" the log, messages from that module can easily be filtered out, since debug logs normally identify exactly what module produced each message (sometimes they even provide a stack trace). Therefore, there is no problem with providing it.

Analogous arguments can be made to show that debug logging does not harm readability, testability, or maintainability.

Another theoretical justification for debug logging says that the debug log function is really just a no-op that happens to be observed by the debugger. When no debugger is running, the function does nothing. Debugging in general obviously breaks the entire object-capability model, but it is also obviously a privileged operation.

oli-obk commented 6 years ago

My statement about "we can figure out a solution [for debugging]" was indeed referring to a potential future API, that is callable from consts, but has some form of printing. Randomly implementing platform specific print operations (just so we can make existing code with print/debug statements be const) is not something that a const evaluator should do. This would be purely opt in, explicitly not having different observable behaviour (e.g. warnings in const eval and command line/file output at runtime). The exact semantics are left to future RFCs and should be considered entirely orthogonal to const fn in general

Kixunil commented 6 years ago

Are there any significant disadvantages to const impl Trait and T: const Trait?

oli-obk commented 6 years ago

Other than even more spraying around of const, only some trait methods might be const, which would require more fine grained control. I don't know of a neat syntax to specify that though. Maybe where <T as Trait>::some_method is const (is could be a contextual keyword).

Again, that is orthogonal to const fn.

SoniEx2 commented 6 years ago

[u8; SizeOf<T>::Output]

If const and side fns are separate, we have to take actual design considerations into account. Easiest way to make them separate is to make const fns an extension to something we have today - the turing-complete type system.

Alternatively, make const fns really const: anything const fn should be evaluated as if every parameter was a const generic.

This makes them a lot easier to reason about, because I can't personally reason about const fns as they currently stand. I can reason about turing-complete types, macros, normal fns, etc, but I find it impossible to reason about const fn, since even minor details change their meaning completely.

oli-obk commented 6 years ago

since even minor details change their meaning completely.

Could you elaborate? Do you mean extensions like const fn pointers, const trait bounds, ...? Because I don't see any minor details in the bare const fn proposal.

Alternatively, make const fns really const: anything const fn should be evaluated as if every parameter was a const generic.

That's what we're doing at compile-time. Just that at runtime the function is used like any other function.

SoniEx2 commented 6 years ago

The problem is that any minor detail can turn a const eval into a runtime eval. This may not seem like a huge deal, at first, but it can be.

Let's say the function call is really long because it's all const fns? And you wanna split it into multiple lines.

So you add some lets.

Now your program takes 20x longer to run.

SimonSapin commented 6 years ago

@SoniEx2 The size of arrays ($N in [u8; $N]) is always evaluated at compile-time. If that expression is non-const, compilation will fail. Conversely, let x = foo() will call foo at runtime whether or not it is a const fn (modulo the optimizer’s inlining and constant propagation, but that’s entirely separate from const fn). If you want to name the result of evaluating some expression at compile-time you need a const item.

oli-obk commented 6 years ago

Now your program takes 20x longer to run.

That's not at all how const fn works!

If you declare a function const fn and you add a let binding inside it, your code stops compiling.

If you remove const from a const fn, it's a breaking change and will break all uses of that function inside e.g. const, static or array lengths. Your code that was runtime code and ran a const fn, would never ever run at compile-time. It's just a normal runtime function call, so it doesn't get slower.

Edit: @SimonSapin beat me to it :D

SoniEx2 commented 6 years ago

Const fn get evaluated at compile-time if possible.

That is,

const fn random() -> i32 {
    4
}

fn thing() -> i32 {
    let i = random(); // the RHS of this binding is evaluated at compile-time, there is no call to random at runtime.
}

Now let's say you have a const fn that takes arguments. This would get evaluated at compile-time:

fn thing() {
    let x = const_fn_with_1_arg(const_fn_returns_value());
}

This would cause const_fn_with_1_arg to be evaluated at runtime:

fn thing() {
    let x = const_fn_returns_value();
    let y = const_fn_with_1_arg(x); // suddenly your program takes 20x longer to run, and compiles 20x faster.
}
matklad commented 6 years ago

@eddyb I wonder if the design concern can be resolved by the observation that the "minimal const fn" is forward compatible with all potential future extensions? That is, my understanding is that we want to stabilize

marking free functions and inherent methods as const, enabling them to be called in constants contexts, with constant arguments.

This seems to be trivially fully forward compatible with any "const effects for traits" designs. It is also compatible with "inferred const" design, because we can make const optional later.

Are there any alternative future designs which are incompatible with the current "minimal const fn" proposal?

matklad commented 6 years ago

@nrc

Note that rfcbot didn't register your everything-const concern (one concern per comment!) However, it seems to be a subset of the design concern, which is addressed by my previous comment (TL;DR: current minimal proposal is fully compatible with everything, we could make const keyword optional in the future).

As for the priority/fallout concern, I'd like to document what we've discussed at all hands, and what we haven't documented already:

Additionally, note that not stabilizing const fn leads to proliferation of sub optimal API in the libraries, because they have to use tricks like ATOMIC_USIZE_INIT to work around lack of const fns.

oli-obk commented 6 years ago

let i = random(); // the RHS of this binding is evaluated at compile-time, there is no call to random at runtime.

No, that is not happening at all. It could be happening (and llvm probably is doing this), but you cannot expect any compiler optimizations that depend on heuristics to actually occur. If you want something to be computed at compile-time, stick it in a const, and you get that guarantee.

SoniEx2 commented 6 years ago

so const fn only get evaluated in a const, and this is basically useless otherwise?

why not have const and non-const fn strictly separate then?

see the semantics are a mess because they intentionally mix up compile-time and runtime stuff.

oli-obk commented 6 years ago

so const fn only get evaluated in a const, and this is basically useless otherwise?

They are not useless, they are executed at runtime like any other function otherwise. This means that you don't have to use different "sublanguages" of Rust depending on whether you are in a const evaluation or whether you are not.

why not have const and non-const fn strictly separate then?

The entire motivation for const fn is to not have this separation. Otherwise we'd need to duplicate all kinds of functions: AtomicUsize::new() + AtomicUsize::const_new(), even though both bodies are identical.

Do you really want to have to write 90% of libcore twice, once for const eval and once for runtime? The same probably goes for a lot of other crates.