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 RFC 2342, "Allow `if` and `match` in constants" #49146

Open
Centril opened this issue Mar 18, 2018 · 44 comments

Comments

@Centril
Copy link
Member

commented Mar 18, 2018

This is a tracking issue for the RFC "Allow if and match in constants" (rust-lang/rfcs#2342).

Steps:

Unresolved questions:

None

@oli-obk

This comment has been minimized.

Copy link
Contributor

commented Mar 19, 2018

  1. add a feature gate for it
  2. switch and switchInt terminators in https://github.com/rust-lang/rust/blob/master/src/librustc_mir/transform/qualify_consts.rs#L347 need to have custom code in case the feature gate is active
  3. instead of having a single current basic block (https://github.com/rust-lang/rust/blob/master/src/librustc_mir/transform/qualify_consts.rs#L328) this needs to be some container that has a list of basic blocks it still has to process.
@eddyb

This comment has been minimized.

Copy link
Member

commented Mar 19, 2018

@oli-obk It's a bit trickier because the complex control-flow means dataflow analysis needs to be employed. I need to get back to @alexreg and figure out how to integrate their changes.

@alexreg

This comment has been minimized.

Copy link
Contributor

commented Mar 19, 2018

@eddyb A good starting point would probably be to take my const-qualif branch (minus the top commit), rebase it over master (not going to be fun), and then add data annotation stuff, right?

@mark-i-m

This comment has been minimized.

Copy link
Member

commented Apr 25, 2018

Any news on this?

@alexreg

This comment has been minimized.

Copy link
Contributor

commented Apr 26, 2018

@mark-i-m Alas no. I think @eddyb has been very busy indeed, because I've not even been able to ping him on IRC for the last few weeks hah. Sadly my const-qualif branch doesn't even compile since I last rebased it over master. (I don't believe I've pushed yet though.)

thread 'main' panicked at 'assertion failed: position <= slice.len()', libserialize/leb128.rs:97:1
note: Run with `RUST_BACKTRACE=1` for a backtrace.
error: Could not compile `rustc_llvm`.

Caused by:
  process didn't exit successfully: `/Users/alex/Software/rust/build/bootstrap/debug/rustc --crate-name build_script_build librustc_llvm/build.rs --error-format json --crate-type bin --emit=dep-info,link -C opt-level=2 -C metadata=74f2a810ad96be1d -C extra-filename=-74f2a810ad96be1d --out-dir /Users/alex/Software/rust/build/x86_64-apple-darwin/stage1-rustc/release/build/rustc_llvm-74f2a810ad96be1d -L dependency=/Users/alex/Software/rust/build/x86_64-apple-darwin/stage1-rustc/release/deps --extern build_helper=/Users/alex/Software/rust/build/x86_64-apple-darwin/stage1-rustc/release/deps/libbuild_helper-89aaac40d3077cd7.rlib --extern cc=/Users/alex/Software/rust/build/x86_64-apple-darwin/stage1-rustc/release/deps/libcc-ead7d4af4a69e776.rlib` (exit code: 101)
warning: build failed, waiting for other jobs to finish...
error: build failed
command did not execute successfully: "/Users/alex/Software/rust/build/x86_64-apple-darwin/stage0/bin/cargo" "build" "--target" "x86_64-apple-darwin" "-j" "8" "--release" "--manifest-path" "/Users/alex/Software/rust/src/librustc_trans/Cargo.toml" "--features" " jemalloc" "--message-format" "json"
expected success, got: exit code: 101
thread 'main' panicked at 'cargo must succeed', bootstrap/compile.rs:1085:9
note: Run with `RUST_BACKTRACE=1` for a backtrace.
failed to run: /Users/alex/Software/rust/build/bootstrap/debug/bootstrap -i build
@alexreg

This comment has been minimized.

Copy link
Contributor

commented Apr 26, 2018

Okay, funnily enough, I rebased again just today and it seems to be building all fine now! Looks like there was a regression, and it just got fixed. All over to @eddyb now.

@eddyb

This comment has been minimized.

Copy link
Member

commented Apr 26, 2018

@alexreg Sorry, I've switched to a local sleep schedule and I see you've pinged me when I wake up but then you're offline all day when I'm awake (ugh timezones).
Should I just make a PR out of your branch? I forgot what we were supposed to do with it?

@alexreg

This comment has been minimized.

Copy link
Contributor

commented Apr 26, 2018

@eddyb That's alright heh. You must be off to bed early, since I'm usually on from 8:00PM GMT, but it's all good! :-)

kennytm added a commit to kennytm/rust that referenced this issue Apr 30, 2018
Make `Vec::new` a `const fn`

`RawVec::empty/_in` are a hack. They're there because `if size_of::<T> == 0 { !0 } else { 0 }` is not allowed in `const` yet. However, because `RawVec` is unstable, the `empty/empty_in` constructors can be removed when rust-lang#49146 is done...
@eddyb

This comment has been minimized.

Copy link
Member

commented May 4, 2018

I'm really sorry, took me a while to realize that the series of patches in question requires removing Qualif::STATIC{,_REF}, i.e. the errors about accessing statics at compile-time. OTOH, this is already broken in terms of const fns and access to statics:

#![feature(const_fn)]
const fn read<T: Copy>(x: &T) -> T { *x }
static FOO: u32 = read(&BAR);
static BAR: u32 = 5;
fn main() {
    println!("{}", FOO);
}

This is not detected statically, instead miri complains that "dangling pointer was dereferenced" (which should really say something about statics instead of "dangling pointer").

So I think reading statics at compile-time should be fine, but some people want const fn to be "pure" (i.e. "referentially transparent" or thereabouts) at runtime, which would mean that a const fn reading from behind a reference it got as an argument is fine, but a const fn should never be able to obtain a reference to a static out of thin air (including from consts).

I think then we can keep statically denying mentioning statics (even if only to take their reference) in consts, const fn, and other constant contexts (including promoteds).
But we still have to remove the STATIC_REF hack which allows statics to take the reference of other statics but (poorly tries and fails to) deny reading from behind those references.

Do we need an RFC for this?

@alexreg

This comment has been minimized.

Copy link
Contributor

commented May 4, 2018

Sounds fair w.r.t. reading from statics. Doubt it needs an RFC, maybe just a crater run, but then I’m probably not the best one to say.

@eddyb

This comment has been minimized.

Copy link
Member

commented May 4, 2018

Note that we wouldn't be restricting anything, we'd be relaxing a restriction that's already broken.

@alexreg

This comment has been minimized.

Copy link
Contributor

commented May 4, 2018

Oh, I misread. So const evaluation would still be sound, just not referentially transparent?

@eddyb

This comment has been minimized.

Copy link
Member

commented May 4, 2018

The last paragraph describes a referentially transparent approach (but we lose that property if we start allowing mentioning statics in consts and const fns). I don't think soundness was really under discussion.

@alexreg

This comment has been minimized.

Copy link
Contributor

commented May 4, 2018

Well, "dangling pointer" sure sounds like a soundness issue, but I'll trust you on this!

@eddyb

This comment has been minimized.

Copy link
Member

commented May 4, 2018

"dangling pointer" is a bad error message, that's just miri forbidding reading from statics. The only constant contexts that can even refer to statics are other statics, so we could "just" allow those reads, since all of that code always runs once, at compile-time.

(from IRC) To summarize, referentially transparent const fn could only ever reach frozen allocations, without going through arguments, which means const needs the same restriction, and non-frozen allocations can only come from statics.

@Centril

This comment has been minimized.

Copy link
Member Author

commented May 4, 2018

I do like preserving referential transparency so @eddyb's idea sounds fantastic!

@alexreg

This comment has been minimized.

Copy link
Contributor

commented May 4, 2018

Yeah I’m pro making const fns pure as well.

@eddyb

This comment has been minimized.

Copy link
Member

commented May 4, 2018

Please note that certain seemingly harmless plans could ruin referential transparency, e.g.:

let x = 0;
let non_deterministic = &x as *const _ as usize;
if non_deterministic.count_ones() % 2 == 0 {
    // do one thing
} else {
    // do a completely different thing
}

This would fail with a miri error at compile-time, but would be non-deterministic at runtime (because we can't mark that memory address as "abstract" like miri can).

EDIT: @Centril had the idea of making certain raw pointer operations (such as comparisons and casts to integers) unsafe within const fn (which we can do up until we stabilize const fn), and state that they can only be used in ways that miri would allow at compile-time.
For example, subtracting two pointers into the same local should be fine (you get a relative distance that only depends on the type layout, array indices, etc.), but formatting the address of a reference (via {:p}) is an incorrect use and therefore fmt::Pointer::fmt can't be marked const fn.
Also none of the Ord / Eq trait impls for raw pointers can be marked as const (whenever we get the ability to annotate them as such), because they're safe but the operation is unsafe in const fn.

@alexreg

This comment has been minimized.

Copy link
Contributor

commented May 4, 2018

Depends what you mean by "harmless"... I can certainly see reason we'd want to ban such non-deterministic behaviour.

@eddyb eddyb referenced this issue May 4, 2018
3 of 3 tasks complete
bors added a commit that referenced this issue May 8, 2018
lint: deny incoherent_fundamental_impls by default

Warn the ecosystem of the pending intent-to-disallow in #49799.

There are 4 ICEs on my machine, look unrelated (having happened before in #49146 (comment))

```rust
thread 'main' panicked at 'assertion failed: position <= slice.len()', libserialize/leb128.rs:97:1
```

```
    [run-pass] run-pass/allocator/xcrate-use2.rs
    [run-pass] run-pass/issue-12133-3.rs
    [run-pass] run-pass/issue-32518.rs
    [run-pass] run-pass/trait-default-method-xc-2.rs
```

r? @nikomatsakis
@lachlansneff

This comment has been minimized.

Copy link

commented Jun 18, 2018

It would be fantastic if work were continued on this.

@alexreg

This comment has been minimized.

Copy link
Contributor

commented Feb 1, 2019

@mark-i-m It's blocked on implementing proper dataflow analysis for const qualification. @eddyb is the most knowledgeable in this area, and he had previously done some work on this. (So had I, but that sort of stagnated...) If @eddyb still doesn't have time, perhaps @oli-obk or @RalfJung could tackle this at some point soon. :-)

@eddyb

This comment has been minimized.

Copy link
Member

commented Feb 14, 2019

#58403 is a small step towards dataflow-based qualification.

@jyn514

This comment has been minimized.

Copy link

commented Apr 24, 2019

@eddyb you mentioned preserving referential transparency in const fn, which I think is a good idea. What if you prevented using pointers in const fn? So your previous code sample would no longer compile:

let x = 0;
// compile time error: cannot cast reference to pointer in `const fun`
let non_deterministic = &x as *const _ as usize;
if non_deterministic.count_ones() % 2 == 0 {
    // do one thing
} else {
    // do a completely different thing
}

References would still be allowed but you wouldn't be allowed to introspect them:

let x = 0;
let p = &x;
if *p != 0 {  // this is fine
    // do one thing
} else {
    // do a completely different thing
}

Let me know if I'm completely off base, I just thought this would be a good way to make this deterministic.

@oli-obk

This comment has been minimized.

Copy link
Contributor

commented Apr 24, 2019

@jyn514 that is already covered by making as usize casts unstable (#51910), but users can also compare raw pointers (#53020) which is just as bad and thus also unstable. We can handle these independently of control flow.

@mark-i-m

This comment has been minimized.

Copy link
Member

commented Jul 25, 2019

Any new on this?

@oli-obk

This comment has been minimized.

@est31

This comment has been minimized.

Copy link
Contributor

commented Jul 31, 2019

@oli-obk your link doesn't work. What does it say?

@alexreg

This comment has been minimized.

Copy link
Contributor

commented Aug 1, 2019

It works for me... you've got to sign into Zulip though.

@est31

This comment has been minimized.

Copy link
Contributor

commented Aug 1, 2019

@alexreg hmm yeah I presume it was about the dataflow based const qualification work. @alexreg do you know why it's needed for if and match in constants?

@oli-obk

This comment has been minimized.

Copy link
Contributor

commented Aug 1, 2019

if we don't have a dataflow based version we either accidentally allow &Cell<T> inside constants or accidentally forbid None::<&Cell<T>> (which works on stable. It's essentially impossible to implement properly without dataflow (or any implementation will be a bad broken ad-hoc version of dataflow)

@alexreg

This comment has been minimized.

Copy link
Contributor

commented Aug 1, 2019

@est31 Well, @oli-obk understands this much better than me, but from a high-level basically anything involving branching is going to predicate dataflow analysis unless you want a bunch of edge cases. Anyway, it seems like this person on Zulip is trying to work on it, and if not I know oli-obk and eddyb have intentions to, maybe this month or next (from when I last spoke to them about it), though I can't/won't make promises on their behalf.

@ecstatic-morse

This comment has been minimized.

Copy link
Contributor

commented Aug 19, 2019

@alexreg @mark-i-m @est31 @oli-obk I should be able to publish my WIP implementation of dataflow-based const qualification sometime this week. There are a lot of compatibility hazards here, so it may take a while to actually merge it.

@alexreg

This comment has been minimized.

Copy link
Contributor

commented Aug 19, 2019

Super; look forward to it.

@jhpratt

This comment has been minimized.

Copy link

commented Sep 23, 2019

(copying from #57563 per request)

Would it be possible to special-case bool && bool, bool || bool, etc.? They can currently be performed in a const fn, but doing so requires bitwise operators, which is sometimes unwanted.

@RalfJung

This comment has been minimized.

Copy link
Member

commented Sep 23, 2019

They are already special-cased in const and static items -- by translating them to bitwise operations. But that special-casing is a huge hack and it is very hard to make sure that this is actually correct. As you said, it is also sometimes unwanted. So we'd rather not do this more often.

Doing things right will take a bit, but it'll happen. If we pile on too many hacks in the mean time, we might pain ourselves into a corner that we cannot get out of (if some of those hacks end up interacting in wrong ways, thus accidentally stabilizing behavior we do not want).

Centril added a commit to Centril/rust that referenced this issue Sep 24, 2019
…i-obk

Add a cycle detector for generic `Graph`s and `mir::Body`s

Cycle detection is one way to differentiate the upcoming `const_loop` feature flag (rust-lang#52000) from the `const_if_match` one (rust-lang#49146). It would be possible to use the existing implementation of strongly-connected components for this but less efficient.

The ["tri-color" terminology](http://www.cs.cornell.edu/courses/cs2112/2012sp/lectures/lec24/lec24-12sp.html) is common in introductory data structures and algorithms courses: black nodes are settled, grey nodes are visited, and white nodes have no state. This particular implementation is iterative and uses a well-known technique where "node settled" events are kept on the stack alongside nodes to visit. When a settled event is popped, we know that all successors of that node have been visited and themselves settled. If we encounter a successor node that has been visited (is on the stack) but not yet settled, we have found a cycle.

r? @eddyb
Centril added a commit to Centril/rust that referenced this issue Sep 24, 2019
…i-obk

Add a cycle detector for generic `Graph`s and `mir::Body`s

Cycle detection is one way to differentiate the upcoming `const_loop` feature flag (rust-lang#52000) from the `const_if_match` one (rust-lang#49146). It would be possible to use the existing implementation of strongly-connected components for this but less efficient.

The ["tri-color" terminology](http://www.cs.cornell.edu/courses/cs2112/2012sp/lectures/lec24/lec24-12sp.html) is common in introductory data structures and algorithms courses: black nodes are settled, grey nodes are visited, and white nodes have no state. This particular implementation is iterative and uses a well-known technique where "node settled" events are kept on the stack alongside nodes to visit. When a settled event is popped, we know that all successors of that node have been visited and themselves settled. If we encounter a successor node that has been visited (is on the stack) but not yet settled, we have found a cycle.

r? @eddyb
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
You can’t perform that action at this time.