5

I'm implementing an algorithm, and in order to maintain the desired time complexity, I would like to hold a pointer to an element of a Vec while the Vec is being moved.

Specifically, something like this:

fn main() {
    let mut v: Vec<usize> = vec![1, 2, 3];
    let ptr: *mut usize = &mut v[1] as *mut usize;
    let mut u: Vec<usize> = v;
    assert!(ptr == &mut u[1] as *mut usize);
    println!("{}", unsafe { *ptr });
}

The actual code is more complicated, and involves a tree-like data structure where each vertex owns a Vec of children. I'm not asking about coding style here, but my question is about whether this code can be relied on to do what I think it does.

Since Vec has to hold its content on the heap, and moves are equivalent to memcpy in Rust, I think the fact that Vec is movable would imply that my code is sound (i.e. not undefined behaviour). Is this correct?

Bernard
  • 5,209
  • 1
  • 34
  • 64
  • Well unless the moved vector is then resized beyond its capacity (by adding elements), in which case you're left with a dangling pointer (since all the data is copied into another location with bigger capacity) – Alexey S. Larionov Aug 24 '20 at 15:58
  • Is `Vec` really *guaranteed* to hold its element on the heap in any case? Would it potentially be allowed to do some small-vector-optimizations (i.e. hold elements in an array if there are e.g. only up to 4 elements)? – phimuemue Aug 24 '20 at 15:59
  • @AlexLarionov I can guarantee that the moved vector isn't resized beyond its capacuty. – Bernard Aug 24 '20 at 16:02
  • @phimuemue Well, `Vec` has `from_raw_parts` and `into_raw_parts`, and I don't think they're implementable if there are small vector optimizations. – Bernard Aug 24 '20 at 16:03
  • 2
    @phimuemue _Vec will never perform a "small optimization" where elements are actually stored on the stack_ ([ref](https://doc.rust-lang.org/std/vec/struct.Vec.html#guarantees)) – Ömer Erden Aug 24 '20 at 16:06

1 Answers1

3

You can do it like this:

fn main() {
    let mut v: Vec<usize> = vec![1, 2, 3];
    let ptr: *mut usize = &mut v[1] as *mut usize;
    let mut u: Vec<usize> = v;
    assert!(ptr == &mut u[1] as *mut usize);
    // I copied this from Stack Overflow without reading the surrounding prose 
    println!("{}", unsafe { *ptr });
}

You should document the unsafe block with exactly what the safety conditions are and how you are upholding them. In this case...

  1. The Vec's elements are heap-allocated:

    If a Vec has allocated memory, then the memory it points to is on the heap

  2. You have not changed the backing allocation during the time of the move. This could be due to any modification of the Vec that results in a resize or destruction.

  3. No aliasing reference to the same element (including anything that could reach the same element) exists when you try to use the reference.

For this example, I'd just use an index (1). For your tree case, I'd try to use a vector of indices. Benchmark to see if there's a noticeable difference.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
  • While in the unsafe block, both the `Vec` itself and an `&mut usize` will coexist, and the compiler wouldn't know that the `&mut usize` came from the `Vec`. Is it acceptable to have a mut reference to `u` coexist with a mut reference to `u[1]` in general (as long as I don't have a second reference to `u[1]`)? – Bernard Aug 24 '20 at 16:11
  • `u` doesn't have any references within it, only more raw pointers. Having a mutable reference to `u` would be suspicious [because that's not allowed normally](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=612d0ab023ad17260e8a11a72d55d2ab). You'd be able to get a second mutable reference to the element. – Shepmaster Aug 24 '20 at 16:20
  • See also [Simultaneous mutable access to arbitrary indices of a large vector that are guaranteed to be disjoint](https://stackoverflow.com/q/55939552/155423); [How can I use multiple items in a Vec at a time in Rust?](https://stackoverflow.com/q/41285979/155423); [How to get mutable references to two array elements at the same time?](https://stackoverflow.com/q/30073684/155423) – Shepmaster Aug 24 '20 at 16:22
  • Sorry, I think I wasn't clear. I mean something like [this](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=d60946689083d8a5a1a69d063c9225f6). Yes, it wouldn't be possible in safe Rust to do such a thing. But if I wanted to mutate the element in the pointer via an API that expects a reference (as per the linked code), would that immediately become UB because of the coexistence of a mut ref together with `u`? I could take another mut ref by doing `&mut u[1]`, and I think that would be immediate UB; but if I didn't do such a thing, would the code remain well-defined? – Bernard Aug 24 '20 at 16:33
  • 1
    As I mentioned, `u` doesn't have any references within it. Since it has no references, there can be no aliasing with another reference. – Shepmaster Aug 24 '20 at 16:47