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(1)
51 }
52}
53
54impl TickMap {
55 #[must_use]
61 pub fn new(tick_spacing: u32) -> Self {
62 assert!(tick_spacing > 0, "Tick spacing must be greater than zero");
63 Self {
64 ticks: AHashMap::new(),
65 tick_bitmap: TickBitmap::new(tick_spacing),
66 liquidity: 0,
67 max_liquidity_per_tick: tick_spacing_to_max_liquidity_per_tick(tick_spacing as i32),
68 }
69 }
70
71 #[must_use]
73 pub fn get_tick(&self, tick: i32) -> Option<&PoolTick> {
74 self.ticks.get(&tick)
75 }
76
77 pub fn get_tick_or_init(&mut self, tick: i32) -> &mut PoolTick {
79 self.ticks
80 .entry(tick)
81 .or_insert_with(|| PoolTick::from_tick(tick))
82 }
83
84 pub fn get_fee_growth_inside(
86 &mut self,
87 lower_tick: i32,
88 upper_tick: i32,
89 current_tick: i32,
90 fee_growth_global_0: U256,
91 fee_growth_global_1: U256,
92 ) -> (U256, U256) {
93 self.ticks
95 .entry(lower_tick)
96 .or_insert_with(|| PoolTick::from_tick(lower_tick));
97 self.ticks
98 .entry(upper_tick)
99 .or_insert_with(|| PoolTick::from_tick(upper_tick));
100
101 let lower_tick = &self.ticks[&lower_tick];
103 let upper_tick = &self.ticks[&upper_tick];
104
105 let fee_growth_below_0 = if current_tick >= lower_tick.value {
107 lower_tick.fee_growth_outside_0
108 } else {
109 fee_growth_global_0 - lower_tick.fee_growth_outside_0
110 };
111 let fee_growth_below_1 = if current_tick >= lower_tick.value {
112 lower_tick.fee_growth_outside_1
113 } else {
114 fee_growth_global_1 - lower_tick.fee_growth_outside_1
115 };
116
117 let fee_growth_above_0 = if current_tick < upper_tick.value {
119 upper_tick.fee_growth_outside_0
120 } else {
121 fee_growth_global_0 - upper_tick.fee_growth_outside_0
122 };
123 let fee_growth_above_1 = if current_tick < upper_tick.value {
124 upper_tick.fee_growth_outside_1
125 } else {
126 fee_growth_global_1 - upper_tick.fee_growth_outside_1
127 };
128
129 let fee_growth_inside_0 = fee_growth_global_0 - fee_growth_below_0 - fee_growth_above_0;
131 let fee_growth_inside_1 = fee_growth_global_1 - fee_growth_below_1 - fee_growth_above_1;
132
133 (fee_growth_inside_0, fee_growth_inside_1)
134 }
135
136 fn update_tick_data(
138 &mut self,
139 tick: i32,
140 tick_current: i32,
141 liquidity_delta: i128,
142 upper: bool,
143 fee_growth_global_0: U256,
144 fee_growth_global_1: U256,
145 ) -> bool {
146 let max_liquidity_per_tick = self.max_liquidity_per_tick;
147 let tick = self.get_tick_or_init(tick);
148
149 let liquidity_gross_before = tick.update_liquidity(liquidity_delta, upper);
150 let liquidity_gross_after = tick.liquidity_gross;
151 assert!(
152 liquidity_gross_after <= max_liquidity_per_tick,
153 "Liquidity exceeds maximum per tick"
154 );
155
156 if liquidity_gross_before == 0 {
157 if tick.value <= tick_current {
159 tick.fee_growth_outside_0 = fee_growth_global_0;
160 tick.fee_growth_outside_1 = fee_growth_global_1;
161 }
162 tick.initialized = true;
163 }
164
165 (liquidity_gross_after == 0) != (liquidity_gross_before == 0)
167 }
168
169 pub fn update(
171 &mut self,
172 tick: i32,
173 tick_current: i32,
174 liquidity_delta: i128,
175 upper: bool,
176 fee_growth_global_0: U256,
177 fee_growth_global_1: U256,
178 ) -> bool {
179 let flipped = self.update_tick_data(
180 tick,
181 tick_current,
182 liquidity_delta,
183 upper,
184 fee_growth_global_0,
185 fee_growth_global_1,
186 );
187
188 if flipped {
190 self.tick_bitmap.flip_tick(tick);
191 }
192
193 flipped
194 }
195
196 pub fn cross_tick(
198 &mut self,
199 tick: i32,
200 fee_growth_global_0: U256,
201 fee_growth_global_1: U256,
202 ) -> i128 {
203 let tick = self.get_tick_or_init(tick);
204 tick.update_fee_growth(fee_growth_global_0, fee_growth_global_1);
205
206 tick.liquidity_net
207 }
208
209 #[must_use]
211 pub fn active_tick_count(&self) -> usize {
212 self.ticks
213 .iter()
214 .filter(|(_, tick)| self.is_tick_initialized(tick.value))
215 .count()
216 }
217
218 #[must_use]
220 pub fn total_tick_count(&self) -> usize {
221 self.ticks.len()
222 }
223
224 #[must_use]
226 pub fn get_all_ticks(&self) -> &AHashMap<i32, PoolTick> {
227 &self.ticks
228 }
229
230 pub fn set_tick(&mut self, tick_data: PoolTick) {
232 let tick = tick_data.value;
233 self.ticks.insert(tick, tick_data);
234 }
235
236 pub fn restore_tick(&mut self, tick_data: PoolTick) {
241 let is_initialized = tick_data.initialized;
242 let tick_value = tick_data.value;
243
244 self.set_tick(tick_data);
245
246 if is_initialized {
248 self.tick_bitmap.flip_tick(tick_value);
249 }
250 }
251
252 pub fn clear(&mut self, tick: i32) {
254 self.ticks.remove(&tick);
255 }
256
257 #[must_use]
259 pub fn next_initialized_tick(&self, tick: i32, lte: bool) -> (i32, bool) {
260 self.tick_bitmap
261 .next_initialized_tick_within_one_word(tick, lte)
262 }
263
264 #[must_use]
266 pub fn is_tick_initialized(&self, tick: i32) -> bool {
267 self.tick_bitmap.is_initialized(tick)
268 }
269}
270
271#[cfg(test)]
272mod tests {
273 use std::str::FromStr;
274
275 use rstest::{fixture, rstest};
276
277 use super::*;
278
279 #[fixture]
280 fn tick_map() -> TickMap {
281 TickMap::new(1)
282 }
283
284 #[rstest]
285 fn test_new_tick_maps(tick_map: TickMap) {
286 assert_eq!(tick_map.active_tick_count(), 0);
287 assert_eq!(tick_map.liquidity, 0);
288 }
289
290 #[rstest]
291 fn test_get_fee_growth_inside_uninitialized_ticks(mut tick_map: TickMap) {
292 let fee_growth_global_0 = U256::from(15);
293 let fee_growth_global_1 = U256::from(15);
294
295 let (fee_growth_inside_0, fee_growth_inside_1) =
297 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
298 assert_eq!(fee_growth_inside_0, U256::from_str("15").unwrap());
299 assert_eq!(fee_growth_inside_1, U256::from_str("15").unwrap());
300
301 let (fee_growth_inside_0, fee_growth_inside_1) =
303 tick_map.get_fee_growth_inside(-2, 2, 4, fee_growth_global_0, fee_growth_global_1);
304 assert_eq!(fee_growth_inside_0, U256::ZERO);
305 assert_eq!(fee_growth_inside_1, U256::ZERO);
306
307 let (fee_growth_inside_0, fee_growth_inside_1) =
309 tick_map.get_fee_growth_inside(-2, 2, -4, fee_growth_global_0, fee_growth_global_1);
310 assert_eq!(fee_growth_inside_0, U256::ZERO);
311 assert_eq!(fee_growth_inside_1, U256::ZERO);
312 }
313
314 #[rstest]
315 fn test_get_fee_growth_inside_if_upper_tick_is_below(mut tick_map: TickMap) {
316 tick_map.set_tick(PoolTick::new(
317 2, 0,
319 0,
320 U256::from(2),
321 U256::from(3),
322 true,
323 0,
324 ));
325 let fee_growth_global_0 = U256::from(15);
326 let fee_growth_global_1 = U256::from(15);
327 let (fee_growth_inside_0, fee_growth_inside_1) =
328 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
329 assert_eq!(fee_growth_inside_0, U256::from(13));
330 assert_eq!(fee_growth_inside_1, U256::from(12));
331 }
332
333 #[rstest]
334 fn test_get_fee_growth_inside_if_lower_tick_is_above(mut tick_map: TickMap) {
335 tick_map.set_tick(PoolTick::new(
336 -2, 0,
338 0,
339 U256::from(2),
340 U256::from(3),
341 true,
342 0,
343 ));
344 let fee_growth_global_0 = U256::from(15);
345 let fee_growth_global_1 = U256::from(15);
346 let (fee_growth_inside_0, fee_growth_inside_1) =
347 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
348 assert_eq!(fee_growth_inside_0, U256::from(13));
349 assert_eq!(fee_growth_inside_1, U256::from(12));
350 }
351
352 #[rstest]
353 fn test_get_fee_growth_inside_if_upper_and_lower_tick_are_initialized(mut tick_map: TickMap) {
354 tick_map.set_tick(PoolTick::new(
355 -2, 0,
357 0,
358 U256::from(2),
359 U256::from(3),
360 true,
361 0,
362 ));
363 tick_map.set_tick(PoolTick::new(
364 2, 0,
366 0,
367 U256::from(4),
368 U256::from(1),
369 true,
370 0,
371 ));
372 let fee_growth_global_0 = U256::from(15);
373 let fee_growth_global_1 = U256::from(15);
374 let (fee_growth_inside_0, fee_growth_inside_1) =
375 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
376 assert_eq!(fee_growth_inside_0, U256::from(9));
377 assert_eq!(fee_growth_inside_1, U256::from(11));
378 }
379
380 #[rstest]
381 fn test_get_fee_growth_inside_with_overflow(mut tick_map: TickMap) {
382 tick_map.set_tick(PoolTick::new(
383 -2,
384 0,
385 0,
386 U256::MAX - U256::from(3u32), U256::MAX - U256::from(2u32), true,
389 0,
390 ));
391 tick_map.set_tick(PoolTick::new(
392 2,
393 0,
394 0,
395 U256::from(3u32),
396 U256::from(5u32),
397 true,
398 0,
399 ));
400 let fee_growth_global_0 = U256::from(15);
401 let fee_growth_global_1 = U256::from(15);
402 let (fee_growth_inside_0, fee_growth_inside_1) =
403 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
404 assert_eq!(fee_growth_inside_0, U256::from(16u32));
405 assert_eq!(fee_growth_inside_1, U256::from(13u32));
406 }
407
408 #[rstest]
409 fn test_update_flips_from_zero_to_nonzero(mut tick_map: TickMap) {
410 assert!(!tick_map.is_tick_initialized(0));
412
413 let flipped = tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
414 assert!(flipped);
415
416 assert!(tick_map.is_tick_initialized(0));
418 }
419
420 #[rstest]
421 fn test_update_does_not_flip_from_nonzero_to_greater_nonzero(mut tick_map: TickMap) {
422 tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
424 assert!(tick_map.is_tick_initialized(0));
425
426 let flipped = tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
428 assert!(!flipped);
429
430 assert!(tick_map.is_tick_initialized(0));
432 }
433
434 #[rstest]
435 fn test_update_flips_from_nonzero_to_zero(mut tick_map: TickMap) {
436 let flipped_first = tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
438 assert!(flipped_first);
439 assert!(tick_map.is_tick_initialized(0));
440
441 let flipped_second = tick_map.update(0, 0, -1, false, U256::ZERO, U256::ZERO);
443 assert!(flipped_second);
444
445 assert!(!tick_map.is_tick_initialized(0));
447 }
448
449 #[rstest]
450 fn test_update_does_not_flip_from_nonzero_to_lesser_nonzero(mut tick_map: TickMap) {
451 tick_map.update(0, 0, 2, false, U256::ZERO, U256::ZERO);
453 assert!(tick_map.is_tick_initialized(0));
454
455 let flipped = tick_map.update(0, 0, -1, false, U256::ZERO, U256::ZERO);
457 assert!(!flipped);
458
459 assert!(tick_map.is_tick_initialized(0));
461 }
462
463 #[rstest]
464 #[should_panic(expected = "Liquidity exceeds maximum per tick")]
465 fn test_update_reverts_if_total_liquidity_gross_exceeds_max() {
466 let mut tick_map = TickMap::new(200); let max_liquidity = tick_map.max_liquidity_per_tick;
470 tick_map.update(
471 0,
472 0,
473 (max_liquidity / 2) as i128,
474 false,
475 U256::ZERO,
476 U256::ZERO,
477 );
478 tick_map.update(
479 0,
480 0,
481 (max_liquidity / 2) as i128,
482 true,
483 U256::ZERO,
484 U256::ZERO,
485 );
486
487 tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
489 }
490
491 #[rstest]
492 fn test_update_nets_liquidity_based_on_upper_flag(mut tick_map: TickMap) {
493 tick_map.update(0, 0, 2, false, U256::ZERO, U256::ZERO);
495 tick_map.update(0, 0, 1, true, U256::ZERO, U256::ZERO);
497 tick_map.update(0, 0, 3, true, U256::ZERO, U256::ZERO);
499 tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
501
502 let tick = tick_map.get_tick(0).unwrap();
503
504 assert_eq!(tick.liquidity_gross, 7);
506
507 assert_eq!(tick.liquidity_net, -1);
509 }
510
511 #[rstest]
512 fn test_update_assumes_all_growth_happens_below_ticks_lte_current_tick() {
513 let mut tick_map = TickMap::new(1);
514 let fee_growth_global_0 = U256::from(15);
515 let fee_growth_global_1 = U256::from(2);
516 tick_map.update(1, 1, 1, false, fee_growth_global_0, fee_growth_global_1);
518
519 let tick = tick_map.get_tick(1).unwrap();
520
521 assert_eq!(tick.fee_growth_outside_0, U256::from(15u32));
523 assert_eq!(tick.fee_growth_outside_1, U256::from(2u32));
524 assert!(tick.initialized);
525 assert_eq!(tick.liquidity_gross, 1);
526 assert_eq!(tick.liquidity_net, 1);
527 }
528
529 #[rstest]
530 fn test_update_does_not_set_growth_fields_if_tick_already_initialized() {
531 let mut tick_map = TickMap::new(1);
532 let fee_growth_0_initial = U256::from(1);
533 let fee_growth_1_initial = U256::from(2);
534 tick_map.update(1, 1, 1, false, fee_growth_0_initial, fee_growth_1_initial);
536
537 let fee_growth_0_second = U256::from(6);
539 let fee_growth_1_second = U256::from(7);
540 tick_map.update(1, 1, 1, false, fee_growth_0_second, fee_growth_1_second);
541
542 let tick = tick_map.get_tick(1).unwrap();
543
544 assert_eq!(tick.fee_growth_outside_0, U256::from(1u32)); assert_eq!(tick.fee_growth_outside_1, U256::from(2u32)); assert!(tick.initialized);
548 assert_eq!(tick.liquidity_gross, 2); assert_eq!(tick.liquidity_net, 2); }
551
552 #[rstest]
553 fn test_update_does_not_set_growth_fields_for_ticks_gt_current_tick() {
554 let mut tick_map = TickMap::new(1);
555 let fee_growth_global_0 = U256::from(1);
556 let fee_growth_global_1 = U256::from(2u32);
557 tick_map.update(2, 1, 1, false, fee_growth_global_0, fee_growth_global_1);
559
560 let tick = tick_map.get_tick(2).unwrap();
561
562 assert_eq!(tick.fee_growth_outside_0, U256::ZERO); assert_eq!(tick.fee_growth_outside_1, U256::ZERO); assert!(tick.initialized);
566 assert_eq!(tick.liquidity_gross, 1);
567 assert_eq!(tick.liquidity_net, 1);
568 }
569
570 #[rstest]
571 fn test_clear_deletes_all_data_in_tick(mut tick_map: TickMap) {
572 tick_map.set_tick(PoolTick::new(
574 2,
575 3,
576 4,
577 U256::from(1u32),
578 U256::from(2u32),
579 true,
580 0,
581 ));
582
583 let tick_before = tick_map.get_tick(2).unwrap();
585 assert_eq!(tick_before.fee_growth_outside_0, U256::from(1u32));
586 assert_eq!(tick_before.fee_growth_outside_1, U256::from(2u32));
587 assert_eq!(tick_before.liquidity_gross, 3);
588 assert_eq!(tick_before.liquidity_net, 4);
589 assert!(tick_before.initialized);
590
591 tick_map.clear(2);
593
594 assert_eq!(tick_map.get_tick(2), None);
596 }
597
598 #[rstest]
599 fn test_cross_tick_flips_growth_variables(mut tick_map: TickMap) {
600 tick_map.set_tick(PoolTick::new(
602 2,
603 3,
604 4,
605 U256::from(1u32),
606 U256::from(2u32),
607 true,
608 7,
609 ));
610
611 let liquidity_net = tick_map.cross_tick(
616 2,
617 U256::from(7u32), U256::from(9u32), );
620
621 let tick = tick_map.get_tick(2).unwrap();
622
623 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);
629
630 assert_eq!(tick.liquidity_gross, 3);
632 assert_eq!(tick.liquidity_net, 4);
633 assert!(tick.initialized);
634 }
635}