Rust Vec Borrow - November 2024
tldr;
Use Rc to wrap big structs
Rust borrow checking
In a GC imperative OO language you can loop over a collection, create a new collection in the loop when conditions are met, and then add that new collection to the other one and repeat the loop. Just to spice up the memory usage, as well as adding to the collection we will add the same item to a hashmap.
Its such a simple algorithm, but in rust… “value moved here”, “value borrowed here after move” errors. More on them after the code.
So this is about understanding approaches to this. i.e. creating a collection of things, and also storing those things in as Map.
The payload
We need a payload, pretend its big, but in the case below its small, and clone is cheap, but lets pretend clone is not cheap.
struct Coord {
x: usize,
y: usize
}
impl Coord {
pub fn new(x:usize, y:usize) -> Self {
Coord{x,y}
}
pub fn key(&self) -> usize { self.x * 1000 + self.y }
}
The loop
25 pub fn simpler() -> HashMap<usize, Coord>{
26
27 let mut dict = HashMap::new();
28 let sc = Coord::new(3,4);
29 let mut loop_collection = vec![&sc];
30 for c in loop_collection {
31 let nc = Coord::new(5,6);
32 dict.insert(c.key(), nc);
33 let mut new_collection = vec![&nc];
34 }
35 dict
36 }
Yes, its dumb and incomplete, but this post is a bit of a journey, so lets just fix this error first.
31 | let nc = Coord::new(5,6);
| -- move occurs because `nc` has type `Coord`, which does not implement the `Copy` trait
32 | dict.insert(c.key(), nc);
| -- value moved here
33 | let mut new_collection = vec![&nc];
| ^^^ value borrowed here after move
Lets just switch the rows, and take the ref before we move it into the map:
let mut new_collection = vec![&nc];
dict.insert(c.key(), nc);
Great!
Lets now append to the vec
pub fn simpler() -> HashMap<usize, Coord>{
let mut dict = HashMap::new();
let sc = Coord::new(1,1);
let sc1 = Coord::new(2,2);
let mut loop_collection = vec![&sc, &sc1];
let mut count = 0;
for c in loop_collection {
let nc = Coord::new(3,3);
let mut new_collection = vec![&nc];
let mut replace_collection = vec![];
for inner_c in new_collection {
count+=1;
if count>5 {break;}
let inner_c = Coord::new(4,4);
replace_collection.push(&inner_c);
dict.insert(c.key(), inner_c);
}
}
dict
}
How mad is that? and I called it simpler(), well, whatever. The error is now:
error[E0597]: `inner_c` does not live long enough
--> rust_examples\src\vec_borror\vec_borrow.rs:40:41
|
39 | let inner_c = Coord::new(4,4);
| ------- binding `inner_c` declared here
40 | replace_collection.push(&inner_c);
| ------------------ ^^^^^^^^ borrowed value does not live long enough
| |
| borrow later used here
41 | dict.insert(c.key(), inner_c);
42 | }
| - `inner_c` dropped here while still borrowed
So, by creating the new coord in an inner loop, and adding it to something from an outer scope, we are dead in the water.
We need the Coord we create in the inner loop to live longer, so we could move it into the replace_collection, and change that to be a move, not a borrow.
replace_collection.push(inner_c);
// dict.insert(c.key(), inner_c);
ie, the inferred type of the replace_collection is now Coord rather than &Coord, and to simplify it, get rid of the insert into dict. This compiles. So surely, storing in the dict, and borrowing in the vec must work too, but that was the original form, and it fails. Hmm.
pub fn simpler() -> HashMap<usize, Coord>{
let mut dict = HashMap::new();
let sc = Coord::new(1,1);
let sc1 = Coord::new(2,2);
let mut loop_collection = vec![&sc, &sc1];
let mut count = 0;
for c in loop_collection {
let nc = Coord::new(3,3);
let mut new_collection = vec![&nc];
let mut replace_collection = vec![];
for inner_c in new_collection {
count+=1;
if count>5 {break;}
let wc = Coord::new(4,4);
replace_collection.push(wc);
}
for c in replace_collection {
new_collection.push(&c);
dict.insert(c.key(), c);
}
}
dict
}
I’m so clever. Actualy, not at all:
error[E0382]: borrow of moved value: `new_collection`
--> rust_examples\src\vec_borror\vec_borrow.rs:42:17
|
33 | let mut new_collection = vec![&nc];
| ------------------ move occurs because `new_collection` has type `Vec<&Coord>`, which does not implement the `Copy` trait
34 | let mut replace_collection = vec![];
35 | for inner_c in new_collection {
| -------------- `new_collection` moved due to this implicit call to `.into_iter()`
...
42 | new_collection.push(&c);
| ^^^^^^^^^^^^^^ value borrowed here after move
|
note: `into_iter` takes ownership of the receiver `self`, which moves `new_collection`
--> C:\Users\Jonathan\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib/rustlib/src/rust\library\core\src\iter\traits\collect.rs:268:18
|
268 | fn into_iter(self) -> Self::IntoIter;
| ^^^^
help: consider iterating over a slice of the `Vec<&Coord>`'s content to avoid moving into the `for` loop
|
35 | for inner_c in &new_collection {
|
Oh my, so iterating means the Vec is unusable, and thats fixed by iterating over a ref, which is a slice. OK.
for inner_c in &new_collection {
Which gives another error
error[E0597]: `c` does not live long enough
--> rust_examples\src\vec_borror\vec_borrow.rs:42:37
|
41 | for c in replace_collection {
| - binding `c` declared here
42 | new_collection.push(&c);
| -------------- ^^ borrowed value does not live long enough
| |
| borrow later used here
43 | dict.insert(c.key(), c);
44 | }
| - `c` dropped here while still borrowed
It is again upset that it goes out of scope and is dropped. How about if we move all the collections outside the loop? Then the coord would be preserved, and we would just move it between collections?
let nc = Coord::new(3,3);
let mut new_collection = vec![&nc];
let mut replace_collection = vec![];
for c in loop_collection {
for inner_c in &new_collection {
count+=1;
if count>5 {break;}
let wc = Coord::new(4,4);
replace_collection.push(wc);
}
for c in &replace_collection {
new_collection.push(c);
}
}
Well, the borrow checker isn’t happy.
error[E0502]: cannot borrow `replace_collection` as mutable because it is also borrowed as immutable
--> rust_examples\src\vec_borror\vec_borrow.rs:39:17
|
39 | replace_collection.push(wc);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
40 | }
41 | for c in &replace_collection {
| ------------------- immutable borrow occurs here
42 | new_collection.push(c);
| -------------- immutable borrow later used here
Vec.extend to the rescue.
So, there is an extend, so if we make both vec hold the Coord and not a ref, that works:
let nc = Coord::new(3,3);
let mut new_collection = vec![nc];
for c in loop_collection {
let mut replace_collection = vec![];
for inner_c in &new_collection {
count+=1;
if count>5 {break;}
let wc = Coord::new(4,4);
replace_collection.push(wc);
}
new_collection.extend(replace_collection);
// dict.insert(c.key(), c);
}
No errors. So lets add it back into the HashMap, err, the HashMap has to return out of scope.
Lets write the problem again
We want to create lots of Structs in a function, return them to the caller, but use them in contrived ways in Vecs within the function. There are no threads involved, to std::rc reads like it would sort this out for us.
Reading the documents, the key thing is you can clone an Rc and it will do that without cloning the theoritcally huge Coord - the entire mind game here is to try not clone and copy Coord.
Solution is Rc
pub fn simpler() -> HashMap<usize, Rc<Coord>>{
let mut dict : HashMap<usize, Rc<Coord>> = HashMap::new();
let sc = Coord::new(1,1);
let sc1 = Coord::new(2,2);
let mut loop_collection = vec![sc, sc1];
let mut count = 0;
let nc = Rc::new(Coord::new(3,3));
let mut new_collection = vec![nc];
for c in loop_collection {
let mut replace_collection = vec![];
for inner_c in &new_collection {
count+=1;
if count>5 {break;}
let wc = Rc::new(Coord::new(4,4));
dict.insert(wc.key(), wc.clone());
replace_collection.push(wc);
}
new_collection.extend(replace_collection);
}
dict
}
Obviously I knew this, but getting back into Rust after a C# frenzy is a bit tricky, so starting at the bottom and working my way back up again.