Recursive type with mutable borrow

help
1

I'm trying to implement a tiny language interpreter, things works fine until I tried to create a Scope struct.

In my head, a Scope definition is as simple as this:


struct Scope<'outer> {
   outer_scope: Option<&'outer mut Scope<'outer>>,
   // ...other fields
}

impl<'o> Scope<'o> {
   fn inner(&mut self) -> Scope<'_> {
      Scope {
          outer_scope: Some(self),
      }
   }
}

Unfortunately, this doesn't really work since 'outer is invariant. So I changed the code to something like this:

struct Scope<'me, 'outer> {
   outer_scope: Option<&'me mut Scope<'outer, 'outer>>,
   // ...other fields
}

impl<'i: 'o, 'o> Scope<'i, 'o> {
   fn inner(&mut self) -> Scope<'_, 'o> {
      Scope {
          outer_scope: Some(self),
      }
   }
}

At least the code compiles for now, but it breaks when I calls scope.inner().inner().
Playground

A workaround can be made with GAT, but this creates types like Scope<'_, Scope<'_, Scope<'_ ....

My question: Is there a simpler way to express recursive type with mutable borrow?

P.S. Yes I know in this specific case I can alloc all scope in an arena and then all reference to the arena somehow. I'm just wondering if this linked-list-like structure is possible in rust.

2

Yes, in general it is possible, however since lifetimes are a compile time feature, it's limited to lists of things that can be enumerated statically. You won't be able to use Rust's built-in knowledge of lifetimes, which is bound up with the notion of scopes in the Rust code that makes up the interpreter, to implement scopes in the code the interpreter interprets, which can be any shape and depth.

This is a common theme for language implementation. You often have to implement the semantics of the implemented language without using the analogous features in the implementation language, because doing so either is a logical impossibility or hamstrings the implementation in some other way.

You probably want some solution that does not involve lifetimes, such as reference counting or having the stack be a Vec<Object> that you index with an integer instead of holding &Objects.

3

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.