Design pattern for heavily connected structure


I’m building a data structure that contains numerous cross-references. I’m currently doing this with a two-tier API. The internal API stores these cross-references as indices that can be used to look up the referent in the main data structure. The public API consists of wrapper classes that have a reference to some object and a reference to the root of the structure, which enables it to provide getters that perform the above-mentioned lookups. Does this make sense? Should I be using some sort of direct references in the structure itself instead of indices?

Simple Example:

struct Root {
   foos: Vec<Foo>,
   bars: Vec<Bar>,

struct Foo {
  id: u32,
  name: String,
  bar: u32

struct Bar {
  id: u32,
  name: String.

struct FooRef<'a> {
  foo: &'a foo,
  root: &'a root,

impl Deref for FooRef { type Target = Foo ... }

impl FooRef {
  pub fn get_bar(&self) -> &Bar {
    self.root.bars.get( as usize)

Unsafe assumptions

Besides the design issues, this raises the issue of assuming that any given instance of FooRef will only be used in relation to the Root instance that it’s related to. However, I can’t think of a way to enforce this at compile time. Instead, when a FooRef is passed to some method of a Root instance, I assert at runtime that the &Root referenced of the FooRef is identical to &self. Using real references instead of indices would get rid of the need for FooRef, but it wouldn’t solve the problem of accidentally passing a member of one Root instance to the method of another Root instance.

Trouble with mutable references

Another problem I’m having is trying to add and return an item in the same method call:

impl Root {
  pub fn new_bar(&mut self, name: &str) -> &Bar {
    let id = self.bars.len();
    let bar = Bar { id: id, name: name.to_owned() };
   // return &bar; // This doesn't work because bar has been moved
  self.bars.get(id).unwrap()  // This works, but is tied to the lifetime of the mutable reference to the Root

This becomes problematic when you then want to use the newly created object:

fn main() {
  let root = Root::new();
  let bar = root.new_bar("name");
  root.new_foo("name", bar);

This fails the borrow checker because there is still a mutable borrow of root left over from the call to new_bar(). It seems to be impossible to make bar (which is, in essence, an immutable borrow of some item in root.bars) last longer than this mutable borrow which was used to create it (but which is no longer needed since the mutation is complete when new_bar() returns.


Here’s a thread about mutable->immutable borrowing:

But even if that borrow was “demoted”, that would only allow additional immutable borrows. It can’t let you take a new &mut Root somewhere else, because that would allow mutating bars too, which might invalidate your &Bar.