I'm trying to write a program that generates mathematical expressions and then evaluates them. Expressions can contain primitive operations (plus, minus, etc.) or other sub-expressions that consist of primitive operations.
The problem is that sub-expressions are local for the created expression and won't be needed anywhere else except their parent expression (so, I should not make them static), but I can't move parent expression somewhere, because local sub-expressions considered as dropped even if I move them to the parent expression struct.
Minimal example:
trait Operation {
fn compute(&self) -> i32;
}
struct SumNumbers {
pub numbers: Vec<i32>,
}
impl Operation for SumNumbers {
fn compute(&self) -> i32 {
let mut result = 0;
for x in &self.numbers {
result += x;
}
result
}
}
struct Expression<'a> {
pub operations: Vec<&'a dyn Operation>,
sub_expr_holder: Vec<Expression<'a>>,
}
// Not working attempt to ensure sub_expr_holder will live longer than operations
// struct Expression<'a, 'b : 'a> {
// pub operations: Vec<&'a dyn Operation>,
// sub_expr_holder: Vec<Expression<'a, 'b>>,
// }
impl Operation for Expression<'_> {
fn compute(&self) -> i32 {
let mut result = 0;
for operation in &self.operations {
result += operation.compute();
}
result
}
}
fn build_single_expression() {
let static_sum2 = SumNumbers {
numbers: vec![1, 1],
};
let static_sum4 = SumNumbers {
numbers: vec![1, 3],
};
let static_sum6 = SumNumbers {
numbers: vec![4, 2],
};
let root_expr = {
let local_expr_sum10 = Expression {
operations: vec![&static_sum4 as &dyn Operation,
&static_sum6 as &dyn Operation],
sub_expr_holder: vec![]
};
let mut root_expr = Expression {
operations: vec![],
sub_expr_holder: vec![local_expr_sum10]
};
root_expr.operations = vec![&root_expr.sub_expr_holder[0], &static_sum2];
// Ideal option would be to keep it immutable:
// let root_expr = Expression {
// operations: vec![&local_expr_sum10, &static_sum2],
// sub_expr_holder: vec![local_expr_sum10]
// };
root_expr
};
let root_expr = &root_expr as &dyn Operation;
let result = root_expr.compute();
assert_eq!(result, 12)
}
The errors I get are:
error[E0597]: `root_expr.sub_expr_holder` does not live long enough
--> src/gep_tools/test.rs:61:38
|
50 | let root_expr = {
| --------- borrow later stored here
...
61 | root_expr.operations = vec![&root_expr.sub_expr_holder[0], &static_sum2];
| ^^^^^^^^^^^^^^^^^^^^^^^^^ borrowed value does not live long enough
...
70 | };
| - `root_expr.sub_expr_holder` dropped here while still borrowed
Even though I move the local_expr_sum10 into the root_expr, the compiler says it doesn't live long enough to be borrowed from root_expr.operations. It seems the second error explains why:
error[E0505]: cannot move out of `root_expr` because it is borrowed
--> src/gep_tools/test.rs:69:9
|
61 | root_expr.operations = vec![&root_expr.sub_expr_holder[0], &static_sum2];
| ------------------------- borrow of `root_expr.sub_expr_holder` occurs here
...
69 | root_expr
| ^^^^^^^^^
| |
| move out of `root_expr` occurs here
| borrow later used here
As I understand, the compiler assumes that I can move the root_expr.sub_expr_holder out of the root_expr struct and it will be dropped while still borrowed by root_expr.operations.
Is there a way how I can force the compiler to forbid move of root_expr.sub_expr_holder out of the struct and therefore let me borrow it? Or any other approach that will let me borrow the local sub-expressions this way?
Edit: I want to use references specifically, because there may be a lot primitive expressions which are reused among all the expressions and it would be waste of memory to copy them each time. Also, the sub-expressions can be used in the root expression several times:
root_expr.operations = vec![&root_expr.sub_expr_holder[0], &static_sum2, &root_expr.sub_expr_holder[0]];
This doesn't make a lot of sense in this minimal example, but in my full code arguments can be passed to the sub-expressions, so it makes sense to put them in a single expression several times. So, again, it would be a waste of memory to copy them multiple times.
Someone marked this question as a duplicate of "self-referential struct problem" (it was re-opened since then), but as I said, this is just 1 of my attempts to solve my problem. As it turned out, the actual problem is called "Multiple Ownership" and as Chayim Friedman suggested, it can be solved with Rc.
As a simple conclusion: if you need to use a local struct that will be dropped at the end of the scope, but you can not move it and have to use references, then go with a reference counter.
A good place to read about Rc and multiple ownership is the Rust Book.
My solution:
use std::rc::Rc;
trait Operation {
fn compute(&self) -> i32;
}
struct SumNumbers {
pub numbers: Vec<i32>,
}
impl Operation for SumNumbers {
fn compute(&self) -> i32 {
let mut result = 0;
for x in &self.numbers {
result += x;
}
result
}
}
struct Expression {
pub operations: Vec<Rc<dyn Operation>>,
}
impl Operation for Expression<> {
fn compute(&self) -> i32 {
let mut result = 0;
for operation in &self.operations {
result += operation.compute();
}
result
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn build_single_expression() {
let static_sum2 = SumNumbers {
numbers: vec![1, 1],
};
let static_sum4 = SumNumbers {
numbers: vec![1, 3],
};
let static_sum6 = SumNumbers {
numbers: vec![4, 2],
};
let root_expr = {
let local_expr_sum10: Rc<dyn Operation> = Rc::new(
Expression {
operations: vec![Rc::new(static_sum4),
Rc::new(static_sum6)]
});
Expression {
operations: vec![Rc::clone(&local_expr_sum10),
Rc::clone(&local_expr_sum10),
Rc::new(static_sum2)],
}
};
let root_expr = &root_expr as &dyn Operation;
let result = root_expr.compute();
assert_eq!(result, 22)
}
}
I'm not sure how good this solution is, but it completely solves my problem, and it should not affect performance.