MIR borrowck doesn't accept the example of iterating and updating a mutable reference

[nikomatsakis]

I expected this example from the NLL RFC to pass the MIR borrow checker:

struct List<T> {
    value: T,
    next: Option<Box<List<T>>>,
}

fn to_refs<T>(mut list: &mut List<T>) -> Vec<&mut T> {
    let mut result = vec![];
    loop {
        result.push(&mut list.value);
        if let Some(n) = list.next.as_mut() {
            list = n;
        } else {
            return result;
        }
    }
}

fn main() {
}

The idea here is that assigning to list is supposed to clear the existing borrows of list.{value,next}. However, it still gets errors for me:

lunch-box. rustc --stage1 iterate-mut-ref.rs  -Zborrowck=mir
error[E0499]: cannot borrow `list.value` as mutable more than once at a time
  --> iterate-mut-ref.rs:9:21
   |
9  |         result.push(&mut list.value);
   |                     ^^^^^^^^^^^^^^^ mutable borrow starts here in previous iteration of loop
...
16 | }
   | - mutable borrow ends here

error[E0499]: cannot borrow `list.next` as mutable more than once at a time
  --> iterate-mut-ref.rs:10:26
   |
10 |         if let Some(n) = list.next.as_mut() {
   |                          ^^^^^^^^^ mutable borrow starts here in previous iteration of loop
...
16 | }
   | - mutable borrow ends here

error[E0506]: cannot assign to `list` because it is borrowed
  --> iterate-mut-ref.rs:11:13
   |
9  |         result.push(&mut list.value);
   |                     --------------- borrow of `list` occurs here
10 |         if let Some(n) = list.next.as_mut() {
11 |             list = n;
   |             ^^^^^^^^ assignment to borrowed `list` occurs here

error: aborting due to 3 previous errors

cc @pnkfelix @arielb1

[nikomatsakis]

It turns out the code for this was just never written. What we need to do is "kill" the relevant borrows in the borrows.rs data flow code. The StorageDead case is doing something similar already, but specific to local variable places:

rust/src/librustc_mir/dataflow/impls/borrows.rs

Lines 265 to 268 in 707d070

	// FIXME: expand this to variables that are assigned over.
	if let Some(borrow_indexes) = self.local_map.get(&local) {
	sets.kill_all(borrow_indexes);
	}

We would need to handle this in the case of a general assignment, but there the Place values that can be assigned can be any sort of path, so we need to be handling them all.

[Yoric]

So, if I understand correctly, we want to duplicate/share the logics from StorageDead to Assign(ref lhs, _), right? I'm starting to look into it.

[Yoric]

As discussed with @pnkfelix over gitter, I'll try to first write a patch that works only if we Assign to a Local. Once this works, I'll see if I can understand what to do for a Place::Projection.

[nikomatsakis]

@Yoric great! that's a good starting point.

[Yoric]

I'm now trying to tackle down the next part, but I can't find anything useful in the RFC, so I'm a bit blind here.

Looking at projections, I see the following cases:

1. *a = expr
2. a.foo = expr
3. a[slice] = expr
4. a[literal] = expr
5. a[expr] = expr
6. downcasts (not entirely sure what they are)

I imagine that case 1. is basically the same thing as what I have done already and that cases for 3 and 5, there isn't anything we can do. What about cases 2, 4 and 6?

[Yoric]

needinfo @pnkfelix , @nikomatsakis ?

[nikomatsakis]

@Yoric as I wrote in gitter, one way to approach this is to generalize the routine that is used to detect overlap between paths. This function is called places_conflict:

rust/src/librustc_mir/borrow_check/mod.rs

Lines 1769 to 1777 in 78f24d8

	/// Returns whether an access of kind `access` to `access_place` conflicts with
	/// a borrow/full access to `borrow_place` (for deep accesses to mutable
	/// locations, this function is symmetric between `borrow_place` & `access_place`).
	fn places_conflict(
	&mut self,
	borrow_place: &Place<'tcx>,
	access_place: &Place<'tcx>,
	access: ShallowOrDeep,
	) -> bool {

However, presently it is "biased" towards returning that yes, places overlap. This is because it is used to detect illegal assignments. Specifically, with indexing, we wind up approximating -- that is, if you borrow foo[i].bar, and then assign to foo[j].bar, we assume that i=j. But for the purposes of this code, we do not know that those two paths overlap, so we do now want to kill the borrow of foo[i].bar. We could therefore make places_overlap return an Option<bool>, where None means unknown. Alternatively, we could give it a parameter indicating its "bias" -- that may be easier.

The part of the code that controls how we handle array accesses is here. Returning EqualOrDisjoint means that we will consider paths that involve two array accesses to be equal (i.e., overlapping) unless other parts of them are disjoint (so, e.g., foo[i].bar and foo[i].baz are disjoint because of bar and baz being disjoint). If we were threading down a "bias" parameter, we might here consider returning instead just Disjoint.

[nikomatsakis]

This is not as general as it could be, but I'm marking as deferred rather than complete because honestly I think handling local variables is "good enough" for now, and we can always come back to it.

[nikomatsakis]

Here is an example (from #48001) of code that ought to pass when this is fully implemented:

#![feature(nll)]

struct Foo;

impl Foo {
    fn get_self(&mut self) -> Option<&mut Self> {
        Some(self)
    }

    fn new_self(&mut self) -> &mut Self {
        self
    }
    
    fn trigger_bug(&mut self) {
        let other = &mut (&mut *self);
        
        *other = match (*other).get_self() {
            Some(s) => s,
            None => (*other).new_self()
        };
        
        let c = other;
        
    }
}

fn main() {}

currently it fails with

error[E0505]: cannot move out of `other` because it is borrowed
  --> src/main.rs:22:17
   |
17 |         *other = match (*other).get_self() {
   |                        -------- borrow of `**other` occurs here
...
22 |         let c = other;
   |                 ^^^^^ move out of `other` occurs here

[SimonSapin]

I tried to write some code with an early-returned borrow inside a loop that I expected NLL would accept, but it didn’t. A reduced test case is below. Is this the same issue?

#![feature(nll)]

fn main() {}

pub struct Decoder {
    buf_read: BufRead,
}

impl Decoder {
    pub fn next<'a>(&'a mut self) -> &'a str {
        loop {
            let buf = self.buf_read.fill_buf();
            if let Some(s) = decode(buf) {
                return s
            }
            // loop to get more input data

            // At this point `buf` is not used anymore.
            // With NLL I would expect the borrow to end here,
            // such that `self.buf_read` is not borrowed anymore
            // by the time we start the next loop iteration.
        }
    }
}

struct BufRead;

impl BufRead {
    fn fill_buf(&mut self) -> &[u8] { unimplemented!() }
}

fn decode(_: &[u8]) -> Option<&str> { unimplemented!() }

(Playground)

Errors:

   Compiling playground v0.0.1 (file:///playground)
error[E0499]: cannot borrow `self.buf_read` as mutable more than once at a time
  --> src/main.rs:12:23
   |
12 |             let buf = self.buf_read.fill_buf();
   |                       ^^^^^^^^^^^^^ mutable borrow starts here in previous iteration of loop
   |
note: borrowed value must be valid for the lifetime 'a as defined on the method body at 10:17...
  --> src/main.rs:10:17
   |
10 |     pub fn next<'a>(&'a mut self) -> &'a str {
   |                 ^^

error: aborting due to previous error

For more information about this error, try `rustc --explain E0499`.
error: Could not compile `playground`.

To learn more, run the command again with --verbose.

[SimonSapin]

Interestingly, this a case where NLL is not "just" about making some code slightly nicer. As far as I can tell there is no way to write the algorithm without unsafe in current Stable Rust. As to the unsafe way, it compiles but it’s very tricky to convince myself that it’s actually valid, especially in the non-reduced code: https://play.rust-lang.org/?gist=ac9aa0aac36330cb52d113f26452a06a&version=stable&mode=debug&edition=2015

[pnkfelix]

Re-triaging for #56754. Leaving assigned to @davidtwco. P-medium, NLL-complete.

[goffrie]

@nikomatsakis's example still doesn't work, right?

error[E0499]: cannot borrow `**other` as mutable more than once at a time
  --> src/main.rs:19:21
   |
17 |         *other = match (*other).get_self() {
   |                        -------- first mutable borrow occurs here
18 |             Some(s) => s,
19 |             None => (*other).new_self()
   |                     ^^^^^^^^
   |                     |
   |                     second mutable borrow occurs here
   |                     first borrow later used here

error: aborting due to previous error

[davidtwco]

@goffrie @nikomatsakis’s example is now missing the second error that this issue was intended to solve, namely:

error[E0505]: cannot move out of `other` because it is borrowed
  --> src/main.rs:22:17
   |
17 |         *other = match (*other).get_self() {
   |                        -------- borrow of `**other` occurs here
...
22 |         let c = other;
   |                 ^^^^^ move out of `other` occurs here