How is Vec implemented in a way that borrowing one element, has the same effect as borrowing the entire Vec?

help
1

I understand how a vector data structure works under the hood. But I am confused about how Rust's ownership system works with it.

The following code works fine:

struct Pair {
    a: i32, b: i32
}

fn main() {
    let mut p = Pair { a: 1, b: 2 };
    let ra = &mut p.a;
    let rb = &mut p.b;
    println!("{}, {}", ra, rb);
    *ra = 11;
    *rb = 12;
}

And outputs

1, 2

However this code:

fn main() {
    let mut v = vec![1, 2, 3];
    let item = &mut v[0];
    v.push(4);
    *item = 10;
}

won't compile. (Because v is mutably borrowed at push while an older borrow (item) is used after that)

It makes sense. Pair and Vec are fundamentally different data structures. (Pair won't move around its "elements" in memory)

My question is how Vec has "annotated" it's (get|index)[_mut] functions in a way that borrowing one element, has the same effect as borrowing the entire Vec container?

2

Well, it's kind of the other way around. Any datastructure that offers any kind of getter will have an signature for such getters of the form:

fn get<'duration> (
    datastructure: &'duration DataStructure,
) -> &'duration Field

fn get_mut<'duration> (
    datastructure: &'duration mut DataStructure,
) -> &'duration mut Field

This is, for instance, the case for IndexMut (and say, Vec<T>):

impl<T> IndexMut<usize> for Vec<T> {
    fn index_mut<'duration> (
        self: &'duration mut Vec<T>,
        idx: usize,
    ) -> &'duration mut T

In all these cases, the 'duration within which the borrow to the Field or to the indexed element lasts is "connected to" / "equal to" the 'duration within which the whole datastructure is borrowed.

And it turns out there is not really a way to, directly, express the disjointness of fields when using getters.

  • So, tuples and struct(ure)s are kind of the exception here. When you & or &mut borrow one .field or .tuple_idx, it involves special magical borrowing rules so that Rust knows the other fields aren't borrowed.

    That is, it is impossible in Rust to define a .x_mut() method / getter so that thing.x_mut() is fully equivalent to &mut thing.x.

The only option / workaround then is to use a "get-them-all(-at-once)" getter, also called a "projection method", which yields a new datastructures containing all the desired simultaneous and non-overlapping borrows at once. Such new data structure can also be called a view type.

Example

Consider:

struct Foo { x: i32, y: i32 }

impl Foo {
    fn x_mut (self: &'_ mut Foo)
      -> &'_ mut i32
    {
        &mut self.x
    }

    fn y_mut (self: &'_ mut Foo)
      -> &'_ mut i32
    {
        &mut self.y
    }
}

let mut foo = Foo { x: 0, y: 0 };

Then, the following works:

let x = &mut foo.x;
let y = &mut foo.y;
::core::mem::swap(x, y); // OK

but the following does not:

let x = foo.x_mut();
let y = foo.y_mut(); // Error, the previous `&mut` borrow on `foo`
                     // must still be active / held so that the
                     // `x` borrow itself remains usable
                     // (as stated by the signature of `fn x_mut()`),
                     // and `x` must remain usable since it is used
                     // in the following line:
::core::mem::swap(x, y);

And the workaround:

impl Foo {
    fn x_and_y_mut (self: &'_ mut Foo)
      -> (&'_ mut i32, &'_ mut i32)
    {
        (&mut self.x, &mut self.y)
    }
}

let (x, y) = foo.x_and_y_mut();
::core::mem::swap(x, y);
  • Here, my "view type" is a simple (&mut i32, &mut i32) tuple, but since tuples can become less readable as the number of fields increases, defining our own wrapper around it can be a more robust approach:
#[non_exhaustive]
pub
struct MutBorrowedFieldsOfFoo<'duration> {
    pub
    x: &'duration mut i32,

    pub
    y: &'duration mut i32,
}

impl Foo {
    pub
    fn fields_mut<'duration> (
        self: &'duration mut Foo,
    ) -> MutBorrowedFieldsOfFoo<'duration>
    {
        let Self { x, y } = self; // abuse the magic of match ergonomics
        MutBorrowedFieldsOfFoo { x, y }
     }
}

let fields = foo.fields_mut();
::core::mem::swap(fields.x, fields.y);

Obviously when the x and y fields of Foo are already public to begin with, there is no point in doing all this; but when privacy is involved, it can become useful:

mod lib {
    #[derive(Default)]
    pub
    struct Foo {
         /* private */
        immutable_x: i32,

        pub
        y: i32,
    }

    impl Foo {
        fn x (self: &'_ Foo)
          -> &'_ i32
        {
             &self.immutable_x
        }
    }
}
use lib::Foo;

fn main ()
{
     let mut foo = Foo::default();
     // let x = &foo.x; /* Error, field `x` is private */
     let x = foo.x();
     let y = &mut foo.y; // Error, `foo` is `&`-borrowed until `x` is no longer used.
     *y = *x;
}

hence the workaround:

#[non_exhaustive]
pub
struct FieldsOfFoo<'duration> {
    pub
    x: &'duration i32,

    pub
    y: &'duration mut i32,
}

impl Foo {
    pub
    fn fields<'duration> (
        self: &'duration mut Foo,
    ) -> FieldsOfFoo<'duration>
    {
        let Self { immutable_x: x, y } = self;
        FieldsOfFoo { x, y }
    }
}

with it:

let mut foo = Foo::default();
let FieldsOfFoo { x, y, .. } = foo.fields();
*y = *x; // OK
4 Likes
3

To add to @Yandros's answer, the "borrowing one borrows all" effect when indexing is a natural result of the trait used to implement indexing syntax.

The best explanation is to look at the source code directly:

In fn index_mut(&mut self, index: Idx) -> &mut Self::Output, the lifetime attached to the &mut Self::Output is coupled to the lifetime in &mut self, so as long as the indexed element is in scope you won't be able to touch the Vec again.

1 Like
4

Thanks, guys. Got it.

5

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.