Odd problem with lifetimes, parent pointers, and recursion

help
1

I'm writing my own interpreter for a DSL we use at work and ran into a funny problem when implementing nested stack frames.

The general idea is each stack frame has a reference to it's parent (Option<&'a mut Frame<'a>>), with the root frame being stack-allocated and having the type Frame<'static>, then every time the interpreter reaches a call instruction it'll allocate a frame on the (rust) stack, give it a mutable reference to it's parent, then recurse.

I feel like this should be sound and that the lifetimes line up correctly, but the compiler keeps saying these two types are declared with different lifetimes... but data from `frame` flows into `frame` here and points to a non-existent error code (rustc --explain E0623).

Does anyone know where my logic went wrong?

TL;DR:

struct Frame<'a> {
    parent: Option<&'a mut Frame<'a>>,
}

fn execute(frame: &mut Frame<'_>, i: usize) {
    if i > 0 {
        println!("Call {}", i);
        let child_frame = Frame {
            parent: Some(frame),
        };
        execute(&mut child_frame, i - 1);
    }
}

fn main() {
    let mut root = Frame { parent: None };
    execute(&mut root, 5);
}

(playground)

The above errors with the output:

   Compiling playground v0.0.1 (/playground)
error[E0623]: lifetime mismatch
 --> src/main.rs:9:26
  |
5 | fn execute(frame: &mut Frame<'_>, i: usize) {
  |                   --------------
  |                   |
  |                   these two types are declared with different lifetimes...
...
9 |             parent: Some(frame),
  |                          ^^^^^ ...but data from `frame` flows into `frame` here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0623`.
error: Could not compile `playground`.
2 Likes
2

This is a good one - seemingly simple, yet doesn’t work :slight_smile:. In short, I don’t think it’s possible to express this. I’m on mobile so the below may be mumble jumble.

struct Frame<'a> {
   parent: Option<&'a mut Frame<'a>>,
}

First issue is the mutable reference - that makes the parent invariant in 'a. In execute(), it means you won’t be able to borrow the local child_frame for long enough. You can see that here.

Next logical step is to give the borrow and Frame different lifetimes:

struct Frame<'a, 'b> {
   parent: Option<&'a mut Frame<'b, 'b>>,
}

This is awkward because the parent frame can’t have 'a in it or else we’re back to the problem above - so we shove 'b in there twice.

So now Frame<'b, 'b> is invariant. One may imagine that execute looks like this now:

fn execute<'a, 'b>(frame: &'a mut Frame<'b, 'b>, i: usize) {
    if i > 0 {
        println!("Call {}", i);
        let child_frame = Frame {
            parent: Some(frame),
        };
        execute(&mut child_frame, i - 1);
    }
}

Now Frame<'b, 'b> is invariant. When trying to resolve regions/lifetimes for the recursive execute call, the compiler can figure out what 'a to use (ie region for that is the call itself, just that statement), but can’t figure out what to do with 'b. Typically a mutable borrow is reborrowed for a shorter lifetime, but how do we do that with Frame<'b, 'b>? We can’t shorten the 'b for the recursive call (because invariance prevents that). And if we were somehow able to pass the 'b through as-is, so to speak, what would that actually mean? If we look at the stack of borrows, it seems it would end up being the lifetime of the outermost frame, where the root frame is created - that’s likely not what you want to represent here anyway, I suspect (because you’d presumably want successively smaller borrows of each child frame so you can mutate it accordingly - or else why is the parent behind a mutable reference?).

Personally, I’d explore different approaches. For example, maintain frames in a, say, Vec, pass this Vec to child frames, and give them access to parent frames via an index (frame id) into that Vec.

4 Likes
3

Thanks @vitalyd, I had a feeling it might have something to do with subtyping/variance and that &'a mut Frame<'b>.

I thought of using a Vec and indice or Rc<RefCell<Frame>> as workarounds but both solutions aren't very satisfactory. Further research into intrusive singly-linked lists (which is effectively what my Frame is) doesn't seem promising either.

It sounds like those other solutions might be better in the long run though. I'd like a nice way to mutably walk up the stack (e.g. say you want to update a variable in a parent scope) and you can't really write a mutable iterator over my original stack frame type (the iterator hands out a &mut Frame but also needs to hold an &mut Frame with the same lifetime) meaning every function which wants to walk the stack would need to add recursion boilerplate. This just isn't a problem with the Vec<Frame> solution.

4

This problem with stacks and lifetimes reminds me of this blog post about the implementation (at that time) of ::std::collections::BTreeMap. Around 40% of page scrolling (:sweat_smile:) they talk about a stack, and how it used raw *mut pointers since the recursive lifetime constraints weren't really expressible with &'? mut.
In order to make the required unsafe sound, they add phantom lifetimes and an API with very precise lifetime bounds that calls the given closure.

In other words, there might be a way to craft and "hack" a solution, but it requires unsafe to make rust "let you define the lifetimes", and thus a very very precisely defined phantom lifetimes + closure interaction.

Pretty complex stuff I dare say (I, for instance, haven't completely understood all the shenanigans involved).

An easier solution, just requiring a minor runtime cost, would be to use reference counting (with maybe weak pointers and some runtime unwrapping).

That's what I'd start with, and only try the complicated unsafe (and thus bug-prone and dangerous!) stuff if reference counting ends up having an impactful performance cost.

1 Like
5

Yep. Indices as "safe" raw pointers is a trick that often works surprisingly well, and you are only paying for occasional bound checks. But if you need mutation you will need to wrap the main Vec in a RefCell before giving (shared) references to it to the Frames.

struct Frames /* = */ (Vec<Frame>);

struct Frame {
  index: usize,
  // remaining Frame data
}

impl Frames {
  fn execute(&mut self, /* frame: usize, */ depth: usize)
  {
    // assert!(self.len() == frame + 1, "Frame index out of bounds");
    let frame = self.0.len().checked_sub(1).expect("Got no frames");
    if let Some(next_depth) = depth.checked_sub(1) {
      let child_frame = Frame {
        index: frame + 1,
        // data
      };
      self.0.push(child_frame);
      self.execute(next_depth);
      let _ = self.0.pop();
    }
  }
}
fn main ()
 {
   const MAX_DEPTH: usize = 5;
   let root_frame = Frame {
     index: 0,
     // data
   };
   let mut frames = Frames(Vec::with_capacity(1 + MAX_DEPTH));
   frames.0.push(root_frame);
   frames.execute(MAX_DEPTH);
   let _ = frames.0.pop();
}