Circular reference issue

help
1

I have two structs Parent and Child, and they reference each other, I can write this code in any other language easily, I know why Rust compile fail, but if I have to solve this situation, how to fix it?

Code is here:

fn main() {
	let parent = Parent { children : vec![], numbers : vec![] };
	let child1 = Child { name : "c1".to_string(), parent : parent };
	let child2 = Child { name : "c2".to_string(), parent : parent };

	parent.add_child(child1);
	parent.add_child(child2);

	child1.add_number_to_parent(1);
	child2.add_number_to_parent(2);
}

struct Parent {
	children : Vec<Child>,
	numbers : Vec<i32>
}

impl Parent {
	fn add_child(&mut self, child : Child) {
		self.children.push(child);
	}

	fn add_number(&mut self, v : i32) {
		self.numbers.push(v);
	}
}

struct Child {
	name : String,
	parent : Parent
}

impl Child {
	fn add_number_to_parent(&mut self, v : i32) {
		self.parent.add_number(v);
	}
}
2

There are a few ways to do this, the underlying theme involving some sort of runtime reference (either RefCell or an index to some collection of Parents). This recent blog post has some nice info on the topic: Fighting the Borrow Checker · Void()

There's a section dedicated to circular references but the whole thing is worth a read.

1 Like
3

FYI, the best (efficient) way to solve this problem is to sidestep it and avoid pointer trees; they're inherently inefficient (lots of allocations and poor memory locality). This is one of the first optimizations one applies to data structures written in Java.

A great way to do this is to have a Tree/Graph struct that stores everything in Vecs (unboxed) and hands out "handles" for manipulating the tree. I recommend you take a look at the petgraph crate.

Obviously, if performance isn't really an issue, you can ignore this advice.

3 Likes
4

Finally, I work fine with RefCell, Weak, and Rc, but lost all compile time check, I do not think it's a good idea except it can compile and work correctly.
Any better idea?

The code is belew:

use std::rc::Rc;
use std::rc::Weak;
use std::cell::RefCell;

fn main() {
	let parent = Rc::new(
		RefCell::new(
			Parent {
				children : vec![],
				numbers : vec![]
			}
		)
	);

	let child1 = Rc::new(
		RefCell::new(
			Child {
				name : "c1".to_string(),
				parent : Rc::downgrade(&parent)
			}
		)
	);

	let child2 = Rc::new(
		RefCell::new(
			Child {
				name : "c2".to_string(),
				parent : Rc::downgrade(&parent)
			}
		)
	);

	parent.borrow_mut().add_child(child1.clone());
	parent.borrow_mut().add_child(child2.clone());

	child1.borrow_mut().add_number_to_parent(1);
	child2.borrow_mut().add_number_to_parent(2);

	println!("{:?}", parent.borrow().numbers);
}

struct Parent {
	children : Vec<Rc<RefCell<Child>>>,
	numbers : Vec<i32>
}

impl Parent {
	fn add_child(&mut self, child : Rc<RefCell<Child>>) {
		self.children.push(child);
	}

	fn add_number(&mut self, v : i32) {
		self.numbers.push(v);
	}
}

struct Child {
	name : String,
	parent : Weak<RefCell<Parent>>
}

impl Child {
	fn add_number_to_parent(&self, v : i32) {
		let p = self.parent.upgrade().unwrap();
		p.borrow_mut().add_number(v);
	}
}
1 Like
5

I think find the node in a tree by handles has cost too.

6

Looking up nodes by handle will generally be practically free; the "handle" will be an index into some array. Looking up children will probably be faster for reasonable sized trees (this really depends on how your graph looks). However, I should stress that this doesn't matter if it's not a bottleneck (I assume this isn't part of some graph search algorithm).

The main problem is that you loose the object-oriented feeling (and go towards a more data oriented design).

Just a note on your design above: it's pretty much what you'd have in Java (minus a generational garbage collector). It feels dirty in Rust because Rust forces you to explicitly opt-in to a lot of things that Java just lets you do implicitly (shared mutable access and runtime memory management).

7

I think you are right.
Btw, in C++, I always use shared_ptr and weak_ptr

8

This is a complete tangent but, if you're interested, shared_ptr versus Rc illustrates two important features of the the Rust type system.

  1. shared_ptr is equivalent to Arc, not Rc. Arc (and shared_ptr) use atomic operations for reference counting while Rc uses simple arithmetic. This makes Rc faster than Arc but multithreading-unsafe. However, that's fine in Rust because Rust can prevent types from being sent across thread boundaries using special traits; only types implementing the Send trait can be sent across threads. C++ doesn't have any way to enforce constraints like this (yet) so it makes the safe-by-default choice and uses atomic variables for reference counting (assuming that you might share the shared_ptr between threads).

  2. In C++, it's really easy to accidentally dereference and copy a shared_ptr. This will cost two atomic operations (atomic increment on copy, atomic decrement on drop). Rust doesn't have implicit copy/move constructors so problems like this can't happen (to copy an Arc/Rc, you have to call clone()).

1 Like