Property-Based Testing & Engine v1

Three kinds of property cover nearly everything you'll write for an exchange:

1. Invariants: facts about state that hold after every command. The book is not crossed. Every resting order has positive quantity. L2 equals the aggregate of L3.
2. Model equivalence (differential testing): the real engine and a slow, obviously correct reference produce the same event stream for the same input.
3. Round-trips: decode(encode(m)) == m for every message (week 11), and replay(journal) == state for every journal (week 9).

The book invariants, from the most to the least obvious:

• Not crossed, and not locked. Best bid strictly below best ask. In a single venue's own book, bid equal to ask is also a bug: those two orders should have traded on arrival. (Locked markets do appear across venues in a fragmented market, which is a different story.)
• Live, unique orders. Every resting order has quantity > 0 and a unique id. A zero-quantity order means a fill path forgot to remove it. That ghost then sits in the FIFO and corrupts queue position for everyone behind it.
• L2 agrees with L3. Every published level's total and count equals the sum over the orders at that price. Every price with orders has a level, and every level has orders. This is the invariant that catches market-data bugs (week 10) before your clients do.
• Conservation of quantity. Over the lifetime of the book: submitted = resting + cancelled + 2 × traded. The factor of 2 is the subtle part. A trade of 5 removes 5 from the aggressor and 5 from the passive order.

use std::collections::{HashMap, HashSet};

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Side {
    Buy,
    Sell,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Resting {
    pub id: u64,
    pub side: Side,
    pub price: i64,
    pub qty: u64,
}

/// One L2 level as the book publishes it (week 10).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Level {
    pub side: Side,
    pub price: i64,
    pub total_qty: u64,
    pub count: u32,
}

/// Engine state plus lifetime counters, captured after a command.
pub struct Snapshot {
    pub orders: Vec<Resting>,  // every resting order (L3)
    pub levels: Vec<Level>,    // the published L2 view
    pub submitted_qty: u64,    // sum of qty over every accepted order
    pub traded_qty: u64,       // sum of qty over every trade (counted once)
    pub cancelled_qty: u64,    // cancels + IOC/market remainders
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Violation {
    /// best bid >= best ask (locked counts: it should have traded).
    Crossed { bid: i64, ask: i64 },
    ZeroQty { id: u64 },
    /// Report each duplicated id once, however many copies there are.
    DuplicateId { id: u64 },
    /// L2 and L3 disagree at (side, price): wrong total or count, a level
    /// with no orders, or orders with no level. Report each key once.
    LevelMismatch { side: Side, price: i64 },
    /// submitted != resting + cancelled + 2 * traded
    QtyNotConserved { submitted: u64, accounted: u64 },
}

/// Every violation in the snapshot; order of the Vec does not matter.
pub fn check(s: &Snapshot) -> Vec<Violation> {
    todo!()
}

Invariants catch broken states. They don't catch a wrong but internally consistent outcome, such as a fill at the wrong price, or the second order at a level filling before the first. For that you need a model: a second implementation that is slow, simple and obviously correct, run on the same input, with outputs compared event by event.

For a matching engine the model is a Vec of resting orders, each tagged with an arrival counter. To match, scan for the best opposite order (highest bid or lowest ask, ties broken by lowest arrival counter), fill, repeat. Cancels are a linear search. It's O(n) per operation and about 60 lines, and you can verify it by reading it. Never optimize the model. Its only job is to be right.

Generators decide what you find. Uniformly random prices over a wide range almost never cross the spread, so matching code goes untested. Shape the distribution:

• Prices within a few ticks of a drifting mid, so that crossing, partial fills and multi-level sweeps are common.
• Small quantities (1–10), so partial fills dominate.
• Cancels and modifies that mostly target live orders, with a small fraction targeting dead or unknown ids to exercise the reject paths.
• Every order type from week 8 represented, with post-only and FOK at meaningful rates.

Use a seeded generator you own. A small, fast, well-known choice is SplitMix64:

struct SplitMix64(u64);
impl SplitMix64 {
    fn next(&mut self) -> u64 {
        self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
        let mut z = self.0;
        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
        z ^ (z >> 31)
    }
}

The repo's types::Rng is exactly this generator. Print the seed on every failure. A failing seed is a complete, deterministic reproduction. Your engine is deterministic (week 9), so the same seed gives the same stream, the same events and the same bug.

A random failing stream is useless as a bug report. Nobody can debug 400 commands. Shrinking finds a 1-minimal failing input: removing any single command makes the failure disappear. That is weaker than globally minimal, which would need exponential search, but in practice it's nearly always the reproduction you'd have written by hand.

The algorithm in one paragraph: try deleting the first half, then the second half. Whenever a deletion still fails, keep it. When no chunk of the current size can be removed, halve the chunk size, down to single commands. Then shrink values: for each order, binary-search its quantity downward while the failure persists. Repeat both phases until nothing changes. Count your predicate calls. Each call is a full engine run, so a shrinker that restarts from scratch after every successful deletion becomes quadratic and slow.

Library context: QuickCheck-style libraries shrink values through per-type shrink functions. proptest shrinks through the ValueTree that generated the value, and Python's Hypothesis shrinks the underlying sequence of random choices. The repo doesn't use proptest: its engine::testkit::shrink is a hand-written delta-debugging shrinker over commands, the deletion half of today's drill. The drill makes you write the core yourself so you know what a library is doing when it takes 30 seconds.

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Side {
    Buy,
    Sell,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Op {
    Add { id: u64, side: Side, price: i64, qty: u64 },
    Cancel { id: u64 },
}

/// `fails(&input)` is true. Return a smaller stream for which it is still true:
///   1. 1-minimal: removing any single op makes `fails` return false;
///   2. each Add's qty is minimal: qty == 1, or qty - 1 no longer fails;
///   3. surviving ops keep their original relative order.
/// You may assume `fails` is monotone in qty (raising a qty never fixes it).
/// The harness counts calls to `fails` on a 400-op input: keep it under 1500.
pub fn shrink<F: Fn(&[Op]) -> bool>(input: Vec<Op>, fails: F) -> Vec<Op> {
    todo!()
}

Your previous weeks already supply three properties that only work because the engine is deterministic:

• Replay identity (week 9): run a generated stream, then rebuild state from the journal. The state hashes must match.
• Market-data fidelity (week 10): a client book built only from your L2 incrementals equals the engine's book after every command.
• Wire round-trip (week 11): every generated command survives encode → decode unchanged.

Run all of them inside the same generated stream, after every command. The marginal cost is small and the coverage compounds.

Engine v1 is the first time all the Phase 1 pieces run as one pipeline on one thread:

bytes ──decode (w11)──▶ command ──sequence + journal (w09)──▶ validate (w08)
      ──match (w07, book w06)──▶ events ──L2 incrementals (w10)──▶ publisher

In the repo, engine v1 is engine::Pipeline, and it starts from a decoded Command: journal append, Engine::process (validation and matching), then the L2 publisher. Decoding bytes stays at the edge, in the week 13 gateway.

The journal comes before matching. The input is made durable (in memory for now) before any state changes, so replay reproduces exactly what happened. That's the LMAX-style "journal the input, then run the business logic" ordering. Matching emits events into a reusable buffer, and market data consumes that buffer, not the book.

The week's throughput target, 5M commands per second end to end, is a budget of 200 ns per command on average. Your earlier targets were stated as p99 (journal append 100 ns, L2 update 100 ns, matching 450 ns). Averages run well below p99, so the budget is reachable, but only if nothing on the path allocates per command. If you miss it, profile before guessing. Week 26 makes profiling a habit.