I wanted to implement the Merge Sort algorithm, but I am having trouble with the borrow checker rules.
The compiler gives me the hint:
cannot borrow *lst as immutable because it is also borrowed as mutable [E0502]
immutable borrow occurs here
fn merge_sort(lst: &mut [i32]) {
let len: usize = lst.len();
let mut tmp: Vec<i32> = vec![0; len];
let mut src: &mut [i32] = lst;
let mut dst: &mut [i32] = &mut tmp;
let mut width: usize = INSERTION_SORT_THRESHOLD;
// Use insertion sort
for chunk in src.chunks_mut(width) {
insertion_sort(chunk);
}
// Use merge sort
while width < len {
let mut left: usize = 0;
while left < len {
let mid: usize = min(left + width, len);
let right: usize = min(left + width * 2, len);
merge(src, dst, left, mid, right);
left += width * 2;
}
std::mem::swap(&mut src, &mut dst);
width *= 2;
}
if src.as_ptr() != lst.as_ptr() {
lst.copy_from_slice(src);
}
}
ERROR:
error[E0502]: cannot borrow `*lst` as immutable because it is also borrowed as mutable
--> src/main.rs:99:24
|
72 | let mut src: &mut [i32] = lst;
| --- mutable borrow occurs here
...
99 | if src.as_ptr() != lst.as_ptr() {
| ^^^ immutable borrow occurs here
100 | lst.copy_from_slice(src);
| --- mutable borrow later used here
There are two problems with your code as written.
The first, easily fixable, problem is that the check to see whether src and lst are the same runs lst.as_ptr() – calling any methods at all on a reference, even one as inoffensive as .as_ptr(), invalidates any mutable borrows of that reference (thus, when you call a method on lst, this invalidates src because it could potentially be mutably borrowed from lst). This is the issue that produces the error message you've given in the question. The fix here is to move the lst.as_ptr() call to before the point at which lst is borrowed:
let lst_ptr = lst.as_ptr();
let mut src: &mut [i32] = lst;
…
if src.as_ptr() != lst_ptr
This way, the lst.as_ptr() call doesn't invalidate src because the call happens before src is initially borrowed, so there's nothing to invalidate.
The reason that Rust produces an error here is that the type checker doesn't look into the internals of methods to see what they do: it relies entirely on the stated type, and it's possible to imagine hypothetical methods with the same type as those in your program for which the double borrow would be dangerous (e.g. imagine that merge used a background thread to mutate its arguments, continuing throughout the entire lifetime of the variables being merged, and as_ptr contained some sort of assert that read the values inside without synchronization: this is a very unlikely combination, but if the methods did work like that, it could cause a torn read, possibly invalidating invariants that the code relies on). With the actual implementation of as_ptr, there is not even a potential safety issue, but the type checker doesn't know that.
The second problem is that copy_from_slice requires the slices being copied to and from to be disjoint (i.e. different and not overlapping). It is possible for src and lst to reference the same list (in fact, your code contains an explicit guard to check that!), so lst.copy_from_slice(src) will be rejected by the borrow checker. Although you checked to see whether they were different, the borrow checker doesn't look at your program's logic – only at the types you used – so it notices that you might be trying to copy from lst to itself, and rejects the program.
In the case of this particular program, there's an easy fix: you know that lst is always either src or dst, and the borrow checker knows that dst and src are disjoint even though it doesn't know that lst and src are disjoint. So, instead of copying from src to lst, you can instead just copy from src to dst (which you know will necessarily be an alias for lst if that block of code is reachable).
The two fixes I suggested above are somewhat specific to this particular program, but in general they're both caused by the borrow-checker not knowing what methods do (just by what their types are) and worrying about possibilities that are compatible with the method's type but not with the method's behaviour, often related to multithreading. In cases where you know that the program is safe because it's single-threaded, one possibility is to switch from &mut T (which allows reading and writing, but prevents the use of any other references to the same thing) to &Cell<T> (which also allows reading and writing, but does not assume that there are no other references, meaning that the code is only safe in single-threaded contexts). See the documentation of Cell::from_mut, which gives an example of using it with a slice. In effect, this technique turns off the checks in the borrow checker against reading something while it is being modified – in single-threaded code, this can't violate type safety or memory safety, although it means you need to think a lot more about whether the value you're reading mid-modification is meaningful. (The borrow checker isn't really designed to catch logic errors, and doesn't guarantee that it will catch them, but sometimes manages to do so anyway, e.g. with iterator invalidation. When using the Cell technique, it is even less likely to catch them than normal, so you have fewer safeguards in that sense.)
Note that &Cell<T> isn't a drop-in replacement for &mut T – the standard libraries API are normally written to work with &mut T, so you would have to write out methods like copy_from_slice by hand (but that is pretty simple to do). Additionally, you can't take a reference to the "inside" of a Cell, so any reads and writes have to be done via copying or swapping (but in the case of a merge sort, doing everything using copies or swaps is fine).
In general, I prefer to use a solution that satifies the borrow checker (such as the "calculate lst_ptr in advance, and copy src to dst" solution above), but solving that for any given program often depends on its details ad may not always be possible. As such, it's useful to know about the general escape valve of going via Cell – it's much safer than using unsafe would be, because it can't introduce type-safety or memory-safety errors (it simply removes some of the safeguards against logic errors).