rustc infinite loop: warning: Constant evaluating a complex constant, this might take some time

[vegard]

Not sure if this is really a bug, but I tried searching and couldn't find any hits on the warning message. Feel free to close the issue if this is intended/expected behaviour.

Input:

fn main() {
    [(); loop {}]
}

Output:

$ rustc -
error[E0019]: constant contains unimplemented expression type
 --> <anon>:2:10
  |
2 |     [(); loop {}]
  |          ^^^^^^^

warning: Constant evaluating a complex constant, this might take some time
 --> <anon>:2:10
  |
2 |     [(); loop {}]
  |          ^^^^^^^

At this point the rustc process hangs seemingly forever while consuming 100% CPU.

I'm on commit c166b03.

[scottmcm]

This was decided in general over in rust-lang/rfcs#2344 (comment)

@oli-obk Would be be feasible to catch some simple cases of "this definitely won't finish"?

[porglezomp]

Existing control-flow analysis gives a warning about unreachable code following a loop {}, I'm not sure if that same analysis is present in the constant evaluator but those cases seems like the "definitely won't finish" cases.

[oli-obk]

uuuuh... Reaching that warning is a bug in my book. The first error should have cause this expression from never being evaluated.

That said,

Would be be feasible to catch some simple cases of "this definitely won't finish"?

Oh yea, there's a super easy trick for doing that. The moment we emit the warning, we hash the state of the const evaluator and place it into a HashSet. Then, every (n?) step(s) from then on, we do the same. If we ever encounter the same hash again, we're 100% in an infinite loop, because const eval is deterministic and thus reaching the same state will mean we'll just reach it again soonish.

[nikomatsakis]

Definitely a bug. Not P-high, but we ought to fix. Marking as P-medium. My ideal scenario here is that @oli-obk writes up mentoring instructions and adds the appropriate labels, because this seems like a nice bug for someone looking to learn something about miri.

[oli-obk]

As a first step, we should implement #49980, which turns the unconditional warning into a lint.

Then, in order to actually detect true recursions and abort for them:

• https://github.com/rust-lang/rust/blob/master/src/librustc_mir/interpret/step.rs#L15 is where all the action should be happening
• We can probably get away with just hashing the memory object (https://github.com/rust-lang/rust/blob/master/src/librustc_mir/interpret/eval_context.rs#L37) and the stack object (https://github.com/rust-lang/rust/blob/master/src/librustc_mir/interpret/eval_context.rs#L40).
• deriving hash for the relevant types probably won't work, because there are HashMaps inside (https://github.com/rust-lang/rust/blob/master/src/librustc_mir/interpret/memory.rs#L40)
  • A manual implementation would need to hash the length and then store all (&key, &value) tuples in a Vec and sort them by the key. This should be as simple as let v: Vec<_> = map.iter().collect(); v.sort_by_key(|(a, _)| a);
• Place the resulting hash into a FxHashSet.
• If the hash already existed in the FxHashSet, we have found a possible loop. It's not necessarily a loop, as the hashes could have collisions. So we now need to figure out whether this was an actual collision.
  • clone the memory and stack objects
  • place them into another FxHashSet
  • if there's a collision in the second FxHashSet, then we are apparently in an infinite loop
  • create a new error variant for that case, and report that error right here

This will take riddiculous amounts of memory and computation time, but since we only start doing this once we hit a certain counter limit, this should be fine. If not, we can just increase the limit.

Once we have hit the limit we also need to set a flag so while we will now do the hashing at every step, the lint should only show up every 1M steps (or whatever the setting is).