fusionamm_core/math/
tick_array_sequence.rs

1//
2// Copyright (c) Cryptic Dot
3//
4// Modification based on Orca Whirlpools (https://github.com/orca-so/whirlpools),
5// originally licensed under the Apache License, Version 2.0, prior to February 26, 2025.
6//
7// Modifications licensed under FusionAMM SDK Source-Available License v1.0
8// See the LICENSE file in the project root for license information.
9//
10
11use crate::{
12    get_initializable_tick_index, get_next_initializable_tick_index, get_prev_initializable_tick_index, CoreError, TickArrayFacade, TickFacade,
13    INVALID_TICK_ARRAY_SEQUENCE, INVALID_TICK_INDEX, MAX_TICK_INDEX, MIN_TICK_INDEX, TICK_ARRAY_SIZE, TICK_INDEX_OUT_OF_BOUNDS, TICK_SEQUENCE_EMPTY,
14};
15use once_cell::sync::Lazy;
16use std::collections::HashMap;
17
18static DEFAULT_TICK_FACADE: Lazy<TickFacade> = Lazy::new(TickFacade::default);
19
20#[derive(Clone, Debug, PartialEq, Eq)]
21pub struct TickArraySequence {
22    pub start_tick_index: i32,
23    pub end_tick_index: i32,
24    pub ticks: HashMap<i32, TickFacade>,
25    pub tick_spacing: u16,
26}
27
28impl TickArraySequence {
29    pub fn new(tick_arrays: Vec<TickArrayFacade>, tick_spacing: u16) -> Result<Self, CoreError> {
30        let mut tick_arrays = tick_arrays;
31        tick_arrays.sort_by_key(|tick_array| tick_array.start_tick_index);
32
33        if tick_arrays.is_empty() {
34            return Err(TICK_SEQUENCE_EMPTY);
35        }
36
37        let mut ticks = HashMap::new();
38
39        let start_tick_index = tick_arrays[0].start_tick_index;
40        let end_tick_index = tick_arrays.last().unwrap().start_tick_index + TICK_ARRAY_SIZE as i32 * tick_spacing as i32 - 1;
41
42        for tick_array in tick_arrays {
43            for i in 0..tick_array.ticks.len() {
44                if tick_array.ticks[i].initialized {
45                    ticks.insert(tick_array.start_tick_index + i as i32 * tick_spacing as i32, tick_array.ticks[i]);
46                }
47            }
48        }
49
50        Ok(Self {
51            start_tick_index,
52            end_tick_index,
53            ticks,
54            tick_spacing,
55        })
56    }
57
58    /// Returns the first valid tick index in the sequence.
59    pub fn start_index(&self) -> i32 {
60        self.start_tick_index.max(MIN_TICK_INDEX)
61    }
62
63    /// Returns the last valid tick index in the sequence.
64    pub fn end_index(&self) -> i32 {
65        self.end_tick_index.min(MAX_TICK_INDEX)
66    }
67
68    pub fn tick(&self, tick_index: i32) -> Result<&TickFacade, CoreError> {
69        if (tick_index < self.start_index()) || (tick_index > self.end_index()) {
70            return Err(TICK_INDEX_OUT_OF_BOUNDS);
71        }
72        if (tick_index % self.tick_spacing as i32) != 0 {
73            return Err(INVALID_TICK_INDEX);
74        }
75
76        let tick = match self.ticks.get(&tick_index) {
77            None => &DEFAULT_TICK_FACADE,
78            Some(tick) => tick,
79        };
80
81        Ok(tick)
82    }
83
84    pub fn next_initialized_tick(&self, tick_index: i32) -> Result<(Option<&TickFacade>, i32), CoreError> {
85        let array_end_index = self.end_index();
86        if tick_index >= array_end_index {
87            return Err(INVALID_TICK_ARRAY_SEQUENCE);
88        }
89        let mut next_index = tick_index;
90        loop {
91            next_index = get_next_initializable_tick_index(next_index, self.tick_spacing);
92            // If at the end of the sequence, we don't have tick info but can still return the next tick index
93            if next_index > array_end_index {
94                return Ok((None, array_end_index));
95            }
96            let tick = self.tick(next_index)?;
97            if tick.initialized {
98                return Ok((Some(tick), next_index));
99            }
100        }
101    }
102
103    pub fn prev_initialized_tick(&self, tick_index: i32) -> Result<(Option<&TickFacade>, i32), CoreError> {
104        let array_start_index = self.start_index();
105        if tick_index < array_start_index {
106            return Err(INVALID_TICK_ARRAY_SEQUENCE);
107        }
108        let mut prev_index = get_initializable_tick_index(tick_index, self.tick_spacing, Some(false));
109        loop {
110            // If at the start of the sequence, we don't have tick info but can still return the previous tick index
111            if prev_index < array_start_index {
112                return Ok((None, array_start_index));
113            }
114            let tick = self.tick(prev_index)?;
115            if tick.initialized {
116                return Ok((Some(tick), prev_index));
117            }
118            prev_index = get_prev_initializable_tick_index(prev_index, self.tick_spacing);
119        }
120    }
121}
122
123#[cfg(all(test, not(feature = "wasm")))]
124mod tests {
125    use super::*;
126    use crate::get_tick_array_start_tick_index;
127
128    fn test_tick(initialized: bool, liquidity_net: i128) -> TickFacade {
129        TickFacade {
130            initialized,
131            liquidity_net,
132            ..TickFacade::default()
133        }
134    }
135
136    fn test_ticks_initialized() -> [TickFacade; TICK_ARRAY_SIZE] {
137        (0..TICK_ARRAY_SIZE)
138            .map(|x| test_tick(true, x as i128))
139            .collect::<Vec<TickFacade>>()
140            .try_into()
141            .unwrap()
142    }
143
144    fn test_ticks_uninitialized() -> [TickFacade; TICK_ARRAY_SIZE] {
145        (0..TICK_ARRAY_SIZE)
146            .map(|_| test_tick(false, 0))
147            .collect::<Vec<TickFacade>>()
148            .try_into()
149            .unwrap()
150    }
151
152    fn test_ticks_alternating_initialized() -> [TickFacade; TICK_ARRAY_SIZE] {
153        (0..TICK_ARRAY_SIZE)
154            .map(|x| {
155                let initialized = x & 1 == 1;
156                test_tick(initialized, if initialized { x as i128 } else { 0 })
157            })
158            .collect::<Vec<TickFacade>>()
159            .try_into()
160            .unwrap()
161    }
162
163    fn test_sequence_with_one_tick_array(tick_spacing: u16, ticks: [TickFacade; TICK_ARRAY_SIZE], start_tick_index: i32) -> TickArraySequence {
164        let one = TickArrayFacade { start_tick_index, ticks };
165        TickArraySequence::new(vec![one], tick_spacing).unwrap()
166    }
167
168    fn test_sequence(tick_spacing: u16, ticks: [TickFacade; TICK_ARRAY_SIZE]) -> TickArraySequence {
169        let one = TickArrayFacade {
170            start_tick_index: -(TICK_ARRAY_SIZE as i32 * tick_spacing as i32),
171            ticks,
172        };
173        let two = TickArrayFacade { start_tick_index: 0, ticks };
174        let three = TickArrayFacade {
175            start_tick_index: TICK_ARRAY_SIZE as i32 * tick_spacing as i32,
176            ticks,
177        };
178        TickArraySequence::new(vec![one, two, three], tick_spacing).unwrap()
179    }
180
181    #[test]
182    fn test_tick_array_start_index() {
183        let sequence = test_sequence(16, test_ticks_alternating_initialized());
184        assert_eq!(sequence.start_index(), -1408);
185    }
186
187    #[test]
188    fn test_tick_array_end_index() {
189        let sequence = test_sequence(16, test_ticks_alternating_initialized());
190        assert_eq!(sequence.end_index(), 2815);
191    }
192
193    #[test]
194    fn test_get_tick() {
195        let sequence = test_sequence(16, test_ticks_alternating_initialized());
196        assert_eq!(sequence.tick(-1408).map(|x| x.liquidity_net), Ok(0));
197        assert_eq!(sequence.tick(-16).map(|x| x.liquidity_net), Ok(87));
198        assert_eq!(sequence.tick(0).map(|x| x.liquidity_net), Ok(0));
199        assert_eq!(sequence.tick(16).map(|x| x.liquidity_net), Ok(1));
200        assert_eq!(sequence.tick(1408).map(|x| x.liquidity_net), Ok(0));
201        assert_eq!(sequence.tick(1424).map(|x| x.liquidity_net), Ok(1));
202    }
203
204    #[test]
205    fn test_get_tick_large_tick_spacing() {
206        let sequence = test_sequence(32896, test_ticks_alternating_initialized());
207        assert_eq!(sequence.tick(-427648).map(|x| x.liquidity_net), Ok(75));
208        assert_eq!(sequence.tick(0).map(|x| x.liquidity_net), Ok(0));
209        assert_eq!(sequence.tick(427648).map(|x| x.liquidity_net), Ok(13));
210    }
211
212    #[test]
213    fn test_get_tick_errors() {
214        let sequence = test_sequence(16, test_ticks_alternating_initialized());
215
216        let out_out_bounds_lower = sequence.tick(-1409);
217        assert!(matches!(out_out_bounds_lower, Err(TICK_INDEX_OUT_OF_BOUNDS)));
218
219        let out_of_bounds_upper = sequence.tick(2817);
220        assert!(matches!(out_of_bounds_upper, Err(TICK_INDEX_OUT_OF_BOUNDS)));
221
222        let invalid_tick_index = sequence.tick(1);
223        assert!(matches!(invalid_tick_index, Err(INVALID_TICK_INDEX)));
224
225        let invalid_negative_tick_index = sequence.tick(-1);
226        assert!(matches!(invalid_negative_tick_index, Err(INVALID_TICK_INDEX)));
227    }
228
229    #[test]
230    fn test_get_next_initializable_tick_index() {
231        let sequence = test_sequence(16, test_ticks_alternating_initialized());
232        let pair = sequence.next_initialized_tick(0);
233        assert_eq!(pair.map(|x| x.1), Ok(16));
234        assert_eq!(pair.map(|x| x.0.map(|x| x.liquidity_net)), Ok(Some(1)));
235    }
236
237    #[test]
238    fn test_get_next_initializable_tick_index_off_spacing() {
239        let sequence = test_sequence(16, test_ticks_alternating_initialized());
240        let pair = sequence.next_initialized_tick(-17);
241        assert_eq!(pair.map(|x| x.1), Ok(-16));
242        assert_eq!(pair.map(|x| x.0.map(|x| x.liquidity_net)), Ok(Some(87)));
243    }
244
245    #[test]
246    fn test_get_next_initializable_tick_cross_array() {
247        let sequence = test_sequence(16, test_ticks_alternating_initialized());
248        let pair = sequence.next_initialized_tick(1392);
249        assert_eq!(pair.map(|x| x.1), Ok(1424));
250        assert_eq!(pair.map(|x| x.0.map(|x| x.liquidity_net)), Ok(Some(1)));
251    }
252
253    #[test]
254    fn test_get_next_initializable_tick_skip_uninitialized() {
255        let sequence = test_sequence(16, test_ticks_alternating_initialized());
256        let pair = sequence.next_initialized_tick(-1);
257        assert_eq!(pair.map(|x| x.1), Ok(16));
258        assert_eq!(pair.map(|x| x.0.map(|x| x.liquidity_net)), Ok(Some(1)));
259    }
260
261    #[test]
262    fn test_get_next_initializable_tick_invalid_tick_array_sequence() {
263        let sequence = test_sequence(16, test_ticks_alternating_initialized());
264        let pair_2813 = sequence.next_initialized_tick(2813);
265        let pair_2814 = sequence.next_initialized_tick(2814);
266        let pair_2815 = sequence.next_initialized_tick(2815);
267        let pair_2816 = sequence.next_initialized_tick(2816);
268        assert_eq!(pair_2813, Ok((None, 2815)));
269        assert_eq!(pair_2814, Ok((None, 2815)));
270        assert_eq!(pair_2815, Err(INVALID_TICK_ARRAY_SEQUENCE));
271        assert_eq!(pair_2816, Err(INVALID_TICK_ARRAY_SEQUENCE));
272    }
273
274    #[test]
275    fn test_get_next_initializable_tick_with_last_initializable_tick_initialized() {
276        let sequence = test_sequence(16, test_ticks_initialized());
277        let pair_2799 = sequence.next_initialized_tick(2799);
278        let pair_2800 = sequence.next_initialized_tick(2800);
279        assert_eq!(pair_2799, Ok((Some(&test_tick(true, 87)), 2800)));
280        assert_eq!(pair_2800, Ok((None, 2815)));
281    }
282
283    #[test]
284    fn test_get_next_initializable_tick_with_last_initializable_tick_uninitialized() {
285        let sequence = test_sequence(16, test_ticks_uninitialized());
286        let pair_2799 = sequence.next_initialized_tick(2799);
287        assert_eq!(pair_2799, Ok((None, 2815)));
288    }
289
290    #[test]
291    fn test_get_next_initializable_tick_in_end_tick_array_with_uninitialized_ticks_ts_16() {
292        let tick_spacing = 16;
293        let start_tick_index = get_tick_array_start_tick_index(MAX_TICK_INDEX, tick_spacing);
294        let sequence = test_sequence_with_one_tick_array(tick_spacing, test_ticks_uninitialized(), start_tick_index);
295        let pair = sequence.next_initialized_tick(start_tick_index);
296        assert_eq!(pair, Ok((None, MAX_TICK_INDEX)));
297    }
298
299    #[test]
300    fn test_get_next_initializable_tick_in_end_tick_array_with_uninitialized_ticks_ts_1() {
301        let tick_spacing = 1;
302        let start_tick_index = get_tick_array_start_tick_index(MAX_TICK_INDEX, tick_spacing);
303        let sequence = test_sequence_with_one_tick_array(tick_spacing, test_ticks_uninitialized(), start_tick_index);
304        let pair = sequence.next_initialized_tick(start_tick_index);
305        assert_eq!(pair, Ok((None, MAX_TICK_INDEX)));
306    }
307
308    #[test]
309    fn test_get_next_initializable_tick_in_end_tick_array_with_initialized_ticks_ts_1() {
310        let tick_spacing = 1;
311        let start_tick_index = get_tick_array_start_tick_index(MAX_TICK_INDEX, tick_spacing);
312        let sequence = test_sequence_with_one_tick_array(tick_spacing, test_ticks_initialized(), start_tick_index);
313        let pair = sequence.next_initialized_tick(MAX_TICK_INDEX - 1);
314        assert_eq!(pair, Ok((Some(&test_tick(true, 28)), MAX_TICK_INDEX)));
315    }
316
317    #[test]
318    fn test_get_prev_initializable_tick_index() {
319        let sequence = test_sequence(16, test_ticks_alternating_initialized());
320        let pair = sequence.prev_initialized_tick(32);
321        assert_eq!(pair.map(|x| x.1), Ok(16));
322        assert_eq!(pair.map(|x| x.0.map(|x| x.liquidity_net)), Ok(Some(1)));
323    }
324
325    #[test]
326    fn test_get_prev_initializable_tick_index_off_spacing() {
327        let sequence = test_sequence(16, test_ticks_alternating_initialized());
328        let pair = sequence.prev_initialized_tick(-1);
329        assert_eq!(pair.map(|x| x.1), Ok(-16));
330        assert_eq!(pair.map(|x| x.0.map(|x| x.liquidity_net)), Ok(Some(87)));
331    }
332
333    #[test]
334    fn test_get_prev_initializable_tick_skip_uninitialized() {
335        let sequence = test_sequence(16, test_ticks_alternating_initialized());
336        let pair = sequence.prev_initialized_tick(33);
337        assert_eq!(pair.map(|x| x.1), Ok(16));
338        assert_eq!(pair.map(|x| x.0.map(|x| x.liquidity_net)), Ok(Some(1)));
339    }
340
341    #[test]
342    fn test_get_prev_initializable_tick_cross_array() {
343        let sequence = test_sequence(16, test_ticks_alternating_initialized());
344        let pair = sequence.prev_initialized_tick(1408);
345        assert_eq!(pair.map(|x| x.1), Ok(1392));
346        assert_eq!(pair.map(|x| x.0.map(|x| x.liquidity_net)), Ok(Some(87)));
347    }
348
349    #[test]
350    fn test_get_prev_initialized_tick_invalid_tick_array_sequence() {
351        let sequence = test_sequence(16, test_ticks_alternating_initialized());
352        let pair_1407 = sequence.prev_initialized_tick(-1407);
353        let pair_1408 = sequence.prev_initialized_tick(-1408);
354        let pair_1409 = sequence.prev_initialized_tick(-1409);
355        let pair_1410 = sequence.prev_initialized_tick(-1410);
356        assert!(matches!(pair_1407, Ok((None, -1408))));
357        assert!(matches!(pair_1408, Ok((None, -1408))));
358        assert!(matches!(pair_1409, Err(INVALID_TICK_ARRAY_SEQUENCE)));
359        assert!(matches!(pair_1410, Err(INVALID_TICK_ARRAY_SEQUENCE)));
360    }
361
362    #[test]
363    fn test_get_prev_initializable_tick_with_first_initializable_tick_initialized() {
364        let sequence = test_sequence(16, test_ticks_initialized());
365        let pair = sequence.prev_initialized_tick(-1408);
366        assert_eq!(pair, Ok((Some(&test_tick(true, 0)), -1408)));
367    }
368
369    #[test]
370    fn test_get_prev_initializable_tick_with_first_initializable_tick_uninitialized() {
371        let sequence = test_sequence(16, test_ticks_uninitialized());
372        let pair = sequence.prev_initialized_tick(-1408);
373        assert_eq!(pair, Ok((None, -1408)));
374    }
375
376    #[test]
377    fn test_get_prev_initializable_tick_in_first_tick_array_with_uninitialized_ticks_ts_16() {
378        let tick_spacing = 16;
379        let start_tick_index = get_tick_array_start_tick_index(MIN_TICK_INDEX, tick_spacing);
380        let sequence = test_sequence_with_one_tick_array(tick_spacing, test_ticks_uninitialized(), start_tick_index);
381        let pair = sequence.prev_initialized_tick(MIN_TICK_INDEX + tick_spacing as i32);
382        assert_eq!(pair, Ok((None, MIN_TICK_INDEX)));
383    }
384
385    #[test]
386    fn test_get_prev_initializable_tick_in_first_tick_array_with_uninitialized_ticks_ts_1() {
387        let tick_spacing = 1;
388        let start_tick_index = get_tick_array_start_tick_index(MIN_TICK_INDEX, tick_spacing);
389        let sequence = test_sequence_with_one_tick_array(tick_spacing, test_ticks_uninitialized(), start_tick_index);
390        let pair = sequence.prev_initialized_tick(MIN_TICK_INDEX + tick_spacing as i32);
391        assert_eq!(pair, Ok((None, MIN_TICK_INDEX)));
392    }
393
394    #[test]
395    fn test_get_prev_initializable_tick_in_first_tick_array_with_initialized_ticks_ts_1() {
396        let tick_spacing = 1;
397        let start_tick_index = get_tick_array_start_tick_index(MIN_TICK_INDEX, tick_spacing);
398        let sequence = test_sequence_with_one_tick_array(tick_spacing, test_ticks_initialized(), start_tick_index);
399        let pair = sequence.prev_initialized_tick(MIN_TICK_INDEX);
400        assert_eq!(pair, Ok((Some(&test_tick(true, 60)), MIN_TICK_INDEX)));
401    }
402}
fusionamm_core/math/tick_array_sequence.rs

fusionamm_core/math/
tick_array_sequence.rs
