Structs with circular relations

[matrixdev]

Firstly I'm aware this is not the best architecture, but project requires this.

I have a problem of multiple types/structs implementations requiring mutable access to each others. For example i have A, B and C where (this is just an example):

• A needs &mut B and &mut C
• B needs &mut A and &mut C
• C needs &mut A and &mut B

I don't want to use Arc/RefCell everywhere so I searched some more. Other forum posts recommend to use some kind of a pool, store only ids and get mutable reference by id:

struct Pool {
  a: Vec<A>,
  b: Vec<B>,
  c: Vec<C>,
  // many more
}

// what I would like is this:
impl A {
  fn mutate(&self, pool: &mut Pool) {
    pool.b.get_mut(self.b_id).mutate();
    pool.c.get_mut(self.c_id).mutate();
  }
}

But the problem with this is that I can't pass the Pool object via mutable reference to the A, because Pool contains that A and borrow checker doesn't like it. So instead I had to adapt:

struct ADependencies<'a> {
  b: &'a mut Vec<B>,
  c: &'a mut Vec<C>,
}

impl A {
  fn mutate(&self, dependencies: ADependencies) {
    dependencies.b.get_mut(self.b_id).mutate(BDependencies { ... });
    dependencies.c.get_mut(self.c_id).mutate(CDependencies { ... });
  }
}

a.mutate(ADependencies {
  b: &mut pool.b,
  c: &mut pool.c,
});

This works but the problem is that I now need to create all these XDependencies structs for each object and it is a lot of boilerplate code. Moving all functions from objects to the level of the Pool object is not really feasible.

I also would like to avoid following (doesn't play well with nested calls):

a.mutate(pool.b.get_mut(a.b_id), pool.c.get_mut(a.c_id));

Is there any other way around it? Maybe I'm missing something?

[RedDocMD]

@matrixdev

Other forum posts recommend to use some kind of a pool, store only ids and get mutable reference by id

Correct me if I'm wrong, but I think the advice you were given was to create a Pool which can give you a mutable-reference via an immutable reference to the Pool - which means you are basically implementing a fancier version of RefCell manually using UnsafeCell internally and keeping track of the borrows manually.

@matrixdev

I don't want to use Arc/RefCell everywhere

Why not?

@matrixdev

Firstly I'm aware this is not the best architecture, but project requires this

Perhaps it would be more fruitful to use this road-block to rethink your architecture. Judging by the way you're going about with this, you're going to end up with very painful API's very fast.
It really would make a lot of sense to think why you need an effectively circular chain of mutable references.
Sometimes, there isn't a good way around - so you have to bite the bullet and just do it.

[kornel]

No, this won't work.

Borrow checking model fundamentally doesn't support self-referential structs. On top of that, &mut is for temporary exclusive access, and circular relation breaks that.

You will have to use Arc, or at least shared (not exclusive) references from a single memory pool, and use interior mutability to set up the circular references.

Basically, you do need Arc/Mutex, and you can't just not want them Temporary scope-limited strictly tree-shaped references are just not the tool for this.

[matrixdev]

@RedDocMD

Why not?

I would like to at least try to play nice with the borrow checker.

@RedDocMD

It really would make a lot of sense to think why you need an effectively circular chain of mutable references.

This is a very simplified example (real tree is much deeper and contains more objects):

RendererEngine
  - Textures - can be shared between surfaces
  - TextureGenerators - needs mutable access to the Textures to update it, can be called/triggered from outside
  - SurfacesToScreen
    - Entities - needs immutable access to the Textures to render it
  - SurfacesToTexture
    - Entities - needs immutable access to the Textures to render it
    - Rasterizer - needs mutable access to the Textures to render to it

[geebee22]

You should use Rc/RefCell, or if the data is shared across threads, Arc/Mutex or Arc/RwLock.

Rc/RefCell is extremely efficient.

[RedDocMD]

@matrixdev

I would like to at least try to play nice with the borrow checker.

Using RefCell and Rc is not a sign of failure. It addresses a limitation of the borrow-checker. Use it if it is the natural solution (which I think it is)

[VorfeedCanal]

@RedDocMD

It addresses a limitation of the borrow-checker.

It's not even limitation of borrow-checker. The whole static borrow-checking model assumes that you don't circular relationships.

RefCell moves that model to runtime where it belongs if you really need relationship which doesn't fit that model.

And yes, if you really couldn't avoid circular relationships then RefCell and Rc is the way to do them.

[droundy]

@matrixdev

struct Pool {
  a: Vec<A>,
  b: Vec<B>,
  c: Vec<C>,
  // many more
}

// what I would like is this:
impl A {
  fn mutate(&self, pool: &mut Pool) {
    pool.b.get_mut(self.b_id).mutate();
    pool.c.get_mut(self.c_id).mutate();
  }
}

But the problem with this is that I can't pass the Pool object via mutable reference to the A, because Pool contains that A and borrow checker doesn't like it. So instead I had to adapt:

The problem here is that you're creating a pool object but then not using it to do what it is there for. The point of using a pool was to not be passing references around, mutable or not. Instead you pass around indices into the pool, and all works fine. To make this more tolerable, it's helpful to create newtypes for the indices so you can implement some type safety.

struct Ai(usize);
struct Bi(usize);
struct Bi(usize);
impl Pool {
   fn get_b(&self, which: Bi) {
       self.b[which. 0]
   }
   fn mutate_A(&mut self, which: Ai) {
     self.mutate_B(self.get_b(self.get_a(which).b_id));
     self.mutate_C(self.get_c(self.get_a(which).c_id));
   }
}

Or if you'd prefer a different spelling, you could create the mutate methods on the Ai and Bi types, and pass the pool in as an argument. Either way you avoid using the references that are causing the trouble.

[matrixdev]

But in your sample I need to move all the actual logic (mutate functions) to the pool which is not really responsibility of the Pool object..

@droundy

Instead you pass around indices into the pool, and all works fine.

I am actually passing indices around:

pool.b.get_mut(self.b_id) // b_id is actually an index to B inside object A

Problem is actually materialising index B into the object B at the call site in the object A.

As other have mentioned I probably should use Rc/RefCell after all.

[droundy]

@matrixdev

But in your sample I need to move all the actual logic (mutate functions) to the pool which is not really responsibility of the Pool object.

You can think of it that way, or you can choose to think of the Pool object as being the graph data structure that you are manipulating.

I went through much the same process you're going through while working on translating fac from C to rust. Fac has a graph describing dependency relationships between files (and directories and symlinks) and rules to build objects, which can get pretty large, and has significant interdependencies. The graph needs to be cyclic, because for each file we need to be able to (quickly) identify the rule to build it, and each rule must know which files it depends on as well as which files it builds. So it has the same kind of issue where updating a Rule requires updating a bunch of Files and vice versa. And on top of that, we need HashMaps to allow us to identify File data structures based on actual filenames.

@matrixdev

As other have mentioned I probably should use Rc/RefCell after all.

You absolutely can make things work with Rc/RefCell, or Arc/Mutex, and it's appealing coming from a C (or C++) background, but it ends up actually making your code less clear, and bugs that the borrow checker would have caught end up turning into runtime panics or deadlocks (if you're using threads).

If you're curious, you could check out my version of your Pool in fac, which is called Build. I won't claim it's the most beautiful code, and nowadays I'd probably design things differently. But it's where my advice about using indices (RuleRef and FileRef in my code) comes from. And I'd definitely still be using indices in a pretty similar manner... that's not where I'd put the changes.