レッスン6 — `cancel` — order を book から引き抜く

問い

fill される前に resting order を削除したい。削除と同時に空になった price level を残さない（best_bid が嘘をつかない）ようにするには？

原理（最小モデル）

BTreeMap::retain が「mutate + 空 entry drop」を 1 closure でこなす。 同じ callback が queue から該当 order を削除し、level を残すか（!queue.is_empty()）を返す。1 pass で済み、submit 由来の空 level 不変条件が自動維持される。
O(n) 線形 scan が v0 で正しい。 O(1) cancel のための HashMap<OrderId, (Side, Price)> index は、BTreeMap と同期する 2 つ目の構造・追加メモリ・cache 圧を生む。profile に出ないものを最適化しない。
bool 戻り値が最小の正直な形。 Option<RestingOrder> は private にした RestingOrder を漏らす。Result<(), CancelError> は「見つからない」をエラーに強制するが、cancel の冪等性（2 回呼んでも安全）はバグでなく機能。
空 level の掃除が best_bid の正直さを保つ。 空 queue を残すと流動性ゼロなのに best_bid() が価格を返し、次の sell が幻の価格でマッチする。

具体例

retain closure は各 (price, queue) で 2 段判断:

Case A — 同一 level に他の order あり:
  BEFORE 100 → [O_3, O_5, O_4] → O_5 remove → AFTER 100 → [O_3, O_4]（queue 非空 → KEEP）
Case B — その level に他がない:
  BEFORE 100 → [O_7] → O_7 remove → AFTER（100 の entry 消滅）（queue 空 → DROP）

Case B が「空 level cleanup」を自動で守る — submit の「空 queue を即 drop」と同じ規律を retain の return 値が代行する。

失敗例（誤解）

「BTreeMap を iterate して order を削除し、もう一度 iterate して空 level を drop」は誤り — 2 pass は無駄で、invariant が 2 箇所に分散し、「削除した」と「空か check した」の間に inconsistent な窓ができる。1 closure、2 つの仕事、1 つの invariant。

ここまでで「retain の二役・O(n) で十分・bool 戻り値」は着地した。ここから組み立てる（matching engine がこれで機能的に完成）。コードは完全形。

🛑 予測。 price 100 で 50 unit の Limit Buy を rest させ、その order id で cancel する。cancel 後 best_bid() は何を返すべきか？（答え: None。100 で唯一の order だったので cancel で queue が空 → retain が level を drop → bids.keys().next() が None。空 level cleanup が best_bid を「実際に liquidity があるか」について正直に保つ。）

ステップで組み立てる

Step 1: `cancel`（`impl Book` 内、`submit_market` の後）

    /// Cancel a resting order by id. O(n) linear scan; fine for v0 book sizes.
    /// Returns true if the order was found and removed. Empty price levels
    /// left behind by cancellation are also dropped, so `best_bid`/`best_ask`
    /// stay consistent with `depth_bid`/`depth_ask`.
    pub fn cancel(&mut self, order_id: OrderId) -> bool {
        let mut found = false;
        self.bids.retain(|_, queue| {
            if !found && let Some(pos) = queue.iter().position(|o| o.id == order_id) {
                queue.remove(pos);
                found = true;
            }
            !queue.is_empty()
        });
        if found {
            return true;
        }
        self.asks.retain(|_, queue| {
            if !found && let Some(pos) = queue.iter().position(|o| o.id == order_id) {
                queue.remove(pos);
                found = true;
            }
            !queue.is_empty()
        });
        found
    }

retain が全 (key, queue) を辿り、closure が queue を mutate して bool を返す（false→entry drop、true→保持）。if !found && let Some(pos) = ...position(|o| o.id == order_id) で未発見時のみ検索（found = true 後は以降の level で queue 内探索を省く最適化）。!queue.is_empty() の return が空 level を drop。if found { return true } で bid で見つかれば ask scan を skip。OrderId は caller が unique 性を所有する前提。let-chain（if let && ...）は Rust 1.65+ stable（古い環境なら if !found { if let Some(pos) = ... } にネスト）。

答え合わせ

cd ~/code/openhl-reference && git checkout 55a9dff
diff -u ~/code/my-openhl/crates/clob/src/book.rs ./crates/clob/src/book.rs
git checkout main

本レッスン後、book.rs は 55a9dff の参照と 機能的に同一（残る違いは doc/空白とテストモジュール — レッスン7-8 で追加）。

合格基準

cargo check -p openhl-clob

clean。一時 smoke test（後で削除）:

#[cfg(test)]
mod smoke {
    use super::*;

    fn limit_buy(id: u64, account: u64, qty: u64, price: u64) -> Order {
        Order {
            id: OrderId(id),
            account: AccountId(account),
            side: Side::Buy,
            qty: Qty(qty),
            order_type: OrderType::Limit { price: Price(price) },
        }
    }

    #[test]
    fn cancel_removes_resting_order() {
        let mut book = Book::new();
        book.submit(limit_buy(1, 1, 30, 100));
        book.submit(limit_buy(2, 2, 30, 99));
        assert_eq!(book.best_bid(), Some(Price(100)));
        assert_eq!(book.depth_bid(), 2);

        assert!(book.cancel(OrderId(1)));
        assert_eq!(book.best_bid(), Some(Price(99))); // 99 is now the best
        assert_eq!(book.depth_bid(), 1);

        assert!(!book.cancel(OrderId(1))); // already removed
    }

    #[test]
    fn cancel_searches_both_sides() {
        let mut book = Book::new();
        book.submit(Order {
            id: OrderId(7),
            account: AccountId(1),
            side: Side::Sell,
            qty: Qty(30),
            order_type: OrderType::Limit { price: Price(100) },
        });
        assert!(book.cancel(OrderId(7)));
        assert_eq!(book.best_ask(), None);
    }

    #[test]
    fn cancel_nonexistent_returns_false() {
        let mut book = Book::new();
        book.submit(limit_buy(1, 1, 30, 100));
        assert!(!book.cancel(OrderId(99)));
        assert_eq!(book.depth_bid(), 1);
    }
}

cargo test -p openhl-clob smoke → 3 つ pass、その後 smoke を削除（本格テストはレッスン7）。よくあるミス: closure が !queue.is_empty() でなく無条件 true を返す（cancel 後も best_bid が幻価格）/ position 述語が o.id でなく o.account を比較。

まとめ（3行）

BTreeMap::retain が「該当 order 削除」と「空 level drop」を 1 closure・1 pass でこなす（invariant が分散しない）。
O(n) 線形 scan は v0 で正しい — index は profile が要求してから（連続配置の VecDeque は cache 効率も良い）。
bool 戻り値が最小の正直な形 — 内部型を漏らさず、cancel の冪等性を保つ。

レッスン6 — cancel — order を book から引き抜く

問い