レッスン3 — `Book` struct と `Reverse<Price>` トリック

問い

best bid / best ask を O(1) で取れる order book を、custom comparator を書かずにどう組むか？そして resting order の「不可能な状態」をどう表現不能にするか？

原理（最小モデル）

BTreeMap 2 個が matching engine の状態のすべて。 order-id index も best-price cache も side ごとの counter も持たない。それ以外は派生値で、最適化はコアモデルを変えず後から重ねられる。
Reverse<Price> で bid を高値から走査。 key 型 の Ord::cmp を反転させると、両 side が BTreeMap::keys().next() という同じ形で best を返す。型側の非対称性 1 つで matching コードの対称性が手に入る。
RestingOrder は Order を trim する。 resting order に side は不要（どちらの map にあるかで分かる）、order_type も不要（Market は rest しない）。不可能な状態を表現不能にする = 型設計は制約エンジニアリング。
FIFO queue は VecDeque（Vec でない）。 Vec::remove(0) は O(n)、VecDeque::pop_front() は O(1)。price-time priority は push-back と pop-front の両方が速くないと成立しない。

具体例

bids (BTreeMap<Reverse<Price>, VecDeque<RestingOrder>>) — 高値から:
  Reverse(Price(102)) → [O3]              ← best bid: keys().next()
  Reverse(Price(100)) → [O1, O2]
asks (BTreeMap<Price, VecDeque<RestingOrder>>) — 安値から:
  Price(103) → [O7, O8]                   ← best ask: keys().next()
  Price(105) → [O9]

外側 BTreeMap が 価格優先（sorted key）、内側 VecDeque が 時間優先（FIFO）。bid 側の Reverse<Price> だけが非対称で、両 side の keys().next() を「最良気配」に揃える。

失敗例（誤解）

「HashMap の方が lookup が O(1) で速い」は誤り — 価格順に iterate する必要がある。「best bid」=「最高価格の bid」で、HashMap には「次の sorted key」がなく全 key を O(n) scan するしかない。BTreeMap の sorted iteration なら best は keys().next() で取れる。「Order をそのまま book に保存して qty を mutate」も誤り（Copy 型を mutate するのはバグに見えるし、resting Market order が作れてしまう）。

ここまでで「BTreeMap×2・Reverse トリック・trim」は着地した。ここから book.rs を組み立てる（matching ロジックはレッスン4-6）。コードは完全形。

🛑 予測。 BTreeMap は key を natural order（小さい順）で iterate する。ask（最安が先）は BTreeMap<Price, _> でぴったり。bid は最高が先に欲しい。custom comparator を書かずに BTreeMap を最高先に辿らせる最安の方法は？ ヒント:「u64 の ordering を反転する」を型として考える。

ステップで組み立てる

Step 1: `book.rs` — doc + imports

//! Price-time priority orderbook + matching engine.
//!
//! Bids are stored with a `Reverse<Price>` key so `BTreeMap` natural-order
//! iteration walks them best-first (highest price first). Asks are stored
//! with `Price` directly so they also walk best-first (lowest price first).
//! Within each price level, orders are queued FIFO — that's the "time
//! priority" half of price-time priority.

use core::cmp::Reverse;
use std::collections::{BTreeMap, VecDeque};

use crate::types::{
    AccountId, Fill, FillResult, Order, OrderId, OrderType, Price, Qty, Side,
};

Reverse は任意の Ord 型の ordering を反転（Reverse(Price(100)) は Reverse(Price(200)) より 大きい）。VecDeque は両端 queue（新規は push_back、マッチは pop_front）。レッスン4-6 で使う型も含め import をここで揃える（レッスン3 では一部 unused 警告が出て、後で消える）。

Step 2: `Book` struct

#[derive(Debug, Default)]
pub struct Book {
    /// Bids: `Reverse<Price>` key gives best-first iteration (highest first).
    bids: BTreeMap<Reverse<Price>, VecDeque<RestingOrder>>,
    /// Asks: `Price` key gives best-first iteration (lowest first).
    asks: BTreeMap<Price, VecDeque<RestingOrder>>,
}

状態全体が BTreeMap 2 個。asks は Price 直接（natural order で Price(99)→Price(100)→…、最安 ask は asks.keys().next()）。bids は Reverse<Price>（natural order が price 降順、最高 bid は bids.keys().next()）。どちらも keys().next() で best — これが型の非対称性を正当化する API 対称性（予測の答え）。Reverse なしだと bid が keys().next_back() になり side 間で非対称になる。

Step 3: `RestingOrder` struct

/// An order resting on the book. Trimmed from `Order` — side and `order_type`
/// are implicit from which side of the book it's resting on, and `qty` shrinks
/// as fills consume it.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct RestingOrder {
    id: OrderId,
    account: AccountId,
    qty: Qty,
}

3 field、非 pub（内部型）。side を落とす（どの map にあるかで分かる）、order_type を落とす（resting は常に Limit。Market は rest しない）、qty は残すが部分 fill で縮む。別型にすることで「これは mutate される」性質を明示する（Order は Copy で mutate がバグに見える）。

Step 4: `new()` + accessor 4 個

impl Book {
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    #[must_use]
    pub fn best_bid(&self) -> Option<Price> {
        self.bids.keys().next().map(|rp| rp.0)
    }

    #[must_use]
    pub fn best_ask(&self) -> Option<Price> {
        self.asks.keys().next().copied()
    }

    #[must_use]
    pub fn depth_bid(&self) -> usize {
        self.bids.values().map(VecDeque::len).sum()
    }

    #[must_use]
    pub fn depth_ask(&self) -> usize {
        self.asks.values().map(VecDeque::len).sum()
    }
}

best_bid は keys().next()（最小 key = 最高 price を wrap）→ .map(|rp| rp.0) で Reverse を剥がす。best_ask は key が Price 直接で .copied()。best を Option<Price> にするのは空 book で best が存在しないから（Price(0) を返すと caller が実価格と誤認する）。depth_* は inspection 用（hot path では呼ばない）。

Step 5: `lib.rs`

//! Pure-Rust CLOB (central limit order book) matching engine for openhl.
//!
//! No I/O. No allocation beyond fill output. Deterministic by construction.
//! See [`book::Book`] for the matching state machine.

pub mod book;
pub mod types;

pub use book::Book;
pub use types::*;

Book のみ re-export、RestingOrder はしない（内部 queue 要素、外から construct/read すべきでない）。book.rs で pub struct でなく struct のままにして compiler に強制させる。

答え合わせ

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 の最初の ~45 行（struct + new() + accessor）に相当。submit（レッスン4-5）/ cancel（レッスン6）/ match_at_level（レッスン4）は後続。

合格基準

cargo check -p openhl-clob

→ clean compile（Fill/FillResult/Order/OrderType/Qty/Side の unused import 警告は OK、レッスン4-6 で消える。参照 SHA がこれら import を残しているので build-along を byte-identical に保つには残す）。よくあるミス: レッスン1 で Price に Ord derive 忘れ（BTreeMap<Reverse<Price>> が壊れる）/ RestingOrder を外から触ろうとする（private）。

まとめ（3行）

matching engine の状態は BTreeMap 2 個 — index/cache なし、他は派生。最適化は後から重ねる。
bid に Reverse<Price> を使うと両 side が keys().next() で best を返す（型の非対称性 → API の対称性）。
RestingOrder を Order から trim して不可能な状態（resting Market order 等）を表現不能にする。

レッスン3 — Book struct と Reverse<Price> トリック

問い