[Bug Report] FIFOBook loses orders and under-matches: check_for_trades drops a popped order, and stale price bounds hide marketable orders

[OPTIONPOOL]

Found while running this engine through an open-source matching-engine benchmark, the Matching Engine Performance Challenge — it cross-checks engines against the byte-identical consensus of other open source engines. engine::algos::optimised_fifo::FIFOBook (driven by me_state_machine.rs:97-99 as book.apply(order) then book.check_for_trades()) diverges from that consensus on every scenario. On normal it emits ~3,000 trades against the ~10,000 the consensus produces — roughly 70% under-matched. Two separate quantity-conservation / price-priority bugs, both in the matcher core. Line numbers are against main de195a8.

Bug 1 — check_for_trades drops a popped order when the partner side is empty

pop_bid (optimised_fifo.rs:35-47) and pop_ask (:49-61) remove the front order with pop_front() before returning it. The entry point of check_for_trades pops both sides, then bails if either is empty (:121-124):

let (mut bid, mut ask) = match (self.pop_bid(), self.pop_ask()) {
    (Some(bid_new), Some(ask_new)) => (bid_new, ask_new),
    _ => return trades,
};

The tuple evaluates left-to-right, so pop_bid() runs first and removes the best bid. If pop_ask() then returns None, the _ => return trades arm returns without re-inserting the bid it already popped — that order is gone. The loss is symmetric: in the (None, Some(ask_new)) case the _ arm likewise drops the ask that pop_ask() already removed. The inner re-pop sites at :132/:144 handle this correctly — they push_front the leftover back when the partner pop fails (:136-139, :148-151) — but this top-of-function pop does not.

Repro. Rest a buy @50 and cross it with a sell @50. That fully trades but leaves an empty @50 ask bucket behind, with min_ask_price stuck at 50. Now send a non-crossing buy @100, size 7:

• the guard passes (max_bid_price 100 ≥ min_ask_price 50),
• pop_bid() pops the buy @100,
• pop_ask() scans from min_ask_price 50, finds only the empty @50 bucket, returns None,
• _ => return trades — the buy @100 never rests.

Standalone (book.rs + optimised_fifo.rs lifted verbatim, plus a small read-only inspector to print bucket contents) confirms it: total resting buy quantity before=0 after=0 (expected 7), and the buy @100 is absent from bid_price_buckets afterward.

Fix. Re-insert the popped order when the partner pop returns None (mirroring the :136/:148 handling), or peek each side and only pop once a real cross is confirmed.

Bug 2 — stale price bounds hide a marketable order (under-match, leaves the book crossed)

check_for_trades short-circuits on a bounds check (:115):

if self.max_bid_price < self.min_ask_price {
    return Vec::new();
}

Those bounds drift pessimistic and are never corrected. pop_ask assigns self.min_ask_price = ask_price on every price it steps over (:51), so a scan that walks across emptied buckets parks the bound at the far end. And apply only refreshes a bound on the new-bucket path (:90-91 for bids, :102-103 for asks); when an order lands in a bucket that already exists — including one emptied earlier — the Some(bucket) => bucket.push_back(order) arm runs and the bound is left untouched.

Together: once min_ask_price has walked up off an emptied low bucket, a later sell that refills that low bucket takes the Some(bucket) path and leaves min_ask_price stale-high. A genuinely crossing bid is then hidden by the :115 guard, so it rests against the lower ask with no trade — and the book is left crossed.

Trace (illustrative; reproduced standalone):

1. Asks rest at @60 and @90, so min_ask_price = 60.
2. Trading empties the @60 bucket, and a subsequent ask scan ratchets min_ask_price up to 90 (:51 reassigns it on each price it skips).
3. A new sell @60 arrives. The @60 bucket still exists, so apply takes Some(bucket) => push_back and does not lower min_ask_price — it stays 90.
4. A buy @70 arrives. It crosses the live @60 ask, but the guard reads max_bid_price 70 < min_ask_price 90 and returns early. Zero trades; the @60 ask and @70 bid both rest. The resting buy @70 sits above the resting sell @60 — a crossed book.

Fix. Keep min_ask_price/max_bid_price (and the min-bid/max-ask siblings) tracking the live best levels: recompute the bound when a bucket empties, and refresh it on every insert, not only the new-bucket path. Don't let pop_* move the bound to a price it merely skipped over.

---

Both reproduce standalone with book.rs and optimised_fifo.rs taken verbatim from de195a8 (only the proto/raft helpers and the embedded test module removed so it builds without the RPC stack, plus a small read-only inspector added to print bucket contents; the matcher core is untouched). The ~70% normal figure is what the benchmark observed on its workload, not a number from the source. Happy to share the failing workload and the standalone repro.