Improve diagnostics to guide users past Borrow checking regression in brotli

[SimonSapin]

I mean regression in the sense that code that used to compile doesn’t anymore. Maybe that is an intentional soundness fix.

Compiling https://crates.io/crates/brotli / https://github.com/dropbox/rust-brotli with:

• rustc 1.25.0-nightly (61452e5 2018-01-09): OK
• rustc 1.25.0-nightly (f62f774 2018-01-10): borrowck error:

error[E0502]: cannot borrow `self.buckets_` as immutable because it is also borrowed as mutable
   --> src/enc/backward_references.rs:339:51
    |
338 |     (*self).buckets_.slice_mut()[(key as (usize)).wrapping_add((cur_ix >> 3)
    |     ---------------- mutable borrow occurs here
339 |                                     .wrapping_rem(self.buckets_.BUCKET_SWEEP() as
    |                                                   ^^^^^^^^^^^^^ immutable borrow occurs here
340 |                                                   usize))] = cur_ix as (u32);
    |                                                          - mutable borrow ends here

error: aborting due to previous error

error: Could not compile `brotli`.

Commit range: 61452e5...f62f774. #47167 seems relevant. CC @ivanbakel @eddyb

[eddyb]

cc @nikomatsakis

[nikomatsakis]

Hmm.

[nikomatsakis]

triage: P-high

Have to get to the bottom of this.

[nikomatsakis]

Standalone test case:

trait Sweep {
    fn sweep(&self) -> usize;
}

trait SliceWrapper<T> {
    fn slice(&self) -> &[T];
}

trait SliceWrapperMut<T> {
    fn slice_mut(&mut self) -> &mut [T];
}

fn foo<B: SliceWrapper<u32> + SliceWrapperMut<u32> + Sweep>(mut buckets: B) {
    let key = 0u32;
    buckets.slice_mut()[(key as usize).wrapping_add(22).wrapping_rem(buckets.sweep())] = 22;
}

fn main() { }

changing the function foo to this version, bar, that operates on slices makes the error go away:

fn bar(buckets: &mut [u32]) {
    let key = 0u32;
    buckets[(key as usize).wrapping_add(22).wrapping_rem(buckets.len())] = 22;
}

Now to decide if it is legit. =)

[nikomatsakis]

OK, so, I think the error is legit. In fact, what's a bit curious is that the other example works. Here is what is happening, and why the error makes sense. It is easier to see if you view the MIR (I enabled NLL, in fact, just to check, and dumped the MIR; you get the same error there).

Basically the code desugars into something like this:

tmp0 = SliceWrapper::slice_mut(&mut buckets); // starts the borrow of `buckets`
let index = (key as usize).wrapping_add(22).wrapping_rem(buckets.sweep());
if index < tmp0.len() {
    tmp0[index] = 22;
}

Clearly, as you can see, we started a borrow of buckets and used that to get our slice. Then we are using buckets some more. Can't do that (it's also not affected by two-phase borrows, since the &mut buckets is used (passed to slice_mut as a parameter) before the index is computed).

Now, the somewhat surprising thing is that the version using a plain u32 does compile. In fact, so does this somewhat wilder thing:

fn bar(mut buckets: &mut [u32]) {
    let key = 0u32;
    buckets[{buckets = &mut []; (key as usize).wrapping_add(22).wrapping_rem(buckets.len())}] = 22;
}

The reason is that, in this case, buckets is an lvalue. The desugaring winds up being something like:

let index = {
    buckets = &mut [];
    (key as usize).wrapping_add(22).wrapping_rem(buckets.len())
};
if index < buckets.len() {
    buckets[index] = 22;
}

In this case, there is no initial borrow of buckets to conflict with. I feel like one could argue that we should have had a different, stricter desugaring -- but seeing as this code compiles on stable, it's a bit late for that. (It wouldn't really be a soundness fix, after all.)

[nikomatsakis]

Seeing as how the error appears to be legit, and brotli has worked around it, I guess I'm inclined to close this issue. One could imagine doing a forward compatibility lint but it'd be quite tricky to do.

[oli-obk]

I think it would be enough to add an automatically applicable suggestion to the error that suggests inserting the intermediate variable.

[nikomatsakis]

triage: P-medium

Converting to a A-diagnostics bug -- i.e., we should offer a better suggestion -- and dropping priority from P-high, since the new behavior is correct.

[leoyvens]

Triage: Should be removed from the milestone.

[nikomatsakis]

Marking as release candidate. It'd be good to have some suggestions for what the error should be.

[nikomatsakis]

I'm not really sure what this error should be. It occurs in a few crates in practice. I guess the suggestion would be to pull out the subcomputation into a separate variable... the next question then is when to trigger this suggestion. There are a number of scenarios where it applies, e.g. in this example from #51915 as well (mem::replace(&mut foo, foo.bar())).

I am imagining something like this:

• If the "starting borrow" is written into a temporary, and that temporary (or some other temporary that it is copied into) winds up being ultimately used as the argument to a call;
• and the "error case" comes between that starting borrow and the call

then we might add a note like

"consider extracting this into a fresh variable with a let"

[nikomatsakis]

I'm going to bump this down to RC2 in priority. Just doesn't seem that high priority.

[nikomatsakis]

I've changed my mind and brought this back to the RC. This may be a sort of common scenario and being able to guide users would be good.

[KiChjang]

Let me see what I can do for this one.

[nikomatsakis]

So @KiChjang took a stab at this but we came to realize that -- in MIR in particular -- it's a bit tricky to figure out when to offer a suggestion. Basically the suggestion comes down to a kind of code motion: saying "this little chunk of code would borrow-check if it occurred before the mut-borrow occurs".

Figuring out if that is really true is a bit tricky, and there is always the question of changing semantics (e.g., moving code earlier might mean that the value of some variables is different and so forth). So we have to decide how far we want to go here with this suggestion.

On the other hand, maybe we can phrase some kind of neutral text, sort of like "note: consider moving this expression so that it occurs before the mutable borrow begins"? This kind of general advice is basically always applicable though, so how do we decide when to give it?

[pnkfelix]

discussed in meeting. Going to try to lower priority on this, since its not clear how we should resolve this, and the payoff (to me at least) is not totally clear.

[pnkfelix]

discussed with @nikomatsakis . Decided that while it might be interesting to have some kind of code motion analysis that would suggest to the user ways they could rearrange their expression to get things compiling, its not something that we have to have built-in. (For example, I think it might be interesting to try to incorporate such things into clippy...)

So, since the error is legit, and brotli has worked around it, we are going to close this issue.