1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
use borsh::{BorshDeserialize, BorshSerialize};
use num_derive::{FromPrimitive, ToPrimitive};
use num_traits::{FromPrimitive, ToPrimitive};
use solana_program::{account_info::AccountInfo, program_error::ProgramError, pubkey::Pubkey};
use std::{cell::RefCell, convert::TryInto, io::Write, rc::Rc};

use crate::critbit::IoError;

pub use crate::orderbook::{OrderSummary, ORDER_SUMMARY_SIZE};

#[derive(BorshDeserialize, BorshSerialize, Clone, Debug, PartialEq)]
#[allow(missing_docs)]
pub enum AccountTag {
    Uninitialized,
    Market,
    EventQueue,
    Bids,
    Asks,
}

#[derive(
    BorshDeserialize, BorshSerialize, Clone, Copy, PartialEq, FromPrimitive, ToPrimitive, Debug,
)]
#[repr(u8)]
#[allow(missing_docs)]
pub enum Side {
    Bid,
    Ask,
}

impl Side {
    /// Helper function to get the opposite side.
    pub fn opposite(&self) -> Self {
        match self {
            Side::Bid => Side::Ask,
            Side::Ask => Side::Bid,
        }
    }
}

#[derive(BorshDeserialize, BorshSerialize, Clone, PartialEq)]
/// Describes what happens when two order with identical callback informations are matched together
pub enum SelfTradeBehavior {
    /// The orders are matched together
    DecrementTake,
    /// The order on the provide side is cancelled. Matching for the current order continues and essentially bypasses
    /// the self-provided order.
    CancelProvide,
    /// The entire transaction fails and the program returns an error.
    AbortTransaction,
}

#[derive(BorshDeserialize, BorshSerialize, Debug)]
/// The orderbook market's central state
pub struct MarketState {
    /// Identifies the account as a [`MarketState`] object.
    pub tag: AccountTag,
    /// The required signer for all market operations.
    pub caller_authority: Pubkey,
    /// The public key of the orderbook's event queue account
    pub event_queue: Pubkey,
    /// The public key of the orderbook's bids account
    pub bids: Pubkey,
    /// The public key of the orderbook's asks account
    pub asks: Pubkey,
    /// The length of an order actor's callback identifier.
    pub callback_id_len: u64,
    /// The length of an order's callback metadata.
    pub callback_info_len: u64,
    /// The current budget of fees that have been collected.
    /// Cranker rewards are taken from this. This value allows
    /// for a verification that the fee was payed in the caller program
    /// runtime while not having to add a CPI call to the serum-core.
    pub fee_budget: u64,
    /// The amount of lamports the market account was created with.
    pub initial_lamports: u64,
    /// The minimum order size that can be inserted into the orderbook after matching.
    pub min_base_order_size: u64,
    //TODO cranked_accs
}

impl MarketState {
    pub(crate) fn check(self) -> Result<Self, ProgramError> {
        if self.tag != AccountTag::Market {
            return Err(ProgramError::InvalidAccountData);
        };
        Ok(self)
    }
}

////////////////////////////////////////////////////
// Events
#[derive(BorshDeserialize, BorshSerialize, Debug)]
/// Events are the primary output of the asset agnostic orderbook
pub enum Event {
    /// A fill event describes a match between a taker order and a provider order
    Fill {
        #[allow(missing_docs)]
        taker_side: Side,
        /// The order id of the maker order
        maker_order_id: u128,
        /// The total quote size of the transaction
        quote_size: u64,
        /// The total base size of the transaction
        base_size: u64,
        /// The callback information for the maker
        maker_callback_info: Vec<u8>,
        /// The callback information for the taker
        taker_callback_info: Vec<u8>,
    },
    /// An out event describes an order which has been taken out of the orderbook
    Out {
        #[allow(missing_docs)]
        side: Side,
        #[allow(missing_docs)]
        order_id: u128,
        #[allow(missing_docs)]
        base_size: u64,
        #[allow(missing_docs)]
        delete: bool,
        #[allow(missing_docs)]
        callback_info: Vec<u8>,
    },
}

impl Event {
    /// Used to serialize an event object into a generic byte writer.
    pub fn serialize<W: Write>(&self, writer: &mut W) -> Result<(), IoError> {
        match self {
            Event::Fill {
                taker_side,
                maker_order_id,
                quote_size,
                base_size,
                maker_callback_info,
                taker_callback_info,
            } => {
                writer.write_all(&[0])?;
                writer.write_all(&[taker_side.to_u8().unwrap()])?;
                writer.write_all(&maker_order_id.to_le_bytes())?;
                writer.write_all(&quote_size.to_le_bytes())?;
                writer.write_all(&base_size.to_le_bytes())?;
                writer.write_all(&maker_callback_info)?;
                writer.write_all(&taker_callback_info)?;
            }
            Event::Out {
                side,
                order_id,
                base_size,
                delete,
                callback_info,
            } => {
                writer.write_all(&[1])?;
                writer.write_all(&[side.to_u8().unwrap()])?;
                writer.write_all(&order_id.to_le_bytes())?;
                writer.write_all(&base_size.to_le_bytes())?;
                writer.write_all(&[(*delete as u8)])?;
                writer.write_all(&callback_info)?;
            }
        };
        Ok(())
    }

    /// Used to deserialize an event object from bytes.
    pub fn deserialize(buf: &mut &[u8], callback_info_len: usize) -> Self {
        match buf[0] {
            0 => Event::Fill {
                taker_side: Side::from_u8(buf[1]).unwrap(),
                maker_order_id: u128::from_le_bytes(buf[2..18].try_into().unwrap()),
                quote_size: u64::from_le_bytes(buf[18..26].try_into().unwrap()),
                base_size: u64::from_le_bytes(buf[26..34].try_into().unwrap()),
                maker_callback_info: buf[34..34 + callback_info_len].to_owned(),
                taker_callback_info: buf[34 + callback_info_len..34 + (callback_info_len << 1)]
                    .to_owned(),
            },
            1 => Event::Out {
                side: Side::from_u8(buf[1]).unwrap(),
                order_id: u128::from_le_bytes(buf[2..18].try_into().unwrap()),
                base_size: u64::from_le_bytes(buf[18..26].try_into().unwrap()),
                delete: buf[26] == 1,
                callback_info: buf[27..27 + callback_info_len].to_owned(),
            },
            _ => unreachable!(),
        }
    }

    /// An event queue is divided into slots. The size of these slots depend on the particular market's `callback_info_len` constant.
    pub fn compute_slot_size(callback_info_len: usize) -> usize {
        1 + 33 + 2 * callback_info_len
    }
}

////////////////////////////////////////////////////
// Event Queue

#[derive(BorshDeserialize, BorshSerialize, Clone)]
/// Describes the current state of the event queue
pub struct EventQueueHeader {
    tag: AccountTag, // Initialized, EventQueue
    head: u64,
    /// The current event queue length
    pub count: u64,
    event_size: u64,
    seq_num: u64,
    register_size: u32, //TODO useful if constant?
}

#[allow(missing_docs)]
pub const EVENT_QUEUE_HEADER_LEN: usize = 37;

impl EventQueueHeader {
    pub(crate) fn initialize(callback_info_len: usize) -> Self {
        Self {
            tag: AccountTag::EventQueue,
            head: 0,
            count: 0,
            event_size: Event::compute_slot_size(callback_info_len) as u64,
            register_size: ORDER_SUMMARY_SIZE + 1,
            seq_num: 0,
        }
    }

    pub(crate) fn check(self) -> Result<Self, ProgramError> {
        if self.tag != AccountTag::EventQueue {
            return Err(ProgramError::InvalidAccountData);
        };
        Ok(self)
    }
}

/// The event queue account contains a serialized header
/// and a circular buffer of serialized events.
///
/// This struct is used at runtime but doesn't represent a serialized event queue
pub struct EventQueue<'a> {
    pub(crate) header: EventQueueHeader,
    pub(crate) buffer: Rc<RefCell<&'a mut [u8]>>, //The whole account data
    callback_info_len: usize,
}

/// The event queue register can hold arbitrary data returned by the AAOB. Currently only used to return [`OrderSummary`] objects.
pub type Register<T> = Option<T>;

impl<'a> EventQueue<'a> {
    pub(crate) fn new_safe(
        header: EventQueueHeader,
        account: &AccountInfo<'a>,
        callback_info_len: usize,
    ) -> Result<Self, ProgramError> {
        let q = Self {
            header: header.check()?,
            buffer: Rc::clone(&account.data),
            callback_info_len,
        };
        q.clear_register();
        Ok(q)
    }

    /// Initialize a new EventQueue object.
    ///
    /// Within a CPI context, the account parameter can be supplied through
    /// ```no_run
    /// use std::rc::Rc;
    /// let a: AccountInfo;
    ///
    /// let event_queue_header = EventQueueHeader::deserialize(&mut &a.data.borrow()[..EVENT_QUEUE_HEADER_LEN]).unwrap()
    /// let event_queue = EventQueue::new(event_queue_header, Rc::clone(&a.data), callback_info_len);
    ///
    /// ```
    pub fn new(
        header: EventQueueHeader,
        account: Rc<RefCell<&'a mut [u8]>>,
        callback_info_len: usize,
    ) -> Self {
        Self {
            header,
            buffer: account,
            callback_info_len,
        }
    }
}

impl<'a> EventQueue<'a> {
    pub(crate) fn gen_order_id(&mut self, limit_price: u64, side: Side) -> u128 {
        let seq_num = self.gen_seq_num();
        let upper = (limit_price as u128) << 64;
        let lower = match side {
            Side::Bid => !seq_num,
            Side::Ask => seq_num,
        };
        upper | (lower as u128)
    }

    fn gen_seq_num(&mut self) -> u64 {
        let seq_num = self.header.seq_num;
        self.header.seq_num += 1;
        seq_num
    }

    pub(crate) fn get_buf_len(&self) -> usize {
        self.buffer.borrow().len() - EVENT_QUEUE_HEADER_LEN - (self.header.register_size as usize)
    }

    pub(crate) fn full(&self) -> bool {
        self.header.count as usize == (self.get_buf_len() / (self.header.event_size as usize))
        //TODO check
    }

    pub(crate) fn push_back(&mut self, event: Event) -> Result<(), Event> {
        if self.full() {
            return Err(event);
        }
        let offset = EVENT_QUEUE_HEADER_LEN
            + (self.header.register_size as usize)
            + (((self.header.head + self.header.count * self.header.event_size) as usize)
                % self.get_buf_len());
        let mut queue_event_data =
            &mut self.buffer.borrow_mut()[offset..offset + (self.header.event_size as usize)];
        event.serialize(&mut queue_event_data).unwrap();

        self.header.count += 1;
        self.header.seq_num += 1;

        Ok(())
    }

    /// Retrieves the event at position index in the queue.
    pub fn peek_at(&self, index: u64) -> Option<Event> {
        if self.header.count <= index {
            return None;
        }

        let header_offset = EVENT_QUEUE_HEADER_LEN + self.header.register_size as usize;
        let offset = ((self.header.head + index * self.header.event_size) as usize
            % self.get_buf_len())
            + header_offset;
        let mut event_data =
            &self.buffer.borrow()[offset..offset + (self.header.event_size as usize)];
        Some(Event::deserialize(&mut event_data, self.callback_info_len))
    }

    /// Returns the effective number of entries that were popped.
    pub(crate) fn pop_n(&mut self, number_of_entries_to_pop: u64) {
        let capped_number_of_entries_to_pop =
            std::cmp::min(self.header.count, number_of_entries_to_pop);
        self.header.count -= capped_number_of_entries_to_pop;
        self.header.head = (self.header.head
            + capped_number_of_entries_to_pop * self.header.event_size)
            % self.get_buf_len() as u64;
    }

    pub(crate) fn write_to_register<T: BorshSerialize + BorshDeserialize>(&self, object: T) {
        let mut register = &mut self.buffer.borrow_mut()
            [EVENT_QUEUE_HEADER_LEN..EVENT_QUEUE_HEADER_LEN + (self.header.register_size as usize)];
        Register::Some(object).serialize(&mut register).unwrap();
    }

    pub(crate) fn clear_register(&self) {
        let mut register = &mut self.buffer.borrow_mut()
            [EVENT_QUEUE_HEADER_LEN..EVENT_QUEUE_HEADER_LEN + (self.header.register_size as usize)];
        Register::<u8>::None.serialize(&mut register).unwrap();
    }

    /// This method is used to deserialize the event queue's register
    ///
    /// The nature of the serialized object should be deductible from caller context
    pub fn read_register<T: BorshSerialize + BorshDeserialize>(
        &self,
    ) -> Result<Register<T>, IoError> {
        let mut register = &self.buffer.borrow()
            [EVENT_QUEUE_HEADER_LEN..EVENT_QUEUE_HEADER_LEN + (self.header.register_size as usize)];
        Register::deserialize(&mut register)
    }

    /// Returns an iterator over all the queue's events
    #[cfg(feature = "no-entrypoint")]
    pub fn iter<'b>(&'b self) -> QueueIterator<'a, 'b> {
        QueueIterator {
            queue_header: &self.header,
            buffer: Rc::clone(&self.buffer),
            current_index: self.header.head as usize,
            callback_info_len: self.callback_info_len,
            buffer_length: self.get_buf_len(),
            header_offset: EVENT_QUEUE_HEADER_LEN + self.header.register_size as usize,
            remaining: self.header.count,
        }
    }
}

#[cfg(feature = "no-entrypoint")]
impl<'a, 'b> IntoIterator for &'b EventQueue<'a> {
    type Item = Event;

    type IntoIter = QueueIterator<'a, 'b>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}
#[cfg(feature = "no-entrypoint")]
/// Utility struct for iterating over a queue
pub struct QueueIterator<'a, 'b> {
    queue_header: &'b EventQueueHeader,
    buffer: Rc<RefCell<&'a mut [u8]>>, //The whole account data
    current_index: usize,
    callback_info_len: usize,
    buffer_length: usize,
    header_offset: usize,
    remaining: u64,
}

#[cfg(feature = "no-entrypoint")]
impl<'a, 'b> Iterator for QueueIterator<'a, 'b> {
    type Item = Event;

    fn next(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            return None;
        }
        let result = Event::deserialize(
            &mut &self.buffer.borrow()[self.header_offset + self.current_index..],
            self.callback_info_len,
        );
        self.current_index =
            (self.current_index + self.queue_header.event_size as usize) % self.buffer_length;
        self.remaining -= 1;
        Some(result)
    }
}

/// This byte flag is set for order_ids with side Bid, and unset for side Ask
pub const ORDER_ID_SIDE_FLAG: u128 = 1 << 63;

/// This helper function deduces an order's side from its order_id
pub fn get_side_from_order_id(order_id: u128) -> Side {
    if ORDER_ID_SIDE_FLAG & order_id != 0 {
        Side::Bid
    } else {
        Side::Ask
    }
}