Skip to main content

nautilus_backtest/
accumulator.rs

1// -------------------------------------------------------------------------------------------------
2//  Copyright (C) 2015-2026 Nautech Systems Pty Ltd. All rights reserved.
3//  https://nautechsystems.io
4//
5//  Licensed under the GNU Lesser General Public License Version 3.0 (the "License");
6//  You may not use this file except in compliance with the License.
7//  You may obtain a copy of the License at https://www.gnu.org/licenses/lgpl-3.0.en.html
8//
9//  Unless required by applicable law or agreed to in writing, software
10//  distributed under the License is distributed on an "AS IS" BASIS,
11//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//  See the License for the specific language governing permissions and
13//  limitations under the License.
14// -------------------------------------------------------------------------------------------------
15
16//! Time event accumulation and scheduling for the backtest engine.
17
18use std::{
19    cmp::{Ordering, Reverse},
20    collections::BinaryHeap,
21};
22
23use nautilus_common::{clock::VirtualClock, timer::TimeEventHandler};
24use nautilus_core::UnixNanos;
25
26/// Provides a means of accumulating and draining time event handlers using a priority queue.
27///
28/// Events are maintained in timestamp order using a binary heap, allowing efficient
29/// retrieval of the next event to process.
30#[derive(Debug)]
31pub struct TimeEventAccumulator {
32    heap: BinaryHeap<Reverse<AccumulatedTimeEventHandler>>,
33    next_sequence: u64,
34}
35
36#[derive(Debug)]
37struct AccumulatedTimeEventHandler {
38    handler: TimeEventHandler,
39    // Replaces the handler's random event ID as the final heap tie-break.
40    sequence: u64,
41}
42
43impl AccumulatedTimeEventHandler {
44    fn cmp_key(&self, other: &Self) -> Ordering {
45        self.handler
46            .event
47            .ts_event
48            .cmp(&other.handler.event.ts_event)
49            .then_with(|| self.handler.event.name.cmp(&other.handler.event.name))
50            .then_with(|| self.handler.event.ts_init.cmp(&other.handler.event.ts_init))
51            .then_with(|| self.sequence.cmp(&other.sequence))
52    }
53}
54
55impl PartialOrd for AccumulatedTimeEventHandler {
56    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
57        Some(self.cmp(other))
58    }
59}
60
61impl PartialEq for AccumulatedTimeEventHandler {
62    fn eq(&self, other: &Self) -> bool {
63        self.cmp_key(other).is_eq()
64    }
65}
66
67impl Eq for AccumulatedTimeEventHandler {}
68
69impl Ord for AccumulatedTimeEventHandler {
70    fn cmp(&self, other: &Self) -> Ordering {
71        self.cmp_key(other)
72    }
73}
74
75impl TimeEventAccumulator {
76    /// Creates a new [`TimeEventAccumulator`] instance.
77    #[must_use]
78    pub fn new() -> Self {
79        Self {
80            heap: BinaryHeap::new(),
81            next_sequence: 0,
82        }
83    }
84
85    fn push(&mut self, handler: TimeEventHandler) {
86        let sequence = self.next_sequence;
87        self.next_sequence = self
88            .next_sequence
89            .checked_add(1)
90            .expect("Time event accumulator sequence overflow");
91        self.heap
92            .push(Reverse(AccumulatedTimeEventHandler { handler, sequence }));
93    }
94
95    /// Advance the given clock to the `to_time_ns` and push events to the heap.
96    pub fn advance_clock(
97        &mut self,
98        clock: &mut VirtualClock,
99        to_time_ns: UnixNanos,
100        set_time: bool,
101    ) {
102        let events = clock.advance_time(to_time_ns, set_time);
103        let handlers = clock.match_handlers(events);
104        for handler in handlers {
105            self.push(handler);
106        }
107    }
108
109    /// Peek at the next event timestamp without removing it.
110    ///
111    /// Returns `None` if the heap is empty.
112    #[must_use]
113    pub fn peek_next_time(&self) -> Option<UnixNanos> {
114        self.heap.peek().map(|h| h.0.handler.event.ts_event)
115    }
116
117    /// Pop the next event if its timestamp is at or before `ts_now`.
118    ///
119    /// Returns `None` if the heap is empty or the next event is after `ts_now`.
120    pub fn pop_next_at_or_before(&mut self, ts_now: UnixNanos) -> Option<TimeEventHandler> {
121        if self
122            .heap
123            .peek()
124            .is_some_and(|h| h.0.handler.event.ts_event <= ts_now)
125        {
126            self.heap.pop().map(|h| h.0.handler)
127        } else {
128            None
129        }
130    }
131
132    /// Check if the heap is empty.
133    #[must_use]
134    pub fn is_empty(&self) -> bool {
135        self.heap.is_empty()
136    }
137
138    /// Get the number of events in the heap.
139    #[must_use]
140    pub fn len(&self) -> usize {
141        self.heap.len()
142    }
143
144    /// Clear all events from the heap.
145    pub fn clear(&mut self) {
146        self.heap.clear();
147        self.next_sequence = 0;
148    }
149
150    /// Cancels accumulated events for a timer already advanced off its clock.
151    pub(crate) fn cancel_timer(&mut self, name: &str) {
152        self.heap
153            .retain(|handler| handler.0.handler.event.name.as_str() != name);
154    }
155
156    /// Drain all events from the heap in timestamp order.
157    ///
158    /// This is provided for backwards compatibility with code that expects
159    /// batch processing. For iterative processing, prefer `pop_next_at_or_before`.
160    pub fn drain(&mut self) -> Vec<TimeEventHandler> {
161        let mut handlers = Vec::with_capacity(self.heap.len());
162        while let Some(scheduled) = self.heap.pop() {
163            handlers.push(scheduled.0.handler);
164        }
165        handlers
166    }
167}
168
169impl Default for TimeEventAccumulator {
170    /// Creates a new default [`TimeEventAccumulator`] instance.
171    fn default() -> Self {
172        Self::new()
173    }
174}
175
176#[cfg(test)]
177mod determinism_tests {
178    use nautilus_common::timer::{TimeEvent, TimeEventCallback};
179    use nautilus_core::UUID4;
180    use rstest::rstest;
181    use ustr::Ustr;
182
183    use super::*;
184
185    #[rstest]
186    fn test_accumulator_preserves_fifo_order_for_identical_timer_keys() {
187        let callback = TimeEventCallback::from(|_: TimeEvent| {});
188        let first_event = TimeEvent::new(
189            Ustr::from("REBALANCE"),
190            UUID4::from("ffffffff-ffff-4fff-bfff-ffffffffffff"),
191            100.into(),
192            100.into(),
193        );
194        let second_event = TimeEvent::new(
195            Ustr::from("REBALANCE"),
196            UUID4::from("00000000-0000-4000-8000-000000000000"),
197            100.into(),
198            100.into(),
199        );
200
201        let mut accumulator = TimeEventAccumulator::new();
202        accumulator.push(TimeEventHandler::new(first_event.clone(), callback.clone()));
203        accumulator.push(TimeEventHandler::new(second_event, callback));
204
205        let popped = accumulator
206            .pop_next_at_or_before(100.into())
207            .expect("Expected first accumulated timer");
208        assert_eq!(popped.event.event_id, first_event.event_id);
209    }
210}
211
212#[cfg(all(test, feature = "python"))]
213mod tests {
214    use nautilus_common::timer::{TimeEvent, TimeEventCallback};
215    use nautilus_core::UUID4;
216    use pyo3::{Py, Python, prelude::*, types::PyList};
217    use rstest::*;
218    use ustr::Ustr;
219
220    use super::*;
221
222    #[rstest]
223    fn test_accumulator_pop_in_order() {
224        Python::initialize();
225        Python::attach(|py| {
226            let py_list = PyList::empty(py);
227            let py_append = Py::from(py_list.getattr("append").unwrap());
228
229            let mut accumulator = TimeEventAccumulator::new();
230
231            let time_event1 = TimeEvent::new(
232                Ustr::from("TEST_EVENT_1"),
233                UUID4::new(),
234                100.into(),
235                100.into(),
236            );
237            let time_event2 = TimeEvent::new(
238                Ustr::from("TEST_EVENT_2"),
239                UUID4::new(),
240                300.into(),
241                300.into(),
242            );
243            let time_event3 = TimeEvent::new(
244                Ustr::from("TEST_EVENT_3"),
245                UUID4::new(),
246                200.into(),
247                200.into(),
248            );
249
250            let callback = TimeEventCallback::from(py_append.into_any());
251
252            let handler1 = TimeEventHandler::new(time_event1.clone(), callback.clone());
253            let handler2 = TimeEventHandler::new(time_event2.clone(), callback.clone());
254            let handler3 = TimeEventHandler::new(time_event3.clone(), callback);
255
256            accumulator.push(handler1);
257            accumulator.push(handler2);
258            accumulator.push(handler3);
259            assert_eq!(accumulator.len(), 3);
260
261            let popped1 = accumulator.pop_next_at_or_before(1000.into()).unwrap();
262            assert_eq!(popped1.event.ts_event, time_event1.ts_event);
263
264            let popped2 = accumulator.pop_next_at_or_before(1000.into()).unwrap();
265            assert_eq!(popped2.event.ts_event, time_event3.ts_event);
266
267            let popped3 = accumulator.pop_next_at_or_before(1000.into()).unwrap();
268            assert_eq!(popped3.event.ts_event, time_event2.ts_event);
269
270            assert!(accumulator.is_empty());
271        });
272    }
273
274    #[rstest]
275    fn test_accumulator_pop_same_timestamp_in_name_order() {
276        Python::initialize();
277        Python::attach(|py| {
278            let py_list = PyList::empty(py);
279            let py_append = Py::from(py_list.getattr("append").unwrap());
280
281            let mut accumulator = TimeEventAccumulator::new();
282            let callback = TimeEventCallback::from(py_append.into_any());
283
284            let spread_event = TimeEvent::new(
285                Ustr::from("SPREAD_QUOTE_ESM4"),
286                UUID4::new(),
287                100.into(),
288                100.into(),
289            );
290            let time_bar_event = TimeEvent::new(
291                Ustr::from("TIME_BAR_ESM4-2-MINUTE-ASK-INTERNAL"),
292                UUID4::new(),
293                100.into(),
294                100.into(),
295            );
296
297            accumulator.push(TimeEventHandler::new(
298                time_bar_event.clone(),
299                callback.clone(),
300            ));
301            accumulator.push(TimeEventHandler::new(spread_event.clone(), callback));
302
303            let popped1 = accumulator.pop_next_at_or_before(100.into()).unwrap();
304            assert_eq!(popped1.event.ts_event, spread_event.ts_event);
305            assert_eq!(popped1.event.name, spread_event.name);
306
307            let popped2 = accumulator.pop_next_at_or_before(100.into()).unwrap();
308            assert_eq!(popped2.event.ts_event, time_bar_event.ts_event);
309            assert_eq!(popped2.event.name, time_bar_event.name);
310        });
311    }
312
313    #[rstest]
314    fn test_accumulator_pop_respects_timestamp() {
315        Python::initialize();
316        Python::attach(|py| {
317            let py_list = PyList::empty(py);
318            let py_append = Py::from(py_list.getattr("append").unwrap());
319
320            let mut accumulator = TimeEventAccumulator::new();
321
322            let time_event1 = TimeEvent::new(
323                Ustr::from("TEST_EVENT_1"),
324                UUID4::new(),
325                100.into(),
326                100.into(),
327            );
328            let time_event2 = TimeEvent::new(
329                Ustr::from("TEST_EVENT_2"),
330                UUID4::new(),
331                300.into(),
332                300.into(),
333            );
334
335            let callback = TimeEventCallback::from(py_append.into_any());
336
337            accumulator.push(TimeEventHandler::new(time_event1.clone(), callback.clone()));
338            accumulator.push(TimeEventHandler::new(time_event2.clone(), callback));
339
340            let popped1 = accumulator.pop_next_at_or_before(200.into()).unwrap();
341            assert_eq!(popped1.event.ts_event, time_event1.ts_event);
342
343            // Event at 300 should not be returned with ts=200
344            assert!(accumulator.pop_next_at_or_before(200.into()).is_none());
345
346            let popped2 = accumulator.pop_next_at_or_before(300.into()).unwrap();
347            assert_eq!(popped2.event.ts_event, time_event2.ts_event);
348        });
349    }
350
351    #[rstest]
352    fn test_peek_next_time() {
353        Python::initialize();
354        Python::attach(|py| {
355            let py_list = PyList::empty(py);
356            let py_append = Py::from(py_list.getattr("append").unwrap());
357            let callback = TimeEventCallback::from(py_append.into_any());
358
359            let mut accumulator = TimeEventAccumulator::new();
360            assert!(accumulator.peek_next_time().is_none());
361
362            let time_event1 = TimeEvent::new(
363                Ustr::from("TEST_EVENT_1"),
364                UUID4::new(),
365                200.into(),
366                200.into(),
367            );
368            let time_event2 = TimeEvent::new(
369                Ustr::from("TEST_EVENT_2"),
370                UUID4::new(),
371                100.into(),
372                100.into(),
373            );
374
375            accumulator.push(TimeEventHandler::new(time_event1, callback.clone()));
376            assert_eq!(accumulator.peek_next_time(), Some(200.into()));
377
378            accumulator.push(TimeEventHandler::new(time_event2, callback));
379            assert_eq!(accumulator.peek_next_time(), Some(100.into()));
380        });
381    }
382
383    #[rstest]
384    fn test_drain_returns_in_order() {
385        Python::initialize();
386        Python::attach(|py| {
387            let py_list = PyList::empty(py);
388            let py_append = Py::from(py_list.getattr("append").unwrap());
389            let callback = TimeEventCallback::from(py_append.into_any());
390
391            let mut accumulator = TimeEventAccumulator::new();
392
393            for ts in [300u64, 100, 200] {
394                let event = TimeEvent::new(Ustr::from("TEST"), UUID4::new(), ts.into(), ts.into());
395                accumulator.push(TimeEventHandler::new(event, callback.clone()));
396            }
397
398            let handlers = accumulator.drain();
399
400            assert_eq!(handlers.len(), 3);
401            assert_eq!(handlers[0].event.ts_event.as_u64(), 100);
402            assert_eq!(handlers[1].event.ts_event.as_u64(), 200);
403            assert_eq!(handlers[2].event.ts_event.as_u64(), 300);
404            assert!(accumulator.is_empty());
405        });
406    }
407
408    #[rstest]
409    fn test_interleaved_push_pop_maintains_order() {
410        Python::initialize();
411        Python::attach(|py| {
412            let py_list = PyList::empty(py);
413            let py_append = Py::from(py_list.getattr("append").unwrap());
414            let callback = TimeEventCallback::from(py_append.into_any());
415
416            let mut accumulator = TimeEventAccumulator::new();
417            let mut popped_timestamps: Vec<u64> = Vec::new();
418
419            for ts in [100u64, 300] {
420                let event = TimeEvent::new(Ustr::from("TEST"), UUID4::new(), ts.into(), ts.into());
421                accumulator.push(TimeEventHandler::new(event, callback.clone()));
422            }
423
424            let handler = accumulator.pop_next_at_or_before(1000.into()).unwrap();
425            popped_timestamps.push(handler.event.ts_event.as_u64());
426
427            // Simulate callback scheduling new event at 150 (between popped 100 and pending 300)
428            let event = TimeEvent::new(Ustr::from("NEW"), UUID4::new(), 150.into(), 150.into());
429            accumulator.push(TimeEventHandler::new(event, callback));
430
431            while let Some(handler) = accumulator.pop_next_at_or_before(1000.into()) {
432                popped_timestamps.push(handler.event.ts_event.as_u64());
433            }
434
435            assert_eq!(popped_timestamps, vec![100, 150, 300]);
436        });
437    }
438
439    #[rstest]
440    fn test_same_timestamp_events() {
441        Python::initialize();
442        Python::attach(|py| {
443            let py_list = PyList::empty(py);
444            let py_append = Py::from(py_list.getattr("append").unwrap());
445            let callback = TimeEventCallback::from(py_append.into_any());
446
447            let mut accumulator = TimeEventAccumulator::new();
448
449            for i in 0..3 {
450                let event = TimeEvent::new(
451                    Ustr::from(&format!("EVENT_{i}")),
452                    UUID4::new(),
453                    100.into(),
454                    100.into(),
455                );
456                accumulator.push(TimeEventHandler::new(event, callback.clone()));
457            }
458
459            let mut count = 0;
460
461            while let Some(handler) = accumulator.pop_next_at_or_before(100.into()) {
462                assert_eq!(handler.event.ts_event.as_u64(), 100);
463                count += 1;
464            }
465            assert_eq!(count, 3);
466        });
467    }
468
469    #[rstest]
470    fn test_pop_at_exact_timestamp_boundary() {
471        Python::initialize();
472        Python::attach(|py| {
473            let py_list = PyList::empty(py);
474            let py_append = Py::from(py_list.getattr("append").unwrap());
475            let callback = TimeEventCallback::from(py_append.into_any());
476
477            let mut accumulator = TimeEventAccumulator::new();
478
479            let event = TimeEvent::new(Ustr::from("TEST"), UUID4::new(), 100.into(), 100.into());
480            accumulator.push(TimeEventHandler::new(event, callback));
481
482            let handler = accumulator.pop_next_at_or_before(100.into());
483            assert!(handler.is_some());
484            assert_eq!(handler.unwrap().event.ts_event.as_u64(), 100);
485
486            let event2 = TimeEvent::new(Ustr::from("TEST2"), UUID4::new(), 200.into(), 200.into());
487            accumulator.push(TimeEventHandler::new(
488                event2,
489                TimeEventCallback::from(Py::from(py_list.getattr("append").unwrap()).into_any()),
490            ));
491
492            assert!(accumulator.pop_next_at_or_before(199.into()).is_none());
493            assert!(accumulator.pop_next_at_or_before(200.into()).is_some());
494        });
495    }
496}