Struct with a mutable reference to another instance of the same type

Question

How can I make a struct with an optional mutable reference to it's own type. Not self-referential, so the instance is different, for example

struct Environment<'a> {
    outer: Option<&'a mut Environment<'a>>,
    // Can be swapped for any other data
    variables: HashMap<Identifier, Expression>, 
}

I've also experimented with:

struct Environment<'a, 'b> {
    outer: Option<&'a mut Environment<'b, 'b>>, //...

but to no success.

I would like to be able to:

• Keep it as reference (no Box), since the instances would be on stack
• Keep it without extra runtime performance hit (Rc/RefCell)
• Change variables in arbitrarily-outer environment
• NOT be able to change the value behind outer.outer (as I understand this could lead to unsoundness)
• Keep an inner environment acting as-if it was borrowing the outer environment mutably (exclusively) as long as it exists (so no two inner/children from the same outer/parent)

So a sort of split borrow. Where the variables up the outer chain are borrowed &mut, but outer is & and the Environment as a whole is also &mut'd

I understand that the problem is that &mut T is invariant over T. Is there some way I can make &mut T become covariant as if it was &T?

Edit: Desired example usage (doesn't compile)

struct Environment<'a> {
    outer: Option<&'a mut Environment<'a>>,
    value: i32,
}

impl<'a> Environment<'a> {
    fn new(value: i32) -> Self {
        Self { outer: None, value }
    }
    
    fn child<'b>(&'b mut self, value: i32) -> Environment<'b>
    where
        // This is the relationship I would want
        // parent environment outlives child environment
        'a: 'b
    {
        Self { outer: Some(self), value }
    }
}

fn user_that_creates_child(env: &mut Environment) {
    let child_env = env.child(11);
    // Do something with the child
    child_env.outer.unwrap().value = 8; // This should be possible
    // child_env.outer.unwrap().outer = // This shouldn't be
}

fn main() {
    let mut root_env = Environment::new(7);
}

Compiler suggest the inverse of the relationship I want, ie where 'b: 'a for the child function

Answer 1

The problem is that you don't need one lifetime. Even two won't help. You need infinitely many lifetimes, or a dynamic set of lifetimes, to track each dynamic child. This of course can't work.

As far as I know what you want cannot be written in safe Rust.

With unsafe Rust it is possible to do soundly, as long as you never mutate the outer pointer. The reason this is not safe is because the compiler cannot prove that. There are two ways to tackle this case with unsafe Rust. One is to store the parent pointer as raw pointer:

use std::collections::HashMap;
use std::marker::PhantomData;
use std::ptr::NonNull;

struct Environment<'a> {
    outer: Option<NonNull<Environment<'a>>>,
    value: HashMap<i32, String>,
    _marker: PhantomData<&'a ()>,
}

// Needed because of the `NonNull`, safe as long as the keys and values are `Send` and `Sync`.
unsafe impl Send for Environment<'_> {}
unsafe impl Sync for Environment<'_> {}

impl<'a> Environment<'a> {
    fn new() -> Self {
        Self {
            outer: None,
            value: HashMap::new(),
            _marker: PhantomData,
        }
    }

    fn child<'b>(&'b mut self) -> Environment<'b> {
        Self {
            outer: Some(self.into()),
            value: HashMap::new(),
            _marker: PhantomData,
        }
    }
    
    fn map_depth(&self, depth: u32) -> Option<&HashMap<i32, String>> {
        unsafe {
            let mut this = NonNull::from(self);
            for _ in 0..depth {
                this = this.as_ref().outer?;
            }
            Some(&this.as_ref().value)
        }
    }
    
    fn map_depth_mut(&mut self, depth: u32) -> Option<&mut HashMap<i32, String>> {
        unsafe {
            let mut this = NonNull::from(self);
            for _ in 0..depth {
                this = this.as_mut().outer?;
            }
            Some(&mut this.as_mut().value)
        }
    }
}

The other, IMHO more safe, is to use interior mutability: just like wrapping the value in a RefCell, just using UnsafeCell instead of RefCell to avoid runtime overhead:

use std::cell::UnsafeCell;
use std::collections::HashMap;

struct Environment<'a> {
    outer: Option<&'a Environment<'a>>,
    value: UnsafeCell<HashMap<i32, String>>,
}

// Needed because of the `UnsafeCell`, safe as long as the keys and values are `Sync`.
unsafe impl Sync for Environment<'_> {}

impl<'a> Environment<'a> {
    fn new() -> Self {
        Self {
            outer: None,
            value: UnsafeCell::new(HashMap::new()),
        }
    }

    fn child<'b>(&'b mut self) -> Environment<'b> {
        Environment {
            outer: Some(self),
            value: UnsafeCell::new(HashMap::new()),
        }
    }

    fn map_depth(&self, depth: u32) -> Option<&HashMap<i32, String>> {
        let mut this: &Environment = self;
        for _ in 0..depth {
            this = this.outer?;
        }
        Some(unsafe { &*this.value.get() })
    }

    fn map_depth_mut(&mut self, depth: u32) -> Option<&mut HashMap<i32, String>> {
        let mut this: &Environment = self;
        for _ in 0..depth {
            this = this.outer?;
        }
        Some(unsafe { &mut *this.value.get() })
    }
}