MIR-borrowck: identify cause of (and fix) extra "move out"/"assign to" errors signalled by mir-borrowck

[pnkfelix]

There are many tests in compile-fail/borrowck/ that, in addition to signalling the errors that we already expect, also include a number of additional errors usually of the form "cannot move out of because it is borrowed.".

• You can see list of such tests in the discrepancy spreadsheet.

• Here is example output from an especially bad instance of the problem:

error[E0505]: cannot move out of `vec` because it is borrowed (Mir)
  --> ./src/test/compile-fail/borrowck/borrowck-vec-pattern-element-loan.rs:22:2
   |
22 | }
   |  ^

error[E0505]: cannot move out of `vec` because it is borrowed (Mir)
  --> ./src/test/compile-fail/borrowck/borrowck-vec-pattern-element-loan.rs:22:2
   |
22 | }
   |  ^

error[E0506]: cannot assign to `vec` because it is borrowed (Mir)
  --> ./src/test/compile-fail/borrowck/borrowck-vec-pattern-element-loan.rs:22:2
   |
22 | }
   |  ^

error[E0505]: cannot move out of `vec` because it is borrowed (Mir)
  --> ./src/test/compile-fail/borrowck/borrowck-vec-pattern-element-loan.rs:32:2
   |
32 | }
   |  ^

error[E0505]: cannot move out of `vec` because it is borrowed (Mir)
  --> ./src/test/compile-fail/borrowck/borrowck-vec-pattern-element-loan.rs:32:2
   |
32 | }
   |  ^

error[E0506]: cannot assign to `vec` because it is borrowed (Mir)
  --> ./src/test/compile-fail/borrowck/borrowck-vec-pattern-element-loan.rs:32:2
   |
32 | }
   |  ^

error[E0505]: cannot move out of `vec` because it is borrowed (Mir)
  --> ./src/test/compile-fail/borrowck/borrowck-vec-pattern-element-loan.rs:42:2
   |
42 | }
   |  ^

error[E0505]: cannot move out of `vec` because it is borrowed (Mir)
  --> ./src/test/compile-fail/borrowck/borrowck-vec-pattern-element-loan.rs:42:2
   |
42 | }
   |  ^

error[E0506]: cannot assign to `vec` because it is borrowed (Mir)
  --> ./src/test/compile-fail/borrowck/borrowck-vec-pattern-element-loan.rs:42:2
   |
42 | }
   |  ^

These errors often (perhaps always?) occur at the end of some lexical scope, so perhaps they are arising due to over-zealous handling of destructors, or StorageDead (or EndRegion)?

In any case, they represent a lot of extra noise and need to be dealt with.

[pnkfelix]

(Incomplete list of) relevant tests according to the discrepancy spreadsheet. (caveat: data is based on out-of-date pnkfelix/mir-borrowck4 branch)

tests where MIR-borrowck is reporting extra (and silly) move outs
borrowck-overloaded-index-move-index.rs
borrowck-multiple-captures.rs
borrowck-issue-2657-1.rs
borrowck-loan-blocks-move.rs
borrowck-move-from-subpath-of-borrowed-path.rs
borrowck-mut-borrow-linear-errors.rs
borrowck-no-cycle-in-exchange-heap.rs
borrowck-unary-move.rs
borrowck-loan-blocks-move-cc.rs

I would like to attempt to fix this if that's cool. I would like to just known if this is a single test or part of the main Rust test suite this bug is hitting.

Seems this line is in all three:
let vec: &[isize] = &vec;
Why are we passing a reference that is immutable according to the lanauge specs when I looked at them, wouldn't let vec: &[isize] = vec actually work better?;

[pnkfelix]

@xerofoify asked:

Why are we passing a reference that is immutable according to the lanauge specs when I looked at them, wouldn't let vec: &[isize] = vec actually work better?;

You cannot assign vec (which is a Vec holding some integer type) into a variable of type &[isize]. A vector is not a reference. You can see this for yourself by cut-and-pasting the code into the playpen and then making the change you suggest: playpen.

You can assign a &Vec<isize> into a variable of type &[isize], because of Deref Coercions (combined with the fact that Vec<T> implements Deref<Target=[T]>).

• The fact that the test is named borrowck-vec-pattern-element-loan.rs may lead one to ask the question: Why is the test named as if it were testing borrowing elements of the vector directly, rather than borrowing elements of a slice? The answer is that the test has changed quite a bit over the life of that file; in particular, vectors used to be a special type built into the language, ~[T], and at that time this test was checking that you could use match on such a thing, and get errors in the cases where you tried to make a borrow of the suffix that outlives the original object. See for example this change from Feb 2014 when we removed "unique vector patterns": 33923f4#diff-ca8b59e6bc8d77bc637e67c5a9d9ae29
• Wow the history of this file goes way back: renamed from alt-vec-illegal-tail-loan.rs in 2013 which was added back at end of 2012

[pnkfelix]

@xerofoify there may be easier issues to start in on if this is your first foray into hacking on the borrow checking code.

In particular, a narrow test failure like this one where mir-borrowck isn't handling FRU correctly #44833 might be a good initial bug.

Having said that, I'm happy to advise on any bug you want to dive in on. Feel free to join us in the gitter channel for NLL (which encompasses the mir-borrowck work for now): https://gitter.im/rust-impl-period/WG-compiler-nll

[pnkfelix]

I looked a little bit into this tonight, for the specific case of borrowck-unary-move.rs, since that is a pretty small self-contained example.

Below is the MIR (in the <Details> block)

• this is all generated via the command RUST_LOG=rustc_mir::borrow_check ./build/x86_64-unknown-linux-gnu/stage1/bin/rustc -Z borrowck-mir -Z identify-regions ../src/test/compile-fail/borrowck/borrowck-unary-move.rs -Z dump-mir=foo
• this particular MIR is dumped to rustc.node4.001-002.NLL.after.mir -- when we want to know what the input to MIR-borrowck looks like, we should look at the files with extension NLL.after.mir.

// MIR for `foo`
// source = Fn(NodeId(4))
// pass_name = NLL
// disambiguator = after

fn foo(_1: std::boxed::Box<isize>) -> isize {
    let mut _0: isize;                   // return pointer
    scope 1 {
        let _2: std::boxed::Box<isize>;  // "x" in scope 1 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:12:8: 12:9
        scope 2 {
            let _3: &'13_0rs isize;      // "y" in scope 2 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:13:9: 13:10
        }
        scope 3 {
        }
    }
    let mut _4: ();
    let mut _5: std::boxed::Box<isize>;
    let mut _6: isize;

    bb0: {
        StorageLive(_2);                 // scope 1 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:12:8: 12:9
        _2 = _1;                         // scope 1 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:12:8: 12:9
        StorageLive(_3);                 // scope 2 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:13:9: 13:10
        _3 = &'13_0rs (*_2);             // scope 2 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:13:13: 13:16
        StorageLive(_5);                 // scope 2 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:14:10: 14:11
        _5 = _2;                         // scope 2 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:14:10: 14:11
        _4 = const free(_5) -> [return: bb1, unwind: bb6]; // scope 2 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:14:5: 14:12
    }

    bb1: {
        drop(_5) -> [return: bb7, unwind: bb4]; // scope 2 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:14:12: 14:12
    }

    bb2: {                               // cleanup
        resume;                          // scope 0 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:12:1: 16:2
    }

    bb3: {                               // cleanup
        drop(_2) -> bb2;                 // scope 0 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:16:2: 16:2
    }

    bb4: {                               // cleanup
        drop(_1) -> bb3;                 // scope 0 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:16:2: 16:2
    }

    bb5: {                               // cleanup
        EndRegion('13_0rs);              // scope 1 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:12:32: 16:2
        goto -> bb4;                     // scope 1 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:12:32: 16:2
    }

    bb6: {                               // cleanup
        drop(_5) -> bb5;                 // scope 2 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:14:12: 14:12
    }

    bb7: {
        StorageDead(_5);                 // scope 2 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:14:12: 14:12
        StorageLive(_6);                 // scope 2 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:15:5: 15:7
        _6 = (*_3);                      // scope 2 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:15:5: 15:7
        _0 = _6;                         // scope 2 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:15:5: 15:7
        StorageDead(_6);                 // scope 2 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:15:7: 15:7
        EndRegion('13_0rs);              // scope 1 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:12:32: 16:2
        StorageDead(_3);                 // scope 1 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:16:2: 16:2
        drop(_1) -> [return: bb8, unwind: bb3]; // scope 0 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:16:2: 16:2
    }

    bb8: {
        drop(_2) -> bb9;                 // scope 0 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:16:2: 16:2
    }

    bb9: {
        StorageDead(_2);                 // scope 0 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:16:2: 16:2
        return;                          // scope 0 at ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:16:2: 16:2
    }
}

And, here is the line from RUST_LOG (with some line breaks added by hand for presentation purposes), right before we emit the extraneous error, along with the error itself:

DEBUG:rustc_mir::borrow_check: MirBorrowckCtxt::process_terminator(bb3[0], \
    Terminator { source_info: SourceInfo { span: ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:16:2: 16:2, scope: scope0 }, \
                                           kind: drop(_2) -> bb2 }): \
    borrows in effect: [&'13_0rs (*_2)] borrows generated: [] inits: [_0, _3, _4, _6] uninits: [_0, _1, _2, _4, _5, _6]
error[E0505]: cannot move out of `x` because it is borrowed (Mir)
  --> ../src/test/compile-fail/borrowck/borrowck-unary-move.rs:16:2
   |
13 |     let y = &*x;
   |             --- borrow of `(*x)` occurs here
...
16 | }
   |  ^ move out of `x` occurs here

Two things of interest.

1. _2 is not in the inits set, so we know from the dataflow that it cannot be initialized, which means this drop is a no-op. (Could/should we avoid emitting diagnostics for such case?)
2. The borrow &'13_0rs (*_2) is apparently still in effect for this drop of _2 (which is the sole content of bb3). There are three other drops of _2 in the MIR, and the RUST_LOG output indicates that that borrow is not effect for any of those; just this particular one. So my immediate questions are:
   • shouldn't there be an EndRegion('13_0rs) along every control-flow path before we get to bb3?
   • And if there is such an EndRegion, then what's going wrong with the Borrows dataflow implementation?)

I think point 2 is the bigger bug of interest here. Figuring out what's happening there might resolve a lot of these extraneous E0505 emissions that I am seeing from MIR-borrowck.

[pnkfelix]

Okay so next step: I made a copy of borrowck-unary-move.rs and added this to the top of it, right above the fn foo:

#![feature(rustc_attrs)]

#[rustc_mir(borrowck_graphviz_preflow="preflow.dot",
            borrowck_graphviz_postflow="postflow.dot")]

This special attribute tells the compiler to dump dot files summarizing the dataflow state (both before and after running the flow).

From the generated borrows_postflow.dot, I am able to better see how things got here.

In particular, the control flow path bb0 -> bb1 -> bb4 -> bb3 is the problematic one.

bb0 creates the borrow, then we assume a normal return to bb1, then during the drop there we allow for a fault that causes us to unwind to bb4 which falls through to bb3 and we hit our problematic drop.

• (p.s. graphviz has been broken on my mac for a while but it seems like http://viz-js.com combined with http://svgur.com is a pretty rocking web-based workaround.)

[pnkfelix]

Okay I think I am on the road to fixing this.

Namely, I have a local branch that modifies we emit EndRegion, specifically how we handle the diverge-path (i.e. unwinding) with respect to EndRegion. If you look at the control-flow graph in my previous comment, you might be able to tell that some EndRegions were dropped on the floor on one particular control-flow involving unwind.

I believe this local branch will fix at least the following cases:

tests resolved by change to diverge-chain
borrowck-issue-2657-1.rs
borrowck-issue-2657-2.rs
borrowck-loan-blocks-move.rs
borrowck-move-from-subpath-of-borrowed-path.rs
borrowck-move-out-of-overloaded-deref.rs
borrowck-move-subcomponent.rs
borrowck-no-cycle-in-exchange-heap.rs
borrowck-overloaded-index-move-index.rs
borrowck-overloaded-index-move-from-vec.rs
borrowck-unary-move.rs

[arielb1]

I have a fix for this in a local branch