Convincing the borrow checker that v[i] and v[j] are separate when assert!(i != j)

help
1

Hello,

I understand that in general it's tricky for the borrow checker to see at compile time that two elements v[i] and v[j] are independent.

But even the following does not compile (note the assert):

fn main() {
    let mut cache = Vec::<Vec<i32>>::new();
    cache.push(vec![1, 2, 3]);
    cache.push(Vec::<i32>::new());

    let i = 0;
    let j = 1;
    assert!(i != j);

    for e in &cache[i] {
        cache[j].push(e*e);
    }

    dbg!(cache);
}

Having been spoiled quite a bit by the intelligence of the borrow checker so far, I wonder why this is so?

  • Is there a possibility of UB that I overlook here?
  • Is this difficult to implement in the compiler (in sufficient generality)?
  • Is it considered not important, because there exist good enough workarounds? (In my real code the elements of the outer vector are hash maps, and I need to iterate over cache[i] and cache[j] while mutating cache[k], so split_at_mut seems cumbersome.)

Thanks for any suggestions!

2

Reality is more complex, but if I simplify pretty hard it's because values (in this case the cache Vec) are seen as one unit by the borrow checker. That is to say, when you borrow &cache[I], the cache is locked by borrowck "in immutable mode".
Once you know that and the fact that borrowck enforces CREWÂą semantics, it becomes more clear why cache[j].push(e*e) generates a compile error.

The difficult part isn't implementation, per se. Its that in order to separate parts of a Vec, 2 things would need to happen:

  1. Special case support for Vec's (or more likely, slices)

  2. The compiler must be able to prove that 2 simultaneously accessed parts of a vec/slice are indeed disjoint. In general, that's pretty hard to do.

It's more a combination of the difficulty in the one hand, which would mean a lot of time and resources need to be spent on it in order to gain confidence in the new analysis, and the fact that there is already a backlog that's likely long enough to fill the next 5-10 years with on the other. That means a lot of features are being (de)prioritized, by necessity, as the Rust project has finite resources.

One thing that might work for your use case is something like cache.split_at_mut(), which would borrow cache and split that into 2 parts. If you choose the split index s such that i < s < j or j < s < i then you might be able to access both indices at the same time. Just remember to do the proper index arithmetic.

Âą Concurrent Reads, Exclusive Writes. Though even that is a simplification because of the existence of internal mutability

6 Likes
3

How general would you want the solution to be?

Containers such as Vec appear to implement indexing with Index and IndexMut and the lifetime of the borrowed output is tied to the lifetime of the borrowed input by the types of the trait methods. There's no way to express disjointness in the type system (as far as I know).

There's other related stuff that rustc doesn't allow. For instance if you write

for i in 0..10 {
    if i == 5 {
        f()
    }
}

the borrow checker won't let f be FnOnce, even though we know it will only be executed once. But if you rewrote this to something like f.take().unwrap()() where f stores an Option the optimizer can probably see through what's going on and eliminate the check.

4 Likes
4

There is an unstable get_many_mut method for cases like this.

14 Likes
5

Technically not, but split_at_mut() can be used in exactly this kind of situations. It of course uses unsafe under the hood so the disjointness of the returned slices is only guaranteed by the library, not proven by the compiler.

3 Likes
6

split_at_mut has to be a separate function that returns a tuple because the type of index_mut implies that the mutable borrow of the container has the same lifetime as the borrow of the output. There's no way to make a lifetime that just refers to a subset of a slice. Definitely it is the way to go but the original poster is aware of that and writes that it is "cumbersome."

2 Likes
7

Yes; global reasoning is hard. There's nothing in the type system that connects the i != j assertion with the following statements. The compiler is not "magic" or even "intelligent"; it merely follows rigorous, piecemeal inference rules baked into the type system and no more. If you can't express something using types, you can't express it.

Your use case is very easy to fix, though. Instead of requiring the compiler to "infer" the inequality from an assertion, just be explicit about it:

fn get_mut_nonoverlapping<T>(slice: &mut [T], i: usize, j: usize) -> (&mut T, &mut T) {
    assert!(i < j); // this is NOT necessary, only here for a clearer panic message
    let (head, middle) = slice.split_at_mut(i + 1);
    let (_, tail) = middle.split_at_mut(j - i - 1);
    (head.last_mut().unwrap(), tail.first_mut().unwrap())
}
3 Likes
8

The problem is not “how to implement that in the compiler”, but more of “how to implement that in the type system”.

What you are asking for is more-or-less full-blown dependent types in a disguise.

With all the complexity but without benefits of language-level dependent types.

I would say that going that way would be just stupid: if someone would really have resources to tackle that then adding full-blown dependent typing to the language sounds more sensible.

But that would give us entirely different language, maybe even better language, but that wouldn't be Rust.

Maybe in 10-20 years someone would do that.

4 Likes
9

The issue is about aliasing. If aliasing is not what you want, you can just avoid aliasing, and voilĂ , the issue is gone!

let mut cache_j = std::mem::take(&mut cache[j]);

for e in &cache[i] {
    cache_j.push(e * e);
}

cache[j] = cache_j;
5 Likes
10

If I'm trying to get single elements, I personally prefer to lean on iter_mut instead of split_at_mut:

fn get_two_mut<T>(slice: &mut [T], i: usize, j: usize) -> Option<(&mut T, &mut T)> {
    if i == j { return None; }
    if j < i {
        let (a,b) = get_two_mut(slice, j, i)?;
        return Some((b,a));
    }
    
    let mut iter = slice.iter_mut();
    let iter = &mut iter;
    
    Some((
        iter.nth(i)?,
        iter.nth(j - i - 1)?
    ))
}
2 Likes
12

Thanks. I see that supporting this in full generality would be tricky, but naively I assumed that the compiler has been taught to understand at least the special case of slice indexing and an explicit assert (or constants).

In my particular case, I need to iterate over v[i] and v[j] while mutating v[k] where k = i + j, so split_at_mut(k) will work:

fn main() {
    let mut cache = Vec::<Vec<i32>>::new();
    cache.push(vec![1, 2, 3]);
    cache.push(Vec::new());

    {
        let i = 0;
        let j = 0;
        let k = 1;
        assert!(k != i && k != j);

        let (cache, cache_k) = cache.split_at_mut(k);
        let cache_k = &mut cache_k[0];
        for ei in &cache[i] {
            for ej in &cache[j] {
                cache_k.push(ei * ej);
            }
        }
    }

    dbg!(cache);
}

But the more general case where i, j, and k are not ordered, would be less nice, since one would have to deal with shifted indices.

13

For that situation, the easiest path is probably @Hyeonu's solution to mem::take(&mut v[k]) and then put it back when you're done with the changes. Empty vectors don't allocate, so you're not really doing much extra work here.

3 Likes
14

The assembly of that function is however terrible. LLVM can't even remove the recursion!

FYI this version used to optimize really well until Rust 1.64, but regressed in Rust 1.65. LLVM used to even remove the if i < j branch. It didn't work as nicely when using Option though.

fn get_two_mut<T>(slice: &mut [T], i: usize, j: usize) -> (&mut T, &mut T) {
    assert!(i != j && i < slice.len() && j < slice.len());
    
    if i < j {
        let (head, tail) = slice.split_at_mut(j);
        (&mut head[i], &mut tail[0])
    } else {
        let (head, tail) = slice.split_at_mut(i);
        (&mut tail[0], &mut head[j])
    }
}

Edit: here's an updated version where the i < j branch is elided both when panicking and returning an Option. The Option variant is also branchless (it uses conditional moves).

Even that would still be too prone to accidental regressions that it will likely never be included.

And by the way compilers are not "taught" something, they are implemented to handle code and decide whether it satisfies some set of formal rules.

4 Likes
15

I like to use informal language whenever I judge it to be clear enough. I thought that this was the case here.

(To give another example, algorithms are not people and cannot be "greedy" or "optimistic", and we still like to employ these terms.)

16

The problem is that the type of the indexing operation forbids what you want to do. When you write cache[j].push the array access is shorthand for cache.index_mut(j) which takes as input a &'a mut Vec<Vec<i32>> and index and returns a &'a mut Vec<i32>. The exclusive borrow of the container lasts as long as the exclusive borrow of the item. It doesn't matter what the index is.

Although it looks similar this isn't like non-lexical lifetimes where rustc accepts more code than it used to.

The optimizer can sometimes eliminate runtime checks that the language forces on you.

3 Likes
17

I see - thanks a lot. I knew that square bracket indexing uses the Index and IndexMut traits, but didn't think this through. Then I found the thread linked in the first message that seemed to indicate that the difficulty lies in the compiler not being able to convince itself that i != j. But actually they come to the same conclusion there as well:

But of course, as you say, that would entail either giving slices some special treatment in the compiler, or increasing the language's expressivity until the notion of a disjoint borrow can be expressed in a method's interface.

18

assert! is used to enforce run-time invariants, I don't think assert can be used to interact with the compiler.

hmm... Maybe in the future the standard library can include const_assert or compiler_assert to enforce compile-time invariants(or other types-invariants). But since the signatures of the Index and IndexMut traits do not imply this relationship, this invariant certainly does not manifest itself in the form of simultaneous shared&mutable accesses to cache[i] and cache[j].

You can implement const_assert in some way, but the compiler doesn't enforce more invariants based on it

19

That's what I used to believe as well, but have a look at this:

An assert macro expands to something like if !condition { panic!("Assertion failed!") }. The compiler is smart enough to understand that panic never returns, so that indeed (as demonstrated by @scottmcm above) assertions can lead to emission of more efficient code.

1 Like
20

Yes, but that's a very low-level effect. Since this only pertains to a very narrow aspect of control flow analysis, and not something rigorously encoded in the type system, it can be used for this one specific kind of optimization, but not for anything else that would require a proper type-level check.

21

I'm not denying that compilers can generate efficient code based on asserts. In fact, I would say any compiler that can't do this(for this simple example) during optimization is... bad

But, it's optimization instead of semantic analysis.

My view here is that you can't make rust's semantic analysis think:

// cache is a slice
assert!(i != j);
// emm.. I know i != j
let ref_i = &cache[i];
let ref_j = &mut cache[j];
// oh, ref_i and ref_j are references to different memory region
// so, safe rust allow to access them simultaneous

Update on 2024.08.04:

I just read a RFC about using type system to mark discontinuous borrowing(RFC2025#discontinuous-borrows)

3 Likes