How to model circular dependence?

[rubik]

I am building a system for multi-agents simulations. I have an Agent trait, and many types that implement it. Then there's a Kernel type -- the kernel handles some startup operations and then acts as a router of messages between the agents.

The problem is that the agents need to have a reference to the kernel (to send messages), and the kernel needs to have a reference to the agents (to send messages and perform some other operations). This cyclic reference logic is not accepted by the borrow checker, so I tried to sidestep it with a RefCell, but I ran into problems with that too.

Here's a sketch of the types:

pub struct Kernel {
    // other irrelevant fields have been omitted
    pub agents: HashMap<AgentID, Box<dyn Agent>>,
}

impl Kernel {
    pub fn send(&mut self, ...) {
        // ..
    }
}

pub struct CustomAgent {
    id: AgentID,
    kernel_ref: Rc<RefCell<Kernel>>,
}

impl Agent for CustomAgent {
   // ...
}

The problem comes in in the initialization stage: I create the Kernel first, then the Kernel needs to create the agents and pass a reference to itself to each agent. I cannot find a way to make it work. Each agent needs a mutable reference to the kernel because sending messages mutates the state of the kernel. That's why I had to resort to a RefCell. I cannot find a way to construct the Agent types and passing them a reference to the kernel.

[2e71828]

You can have the Kernel store a Weak pointer to itself by doing something like this, and then clone that to give to your agents as a backpointer:

pub struct Kernel {
    self_rc: RefCell<Weak<Self>>;
}

impl Kernel {
    fn new()->Rc<Self> {
        let result = Rc::new(Kernel {
            rc: Default::default()
        });
        result.self_rc.replace(Rc::downgrade(result));
        result
    }
}

The experimental Rc::new_cyclic() can eliminate this RefCell if you’re on the nightly compiler.

[Phlopsi]

You need std::rc::Rc + std::rc::Weak. The latter can be produced by calling Rc::downgrade and you can get the Rc back from the Weak by calling Weak::upgrade. The T in Rc<T> gets dropped when the strong count hits 0 and the internal box gets deallocated when the strong and weak counts both hit 0.

If there is no obvious hierarchy between the two, I recommend keeping the Rc at the more frequently used location, because upgrading a Weak to an Rc incurs some additional checks which can have a noticeable effect on performance.

[2e71828]

@Phlopsi

If there is no obvious hierarchy between the two, I recommend keeping the Rc at the more frequently used location, because upgrading a Weak to an Rc incurs some additional checks which can have a noticeable effect on performance.

If this extra checking is a problem, you can also keep everything as an Rc and manually break the cycles when you’re done (probably by emptying Kernel::agents). This runs the risk that you’ll have a memory leak by forgetting to do this but should be more performant.

If you go this route, I recommend providing a non-Clone handle object to outside code with a Drop implementation that does the cycle breaking.

[rubik]

Thanks to both, @2e71828 and @Phlopsi, for the very quick replies. I knew that Weak references existed but it's not clear to me why they solve the problem. I will start by reading the documentation. I also hadn't considered swapping RefCell and Rc/Weak. I see that keeping the RefCell outside allows the use of the replace method which is convenient in this case.

[s3bk]

Keep the Kernel and Agents separate:

pub struct Manager {
    kernel: Kernel,
    agents: HashMap<AgentID, Box<dyn Agent>>,
}
pub struct CustomAgent {
    …
}

impl Agent for CustomAgent {
    fn do_thing(&mut self, id: AgentId, kernel: &mut Kernel) { … }
}
impl Manager {
    fn run(&mut self) {
        for (id, agent) in &mut self.agents {
            agent.do_thing(id, &mut self.kernel);
        }
    }
}

[rubik]

This is a very clean solution. I tried applying it to my use-case but I don't think it's possible. In my case the kernel has a send(&mut self) method and the agents have a recv(&mut self) method, and the fact that both of them are mutable creates a lot of ownership problems.

In the end, I solved it by making both methods immutable with &self and hiding all the state in RefCell's.

Since the agents have receive methods and use the kernel to send, and the kernel has a send method and transmits the messages to the agents, I think there's a cleaner solution using channels. The kernel could provide agents with a (sender, receiver) channel pair during the initialization phase.