Understanding the effects of shared references on a nested data structure

There are particular cases where you can split borrows, creating simultaneously existing references that can be any mix of mutable and immutable as long as they don't overlap. These are:

• Anything where the compiler can statically track the lack of overlap: that is, fields in a struct, tuple, or enum.
• Specifically written unsafe code which provides this feature, such as mutable-reference iterators over collections.

Your code as written does not compile because the compiler does not attempt to understand what indexing a Vec does, so it does not possess and cannot use the fact that v[0][0] does not overlap v[0][1].

Here is program which works with a direct translation of the tree shown in the figure:

#[derive(Debug)]
struct Things {
    label: &'static str,
    a: Option<Box<Things>>,
    b: Option<Box<Things>>,
    c: Option<Box<Things>>,
}

fn main() {
    // Construct depicted structure
    let mut root = Box::new(Things {
        label: "root",
        a: None,
        b: None,
        c: Some(Box::new(Things {
            label: "root.c",
            a: None,
            b: None,
            c: None,
        })),
    });

    // "Borrowing a shared reference"
    // .as_ref().unwrap() gets `&Things` out of `&Option<Things>`
    // (there are several other ways this could be done)
    let shared_reference = &root.c.as_ref().unwrap();
    let mutable_reference = &mut root.a;
    // Now, root and root.a are in the "inaccessible" state because they are
    // borrowed. (We could still create an &root.b reference).

    // Mutate while the shared reference must still exist
    dbg!(shared_reference);
    *mutable_reference = Some(Box::new(Things {
        label: "new",
        a: None,
        b: None,
        c: None,
    }));
    dbg!(shared_reference);

    // Now the references are not used any more, so we can access the root.
    // Let's look at the change we made.
    dbg!(root);
}

This program is accepted by the compiler because it understands that struct fields do not overlap, so the root may be split.

It is possible to split borrows of vectors — just not with the indexing operator. You can do it with pattern matching, mutable iteration, or with .split_at_mut(). Here's that last option, which is the most “random access” capable one:

fn main() {                                                                                                    
    let mut v = Vec::new();
    v.push(Vec::new());
    v[0].push(vec!["alpha".to_string()]);
    v[0].push(vec!["beta".to_string(), "gamma".to_string()]);
    
    let (half1, half2): (&mut [Vec<String>], &mut [Vec<String>]) =
        v[0].split_at_mut(1);
    let r1 = &mut half1[0];
    let r2 = &half2[0];

    r1.push("pi".to_string());
    println!("{:?}", r2);
}

This program works because split_at_mut() contains unsafe code that specifically creates two non-overlapping slices. This is one of the fundamental tools of Rust: using unsafe inside of libraries to create sound abstractions that wouldn't be possible using just the concepts the compiler understands.

With a pattern match instead, it would be:

    if let [r1, r2] = &mut *v[0] {
        r1.push("pi".to_string());
        println!("{:?}", r2);
    } else {
        // Pattern failed because the length did not match
        panic!("oops, v was not two elements long");
    }

This compiles because the compiler understands that pattern-matching a slice (or a struct, or anything else matchable) creates non-overlapping references to each element. (Pattern matching is implemented by the compiler and never runs Rust code to make decisions about the structure being matched.)

(This version has an explicit failure branch; the previous version would panic on the split_at_mut() or on half2[0] if v[0] was too short.)

Someone should probably check my answer, as I am fairly new to Rust myself. But...

I think this is because a Vec doesn't uphold the same invariance as, say, a tuple or nested structs.

Here's a tuple version of the example you gave (Although tuples don't support pushing, so I'm just incrementing an integer):

fn main() {
    let mut v = (((1, 3), (5)));

    let r2 = &v.0.1; //Taking a shared reference here
    let v2 = &mut v.0.0;
    *v2 += 1;

    println!("{:?}", r2);
}

The above compiles. But if you attempt to borrow: let r2 = &v.0.0;, you'll get the same error as before.

Now, if you want to actually use nested vectors for trees. There are some crates to help with that, which do not incur runtime costs. Namely token_cell (or its inspiration, ghost_cell):
https://docs.rs/token-cell/1.1.0/token_cell/index.html
https://docs.rs/ghost-cell/latest/ghost_cell/

Here's the example with a token_cell wrapping the vec tree structure:

use token_cell::*;

generate_static_token!(Token);
fn main() {
    let mut token = Token::new();
    let token2 = Token::new();
    let v = TokenCell::new(vec![vec![
        vec!["beta".to_string()],
        vec!["gamma".to_string()],
    ]]);
    let r2 = &v.borrow(&token2)[0][1]; //Taking a shared reference here
    v.borrow_mut(&mut token)[0][0].push("pi".to_string());
    println!("{:?}", r2)
}

I hope this clears some confusion up at least.