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 2344, "Allow `loop` in constant evaluation" #52000

Open
Centril opened this issue Jul 2, 2018 · 22 comments

Comments

Projects
None yet
9 participants
@Centril
Copy link
Contributor

commented Jul 2, 2018

This is a tracking issue for the RFC "Allow loop in constant evaluation" (rust-lang/rfcs#2344).

Steps:

Unresolved questions:

  • Should we add a true recursion check that hashes the interpreter state and detects if it has reached the same state again?
    • This will slow down const evaluation enormously and for complex iterations is essentially useless because it'll take forever (e.g. counting from 0 to u64::max_value())
@brunocodutra

This comment has been minimized.

Copy link
Contributor

commented Jul 21, 2018

This feature seems simple enough for me to tackle as my first attempt to contribute to rust, at least getting it to work appears to be as simple as removing the check against loops in constant functions.

I believe the real work actually goes into implementing the lint for potential infinite loops. I'm going to tackle this next and I'd really appreciate some mentorship along the way.

@oli-obk

This comment has been minimized.

Copy link
Contributor

commented Jul 21, 2018

Implementing this feature is blocked on a bunch of definitely not beginner level things. But there's ongoing preliminary work happening, so this isn't standing still even if nothing happens on the issue.

If we'd just remove the check against loops, we'd end up with amusingly broken code, because most of the const checking code only knows it needs to prevent writing multiple times to a variable... which loops can do without naming the variable twice.

Anyway, guarding against infinite loops has been partially implemented, and if you're interested in doing some work there, we're tracking one of the issues in #52475

@brunocodutra

This comment has been minimized.

Copy link
Contributor

commented Jul 21, 2018

Thanks for pointing me to the right direction, I'll definitely have a look for something I can help with.

@jkarns275

This comment has been minimized.

Copy link

commented Aug 23, 2018

Would an iteration limit be an acceptable solution to the the infinite loop problem? If the iteration limit is actually reached the code can just be compiled instead!

Though this may be deceptive since the const fns wouldn't really be const if the limit is reached.

@estebank

This comment has been minimized.

Copy link
Contributor

commented Aug 23, 2018

Though this may be deceptive since the const fns wouldn't really be const if the limit is reached.

It could be a compilation error, which would let the const fn continue to be const (code that fails to compile has no bearing in execution time ^_^).

@jkarns275

This comment has been minimized.

Copy link

commented Aug 23, 2018

True! Perhaps it would be worth adding a compilation option of some sort that would make it just a warning for edge cases.
Edit: reading this half a year later and i have no idea what i meant

@nikomatsakis nikomatsakis referenced this issue Dec 31, 2018

Closed

const fn tracking issue (RFC 911) #24111

3 of 3 tasks complete

@Lokathor Lokathor referenced this issue Jan 13, 2019

Open

Meta tracking issue for `const fn` #57563

0 of 15 tasks complete
@BatmanAoD

This comment has been minimized.

Copy link

commented Jan 24, 2019

@oli-obk

const checking code only knows it needs to prevent writing multiple times to a variable...

....sorry, I thought that compile-time evaluated code is run by MIRI; why would it matter whether a variable is written to multiple times?

Of course, any (useful) compile-time evaluation is ultimately going to result in static data in the resulting executable, so it makes sense for const values not to be written to multiple times. But shouldn't that already be guaranteed by mutability rules?

@BatmanAoD

This comment has been minimized.

Copy link

commented Jan 24, 2019

Additionally, if the Iter trait were to be stabilized for use in const fn contexts, I think an entirely reasonable resolution to this issue would be to enable only loops that rely on Iter. This would permit many simple obviously-terminating loops (the most obvious example being those iterating over range-literals), while limiting the potential for unbounded compiler execution to problems in the implementation of the iterator used.

An even simpler and forward-compatible solution would be to only permit iteration over range-literals for now.

@BatmanAoD

This comment has been minimized.

Copy link

commented Jan 24, 2019

^ Sorry, I thought this was an RFC PR, not a tracking-issue PR. Since this RFC explicitly states that for loops wouldn't be usable anyway, would it be worth writing a separate RFC about permitting for <var> in <range> in const fn?

@scottmcm

This comment has been minimized.

Copy link
Member

commented Jan 24, 2019

@BatmanAoD My assumption here is that everyone wants to be able to use traits in const fn eventually, and that for will just naturally happen along with that.

@oli-obk

This comment has been minimized.

Copy link
Contributor

commented Jan 24, 2019

sorry, I thought that compile-time evaluated code is run by MIRI; why would it matter whether a variable is written to multiple times?

The const evaluator based on the miri-engine is what actually interprets the MIR and produces the final constant. We have an additional analysis that checks whether your constant only does things we can statically prove to not cause a certain range of errors. E.g. we currently forbid unions and transmuting via this static analysis, even though miri can evaluate them just fine. The same goes for calling trait methods. We want the const evaluator to only evaluate things that we have RFCed. The same thing is true for this issue. It's trivial for miri to evaluate loops, but we don't want to accidentally cause Cell types to end up in static variables, and the current static analyis just doesn't know how to prevent that in the presence of loops.

@BatmanAoD

This comment has been minimized.

Copy link

commented Jan 25, 2019

@oli-obk Okay, I think I understand prohibiting transmuting and unions, since those enable operations that have effects that are invisible to the type system. I don't understand how loops would permit a Cell to be part of a static value, though; wouldn't that be part of the static value's type?

@BatmanAoD

This comment has been minimized.

Copy link

commented Jan 25, 2019

(...or, instead of answering that specific question, feel free to point me to a more general resource I can read in order to ask more intelligent questions...)

@oli-obk

This comment has been minimized.

Copy link
Contributor

commented Jan 25, 2019

feel free to point me to a more general resource I can read in order to ask more intelligent questions

I think we're severely lacking in that place. The closest I can come up with is this issue

Maybe we can kill two birds with one stone: I explain it to you, and you write docs for https://github.com/rust-lang-nursery/reference/blob/master/src/items/static-items.md, https://github.com/rust-lang-nursery/reference/blob/master/src/items/constant-items.md and https://github.com/rust-lang-nursery/reference/blob/master/src/items/associated-items.md#associated-constants

I'll review the docs, and this way we'll notice if I explained it correctly.

There's three components and we'll start with the Cell one:

static FOO: Option<Cell<u32>> = Some(Cell::new(42));

Is not legal, because we'd be able to modify the static without thread synchronization. But on the other hand

static FOO: Option<Cell<u32>> = None;

is perfectly ok, because no Cell actually exists. The same goes for

static FOO: Option<Cell<u32>> = (None, Cell::new(42)).0;

because no Cell ends up in the final constant.

Bringing us to the second point: destructors may not be called at compile-time, because Drop::drop is not a const function. This means that

const FOO: u32 = (SomeDropType, 42).1;

is not legal, because the destructor gets called during the evaluation of the constant. On the other hand

const FOO: SomeDropType = SomeDropType;

is legal, because no destructor gets called during the evaluation of the constant. Any use of it might cause a destructor to be called, but that's not a problem here.

Now we get to the third problem:

trait Bar {
    const BAR: Self;
}
trait Foo<T: Bar> {
    const FOO: u32 = (T::BAR, 42).1;
}

Is problematic exactly if T implements Drop (either manually or due to a field impl-ing Drop), because then the evaluation of FOO would call T::drop. While we could emit an error only when using trait Foo<String> or similar, that is a post-monomorphization error, which we are trying to avoid as much as possible. Post-monomorphization errors are bad, because they mean you can write broken code, and only the users of your crate will notice, not you yourself.

@RalfJung

This comment has been minimized.

Copy link
Member

commented Jan 25, 2019

There's also some material at https://github.com/rust-rfcs/const-eval/

@BatmanAoD

This comment has been minimized.

Copy link

commented Jan 25, 2019

@oli-obk I would definitely be up for writing some docs!

I'm still not clear on whether there's actually a problem with Cell, though. In current, stable Rust (and, as it happens, on Nightly), the static _: Option<Cell<_>> = None declaration you've shown is not legal: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=6e3f727044df4a298ab5681ba9a1a425

...so, is there a compelling reason why we would want that to be legal, even as const fn support grows?

For the second/third problem, I don't understand how const values that don't implement Copy can be used by-value at all, but clearly that is already legal in stable Rust, and in fact such a value can even be re-used multiple times: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=7a580a901449868e7b0ab9434a492a8d

In any case, when compiling a trait definition, pre-monomorphization, can the compiler determine where drop calls would be inserted? If so, perhaps const fn simply shouldn't be able to use any types that aren't copy except by reference? (Not knowing hardly anything about the compiler internals: does this sound like an overly complex check?)

@mark-i-m

This comment has been minimized.

Copy link
Contributor

commented Jan 25, 2019

For the second/third problem, I don't understand how const values that don't implement Copy can be used by-value at all, but clearly that is already legal in stable Rust, and in fact such a value can even be re-used multiple times

const values are inlined at compile-time. There is no copying going on at runtime. The compiled binary contains an instance of constant for every usage.

@oli-obk

This comment has been minimized.

Copy link
Contributor

commented Jan 25, 2019

I'm still not clear on whether there's actually a problem with Cell, though. In current, stable Rust (and, as it happens, on Nightly), the static : Option<Cell<>> = None declaration you've shown is not legal:

Oh oops, well, replace static with const and add some indirection: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=79d9f50e2d50294ffc10f6f9bf5867f6

This also relates to your question about Copy. Things are copied bitwise at compile-time. So if we bitwise copy a reference, we don't get a new cell, we just get a new reference. So suddenly we could change one use of a constant and other uses would get changed.

In any case, when compiling a trait definition, pre-monomorphization, can the compiler determine where drop calls would be inserted? If so, perhaps const fn simply shouldn't be able to use any types that aren't copy except by reference? (Not knowing hardly anything about the compiler internals: does this sound like an overly complex check?)

Well... const fn are a separate beast. You can't have any Drop calls inside a const function anyway right now. At least not until we get impl const Drop for SomeType, but a type with impl const Drop is totally fine to drop in a constant, so we're fine. The check will stay for types that just have impl Drop

@BatmanAoD

This comment has been minimized.

Copy link

commented Jan 28, 2019

Ah, okay, that definitely helped me understand both the Cell issue and how const values actually work. (I'm sure I understood the distinction between const and immutable static values at some point, but I entirely forgot that const data is inlined.

Re: Cell, it looks like the compiler currently won't attempt compile-time analysis of a const fn to determine whether or not it contains a problematic value: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=6243cab09e8dadd35c435d65a299adf1

....so can we just keep that same rule (the code is rejected if a const borrow may contain a Cell) in all const contexts? I.e.:

const SOME_REF: &Option<Cell<i32>> = &{
    if /* some complicated logic */ {
        None
    } else {
        Some(Cell::new(7))
    }
};

...would be rejected before attempting to execute /* some complicated logic */ (be it a function call or something involving a loop), simply because the resulting value is of a type that may be invalid. The simple version you showed above, = &None, would be the only valid initialization expression for a const Option<Cell<_>>.

As an aside: I cannot fathom how a const type containing a Cell would ever be useful, except in pattern-matching. Do we intend to provide const-evaluation support inside patterns? That seems...overly complicated.

Re: Drop and monomorphization,

trait Bar {
    const BAR: Self;
}
trait Foo<T: Bar> {
    const FOO: u32 = (T::BAR, 42).1;      // Doesn't this imply either `T: const Drop` or `T: !Drop`?
}

It seems that Foo requires that T either impl const Drop or not impl Drop at all, but the author of Foo doesn't necessarily care which is true. Could the compiler simply reject any such traits (with potential drop calls in const contexts) unless the author specifies one of T: Copy or T: const Drop? Or, more generically, we could automatically derive const Drop (as we automatically derive Sized) for types that don't implement Drop? If that's not permissible, perhaps a new marker trait could be introduce to indicate "this type can be dropped in a const context", and that could be automatically derived?

@oli-obk

This comment has been minimized.

Copy link
Contributor

commented Jan 29, 2019

so can we just keep that same rule (the code is rejected if a const borrow may contain a Cell) in all const contexts?

Seems a sensible precaution, but I also think that this will make ppl uncomfortable (similar to how if 3 < 2 { [42, 43][3]; } triggers an array index out of bounds error). We can lift the limitation further in the future backwards compatibly though, so it's not an issue

As an aside: I cannot fathom how a const type containing a Cell would ever be useful, except in pattern-matching. Do we intend to provide const-evaluation support inside patterns? That seems...overly complicated.

Well, you can use constants to initialize statics, and you might want to do some computation at compile-time, and that computation might want to memoize values to speed up an algorithm. The final result should still not contain a Cell.

Could the compiler simply reject any such traits (with potential drop calls in const contexts) unless the author specifies one of T: Copy or T: const Drop?

That's essentially what we're doing right now I think?

Or, more generically, we could automatically derive const Drop (as we automatically derive Sized) for types that don't implement Drop?

This is something we definitely should do. I mean fn foo<T: Drop>(_: T) {} works with foo(42i32) just fine, so this already exists to some extend, we'll just need to figure out how to handle the const part.

@BatmanAoD

This comment has been minimized.

Copy link

commented Apr 25, 2019

@oli-obk Sorry for the long absence. I'm still up for writing some docs, although at the moment I'm still not sure exactly what needs to be written.

Could the compiler simply reject any such traits (with potential drop calls in const contexts) unless the author specifies one of T: Copy or T: const Drop?

That's essentially what we're doing right now I think?

If that's the case, then doesn't that solve the "third problem" you described above, regarding dropping T during const evaluation?

trait Bar {
    const BAR: Self;
}
trait Foo<T: Bar> {
    const FOO: u32 = (T::BAR, 42).1;
}
@oli-obk

This comment has been minimized.

Copy link
Contributor

commented Apr 26, 2019

This "problem" is solved by rejecting the above code. It's not so much a problem of the source, but of the analysis. The analysis needs to figure out which things are dropped and have a Drop::drop impl. Introducing loops will make this problem impossible to solve in the general case (because of the halting problem). We can introduce a pessimistic analysis that knows a bunch of cases and keeps erroring where it isn't sure. The system for such an analysis exists, but we haven't implemented it for checking constants yet.

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