ecstatic-morse commented 4 years ago

This is a tracking issue for a more precise version of checking for drops in const contexts.

The feature gate for the issue is #![feature(const_precise_live_drops)].

With this feature enabled, drops are checked on slightly elaborated MIR. This makes the analysis that prevents dropping in const fn more accurate for code that does not actually drop anything: specifically, if the initial MIR contains an unnecessary call to drop that may be eliminated in elaboration, it can be accepted with const_precise_live_drops.

Internally, the library can also use this on a per-function basis with #[rustc_allow_const_fn_unstable(const_precise_live_drops)].

About tracking issues

Tracking issues are used to record the overall progress of implementation. They are also used as hubs connecting to other relevant issues, e.g., bugs or open design questions. A tracking issue is however not meant for large scale discussion, questions, or bug reports about a feature. Instead, open a dedicated issue for the specific matter and add the relevant feature gate label. Discussion comments will get marked as off-topic or deleted. Repeated discussions on the tracking issue may lead to the tracking issue getting locked.

Steps

[x] implementation: #71824

Blockers and Concerns:

https://github.com/rust-lang/rust/issues/91009
Changes to what exact elaboration occurs may change what we accept
(per Ralf on Zulip): ideally this would run on the same MIR and with the same logic as borrowck, but that is hard.

RalfJung commented 4 years ago

Cc @rust-lang/wg-const-eval (which I think never happened for this feature or the PR)

DoumanAsh commented 3 years ago

Is there particular reason why this was moved to be a feature? It is more or less bug fix to inaccurate drop detection. So shouldn't it be already stable? This would make it easier to create builders with generic parameters as we currently cannot mutate self

oli-obk commented 3 years ago

cc @rust-lang/lang I am nominating this feature for stabilization

citing @ecstatic-morse from the impl PR:

This isn't really a "feature" but a refinement to const-checking, and it's kind of non-obvious what the user opts in to with the feature gate, since drop elaboration is an implementation detail. A relevant precedent is #![feature(nll)], but that was much larger and more fundamental than this change would be.

This is also somewhat relevant to the stabilization of #![feature(const_if_match)]. Nothing in this PR is specifically related to branching in constants. For instance, it makes the example below compile as well. However, I expect users will commonly want to move out of Option::<T>::Some within a match, which won't work without this PR if T: !Copy

const _: Vec<i32> = {
    let vec_tuple = (Vec::new(),);
    vec_tuple.0
};

To clarify, this PR makes that code compile because previously we were dropping the vec_tuple which had type Option<(Vec,)>?

This code is functionally no different from the following, which currently works on stable because x is moved into the return place unconditionally.

const X: Option<Vec<i32>> = { let x = Vec::new(); x };

Const-checking only considers whole locals for const qualification, but drop elaboration is more precise: It works on projections as well. Because drop elaboration sees that all fields of the tuple have been moved from by the end of the initializer, no Drop terminator is left in the MIR, despite the fact that the tuple itself is never moved from.

RalfJung commented 3 years ago

@oli-obk how do things look like in implementation complexity and the risk of locking us into a scheme that might be hard to maintain or make compatible with other future extensions?

DoumanAsh commented 3 years ago

I believe implementation complexity should not be an issue considering current behavior is bug as compiler incorrectly reports error on drop being executed in const fn. Such things ought to be fixed in any case. Unless we're fine with compiler incorrectly reporting error as right now?

oli-obk commented 3 years ago

I believe implementation complexity should not be an issue considering current behavior is bug as compiler incorrectly reports error on drop being executed in const fn. Such things ought to be fixed in any case. Unless we're fine with compiler incorrectly reporting error as right now?

We may be able to achieve the same result (allowing these kind of const fn) with a different scheme. So Ralf's question is absolutely reasonable to ask and I will answer it after reviewing the implementation again in detail so I can give an educated answer.

RalfJung commented 3 years ago

@DoumanAsh due to the halting problem, rustc will always report "incorrect errors". It is impossible to predict at compiletime if e.g. drop will be executed when a piece of code is being run. Similarly, the borrow checker will always reject some correct programs. That's just a fact of programming languages. Neither of these are a bug.

So there's always a trade-off between analysis complexity and "incorrect errors", but even the best analysis will sometimes show "incorrect errors". My impression after looking at the PR here is that the analysis complexity is totally reasonable (it mostly implicitly reuses the analysis performed by drop elaboration), but this is still a decision we should make explicitly, not implicitly.

More precise drop analysis in const fn is a new feature, not a bugfix. (Just like, for example, NLL was a new feature, not a bugfix.)

@oli-obk Thanks. :) As you probably saw, I also left some questions in the PR that implemented the analysis.

oli-obk commented 3 years ago

I did see these comments, just didn't have time to look more deeply yet.

Cross posting from the comments on that PR:

I am guessing the difference between the needs_drop analysis, and drop elaboration's use of MaybeInitializedPlaces and MaybeUninitializedPlaces is the reason that this feature gate exists at all. We could probably rewrite drop elaboration in terms of the NeedsDrop qualif, which would (afaict) allow post_drop_elaboration to not do any checks except for looking for Drop terminators.

Of course such a change would insta-stabilize the feature gate from this PR without any reasonable way to avoid said stabilization. So I'm tempted to stabilize the feature but leave a FIXME on this function to merge its qualif checks into elaborate_drops

RalfJung commented 3 years ago

We could probably rewrite drop elaboration in terms of the NeedsDrop qualif, which would (afaict) allow post_drop_elaboration to not do any checks except for looking for Drop terminators. Of course such a change would insta-stabilize the feature gate from this PR without any reasonable way to avoid said stabilization.

Even worse, it would change drop elaboration, which is a rather tricky part of the compiler.^^ That should be done with utmost care.

nikomatsakis commented 3 years ago

r? @nikomatsakis

Mark-Simulacrum commented 3 years ago

Dropping the nomination here as it's waiting on Niko; that's tracked in the language team action item list.

inquisitivecrystal commented 3 years ago

What remains to be done before this can be stabilized?

ecstatic-morse commented 3 years ago

Hey y'all. I'll try to summarize exactly what this feature gate does to help inform a decision on stabilization. Oli and Ralf probably already know this information, and can skip the next section.

Background

Currently, it is forbidden to run custom Drop implementations during const-eval. This is because Drop::drop is a trait method, and there's no (stable) way to declare that trait methods are const-safe. MIR uses a special terminator (Drop) to indicate that something is dropped. When building the MIR initially, a Drop terminator is inserted for every variable that has drop glue (ty.needs_drop()). Typically, const-checks are run on the newly built MIR. This is to prevent MIR optimizations from eliminating or transforming code that would fail const-checking into code that passes it, which would make compilation success dependent on MIR optimizations. In general, we try very hard to avoid this.

However, some Drop terminators that we generate during MIR building will never actually execute. For example,

A struct has a field with a custom Drop impl (e.g. Foo(Box<i32>)), but that field is always moved out of before the variable goes out of scope.
An enum has a variant with a custom Drop impl, but we are in a match arm for a different variant without a custom Drop impl.

We rely on a separate MIR pass, elaborate_drops, to remove these terminators prior to codegen (it also does some extra stuff, like adding dynamic drop flags). This happens pretty early in the optimization pipeline, but it is still an optimization, so it runs after const-checking. As a result, the stable version of const-checking sees some Drop terminators that will never actually run, and raises an error.

Current Implementation

#![feature(const_precise_live_drops)] defers the Drop terminator const-checks until after drop elaboration is run. As I mention above, this is unusual, since it makes compilation success dependent on the result of an optimization. On the other hand,

Drop elaboration doesn't change very often. Unlike some other optimizations, it is conceptually pretty simple to determine whether a Drop terminator is frivolous along a given code path. It depends solely on whether some set of move paths are initialized at that point in the CFG.
It is always profitable to remove drop terminators from the MIR when we can. This makes it unlikely that we will ever want to "dial back" drop-elaboration.
- Despite being conceptually straightforward, drop elaboration is not free to compute and having two separate implementations of it (one in const-checking and one in the optimization pipeline) is both inefficient and bad for maintainability.
- If there is bug in drop elaboration that causes us to wrongly eliminate Drops, wrongly accepting some const fns will be the least of our worries, relatively speaking.

For these reasons, I chose the current implementation strategy. I realize that none of these arguments are dispositive, and I don't think it's unreasonable to gate stabilization of this feature on reimplementing the relevant bits of drop elaboration inside const-checking, although I still think it's overly conservative.

Besides that big question, I think there were also some concerns from const-eval members around the use of the NeedsDrop qualif and test coverage (e.g. https://github.com/rust-lang/rust/pull/71824#discussion_r594392980). I'll try to answer those so they can provide a recommendation.

inquisitivecrystal commented 3 years ago

I'm not educated on the details, but it would be super nice to see this stabilized in some form. There are a comparatively large number of new APIs that rely on this. For examples, see issues #76654, #82814, and PR #84087, the last of which is an approved stabilization PR that can't be merged until this is stabilized.

That's why I was checking in on the progress towards stabilization a few days ago. I'm sorry about that, by the way. I know that that sort of message can be annoying, but I wanted to know there if there was anything I could do to help move this along.

ecstatic-morse commented 3 years ago

The fact that the main blocker (and why this was feature gated in the first place) is the implementation makes it somewhat unusual (see https://github.com/rust-lang/rust/pull/71824#discussion_r421675954). That makes it more the domain of the compiler-team rather than the lang-team. Niko reviewed #71824 and is assigned to this issue, but I'm hesitant to ping them specifically unless their expertise is required.

So, if you want to see this stabilized I would figure out some process for getting consent from the compiler team. I think they use the MCP process for this exclusively? Oli is a member, so there's at least one potential sponsor. The team might require documenting the drop-elaboration/const-checking dependency in the dev-guide and maybe the module itself, which I'm happy to do if asked. After that, I can write a stabilization report with some examples and we can do lang-team FCP (assuming any lingering concerns from @rust-lang/wg-const-eval have been addressed).

I'm, uh, not great at navigating bureaucratic systems with many veto points, so if you want to drive this forward your help would be greatly appreciated. However, unless we end up reimplementing drop-elaboration in const-checking like I mention above, I don't think much of the remaining work is technical.

oli-obk commented 3 years ago

I think your summary post contains most of what we need for a stabilization report (full instructions here). We can just mark this issue as requiring sign-off from both T-compiler and T-lang and do all of this at once.

oli-obk commented 3 years ago

Request for stabilization

I would like to stabilize the const_precise_live_drops feature.

Summary

It enables more code to be accepted in const fn. Caveat: const checking is now dependent on drop elaboration, so changes to drop elaboration can silently change what code is allowed in const fn. Details can be found at https://github.com/rust-lang/rust/issues/73255#issuecomment-889420241

A prominent example that doesn't work right now, but would with this feature is Option::unwrap:

const fn unwrap<T>(opt: Option<T>) -> T {
    match opt {
        Some(x) => x,
        None => panic!(),
    }
}

rustc believes that opt will still get dropped in the panic arm (when const checks are running), because the MIR still contains a Drop terminator on that arm.

Documentation

There is none. This feature solely reorders existing passes.

Tests

Demonstrate field and variants being moved out of (without the feature const checks think that the original aggregate may still get dropped and thus execute a non-const destructor)
check that only unstable const fn can use the feature, see also this test
check that previously accepted code still works
interaction with const drop, and more of the same
Show limits of the feature

@rfcbot fcp merge

rfcbot commented 3 years ago

Team member @oli-obk has proposed to merge this. The next step is review by the rest of the tagged team members:

[x] @Aaron1011
[x] @cramertj
[x] @davidtwco
[x] @eddyb
[ ] @estebank
[x] @joshtriplett
[x] @lcnr
[x] @matthewjasper
[ ] @michaelwoerister
[x] @nagisa
[ ] @nikomatsakis
[x] @oli-obk
[x] @petrochenkov
[ ] @pnkfelix
[ ] @scottmcm
[ ] @wesleywiser

Concerns:

reference-material (https://github.com/rust-lang/rust/issues/73255#issuecomment-946942927)

Once a majority of reviewers approve (and at most 2 approvals are outstanding), 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.

RalfJung commented 3 years ago

because the MIR still contains a Drop terminator on that arm

Specifically, the "early" MIR that most of const checking runs on still has it. After drop elaboration, it is gone, which is why running the 'drop' part of const checking later makes such a difference.

nagisa commented 3 years ago

We run some passes early in the MIR pipeline (e.g. borrowck) which are considered to be an integral part of the language. I not sure if I would consider drop elaboration materially different from these and thus an (optional) optimization today. In that context I don't see an issue with it becoming a mechanism through which some programs are allowed to build.

cramertj commented 3 years ago

const checking is now dependent on drop elaboration, so changes to drop elaboration can silently change what code is allowed in const fn.

Do we have anything resembling a specification (RFC, reference, etc.) for drop elaboration that could be used to justify why certain const code does or does not compile? I'm not familiar with that part of the codebase, so it isn't clear to me whether there are lots of potentially implementation-dependent decision points that would be locked in as part of this stabilization, or whether the implementation is relatively unique and therefore unlikely to change in ways that would affect the code that compiles.

Additionally, it'd be nice to have some sort of specification for what code we expect to compile independent of the implementation, since that'd allow us to justify the resulting compiler errors to users without referring to the implementation details.

ecstatic-morse commented 3 years ago

No. Up until now, whether or not a stack-local drop flag could be optimized away for some variable didn't affect program semantics. RFC 320, which introduced the current dynamic drop rules, simply mentions that

Some compiler analysis may be able to identify dynamic drop obligations that do not actually need to be tracked.

That analysis, which is (part of) what came to be known as "drop elaboration", was implemented alongside the rest of the RFC in #33622. It remains mostly identical today modulo a few tweaks (e.g. #68943, which allowed it to make use of the more precise dataflow analysis around enum variants in #68528). As far as I know, there's no documentation besides the discussion on #33622 and the code itself, mostly in this file.

I can write up a description of what the algorithm is currently doing, but I wouldn't call that a "specification" without some form of operational semantics for the MIR. Regarding a specification that's "independent of the implemention": How do we describe a flow-sensitive analysis on the MIR besides describing its implementation? We already have some examples of what works and what doesn't (see Oli's comment). For comparison, the borrow-checker is not defined in the reference using normal Rust syntax but in terms of the MIR.

RalfJung commented 3 years ago

No. Up until now, whether or not a stack-local drop flag could be optimized away for some variable didn't affect program semantics.

Doesn't it affect the borrow checker? Locals need to be live when they are dropped, so whether or not it can be optimized away can affect whether or not a function is accepted by the borrow checker or not. That was my understanding, anyway. (Not sure what exactly you are including in 'program semantics', but even with this feature gate, the dynamic semantics of CTFE are not affected. Both borrow checker and const checking are static analyses, so them being affected by this seems very comparable in impact.)

ecstatic-morse commented 3 years ago

True. I've always been unclear about how much work is duplicated between drop elaboration and the borrow checker, since the latter runs first. The NLL RFC talks about things in terms of lifetimes and #[may_dangle] instead of initializedness, which makes it hard for me to equate the two. Perhaps Niko or Felix could say more?

nagisa commented 3 years ago

From what I remember borrowck relies upon the variable liveness annotations (StorageLive and StorageDead MIR statements) and does not rely on drop elaboration in any way or form. Drop elaboration IIRC works by deriving knowledge from these same annotations as well.

nikomatsakis commented 3 years ago

@rfcbot concern reference-material

I'm raising @cramertj's point to an actual concern. I don't think we need a "formal specification" but I do think we need documentation in the reference. It doesn't have to be enough to implement things independently, but I think that it should be enough that humans can understand it. @ecstatic-morse let's sync up about it a bit.

petrochenkov commented 3 years ago

Do I understand correctly that all of the drop elaboration details become irrelevant once const evaluator actually starts running Drop::drop impls? After that the difference between "not running this because drop elaboration optimized it out" and "not running this because it's a noop" disappears, and all of these cases "just work" simplifying the specification significantly. So the state in which the language spec depends on the drop elaboration pass details is more or less temporary?

RalfJung commented 3 years ago

No, we still need to check upfront if the destructors (the ones that remain after drop elaboration) actually can be run at const-time. It will always be possible for destructors to do non-const stuff, so we will always need a check like that.

petrochenkov commented 3 years ago

@RalfJung

It will always be possible for destructors to do non-const stuff

I don't understand, if the destructor can be optimized away by drop elaboration, then it certainly doesn't do any non-const stuff (because it doesn't do anything).

UPD: Ah, I see, the drop method has a "nominal" constexprness (as opposed to "actual" ability to run it at compile time), which may prevent it from being called from const context, but won't prevent it from being eliminated by drop elaboration.

RalfJung commented 3 years ago

Yes, that is correct.

Drop elaboration details will remain relevant because when we consider some type T whose destructor is called, we cannot know if it does non-const stuff. So we can accept that destruction in const fn if and only if the destructor is optimized away by const elaboration.

You seemed to say that somehow future work on const Drop would remove the dependency of const checking on drop elaboration. That is not the case, and I do not understand how you propose we could remove the dependency in that future world. Consider a function like

const fn something<T>(x: T) {}

If we added T: const Drop (or whatever the syntax will end up being), this is fine, but as written it is not. So whether the destructor for x can be optimized out by drop elaboration remains relevant.

petrochenkov commented 3 years ago

how you propose we could remove the dependency in that future world. Consider a function like

T can be assumed to be const Drop automatically, for example (like it's automatically assumed to be just Drop now). If something in the Drop::drop body is not actually constexpr, then an error will be reported on attempt to execute it by the interpreter. (But if the drop can be optimized out by drop elaboration, then such "something non-constexpr" is guaranteed to not appear during the interpretation.)

(I didn't participate in the const-impl/const-drop discussions, so excuse me if I repeat something that was discussed thousand times.)

UPD: My assumption was that the const checking is done only for the actually executed path, but apparently even

fn non_const() {}

const fn something() {
    if false { non_const() } else { () }
}

fn main() {}

doesn't currently work in Rust. Now it's probably time to remove myself from this thread and go continue writing C++.

RalfJung commented 3 years ago

T can be assumed to be const Drop automatically, for example (like it's automatically assumed to be just Drop now).

That is not backwards compatible.

If something in the Drop::drop body is not actually constexpr, then an error will be reported on attempt to execute it by the interpreter.

This would lead to post-monomorphization errors, and make implementation details (whether or not some destructor happens to be const-evaluatable or not) part of the observed semver guarantees of a library.

In principle, we could entirely ditch all const checks and just run the code in the interpreter and see what happens. (There even is a flag for that: -Zunleash-the-miri-inside-of-you.) We don't do that though, for the reasons stated above. I think your proposal would amount to doing exactly this.

I'm happy to continue this discussion on Zulip if you think it fits better there. More input from people that have not yet internalized all the quirks of our CTFE system is always welcome. :)

ecstatic-morse commented 3 years ago

I opened rust-lang/rustc-dev-guide#1240 last week.

I want to add some more context to this comment for @nikomatsakis (in case they declared notification bankruptcy). Like the const-checker, the borrow-checker also needs to ignore drops of places that are known to be uninitialized, and it also runs before drop elaboration. I believe it runs MaybeUninitializedPlaces solely to remove dead drop terminators. This is a bit less onerous for the borrow-checker than in the const-checker, since the former already has the MoveData (which contains the move path tree, etc).

To me, this suggests that we should do dead drop removal as a pre-pass for both the borrow-checker and the const-checker but keep full drop elaboration as an optimization. However, I remember false edges making things more complex: That's why the borrow-checker does not use mark_inactive_variants_as_uninit, for example. Do you think making "remove dead drops" a separate pass is feasible?

RalfJung commented 3 years ago

Do you think making "remove dead drops" a separate pass is feasible?

Or, alternatively, it might be nice to be able to share the results of MaybeUninitializedPlaces between borrowck and constck. If they are computed anyway, we might as well use them twice...

nbdd0121 commented 3 years ago

I am not sure why this code is accepted:

#![feature(const_precise_live_drops)]

struct S;

impl Drop for S {
    fn drop(&mut self) {
        println!("Hello!");
    }
}

const fn foo() {
    let s = S;
}

When trying to use it in const context it just says "error: any use of this value will cause an error" without any other errors generated.

edit: Filed as #90770.

RalfJung commented 3 years ago

Yeah that code should definitely not be accepted... something is seriously wrong somewhere.

When trying to use it in const context it just says "error: any use of this value will cause an error" without any other errors generated.

CTFE will bail once evaluation hits a non-const fn... probably the span of where that happens is outside this file (it is in the auto-generated drop glue) so that part of the error just disappears.

ecstatic-morse commented 3 years ago

@nbdd0121 Could you open a new issue? The final "post-borrowck cleanup" pass is the Deaggregator, which replaces the assignment _1 = S; with a nop because S has no fields. That means Sis never initialized in the MIR before itsDropterminator, so it never getsNeedsDrop`.

ecstatic-morse commented 3 years ago

In addition to the bug found by Gary above (#90770), we also had #90752 filed yesterday, a bug in drop elaboration proper. Time to test this part out:

If there is bug in drop elaboration that causes us to wrongly eliminate Drops, wrongly accepting some const fns will be the least of our worries, relatively speaking.

I recommend we don't stabilize #![feature(const_precise_live_drops)] as-is but instead pursue something like what I mentioned here:

this suggests that we should do dead drop removal as a pre-pass for both the borrow-checker and the const-checker but keep full drop elaboration as an optimization

nikomatsakis commented 3 years ago

Based on the previous comment, cancelling stabilization proposal:

@rfcbot fcp cancel

rfcbot commented 3 years ago

@nikomatsakis proposal cancelled.

RalfJung commented 3 years ago

This is probably also a blocker: https://github.com/rust-lang/rust/issues/91009

scottmcm commented 3 years ago

I noticed in a PR today that I accidentally changed what this was doing by making what I thought was just an optimization -- same as SimplifyBranches -- but changed the precise drop errors. So I'm glad to see the cancel here, since it made me nervous about where this was happening in the pipe.

Mark-Simulacrum commented 2 years ago

Visiting this for T-lang backlog bonanza. It looks like there's a recent-ish comment https://github.com/rust-lang/rust/pull/91410#issuecomment-984031808 indicating that #91009 remains a blocker, but we'd like an updated summary to confirm that and ask if there are other issues that are blocking moving ahead here (reference material, perhaps?).

RalfJung commented 2 years ago

I wonder if it is possible to make our existing const drop checks a bit smarter so that at least Option::unwrap can be accepted, without the future-compat hazard of letting dropck do the checking? It would be great to unblock (parts of) https://github.com/rust-lang/rust/issues/67441.

clarfonthey commented 1 year ago

Is this still blocked? It appears that #91009 has been closed.

The ability to make unwrap work in const fn would help a lot with simplifying a lot of existing code, since it can help replace a lot of manual match statements with unwraps.

RalfJung commented 1 year ago

We still have this problem: https://github.com/rust-lang/rust/issues/73255#issuecomment-979808791. Basically exactly the thing we were worried about (depending on subtle dropck details) actually came up just after the attempt to stabilize.

clarfonthey commented 1 year ago

Ah! Is there a dedicated issue open for that that can be linked in the description, or is that just a known issue at the moment?

RalfJung commented 1 year ago

It's not a very concrete issue, and I don't think is tracked anywhere explicitly outside of this tracking issue.

clarfonthey commented 1 year ago

That's fair. As is expected with all these const features, something subtle and complicated lurks in the depths that makes it hard to finish up.

I was kinda hopeful that this was mostly done, but alas.

RalfJung commented 1 year ago

It might be, I am honestly not familiar enough with drop elaboration to really evaluate the trade-offs here.

I hope someone else reading along has some good ideas for what can be done before we ask the lang team to discuss this again.

rust-lang / rust

Tracking issue for `#![feature(const_precise_live_drops)]` #73255

About tracking issues

Steps

Blockers and Concerns:

Background

Current Implementation

Request for stabilization

Summary

Documentation

Tests