[Bug Report] Cancels always rejected, duplicate-price orders stranded, and best-ask tracked with the wrong comparison

[OPTIONPOOL]

Found while running this order book 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. The book diverged from that consensus on every scenario; tracing it back turned up three independent correctness bugs, all in book.go (current HEAD df1b8fe8). Each reproduces with a three-line program using only Init/Submit/Cancel.

1. bidMap / askMap are never populated, so every cancel is rejected

bidMap and askMap are the price→level index. They are read on the insert path (book.go:81, :95) and in Cancel (:236, :238), and deleted from when a level empties (:142, :188, :258, :265) — but there is no assignment b.bidMap[price] = lim (or askMap) anywhere in the package. The insert path only ever calls addLimit/orders.add:

lim, ok := b.bidMap[price]   // always !ok — the map is never written
if !ok {
    lim = b.bidTree.addLimit(price, o)
} else {
    lim.orders.add(o)
}

So in Cancel, the lookup at :236/:238 always misses and the function returns at :241:

if !priceExists {
    return false, errors.New("price does not exist, this is should not happen")
}

Every cancel fails, for every order. (A related issue compounds it: the resting order literal at :72-76 never sets the side field, so it defaults to Bid; Cancel reads order.side at :228 to choose which map to consult, so even once the maps are populated an ask would be looked up in bidMap.)

Repro:

b := ob.Init()
id, _, _ := b.Submit(ob.Bid, 33596, 81)
ok, err := b.Cancel(id)
// ok == false, err == "price does not exist, this is should not happen"

2. A second order at an existing price strands its quantity (silent under-match)

Same root cause. Because the map lookup always misses, the insert path always takes the addLimit branch (:82-84, :96-98) even when a level already exists at that price. addLimit → tree.put hits the compare == 0 case (tree.go:72) and returns without inserting, so the new limitPrice is left detached and the second order lives only inside that orphan level — it never gets appended to the resting level's list. bestBid/bestAsk point at one twin; once it's consumed, matching advances past the price and the other order is unreachable. Quantity is not conserved.

Repro: rest two asks at the same price, then cross them with one bid.

b := ob.Init()
b.Submit(ob.Ask, 100, 5)
b.Submit(ob.Ask, 100, 5)          // 10 units resting at 100
_, ex, _ := b.Submit(ob.Bid, 100, 8)
// the incoming bid fills only 5 of 8; the second ask's 5 units are stranded
// (a follow-up bid at 100 for any size matches nothing).

3. Best-ask updated with the wrong comparison

book.go:104:

if b.bestAsk == nil || price > b.bestAsk.price {
    b.bestAsk = lim
}

For asks the best price is the lowest, so this must be price < b.bestAsk.price. (The bid side at :90 is correct — price > b.bestBid.price.) A newly rested cheaper ask never becomes bestAsk, so matchBid compares the incoming bid against a stale, higher ask (:132) and misses a cross it should fill.

Repro:

b := ob.Init()
b.Submit(ob.Ask, 105, 5)
b.Submit(ob.Ask, 103, 5)          // 103 should become best ask
_, ex, _ := b.Submit(ob.Bid, 104, 5)
// fills 0; should fill 5 against the ask at 103

Fixes

1 & 2 — write the index when a new level is created, and set the order's side:

o := &order{
    id:    newOrderID,
    side:  side,          // was unset (defaulted to Bid)
    price: price,
    size:  size - matchedQty,
}
...
if !ok {
    lim = b.bidTree.addLimit(price, o)
    b.bidMap[price] = lim   // add for the bid branch
} else {
    lim.orders.add(o)
}
// ...and symmetrically b.askMap[price] = lim in the ask branch

3 — flip the comparison at :104:

if b.bestAsk == nil || price < b.bestAsk.price {
    b.bestAsk = lim
}

With these four lines, the three repros above behave correctly (cancels on both sides succeed, the bid for 8 fills 8, the bid at 104 fills 5 against 103), and the book reproduces the benchmark consensus.

Two more latent ones worth a look while you're in here: Top() (:274) nil-derefs b.bestBid/b.bestAsk on an empty side, and genID() (order.go:30) draws a random 8-digit id with no de-dup, so it will collide over a long run.

Happy to share the failing workload.