Design question - avoiding callback pattern and passing references to self

I have a design question, rather than a particular code issue, hence a bit longer text (sorry).

In short: I work on a personal project that allows to emulate various electronic components (chips), and simulate circuits. As in physical world, components communicate with each other via pins that are actual inputs and outputs. In simplistic approach: if I change a state (signal) on an output pin, the corresponding input pin immediately "knows" about the state change - and the change can trigger some action in the underlying logic. Think, as example, about an oscilator component that writes pulses in a given frequency to its output pin, and a connected CPU on the input end, that "ticks" for every pulse. Or a NAND gate, that changes its output every time some of the input changes. The immediate reaction to the state change is a key point here: in the example above the CPU component doesn't read the clock tick, but is being triggered by it. I am trying to solve it without a callback pattern (that seems to be discouraged in Rust), but I can't. My ideas so far:

  1. Naive approach: model the real world one-to-one.
    In such case I have structs representing pins; the pins can be linked together and they hold reference to anything that implements PinStateChange trait (its method is being then called, when a pin changes its state). That means:
    a) it's actually a callback pattern
    b) it feels that a pin "owns" the underlying logic, rather the other way around
    c) the logic must borrow the reference to self (hence I am returning Rc from new), that feels not right (and will drive me to a situation where I will have Rc's "all way down")

This is (with some shortcuts) - how such approach can look like:

trait IPin {
   read(&self) -> bool;
   write(&self, val: bool);
   set_handler(&self, Rc<dyn PinStateChange>);  // this is what I'm trying to avoid
   // ...
}

trait PinStateChange {
    fn on_state_change(pin: Rc<Pin>);
}

struct Pin {
    direction: PinDirection,  // input or output
    linked_pin: RefCell<Weak<Pin>>,    // the "other end" 
    handler: RefCell<Rc<dyn PinStateChange>> // change handler (again: I don't like it)
}

impl IPin for Pin { ... }

// example component: NAND gate

struct NandPins {
    in0: Rc<Pin>,
    in1: Rc<Pin>,
    out: Rc<Pin>
}

trait INand {
    fn execute(in0: bool, 	in1: bool) -> bool {
        !(in0 && in1)
    }
}

struct NandLogic;
impl INand for NandLogic {}

struct Nand<T: INand {
    pins: NandPins,
    logic: T
}

impl<T: INand> Nand<T> {
    pub fn new(logic: T) -> Rc<Self> {
        let pins = NandPins::new();
        let logic = NandLogic::new();
        let nand = Nand { pins, logic };
        let ref = Rc::new(nand);
        
        nand.pins.in0.set_listener(Rc::clone(&ref));
        nand.pins.in1.set_listener(Rc::clone(&ref));
        
        ref
    }
}

// connecting pin state change with component's logic
impl<T: INand> PinStateChange for Nand<T> {
  fn on_state_change(_pin: Rc<Pin>) {
    let val = self.logic.execute(self.pins.in0.read(), self.pins.in1.read());
    self.pins.out.write(val);
  }
}

#[test]
fn test_nand_state_change() {
   let nand = Nand::new(NandLogic);
   let pin1 = Pin::output();
   let pin2 = Pin::output();
   Pin::link(&nand.pins.in0, &pin1);
   Pin::link(&nand.pins.in1, &pin2);
   
   // the out pin changes its state here, immediately after write
   pin1.write(false);
   pin2.write(true);
   
   assert_eq!(true, nand.pins.out.read());
}

Other potential approaches:

  1. Reversed approach (to the above) - the components own pins and check the state change constantly. The only implementation of it I can think of is a case where every component runs an infinite loop (in a thread) constantly checking its pins state. Feels suboptimal and ugly.

  2. Event bus. Rather than simulating physical pin connections, each component can produce an event to a global event bus, and its underlying logic will then handle communication between components. There's quite a bit of coupling here: either the bus will need to own all the components (to invoke given method on them on state change) or have some callbacks (again). Plus every component needs to have an access to the bus (in opposition to access to its own pins).

  3. Channels? They give a nice separation, but I'm not sure about the performance. Think about components "ticking" in a few MHz rate. Plus... doesn't it look like slightly improved option 2.

  4. ??? Perhaps the real solution is here - something I'm not aware of with my current knowledge of Rust (like async Rust)

To wrap up: I see my problem as a "reactive graph" as the electronic circuit can be easily represented by a graph. The main question here is how to make it reactive? - have a change in one of the nodes propagate automatically into its neighbors (and so on). I can do it with callbacks, but I'm curious what's the Rust way of doing it right.

Base on my question you can clearly see I'm fairly new to Rust. After two months of "happy coding" in Rust I made myself somehow familiar with the language and its syntax and concepts, but I think I'm still miles away from "thinking in Rust", and my design approach mostly comes from my previous experiences (Clojure, C, Python, JS).

I don't think that's true (i.e. that callbacks would be discouraged as-is). Callbacks are sometimes a good API choice, sometimes they aren't, just like any other construct.

Commodity computers run at clock speeds in the several GHz range. The simulation can be 1000 times slower than physical reality and still work. I don't think that channels will block for entire microseconds (meaning several thousands of clock cycles) just to deliver a single message. This Playground suggests that 1 million items are transmitted in around 40 milliseconds, i.e., 40 nanoseconds per iteration, which is around 25 times faster than you apparently need.

I don't think async would help here.

What you are describing is a graph. You are trying to build a heavily interlinked data structure. The usual suggestion to model this kind of data structure in Rust is to make a list of components and access them by their index, so that you can avoid borrowing everything.

7 Likes

Thank you, @H2CO3. Following your suggestion, I have created a Circuit struct, that holds all components, pins, and connections between them. I've tried initially with a graph data structure (Petgraph), but I found it more convenient to build it on hasmaps.
Here is the code on play-rust - I have added some comments there, and placed three questions in areas that I find ugly, or I sense they could be improved (lines 188, 301, 315). I would appreciate any comments/suggestions. Thanks you

I'm sorry but that's a lot of code. I don't really get why you still need RefCells and Rcs all over the place – the very point of using flat lists and indices would have been to avoid passing long-lived borrows directly.

I especially don't understand the question on line 188 – you state that you need a mutable reference in on_pin_state_change, but that already takes &mut self. I don't see why you don't just use HashMap::get_mut() instead of get() and a RefCell.

Sorry for rather long example. That's the minimal working code I could create to illustrate the problem. The actual concerning code is around the CircuitBuilder, so from line 250 onwards.

You are right, storing RefCells in the map seems pointless here...

In my initial code I had all components and pins being wrapped with Rc, which is not needed anymore. But I still have the Circuit as Rc.

Anyway my main concern now is related to the "reactivity" of the pins, so how to make any state change propagate across the graph. I've achieved it with the callback/handler (line 208) and I'm curious whether it's the right way to go, or would you suggest another approach?

The issue is with the line 226:
let mut component = self.0.components[&component_id].borrow_mut();
I can't change it to:
let mut component = self.0.components.get_mut(&component_id);
because self.0 is Rc<Circuit>. I'd be happy to avoid wrapping it with Rc if that's possible...

If you squint hard enough, a game is just another form of simulation, albeit one that allows an outside actor (the player) to interact with it.

Games also run into a similar problem where you've got lots of interconnected components that all need to update each other once per "tick". For example, mobs have an AI which will look at the surrounding terrain and other entities to figure out what to do next, then they'll execute actions accordingly.

The predominant solution for this is to design your application around an Entity-Component-System architecture... This is where you'll have a bunch of "entities" which have properties attached to them ("components"). Then your main loop will use a bunch of "systems" to implement your game mechanics. For example, there could be a physics system which updates an entity's position component and implements collisions, then there could be a mob AI system which uses the state of the world to change its high-level planning, and so on.

There are a bunch of ECS crates listed on the Are We Game Yet? website.

You might be interested in watching "Using Rust For Game Development" by Catherine West from RustConf 2018. Catherine talks through a lot of the design problems you are seeing and proposes some Rust-specific solutions.

2 Likes

This is very interesting analogy, @Michael-F-Bryan - thank you so much for sharing your thoughts. My first impression is that, unlike games - where high parallelism can be introduced (for every component) - my system is pretty much synchronous. However the interconnections between components and necessity to complete signal propagation across the graph within a single cycle (tick), is pretty much relevant.

I'm very curious about the video you've shared. I haven't done any game development since the old days of coding in Assembly on MOS/Motorola processors ages ago, so I think I can learn a lot from it. Thanks a lot.

Below some extra details about how the circuit (and my emulator) works:

The idea of a "cycle" is actually not very accurate here, and it works only in some cases. Some chips, like CPUs, are being driven by "ticks", but some "immediately" react to input changes. Components like logical gates or static memory don't need to be "ticked". Let's take as example static RAM in read (output) mode. It has some address pins and data pins. As soon as signal changes on any address pins, the state of the output pins changes and "propagates" further (of course there is some physical latency in reading data, but it's not clock driven). In such system a CPU doesn't "read" data from RAM, but it sends address to its output pins, and the relevant data "appears" on its input pins - all happens within the same clock cycle.

From my CPU emulation in Rust, the above scenario looks as follows:

self.pins.rw.set_high(); // (1)
self.pins.addr_port.write(0x0c02); // (2)
let byte = self.pins.data_port.read(); // (3)

where:

  1. Sets the CPU's data pins to INPUT mode (and connected device into OUTPUT)
  2. addr_port is a wrapper for 16 address pins - it sends address data there
  3. data_port wraps 8 data pins, reads bits from there and returns a byte. What's important here is that it doesn't read from the connected device, but it reads the current state of its own pins. The actual state of data pins has changed on step (2), when we sent the address and then RAM sent the data to its output pins.

As you can see the CPU doesn't know anything about RAM. It could be, instead, connected with some addressable I/O device or a bunch of gates.

If I'd repeat the same three operations once again, then absolutely nothing happens on the graph (circuit), as there is no state change. The CPU would just read the same state from its data pins.
Hope that explains the full logic of the system.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.