1use std::{
19 cmp::{Ordering, Reverse},
20 collections::BinaryHeap,
21};
22
23use nautilus_common::{clock::VirtualClock, timer::TimeEventHandler};
24use nautilus_core::UnixNanos;
25
26#[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 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 #[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 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 #[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 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 #[must_use]
134 pub fn is_empty(&self) -> bool {
135 self.heap.is_empty()
136 }
137
138 #[must_use]
140 pub fn len(&self) -> usize {
141 self.heap.len()
142 }
143
144 pub fn clear(&mut self) {
146 self.heap.clear();
147 self.next_sequence = 0;
148 }
149
150 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 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 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 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 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}