[NLL] false edges on infinite loops

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.

@mikhail-m1

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".

@davidtwco

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

cc nll folks:

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

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.

@Pulkit07

@Pulkit07 nice :)

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.

@Pulkit07

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

@nikomatsakis

@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.

@Pulkit07

@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

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

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
}

@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.

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.

mir: Add false edge cleanup out of infinite loops

Auto merge of #47802 - bobtwinkles:loop_false_edge, r=nikomatsakis

Rollup merge of rust-lang#81387 - c410-f3r:tests-tests-tests, r=petro…

Navigation Menu

Repository navigation

[NLL] false edges on infinite loops #46036

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	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()
	}

	/// 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)
	}

[NLL] false edges on infinite loops #46036

Description

Activity

nikomatsakis commented on Jan 17, 2018

nikomatsakis commented on Jan 17, 2018

Pulkit07 commented on Jan 17, 2018

nikomatsakis commented on Jan 18, 2018

Pulkit07 commented on Jan 18, 2018

nikomatsakis commented on Jan 18, 2018

Pulkit07 commented on Jan 19, 2018

nikomatsakis commented on Jan 19, 2018

nikomatsakis commented on Jan 19, 2018

sapphire-arches commented on Jan 23, 2018

nikomatsakis commented on Jan 24, 2018

nikomatsakis commented on Jan 26, 2018

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions