NLL: Improve move error loop detection

[davidtwco]

In #53995, errors were deduplicated and generally this kept errors with the improved "previous iteration of loop" diagnostic:

LL |         while true { while true { while true { x = y; x.clone(); } } }
   |                                                    ^ value moved here in previous iteration of loop

However, in one case, liveness-move-in-while.rs, the remaining error did not have the improved loop diagnostic.

From @nikomatsakis, in a comment from that PR (context mine):

actually, I think this [the diagnostic with loop message being missing] is an improvement — or rather it would be if the previous message mentioned the loop. Basically these seem like duplicate errors. I'm not sure why the "borrow of moved value" doesn't mention the loop, though: it seems like a failure in our loop printing heuristic, which is not very good. I think we ought to be walking from the point of the move forward (but ignoring backedges) — if we encounter the use point, then there is no loop, but otherwise we can say "in previous iteration of loop"... or something like that.

[nikomatsakis]

I'm adding this to "RC 2" list as a "nice to have"

[nikomatsakis]

I think @blitzerr is going to work on this

[nikomatsakis]

Context:

The liveness-move-in-while test from the repository, currently gets this error:

error[E0382]: borrow of moved value: `y`
 --> src/main.rs:8:24
  |
8 |         println!("{}", y); //~ ERROR use of moved value: `y`
  |                        ^ value borrowed here after move
9 |         while true { while true { while true { x = y; x.clone(); } } }
  |                                                    - value moved here
  |
  = note: move occurs because `y` has type `std::boxed::Box<isize>`, which does not implement the `Copy` trait

we would rather add "in previous iteration of loop" to the "value moved here" message:

9 |         while true { while true { while true { x = y; x.clone(); } } }
  |                                                    - value moved here, in previous iteration of loop

This error reporting occurs in this function:

rust/src/librustc_mir/borrow_check/error_reporting.rs

Lines 33 to 39 in f17c230

	pub(super) fn report_use_of_moved_or_uninitialized(
	&mut self,
	context: Context,
	desired_action: InitializationRequiringAction,
	(place, span): (&Place<'tcx>, Span),
	mpi: MovePathIndex,
	) {

The first thing it does is to compute the "move out indices" that may be relevant:

rust/src/librustc_mir/borrow_check/error_reporting.rs

Line 45 in f17c230

let mois = self.get_moved_indexes(context, mpi);

To understand this, you have to understand a bit about the MoveData data structure. There is some introductory material in the rustc-guide. The key part for us is the field moves -- this stores information about each "move" that occurs in the source code. Basically, each place in the source code where something is moved.

In the case of our example, the x = y is a MoveOut of the path y. When we do our search for relevant "move-outs", we are going to walk backwards from the use, looking for all move-outs we find. In this case, we'll find the x = y.

Now, right now, what we do is to iterate over those resulting move-outs:

rust/src/librustc_mir/borrow_check/error_reporting.rs

Line 93 in f17c230

for moi in &mois {

For each of them we issue a "value moved here" label. We sometimes print "in previous iteration of loop", but our heuristic is kind of insufficient. We look for a case where the "use" and the previous move have the same span:

rust/src/librustc_mir/borrow_check/error_reporting.rs

Lines 106 to 111 in f17c230

	if span == move_span {
	err.span_label(
	span,
	format!("value moved{} here in previous iteration of loop", move_msg),
	);
	is_loop_move = true;

This only works when you have something like loop { drop(x); } -- here, the drop(x) from the previous loop iteration is conflicting with the drop(x) with the next iteration. But it doesn't work for a case like this: loop { use(x); drop(x); }, which is what we have in this example.

The right way to detect this case is to look for a "backedge". In compiler terminology, a "backedge" in the control-flow graph is an edge B -> A where A dominates B. Put another way: in order to get to the point B, you have to go through A (because A dominates B), but this edge B->A then lets you get from B back to A. This is basically the definition of a loop.

I think perhaps the easiest thing for us to do, then, is to modify the function get_moved_indexes to watch out for backedges. This function is a little loop that walks all the points reachable from a start location. It keeps a stack that tracks the things to visit. (Standard depth-first search, basically.)

The point where we traverse edges is here:

rust/src/librustc_mir/borrow_check/error_reporting.rs

Line 593 in f17c230

stack.extend(mir.predecessor_locations(l));

what we could do is to keep a "boolean" as we traverse. It would start out false, but become true if ever traverse a backedge.

I'd probably start by adding a IsBackEdge newtype:

struct IsBackEdge(bool);

So change that call to extend into something like this:

stack.extend(
  mir.predecessor_locations(l)
      .map(|predecessor| {
          // There is an edge `predecessor -> l`. This is a backedge if `l` dominates `predecessor`.
          let is_backedge = l.dominates(predecessor, &self.dominators);
          (predecessor, IsBackEdge(is_backedge))
        }
);

This will put (point, bool) pairs onto the stack. Obviously we'll have to tweak a few other things. I think we can just ignore the boolean for the point of view of tracking where we have been -- we don't want to visit the same block twice. We would then want to modify the return value to be not just a MoveOutIndex but a (MoveOutIndex, IsBackEdge) tuple:

Vec<(MoveOutIndex, IsBackEdge)>

then we can adjust the code to add the ", in previous iteration of loop" only if IsBackEdge is true.

[blitzerr]

That is one hell of an explanation. Thank you so much for taking time to put your thoughts in such an elaborate manner. Thanks

[nikomatsakis]

Zulip stream

[nikomatsakis]

@blitzerr has a WIP PR here for this issue #54343 (I don't see a link right now)