Rust – moved variable forbids to borrow itself ("dropped here while still borrowed")

Question

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:

Rust Playground

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.

Answer 1

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:

Rust Playground

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.