1use std::collections::HashMap;
17
18use alloy_primitives::U256;
19
20use crate::defi::tick_map::{
21 liquidity_math::tick_spacing_to_max_liquidity_per_tick, tick::PoolTick, tick_bitmap::TickBitmap,
22};
23
24pub mod bit_math;
25pub mod full_math;
26pub mod liquidity_math;
27pub mod sqrt_price_math;
28pub mod tick;
29pub mod tick_bitmap;
30pub mod tick_math;
31
32#[derive(Debug, Clone)]
38pub struct TickMap {
39 ticks: HashMap<i32, PoolTick>,
41 tick_bitmap: TickBitmap,
43 pub liquidity: u128,
45 pub max_liquidity_per_tick: u128,
47}
48
49impl Default for TickMap {
50 fn default() -> Self {
51 Self::new(0)
52 }
53}
54
55impl TickMap {
56 pub fn new(tick_spacing: u32) -> Self {
58 Self {
59 ticks: HashMap::new(),
60 tick_bitmap: TickBitmap::new(tick_spacing),
61 liquidity: 0,
62 max_liquidity_per_tick: tick_spacing_to_max_liquidity_per_tick(tick_spacing as i32),
63 }
64 }
65
66 pub fn get_tick(&self, tick: i32) -> Option<&PoolTick> {
68 self.ticks.get(&tick)
69 }
70
71 pub fn get_tick_or_init(&mut self, tick: i32) -> &mut PoolTick {
73 self.ticks
74 .entry(tick)
75 .or_insert_with(|| PoolTick::from_tick(tick))
76 }
77
78 pub fn get_fee_growth_inside(
80 &mut self,
81 lower_tick: i32,
82 upper_tick: i32,
83 current_tick: i32,
84 fee_growth_global_0: U256,
85 fee_growth_global_1: U256,
86 ) -> (U256, U256) {
87 self.ticks
89 .entry(lower_tick)
90 .or_insert_with(|| PoolTick::from_tick(lower_tick));
91 self.ticks
92 .entry(upper_tick)
93 .or_insert_with(|| PoolTick::from_tick(upper_tick));
94
95 let lower_tick = &self.ticks[&lower_tick];
97 let upper_tick = &self.ticks[&upper_tick];
98
99 let fee_growth_below_0 = if current_tick >= lower_tick.value {
101 lower_tick.fee_growth_outside_0
102 } else {
103 fee_growth_global_0 - lower_tick.fee_growth_outside_0
104 };
105 let fee_growth_below_1 = if current_tick >= lower_tick.value {
106 lower_tick.fee_growth_outside_1
107 } else {
108 fee_growth_global_1 - lower_tick.fee_growth_outside_1
109 };
110
111 let fee_growth_above_0 = if current_tick < upper_tick.value {
113 upper_tick.fee_growth_outside_0
114 } else {
115 fee_growth_global_0 - upper_tick.fee_growth_outside_0
116 };
117 let fee_growth_above_1 = if current_tick < upper_tick.value {
118 upper_tick.fee_growth_outside_1
119 } else {
120 fee_growth_global_1 - upper_tick.fee_growth_outside_1
121 };
122
123 let fee_growth_inside_0 = fee_growth_global_0 - fee_growth_below_0 - fee_growth_above_0;
125 let fee_growth_inside_1 = fee_growth_global_1 - fee_growth_below_1 - fee_growth_above_1;
126
127 (fee_growth_inside_0, fee_growth_inside_1)
128 }
129
130 fn update_tick_data(
132 &mut self,
133 tick: i32,
134 tick_current: i32,
135 liquidity_delta: i128,
136 upper: bool,
137 fee_growth_global_0: U256,
138 fee_growth_global_1: U256,
139 ) -> bool {
140 let max_liquidity_per_tick = self.max_liquidity_per_tick;
141 let tick = self.get_tick_or_init(tick);
142
143 let liquidity_gross_before = tick.update_liquidity(liquidity_delta, upper);
144 let liquidity_gross_after = tick.liquidity_gross;
145 assert!(
146 liquidity_gross_after <= max_liquidity_per_tick,
147 "Liquidity exceeds maximum per tick"
148 );
149
150 if liquidity_gross_before == 0 {
151 if tick.value <= tick_current {
153 tick.fee_growth_outside_0 = fee_growth_global_0;
154 tick.fee_growth_outside_1 = fee_growth_global_1
155 }
156 tick.initialized = true
157 }
158
159 (liquidity_gross_after == 0) != (liquidity_gross_before == 0)
161 }
162
163 pub fn update(
165 &mut self,
166 tick: i32,
167 tick_current: i32,
168 liquidity_delta: i128,
169 upper: bool,
170 fee_growth_global_0: U256,
171 fee_growth_global_1: U256,
172 ) -> bool {
173 let flipped = self.update_tick_data(
174 tick,
175 tick_current,
176 liquidity_delta,
177 upper,
178 fee_growth_global_0,
179 fee_growth_global_1,
180 );
181
182 if flipped {
184 self.tick_bitmap.flip_tick(tick);
185 }
186
187 flipped
188 }
189
190 pub fn cross_tick(
192 &mut self,
193 tick: i32,
194 fee_growth_global_0: U256,
195 fee_growth_global_1: U256,
196 ) -> i128 {
197 let tick = self.get_tick_or_init(tick);
198 tick.update_fee_growth(fee_growth_global_0, fee_growth_global_1);
199
200 tick.liquidity_net
201 }
202
203 #[must_use]
205 pub fn active_tick_count(&self) -> usize {
206 self.ticks
207 .iter()
208 .filter(|(_, tick)| self.is_tick_initialized(tick.value))
209 .count()
210 }
211
212 #[must_use]
214 pub fn total_tick_count(&self) -> usize {
215 self.ticks.len()
216 }
217
218 #[must_use]
220 pub fn get_all_ticks(&self) -> &HashMap<i32, PoolTick> {
221 &self.ticks
222 }
223
224 pub fn set_tick(&mut self, tick_data: PoolTick) {
226 let tick = tick_data.value;
227 self.ticks.insert(tick, tick_data);
228 }
229
230 pub fn restore_tick(&mut self, tick_data: PoolTick) {
235 let is_initialized = tick_data.initialized;
236 let tick_value = tick_data.value;
237
238 self.set_tick(tick_data);
239
240 if is_initialized {
242 self.tick_bitmap.flip_tick(tick_value);
243 }
244 }
245
246 pub fn clear(&mut self, tick: i32) {
248 self.ticks.remove(&tick);
249 }
250
251 pub fn next_initialized_tick(&self, tick: i32, lte: bool) -> (i32, bool) {
253 self.tick_bitmap
254 .next_initialized_tick_within_one_word(tick, lte)
255 }
256
257 pub fn is_tick_initialized(&self, tick: i32) -> bool {
259 self.tick_bitmap.is_initialized(tick)
260 }
261}
262
263#[cfg(test)]
268mod tests {
269 use std::str::FromStr;
270
271 use rstest::{fixture, rstest};
272
273 use super::*;
274
275 #[fixture]
276 fn tick_map() -> TickMap {
277 TickMap::new(1)
278 }
279
280 #[rstest]
281 fn test_new_tick_maps(tick_map: TickMap) {
282 assert_eq!(tick_map.active_tick_count(), 0);
283 assert_eq!(tick_map.liquidity, 0);
284 }
285
286 #[rstest]
287 fn test_get_fee_growth_inside_uninitialized_ticks(mut tick_map: TickMap) {
288 let fee_growth_global_0 = U256::from(15);
289 let fee_growth_global_1 = U256::from(15);
290
291 let (fee_growth_inside_0, fee_growth_inside_1) =
293 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
294 assert_eq!(fee_growth_inside_0, U256::from_str("15").unwrap());
295 assert_eq!(fee_growth_inside_1, U256::from_str("15").unwrap());
296
297 let (fee_growth_inside_0, fee_growth_inside_1) =
299 tick_map.get_fee_growth_inside(-2, 2, 4, fee_growth_global_0, fee_growth_global_1);
300 assert_eq!(fee_growth_inside_0, U256::ZERO);
301 assert_eq!(fee_growth_inside_1, U256::ZERO);
302
303 let (fee_growth_inside_0, fee_growth_inside_1) =
305 tick_map.get_fee_growth_inside(-2, 2, -4, fee_growth_global_0, fee_growth_global_1);
306 assert_eq!(fee_growth_inside_0, U256::ZERO);
307 assert_eq!(fee_growth_inside_1, U256::ZERO);
308 }
309
310 #[rstest]
311 fn test_get_fee_growth_inside_if_upper_tick_is_below(mut tick_map: TickMap) {
312 tick_map.set_tick(PoolTick::new(
313 2, 0,
315 0,
316 U256::from(2),
317 U256::from(3),
318 true,
319 0,
320 ));
321 let fee_growth_global_0 = U256::from(15);
322 let fee_growth_global_1 = U256::from(15);
323 let (fee_growth_inside_0, fee_growth_inside_1) =
324 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
325 assert_eq!(fee_growth_inside_0, U256::from(13));
326 assert_eq!(fee_growth_inside_1, U256::from(12));
327 }
328
329 #[rstest]
330 fn test_get_fee_growth_inside_if_lower_tick_is_above(mut tick_map: TickMap) {
331 tick_map.set_tick(PoolTick::new(
332 -2, 0,
334 0,
335 U256::from(2),
336 U256::from(3),
337 true,
338 0,
339 ));
340 let fee_growth_global_0 = U256::from(15);
341 let fee_growth_global_1 = U256::from(15);
342 let (fee_growth_inside_0, fee_growth_inside_1) =
343 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
344 assert_eq!(fee_growth_inside_0, U256::from(13));
345 assert_eq!(fee_growth_inside_1, U256::from(12));
346 }
347
348 #[rstest]
349 fn test_get_fee_growth_inside_if_upper_and_lower_tick_are_initialized(mut tick_map: TickMap) {
350 tick_map.set_tick(PoolTick::new(
351 -2, 0,
353 0,
354 U256::from(2),
355 U256::from(3),
356 true,
357 0,
358 ));
359 tick_map.set_tick(PoolTick::new(
360 2, 0,
362 0,
363 U256::from(4),
364 U256::from(1),
365 true,
366 0,
367 ));
368 let fee_growth_global_0 = U256::from(15);
369 let fee_growth_global_1 = U256::from(15);
370 let (fee_growth_inside_0, fee_growth_inside_1) =
371 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
372 assert_eq!(fee_growth_inside_0, U256::from(9));
373 assert_eq!(fee_growth_inside_1, U256::from(11));
374 }
375
376 #[rstest]
377 fn test_get_fee_growth_inside_with_overflow(mut tick_map: TickMap) {
378 tick_map.set_tick(PoolTick::new(
379 -2,
380 0,
381 0,
382 U256::MAX - U256::from(3u32), U256::MAX - U256::from(2u32), true,
385 0,
386 ));
387 tick_map.set_tick(PoolTick::new(
388 2,
389 0,
390 0,
391 U256::from(3u32),
392 U256::from(5u32),
393 true,
394 0,
395 ));
396 let fee_growth_global_0 = U256::from(15);
397 let fee_growth_global_1 = U256::from(15);
398 let (fee_growth_inside_0, fee_growth_inside_1) =
399 tick_map.get_fee_growth_inside(-2, 2, 0, fee_growth_global_0, fee_growth_global_1);
400 assert_eq!(fee_growth_inside_0, U256::from(16u32));
401 assert_eq!(fee_growth_inside_1, U256::from(13u32));
402 }
403
404 #[rstest]
405 fn test_update_flips_from_zero_to_nonzero(mut tick_map: TickMap) {
406 assert!(!tick_map.is_tick_initialized(0));
408
409 let flipped = tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
410 assert!(flipped);
411
412 assert!(tick_map.is_tick_initialized(0));
414 }
415
416 #[rstest]
417 fn test_update_does_not_flip_from_nonzero_to_greater_nonzero(mut tick_map: TickMap) {
418 tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
420 assert!(tick_map.is_tick_initialized(0));
421
422 let flipped = tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
424 assert!(!flipped);
425
426 assert!(tick_map.is_tick_initialized(0));
428 }
429
430 #[rstest]
431 fn test_update_flips_from_nonzero_to_zero(mut tick_map: TickMap) {
432 let flipped_first = tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
434 assert!(flipped_first);
435 assert!(tick_map.is_tick_initialized(0));
436
437 let flipped_second = tick_map.update(0, 0, -1, false, U256::ZERO, U256::ZERO);
439 assert!(flipped_second);
440
441 assert!(!tick_map.is_tick_initialized(0));
443 }
444
445 #[rstest]
446 fn test_update_does_not_flip_from_nonzero_to_lesser_nonzero(mut tick_map: TickMap) {
447 tick_map.update(0, 0, 2, false, U256::ZERO, U256::ZERO);
449 assert!(tick_map.is_tick_initialized(0));
450
451 let flipped = tick_map.update(0, 0, -1, false, U256::ZERO, U256::ZERO);
453 assert!(!flipped);
454
455 assert!(tick_map.is_tick_initialized(0));
457 }
458
459 #[rstest]
460 #[should_panic(expected = "Liquidity exceeds maximum per tick")]
461 fn test_update_reverts_if_total_liquidity_gross_exceeds_max() {
462 let mut tick_map = TickMap::new(200); let max_liquidity = tick_map.max_liquidity_per_tick;
466 tick_map.update(
467 0,
468 0,
469 (max_liquidity / 2) as i128,
470 false,
471 U256::ZERO,
472 U256::ZERO,
473 );
474 tick_map.update(
475 0,
476 0,
477 (max_liquidity / 2) as i128,
478 true,
479 U256::ZERO,
480 U256::ZERO,
481 );
482
483 tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
485 }
486
487 #[rstest]
488 fn test_update_nets_liquidity_based_on_upper_flag(mut tick_map: TickMap) {
489 tick_map.update(0, 0, 2, false, U256::ZERO, U256::ZERO);
491 tick_map.update(0, 0, 1, true, U256::ZERO, U256::ZERO);
493 tick_map.update(0, 0, 3, true, U256::ZERO, U256::ZERO);
495 tick_map.update(0, 0, 1, false, U256::ZERO, U256::ZERO);
497
498 let tick = tick_map.get_tick(0).unwrap();
499
500 assert_eq!(tick.liquidity_gross, 7);
502
503 assert_eq!(tick.liquidity_net, -1);
505 }
506
507 #[rstest]
508 fn test_update_assumes_all_growth_happens_below_ticks_lte_current_tick() {
509 let mut tick_map = TickMap::new(1);
510 let fee_growth_global_0 = U256::from(15);
511 let fee_growth_global_1 = U256::from(2);
512 tick_map.update(1, 1, 1, false, fee_growth_global_0, fee_growth_global_1);
514
515 let tick = tick_map.get_tick(1).unwrap();
516
517 assert_eq!(tick.fee_growth_outside_0, U256::from(15u32));
519 assert_eq!(tick.fee_growth_outside_1, U256::from(2u32));
520 assert!(tick.initialized);
521 assert_eq!(tick.liquidity_gross, 1);
522 assert_eq!(tick.liquidity_net, 1);
523 }
524
525 #[rstest]
526 fn test_update_does_not_set_growth_fields_if_tick_already_initialized() {
527 let mut tick_map = TickMap::new(1);
528 let fee_growth_0_initial = U256::from(1);
529 let fee_growth_1_initial = U256::from(2);
530 tick_map.update(1, 1, 1, false, fee_growth_0_initial, fee_growth_1_initial);
532
533 let fee_growth_0_second = U256::from(6);
535 let fee_growth_1_second = U256::from(7);
536 tick_map.update(1, 1, 1, false, fee_growth_0_second, fee_growth_1_second);
537
538 let tick = tick_map.get_tick(1).unwrap();
539
540 assert_eq!(tick.fee_growth_outside_0, U256::from(1u32)); assert_eq!(tick.fee_growth_outside_1, U256::from(2u32)); assert!(tick.initialized);
544 assert_eq!(tick.liquidity_gross, 2); assert_eq!(tick.liquidity_net, 2); }
547
548 #[rstest]
549 fn test_update_does_not_set_growth_fields_for_ticks_gt_current_tick() {
550 let mut tick_map = TickMap::new(1);
551 let fee_growth_global_0 = U256::from(1);
552 let fee_growth_global_1 = U256::from(2u32);
553 tick_map.update(2, 1, 1, false, fee_growth_global_0, fee_growth_global_1);
555
556 let tick = tick_map.get_tick(2).unwrap();
557
558 assert_eq!(tick.fee_growth_outside_0, U256::ZERO); assert_eq!(tick.fee_growth_outside_1, U256::ZERO); assert!(tick.initialized);
562 assert_eq!(tick.liquidity_gross, 1);
563 assert_eq!(tick.liquidity_net, 1);
564 }
565
566 #[rstest]
567 fn test_clear_deletes_all_data_in_tick(mut tick_map: TickMap) {
568 tick_map.set_tick(PoolTick::new(
570 2,
571 3,
572 4,
573 U256::from(1u32),
574 U256::from(2u32),
575 true,
576 0,
577 ));
578
579 let tick_before = tick_map.get_tick(2).unwrap();
581 assert_eq!(tick_before.fee_growth_outside_0, U256::from(1u32));
582 assert_eq!(tick_before.fee_growth_outside_1, U256::from(2u32));
583 assert_eq!(tick_before.liquidity_gross, 3);
584 assert_eq!(tick_before.liquidity_net, 4);
585 assert!(tick_before.initialized);
586
587 tick_map.clear(2);
589
590 assert_eq!(tick_map.get_tick(2), None);
592 }
593
594 #[rstest]
595 fn test_cross_tick_flips_growth_variables(mut tick_map: TickMap) {
596 tick_map.set_tick(PoolTick::new(
598 2,
599 3,
600 4,
601 U256::from(1u32),
602 U256::from(2u32),
603 true,
604 7,
605 ));
606
607 let liquidity_net = tick_map.cross_tick(
612 2,
613 U256::from(7u32), U256::from(9u32), );
616
617 let tick = tick_map.get_tick(2).unwrap();
618
619 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);
625
626 assert_eq!(tick.liquidity_gross, 3);
628 assert_eq!(tick.liquidity_net, 4);
629 assert!(tick.initialized);
630 }
631}