rustrade_execution/
reduce_only.rs

1//! Which of an instrument's orders were sent reduce-only, kept so a fill can be matched to the
2//! flag of its order.
3//!
4//! Neither an [`Order`](crate::order::Order) nor a venue's report of one carries the flag set by
5//! [`RequestOpen::reduce_only`](crate::order::request::RequestOpen::reduce_only). Whoever sends
6//! the request is the one place that learns it, so whoever needs it for a fill later, such as a
7//! tracker that cuts a reduce-only fill short of flipping a position (see
8//! [`Trade::holding_move`](crate::trade::Trade::holding_move)), has to keep it. A
9//! [`ReduceOnlyBook`] is that record, and finds the order of a fill by its client order id or, for
10//! a fill that carries only the venue's id (a recovered fill), by the venue order id.
11
12use crate::{
13    order::id::{ClientOrderId, OrderId},
14    trade::Trade,
15};
16use rustrade_integration::collection::FnvIndexMap;
17use serde::{Deserialize, Serialize};
18use tracing::debug;
19
20/// An order the book was told of, still in force.
21#[derive(Debug, Clone, Eq, PartialEq, Deserialize, Serialize)]
22struct LiveOrder {
23    reduce_only: bool,
24    venue_id: Option<OrderId>,
25}
26
27/// An order found in a [`ReduceOnlyBook`].
28#[non_exhaustive]
29#[derive(Debug, Clone, Copy, Eq, PartialEq)]
30pub struct BookedOrder<'a> {
31    /// The order's client order id, as the book holds it.
32    pub cid: &'a ClientOrderId,
33    /// Whether the order was sent reduce-only.
34    pub reduce_only: bool,
35}
36
37/// One instrument's record of which orders were sent reduce-only. Plain data with no locking and
38/// no I/O, so the owner keeps it behind whatever synchronisation it already has, one book for each
39/// instrument.
40///
41/// The owner calls, for each order:
42/// 1. [`register`](Self::register) when the open request is sent,
43/// 2. [`acknowledge`](Self::acknowledge) when the venue reports the order's id, and
44/// 3. [`retire`](Self::retire) when the order ends. **Every** order must be retired, or the book
45///    keeps it for good.
46///
47/// Then [`lookup`](Self::lookup) finds the flag of a fill's order.
48///
49/// A retired order stays findable only if it was reduce-only, and only the last
50/// [`RETIRED_CAPACITY`](Self::RETIRED_CAPACITY) of those, oldest dropped first, so that a late
51/// fill of one is still recognised and ordinary orders do not push them out. A late fill of any
52/// other retired order is not found: read that as not reduce-only.
53///
54/// # Serialised form
55/// `{"live": {<cid>: {"reduce_only": bool, "venue_id": <id>|null}}, "retired": {<cid>: <id>|null}}`,
56/// each map in order, either part optional. It is stored as part of its owner's state, so a
57/// change to it is a breaking change. A book loaded with more retired orders than
58/// [`RETIRED_CAPACITY`](Self::RETIRED_CAPACITY) keeps the latest.
59#[derive(Debug, Clone, Default, Eq, PartialEq, Serialize, Deserialize)]
60#[serde(from = "BookParts")]
61pub struct ReduceOnlyBook {
62    /// In the order registered.
63    live: FnvIndexMap<ClientOrderId, LiveOrder>,
64    /// The reduce-only orders that ended, each with its venue order id once known, in the order
65    /// they ended.
66    retired: FnvIndexMap<ClientOrderId, Option<OrderId>>,
67    /// How many of `live` are reduce-only, so that [`has_reduce_only`](Self::has_reduce_only) is
68    /// O(1). Derived, so it is not serialised.
69    #[serde(skip)]
70    live_reduce_only: usize,
71}
72
73/// What is serialised of a [`ReduceOnlyBook`]; loading one rebuilds the rest.
74#[derive(Deserialize)]
75struct BookParts {
76    #[serde(default)]
77    live: FnvIndexMap<ClientOrderId, LiveOrder>,
78    #[serde(default)]
79    retired: FnvIndexMap<ClientOrderId, Option<OrderId>>,
80}
81
82impl From<BookParts> for ReduceOnlyBook {
83    fn from(parts: BookParts) -> Self {
84        let BookParts { live, mut retired } = parts;
85        // An order is live or retired, never both; the live one wins.
86        retired.retain(|cid, _| !live.contains_key(cid));
87        let excess = retired.len().saturating_sub(Self::RETIRED_CAPACITY);
88        retired.drain(..excess);
89        let live_reduce_only = live.values().filter(|order| order.reduce_only).count();
90        Self {
91            live,
92            retired,
93            live_reduce_only,
94        }
95    }
96}
97
98impl ReduceOnlyBook {
99    /// How many retired reduce-only orders the book keeps.
100    pub const RETIRED_CAPACITY: usize = 64;
101
102    /// An empty book.
103    pub fn new() -> Self {
104        Self::default()
105    }
106
107    /// Whether the book holds no order, live or retired.
108    pub fn is_empty(&self) -> bool {
109        self.live.is_empty() && self.retired.is_empty()
110    }
111
112    /// How many orders are live: registered and not yet retired. An owner that retires every
113    /// order sees this fall back to the number it has open.
114    pub fn live_len(&self) -> usize {
115        self.live.len()
116    }
117
118    /// Whether any order the book holds is reduce-only, live or retired. When it is not, every
119    /// [`lookup`](Self::lookup) finds no reduce-only order, so a caller can skip it. O(1).
120    pub fn has_reduce_only(&self) -> bool {
121        self.live_reduce_only > 0 || !self.retired.is_empty()
122    }
123
124    /// Record that the open request `cid` is being sent, reduce-only or not.
125    ///
126    /// A client order id reused for a new order replaces everything an earlier order under it
127    /// left, live or retired, so its flag does not outlive the order. The new order counts as the
128    /// latest registered. Registering a client order id that is still live replaces that order,
129    /// dropping the venue order id it was acknowledged with, so register once for each order sent.
130    pub fn register(&mut self, cid: &ClientOrderId, reduce_only: bool) {
131        self.retired.shift_remove(cid);
132        if let Some(earlier) = self.live.shift_remove(cid) {
133            self.live_reduce_only -= usize::from(earlier.reduce_only);
134        }
135        self.live_reduce_only += usize::from(reduce_only);
136        self.live.insert(
137            cid.clone(),
138            LiveOrder {
139                reduce_only,
140                venue_id: None,
141            },
142        );
143    }
144
145    /// Record the venue's order id for `cid`, live or retired, so a fill that names only that id
146    /// finds the order. Replaces an id given before. Does nothing for an order the book does not
147    /// hold.
148    ///
149    /// An order can end before its id is known, such as one filled on its acknowledgement, so a
150    /// retired order takes it too.
151    pub fn acknowledge(&mut self, cid: &ClientOrderId, venue_id: &OrderId) {
152        if let Some(live) = self.live.get_mut(cid) {
153            live.venue_id = Some(venue_id.clone());
154        } else if let Some(retired) = self.retired.get_mut(cid) {
155            *retired = Some(venue_id.clone());
156        }
157    }
158
159    /// Record that the order `cid` ended. Does nothing for an order the book does not hold.
160    ///
161    /// A reduce-only order moves to the retired orders, dropping the oldest of them when there
162    /// are [`RETIRED_CAPACITY`](Self::RETIRED_CAPACITY). Any other order is forgotten.
163    pub fn retire(&mut self, cid: &ClientOrderId) {
164        if let Some(live) = self.live.shift_remove(cid)
165            && live.reduce_only
166        {
167            self.live_reduce_only -= 1;
168            self.insert_retired(cid.clone(), live.venue_id);
169        }
170    }
171
172    /// [`retire`](Self::retire) every live order for which `is_tracked` is `false`, in the order
173    /// they were registered, so which retirement is dropped first never depends on hashing.
174    ///
175    /// One pass over the live orders, so O(live orders), and it allocates only when a reduce-only
176    /// order ended.
177    pub fn retire_untracked(&mut self, mut is_tracked: impl FnMut(&ClientOrderId) -> bool) {
178        let mut ended: Vec<(ClientOrderId, Option<OrderId>)> = Vec::new();
179        self.live.retain(|cid, order| {
180            let tracked = is_tracked(cid);
181            if !tracked && order.reduce_only {
182                ended.push((cid.clone(), order.venue_id.take()));
183            }
184            tracked
185        });
186        self.live_reduce_only -= ended.len();
187        for (cid, venue_id) in ended {
188            self.insert_retired(cid, venue_id);
189        }
190    }
191
192    /// Find the order a fill belongs to.
193    ///
194    /// By the fill's client order id if it has one, and else by its venue order id: a live order
195    /// first, then a retired one. A client order id the book does not hold finds nothing, and does
196    /// not fall back to the venue's id.
197    pub fn lookup<AssetKey, InstrumentKey>(
198        &self,
199        trade: &Trade<AssetKey, InstrumentKey>,
200    ) -> Option<BookedOrder<'_>> {
201        self.lookup_ids(trade.client_order_id.as_ref(), &trade.order_id)
202    }
203
204    /// [`lookup`](Self::lookup) for the ids of a fill, for a caller that resolved the client order
205    /// id itself. A `cid` the book does not hold finds nothing and does not fall back to
206    /// `order_id`; pass `None` to look up by the venue's id alone.
207    pub fn lookup_ids(
208        &self,
209        cid: Option<&ClientOrderId>,
210        order_id: &OrderId,
211    ) -> Option<BookedOrder<'_>> {
212        if let Some(cid) = cid {
213            return self
214                .live
215                .get_key_value(cid)
216                .map(|(cid, live)| BookedOrder {
217                    cid,
218                    reduce_only: live.reduce_only,
219                })
220                .or_else(|| {
221                    self.retired.get_key_value(cid).map(|(cid, _)| BookedOrder {
222                        cid,
223                        reduce_only: true,
224                    })
225                });
226        }
227        // A live order outranks a retired one under the same venue order id. The scan is of the
228        // open orders, and at most `RETIRED_CAPACITY` retired ones.
229        self.live
230            .iter()
231            .find(|(_, live)| live.venue_id.as_ref() == Some(order_id))
232            .map(|(cid, live)| BookedOrder {
233                cid,
234                reduce_only: live.reduce_only,
235            })
236            .or_else(|| {
237                self.retired
238                    .iter()
239                    .find(|(_, venue_id)| venue_id.as_ref() == Some(order_id))
240                    .map(|(cid, _)| BookedOrder {
241                        cid,
242                        reduce_only: true,
243                    })
244            })
245    }
246
247    /// Whether `trade` is a fill of an order sent reduce-only: [`lookup`](Self::lookup) with an
248    /// order the book does not hold counted as not.
249    pub fn is_reduce_only<AssetKey, InstrumentKey>(
250        &self,
251        trade: &Trade<AssetKey, InstrumentKey>,
252    ) -> bool {
253        self.lookup(trade).is_some_and(|order| order.reduce_only)
254    }
255
256    /// Forget every order, for when the orders the book records are dropped wholesale.
257    pub fn clear(&mut self) {
258        self.live.clear();
259        self.retired.clear();
260        self.live_reduce_only = 0;
261    }
262
263    fn insert_retired(&mut self, cid: ClientOrderId, venue_id: Option<OrderId>) {
264        if self.retired.len() >= Self::RETIRED_CAPACITY
265            && !self.retired.contains_key(&cid)
266            && let Some((evicted, _)) = self.retired.shift_remove_index(0)
267        {
268            debug!(
269                evicted_cid = %evicted,
270                capacity = Self::RETIRED_CAPACITY,
271                "Retired reduce-only orders at capacity: evicting the oldest. A late fill of the \
272                 evicted order is now not recognised as reduce-only."
273            );
274        }
275        self.retired.insert(cid, venue_id);
276    }
277}
278
279#[cfg(test)]
280#[allow(clippy::unwrap_used)] // Test code: panics on bad input are acceptable
281mod tests {
282    use super::*;
283    use crate::{order::id::StrategyId, trade::AssetFees};
284    use chrono::DateTime;
285    use rust_decimal_macros::dec;
286    use rustrade_instrument::Side;
287    use rustrade_instrument::asset::QuoteAsset;
288
289    fn cid(id: &str) -> ClientOrderId {
290        ClientOrderId::new(id)
291    }
292
293    fn venue(id: &str) -> OrderId {
294        OrderId::new(id)
295    }
296
297    fn fill(cid: Option<&str>, venue_id: &str) -> Trade<QuoteAsset, ()> {
298        let trade = Trade::new(
299            crate::trade::TradeId::new("t"),
300            venue(venue_id),
301            (),
302            StrategyId::new("s"),
303            DateTime::UNIX_EPOCH,
304            Side::Sell,
305            dec!(1),
306            dec!(1),
307            None,
308            AssetFees::quote_fees(dec!(0)),
309        );
310        match cid {
311            Some(id) => trade.with_client_order_id(self::cid(id)),
312            None => trade,
313        }
314    }
315
316    fn flag(book: &ReduceOnlyBook, trade: &Trade<QuoteAsset, ()>) -> Option<bool> {
317        book.lookup(trade).map(|order| order.reduce_only)
318    }
319
320    #[test]
321    fn a_fill_finds_its_order_by_client_order_id() {
322        let mut book = ReduceOnlyBook::new();
323        book.register(&cid("ro"), true);
324        book.register(&cid("plain"), false);
325        assert_eq!(flag(&book, &fill(Some("ro"), "v")), Some(true));
326        assert_eq!(flag(&book, &fill(Some("plain"), "v")), Some(false));
327        assert_eq!(flag(&book, &fill(Some("other"), "v")), None);
328        assert!(book.is_reduce_only(&fill(Some("ro"), "v")));
329        assert!(!book.is_reduce_only(&fill(Some("plain"), "v")));
330        assert!(!book.is_reduce_only(&fill(Some("other"), "v")));
331    }
332
333    #[test]
334    fn a_fill_naming_only_the_venue_id_finds_its_order_once_acknowledged() {
335        let mut book = ReduceOnlyBook::new();
336        book.register(&cid("ro"), true);
337        assert_eq!(flag(&book, &fill(None, "v1")), None, "not yet acknowledged");
338        book.acknowledge(&cid("ro"), &venue("v1"));
339        let trade = fill(None, "v1");
340        let found = book.lookup(&trade).unwrap();
341        assert_eq!((found.cid, found.reduce_only), (&cid("ro"), true));
342    }
343
344    #[test]
345    fn a_client_order_id_the_book_lacks_does_not_fall_back_to_the_venue_id() {
346        let mut book = ReduceOnlyBook::new();
347        book.register(&cid("ro"), true);
348        book.acknowledge(&cid("ro"), &venue("v1"));
349        assert_eq!(flag(&book, &fill(Some("other"), "v1")), None);
350    }
351
352    #[test]
353    fn a_retired_reduce_only_order_is_still_found_and_an_ordinary_one_is_forgotten() {
354        let mut book = ReduceOnlyBook::new();
355        book.register(&cid("ro"), true);
356        book.register(&cid("plain"), false);
357        book.acknowledge(&cid("ro"), &venue("v1"));
358        book.acknowledge(&cid("plain"), &venue("v2"));
359        book.retire(&cid("ro"));
360        book.retire(&cid("plain"));
361        assert_eq!(flag(&book, &fill(Some("ro"), "x")), Some(true));
362        assert_eq!(flag(&book, &fill(None, "v1")), Some(true));
363        assert_eq!(flag(&book, &fill(Some("plain"), "x")), None);
364        assert_eq!(flag(&book, &fill(None, "v2")), None);
365    }
366
367    #[test]
368    fn an_order_retired_before_its_acknowledgement_takes_the_venue_id_after() {
369        let mut book = ReduceOnlyBook::new();
370        book.register(&cid("ro"), true);
371        book.retire(&cid("ro"));
372        assert_eq!(flag(&book, &fill(None, "v1")), None);
373        book.acknowledge(&cid("ro"), &venue("v1"));
374        assert_eq!(flag(&book, &fill(None, "v1")), Some(true));
375    }
376
377    #[test]
378    fn a_live_order_outranks_a_retired_one_under_the_same_venue_id() {
379        let mut book = ReduceOnlyBook::new();
380        book.register(&cid("old"), true);
381        book.acknowledge(&cid("old"), &venue("v1"));
382        book.retire(&cid("old"));
383        book.register(&cid("new"), false);
384        book.acknowledge(&cid("new"), &venue("v1"));
385        let trade = fill(None, "v1");
386        let found = book.lookup(&trade).unwrap();
387        assert_eq!((found.cid, found.reduce_only), (&cid("new"), false));
388    }
389
390    #[test]
391    fn registering_a_reused_client_order_id_drops_what_the_earlier_order_left() {
392        for retire_first in [false, true] {
393            let mut book = ReduceOnlyBook::new();
394            book.register(&cid("c"), true);
395            book.acknowledge(&cid("c"), &venue("v1"));
396            if retire_first {
397                book.retire(&cid("c"));
398            }
399            book.register(&cid("c"), false);
400            assert_eq!(flag(&book, &fill(Some("c"), "x")), Some(false));
401            assert_eq!(flag(&book, &fill(None, "v1")), None, "{retire_first}");
402        }
403    }
404
405    #[test]
406    fn the_oldest_retirement_is_dropped_at_capacity() {
407        let mut book = ReduceOnlyBook::new();
408        let cids: Vec<_> = (0..=ReduceOnlyBook::RETIRED_CAPACITY)
409            .map(|i| cid(&format!("c{i}")))
410            .collect();
411        for c in &cids {
412            book.register(c, true);
413            book.retire(c);
414        }
415        assert_eq!(book.retired.len(), ReduceOnlyBook::RETIRED_CAPACITY);
416        assert_eq!(flag(&book, &fill(Some("c0"), "x")), None);
417        assert_eq!(flag(&book, &fill(Some("c1"), "x")), Some(true));
418        assert_eq!(flag(&book, &fill(Some("c64"), "x")), Some(true));
419    }
420
421    #[test]
422    fn ordinary_orders_do_not_push_out_retired_reduce_only_ones() {
423        let mut book = ReduceOnlyBook::new();
424        book.register(&cid("ro"), true);
425        book.retire(&cid("ro"));
426        for i in 0..ReduceOnlyBook::RETIRED_CAPACITY * 2 {
427            let c = cid(&format!("p{i}"));
428            book.register(&c, false);
429            book.retire(&c);
430        }
431        assert_eq!(flag(&book, &fill(Some("ro"), "x")), Some(true));
432    }
433
434    #[test]
435    fn retire_untracked_retires_in_the_order_registered() {
436        let mut book = ReduceOnlyBook::new();
437        let cids: Vec<_> = (0..5).map(|i| cid(&format!("c{i}"))).collect();
438        for c in &cids {
439            book.register(c, true);
440        }
441        let kept = cid("c2");
442        book.retire_untracked(|c| *c == kept);
443        assert!(
444            book.retired
445                .keys()
446                .eq([&cids[0], &cids[1], &cids[3], &cids[4]])
447        );
448        assert!(book.live.keys().eq([&kept]));
449    }
450
451    #[test]
452    fn retire_untracked_keeps_the_reduce_only_count_and_forgets_ordinary_orders() {
453        let mut book = ReduceOnlyBook::new();
454        book.register(&cid("ro1"), true);
455        book.register(&cid("gone"), false);
456        book.register(&cid("ro2"), true);
457        book.register(&cid("kept"), false);
458        book.retire_untracked(|c| *c == cid("kept"));
459        assert_eq!(book.live_reduce_only, 0);
460        assert!(book.live.keys().eq([&cid("kept")]));
461        assert!(book.retired.keys().eq([&cid("ro1"), &cid("ro2")]));
462        assert!(book.has_reduce_only(), "retired ones are still held");
463        book.retired.clear();
464        assert!(!book.has_reduce_only());
465    }
466
467    #[test]
468    fn retiring_or_acknowledging_an_unknown_order_does_nothing() {
469        let mut book = ReduceOnlyBook::new();
470        book.retire(&cid("none"));
471        book.acknowledge(&cid("none"), &venue("v"));
472        assert!(book.is_empty());
473    }
474
475    #[test]
476    fn clear_forgets_everything() {
477        let mut book = ReduceOnlyBook::new();
478        book.register(&cid("a"), true);
479        book.register(&cid("b"), true);
480        book.retire(&cid("b"));
481        book.clear();
482        assert!(book.is_empty());
483    }
484
485    #[test]
486    fn is_empty_and_live_len_count_live_and_retired_orders() {
487        let mut book = ReduceOnlyBook::new();
488        assert_eq!((book.is_empty(), book.live_len()), (true, 0));
489        book.register(&cid("plain"), false);
490        book.register(&cid("ro"), true);
491        assert_eq!((book.is_empty(), book.live_len()), (false, 2), "live only");
492        book.retire(&cid("ro"));
493        assert_eq!((book.is_empty(), book.live_len()), (false, 1));
494        book.retire(&cid("plain"));
495        assert_eq!(
496            (book.is_empty(), book.live_len()),
497            (false, 0),
498            "retired only"
499        );
500    }
501
502    #[test]
503    fn has_reduce_only_follows_the_orders_held() {
504        let mut book = ReduceOnlyBook::new();
505        assert!(!book.has_reduce_only());
506        book.register(&cid("plain"), false);
507        assert!(!book.has_reduce_only());
508        book.register(&cid("ro"), true);
509        assert!(book.has_reduce_only());
510        book.register(&cid("ro"), false);
511        assert!(!book.has_reduce_only(), "replaced by an ordinary order");
512        book.register(&cid("ro"), true);
513        book.retire(&cid("ro"));
514        assert!(book.has_reduce_only(), "retired but still held");
515        book.clear();
516        assert!(!book.has_reduce_only());
517        book.register(&cid("a"), true);
518        book.register(&cid("b"), true);
519        book.retire_untracked(|c| *c == cid("a"));
520        assert_eq!((book.live_len(), book.has_reduce_only()), (1, true));
521    }
522
523    #[test]
524    fn the_serialised_form_is_pinned_and_keeps_the_retirement_order() {
525        let mut book = ReduceOnlyBook::new();
526        book.register(&cid("b"), true);
527        book.acknowledge(&cid("b"), &venue("v"));
528        book.retire(&cid("b"));
529        book.register(&cid("a"), true);
530        book.retire(&cid("a"));
531        book.register(&cid("c"), false);
532        let json = serde_json::to_string(&book).unwrap();
533        assert_eq!(
534            json,
535            r#"{"live":{"c":{"reduce_only":false,"venue_id":null}},"retired":{"b":"v","a":null}}"#
536        );
537        let loaded: ReduceOnlyBook = serde_json::from_str(&json).unwrap();
538        assert!(loaded.retired.keys().eq(book.retired.keys()));
539        assert_eq!(loaded.has_reduce_only(), book.has_reduce_only());
540    }
541
542    #[test]
543    fn a_loaded_book_keeps_its_bound_and_counts_its_live_reduce_only_orders() {
544        // Built as text: `serde_json::Value` would sort the keys.
545        let retired: Vec<String> = (0..100).map(|i| format!(r#""c{i}":null"#)).collect();
546        let json = format!(
547            r#"{{"live":{{"l":{{"reduce_only":true,"venue_id":null}},"c99":{{"reduce_only":false,"venue_id":null}}}},"retired":{{{}}}}}"#,
548            retired.join(",")
549        );
550        let mut book: ReduceOnlyBook = serde_json::from_str(&json).unwrap();
551        assert_eq!(book.retired.len(), ReduceOnlyBook::RETIRED_CAPACITY);
552        assert!(book.retired.keys().next().is_some_and(|c| *c == cid("c35")));
553        assert!(!book.retired.contains_key(&cid("c99")), "live wins");
554        book.retire(&cid("l"));
555        assert_eq!(book.retired.len(), ReduceOnlyBook::RETIRED_CAPACITY);
556        book.retire(&cid("c99"));
557        assert!(book.live.is_empty() && book.live_reduce_only == 0);
558    }
559
560    #[test]
561    fn a_book_round_trips_through_json_and_loads_from_nothing() {
562        let mut book = ReduceOnlyBook::new();
563        book.register(&cid("live"), true);
564        book.acknowledge(&cid("live"), &venue("v1"));
565        book.register(&cid("gone"), true);
566        book.retire(&cid("gone"));
567        let json = serde_json::to_string(&book).unwrap();
568        assert_eq!(serde_json::from_str::<ReduceOnlyBook>(&json).unwrap(), book);
569        assert_eq!(
570            serde_json::from_str::<ReduceOnlyBook>("{}").unwrap(),
571            ReduceOnlyBook::new()
572        );
573    }
574}
rustrade_execution/reduce_only.rs

rustrade_execution/
reduce_only.rs
