Lesson 4 — submit for Limit orders + match_at_level

Question

submit(order) for a Limit order: try to match against the opposite side until exhausted or price-limited, then rest the remainder. match_at_level is the core inner loop.

Principle (minimum model)

• submit skeleton (~30 lines). Determine match-against side; loop while matchable; for each best price level, call match_at_level; if remaining > 0 and limit-price not hit, rest the order.
• match_at_level(level, taker, max_qty) -> (fills, remaining). Pop maker orders FIFO until level exhausted or taker satisfied; emit a Fill for each match.
• Price-time priority (FIFO). At each level, oldest order matches first. Implementation: VecDeque::pop_front().
• Self-trade policy. If maker and taker have same account, apply the policy (Reject / ExpireMaker / CancelMaker). Default: Reject.
• Partial fills. If taker quantity exceeds the entire level, drain the level + advance to the next; if smaller, partial-match the head of the level.
• FillResult aggregation. Collect all fills into a vec; total filled = sum of fill sizes; remaining = initial - filled; status = Filled / PartiallyFilled / Open.
• Edge cases. Empty book (no match; rest at full size). Crossing the spread (multiple levels matched). Limit-price stop (partial match, rest the rest).

Worked example + steps

Lesson 4 — submit for Limit orders + match_at_level

Goal

Concepts you'll grasp in this lesson:

• Buy and Sell are structural mirrors, not generic abstractions — the Buy branch walks asks ascending; Sell walks bids descending. Two near-identical functions read more clearly than one fully-generic helper with boolean-flag puzzles inside.
• Walk-while-crossing is the matching engine's core loop — while remaining > 0 && best_opposite_price crosses limit { match_at_level; advance/drop level }. Once you see this shape, market orders in Lesson 5 fall out as "the same loop minus the price check."
• Empty-queue invariant must be maintained on every mutation — if queue.is_empty() { remove(price) } after each match. If an empty queue is left in the map, best_bid() lies and the no-crossed-book invariant breaks.
• Return value describes what happened to the call; book state describes what is — FillResult::remaining_qty is Qty(0) for Limit (whatever didn't fill went to rest); to know the rested remainder, query best_bid / depth_bid separately. Don't mix the two contracts.
• match_at_level as a free function names its scope — no self; it operates on data the caller has already extracted (queue + remaining). Function signature is documentation.

Verification:

cargo check -p openhl-clob

…still compiles.

Specific changes:

Your Book can now accept Limit orders (Buy + Sell) and produce real Fills. Market orders are still todo!() — that's Lesson 5.

What you'll write:

• submit() — the dispatch method that routes to submit_limit or submit_market based on order.order_type.
• submit_limit() — the meat: walks the opposite side of the book, matches at-or-better than the limit price, rests any unfilled remainder back on the book.
• match_at_level() — a private helper called from submit_limit (and from submit_market in Lesson 5) that does the actual fill at a single price level, mutating both the maker queue and the taker's remaining quantity.

After Lesson 4 you'll have ~150 lines of book.rs. Buy + Sell Limit orders both work; Market still panics with todo!.

Recap

After Lesson 3, book.rs has:

pub struct Book {
    bids: BTreeMap<Reverse<Price>, VecDeque<RestingOrder>>,
    asks: BTreeMap<Price, VecDeque<RestingOrder>>,
}

struct RestingOrder { id: OrderId, account: AccountId, qty: Qty }

impl Book {
    pub fn new() -> Self { ... }
    pub fn best_bid(&self) -> Option<Price> { ... }
    pub fn best_ask(&self) -> Option<Price> { ... }
    pub fn depth_bid(&self) -> usize { ... }
    pub fn depth_ask(&self) -> usize { ... }
}

No way to put an order in. That's what Lesson 4 fixes.

Plan

Three additions, all in crates/clob/src/book.rs:

1. submit() dispatcher — 1 match over OrderType. Limit → submit_limit; Market → todo!() for now.
2. submit_limit() body — about 60 lines. Buy walks asks ascending, matches while ask_price <= limit. Sell walks bids descending, matches while bid_price >= limit. Unfilled remainder rests on the book (entering as a RestingOrder).
3. match_at_level() helper — about 25 lines. Pops or shrinks the maker at the front of a queue, returns a single Fill, mutates the taker's remaining quantity.

This is most of the matching engine. Lesson 5 adds Market (which is submit_limit minus the price check + minus the resting step). Lesson 6 adds cancel. The core of the matching engine is this lesson.

(Answer: fills are [Fill@98 for 30, Fill@99 for 20]. After the trade, O_a is gone, O_b has 10 units left, O_c is untouched at 30, O_d is untouched at 30. The buyer paid less than the limit (98 + 99 vs 100) — that's the "at-or-better" rule.)

Laid out as the book's state transition:

BEFORE — submit Limit Buy @ 100, qty 50:

  asks (lowest first):                bids: (empty)
    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 → consume O_a fully  → Fill(O_a, taker, 98, 30); remaining = 20
    99  ≤ 100 → consume O_b partial → Fill(O_b, taker, 99, 20); remaining = 0
    101 > 100 → STOP                  (price exceeds limit / taker filled)

AFTER:

  asks:                                bids: (still empty — taker fully filled,
    99  → [O_b(10), O_c(30)]                    nothing to rest)
    101 → [O_d(30)]

  returned: FillResult { fills: [F1, F2], remaining_qty: Qty(0) }

That's the matching engine's hot path in motion — the taker walks the ask side upward and consumes liquidity. When the remainder hits zero we stop; if it doesn't, the taker reverses and rests on the bid side (the partial-fill case implemented in Step 3).

Walk-through

Step 1: Add the submit() dispatcher

In crates/clob/src/book.rs, inside the existing impl Book { ... } block (right after new()), add:

    /// 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 Lesson 5"),
        }
    }

3 lines of body. The dispatcher is intentionally tiny — all the matching logic lives in submit_limit and (eventually) submit_market. The dispatcher's only job is type-driven routing, not matching.

todo!() is the right placeholder here: it panics with a clear message at runtime if a Market order is submitted, but compiles cleanly. Lesson 5 will replace it with a real self.submit_market(order) call.

Step 2: Start writing submit_limit — the dispatcher's body

Below submit(), still inside impl Book:

    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 walks asks from cheapest; matches while 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 walks bids from highest; matches while 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);
                    }
                }
            }
        }

        // (rest-the-remainder logic comes next)
        FillResult { fills, remaining_qty: Qty(0) }
    }

This is the matching loop. Walk it carefully. The Buy branch:

1. Loop forever, breaking on conditions. Three exits: (a) taker is fully filled, (b) book is empty on this side, (c) the cheapest ask is more expensive than the limit.
2. self.asks.keys().next().copied() — the cheapest ask price. .copied() because we want a Price value, not &Price.
3. if best_price > limit_price { break } — the at-or-better rule. We won't pay more than limit_price for an ask.
4. self.asks.get_mut(&best_price).expect(...) — the queue at that price. .expect is safe here because we just got best_price from keys().next() — the level definitely exists. The expect message documents this invariant.
5. match_at_level(&order, best_price, queue, &mut remaining) — does the actual match. We'll write this helper next; for now know that it returns a Fill and mutates both queue (pops the maker if fully filled) and remaining (subtracts the filled quantity).
6. if queue.is_empty() { self.asks.remove(&best_price) } — if match_at_level left the queue empty, drop the level so best_ask() stays consistent with depth_ask(). (If we left an empty queue in the map, best_ask() would return that level's price even though no orders are there.)

The Sell branch is structurally identical but inverted:

• Walks bids instead of asks.
• The keys are Reverse<Price>, so we unwrap via best_rev.0.
• Compares with best_price < limit_price (sell at-or-better means sell at or above limit).

The "structural identity" is the load-bearing observation. A Buy + a Sell are mirror images of each other. Both walk the opposite side's best-first; both match while the price clears the limit; both pop the level if it goes empty. The only difference is which BTreeMap they touch and which direction the comparison goes. If you understand the Buy branch, you understand the Sell branch.

Step 3: Add the rest-the-remainder logic

The matching loop above ends with FillResult { fills, remaining_qty: Qty(0) } — that's a placeholder. Replace it with the real "rest the remainder" logic:

        // 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 that rest report zero remaining to the caller —
            // the remainder isn't in the return value, it's in the book.
            FillResult {
                fills,
                remaining_qty: Qty(0),
            }
        } else {
            FillResult {
                fills,
                remaining_qty: Qty(0),
            }
        }
    }

Walk this carefully:

1. if remaining.0 > 0 — taker still has unfilled quantity. For Limit orders, that quantity goes onto the book (Market orders, in Lesson 5, discard it instead).
2. Construct RestingOrder — drop the side and order_type (encoded by which map we push into), keep id + account + remaining qty.
3. self.bids.entry(Reverse(limit_price)).or_default().push_back(resting) — for a Buy order's unfilled remainder. entry + or_default is the "insert if missing, get mutable ref either way" idiom for BTreeMap. The Reverse(limit_price) is the key shape we picked for bids in Lesson 3.
4. self.asks.entry(limit_price).or_default().push_back(resting) — symmetric for Sell.
5. FillResult { fills, remaining_qty: Qty(0) } — return zero remaining_qty to the caller. This is the load-bearing semantic the doc on FillResult in Lesson 2 promised: a Limit order that rests says zero remaining. The remainder is in the book, not in the return value.
6. Both branches (if and else) return Qty(0) remaining. The else branch is for the fully-filled case (taker matched 100%; nothing rests, nothing remains). The two branches produce the same return value but for different reasons.

Step 4: Write the match_at_level() helper

Below the impl Book { ... } block (at module scope, not inside the impl), add:

/// 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
}

This is the actual match — the smallest function that does the real work. Walk it:

1. queue.front_mut().expect(...) — the maker at the front of the queue. Time priority means the first-placed order matches first. expect is safe because submit_limit only calls match_at_level after confirming the level exists.
2. fill_qty = min(maker.qty, remaining) — match the smaller of the two. If the maker has 30 units and the taker still needs 50, the fill is 30 (the maker is fully consumed). If the maker has 30 and the taker only needs 10, the fill is 10 (the maker still has 20 left).
3. Build the Fill — store both order IDs and both account IDs (Lesson 2's design decision: self-contained Fills).
4. maker.qty.0 -= fill_qty.0 — shrink the maker. This is the mutation that's safe inside RestingOrder but would be weird inside Order (Lesson 3's anti-fluency callout — RestingOrder exists exactly to make this kind of mutation explicit).
5. remaining.0 -= fill_qty.0 — shrink the taker's outstanding quantity. The caller (submit_limit) sees this via the &mut Qty argument.
6. if maker.qty.0 == 0 { queue.pop_front() } — if the maker is fully consumed, pop them off. The next iteration of submit_limit's outer loop will check this queue again — if it's now empty, the level itself gets dropped.

Why is this a free function instead of a method on Book? Because it doesn't need access to self. It only touches a single queue (which submit_limit already has a mutable reference to) and a single remaining counter. Making it a free function reflects that scope: nothing about Book as a whole is involved.

Test

cargo check -p openhl-clob

Should compile clean. Unused-import warnings from Lesson 3 (specifically Fill, FillResult, Order, OrderType, Qty, Side) should be gone now — submit_limit and match_at_level use all of them.

To sanity-check the matching logic, we don't have tests yet (those are Lessons 7–8). Paste this one-off smoke test at the very end of crates/clob/src/book.rs (below the match_at_level function). At the bottom of book.rs, Book, OrderId, AccountId, Side, Qty, OrderType, Price are all in scope via crate paths, so a single use super::*; plus use crate::types::*; suffices:

#[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();
        // Place a resting sell at 100 for 30 units.
        book.submit(Order {
            id: OrderId(1),
            account: AccountId(1),
            side: Side::Sell,
            qty: Qty(30),
            order_type: OrderType::Limit { price: Price(100) },
        });
        // Cross with a buy at 100 for 50 units.
        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));
        // 50 - 30 = 20 unfilled, rests as a new bid at 100.
        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
    }
}

Run with cargo test -p openhl-clob smoke::buy_crosses_resting_ask. If it passes, your Limit Buy + Limit Sell logic is correct.

Delete this mod smoke block from book.rs before moving to Lesson 5 — the real test suite goes in Lessons 7–8 with proper hand-traced scenarios + proptests. The smoke test above is just to verify Lesson 4 compiles AND runs correctly. Reset book.rs to a clean state for Lesson 5.

Common errors and fixes:

• error: 'Buy' branch panics with 'todo!()' but I selected Limit not Market — your submit dispatcher's OrderType::Limit arm still has todo!() from a draft state. Re-check Step 1; the Limit arm should call self.submit_limit(order, price).
• error[E0596]: cannot borrow 'maker' as mutable... requires Copy — front_mut() returns Option<&mut T>, not Option<T>. If you wrote let maker = queue.front_mut().expect(...).clone(), you're working with a Copy of the maker and your mutations don't persist. Use the reference directly: let maker = queue.front_mut().expect(...).
• error: cannot find value 'asks' in scope in match_at_level — match_at_level is a free function, not a Book method. It doesn't have self. Use the parameters (queue, remaining) instead.
• Smoke test reports depth_bid: 0 — your rest-the-remainder logic didn't push to bids. Re-check Step 3, especially the Reverse(limit_price) key wrapping (forgetting Reverse means you push into an unwrapped-Price entry which won't be found by best_bid's Reverse-keyed lookup).

Design reflection

Three load-bearing decisions encoded here:

1. Buy and Sell are structural mirrors. The Buy branch walks asks ascending; the Sell branch walks bids descending. We didn't try to abstract over them with generics — duplication was cheaper than the abstraction tax. Two structurally identical functions are easier to read than one fully-generic function.

2. match_at_level is a free function, not a method. It doesn't need self. Making it a free function documents that it operates on data the caller has already extracted (queue + remaining), not on the Book's overall state. Function signature is documentation: name your scope.

3. remaining_qty: Qty(0) for resting Limit orders is intentional. The caller sees "this many units matched; nothing leftover for me." If they want to know about the resting remainder, they query the book directly via best_bid / depth_bid — those are book-state methods. Return values describe what happened to the call; book state describes what is. Don't mix.

Answer key

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

After Lesson 4, your book.rs is approximately the first ~145 lines of the reference (struct + accessors from Lesson 3 + submit dispatcher + submit_limit + match_at_level). The reference also has submit_market (~40 LOC, Lesson 5) and cancel (~25 LOC, Lesson 6) that you haven't written yet.

Return:

git checkout main

Common questions

Q: Why is match_at_level's taker an &Order reference but queue is &mut VecDeque<RestingOrder>? Because match_at_level reads from taker (just to copy fields into the Fill) but writes to queue (pops or shrinks the front element). The function signature matches usage: & for read-only, &mut for mutating. The compiler enforces this — you can't accidentally mutate taker because the reference type doesn't allow it.

Q: What happens if a price level exists but its queue is empty? That's a bug. The invariant is "every key in the map corresponds to a non-empty queue." submit_limit enforces this by checking if queue.is_empty() { self.asks.remove(&best_price) } after each match — so an empty queue is never left behind. If you ever see an empty queue, look for places that mutated the queue without checking emptiness afterward.

Q: Why not use BTreeMap::pop_first() to grab the best level + remove it in one call? Two reasons. (1) Popping unconditionally removes the level, but we don't always want that — sometimes the level still has orders after matching (the maker got partially filled, queue still has others behind them). (2) pop_first was stabilized in Rust 1.66 but the matching pattern with get_mut + conditional remove reads more naturally for the "consume some, maybe drop the level" flow.

Q: Is there a fast path for "the taker exactly matches the maker"? No, and we don't need one. The general path (min(maker.qty, remaining) + shrink-or-pop) handles "exact match" as a special case of the general one. Adding a special-case branch would add a code path to test for marginal speedup; profile first if performance matters.

Next lesson (Lesson 5)

Limit orders work. Market orders still todo!(). Lesson 5 finishes the matching engine by:

• Replacing todo!() in submit() with self.submit_market(order)
• Writing submit_market() — like submit_limit but without the price check (Market takes any price) and without resting the remainder (Market discards leftovers).

Lesson 5 is shorter than Lesson 4 because most of the work (match_at_level, the dispatcher) is done. By the end of Lesson 5 you have a complete matching engine with both order types working.

Summary (3 lines)

• submit for Limit = loop match_at_level while matchable; rest the remainder at the limit price.
• match_at_level pops makers FIFO until level exhausted or taker satisfied. Price-time priority.
• Self-trade policy applied per match. Aggregate fills into FillResult. Next: Market orders.