Nested struct with reference

Question

I have some nested structs and cannot create a back reference to the parent struct. An example:

struct Foo<'a> {
    parent: &'a Bar<'a>,
}

impl<'a> Foo<'a> {
    fn new(parent: &'a Bar) -> Self {
        Foo { parent: parent }
    }

    fn hello_world(&self) -> String {
        self.parent.hello().to_owned() + " world"
    }
}

struct Bar<'b> {
    child: Option<Foo<'b>>,
    data: &'static str,
}

impl<'b> Bar<'b> {
    fn new() -> Self {
        Bar {
            child: None,
            data: "hello",
        }
    }

    fn hello(&self) -> &str {
        self.data
    }

    fn get_foo(&self) -> Option<&Foo> {
        self.child.as_ref()
    }
}

fn main() {
    let bar = Bar::new();
    assert_eq!("hello", bar.hello());
    match bar.get_foo() {
        Some(foo) => assert_eq!("hello world", foo.hello_world()),
        None => (),
    }
}

How can I replace None with Some<Foo> with a reference to Bar? So far I'm not sure that it is possible.

Answer 1

It's not exactly a drop-in solution for your example, but I believe you can create "circular references" as you specify using Arc and RwLock. The API is not exactly the same (e.g., parent is an optional field), I renamed some objects, and it is definitely more verbose, but your tests pass!

use std::sync::{Arc, RwLock};

#[derive(Debug, Clone)]
struct Child {
    parent: Option<Arc<RwLock<Parent>>>
}

impl Child {
    fn new() -> Self {
        Child {
            parent: None
        }
    }

    fn hello_world(&self) -> String {
        let x = self.parent.as_ref().unwrap().clone();
        let y = x.read().unwrap();
        y.hello().to_owned() + " world"
    }
}

#[derive(Debug, Clone)]
struct Parent {
    child: Option<Arc<RwLock<Child>>>,
    data: &'static str
}

impl Parent {
    fn new() -> Self {
        Parent {
            child: None,
            data: "hello"
        }
    }

    fn hello(&self) -> &str {
        self.data
    }

    fn get_child(&self) -> Option<Arc<RwLock<Child>>> {
        self.child.as_ref().map(|x| x.clone() )
    }


}

fn main() {
    let parent = Arc::new(RwLock::new(Parent::new()));
    let child = Arc::new(RwLock::new(Child::new()));

    parent.write().unwrap().child = Some(child.clone());
    child.write().unwrap().parent = Some(parent.clone());

    assert_eq!("hello", parent.read().unwrap().hello());

    {
        let x = parent.read().unwrap();
        match x.get_child() {
            Some(child) => { assert_eq!("hello world", child.read().unwrap().hello_world()); }
            None => {},
        }
    }

}

Answer 2

I have a similar problem, and am not entirely satisfied with the proposed solutions.

If your structure is really nested (i.e. you have a notion of "parent" and "child", with a unique parent for each child), then it seems natural that the parent should own the child(ren). So using Rc/Arc (which are designed to allow for multiple owners) does not look like the right solution -- all the less so because, as @Shepmaster points out, it "encourages" (or at least allows) the creation of cyclic references.

My idea was to have each child hold a raw pointer to its parent:

pub struct Node {
    parent: *mut Node,
    // ...
}

Since a node is owned by its parent, it can only be borrowed (resp. mutably borrowed) while its parent is being borrowed (resp. mutably borrowed). So in that context, it should be safe to cast self.parent to a &Node (resp. &mut Node, if self is mutable).

impl Node {
    pub fn get_parent(&self) -> Option<&Node> {
        unsafe { self.parent.as_ref() }
    }

    pub fn get_mut_parent(&mut self) -> Option<&mut Node> {
        unsafe { self.parent.as_mut() }
    }
}

However, this requires that the address of the parent node never changes (i.e. the parent is never moved). This can be achieved by only ever handling boxed nodes.

pub struct Node {
    parent: *mut Node,
    children: Vec<Box<Node>>,
    // ..
}

impl Node {
    pub fn new(data: &str) -> Box<Node> {
        Box::new(Node {
            parent: std::ptr::null_mut(),
            children: vec![],
            // ..
        })
    }

    pub fn append_child(&mut self, mut child: Box<Node>) -> usize {
        child.parent = self;
        self.children.push(child);
        self.children.len() - 1
    }
}

I implemented a full-fledged example in the playground.