Skip to main content

tycho_simulation/book/
levels.rs

1//! A ladder of price levels, the shape every venue's book takes once its wire format is
2//! decoded: filling an amount level by level, inverting a side, and valuing a side.
3//!
4//! Venues decode their wire levels into [`Levels`] at the ingestion boundary and store that, so
5//! the simulation math runs on validated data without converting per call.
6
7use derive_more::Deref;
8use itertools::Itertools as _;
9use serde::{Deserialize, Deserializer, Serialize};
10use thiserror::Error;
11
12/// How much of the input a fill may leave unspent and still count as complete: four ulps.
13///
14/// An amount reaches a fill through atomic units — `sim::to_atomic` scales it by `10^decimals`
15/// and truncates it into a `BigUint`, `sim::to_human` divides it back — and each of those three
16/// steps rounds, with a fourth ulp for the subtraction that measures what the walk left. Measured
17/// live, the round trip alone overshoots by up to one ulp.
18const FILL_TOLERANCE: f64 = 4.0 * f64::EPSILON;
19
20/// One price level: `quantity` units of the input token, each worth `price` units of the output
21/// token. Inside a [`Levels`] both are finite and positive.
22#[derive(Clone, Copy, Debug, PartialEq, Serialize, Deserialize)]
23pub struct PriceLevel {
24    /// Output token received per unit of input token.
25    pub price: f64,
26    /// Input token units this level absorbs.
27    pub quantity: f64,
28}
29
30impl PriceLevel {
31    /// The one place a level is judged fit to sit in a [`Levels`]: `Some` for a level that offers
32    /// something at a price, `None` for a zero-quantity placeholder (some venues publish `[0, 0]`),
33    /// and `Err` for a quantity or price no trade could be read out of. What to do about the last
34    /// two is the caller's: a ladder arriving from a venue rejects them, one computed from another
35    /// ladder drops them.
36    fn fillable(self) -> Result<Option<Self>, InvalidLevel> {
37        if !self.quantity.is_finite() || self.quantity < 0.0 {
38            return Err(InvalidLevel::Quantity(self.quantity));
39        }
40        if self.quantity == 0.0 {
41            return Ok(None);
42        }
43        if !self.price.is_finite() || self.price <= 0.0 {
44            return Err(InvalidLevel::Price(self.price));
45        }
46        Ok(Some(self))
47    }
48}
49
50/// Why a level cannot be part of a ladder.
51#[derive(Clone, Copy, Debug, PartialEq, Error)]
52pub enum InvalidLevel {
53    #[error("price level quantity must be a non-negative finite number, got {0}")]
54    Quantity(f64),
55    #[error("price level price must be a positive finite number, got {0}")]
56    Price(f64),
57}
58
59/// A ladder of price levels in the order a fill walks them, as the venue published it.
60///
61/// Every level has a finite positive quantity and price: [`Levels::new`] drops zero-quantity
62/// placeholders and rejects everything else that is not, and deserialization goes through the
63/// same check. The ladder derefs to a slice for read access.
64#[derive(Clone, Debug, Default, Deref, PartialEq, Serialize)]
65#[serde(transparent)]
66#[deref(forward)]
67pub struct Levels(Vec<PriceLevel>);
68
69impl Levels {
70    /// Builds a ladder from raw levels. Zero-quantity levels carry no liquidity and are dropped
71    /// whatever their price (some venues publish `[0, 0]` placeholders). Fails on a negative or
72    /// non-finite quantity, or a price that is not finite and positive on a level with quantity.
73    pub fn new(levels: Vec<PriceLevel>) -> Result<Self, InvalidLevel> {
74        // A ladder lives as long as the book it prices, so hand back the spare capacity a
75        // deserializer's doubling left in the caller's buffer.
76        let mut levels: Vec<_> = levels
77            .into_iter()
78            .filter_map(|level| level.fillable().transpose())
79            .try_collect()?;
80        levels.shrink_to_fit();
81        Ok(Levels(levels))
82    }
83
84    /// Consumes `amount_in` level by level, taking as much as each level offers, until the input
85    /// is spent or the ladder is exhausted. Never fails: an amount the ladder cannot absorb comes
86    /// back as `remaining_in`, and an infinite one takes the whole ladder and reports the rest as
87    /// unfilled.
88    pub fn fill(&self, amount_in: f64) -> Fill {
89        // An amount that is not a positive number buys nothing. Leaving it to the loop would rest
90        // on `f64::min` returning the *other* operand for a NaN, which would walk the entire
91        // ladder and report all of its output against an amount that never existed.
92        if amount_in.is_nan() || amount_in <= 0.0 {
93            return Fill { amount_out: 0.0, remaining_in: amount_in };
94        }
95
96        // Accumulate what the walk takes and subtract once, so a walk of the whole ladder adds
97        // its quantities in the same order `totals` does and filling exactly what `totals`
98        // reported leaves exactly nothing.
99        let mut consumed = 0.0;
100        let mut amount_out = 0.0;
101        for level in &self.0 {
102            let taken = (amount_in - consumed).min(level.quantity);
103            amount_out += taken * level.price;
104            consumed += taken;
105            if consumed >= amount_in {
106                break;
107            }
108        }
109
110        let remaining_in = amount_in - consumed;
111        // An amount that came through atomic units can land a hair above what the ladder holds
112        // (see `FILL_TOLERANCE`), and that hair is not liquidity anyone can trade. An infinite
113        // amount keeps its infinite remainder.
114        let remaining_in = if remaining_in.is_finite() && remaining_in <= amount_in * FILL_TOLERANCE
115        {
116            0.0
117        } else {
118            remaining_in
119        };
120
121        Fill { amount_out, remaining_in }
122    }
123
124    /// Re-expresses the ladder for the opposite trade direction: `(quote per base, base
125    /// quantity)` becomes `(base per quote, quote quantity)`. A level whose inverse is not
126    /// fillable — the price overflows to a non-finite value, or the quantity underflows to zero —
127    /// is dropped.
128    pub fn invert(&self) -> Levels {
129        Levels(
130            self.0
131                .iter()
132                .filter_map(|level| {
133                    PriceLevel { price: 1.0 / level.price, quantity: level.quantity * level.price }
134                        .fillable()
135                        .ok()
136                        .flatten()
137                })
138                .collect(),
139        )
140    }
141
142    /// The ladder's value in output units: the sum of `price * quantity` over every level.
143    pub fn notional(&self) -> f64 {
144        self.totals().1
145    }
146
147    /// Total input the ladder absorbs and the output it pays for it: the two swap limits.
148    pub fn totals(&self) -> (f64, f64) {
149        self.0
150            .iter()
151            .fold((0.0, 0.0), |(quantity, notional), level| {
152                (quantity + level.quantity, notional + level.price * level.quantity)
153            })
154    }
155
156    /// The price of the next input unit after `filled` units went in: the price of the level
157    /// where a fill of `filled` stops, which is the following level when it ends exactly on a
158    /// boundary. `None` once `filled` reaches the depth of the ladder, and for an amount that is
159    /// not a number.
160    pub fn marginal_price(&self, filled: f64) -> Option<f64> {
161        let mut depth = 0.0;
162        for level in &self.0 {
163            depth += level.quantity;
164            if filled < depth {
165                return Some(level.price);
166            }
167        }
168        None
169    }
170
171    /// Average output per input unit for filling `amount_in`, priced on the part the ladder
172    /// absorbs when it cannot absorb everything. `None` when nothing is consumed — an empty
173    /// ladder, or an amount that is not a positive number, or one too large to subtract.
174    pub fn average_price(&self, amount_in: f64) -> Option<f64> {
175        let fill = self.fill(amount_in);
176        let consumed = amount_in - fill.remaining_in;
177        (consumed > 0.0).then(|| fill.amount_out / consumed)
178    }
179}
180
181impl<'de> Deserialize<'de> for Levels {
182    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
183        Levels::new(Vec::deserialize(deserializer)?).map_err(serde::de::Error::custom)
184    }
185}
186
187/// What filling an amount against a ladder yields.
188#[derive(Clone, Copy, Debug, PartialEq)]
189pub struct Fill {
190    /// Output bought by the consumed input.
191    pub amount_out: f64,
192    /// Input the ladder could not absorb; zero when the fill is complete.
193    pub remaining_in: f64,
194}
195
196impl Fill {
197    pub fn is_complete(&self) -> bool {
198        self.remaining_in <= 0.0
199    }
200}
201
202#[cfg(test)]
203mod tests {
204    use rstest::rstest;
205
206    use super::*;
207
208    fn ladder() -> Levels {
209        Levels::new(vec![
210            PriceLevel { price: 3000.0, quantity: 1.0 },
211            PriceLevel { price: 2999.0, quantity: 2.0 },
212        ])
213        .unwrap()
214    }
215
216    #[test]
217    fn new_drops_zero_quantity_placeholders() {
218        let levels = Levels::new(vec![
219            PriceLevel { price: 0.0, quantity: 0.0 },
220            PriceLevel { price: 3000.0, quantity: 1.0 },
221            PriceLevel { price: -1.0, quantity: 0.0 },
222        ])
223        .unwrap();
224
225        assert_eq!(&*levels, &[PriceLevel { price: 3000.0, quantity: 1.0 }]);
226    }
227
228    #[test]
229    fn new_rejects_invalid_levels() {
230        assert_eq!(
231            Levels::new(vec![PriceLevel { price: 1.0, quantity: -1.0 }]),
232            Err(InvalidLevel::Quantity(-1.0))
233        );
234        assert!(matches!(
235            Levels::new(vec![PriceLevel { price: 1.0, quantity: f64::NAN }]),
236            Err(InvalidLevel::Quantity(_))
237        ));
238        assert_eq!(
239            Levels::new(vec![PriceLevel { price: 0.0, quantity: 1.0 }]),
240            Err(InvalidLevel::Price(0.0))
241        );
242        assert_eq!(
243            Levels::new(vec![PriceLevel { price: f64::INFINITY, quantity: 1.0 }]),
244            Err(InvalidLevel::Price(f64::INFINITY))
245        );
246    }
247
248    #[test]
249    fn deserialize_validates_and_serialize_is_transparent() {
250        let levels: Levels = serde_json::from_str(
251            r#"[{"price":3000.0,"quantity":1.0},{"price":1.0,"quantity":0.0}]"#,
252        )
253        .unwrap();
254        assert_eq!(levels.len(), 1);
255        assert_eq!(serde_json::to_string(&levels).unwrap(), r#"[{"price":3000.0,"quantity":1.0}]"#);
256
257        assert!(serde_json::from_str::<Levels>(r#"[{"price":0.0,"quantity":1.0}]"#).is_err());
258    }
259
260    #[test]
261    fn fill_walks_levels_in_order_and_reports_the_unfilled_rest() {
262        let ladder = ladder();
263
264        assert_eq!(ladder.fill(1.0), Fill { amount_out: 3000.0, remaining_in: 0.0 });
265        assert_eq!(ladder.fill(2.0), Fill { amount_out: 5999.0, remaining_in: 0.0 });
266        let partial = ladder.fill(5.0);
267        assert_eq!(partial, Fill { amount_out: 8998.0, remaining_in: 2.0 });
268        assert!(!partial.is_complete());
269    }
270
271    #[rstest]
272    #[case::nothing_filled(0.0, Some(3000.0))]
273    #[case::inside_the_first_level(0.5, Some(3000.0))]
274    #[case::on_the_boundary(1.0, Some(2999.0))]
275    #[case::inside_the_second_level(2.5, Some(2999.0))]
276    #[case::on_the_depth(3.0, None)]
277    #[case::past_the_depth(4.0, None)]
278    #[case::not_a_number(f64::NAN, None)]
279    fn marginal_price_is_the_price_of_the_next_unit(
280        #[case] filled: f64,
281        #[case] expected: Option<f64>,
282    ) {
283        assert_eq!(ladder().marginal_price(filled), expected);
284    }
285
286    #[test]
287    fn marginal_price_of_an_empty_ladder_is_none() {
288        assert_eq!(Levels::default().marginal_price(0.0), None);
289    }
290
291    #[rstest]
292    #[case::nothing(0.0)]
293    #[case::less_than_nothing(-1.0)]
294    #[case::not_a_number(f64::NAN)]
295    fn fill_of_an_amount_that_is_not_positive_takes_nothing(#[case] amount_in: f64) {
296        // Least obvious for the NaN: `f64::min` answers with its other operand, so without a
297        // guard every level would report itself fully taken and the ladder would pay out 8998 (1 ×
298        // 3000 + 2 × 2999).
299        let fill = ladder().fill(amount_in);
300
301        assert_eq!(fill.amount_out, 0.0);
302        assert!(
303            fill.remaining_in.to_bits() == amount_in.to_bits(),
304            "the amount comes back untouched"
305        );
306    }
307
308    #[test]
309    fn fill_of_an_infinite_amount_takes_the_whole_ladder() {
310        // What an amount past `f64::MAX` becomes on its way in: the ladder pays everything it
311        // has and the fill reports itself incomplete, rather than claiming to have filled it.
312        let fill = ladder().fill(f64::INFINITY);
313
314        assert_eq!(fill.amount_out, 8998.0);
315        assert_eq!(fill.remaining_in, f64::INFINITY);
316        assert!(!fill.is_complete());
317    }
318
319    /// Ten levels whose quantities sum to 98.008172. Subtracting them from that sum one at a
320    /// time leaves 7.1e-15 behind — the sum and the subtractions round differently — so a swap
321    /// of exactly the ladder's depth has to report itself filled all the same.
322    #[test]
323    fn filling_the_whole_ladder_leaves_nothing() {
324        let quantities = [1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9, 48.508172];
325        let ladder = Levels::new(
326            quantities
327                .iter()
328                .map(|&quantity| PriceLevel { price: 2.0, quantity })
329                .collect(),
330        )
331        .unwrap();
332        let (depth, _) = ladder.totals();
333
334        let fill = ladder.fill(depth);
335
336        assert_eq!(fill.remaining_in, 0.0);
337        assert!(fill.is_complete());
338    }
339
340    /// The tolerance covers rounding, not liquidity: a ladder asked for a thousandth more than it
341    /// holds still reports that thousandth as unfilled.
342    #[test]
343    fn filling_past_the_ladder_still_reports_the_shortfall() {
344        let ladder = ladder();
345        let (depth, _) = ladder.totals();
346
347        let fill = ladder.fill(depth + 0.001);
348
349        assert!((fill.remaining_in - 0.001).abs() < 1e-12, "got {}", fill.remaining_in);
350        assert!(!fill.is_complete());
351    }
352
353    #[test]
354    fn invert_swaps_units_and_drops_overflowing_levels() {
355        // (0.11 TAMARA per USDC, 3000 USDC) becomes (9.09 USDC per TAMARA, 330 TAMARA).
356        let inverted = Levels::new(vec![
357            PriceLevel { price: 0.11, quantity: 3000.0 },
358            PriceLevel { price: 0.12, quantity: 3000.0 },
359            PriceLevel { price: 1e308, quantity: 1e308 },
360        ])
361        .unwrap()
362        .invert();
363
364        assert_eq!(inverted.len(), 2);
365        assert!((inverted[0].price - 9.090909090909092).abs() < 1e-9);
366        assert!((inverted[0].quantity - 330.0).abs() < 1e-9);
367        assert!((inverted[1].price - 8.333333333333334).abs() < 1e-9);
368        assert!((inverted[1].quantity - 360.0).abs() < 1e-9);
369    }
370
371    #[test]
372    fn notional_and_totals_sum_the_ladder() {
373        let ladder = ladder();
374
375        assert_eq!(ladder.notional(), 8998.0);
376        assert_eq!(ladder.totals(), (3.0, 8998.0));
377    }
378
379    #[test]
380    fn average_price_is_per_consumed_unit() {
381        let ladder = ladder();
382
383        assert_eq!(ladder.average_price(1.0), Some(3000.0));
384        assert_eq!(ladder.average_price(2.0), Some(2999.5));
385        // Only 3 of 5 units fill; the price is over those 3.
386        assert_eq!(ladder.average_price(5.0), Some(8998.0 / 3.0));
387        assert_eq!(ladder.average_price(0.0), None);
388        assert_eq!(Levels::default().average_price(1.0), None);
389    }
390}