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

Solving the problem with promotion #53

Closed
RalfJung opened this issue Aug 12, 2020 · 17 comments · Fixed by #67
Closed

Solving the problem with promotion #53

RalfJung opened this issue Aug 12, 2020 · 17 comments · Fixed by #67

Comments

@RalfJung
Copy link
Member

RalfJung commented Aug 12, 2020

Over the years, promotion has caused many problems. The point of this issue is to collect those cases, which hopefully serves as a useful argument when we start to deprecate some of those mechanisms or when we reject proposals to promote more things.

What is promotion?

The short version is "it makes &expr have static lifetime for some expr". For more details, see here.

What are the problems?

The earliest critical problem I am aware of is rust-lang/rust#50814, where I made Miri detect arithmetic overflows even in release mode and promotion made that unsound because it lead to unexpected const-eval failures. We later plugged that kind of soundness hole for good but it can still lead to unexpected program aborts, which is not great.

The high-level summary is that we have a problem when the promoted constant fails to evaluate: it might be in dead code, so we cannot just make compilation fail (that would mean that our decision to promote caused otherwise valid code to fail to compile). But we have to do something. All other constants stop compilation when they fail to evaluate, so this requires special cases all over the place (we have checks for "is this a promoted" in const error reporting, in codegen, in Miri, and probably more places; also see rust-lang/rust#75461, rust-lang/rust#71800).

Most recently, we realized that our required_consts scheme, which is supposed to ensure that we do not compile functions that use ill-formed consts, also needs a special case as we can indeed have ill-formed promoteds.

@oli-obk collected some more problems specifically around promoting const fn calls in #19.

Other "fun" cases of promotion requiring a special case:

What could be the solution?

First of all we tried hard to limit promotion and even de-promoted some functions (rust-lang/rust#67531, rust-lang/rust#71796). We distinguish between "implicit" and "explicit" promotion context (see here, and are less careful in "explicit" contexts such as const initializers. However, even those can have dead code, so all the problems caused by promoteds that fail to evaluate still apply.

But what is the endgame here, what is a subset of promotable expressions that actually avoids all these problems? The largest possible subset is the set of expressions that cannot fail to evaluate. This covers almost all of the above problems; if we consider validation failures (such as invalid results of unsafe code or unexpected interior mutability) to also be evaluation failures, then I think this indeed covers all the problems.

See this hackmd for the details of that possibility.

So the least thing would be to forbid all of fallible operations. Another choice, perhaps easier to explain, would be to say that we only promote things that would also be legal as a pattern. That would mean de-promoting all arithmetic and logical operations as well -- but it is not clear that we can get away with that, so we might have to settle for infallible operations.

The intended replacement for code that wants things to have static lifetime is to explicitly request that lifetime via rust-lang/rfcs#2920. Compilation fails when that const block fails to evaluate, which means that promotion itself cannot fail, thus satisfying the infallibility condition.

@oli-obk
Copy link
Contributor

oli-obk commented Aug 13, 2020

One way that satisfies just the "only promote things that we can successfully evaluate" would be to

  • do promotion, but don't modify the original MIR yet
  • try to evaluate the promoted
    • if successful, just finish the promotion
    • if not successful, look for a const wf bound (cc @lcnr) that matches the promoted
      • if there is one, just finish the promotion
      • if there is none, put the promoted into a debuginfo datastructure and let borrowck check that datastructure when encountering lifetime errors. In case of lifetime errors, suggest a wf bound matching the promoted

This will still be a breaking change, but it will be much less of one (and also not cause post-monomorphization errors)

@RalfJung
Copy link
Member Author

RalfJung commented Aug 13, 2020

Yes that would be like a fallback solution. The reason I like it less is that it is "too smart" -- that makes it really hard to predict what will happen, and now the lifetime of something can depend on subtle details of const evaluation. I would hope that at least in implicit promotion contexts, we can do better, since we promote less.

(EDIT: the following is outdated, see my next post)

But in explicit contexts, we have all the same problems! They can have dead code, too:

const FOO: i32 = {
  if false { &promotable }
}

So all the concerns about creating promoteds that fail const evaluation apply here, too, I think? All the time we were concerned about changing behavior due to suddenly evaluating things at compile-time that used to be run-time-evaluated, but I now feel like the worse part is the one where we have consts (with separate const-eval queries) that fail to evaluate.

Note that another cause of const-eval queries are nullary functions. But those don't cause any problems I think. I wonder why?

@RalfJung
Copy link
Member Author

I think I overreacted re: explicit promotion contexts.

The property that I was going for all along here is: When a CTFE query fails, that's a hard error. Promoteds in implicit contexts are always evaluated during codegen, even in dead code, so this implies that evaluation of an implicit promoted must never fail.

But for explicit promoteds, we either already hard-error when they fail as codegen needs their result (e.g. rustc_args_required_const), or we just evaluate them "on-demand" (const items). So we can do anything we want here in terms of promotion I think, as long as we do not add promoteds to required_consts -- which makes sense, they are not required, as the user did not ask for them to be evaluated.

@RalfJung
Copy link
Member Author

RalfJung commented Aug 13, 2020

We already check that explicit promotion succeeds or halts compilation:

https://github.com/rust-lang/rust/blob/814bc4fe9364865bfaa94d7825b8eabc11245c7c/src/librustc_mir/transform/promote_consts.rs#L801-L810

What we do not check yet, I think, is that evaluating the explicit promoted succeeds or compilation halts. That is a property we would need for this plan to work out.

@RalfJung
Copy link
Member Author

What we do not check yet, I think, is that evaluating the explicit promoted succeeds or compilation halts. That is a property we would need for this plan to work out.

But not proactively, i.e., only when the promoted is actually used. IOW, this should only lint on implicit promoteds:

https://github.com/rust-lang/rust/blob/d69b0997d7dcc99a188d5cb19137dedc4fc05d25/src/librustc_mir/const_eval/eval_queries.rs#L362

Can we store the information whether a promoted is implicit or explicit? That code currently checks the def_kind, but I think that will not work for rustc_args_required_const.

@oli-obk
Copy link
Contributor

oli-obk commented Aug 13, 2020

I think the only place we can store it reasonably is in the mir::Body

@RalfJung
Copy link
Member Author

Turns out we have yet another huge problem with promotion caused by their "design" (if you want to call it that) never having been written down and discussed at a high level.

@ecstatic-morse
Copy link
Contributor

When a CTFE query fails, that's a hard error.

A bit off-topic, but this can't hold in general due to the const-propagation transform. Maybe you just mean for CompileTimeInterpreter and not ConstPropMachine?

@RalfJung
Copy link
Member Author

Ah sure, ConstProp can just bail out and be like "I'm not touching this" on errors, that's fair.

(Though if all consts reaching codegen must successfully evaluate, I think the only bad consts ConstProp might encounter are promoteds in explicit promotion context in dead code.)

@RalfJung

This comment has been minimized.

@RalfJung
Copy link
Member Author

RalfJung commented Aug 14, 2020

Actually ConstProp should be easy -- we just make TooGeneric not emit hard error, and instead propagate that to the caller of the query. That should be the only error ConstProp ever encounters that can be ignored. If it doesn't get TooGeneric, then codegen would have gotten the exact same result, so it is okay for this query to emit a hard error.

The only exception of course are const/static bodies, as they are not codegen'd. We can just not ConstProp them either... though we have some lints in ConstProp that we would miss then. Well, this is another argument for not doing promotion for those, but instead doing lifetime extension the old way (StorageDead removal).

@RalfJung
Copy link
Member Author

I have collected my current thoughts on this in a hackmd. Please feel free to expand that with missing information!

@ecstatic-morse
Copy link
Contributor

Removing StorageDead as a substitute for promotion does not work once you can loop in a const initializer. It results in multiple StorageLives for the same MIR local with no corresponding StorageDead. You could hoist temporaries that are eligible for lifetime extension out of the loop, but at some point you're just reimplementing promotion.

const _: () = {
    loop {
        let _x: &'static i32 = &5;
    }
}

@RalfJung
Copy link
Member Author

RalfJung commented Aug 15, 2020

@ecstatic-morse that's a good point, dang.

So, uh, what can we do? I don't suppose there is any hope of restricting lifetime extension in const/static bodies to just infallible code? The only other way then to still achieve "all CTFE failures are hard errors" is to make sure we only evaluate lifetime extended promoteds that we actually need -- doing it on-demand instead of eagerly. This affects MIR optimizations, they must be careful not to trigger evaluation of these promoteds.

Also, doesn't this entirely break promotion of mutable data? What if we have &mut [1,2,3] in a loop? I'll try to craft something. EDIT: rust-lang/rust#75556


@lcnr, thanks for your comment! However, I don't think hacmd makes any sense for discussion, it only makes sense for documenting the result of a discussion. So let me move your comment here:

From what I can tell we already have generic promoteds in associated constants: playground
So we can't just always eagerly evaluate promoteds...
I think requiring constants to be eagerly evaluated seems slightly inconsistent considering how we deal with generic constants.
(note: I really would have to spend a few more hours looking into this to form a more complete opinion here)

However, the example you give has nothing to do with promotion. See the Vec::new example. Also, the lazy/eager evaluation I am talking about has nothing to do with lazy/eager normalization of const generics. I am talking about the case where you have a fully monomorphic const body that you want to evaluate, and in some dead code it contains a rustc_required_const argument. If this was runtime code, we'd still evaluate that argument because it has to happen during codegen. For CTFE we could in principle decide to only evaluate such arguments on-demand when they are in live code.

In the light of what @ecstatic-morse noted, since we have to evaluate lifetime extension promoteds lazily in const/static bodies, we might as well do the same with other promoteds...


@oli-obk same for your comment

These are codegen’d, so we have to evaluate all promoteds, even in dead code.

do we have to even in dead code? I thought we want to, but theoretically we can just remove dead code during mir optimizations.

Yes we have to. It is impossible to determine all dead code -- see "halting problem". We could remove some dead code, but then we get an inconsistent mess, not a better system.

(Btw hackmd also has a dedicated comment mechanism, we could also try that. But then we'd have two threads of discussion and I do not know if hackmd sends out any notifications. Either way, using a free-form text editor as a discussion forum is a rather poor substitute IMO.^^)

@lcnr

This comment has been minimized.

@RalfJung

This comment has been minimized.

bors added a commit to rust-lang-ci/rust that referenced this issue Oct 25, 2020
stop promoting union field accesses in 'const'

Turns out that promotion of union field accesses is the only difference between "promotion in `const`/`static` bodies" and "explicit promotion". So if we can remove this, we have finally achieved what I thought to already be the case -- that the bodies of `const`/`static` initializers behave the same as explicit promotion contexts.

The reason we do not want to promote union field accesses is that they can introduce UB, i.e., they can go wrong. We want to [minimize the ways promoteds can fail to evaluate](rust-lang/const-eval#53). Also this change makes things more consistent overall, removing a special case that was added without much consideration (as far as I can tell).

Cc `@rust-lang/wg-const-eval`
@RalfJung
Copy link
Member Author

RalfJung commented May 9, 2021

RFC 3072 got accepted, so most of the rest of the work here is tracked at rust-lang/rust#80619.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants