Recursive struct link by reference

[KKKIIO]

I'm writing a recursive algo and sharing state via recursive struct, and it fail to compile.
Here is the simplified code:

struct RecursiveState<'o> {
    outer: Option<&'o mut RecursiveState<'o>>,
    mutable_state: u32,
}

struct Runner<'o> {
    state: RecursiveState<'o>,
}

impl<'o> Runner<'o> {
    fn run_rec(&mut self, level:u32) {
        if level > 0 {
            Runner{
                state: RecursiveState{
                    outer: Some(&mut self.state),
                    mutable_state:0,
                }
            }.run_rec(level-1)
        }
    }
}

fn main() {
    Runner{
        state: RecursiveState {
            outer: None,
            mutable_state: 0,
        }
    }.run_rec(1)
}

The struct is similar to link list. How to write a program like this in Rust?

[2e71828]

@KKKIIO

&'o mut RecursiveState<'o>

The 'o in RecursiveState<'o> says that the RecursiveState cannot live outside the bounds of 'o, and the 'o in &'o mut T says that all accesses to T within the region 'o must occur through the mutable (i.e. exclusive) reference.

There is only one solution that solves both of these constraints at the same time: The RecursiveState value becomes permanently locked to the mutable reference as soon as it's created. This is almost never what you actually want to happen.

---

Beyond that, I can't tell what you're actually trying to calculate: Your simplified code appears to be a fancy no-op which neither returns a value nor has any side effects. Can you describe in prose what you're trying to do?

[KKKIIO]

Thank you for your patience and thorough explanation. I make a more practical (and long) example:

#[derive(PartialEq)]
enum UpValue {
    Local(usize),
    Upvalue(usize),
}

struct Compiler<'o> {
    outer: Option<&'o mut Compiler<'o>>,
    vars: Vec<u32>,
    upvalues: Vec<UpValue>,
}

impl<'o> Compiler<'o> {
    fn compile(&mut self, fun: &Fun) {
        self.vars.copy_from_slice(&fun.vars);
        if let Some(nest) = &fun.nest {
            Compiler {
                outer: Some(self),
                vars: vec![],
                upvalues: vec![],
            }
            .compile(fun);
        }
        for &r in fun.nonlocal_refs.iter() {
            let i = self.resolve_upvalue(r);
            println!("{:?}", i);
        }
    }
    fn resolve_upvalue(&mut self, id: u32) -> Option<usize> {
        if let Some(outer) = self.outer {
            if let Some(index) = outer.vars.iter().position(|&v| v == id) {
                Some(self.add_upvalue(UpValue::Local(index)))
            } else if let Some(index) = outer.resolve_upvalue(id) {
                Some(self.add_upvalue(UpValue::Upvalue(index)))
            } else {
                None
            }
        } else {
            None
        }
    }
    fn add_upvalue(&mut self, upvalue: UpValue) -> usize {
        if let Some(i) = self.upvalues.iter().position(|&v| v == upvalue) {
            i
        } else {
            self.upvalues.push(upvalue);
            self.upvalues.len() - 1
        }
    }
}

struct Fun {
    nest: Option<Box<Fun>>,
    vars: Vec<u32>,
    nonlocal_refs: Vec<u32>,
}

fn main() {
    let root = Compiler {
        outer: None,
        vars: vec![],
        upvalues: vec![],
    };
    root.compile(&Fun {
        nest: Some(
            Fun {
                nest: Some(
                    Fun {
                        nest: None,
                        vars: vec![],
                        nonlocal_refs: vec![1],
                    }
                    .into(),
                ),
                vars: vec![],
                nonlocal_refs: vec![],
            }
            .into(),
        ),
        vars: vec![1],
        nonlocal_refs: vec![],
    });
}

[kornel]

Rust's exclusive temporary loans &mut are not suitable for storing data by reference. This language feature is inappropriate for structs, and will give you endless nonsensical lifetime problems.

To store mutable data by reference, use Box<RecursiveState>. This is the correct type of pointer if you don't intend to paralyze the whole struct with lifetimes.

[KKKIIO]

Thank you for sharing your insights. I can only figure out one solution with Box: move in and out via args and return-value:

#[derive(PartialEq)]
enum UpValue {
    Local(usize),
    Upvalue(usize),
}

struct State {
    outer: Option<Box<State>>,
    vars: Vec<u32>,
    upvalues: Vec<UpValue>,
}

impl State {
    fn resolve_upvalue(&mut self, id: u32) -> Option<usize> {
        if let Some(outer) = self.outer.as_deref_mut() {
            if let Some(index) = outer.vars.iter().position(|v| *v == id) {
                Some(self.add_upvalue(UpValue::Local(index)))
            } else if let Some(index) = outer.resolve_upvalue(id) {
                Some(self.add_upvalue(UpValue::Upvalue(index)))
            } else {
                None
            }
        } else {
            None
        }
    }
    fn add_upvalue(&mut self, upvalue: UpValue) -> usize {
        if let Some(i) = self.upvalues.iter().position(|v| *v == upvalue) {
            i
        } else {
            self.upvalues.push(upvalue);
            self.upvalues.len() - 1
        }
    }
}

struct Compiler {}

impl Compiler {
    fn compile(&self, fun: &Fun, mut state: Box<State>) -> Box<State> {
        state.vars.extend(&fun.vars);
        if let Some(nest) = &fun.nest {
            state = self
                .compile(
                    nest,
                    State {
                        outer: Some(state),
                        vars: vec![],
                        upvalues: vec![],
                    }
                    .into(),
                )
                .outer
                .unwrap();
        }
        for &r in fun.nonlocal_refs.iter() {
            let i = state.resolve_upvalue(r);
            println!("{:?}", i);
        }
        state
    }
}

struct Fun {
    nest: Option<Box<Fun>>,
    vars: Vec<u32>,
    nonlocal_refs: Vec<u32>,
}

fn main() {
    let root = Compiler {};
    root.compile(
        &Fun {
            nest: Some(
                Fun {
                    nest: Some(
                        Fun {
                            nest: None,
                            vars: vec![],
                            nonlocal_refs: vec![1],
                        }
                        .into(),
                    ),
                    vars: vec![],
                    nonlocal_refs: vec![],
                }
                .into(),
            ),
            vars: vec![1],
            nonlocal_refs: vec![],
        },
        State {
            outer: None,
            vars: vec![],
            upvalues: vec![],
        }
        .into(),
    );
}

Any suggestion?

[kornel]

The code compiles. Is it working as you wanted? I'm not sure if you have any unresolved questions about it.

You can simplify if let Some(x) = y else { return None } to let x = y?;

[KKKIIO]

I finally found a succinct way: use box to own the state and std::mem::replace to move state out and in from the &mut self.
Thank you for all the help, much appreciated!