use std::collections::HashMap;
#[allow(dead_code)]
struct AlgorithmNode {
node: i32,
index: i32,
}
#[allow(dead_code)]
struct AlgorithmData<'algorithm> {
stack: Vec<&'algorithm AlgorithmNode>,
node_index_to_node: HashMap<i32, AlgorithmNode>, //actually owns the algorithmNodes
result: Vec<i32>,
}
impl<'algorithm> AlgorithmData<'algorithm> {
fn new() -> Self {
AlgorithmData {
stack: vec![],
node_index_to_node: HashMap::new(),
result: vec![],
}
}
fn some_algorithm(&'algorithm mut self) { //also doesn't work with just &mut self
let v = self.node_index_to_node.get_mut(&0).unwrap(); //TODO unwrap temporary
v.index = v.index+1;
let v = &*v; //convert to non mut reference
self.stack.push(v);
/*
some more stuff that fills result
*/
}
}
fn main() {
let mut algorithm_data = AlgorithmData::new();
algorithm_data.node_index_to_node.insert(0, AlgorithmNode{node:0,index:0});
algorithm_data.some_algorithm();
let _x = algorithm_data.result;
}
The code doesnt compile because I get the following error:
error[E0505]: cannot move out of algorithm_data.result because it is borrowed
However I do not understand this error. In my head the algorith_data reference stops existing as soon as some_algorithm() is done and then I should be able to move the result out of the struct?
Is there some way to stop the reference from existing, or how do I solve this issue?
I also tried changing the function signature to
fn some_algorithm(&mut self)
but then I get an error that the lifetime of self must outlive 'algorithm, and I wouldn't know how to fix that issue
this is an anti-pattern, you ended up self-borrowed. just remove the lifetime specifier on self, let the compiler infer the elided lifetime for you.
this is problematic too, you cannot "downgrade" an mut borrow into a immutable borrow, also you are making a self-referential strucuture here, which is invalid.
don't store refereces in the stack, store indices instead might be fixing the problem. but I don't know what algorithm you are trying to implement, so can't say for sure if it's a valid solution.
Good old self-referencing data. This approach cannot work, rustc does not natively support having both the owner and a borrow of the same data stored in the same data structure. That’s why it doesn’t work with either of
fn some_algorithm(&mut self)
or
fn some_algorithm(&'algorithm mut self)
The latter also matches a common anti-pattern, i.e. the type of self would be of the form &'a mut Struct<'a>[1], i.e. a struct with a lifetime parameter borrowed mutably for that same lifetime. It’s almost unworkable and almost never what you want.
As for workarounds, typically there are about three options
split up the struct between borrowed and owned data
use some form of indices instead of actual references
use crates[2] that can help with self-referencing data
In this case, it seems perhaps most straightforward to go with the second option of simply storing your node indices in the stack instead of references.
more precisely, the type here is &'algorithm mut AlgorithmData<'algorithm>↩︎
I have modified to extract the split the struct between the borrowed and owned data like suggested and now I am getting this issue:
use std::collections::HashMap;
#[allow(dead_code)]
struct AlgorithmNode {
node: i32,
index: i32,
}
#[allow(dead_code)]
struct AlgorithmData<'algorithm> {
stack: Vec<&'algorithm AlgorithmNode>,
result: Vec<i32>,
}
impl<'algorithm> AlgorithmData<'algorithm> {
fn new() -> Self {
AlgorithmData {
stack: vec![],
result: vec![],
}
}
fn some_algorithm(&mut self, nodes: &'algorithm mut HashMap<i32, AlgorithmNode>, node: i32) { //also doesn't work with just &mut self
let v = nodes.get_mut(&node).unwrap(); //TODO unwrap temporary
v.index = v.index+1;
let v = &*v; //convert to non mut reference
self.stack.push(v);
/*
some more stuff that fills result
*/
}
}
fn main() {
let mut algorithm_data = AlgorithmData::new();
let mut nodes: HashMap<i32, AlgorithmNode> = HashMap::new(); //owns the nodes. can't be part of algirthm data because that creates a self reference and is not possible to do in safe rust
nodes.insert(0, AlgorithmNode{node:0,index:0});
nodes.insert(1, AlgorithmNode{node:1,index:1});
for i in 0..2 {
let index = i as i32;
algorithm_data.some_algorithm(&mut nodes, index);
}
let _x = algorithm_data.result;
}
This gives me the error
nodes was mutably borrowed here in the previous iteration of the loop
I believe I could probably solve this with refcells, or by storing indices on the stack but I was wondering if theres another simple solution that I am missing ?
Therefore, you cannot store a reference to a node in the Vec (stack). A reference to a node (stored in the HashMap) is invalid as soon as you modify the HashMap, since the objects in the HashMap can be moved to a difference locations in memory -- they are not frozen in the HashMap.
In general you should not store references in data collections, or in structures. This is possible in certain cases, but is a more advanced technique. If you are just starting with Rust, don't try this yet.
You could store the node's key (i32) in the Vec, and then lookup the node in the HashMap when you need it. This is what @steffahn was saying here:
In this case, it seems perhaps most straightforward to go with the second option of simply storing your node indices in the stack instead of references.
Or you could store a separate copy of the node in the Vec, in addition to in the HashMap. This works well if a node's contents are never changed after adding it to the HashMap.
If the data you need to modify is actually Copy like i32 is, and you're ok being single threaded, you can use Cell.
&mut requires exclusivity so there's no way to use get_mut to pull out multiple references that are stored in the Vec; once you've used get_mut to get a single borrowed item out of the HashMap, the entire map remains exclusively borrowed until the borrowed item goes away.