rustc endless loop on some constant casts

[antifuchs]

I bisected nightlies to figure out when my pull request's tests started breaking on nightly. The following is the template cargo-bisect-rustc gave me.

Regression found in the compiler

searched nightlies: from nightly-2019-10-01 to nightly-2019-12-22
regressed nightly: nightly-2019-11-20
searched commits: from 3e525e3 to 618b01f
regressed commit: d1da802
source code: antifuchs/nonzero_ext#7

Instructions

I tried the following on macOS and linux (in CI):

1. Check out the repo & branch of that pull request
2. Run cargo +nightly test --test=compiletest with a nightly version later than d1da802, that is >= nightly-2019-11-20

Error

The compile test (provided by trybuild) does not terminate - rustc seems to be running forever, consuming 99% of my CPU all the while.

Since the instructions to repro are a bit convoluted (and massive), I'll try and boil down the repro case a little bit.

[antifuchs]

Here's a playground link that better illustrates the failure. It builds with stable, but loops endlessly on nightly: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=eb03f3a6297979be89be032bbb558d38

[antifuchs]

(Never mind that the code is wrong: casting a negative number to usize is pretty messed up and seems to work only by chance; however, having the compiler endless-loop is suboptimal) (:

[antifuchs]

Reduced further to https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=1ca768b40e5cb223899e540c4c5dab4a (:

[oli-obk]

similar "endless" loop: #63952

The problem here is that you have an overflow essentially giving you let _ = [(); usize::max_value()];, which... const prop will then try to turn into a constant

cc @wesleywiser

[oli-obk]

for arrays of zsts we can solve this, but if you used u8 we'd actually need to allocate and do some operations. Maybe we should make mir building for repeat expressions not have its own Rvalue variant but instead just convert [X; N] to MIR of the following form

let mut x = MaybeUninit::<[T; N]>::uninit();
for i in &mut x {
    *x = X;
}
let x = x.assert_initialized();

[wesleywiser]

I thought this might have been fixed by #66394, but because it's a ZST, it doesn't trigger that logic. It would probably be easy to extend that logic to include large arrays of ZSTs.

[oli-obk]

While we could fix this just for const prop, we'd still have the same problem in const eval, so we should consider a general solution.

[RalfJung]

Maybe we should make mir building for repeat expressions not have its own Rvalue variant but instead just convert [X; N] to MIR of the following form

That would solve tons of problems I think. Having a single MIR statement turn into a loop in the interpreter is pretty suboptimal anyway -- usually every statement should have a fixed upper bound on its execution time.

As an interim solution we could probably skip this part for arrays of ZST.

[RalfJung]

Or probably it makes more sense to skip this loop if the size is 0.

[oli-obk]

Or we just make the first line of

rust/src/librustc_mir/interpret/memory.rs

Lines 825 to 832 in a916ac2

	pub fn copy_repeatedly(
	&mut self,
	src: Pointer<M::PointerTag>,
	dest: Pointer<M::PointerTag>,
	size: Size,
	length: u64,
	nonoverlapping: bool,
	) -> InterpResult<'tcx> {

be if size == Size::ZERO || length == 0 { return Ok(()) }

That way we can even remove

rust/src/librustc_mir/interpret/step.rs

Line 208 in a916ac2

if length > 1 {

[RalfJung]

Or we just make the first line of

No, we have to still check those pointers to not be dangling.

[oli-obk]

I thought writes of zsts to dangling pointers is fine?

Though yea, I'm unsure about writing zero elements of non-zsts to a destination.

[RalfJung]

Oh wait, looks like we expect the caller to check that. Hm.

I'd probably bail out after getting src_bytes and dest_bytes, if dest_bytes.is_empty() or so.

[RalfJung]

I thought writes of zsts to dangling pointers is fine?

Not always, no. If the pointer is a Pointer (not an integer), but dangling (out-of-bounds or use-after-free), it's UB even with ZST. Also see this test.

[oli-obk]

Ok, so to any implementor: basically bail out from just before

rust/src/librustc_mir/interpret/memory.rs

Line 849 in a916ac2

// SAFE: The above indexing would have panicked if there weren't at least `size` bytes

if dest_bytes.is_empty() and leave a comment explaining that this is an optimization to not run anything for zsts. You can reference this issue, too.

[wesleywiser]

It looks to me like the compiler is busy validating every () in the array. Bailing out if dest_bytes.is_empty() doesn't seem to make any difference at all. However, if I add a case for

ty::Tuple(t) if t.len() == 0 => true

to this match

rust/src/librustc_mir/interpret/validity.rs

Lines 585 to 588 in a916ac2

	match tys.kind {
	ty::Int(..) | ty::Uint(..) | ty::Float(..) => true,
	_ => false,
	}

then the compilation completes in ~0.2 seconds. I'm not sure that's a valid fix though. Do we actually need to validate every ZST in the array?

[RalfJung]

Well, the ZST could be ! or an empty enum, so we certainly can't skip all ZST.

[wesleywiser]

Ah, yeah that's a great point. I believe ty::Tuple(t) if t.len() == 0 will only match the unit type. Perhaps it's worth including a special case for that?

[oli-obk]

Well... any zst that is not uninhabited can do this early bail out, so I think checking with https://doc.rust-lang.org/nightly/nightly-rustc/rustc/ty/struct.TyCtxt.html#method.is_ty_uninhabited_from_any_module for uninhabitedness and then checking the element's zst-ness would work

[RalfJung]

I wouldn't use !uninhabited as a witness for things to be inhabited... this requires that there is no conservatism at all in the uninhabitedness check. (Also I have no idea what that function does.^^ The implementation talks about... forests?!?)

[antifuchs]

Huh, so. From the behavior I reported in bheisler/criterion.rs#377, it looks like the buggy change made it to 1.41.0 stable, but the fix didn't? My crate's benchmark compilation is currently hanging with what looks like these exact symptoms.