1use ahash::AHashMap;
17use alloy_primitives::U256;
18
19use crate::defi::tick_map::{
20 liquidity_math::tick_spacing_to_max_liquidity_per_tick, tick::PoolTick, tick_bitmap::TickBitmap,
21};
22
23pub mod bit_math;
24pub mod full_math;
25pub mod liquidity_math;
26pub mod sqrt_price_math;
27pub mod tick;
28pub mod tick_bitmap;
29pub mod tick_math;
30
31#[derive(Debug, Clone)]
37pub struct TickMap {
38 ticks: AHashMap<i32, PoolTick>,
40 tick_bitmap: TickBitmap,
42 pub liquidity: u128,
44 pub max_liquidity_per_tick: u128,
46}
47
48impl Default for TickMap {
49 fn default() -> Self {
50 Self::new(0)
51 }
52}
53
54impl TickMap {
55 pub fn new(tick_spacing: u32) -> Self {
57 Self {
58 ticks: AHashMap::new(),
59 tick_bitmap: TickBitmap::new(tick_spacing),
60 liquidity: 0,
61 max_liquidity_per_tick: tick_spacing_to_max_liquidity_per_tick(tick_spacing as i32),
62 }
63 }
64
65 pub fn get_tick(&self, tick: i32) -> Option<&PoolTick> {
67 self.ticks.get(&tick)
68 }
69
70 pub fn get_tick_or_init(&mut self, tick: i32) -> &mut PoolTick {
72 self.ticks
73 .entry(tick)
74 .or_insert_with(|| PoolTick::from_tick(tick))
75 }
76
77 pub fn get_fee_growth_inside(
79 &mut self,
80 lower_tick: i32,
81 upper_tick: i32,
82 current_tick: i32,
83 fee_growth_global_0: U256,
84 fee_growth_global_1: U256,
85 ) -> (U256, U256) {
86 self.ticks
88 .entry(lower_tick)
89 .or_insert_with(|| PoolTick::from_tick(lower_tick));
90 self.ticks
91 .entry(upper_tick)
92 .or_insert_with(|| PoolTick::from_tick(upper_tick));
93
94 let lower_tick = &self.ticks[&lower_tick];
96 let upper_tick = &self.ticks[&upper_tick];
97
98 let fee_growth_below_0 = if current_tick >= lower_tick.value {
100 lower_tick.fee_growth_outside_0
101 } else {
102 fee_growth_global_0 - lower_tick.fee_growth_outside_0
103 };
104 let fee_growth_below_1 = if current_tick >= lower_tick.value {
105 lower_tick.fee_growth_outside_1
106 } else {
107 fee_growth_global_1 - lower_tick.fee_growth_outside_1
108 };
109
110 let fee_growth_above_0 = if current_tick < upper_tick.value {
112 upper_tick.fee_growth_outside_0
113 } else {
114 fee_growth_global_0 - upper_tick.fee_growth_outside_0
115 };
116 let fee_growth_above_1 = if current_tick < upper_tick.value {
117 upper_tick.fee_growth_outside_1
118 } else {
119 fee_growth_global_1 - upper_tick.fee_growth_outside_1
120 };
121
122 let fee_growth_inside_0 = fee_growth_global_0 - fee_growth_below_0 - fee_growth_above_0;
124 let fee_growth_inside_1 = fee_growth_global_1 - fee_growth_below_1 - fee_growth_above_1;
125
126 (fee_growth_inside_0, fee_growth_inside_1)
127 }
128
129 fn update_tick_data(
131 &mut self,
132 tick: i32,
133 tick_current: i32,
134 liquidity_delta: i128,
135 upper: bool,
136 fee_growth_global_0: U256,
137 fee_growth_global_1: U256,
138 ) -> bool {
139 let max_liquidity_per_tick = self.max_liquidity_per_tick;
140 let tick = self.get_tick_or_init(tick);
141
142 let liquidity_gross_before = tick.update_liquidity(liquidity_delta, upper);
143 let liquidity_gross_after = tick.liquidity_gross;
144 assert!(
145 liquidity_gross_after <= max_liquidity_per_tick,
146 "Liquidity exceeds maximum per tick"
147 );
148
149 if liquidity_gross_before == 0 {
150 if tick.value <= tick_current {
152 tick.fee_growth_outside_0 = fee_growth_global_0;
153 tick.fee_growth_outside_1 = fee_growth_global_1;
154 }
155 tick.initialized = true;
156 }
157
158 (liquidity_gross_after == 0) != (liquidity_gross_before == 0)
160 }
161
162 pub fn update(
164 &mut self,
165 tick: i32,
166 tick_current: i32,
167 liquidity_delta: i128,
168 upper: bool,
169 fee_growth_global_0: U256,
170 fee_growth_global_1: U256,
171 ) -> bool {
172 let flipped = self.update_tick_data(
173 tick,
174 tick_current,
175 liquidity_delta,
176 upper,
177 fee_growth_global_0,
178 fee_growth_global_1,
179 );
180
181 if flipped {
183 self.tick_bitmap.flip_tick(tick);
184 }
185
186 flipped
187 }
188
189 pub fn cross_tick(
191 &mut self,
192 tick: i32,
193 fee_growth_global_0: U256,
194 fee_growth_global_1: U256,
195 ) -> i128 {
196 let tick = self.get_tick_or_init(tick);
197 tick.update_fee_growth(fee_growth_global_0, fee_growth_global_1);
198
199 tick.liquidity_net
200 }
201
202 #[must_use]
204 pub fn active_tick_count(&self) -> usize {
205 self.ticks
206 .iter()
207 .filter(|(_, tick)| self.is_tick_initialized(tick.value))
208 .count()
209 }
210
211 #[must_use]
213 pub fn total_tick_count(&self) -> usize {
214 self.ticks.len()
215 }
216
217 #[must_use]
219 pub fn get_all_ticks(&self) -> &AHashMap<i32, PoolTick> {
220 &self.ticks
221 }
222
223 pub fn set_tick(&mut self, tick_data: PoolTick) {
225 let tick = tick_data.value;
226 self.ticks.insert(tick, tick_data);
227 }
228
229 pub fn restore_tick(&mut self, tick_data: PoolTick) {
234 let is_initialized = tick_data.initialized;
235 let tick_value = tick_data.value;
236
237 self.set_tick(tick_data);
238
239 if is_initialized {
241 self.tick_bitmap.flip_tick(tick_value);
242 }
243 }
244
245 pub fn clear(&mut self, tick: i32) {
247 self.ticks.remove(&tick);
248 }
249
250 pub fn next_initialized_tick(&self, tick: i32, lte: bool) -> (i32, bool) {
252 self.tick_bitmap
253 .next_initialized_tick_within_one_word(tick, lte)
254 }
255
256 pub fn is_tick_initialized(&self, tick: i32) -> bool {
258 self.tick_bitmap.is_initialized(tick)
259 }
260}
261
262#[cfg(test)]
263mod tests {
264 use std::str::FromStr;
265
266 use rstest::{fixture, rstest};
267
268 use super::*;
269
270 #[fixture]
271 fn tick_map() -> TickMap {
272 TickMap::new(1)
273 }
274
275 #[rstest]
276 fn test_new_tick_maps(tick_map: TickMap) {
277 assert_eq!(tick_map.active_tick_count(), 0);
278 assert_eq!(tick_map.liquidity, 0);
279 }
280
281 #[rstest]
282 fn test_get_fee_growth_inside_uninitialized_ticks(mut tick_map: TickMap) {
283 let fee_growth_global_0 = U256::from(15);
284 let fee_growth_global_1 = U256::from(15);
285
286 let (fee_growth_inside_0, fee_growth_inside_1) =
288 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
289 assert_eq!(fee_growth_inside_0, U256::from_str("15").unwrap());
290 assert_eq!(fee_growth_inside_1, U256::from_str("15").unwrap());
291
292 let (fee_growth_inside_0, fee_growth_inside_1) =
294 tick_map.get_fee_growth_inside(-2, 2, 4, fee_growth_global_0, fee_growth_global_1);
295 assert_eq!(fee_growth_inside_0, U256::ZERO);
296 assert_eq!(fee_growth_inside_1, U256::ZERO);
297
298 let (fee_growth_inside_0, fee_growth_inside_1) =
300 tick_map.get_fee_growth_inside(-2, 2, -4, fee_growth_global_0, fee_growth_global_1);
301 assert_eq!(fee_growth_inside_0, U256::ZERO);
302 assert_eq!(fee_growth_inside_1, U256::ZERO);
303 }
304
305 #[rstest]
306 fn test_get_fee_growth_inside_if_upper_tick_is_below(mut tick_map: TickMap) {
307 tick_map.set_tick(PoolTick::new(
308 2, 0,
310 0,
311 U256::from(2),
312 U256::from(3),
313 true,
314 0,
315 ));
316 let fee_growth_global_0 = U256::from(15);
317 let fee_growth_global_1 = U256::from(15);
318 let (fee_growth_inside_0, fee_growth_inside_1) =
319 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
320 assert_eq!(fee_growth_inside_0, U256::from(13));
321 assert_eq!(fee_growth_inside_1, U256::from(12));
322 }
323
324 #[rstest]
325 fn test_get_fee_growth_inside_if_lower_tick_is_above(mut tick_map: TickMap) {
326 tick_map.set_tick(PoolTick::new(
327 -2, 0,
329 0,
330 U256::from(2),
331 U256::from(3),
332 true,
333 0,
334 ));
335 let fee_growth_global_0 = U256::from(15);
336 let fee_growth_global_1 = U256::from(15);
337 let (fee_growth_inside_0, fee_growth_inside_1) =
338 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
339 assert_eq!(fee_growth_inside_0, U256::from(13));
340 assert_eq!(fee_growth_inside_1, U256::from(12));
341 }
342
343 #[rstest]
344 fn test_get_fee_growth_inside_if_upper_and_lower_tick_are_initialized(mut tick_map: TickMap) {
345 tick_map.set_tick(PoolTick::new(
346 -2, 0,
348 0,
349 U256::from(2),
350 U256::from(3),
351 true,
352 0,
353 ));
354 tick_map.set_tick(PoolTick::new(
355 2, 0,
357 0,
358 U256::from(4),
359 U256::from(1),
360 true,
361 0,
362 ));
363 let fee_growth_global_0 = U256::from(15);
364 let fee_growth_global_1 = U256::from(15);
365 let (fee_growth_inside_0, fee_growth_inside_1) =
366 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
367 assert_eq!(fee_growth_inside_0, U256::from(9));
368 assert_eq!(fee_growth_inside_1, U256::from(11));
369 }
370
371 #[rstest]
372 fn test_get_fee_growth_inside_with_overflow(mut tick_map: TickMap) {
373 tick_map.set_tick(PoolTick::new(
374 -2,
375 0,
376 0,
377 U256::MAX - U256::from(3u32), U256::MAX - U256::from(2u32), true,
380 0,
381 ));
382 tick_map.set_tick(PoolTick::new(
383 2,
384 0,
385 0,
386 U256::from(3u32),
387 U256::from(5u32),
388 true,
389 0,
390 ));
391 let fee_growth_global_0 = U256::from(15);
392 let fee_growth_global_1 = U256::from(15);
393 let (fee_growth_inside_0, fee_growth_inside_1) =
394 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
395 assert_eq!(fee_growth_inside_0, U256::from(16u32));
396 assert_eq!(fee_growth_inside_1, U256::from(13u32));
397 }
398
399 #[rstest]
400 fn test_update_flips_from_zero_to_nonzero(mut tick_map: TickMap) {
401 assert!(!tick_map.is_tick_initialized(0));
403
404 let flipped = tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
405 assert!(flipped);
406
407 assert!(tick_map.is_tick_initialized(0));
409 }
410
411 #[rstest]
412 fn test_update_does_not_flip_from_nonzero_to_greater_nonzero(mut tick_map: TickMap) {
413 tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
415 assert!(tick_map.is_tick_initialized(0));
416
417 let flipped = tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
419 assert!(!flipped);
420
421 assert!(tick_map.is_tick_initialized(0));
423 }
424
425 #[rstest]
426 fn test_update_flips_from_nonzero_to_zero(mut tick_map: TickMap) {
427 let flipped_first = tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
429 assert!(flipped_first);
430 assert!(tick_map.is_tick_initialized(0));
431
432 let flipped_second = tick_map.update(0, 0, -1, false, U256::ZERO, U256::ZERO);
434 assert!(flipped_second);
435
436 assert!(!tick_map.is_tick_initialized(0));
438 }
439
440 #[rstest]
441 fn test_update_does_not_flip_from_nonzero_to_lesser_nonzero(mut tick_map: TickMap) {
442 tick_map.update(0, 0, 2, false, U256::ZERO, U256::ZERO);
444 assert!(tick_map.is_tick_initialized(0));
445
446 let flipped = tick_map.update(0, 0, -1, false, U256::ZERO, U256::ZERO);
448 assert!(!flipped);
449
450 assert!(tick_map.is_tick_initialized(0));
452 }
453
454 #[rstest]
455 #[should_panic(expected = "Liquidity exceeds maximum per tick")]
456 fn test_update_reverts_if_total_liquidity_gross_exceeds_max() {
457 let mut tick_map = TickMap::new(200); let max_liquidity = tick_map.max_liquidity_per_tick;
461 tick_map.update(
462 0,
463 0,
464 (max_liquidity / 2) as i128,
465 false,
466 U256::ZERO,
467 U256::ZERO,
468 );
469 tick_map.update(
470 0,
471 0,
472 (max_liquidity / 2) as i128,
473 true,
474 U256::ZERO,
475 U256::ZERO,
476 );
477
478 tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
480 }
481
482 #[rstest]
483 fn test_update_nets_liquidity_based_on_upper_flag(mut tick_map: TickMap) {
484 tick_map.update(0, 0, 2, false, U256::ZERO, U256::ZERO);
486 tick_map.update(0, 0, 1, true, U256::ZERO, U256::ZERO);
488 tick_map.update(0, 0, 3, true, U256::ZERO, U256::ZERO);
490 tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
492
493 let tick = tick_map.get_tick(0).unwrap();
494
495 assert_eq!(tick.liquidity_gross, 7);
497
498 assert_eq!(tick.liquidity_net, -1);
500 }
501
502 #[rstest]
503 fn test_update_assumes_all_growth_happens_below_ticks_lte_current_tick() {
504 let mut tick_map = TickMap::new(1);
505 let fee_growth_global_0 = U256::from(15);
506 let fee_growth_global_1 = U256::from(2);
507 tick_map.update(1, 1, 1, false, fee_growth_global_0, fee_growth_global_1);
509
510 let tick = tick_map.get_tick(1).unwrap();
511
512 assert_eq!(tick.fee_growth_outside_0, U256::from(15u32));
514 assert_eq!(tick.fee_growth_outside_1, U256::from(2u32));
515 assert!(tick.initialized);
516 assert_eq!(tick.liquidity_gross, 1);
517 assert_eq!(tick.liquidity_net, 1);
518 }
519
520 #[rstest]
521 fn test_update_does_not_set_growth_fields_if_tick_already_initialized() {
522 let mut tick_map = TickMap::new(1);
523 let fee_growth_0_initial = U256::from(1);
524 let fee_growth_1_initial = U256::from(2);
525 tick_map.update(1, 1, 1, false, fee_growth_0_initial, fee_growth_1_initial);
527
528 let fee_growth_0_second = U256::from(6);
530 let fee_growth_1_second = U256::from(7);
531 tick_map.update(1, 1, 1, false, fee_growth_0_second, fee_growth_1_second);
532
533 let tick = tick_map.get_tick(1).unwrap();
534
535 assert_eq!(tick.fee_growth_outside_0, U256::from(1u32)); assert_eq!(tick.fee_growth_outside_1, U256::from(2u32)); assert!(tick.initialized);
539 assert_eq!(tick.liquidity_gross, 2); assert_eq!(tick.liquidity_net, 2); }
542
543 #[rstest]
544 fn test_update_does_not_set_growth_fields_for_ticks_gt_current_tick() {
545 let mut tick_map = TickMap::new(1);
546 let fee_growth_global_0 = U256::from(1);
547 let fee_growth_global_1 = U256::from(2u32);
548 tick_map.update(2, 1, 1, false, fee_growth_global_0, fee_growth_global_1);
550
551 let tick = tick_map.get_tick(2).unwrap();
552
553 assert_eq!(tick.fee_growth_outside_0, U256::ZERO); assert_eq!(tick.fee_growth_outside_1, U256::ZERO); assert!(tick.initialized);
557 assert_eq!(tick.liquidity_gross, 1);
558 assert_eq!(tick.liquidity_net, 1);
559 }
560
561 #[rstest]
562 fn test_clear_deletes_all_data_in_tick(mut tick_map: TickMap) {
563 tick_map.set_tick(PoolTick::new(
565 2,
566 3,
567 4,
568 U256::from(1u32),
569 U256::from(2u32),
570 true,
571 0,
572 ));
573
574 let tick_before = tick_map.get_tick(2).unwrap();
576 assert_eq!(tick_before.fee_growth_outside_0, U256::from(1u32));
577 assert_eq!(tick_before.fee_growth_outside_1, U256::from(2u32));
578 assert_eq!(tick_before.liquidity_gross, 3);
579 assert_eq!(tick_before.liquidity_net, 4);
580 assert!(tick_before.initialized);
581
582 tick_map.clear(2);
584
585 assert_eq!(tick_map.get_tick(2), None);
587 }
588
589 #[rstest]
590 fn test_cross_tick_flips_growth_variables(mut tick_map: TickMap) {
591 tick_map.set_tick(PoolTick::new(
593 2,
594 3,
595 4,
596 U256::from(1u32),
597 U256::from(2u32),
598 true,
599 7,
600 ));
601
602 let liquidity_net = tick_map.cross_tick(
607 2,
608 U256::from(7u32), U256::from(9u32), );
611
612 let tick = tick_map.get_tick(2).unwrap();
613
614 assert_eq!(tick.fee_growth_outside_0, U256::from(6u32)); assert_eq!(tick.fee_growth_outside_1, U256::from(7u32)); assert_eq!(liquidity_net, 4);
620
621 assert_eq!(tick.liquidity_gross, 3);
623 assert_eq!(tick.liquidity_net, 4);
624 assert!(tick.initialized);
625 }
626}