I am implementing a graph data structure in Rust. For each node (and also edges - omitted from this snippet) in the graph I have a struct Algorithm (perhaps poorly named) that performs some node and edge based logic. Algorithms require knowledge of the graph connectivity and so cannot belong to a node or edge themselves. They are based on trait polymorphism, although I plan to refactor this to enum polymorphism later. Lastly, I have a solver that works by iterating the nodes of the graph and creating an algorithm for it. Please note, the example is heavily distilled down.
However, I am having two problems. The first is due to the lifetime of the Boxed struct within the algorithms vector.
error: lifetime may not live long enough
--> main.rs:67:29
|
51 | impl<'a> Solver<'a> {
| -- lifetime `'a` defined here
...
63 | pub fn solve(&mut self) {
| - let's call the lifetime of this reference `'1`
...
67 | let algorithm = Box::new(MyAlgorithm {
| _____________________________^
68 | | graph: &mut self.graph,
69 | | });
| |______________^ assignment requires that `'1` must outlive `'a`
I have tried my best to indicate to the compiler that the lifetime of the Algorithm struct should be kept within the lifetime of the Solver struct, but this hasn't worked.
Upon completion of its job, an Algorithm will need to update the nodes and edges of the graph, and so it requires a mutable reference to the graph object. However, this of course is incorrect due to the second mutable borrow.
cannot borrow `self.graph` as mutable more than once at a time
second mutable borrow occurs here
Below is the code.
struct Node {
// Define the Node struct...
}
impl Node {
// Implement methods for Node...
}
struct Graph {
nodes: Vec<Node>,
}
impl Graph {
fn new() -> Self {
Graph {
nodes: Vec::new(),
// Initialize other fields...
}
}
}
trait BaseAlgorithm<'a> {
// Define the trait methods...
}
// Create a MyAlgorithm struct that takes a mutable reference to the graph
struct MyAlgorithm<'a> {
graph: &'a mut Graph,
}
impl<'a> BaseAlgorithm<'a> for MyAlgorithm<'a> {
// Implement the trait methods for MyAlgorithm...
}
struct Solver<'a> {
algorithms: Vec<Box<dyn BaseAlgorithm<'a> + 'a>>,
graph: Graph,
}
impl<'a> Solver<'a> {
fn new() -> Self {
Solver {
algorithms: Vec::new(),
graph: Graph::new(),
}
}
fn add_algorithm(&mut self, algorithm: Box<dyn BaseAlgorithm<'a> + 'a>) {
self.algorithms.push(algorithm);
}
pub fn solve(&mut self) {
// Loop over the nodes vector within Graph
for node in &mut self.graph.nodes {
// add an algorithm with a mutable reference to Graph
let algorithm = Box::new(MyAlgorithm {
graph: &mut self.graph,
});
self.add_algorithm(algorithm);
}
}
}
fn main() {
let mut solver = Solver::new();
solver.solve();
}
If the design can be fixed, then I would greatly appreciate any help achieving that. However, if the design cannot be fixed, is there an idiomatic Rust pattern for achieving the requirements of this logic?
The answer to this problem depends on this question: When do the algorithms need to modify the graph? If the solver is only going to be using one algorithm at a time, then the graph could be passed as a parameter to the function that the solver is calling on the algorithm, rather than storing a mutable reference to it at all times.
If the algorithms really do require mutable access to the graph at all times, then a &mut cannot achieve this. You will need to provide mutability a different way, using interior mutability. If the program is single-threaded, you can use RefCell and if multi-threaded, Mutex or RwLock. So you could store your graph as a RefCell<Graph>. This makes it possible to mutably borrow the graph even when you only have an immutable reference to the RefCell. Then, it might work to simply borrow the ref cell into each of the algorithms like Algorithm{ graph: &self.graph }, but if not, you can make it work by introducing reference counting. This allows you to avoid having to worry about lifetimes, because all the references to the data are counted, and it will be dropped when there are no references left. The refrence counted pointer types are Rc for single-threaded, and Arc for multithreaded. So you could store your graph as Rc<RefCell<Graph>> or Arc<RwLock<Graph>> depending on multithreadedness. Now, with an Rc or Arc, you can call clone() to get a second Rc or Arc pointing to the same data as the first. If that data is interior mutable, like RefCell, Mutex or RwLock, then you can mutably borrow its contents.