Why AND(0, ?) is 0: three values, snapshots and memory in a logic simulator

In my last post
I planned a feature, and executing it turned up a bug: the simulator could not
hold a bit with two gates. The first circuit in every digital logic course, an SR
latch from two cross-coupled NOR gates, read ? for every combination of inputs.

The short version of that story fits in a paragraph. This post is the long one:
what actually had to change inside the simulator core, in the order it had to
change, with the traces I used to convince myself each step was necessary. If you are building
anything that evaluates a circuit (a logic simulator, a spreadsheet engine, a
reactive graph), some of this will transfer.

Boolflow is a free browser logic simulator. The engine is
plain JavaScript with no React in it, so every number below comes from running
it under bare node.

Three values, and who gets to use them

A wire is 0, 1 or null, where null means "unknown". The original gates were
strict: if any input is unknown, the output is unknown.

That is wrong in exactly the case that matters. AND(0, ?) is 0 whatever the
question mark turns out to be. A controlling value decides a gate on its own:

const and = vs => (vs.includes(0) ? 0 : vs.every(v => v === 1) ? 1 : null);
const or  = vs => (vs.includes(1) ? 1 : vs.every(v => v === 0) ? 0 : null);
const inv = v  => (v === null ? null : v ? 0 : 1);

NAND and NOR are inv(and(...)) and inv(or(...)), so they inherit it.

Not every gate has a controlling value, and the code reflects that. XOR has none:
XOR(?, x) is unknown for either x, so XOR stays strict. NOT is strict because
inverting an unknown is an unknown.

One honest consequence: everything else is also still strict, and strict is
pessimistic. A MUX with an unknown select returns ? even when both data inputs
are 1, where real hardware gives 1. Adders, decoders and comparators do the
same. I only taught the AND/OR family, because that is the family that can resolve
a loop. I have not been bitten by the rest, but it is a real gap, not a design
decision.

Rounds, not sweeps

Here is the circuit. Two NOR gates, each fed by the other's output:

Q  = NOR(R, ~Q)
~Q = NOR(S, Q)

Start with both outputs unknown and set S = 1. Evaluate ~Q first and you get
NOR(1, ?), which is 0 by the controlling value. Now Q sees NOR(0, 0) and
becomes 1. The pair resolved out of nothing.

Notice what I just did: I picked an order. That is the second bug the latch
exposed. My relaxation loop evaluated gates in place, in whatever order the nodes
happen to sit in the file, so each gate saw its neighbour's new value immediately.
For a circuit with no loops that is harmless, because it converges to the same
answer whatever the order. With a loop, the order of the file decides the answer.

Here is the dangerous input to show it. Hold S = R = 1 (both outputs go low), then
release both at once. I replicated the rule in a 15-line toy, since the engine does
not print its rounds. Evaluating in place:

order Q, ~Q:   round 1  Q=1 ~Q=0   round 2  Q=1 ~Q=0   → stable, Q=1
order ~Q, Q:   round 1  Q=0 ~Q=1   round 2  Q=0 ~Q=1   → stable, Q=0

Two different stable answers, picked by which node I happened to list first.
Hardware does not work like that: both gates see the same old values and update
together. So a round now evaluates every gate against a snapshot of the previous
round's values, then applies all the results at once (a Jacobi iteration, if you
want the name):

snapshot:      round 1  Q=1 ~Q=1   round 2  Q=0 ~Q=0   round 3  Q=1 ~Q=1 …

Both gates flip every round, forever. That is what a real SR latch does when you
release both inputs of the forbidden state at the same instant: nothing in the
circuit says which gate wins, and I would rather show that than invent a winner.

The loop is small (relax in simulateComb.js, 26 lines):

const round = nodes => {
  const before = { ...vals };
  readFrom.v = before;           // gates read the snapshot…
  evaluate(nodes);               // …and write into vals
  readFrom.v = vals;
  return Object.keys(vals).filter(k => vals[k] !== before[k]);
};

What it buys is a test that reverses the node list and demands identical answers
for a six-step set / hold / reset / hold / set sequence.

How do you know it will never settle?

A circuit without loops needs as many rounds as its longest path. So the budget is
generous and simple:

const iters = Math.max(combNodes.length * 2, 10);

Still changing after that: the wires that changed in the last round are
oscillating. I do not leave them at whatever value the last round happened to
write, because that would look like a result. Every output of the gates involved
is set to unknown, and the rest of the circuit gets another go at settling around
them. The simulate() result is flagged, and
the editor shows a warning in the status bar.

This is the real engine on the latch, one row per tick:

S=0 R=0  Q=? Qb=?             power-up: nothing has set it
S=1 R=0  Q=1 Qb=0             set
S=0 R=0  Q=1 Qb=0             hold
S=0 R=1  Q=0 Qb=1             reset
S=0 R=0  Q=0 Qb=1             hold
S=1 R=1  Q=0 Qb=0             the forbidden input
S=0 R=0  Q=? Qb=?  UNSETTLED  both released at once
S=1 R=0  Q=1 Qb=0             a normal set recovers it

A small note on the editor: you cannot reach the oscillating row with two
switches, because releasing two switches is two clicks, which is two ticks. You
reach it by wiring one switch to both S and R. I got that wrong in an article
first and had to correct it.

Memory lives in the wires

Look at the "hold" rows. For the latch to hold Q = 1 after S drops to 0, the
tick that sees S = 0 has to start from Q = 1, ~Q = 0. Every call to
simulate() used to start from a blank wire map, so there was nothing to hold. A
latch keeps its bit in its own outputs.

So the values of the combinational wires now carry over from tick to tick, split in
two the same way flip-flop state already was:

let wiresCommitted = new Map();   // what the last tick settled on
let wiresWorking   = new Map();   // what this tick is computing

beginTick() promotes working to committed. Here is the same sequence with the
memory wiped before every tick:

S=0 R=0  Q=? Qb=?
S=1 R=0  Q=1 Qb=0
S=0 R=0  Q=? Qb=?      ← the bit is gone as soon as S is released
S=0 R=1  Q=0 Qb=1
S=0 R=0  Q=? Qb=?

The set and reset still work, because the controlling input is present. Releasing
it forgets. That is the difference between a gate that reacts and a gate that
stores.

Why two maps instead of one? The reason is the one flip-flop state already had, and
the comment above it in the code says it better than I would: simulate() runs
more than once per tick, because a layer is re-simulated once the values coming
through VIAs from other layers are known. With one map advanced in place, the
first of those runs consumed the clock edge while its inputs were still
unresolved, so a flip-flop fed through a VIA latched a stale value and the edge was
spent by the time the real value arrived. Reading every run from the same
start-of-tick baseline makes them recompute the same transition with progressively
better inputs. Wires needed the same treatment for the same reason.

For circuits without loops, stale starting values change nothing, since they settle
to the same answer from anywhere. A test runs different input pairs back to back
through an XOR and an AND and checks every answer.

Time: delta cycles for the stateful elements

Flip-flops, counters and registers are not gates, and they have the opposite
problem. A toggle flip-flop is D = NOT Q: its input depends on its own output.
Evaluated in a single sweep, that reads ?.

So a tick is not one sweep but a sequence of delta cycles, borrowed from how HDL
simulators work:

1. Every element's output pins start out showing its previous state, so feedback reads real values.
2. All elements are evaluated against the same snapshot and updated together. A shift register must not see its neighbour's new value.
3. The combinational logic settles on the new outputs (the rounds from above).
4. Repeat while anything changed.

A ripple counter's second stage sees its clock edge one delta later than the first.
An asynchronous reset takes effect in the delta after the counter reached the
decoded value.

Two details earned their place by failing.

First sight of a clock. A flip-flop meeting its clock for the first time has not
seen it change, so it must not fire. Without that, a stage clocked from a Q-bar
output (idle high) takes a spurious edge at power-up.

The cap. There has to be a ceiling or an oscillating circuit hangs the tab:
MAX_DELTAS = 32. I tested what that means, since a comment in the code said "a
ripple counter needs one per stage". A chain of N toggle flip-flops, each clocked
by the previous one's Q, with one rising edge at the front:

stages	high after the edge tick	one tick later
4	4	4
32	32	32
33	32	33
40	32	40

Beyond 32 stages the ripple does not complete in the tick that caused it. It
finishes on the next tick, because the remaining stages still see an unconsumed
rising edge. Nobody draws a 33-stage ripple counter in a teaching tool, but the
behaviour is a direct consequence of the cap, so I would rather list it.

What it still does not model

• Zero delay. Every gate answers instantly, so there are no glitches and no hazards, and the waveform is an idealisation. The panel says so.
• One kind of "not a number". null means unknown and high-impedance (a tri-state buffer with its enable off returns null). Verilog separates x and z; VHDL's std_logic has nine values. Merging them kept the code small, and I suspect it will eventually bite someone with a bus.
• The pessimistic gates above: MUX, adders, decoders.
• Real latch physics. A real SR latch released from the forbidden state ends up in a random state, or in metastability. The simulator says ? and flags it. I think that is the honest answer, but it is a modelling choice.

The tests

test-latches.mjs has 29 checks: NOR and NAND latches, a gated D latch from four
NAND gates and an inverter, and a master-slave D flip-flop from two of those, with
the output required not to follow D while the clock is high. Each one used to read
? for every input.

If the engine were a library I would have written these first. It was not, I did
not, and it took the first circuit of any digital logic course to find the gap.

Questions

1. Would you split unknown from high-impedance now, or wait until a bus forces it?
2. Is Jacobi (snapshot) rounds the right model for a teaching tool, or is a proper event queue with delays worth the complexity?
3. If you have built an evaluator with feedback, what was your oscillation policy: a cap, a visited-state set, or refusing loops?

Everything above is live at boolflow.site, with the SR
latch and the master-slave flip-flop in the examples.