レッスン4 — Limit order 用 submit + match_at_level
問い
Limit order の matching loop をどう書くか？ Buy と Sell はほぼ同形だが、generic で 1 つにまとめるべきか、ミラーの 2 本に分けるべきか？
原理（最小モデル）
- Buy と Sell は構造的ミラー（generic 抽象でない）。 Buy は ask を昇順、Sell は bid を降順に辿る。ほぼ同形の関数 2 本のほうが、boolean フラグでパズル化した generic helper より読みやすい。
- core loop =「クロスする限り辿る」。
while remaining > 0 && 反対側 best 価格が limit をクロス { match_at_level; level を進める/外す }。これが見えればレッスン5 の market order は「同じ loop から price check を抜いただけ」と分かる。 - 空 queue 不変条件を変更のたびに維持。 各 match 後に
if queue.is_empty() { remove(price) }。空 queue を残すとbest_bid()が嘘をつく。 - 戻り値（何が起きたか）と book 状態（今どうあるか）を分離。 Limit の
remaining_qtyは常にQty(0)（約定しなかった分は rest した）。rest 量はbest_bid/depth_bidで別途問う。
具体例
Limit Buy @ 100, qty 50。ask = {98:[O_a(30)], 99:[O_b(30),O_c(30)], 101:[O_d(30)]}:
walk asks while ask_price ≤ 100 and remaining > 0:
98 ≤ 100 → O_a 完全消費 → Fill(O_a, taker, 98, 30); remaining = 20
99 ≤ 100 → O_b 部分消費 → Fill(O_b, taker, 99, 20); remaining = 0
101 > 100 → STOP
AFTER: asks = {99:[O_b(10),O_c(30)], 101:[O_d(30)]}; FillResult{fills:[F1,F2], remaining_qty:0}
buyer は limit(100)より安く払った（98+99）= at-or-better ルール。
失敗例（誤解）
「submit を 1 つの巨大 match にして matching を各 arm に inline」は誤り — public method が 100+ 行になり、特定 path の test が難しくなる。named function（submit_limit/submit_market）に出して addressable に。「Buy/Sell を generic 化して 1 関数に」も誤り — BTreeMap 型 / 比較演算子 / key を全て抽象化する generic-bound パズルのコストが、~30 行の duplication 削減に見合わない。duplication は安く、abstraction の予算は貴重。
ここまでで「ミラー構造・core loop・関心分離」は着地した。ここから matching engine の core を組み立てる。コードは完全形。
🛑 予測。 上の「ask 98/99/101、Limit Buy @100 qty50」シナリオで、約定はどの順序で起き、trade 後の book はどうなるか？（答え: Fill@98×30, Fill@99×20。O_a 消滅、O_b は 10 残、O_c/O_d は 30 のまま。buyer は limit より安く約定。）
ステップで組み立てる
Step 1: submit() dispatcher（impl Book 内、new() の後）
/// Submit a taker order. Limit orders rest any unfilled remainder on the
/// book; Market orders discard it (returned via `remaining_qty`).
pub fn submit(&mut self, order: Order) -> FillResult {
match order.order_type {
OrderType::Limit { price } => self.submit_limit(order, price),
OrderType::Market => todo!("Market orders land in レッスン 5"),
}
}
dispatcher の唯一の仕事は型駆動ルーティング（matching そのものでない）。todo!() は clean な placeholder（Market submit で clear なメッセージ panic、compile は通る）。レッスン5 で self.submit_market(order) に置換。
Step 2: submit_limit — matching loop（Buy/Sell ミラー）
fn submit_limit(&mut self, order: Order, limit_price: Price) -> FillResult {
let mut remaining = order.qty;
let mut fills = Vec::new();
match order.side {
Side::Buy => {
// Buy は ask を最安から順に辿り、ask <= limit の間マッチする。
loop {
if remaining.0 == 0 {
break;
}
let Some(best_price) = self.asks.keys().next().copied() else {
break;
};
if best_price > limit_price {
break;
}
let queue = self
.asks
.get_mut(&best_price)
.expect("price level exists by construction");
fills.push(match_at_level(&order, best_price, queue, &mut remaining));
if queue.is_empty() {
self.asks.remove(&best_price);
}
}
}
Side::Sell => {
// Sell は bid を最高値から順に辿り、bid >= limit の間マッチする。
loop {
if remaining.0 == 0 {
break;
}
let Some(best_rev) = self.bids.keys().next().copied() else {
break;
};
let best_price = best_rev.0;
if best_price < limit_price {
break;
}
let queue = self
.bids
.get_mut(&best_rev)
.expect("price level exists by construction");
fills.push(match_at_level(&order, best_price, queue, &mut remaining));
if queue.is_empty() {
self.bids.remove(&best_rev);
}
}
}
}
// Any unfilled limit qty rests on the book.
if remaining.0 > 0 {
let resting = RestingOrder {
id: order.id,
account: order.account,
qty: remaining,
};
match order.side {
Side::Buy => self
.bids
.entry(Reverse(limit_price))
.or_default()
.push_back(resting),
Side::Sell => self.asks.entry(limit_price).or_default().push_back(resting),
}
}
// Limit orders report zero remaining — the remainder is in the book,
// not in the return value.
FillResult {
fills,
remaining_qty: Qty(0),
}
}
Buy ブランチの 3 exit: taker 完全約定 / book が空 / 最安 ask が limit 超。get_mut(...).expect(...) は安全（keys().next() 直後なので level 確実に存在、expect が invariant を文書化）。各 match 後 if queue.is_empty() { remove } で best を depth と整合させる。Sell は 構造的同一（bids を辿る / best_rev.0 で unwrap / 比較は <）。rest-the-remainder: 残量を RestingOrder にして Buy は bids.entry(Reverse(limit_price))、Sell は asks.entry(limit_price) に push。rest しても remaining_qty: Qty(0) を返す（remainder は book にある、return 値でない）。
Step 3: match_at_level()（module scope、impl Book の外）
/// Match a taker against the front of a single price level.
/// Mutates `queue` (pops the maker if fully filled) and `remaining`.
fn match_at_level(
taker: &Order,
price: Price,
queue: &mut VecDeque<RestingOrder>,
remaining: &mut Qty,
) -> Fill {
let maker = queue
.front_mut()
.expect("match_at_level called with empty queue");
let fill_qty = Qty(maker.qty.0.min(remaining.0));
let fill = Fill {
maker_order_id: maker.id,
taker_order_id: taker.id,
maker_account: maker.account,
taker_account: taker.account,
price,
qty: fill_qty,
};
maker.qty.0 -= fill_qty.0;
remaining.0 -= fill_qty.0;
if maker.qty.0 == 0 {
queue.pop_front();
}
fill
}
front_mut() = 先頭 maker（time priority）。fill_qty = min(maker.qty, remaining)。Fill に order_id × 2 + account × 2 を保存（レッスン2 の self-contained 設計）。maker と remaining を縮め、maker が 0 になれば pop_front。free function なのは self 不要だから（単一 queue + 単一 remaining にしか触らない）。expect("empty queue") は submit_limit の invariant を明示する防衛境界（空 queue で呼ばれない設計）。
答え合わせ
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 の最初の ~145 行（struct + accessor + submit + submit_limit + match_at_level）。submit_market（レッスン5）/ cancel（レッスン6）は後続。
合格基準
cargo check -p openhl-clob
レッスン3 の unused-import 警告はここで消える（submit_limit と match_at_level が全て使う）。動作確認は book.rs 末尾に一時 smoke test を貼る:
#[cfg(test)]
mod smoke {
use super::*;
use crate::types::{AccountId, OrderId, OrderType, Price, Qty, Side};
#[test]
fn buy_crosses_resting_ask() {
let mut book = Book::new();
book.submit(Order {
id: OrderId(1),
account: AccountId(1),
side: Side::Sell,
qty: Qty(30),
order_type: OrderType::Limit { price: Price(100) },
});
let result = book.submit(Order {
id: OrderId(2),
account: AccountId(2),
side: Side::Buy,
qty: Qty(50),
order_type: OrderType::Limit { price: Price(100) },
});
assert_eq!(result.fills.len(), 1);
assert_eq!(result.fills[0].qty, Qty(30));
assert_eq!(result.fills[0].price, Price(100));
assert_eq!(result.fills[0].maker_order_id, OrderId(1));
assert_eq!(result.fills[0].taker_order_id, OrderId(2));
assert_eq!(result.remaining_qty, Qty(0)); // rested, not returned
assert_eq!(book.best_bid(), Some(Price(100)));
assert_eq!(book.depth_bid(), 1);
assert_eq!(book.depth_ask(), 0); // ask was fully consumed
}
}
cargo test -p openhl-clob smoke::buy_crosses_resting_ask で確認 → pass。レッスン5 に進む前にこの mod smoke は削除する（本格テストはレッスン7-8）。よくあるミス: rest が Reverse(limit_price) で wrap されず best_bid が見つからない / front_mut() の戻りを .clone() して mutation が persist しない。
まとめ（3行）
- Buy/Sell は構造的ミラー — generic 化せず 2 本に分ける（duplication は abstraction tax より安い）。
- core loop は「クロスする限り反対側を best-first で辿り match_at_level」、各 match 後に空 level を外す。
- 戻り値は call で起きたこと（Limit は
remaining_qty: Qty(0)）、book 状態は別メソッドで問う — 関心を分離する。