asset_agnostic_orderbook/state/
event_queue.rs

1//! The event queue is one of two information outputs of the AOB.
2//!
3//! It provides a linear event-based interface to propagate the matching and modifying of orders
4//! to other use-case specific data structures. It is essential to bypass the need for predicting
5//! an instruction's required account beforehand : the runtime can freely decide which users to
6//! match together this way.
7use borsh::{BorshDeserialize, BorshSerialize};
8use bytemuck::{CheckedBitPattern, NoUninit, Pod, Zeroable};
9use num_derive::FromPrimitive;
10use num_traits::FromPrimitive;
11use solana_program::{entrypoint::ProgramResult, msg, program_error::ProgramError};
12
13use crate::error::AoError;
14pub use crate::state::orderbook::{OrderSummary, ORDER_SUMMARY_SIZE};
15pub use crate::utils::get_spread;
16
17use super::{AccountTag, Side};
18
19#[derive(Clone, Zeroable, Pod, Copy, Debug, PartialEq)]
20#[repr(C)]
21/// Represents an order being filled, a match between two parties.
22pub struct FillEvent {
23    /// The u8 representation for an [`AccountTag`] enum
24    pub tag: u8,
25    /// The u8 representation for a [`Side`] enum
26    pub taker_side: u8,
27    pub(crate) _padding: [u8; 6],
28    /// The total quote size of the transaction
29    pub quote_size: u64,
30    /// The order id of the maker order
31    #[cfg(target_os = "solana")]
32    pub maker_order_id: u128,
33    #[cfg(not(target_os = "solana"))]
34    /// The order id of the maker order
35    pub maker_order_id: [u64; 2],
36    /// The total base size of the transaction
37    pub base_size: u64,
38}
39
40impl FillEvent {
41    /// Byte length of the FillEvent object
42    pub const LEN: usize = std::mem::size_of::<Self>();
43}
44
45#[derive(Clone, Zeroable, Pod, Copy, Debug, PartialEq)]
46#[repr(C)]
47/// Represents an order being modified or yanked from the orderbook without being matched
48pub struct OutEvent {
49    /// The u8 representation for an [`AccountTag`] enum
50    pub tag: u8,
51    /// The u8 representation for a [`Side`] enum
52    pub side: u8,
53    pub(crate) _padding: [u8; 14],
54    /// The order id of the maker order
55    #[cfg(target_os = "solana")]
56    pub order_id: u128,
57    #[cfg(not(target_os = "solana"))]
58    /// The order id of the maker order
59    pub order_id: [u64; 2],
60    /// The total base size of the transaction
61    pub base_size: u64,
62}
63
64#[derive(PartialEq, Debug)]
65/// An unmutable reference to an event in the EventQueue
66pub enum EventRef<'a, C> {
67    #[allow(missing_docs)]
68    Fill(FillEventRef<'a, C>),
69    #[allow(missing_docs)]
70    Out(OutEventRef<'a, C>),
71}
72
73#[derive(PartialEq, Debug)]
74/// An immutable reference to a Fill event in the EventQueue, as well as the associated callback information.
75pub struct FillEventRef<'a, C> {
76    #[allow(missing_docs)]
77    pub event: &'a FillEvent,
78    #[allow(missing_docs)]
79    pub maker_callback_info: &'a C,
80    #[allow(missing_docs)]
81    pub taker_callback_info: &'a C,
82}
83
84#[derive(PartialEq, Debug)]
85/// An immutable reference to an Out event in the EventQueue, as well as the associated callback information.
86pub struct OutEventRef<'a, C> {
87    #[allow(missing_docs)]
88    pub event: &'a OutEvent,
89    #[allow(missing_docs)]
90    pub callback_info: &'a C,
91}
92
93#[derive(FromPrimitive, Clone, Copy, CheckedBitPattern, NoUninit)]
94#[repr(u8)]
95pub(crate) enum EventTag {
96    Fill,
97    Out,
98}
99
100pub(crate) type GenericEvent = FillEvent;
101
102pub(crate) trait Event {
103    fn to_generic(&mut self) -> &GenericEvent;
104}
105
106impl Event for FillEvent {
107    fn to_generic(&mut self) -> &GenericEvent {
108        self.tag = EventTag::Fill as u8;
109        self
110    }
111}
112
113impl Event for OutEvent {
114    fn to_generic(&mut self) -> &GenericEvent {
115        self.tag = EventTag::Out as u8;
116        bytemuck::cast_ref(self)
117    }
118}
119
120////////////////////////////////////////////////////
121// Event Queue
122
123#[derive(BorshDeserialize, BorshSerialize, Clone, Copy, Pod, Zeroable)]
124#[repr(C)]
125/// Describes the current state of the event queue
126pub struct EventQueueHeader {
127    /// The current event
128    pub head: u64,
129    /// The current event queue length
130    pub count: u64,
131    seq_num: u64,
132}
133
134impl EventQueueHeader {
135    /// The byte size for the EventQueueHeader object
136    pub const LEN: usize = std::mem::size_of::<Self>();
137}
138
139/// The event queue account contains a serialized header, a register
140/// and a circular buffer of serialized events.
141///
142/// This struct is used at runtime but doesn't represent a serialized event queue
143pub struct EventQueue<'a, C> {
144    pub(crate) header: &'a mut EventQueueHeader,
145    pub(crate) events: &'a mut [FillEvent],
146    pub(crate) callback_infos: &'a mut [C],
147}
148
149impl<'queue, C: Pod> EventQueue<'queue, C> {
150    /// Instantiates an event queue object from an account's buffer
151    pub fn from_buffer(
152        buf: &'queue mut [u8],
153        expected_tag: AccountTag,
154    ) -> Result<Self, ProgramError> {
155        let callback_info_len = std::mem::size_of::<C>();
156
157        let capacity =
158            (buf.len() - 8 - EventQueueHeader::LEN) / (FillEvent::LEN + 2 * callback_info_len);
159        let account_tag: &mut u64 = bytemuck::from_bytes_mut(&mut buf[0..8]);
160
161        if *account_tag != expected_tag as u64 {
162            return Err(AoError::AccountTagMismatch.into());
163        }
164        *account_tag = AccountTag::EventQueue as u64;
165
166        let (header, remaining) = buf[8..].split_at_mut(EventQueueHeader::LEN);
167
168        let (events, callback_infos) = remaining.split_at_mut(capacity * FillEvent::LEN);
169        Ok(Self {
170            header: bytemuck::from_bytes_mut(header),
171            events: bytemuck::cast_slice_mut(events),
172            callback_infos: bytemuck::cast_slice_mut(callback_infos),
173        })
174    }
175}
176
177impl<'queue, C: Clone> EventQueue<'queue, C> {
178    pub(crate) fn push_back<Ev: Event>(
179        &mut self,
180        mut event: Ev,
181        maker_callback_info: Option<&C>,
182        taker_callback_info: Option<&C>,
183    ) -> Result<(), Ev> {
184        if self.full() {
185            return Err(event);
186        }
187        let generic_event = event.to_generic();
188        let event_idx =
189            (self.header.head as usize + self.header.count as usize) % self.events.len();
190        self.events[event_idx] = *generic_event;
191
192        self.header.count += 1;
193
194        if let Some(c) = maker_callback_info {
195            self.callback_infos[event_idx * 2] = c.clone();
196        }
197
198        if let Some(c) = taker_callback_info {
199            self.callback_infos[event_idx * 2 + 1] = c.clone();
200        }
201
202        Ok(())
203    }
204}
205
206impl<'queue, C> EventQueue<'queue, C> {
207    /// Compute the allocation size for an event queue of a desired capacity
208    pub fn compute_allocation_size(desired_event_capacity: usize) -> usize {
209        desired_event_capacity * (FillEvent::LEN + 2 * std::mem::size_of::<C>())
210            + EventQueueHeader::LEN
211            + 8
212    }
213
214    pub(crate) fn check_buffer_size(buffer: &[u8]) -> ProgramResult {
215        const HEADER_OFFSET: usize = EventQueueHeader::LEN + 8;
216        let event_size: usize = FillEvent::LEN + 2 * std::mem::size_of::<C>();
217        let account_len = buffer.len();
218        if account_len < HEADER_OFFSET + 5 * event_size {
219            msg!("The event queue account is too small!");
220            return Err(ProgramError::InvalidAccountData);
221        }
222        if (account_len - HEADER_OFFSET) % event_size != 0 {
223            msg!("Event queue account size is invalid!");
224            return Err(ProgramError::InvalidAccountData);
225        }
226        Ok(())
227    }
228
229    pub(crate) fn gen_order_id(&mut self, limit_price: u64, side: Side) -> u128 {
230        let seq_num = self.gen_seq_num();
231        let upper = (limit_price as u128) << 64;
232        let lower = match side {
233            Side::Bid => !seq_num,
234            Side::Ask => seq_num,
235        };
236        upper | (lower as u128)
237    }
238
239    fn gen_seq_num(&mut self) -> u64 {
240        let seq_num = self.header.seq_num;
241        self.header.seq_num += 1;
242        seq_num
243    }
244
245    pub(crate) fn full(&self) -> bool {
246        self.header.count as usize == self.events.len()
247    }
248
249    /// Retrieves the event at position `index` in the queue.
250    pub fn peek_at(&self, index: u64) -> Option<EventRef<'_, C>> {
251        if self.header.count <= index {
252            return None;
253        }
254
255        let event_idx = (self.header.head.checked_add(index).unwrap() as usize) % self.events.len();
256        Some(self.get_event(event_idx))
257    }
258
259    fn get_event(&self, event_idx: usize) -> EventRef<'_, C> {
260        let event = &self.events[event_idx];
261        match EventTag::from_u8(event.tag).unwrap() {
262            EventTag::Fill => EventRef::Fill(FillEventRef {
263                event,
264                maker_callback_info: &self.callback_infos[2 * event_idx],
265                taker_callback_info: &self.callback_infos[2 * event_idx + 1],
266            }),
267            EventTag::Out => EventRef::Out(OutEventRef {
268                event: bytemuck::cast_ref(event),
269                callback_info: &self.callback_infos[2 * event_idx],
270            }),
271        }
272    }
273
274    /// Pop n entries from the event queue
275    pub fn pop_n(&mut self, number_of_entries_to_pop: u64) {
276        let capped_number_of_entries_to_pop =
277            std::cmp::min(self.header.count, number_of_entries_to_pop);
278        self.header.count -= capped_number_of_entries_to_pop;
279        self.header.head =
280            (self.header.head + capped_number_of_entries_to_pop) % (self.events.len() as u64);
281    }
282
283    /// Returns an iterator over all the queue's events
284    pub fn iter(&self) -> QueueIterator<'_, C> {
285        QueueIterator {
286            queue: self,
287            current_index: 0,
288            remaining: self.header.count,
289        }
290    }
291
292    /// Checks whether the event queue is currently empty
293    pub fn is_empty(&self) -> bool {
294        self.header.count == 0
295    }
296
297    /// Returns the current length of the event queue
298    pub fn len(&self) -> u64 {
299        self.header.count
300    }
301}
302
303/// Utility struct for iterating over a queue
304pub struct QueueIterator<'a, C> {
305    queue: &'a EventQueue<'a, C>,
306    current_index: usize,
307    remaining: u64,
308}
309
310impl<'a, C> Iterator for QueueIterator<'a, C> {
311    type Item = EventRef<'a, C>;
312
313    fn next(&mut self) -> Option<Self::Item> {
314        if self.remaining == 0 {
315            return None;
316        }
317        let event_idx =
318            (self.queue.header.head as usize + self.current_index) % self.queue.events.len();
319        self.current_index += 1;
320        self.remaining -= 1;
321        Some(self.queue.get_event(event_idx))
322    }
323}
324
325#[cfg(test)]
326mod tests {
327    use super::*;
328
329    type EventQueueTest<'a> = EventQueue<'a, [u8; 32]>;
330
331    #[test]
332    fn test_event_queue_0() {
333        let allocation_size = EventQueue::<[u8; 32]>::compute_allocation_size(100);
334        let mut buffer = vec![0; allocation_size];
335
336        assert!(EventQueueTest::from_buffer(&mut buffer, AccountTag::EventQueue).is_err());
337
338        assert!(EventQueueTest::check_buffer_size(&[0; 10]).is_err());
339        assert!(EventQueueTest::check_buffer_size(&[0; 1000]).is_err());
340
341        let mut event_queue =
342            EventQueueTest::from_buffer(&mut buffer, AccountTag::Uninitialized).unwrap();
343
344        let mut seq_gen = 0..;
345        let mut parity_gen = 0..;
346
347        for _ in 0..100 {
348            if parity_gen.next().unwrap() % 7 != 3 {
349                #[allow(clippy::let_and_return)]
350                event_queue
351                    .push_back(
352                        FillEvent {
353                            tag: EventTag::Fill as u8,
354                            taker_side: Side::Ask as u8,
355                            _padding: [0; 6],
356                            quote_size: seq_gen.next().unwrap(),
357                            maker_order_id: {
358                                let s = seq_gen.next().unwrap() as u128;
359                                #[cfg(not(target_os = "solana"))]
360                                let s = [s as u64, 0];
361                                s
362                            },
363                            base_size: seq_gen.next().unwrap(),
364                        },
365                        Some(&[seq_gen.next().unwrap() as u8; 32]),
366                        Some(&[seq_gen.next().unwrap() as u8; 32]),
367                    )
368                    .unwrap();
369            } else {
370                #[allow(clippy::let_and_return)]
371                event_queue
372                    .push_back(
373                        OutEvent {
374                            tag: EventTag::Out as u8,
375                            side: Side::Ask as u8,
376                            _padding: [0; 14],
377                            base_size: seq_gen.next().unwrap(),
378                            order_id: {
379                                let s = seq_gen.next().unwrap() as u128;
380                                #[cfg(not(target_os = "solana"))]
381                                let s = [s as u64, 0];
382                                s
383                            },
384                        },
385                        Some(&[seq_gen.next().unwrap() as u8; 32]),
386                        None,
387                    )
388                    .unwrap();
389            }
390        }
391        #[allow(clippy::let_and_return)]
392        let extra_event = FillEvent {
393            tag: EventTag::Fill as u8,
394            taker_side: Side::Ask as u8,
395            _padding: [0; 6],
396            quote_size: seq_gen.next().unwrap(),
397            maker_order_id: {
398                let s = seq_gen.next().unwrap() as u128;
399                #[cfg(not(target_os = "solana"))]
400                let s = [s as u64, 0];
401                s
402            },
403            base_size: seq_gen.next().unwrap(),
404        };
405        assert_eq!(
406            extra_event,
407            event_queue.push_back(extra_event, None, None).unwrap_err()
408        );
409        let mut number_of_events = 0;
410        let mut seq_gen = 0..;
411        let mut parity_gen = 0..;
412
413        assert!(event_queue.peek_at(100).is_none());
414
415        for (i, e) in event_queue.iter().enumerate() {
416            let is_fill = parity_gen.next().unwrap() % 7 != 3;
417            match e {
418                EventRef::Out(o) => {
419                    assert!(!is_fill);
420                    #[allow(clippy::let_and_return)]
421                    {
422                        assert_eq!(
423                            o,
424                            OutEventRef {
425                                event: &OutEvent {
426                                    tag: EventTag::Out as u8,
427                                    side: Side::Ask as u8,
428                                    _padding: [0; 14],
429                                    base_size: seq_gen.next().unwrap(),
430                                    order_id: {
431                                        let s = seq_gen.next().unwrap() as u128;
432                                        #[cfg(not(target_os = "solana"))]
433                                        let s = [s as u64, 0];
434                                        s
435                                    },
436                                },
437                                callback_info: &[seq_gen.next().unwrap() as u8; 32]
438                            }
439                        );
440                    }
441                }
442                EventRef::Fill(e) => {
443                    assert!(is_fill);
444                    #[allow(clippy::let_and_return)]
445                    {
446                        assert_eq!(
447                            e,
448                            FillEventRef {
449                                event: &FillEvent {
450                                    tag: EventTag::Fill as u8,
451                                    taker_side: Side::Ask as u8,
452                                    _padding: [0; 6],
453                                    quote_size: seq_gen.next().unwrap(),
454                                    maker_order_id: {
455                                        let s = seq_gen.next().unwrap() as u128;
456                                        #[cfg(not(target_os = "solana"))]
457                                        let s = [s as u64, 0];
458                                        s
459                                    },
460                                    base_size: seq_gen.next().unwrap(),
461                                },
462                                maker_callback_info: &[seq_gen.next().unwrap() as u8; 32],
463                                taker_callback_info: &[seq_gen.next().unwrap() as u8; 32]
464                            }
465                        );
466                    }
467                    assert_eq!(EventRef::Fill(e), event_queue.peek_at(i as u64).unwrap());
468                }
469            }
470            number_of_events = i + 1;
471        }
472        assert_eq!(number_of_events, 100);
473    }
474}
asset_agnostic_orderbook/state/event_queue.rs

asset_agnostic_orderbook/state/
event_queue.rs
