3

I have a program that uses a QuadTree. This tree stores mutable borrows to data that is owned by another container (a Vec). I rebuild the QuadTree every game loop, but I do not want to reallocate, so I clear the underlying Vecs of the QuadTree instead of reconstructing it from scratch.

A simplified example that demonstrates the same problem is shown below. Instead of a QuadTree, here I am just using another Vec as this has identical issues.

struct A; fn main() { let mut owned_data = vec![A, A, A]; let mut mut_borrowed_data = vec![]; '_outer: loop { mut_borrowed_data.clear(); '_inner: for borrow in &mut owned_data { mut_borrowed_data.push(borrow); } } }

This gives the error:

error[E0499]: cannot borrow `owned_data` as mutable more than once at a time --> src\main.rs:8:30 | 8 | '_inner: for borrow in &mut owned_data { | ^^^^^^^^^^^^^^^ `owned_data` was mutably borrowed here in the previous iteration of the loop

The issue isn't really that I am mutably borrowing in a previous iteration of the outer loop. If I remove the mut_borrowed_data.push(data); it compiles, because the borrow checker realises that the mutable borrow of owned_data is dropped at the end of each outer loop, therefore the number of mutable borrows is a max of 1. By pushing into mut_borrowed_data, this mutable borrow is moved into this container (Please correct me if I am wrong here), therefore it isn't dropped and the borrow checker is not happy. If I did not have the clear there would be multiple copies of the mutable borrow, and the borrow checker is not smart enough to realise that I only push into the mut_borrowed_data once, and that I clear it every outer loop.

But as it stands, there is only one instance of the mutable borrow at any one time, so is the following code safe/sound?

struct A; fn main() { let mut owned_data = vec![A, A, A]; let mut mut_borrowed_data = vec![]; '_outer: loop { mut_borrowed_data.clear(); '_inner: for borrow in &mut owned_data { let ptr = borrow as *mut A; let new_borrow = unsafe { &mut *ptr }; mut_borrowed_data.push(new_borrow); } } }

This now compiles. The mutable borrow of owned_data (named borrow) is not moved into the mut_borrowed_data and therefore it is dropped at the end of the outer loop. This means owned_data is only mutable borrowed once. The unsafe code takes a copy of the pointer to the data, dereferences it and creates a new borrow to that. (again, please correct me if I am wrong). Because this uses a copy and not a move, the compiler allows borrow and new_borrow to exist at the same time. This use of unsafe could break the borrow rules, but as long as I do not use borrow after I have created new_borrow, and as long as I clear mut_borrowed_data, then I think this is safe/sound.

Moreover, (I think) the guarantees given by the borrow checker still hold as long as I clear the mut_borrowed_data vec. It won't let me push into mut_borrowed_data twice in one loop, because the new_borrow is moved after it is first inserted.

I do not want to use a RefCell as I want this to be as performant as possible. The whole purpose of the QuadTree is to increase performance so I want to make any overhead it introduces as lean as possible. Incrementing the borrow count is probably cheap, but the branch (to check if that value is <= 1), the indirection, and the decreased simplicity of my data, are too much for me to feel happy about.

Is my use of unsafe here safe/sound? Is there anything that could trip me up?

Improve this question
2
  • I think this is sound. slice::split_at_mut does essentially the same thing, using unsafe to guarantee that two &muts obtained from the same container do not overlap. Commented Jan 11, 2023 at 12:38
  • @IvanC Thank you for the speedy reply. Is my understanding of how the borrows and moves work correct? I would be more confident using this if I knew exactly why it worked. Commented Jan 11, 2023 at 12:42

1 Answer 1

Reset to default
2

Let's start with that: your code is safe, and also pretty sound.

The unsafe code takes a copy of the pointer to the data, dereferences it and creates a new borrow to that. (again, please correct me if I am wrong). Because this uses a copy and not a move, the compiler allows borrow and new_borrow to exist at the same time.

This is not accurate. The reason borrow and new_borrow can exist at the same time is not because raw pointers are copied while references are moved, but because when you converted the reference to a raw pointer you detached the lifetime chain - the compiler can no longer track the source of new_borrow.

It won't let me push into mut_borrowed_data twice in one loop, because the new_borrow is moved after it is first inserted.

Yes, but also no:

'_outer: loop { mut_borrowed_data.clear(); '_inner: for borrow in &mut owned_data { let ptr = borrow as *mut A; let new_borrow = unsafe { &mut *ptr }; mut_borrowed_data.push(new_borrow); mut_borrowed_data.push(new_borrow); } } // Does not compile: // error[E0382]: borrow of moved value: `new_borrow` // --> src/lib.rs:12:32 // | // 10 | let new_borrow = unsafe { &mut *ptr }; // | ---------- move occurs because `new_borrow` has type `&mut A`, which does not implement the `Copy` trait // 11 | mut_borrowed_data.push(new_borrow); // | ---------- value moved here // 12 | mut_borrowed_data.push(new_borrow); // | ^^^^^^^^^^ value borrowed here after move // However, this does compile, and it is still Undefined Behavior: '_outer: loop { mut_borrowed_data.clear(); '_inner: for borrow in &mut owned_data { let ptr = borrow as *mut A; let new_borrow = unsafe { &mut *ptr }; mut_borrowed_data.push(new_borrow); eprintln!("{borrow}"); // Use the old `borrow`. } }

You can make it a bit safer by shadowing the original borrow, so it can no longer be used:

'_outer: loop { mut_borrowed_data.clear(); '_inner: for borrow in &mut owned_data { let borrow = unsafe { &mut *(borrow as *mut A) }; mut_borrowed_data.push(borrow); } }

But it is still not perfect. The reason is that since you detach the lifetime, you get an unlimited, essentially 'static reference. This means it can be used longer than allowed, for example:

use std::sync::Mutex; #[derive(Debug)] struct A; static EVIL: Mutex<Option<&'static mut A>> = Mutex::new(None); fn main() { let mut owned_data = vec![A, A, A]; let mut mut_borrowed_data = vec![]; '_outer: loop { if let Some(evil) = EVIL.lock().unwrap().as_deref_mut() { eprintln!("HaHa! We got two overlapping mutable references! {evil:?}"); } mut_borrowed_data.clear(); '_inner: for borrow in &mut owned_data { let borrow = unsafe { &mut *(borrow as *mut A) }; mut_borrowed_data.push(borrow); } *EVIL.lock().unwrap() = mut_borrowed_data.pop(); } }

This does not mean this approach is bad (it is probably what I would use) but you need to be careful.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Am I correct that this problem inherently requires unsafe, or dynamic borrow checking rules? The advice I often see in forums is that 99% of the time you can use safe rust to achieve the same results by rethinking the design. But here I inherently need to move borrowed data into a container owned by an outer scope, therefore the borrow checker will never be able to understand that this container only has one copy of the borrow. The container must be owned by an outer scope, as I need the capacity to persist between usages. Is my wording / understanding of this problem correct?
@Blue7 I think it is possible to encapsulate this pattern in a safe and sound API, but I have to implement it to be sure...
@Blue7 Here it is. I believe it is sound.
@Blue7 Hmm... I'm not so sure anymore it is sound. But I believe it is possible to make it sound.
This is all really interesting! Thank you so much for your time helping me with this. My understanding of the language is improving.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.