kabu_defi_uniswap_v3_math/
tick_bitmap.rs

1use crate::U256_1;
2use crate::tick_provider::TickProvider;
3use crate::{bit_math, error::UniswapV3MathError};
4use alloy::primitives::{Address, BlockNumber, U256};
5use alloy::providers::Provider;
6use alloy::sol;
7use std::{collections::HashMap, sync::Arc};
8
9sol! {
10    #[sol(rpc)]
11    interface IUniswapV3Pool {
12        function tick_bitmap(int16) external returns (uint256);
13    }
14}
15
16//Flips the initialized state for a given tick from false to true, or vice versa
17pub fn flip_tick(tick_bitmap: &mut HashMap<i16, U256>, tick: i32, tick_spacing: i32) -> Result<(), UniswapV3MathError> {
18    if (tick % tick_spacing) != 0 {
19        return Err(UniswapV3MathError::TickSpacingError);
20    }
21
22    let (word_pos, bit_pos) = position(tick / tick_spacing);
23    let mask = U256_1 << bit_pos;
24    let word = *tick_bitmap.get(&word_pos).unwrap_or(&U256::ZERO);
25    tick_bitmap.insert(word_pos, word ^ mask);
26    Ok(())
27}
28
29//Returns the next initialized tick contained in the same word (or adjacent word) as the tick that is either
30//to the left (less than or equal to) or right (greater than) of the given tick
31pub fn next_initialized_tick_within_one_word<T: TickProvider>(
32    tick_provider: &T,
33    tick: i32,
34    tick_spacing: i32,
35    lte: bool,
36) -> Result<(i32, bool), UniswapV3MathError> {
37    let compressed = if tick < 0 && tick % tick_spacing != 0 { (tick / tick_spacing) - 1 } else { tick / tick_spacing };
38
39    if lte {
40        let (word_pos, bit_pos) = position(compressed);
41
42        let mask = (U256_1 << bit_pos) - U256_1 + (U256_1 << bit_pos);
43
44        let masked = tick_provider.get_tick(word_pos).unwrap_or(U256::ZERO) & mask;
45
46        let initialized = !masked.is_zero();
47
48        let next = if initialized {
49            (compressed - (bit_pos.overflowing_sub(bit_math::most_significant_bit(masked)?).0) as i32) * tick_spacing
50        } else {
51            (compressed - bit_pos as i32) * tick_spacing
52        };
53
54        Ok((next, initialized))
55    } else {
56        let (word_pos, bit_pos) = position(compressed + 1);
57
58        let mask = !((U256_1 << bit_pos) - U256_1);
59
60        let masked = tick_provider.get_tick(word_pos).unwrap_or(U256::ZERO) & mask;
61
62        let initialized = !masked.is_zero();
63
64        let next = if initialized {
65            (compressed + 1 + (bit_math::least_significant_bit(masked)?.overflowing_sub(bit_pos).0) as i32) * tick_spacing
66        } else {
67            (compressed + 1 + ((0xFF - bit_pos) as i32)) * tick_spacing
68        };
69
70        Ok((next, initialized))
71    }
72}
73
74//Returns next and initialized. This function calls the node to get the word at the word_pos.
75//current_word is the current word in the TickBitmap of the pool based on `tick`. TickBitmap[word_pos] = current_word
76//Where word_pos is the 256 bit offset of the ticks word_pos.. word_pos := tick >> 8
77pub async fn next_initialized_tick_within_one_word_from_provider<P: Provider>(
78    tick: i32,
79    tick_spacing: i32,
80    lte: bool,
81    pool_address: Address,
82    block_number: Option<BlockNumber>,
83    provider: Arc<P>,
84) -> Result<(i32, bool), UniswapV3MathError> {
85    let compressed = if tick < 0 && tick % tick_spacing != 0 { (tick / tick_spacing) - 1 } else { tick / tick_spacing };
86
87    if lte {
88        let (word_pos, bit_pos) = position(compressed);
89        let mask = (U256_1 << bit_pos) - U256_1 + (U256_1 << bit_pos);
90
91        let word = if let Some(block_number) = block_number {
92            match IUniswapV3Pool::new(pool_address, provider).tick_bitmap(word_pos).block(block_number.into()).call().await {
93                Ok(word) => word,
94                Err(err) => return Err(UniswapV3MathError::MiddlewareError(err.to_string())),
95            }
96        } else {
97            match IUniswapV3Pool::new(pool_address, provider).tick_bitmap(word_pos).call().await {
98                Ok(word) => word,
99                Err(err) => return Err(UniswapV3MathError::MiddlewareError(err.to_string())),
100            }
101        };
102
103        let masked = word & mask;
104
105        let initialized = !masked.is_zero();
106
107        let next = if initialized {
108            (compressed - (bit_pos.overflowing_sub(bit_math::most_significant_bit(masked)?).0) as i32) * tick_spacing
109        } else {
110            (compressed - bit_pos as i32) * tick_spacing
111        };
112
113        Ok((next, initialized))
114    } else {
115        let (word_pos, bit_pos) = position(compressed + 1);
116        let mask = !((U256_1 << bit_pos) - U256_1);
117
118        let word = if let Some(block_number) = block_number {
119            match IUniswapV3Pool::new(pool_address, provider).tick_bitmap(word_pos).block(block_number.into()).call().await {
120                Ok(word) => word,
121                Err(err) => return Err(UniswapV3MathError::MiddlewareError(err.to_string())),
122            }
123        } else {
124            match IUniswapV3Pool::new(pool_address, provider).tick_bitmap(word_pos).call().await {
125                Ok(word) => word,
126                Err(err) => return Err(UniswapV3MathError::MiddlewareError(err.to_string())),
127            }
128        };
129
130        let masked = word & mask;
131        let initialized = !masked.is_zero();
132
133        let next = if initialized {
134            (compressed + 1 + (bit_math::least_significant_bit(masked)?.overflowing_sub(bit_pos).0) as i32) * tick_spacing
135        } else {
136            (compressed + 1 + ((0xFF - bit_pos) as i32)) * tick_spacing
137        };
138
139        Ok((next, initialized))
140    }
141}
142
143//Computes the position in the mapping where the initialized bit for a tick lives
144pub fn position(tick: i32) -> (i16, u8) {
145    ((tick >> 8) as i16, (tick % 256) as u8)
146}
147
148#[cfg(test)]
149mod test {
150    use std::{collections::HashMap, vec};
151
152    use super::{flip_tick, next_initialized_tick_within_one_word};
153    use crate::tick_provider::TickProvider;
154    use alloy::primitives::U256;
155
156    pub struct TickProviderHashMap {
157        tick_bitmap: HashMap<i16, U256>,
158    }
159    impl TickProviderHashMap {
160        pub fn new(tick_bitmap: HashMap<i16, U256>) -> Self {
161            Self { tick_bitmap }
162        }
163        pub fn mut_ref(&mut self) -> &mut HashMap<i16, U256> {
164            &mut self.tick_bitmap
165        }
166        pub fn clear(&mut self) {
167            self.tick_bitmap.clear();
168        }
169    }
170    impl TickProvider for TickProviderHashMap {
171        fn get_tick(&self, word_pos: i16) -> eyre::Result<U256> {
172            let val = self.tick_bitmap.get(&word_pos).cloned();
173            Ok(val.unwrap_or(U256::ZERO))
174        }
175    }
176
177    pub fn init_test_ticks() -> eyre::Result<TickProviderHashMap> {
178        let test_ticks = vec![-200, -55, -4, 70, 78, 84, 139, 240, 535];
179        let mut tick_bitmap: HashMap<i16, U256> = HashMap::new();
180        for tick in test_ticks {
181            flip_tick(&mut tick_bitmap, tick, 1)?;
182        }
183        Ok(TickProviderHashMap::new(tick_bitmap))
184    }
185
186    pub fn initialized<T: TickProvider>(tick: i32, tick_provider: &T) -> eyre::Result<bool> {
187        let (next, initialized) = next_initialized_tick_within_one_word(tick_provider, tick, 1, true)?;
188        if next == tick { Ok(initialized) } else { Ok(false) }
189    }
190
191    #[test]
192    pub fn test_next_initialized_tick_within_one_word_lte_false() -> eyre::Result<()> {
193        let mut tick_bitmap = init_test_ticks()?;
194        //returns tick to right if at initialized tick
195        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 78, 1, false)?;
196        assert_eq!(next, 84);
197        assert!(initialized);
198        tick_bitmap = init_test_ticks()?;
199        // //returns the tick directly to the right
200        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 77, 1, false)?;
201
202        assert_eq!(next, 78);
203        assert!(initialized);
204        tick_bitmap = init_test_ticks()?;
205        // //returns the tick directly to the right
206        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, -56, 1, false)?;
207
208        assert_eq!(next, -55);
209        assert!(initialized);
210        tick_bitmap = init_test_ticks()?;
211        //returns the next words initialized tick if on the right boundary
212        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 255, 1, false)?;
213
214        assert_eq!(next, 511);
215        assert!(!initialized);
216        tick_bitmap = init_test_ticks()?;
217        //returns the next words initialized tick if on the right boundary
218        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, -257, 1, false)?;
219
220        assert_eq!(next, -200);
221        assert!(initialized);
222        tick_bitmap = init_test_ticks()?;
223        //returns the next initialized tick from the next word
224        flip_tick(tick_bitmap.mut_ref(), 340, 1)?;
225        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 328, 1, false)?;
226
227        assert_eq!(next, 340);
228        assert!(initialized);
229        tick_bitmap = init_test_ticks()?;
230        //does not exceed boundary
231        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 508, 1, false)?;
232
233        assert_eq!(next, 511);
234        assert!(!initialized);
235        tick_bitmap = init_test_ticks()?;
236        //skips entire word
237        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 255, 1, false)?;
238
239        assert_eq!(next, 511);
240        assert!(!initialized);
241        tick_bitmap = init_test_ticks()?;
242        //skips half word
243        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 383, 1, false)?;
244
245        assert_eq!(next, 511);
246        assert!(!initialized);
247        Ok(())
248    }
249
250    #[test]
251    pub fn test_next_initialized_tick_within_one_word_lte_true() -> eyre::Result<()> {
252        let mut tick_bitmap = init_test_ticks()?;
253        //returns same tick if initialized
254        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 78, 1, true)?;
255        assert_eq!(next, 78);
256        assert!(initialized);
257        tick_bitmap = init_test_ticks()?;
258        //returns tick directly to the left of input tick if not initialized
259        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 79, 1, true)?;
260
261        assert_eq!(next, 78);
262        assert!(initialized);
263        tick_bitmap = init_test_ticks()?;
264        //will not exceed the word boundary
265        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 258, 1, true)?;
266
267        assert_eq!(next, 256);
268        assert!(!initialized);
269        tick_bitmap = init_test_ticks()?;
270        //at the word boundary
271        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 256, 1, true)?;
272
273        assert_eq!(next, 256);
274        assert!(!initialized);
275        tick_bitmap = init_test_ticks()?;
276        //word boundary less 1 (next initialized tick in next word)',
277        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 72, 1, true)?;
278
279        assert_eq!(next, 70);
280        assert!(initialized);
281        tick_bitmap = init_test_ticks()?;
282        //word boundary
283        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, -257, 1, true)?;
284
285        assert_eq!(next, -512);
286        assert!(!initialized);
287        tick_bitmap = init_test_ticks()?;
288        //entire empty word
289        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 1023, 1, true)?;
290
291        assert_eq!(next, 768);
292        assert!(!initialized);
293        tick_bitmap = init_test_ticks()?;
294        //halfway through empty word
295        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 900, 1, true)?;
296
297        assert_eq!(next, 768);
298        assert!(!initialized);
299        tick_bitmap = init_test_ticks()?;
300        //boundary is initialized
301        flip_tick(tick_bitmap.mut_ref(), 329, 1)?;
302        let (next, initialized) = next_initialized_tick_within_one_word(&tick_bitmap, 456, 1, true)?;
303
304        assert_eq!(next, 329);
305        assert!(initialized);
306        Ok(())
307    }
308
309    #[test]
310    pub fn test_initialized() -> eyre::Result<()> {
311        //is false at first
312        let mut tick_bitmap = TickProviderHashMap::new(HashMap::new());
313        let is_initialized = initialized(1, &tick_bitmap)?;
314
315        assert!(!is_initialized);
316        //is flipped by #flipTick
317        flip_tick(tick_bitmap.mut_ref(), 1, 1)?;
318        let is_initialized: bool = initialized(1, &tick_bitmap)?;
319        assert!(is_initialized);
320
321        //is flipped back by #flipTick
322        tick_bitmap.clear();
323        flip_tick(tick_bitmap.mut_ref(), 1, 1)?;
324        flip_tick(tick_bitmap.mut_ref(), 1, 1)?;
325        let is_initialized = initialized(1, &tick_bitmap)?;
326        assert!(!is_initialized);
327
328        //is not changed by another flip to a different tick
329        tick_bitmap.clear();
330        flip_tick(tick_bitmap.mut_ref(), 2, 1)?;
331        let is_initialized = initialized(1, &tick_bitmap)?;
332        assert!(!is_initialized);
333
334        //is not changed by another flip to a different tick on another word
335        tick_bitmap.clear();
336        flip_tick(tick_bitmap.mut_ref(), 1 + 256, 1)?;
337        let is_initialized = initialized(257, &tick_bitmap)?;
338        assert!(is_initialized);
339        let is_initialized = initialized(1, &tick_bitmap)?;
340        assert!(!is_initialized);
341        Ok(())
342    }
343
344    #[test]
345    pub fn test_flip_tick() -> eyre::Result<()> {
346        //flips only the specified tick
347        let mut tick_bitmap = TickProviderHashMap::new(HashMap::new());
348        flip_tick(tick_bitmap.mut_ref(), -230, 1)?;
349        let is_initialized = initialized(-230, &tick_bitmap)?;
350        assert!(is_initialized);
351        let is_initialized = initialized(-231, &tick_bitmap)?;
352        assert!(!is_initialized);
353        let is_initialized = initialized(-229, &tick_bitmap)?;
354        assert!(!is_initialized);
355        let is_initialized = initialized(-230 + 256, &tick_bitmap)?;
356        assert!(!is_initialized);
357        let is_initialized = initialized(-230 - 256, &tick_bitmap)?;
358        assert!(!is_initialized);
359        flip_tick(tick_bitmap.mut_ref(), -230, 1)?;
360        let is_initialized = initialized(-230, &tick_bitmap)?;
361        assert!(!is_initialized);
362        let is_initialized = initialized(-231, &tick_bitmap)?;
363        assert!(!is_initialized);
364        let is_initialized = initialized(-229, &tick_bitmap)?;
365        assert!(!is_initialized);
366        let is_initialized = initialized(-230 + 256, &tick_bitmap)?;
367        assert!(!is_initialized);
368        let is_initialized = initialized(-230 - 256, &tick_bitmap)?;
369        assert!(!is_initialized);
370        //reverts only itself
371        tick_bitmap.clear();
372        flip_tick(tick_bitmap.mut_ref(), -230, 1)?;
373        flip_tick(tick_bitmap.mut_ref(), -259, 1)?;
374        flip_tick(tick_bitmap.mut_ref(), -229, 1)?;
375        flip_tick(tick_bitmap.mut_ref(), 500, 1)?;
376        flip_tick(tick_bitmap.mut_ref(), -259, 1)?;
377        flip_tick(tick_bitmap.mut_ref(), -229, 1)?;
378        flip_tick(tick_bitmap.mut_ref(), -259, 1)?;
379        let is_initialized = initialized(-259, &tick_bitmap)?;
380        assert!(is_initialized);
381        let is_initialized = initialized(-229, &tick_bitmap)?;
382        assert!(!is_initialized);
383
384        Ok(())
385    }
386}
kabu_defi_uniswap_v3_math/tick_bitmap.rs

kabu_defi_uniswap_v3_math/
tick_bitmap.rs
