[NLL] false edges on infinite loops

[nikomatsakis]

The NLL RFC specifies false edges on infinite loops, so that we get errors in some cases. This is a somewhat disputed clause (see nikomatsakis/nll-rfc#35) that we may change, but it makes sense for now. I'm filing this so we don't forget about it.

[nikomatsakis]

So @mikhail-m1 added the notion of "false edges" in #45384. This seems to be roughly what is needed here. We would want to edit the code that generates a loop construct:

rust/src/librustc_mir/build/expr/into.rs

Lines 149 to 204 in 3e49ada

	ExprKind::Loop { condition: opt_cond_expr, body } => {
	// [block] --> [loop_block] ~~> [loop_block_end] -1-> [exit_block]
	// ^ |
	// | 0
	// | |
	// | v
	// [body_block_end] <~~~ [body_block]
	//
	// If `opt_cond_expr` is `None`, then the graph is somewhat simplified:
	//
	// [block] --> [loop_block / body_block ] ~~> [body_block_end] [exit_block]
	// ^ |
	// | |
	// +--------------------------+
	//
	let loop_block = this.cfg.start_new_block();
	let exit_block = this.cfg.start_new_block();
	// start the loop
	this.cfg.terminate(block, source_info,
	TerminatorKind::Goto { target: loop_block });
	this.in_breakable_scope(
	Some(loop_block), exit_block, destination.clone(),
	move |this| {
	// conduct the test, if necessary
	let body_block;
	if let Some(cond_expr) = opt_cond_expr {
	let loop_block_end;
	let cond = unpack!(
	loop_block_end = this.as_local_operand(loop_block, cond_expr));
	body_block = this.cfg.start_new_block();
	let term = TerminatorKind::if_(this.hir.tcx(), cond,
	body_block, exit_block);
	this.cfg.terminate(loop_block_end, source_info, term);
	// if the test is false, there's no `break` to assign `destination`, so
	// we have to do it; this overwrites any `break`-assigned value but it's
	// always `()` anyway
	this.cfg.push_assign_unit(exit_block, source_info, destination);
	} else {
	body_block = loop_block;
	}
	// The “return” value of the loop body must always be an unit. We therefore
	// introduce a unit temporary as the destination for the loop body.
	let tmp = this.get_unit_temp();
	// Execute the body, branching back to the test.
	let body_block_end = unpack!(this.into(&tmp, body_block, body));
	this.cfg.terminate(body_block_end, source_info,
	TerminatorKind::Goto { target: loop_block });
	}
	);
	exit_block.unit()
	}

and modify the graph in the case where condition is None:

rust/src/librustc_mir/build/expr/into.rs

Line 191 in 3e49ada

body_block = loop_block;

so that we create a FalseEdges that "breaks out".

[nikomatsakis]

Added some mentoring instructions to this NLL issue. Can elaborate as needed!

cc nll folks:

@davidtwco
@chrisvittal
@pnkfelix
@spastorino
@Nashenas88
@gaurikholkar
@qmx
@Pulkit07
@ritiek

[Pulkit07]

I am trying to fix this one. I have already a kind of patch ready, need to dump MIR and see if it's doing the right thing.

[nikomatsakis]

@Pulkit07 nice :)

[Pulkit07]

This might take some time, I getting core dumped error, I need to learn about what's happening before moving things here and there. If this is required to be fixed urgently, I am good with someone else fixing it.

[nikomatsakis]

@Pulkit07 woah, core dumped?! When do you get the error, when bootstrapping?

[Pulkit07]

@nikomatsakis I am getting this error when running tests like src/test/run-pass/auto-loop.rs, src/test/run-pass/break.rs and many others.

[nikomatsakis]

@Pulkit07 even if you don't have time to continue working, it'd be helpful if you could post the diff somewhere of how far you got

[nikomatsakis]

From gitter, here is the diff https://bpaste.net/show/ac4eab0ead8e

[sapphire-arches]

So playing with implementing this I've run in to a stumbling block. It seems like TerminatorKind::FalseEdges is mostly intended for use where control flow could sort-of follow the false edge in "normal" execution; the motivating example being things being moved in match arm guards. However in the situation mentioned here, control flow truly follows the false edge in "exceptional" circumstances (panics). The trouble is that there are a number of analysis passes that don't handle this and I'm not sure how to get that knowledge in to them. The first one I've run in to is MIR typeck:

fn oh_no1() -> i32 {
    loop {
         return 1;
    }
    // we abort here since the fake edge means MIR typeck tries to assert that () == i32
    // even though the only way we can get here is if we're unwinding and at that point the
    // return value doesn't matter
}

[nikomatsakis]

@bobtwinkles

Ah, very good point! You are correct that this control flow is supposed to be like a "false unwind".

My instructions were wrong in this respect. We want the false edge not to "break out" but rather to go to an unwinding target. Basically, where we would unwind to, if we were unwinding. The method to get such a block is diverge_cleanup, iirc:

rust/src/librustc_mir/build/scope.rs

Lines 715 to 722 in 3e49ada

	/// Creates a path that performs all required cleanup for unwinding.
	///
	/// This path terminates in Resume. Returns the start of the path.
	/// See module comment for more details. None indicates there’s no
	/// cleanup to do at this point.
	pub fn diverge_cleanup(&mut self) -> BasicBlock {
	self.diverge_cleanup_gen(false)
	}

I'm not sure whether we will have to further modify FalseEdges to distinguish between a "false unwinding" edge and a "false normal" edge. If so, we can probably just add a boolean flag or something like that.

[nikomatsakis]

Here is a test case that @bobtwinkles and I discussed on IRC:

https://play.rust-lang.org/?gist=f9b57ba12faa3e9bc8e4a4d523d58736&version=nightly

Right now, it ICEs, but it also ought to be reporting an error if this is all working correctly.