2

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.

Improve this question
3
  • 6
    You can't. See stackoverflow.com/q/32300132/155423; stackoverflow.com/q/28833622/155423; and lots of other questions about circular references. Commented Sep 26, 2016 at 15:03
  • @Shepmaster, is that true? What am I missing in my example here? When I add a line to debug print my parent object, I get a stack overflow error where it tries to print the circular references for parent/child... Commented Sep 26, 2016 at 20:37
  • Yes, it's true; I wouldn't deliberately lie to someone ^_^. A reference is &Foo. In the example in your comment, you have an Arc, which isn't a plain, boring reference, but a more intelligent smart pointer. However, you've created an infinite cycle (parent points to child points to parent points to ...). Generally, that's what Weak references are for. Commented Sep 26, 2016 at 20:43

2 Answers 2

Reset to default
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 => {},
        }
    }

}
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Ah, I completely missed that it wasn't OP with that comment, so I forgot to at-mention you. Make sure you check it out; especially the bit about Weak and the fact that this solution doesn't use references.
@Shepmaster, oh, thanks! But isn't a cloned Arc a kind of reference, at least in a non-strict understanding of the word? Also, surely there are cases where you would want an "infinite cycle" of references (understanding of course that they are dangerous and using them in some ways can cause an SO)?
Yeah, it is a kind of reference (Atomically Reference Counted), but if someone were to ask me how to do something with "references", I wouldn't expect to use an Arc. I'm not actually sure why someone would want a cycle of references. Note that a cycle will cause a memory leak when dropped.
1

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.

Improve this answer

5 Comments

Here is a variant using std::ptr::NonNull instead of a raw pointer: play.rust-lang.org/… . Not sure what the difference is, but the documentation of NonNull says "This is often the correct thing to use when building data structures using raw pointers".
Your children functions can be self.children.get_mut(i).map(|x| &mut **x).
Idiomatic Rust naming suggest that the function names would be foo_bar_mut not foo_mut_bar; The get_ prefix is usually not used for methods.
I think your find function's else clause can be self.children.iter_mut().flat_map(|c| c.find_mut(data)).next().
Thanks @Shepmaster for these advices. A more idiomatic version is here: play.rust-lang.org/…

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.