[Bug Report] OrderBook over-matches across non-crossing prices and crashes with IndexOutOfBoundsException

Found while running Java-Matching-Engine-Core 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.

OrderBook keeps both sides in ArrayLists sorted ascending by price (Collections.sort + Order.compareTo) and matches by scanning from index 0. Two bugs in the match loops mean the first incoming order that meets a non-empty opposite book either matches across prices it doesn't cross or throws — so the engine can't get through a single scenario. Line numbers are against the default-branch HEAD 20d5e162f2c605773f7f1bf37d5a0287b8b24c8c.

Bug A — processLimitSell matches non-crossing buys, then crashes

The match-loop guard at OrderBook.java:134 uses || where it needs &&:

if (n != 0 || currentPrice >= order.getPrice()) {   // :134  -- || should be &&
    for (int i = 0; i >= 0; i++) {                   // :136  -- never terminates on its own
        final Order buyOrder = this.buyOrders.get(0); // :137 -- no empty-list guard, no price-cross break
        ...

currentPrice is the best (highest) resting bid, buyOrders.get(n - 1) (:130). The intent is clearly "enter the loop only if the book is non-empty and the best bid crosses the incoming sell" — which is exactly what the buy side does at :70: if (this.sellOrders.get(n - 1).getPrice() <= order.getPrice()). But with ||, the loop is entered whenever the buy book is merely non-empty, regardless of price.

That alone would only cause a wrong fill, except the loop is also missing the two safeguards the buy path has. Compare the buy path's loop, which re-checks the cross on every iteration and breaks (:73-75):

final Order sellOrder = this.sellOrders.get(0);
if (sellOrder.getPrice() > order.getPrice()) {       // buy path: price-cross break
    break;
}

The sell loop has no such break and no empty-list check. It runs for (int i = 0; i >= 0; i++), returns only when a single resting buy fully absorbs the incoming sell, and otherwise keeps doing removeBuyOrder(0); continue;. So it consumes every resting buy — including ones the sell price doesn't cross — and once the book is drained, the next buyOrders.get(0) (:137) throws IndexOutOfBoundsException.

There's a second, latent price-time-priority defect in the same loop: it always fills buyOrders.get(0), which on an ascending list is the worst (lowest) bid, not the best. The trades it does emit are at the wrong end of the book.

Repro. Rest BUY id1 qty 5 @ 100, then submit SELL id2 qty 10 @ 200. 200 > 100, so this must not trade at all. Instead the loop fires (book non-empty), wrongly fills 5 against the 100 bid, drains the book, and on the next iteration throws:

java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
    at net.laffyco.javamatchingengine.core.engine.OrderBook.processLimitSell (OrderBook.java:137)
    at net.laffyco.javamatchingengine.core.engine.OrderBook.process (OrderBook.java:52)

Bug B — processLimitBuy crashes when a buy sweeps the whole ask side

processLimitBuy matches inside while (true) (:73) and reads the best ask with no empty-list guard at OrderBook.java:74:

while (true) {                                       // :73
    final Order sellOrder = this.sellOrders.get(0);  // :74  -- throws once asks are drained
    if (sellOrder.getPrice() > order.getPrice()) {   // :75  -- can't fire with no element left
        break;
    }
    ...
    // partial-fill branch:
    this.removeSellOrder(0);                          // empties sellOrders mid-loop
    continue;

When an incoming buy is large enough to consume all crossing asks, each partial fill does removeSellOrder(0); continue;. After the last ask is removed, sellOrders is empty and the next sellOrders.get(0) (:74) throws IndexOutOfBoundsException. The price-cross break at :75 can't save it, because there's no element left to inspect — the read comes first.

Repro. Rest SELL id1 qty 3 @ 100, then submit BUY id2 qty 10 @ 100. The buy fills the only ask (3), loops back to read the next ask, and throws:

java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
    at net.laffyco.javamatchingengine.core.engine.OrderBook.processLimitBuy (OrderBook.java:74)
    at net.laffyco.javamatchingengine.core.engine.OrderBook.process (OrderBook.java:50)

Net effect and fixes

In the benchmark (a standing book with marketable order flow) the first incoming order that meets a non-empty opposite book hits one of these two paths, so every scenario crashes — the engine never produces a report stream to compare against the cross-engine consensus.

Both repros run against the matcher classes directly — new OrderBook() and process(...), no harness, no Spring.

Fixes, mirroring the side that's already correct:

• Bug A: change || to && at :134 so the loop is only entered when the best bid actually crosses, and add the same per-iteration price-cross break + empty-list guard the buy path has at :73-75. Match buyOrders.get(n - 1) (the best/highest bid), not buyOrders.get(0), so fills respect price-time priority.
• Bug B: guard the loop on a non-empty book — e.g. add if (this.sellOrders.isEmpty()) break; before the get(0), or fold the emptiness check into the loop condition — so the read can't run off the end of a drained book.

Happy to share the failing workload.

OrderBook.java の processLimitSell と processLimitBuy から始め、その後、issue に記載されている new OrderBook() と process(...) を使った 2 つの直接的な再現を実行します。完了条件は、約定条件が交差していない注文が取引されないこと、どちら側を sweep しても例外が発生しないこと、そして fill が指定された優先順位に従って利用可能な最良価格を使用することです。