Data structure organization for mutable cyclic references


#1

(Sorry in advance the vague question, but I’m having difficulty figuring out how to ask it.)

In my app I’d like a tree of things like UI widgets. So say a Window contains a child, maybe a Button. I think these need mutable references to one another and I can’t quite figure out how to model it.

Here’s an example: suppose the window knows how to handle an event and potentially forward it:

fn click(&mut self, ...other stuff...) {
  if click_is_in_right_place() {
    self.child.click();
  }
}

So far so good. But then suppose the child’s implementation would like to notify its parent of some state change in response to the click (like say, maybe it’s dirty and should redraw soon, or maybe it should change colors or whatever).

To do that, the child somehow needs, in its click() implementation, to call some function on a mutable reference to its parent. But the parent’s click already has a mutable self. So even if you follow the example of std::rc::Rc to create cyclic references or use RefCell it seems there’s no way around the fundamental problem: function on mutable object A calls function on mutable B which cannot then call a function on mutable A.

Am I thinking about this wrong? How would you model this? The best answer I’ve come up with is to stuff “messages to the parent” in the return value of the child’s click(), but that means I’d need to encode all possible things a child might want to do to its parent in some return value enum.

It feels like a tree of mutable objects is a thing others have encountered before and I’m just missing some main concept (something about interior mutability maybe?). Any thoughts?


#2

This isn’t directly an answer to your question, but my experience writing Javascript GUIs is that synchronous callbacks are the cause of many, many, many bugs. There’s a limit to what state changes the window expects to see across the button click callback, and that limit is often poorly documented and breaks “interestingly” when violated, due, essentially, to the unrestricted aliasing. You wind up wanting to kick nearly everything to the microtask queue.

Maybe you should model your GUI with a microtask queue, and use that for almost all events. Example (not expected to work, because of the Box<FnOnce> issue among other things; there’s a couple of well-known workarounds, and I actually have a version of this design with no allocations that I’ve been meaning to publish a crate for):

thread_local!(pub static microtasks: VecDequeue<Box<FnOnce ()>> = VecDequeue::new());

fn run() {
    microtasks.with(|fq| {
        while let Some(task) = fq.pop_front() {
            task();
        }
    }
}

fn defer<FN: FnOnce()>(f: FN) {
    microtasks.with(|fq| fq.push_back(Box::new(f)));
}

fn window_button_clicked(w: &Arc<RefCell<Window>>) {
    let wdata = w.borrow_mut();
    let b = wdata.button.clone();
    defer(move || button_clicked(b));
}

#3

Ah, that’s a good idea! I agree with your thought that a microtask queue is an interesting way to prevent state changes at unexpected places.

But in the microtask callback, wouldn’t I need to include a reference to the window? …ah, I guess I use an RefCell and it’s no longer mutably borrowed once window_button_clicked returns.

I’d be curious to see your crate! It’s a little disappointing that I have to change the app architecture so fundamentally to work around the mutable borrowing requirement.


#4

One simple possibility is to just stick all your structs’ individual fields in Cells (zero overhead) or RefCells and use a convention of always calling methods on &T rather than &mut T.