Borrow checker is sensitive to the order of borrows in surprising ways

[ezyang]

Here is a piece of code that borrow-checks:

use std::util;

enum List<T> {
    Cons(T, ~List<T>),
    Nil
}

fn pop<T>(prev: &mut ~List<T>) -> Option<~List<T>> {
    let xs = util::replace(match prev {
        &~Cons(_, ref mut rs) => rs,
        &~Nil => return None
    }, ~Nil);
    Some(util::replace(prev, xs))
}

Here is a rewritten variant of pop, where the let has been substituted in, which does not borrow-check:

fn pop<T>(prev: &mut ~List<T>) -> Option<~List<T>> {
    Some(util::replace(prev, util::replace(match prev {
        &~Cons(_, ref mut rs) => rs,
        &~Nil => return None
    }, ~Nil)))
}

failing with:

del.rs|22 col 18 error| cannot borrow `(**prev)#1` as mutable more than once at a time
del.rs|21 col 23 n| second borrow of `(**prev)#1` as mutable occurs here

What is going on? The problem has to do with the order of arguments to the outer replace. Consider this alternate version, which has a flipped replace function:

pub fn freplace<T>(mut src: T, dest: &mut T) -> T {
    util::swap(dest, &mut src);
    src
}

fn pop<T>(prev: &mut ~List<T>) -> Option<~List<T>> {
    Some(freplace(util::replace(match prev {
        &~Cons(_, ref mut rs) => rs,
        &~Nil => return None
    }, ~Nil), prev))
}

This borrow-checks fine. The key is that the borrow-checker is interpreting the original (failing) code as something like this:

fn pop2<T>(prev: &mut ~List<T>) -> Option<~List<T>> {
    let ref mut prev2 : &mut ~List<T> = prev;
    let xs = util::replace(match prev {
        &~Cons(_, ref mut rs) => rs,
        &~Nil => return None
    }, ~Nil);
    Some(util::replace(*prev2, xs))
}

whereas the succeeding code is more like:

fn pop2<T>(prev: &mut ~List<T>) -> Option<~List<T>> {
    let xs = util::replace(match prev {
        &~Cons(_, ref mut rs) => rs,
        &~Nil => return None
    }, ~Nil);
    let ref mut prev2 : &mut ~List<T> = prev;
    Some(util::replace(*prev2, xs))
}

Operationally, all of these code fragments do the same thing, since only one of the two arguments has side-effects; but of course, to the borrow-checker, a borrow counts as a side-effect.

Since borrows commute, one way to fix this is "sink" big borrows as late as possible (in analogy to how you sink memory dereferences to reduce register pressure). I don't actually know if this works or is a good idea.

If you squint, fixing Issue #6268 might resolve this issue as well. My interpretation goes something like this: the big borrow starts off as the secondary aliasing loan, permitting the inner replace, before it becomes a proper primary loan.

CC @nikomatsakis

[nikomatsakis]

This is a dup of #6268 as the OP suggested might be the case. It has nothing to do with receivers, but receivers are not the heart of the issue, the issue is the hierarchical lifetime structure around function/method calls, and its inability to capture the fact that the pointers passed as argument will not be used until during the call itself.