mina_tree/address/
mod.rs

1pub mod raw;
2
3const fn compute_nbytes(nbits: usize) -> usize {
4    if nbits % 8 == 0 {
5        nbits / 8
6    } else {
7        (nbits / 8) + 1
8    }
9}
10
11/// Devnet uses trees of depth 35, which requires addresses of 35 bits
12const NBITS: usize = 35;
13const NBYTES: usize = compute_nbytes(NBITS);
14
15pub use raw::Direction;
16pub type Address = raw::Address<NBYTES>;
17pub type AddressIterator = raw::AddressIterator<NBYTES>;
18
19#[cfg(test)]
20mod tests {
21    use crate::AccountIndex;
22
23    use super::*;
24
25    #[cfg(target_family = "wasm")]
26    use wasm_bindgen_test::wasm_bindgen_test as test;
27
28    #[test]
29    fn test_address_iter() {
30        use Direction::*;
31
32        let addr = Address::try_from("10101010").unwrap();
33        assert_eq!(
34            addr.iter().collect::<Vec<_>>(),
35            &[Right, Left, Right, Left, Right, Left, Right, Left]
36        );
37
38        let addr = Address::try_from("01010101").unwrap();
39        assert_eq!(
40            addr.iter().collect::<Vec<_>>(),
41            &[Left, Right, Left, Right, Left, Right, Left, Right]
42        );
43
44        let addr = Address::try_from("010101010").unwrap();
45        assert_eq!(
46            addr.iter().collect::<Vec<_>>(),
47            &[Left, Right, Left, Right, Left, Right, Left, Right, Left]
48        );
49
50        let addr = Address::try_from("0101010101").unwrap();
51        assert_eq!(
52            addr.iter().collect::<Vec<_>>(),
53            &[Left, Right, Left, Right, Left, Right, Left, Right, Left, Right]
54        );
55
56        let addr = Address::try_from("").unwrap();
57        assert!(addr.iter().next().is_none());
58
59        assert!(Address::try_from("0101010101a").is_err());
60        assert!(Address::try_from("0".repeat((NBYTES * 8) - 1).as_str()).is_ok());
61        assert!(Address::try_from("0".repeat(NBYTES * 8).as_str()).is_err());
62    }
63
64    #[test]
65    fn test_address_next() {
66        let two: usize = 2;
67
68        // prev
69        for length in 5..23 {
70            let mut addr = Address::last(length);
71
72            elog!("length={length} until={:?}", two.pow(length as u32));
73            for _ in 0..two.pow(length as u32) - 1 {
74                let prev = addr.prev().unwrap();
75                assert_eq!(prev.next().unwrap(), addr);
76                addr = prev;
77            }
78
79            assert!(addr.prev().is_none());
80        }
81
82        // next
83        for length in 5..23 {
84            let mut addr = Address::first(length);
85
86            elog!("length={length} until={:?}", two.pow(length as u32));
87            for _ in 0..two.pow(length as u32) - 1 {
88                let next = addr.next().unwrap();
89                assert_eq!(next.prev().unwrap(), addr);
90                addr = next;
91            }
92
93            assert!(addr.next().is_none());
94        }
95    }
96
97    #[test]
98    fn test_address_clear() {
99        let mut inner: [u8; NBYTES] = Default::default();
100        inner[0] = 0b11111111;
101        inner[1] = 0b11111111;
102
103        let mut addr = Address { inner, length: 12 };
104        elog!("ADDR={:?}", addr);
105        addr.clear_after(6);
106        elog!("ADDR={:?}", addr);
107    }
108
109    #[test]
110    fn test_address_can_reach() {
111        let addr = Address::try_from("00").unwrap();
112        assert!(addr.is_before(&Address::try_from("00").unwrap()));
113        assert!(addr.is_before(&Address::try_from("01").unwrap()));
114        assert!(addr.is_before(&Address::try_from("000").unwrap()));
115        assert!(addr.is_before(&Address::try_from("001").unwrap()));
116        assert!(addr.is_before(&Address::try_from("010").unwrap()));
117        assert!(addr.is_before(&Address::try_from("100").unwrap()));
118
119        let addr = Address::try_from("101").unwrap();
120        assert!(addr.is_before(&Address::try_from("10100").unwrap()));
121        assert!(addr.is_before(&Address::try_from("10111").unwrap()));
122        assert!(!addr.is_before(&Address::try_from("10011").unwrap()));
123    }
124
125    #[test]
126    fn test_address_show() {
127        let addr = Address::first(2);
128        elog!("LA {:?}", addr);
129        let sec = addr.next().unwrap();
130        elog!("LA {:?}", sec);
131        elog!("LA {:?}", sec.child_left());
132    }
133
134    #[test]
135    fn test_address_index() {
136        for length in 1..20 {
137            let mut addr = Address::first(length);
138
139            for index in 0..2u64.pow(length as u32) - 1 {
140                let to_index = addr.to_index();
141
142                assert_eq!(to_index, AccountIndex(index));
143                assert_eq!(addr, Address::from_index(to_index, length));
144
145                addr = addr.next().unwrap();
146            }
147        }
148    }
149
150    #[test]
151    fn test_address_linear() {
152        for (index, s) in [
153            "", "0", "1", "00", "01", "10", "11", "000", "001", "010", "011", "100", "101", "110",
154            "111",
155        ]
156        .iter()
157        .enumerate()
158        {
159            let addr = Address::try_from(*s).unwrap();
160            assert_eq!(index as u64, addr.to_linear_index());
161        }
162    }
163
164    #[test]
165    fn test_address_children() {
166        let root = Address::try_from("00").unwrap();
167        let iter_children = root.iter_children(4);
168        assert_eq!(iter_children.len(), 4);
169        assert_eq!(
170            iter_children.collect::<Vec<_>>(),
171            &[
172                Address::try_from("0000").unwrap(),
173                Address::try_from("0001").unwrap(),
174                Address::try_from("0010").unwrap(),
175                Address::try_from("0011").unwrap(),
176            ]
177        );
178
179        let root = Address::try_from("01").unwrap();
180        let iter_children = root.iter_children(4);
181        assert_eq!(iter_children.len(), 4);
182        assert_eq!(
183            iter_children.collect::<Vec<_>>(),
184            &[
185                Address::try_from("0100").unwrap(),
186                Address::try_from("0101").unwrap(),
187                Address::try_from("0110").unwrap(),
188                Address::try_from("0111").unwrap(),
189            ]
190        );
191
192        let root = Address::try_from("10").unwrap();
193        let iter_children = root.iter_children(4);
194        assert_eq!(iter_children.len(), 4);
195        assert_eq!(
196            iter_children.collect::<Vec<_>>(),
197            &[
198                Address::try_from("1000").unwrap(),
199                Address::try_from("1001").unwrap(),
200                Address::try_from("1010").unwrap(),
201                Address::try_from("1011").unwrap(),
202            ]
203        );
204
205        let root = Address::try_from("11").unwrap();
206        let iter_children = root.iter_children(4);
207        assert_eq!(iter_children.len(), 4);
208        assert_eq!(
209            iter_children.collect::<Vec<_>>(),
210            &[
211                Address::try_from("1100").unwrap(),
212                Address::try_from("1101").unwrap(),
213                Address::try_from("1110").unwrap(),
214                Address::try_from("1111").unwrap(),
215            ]
216        );
217
218        let root = Address::try_from("00").unwrap();
219        let iter_children = root.iter_children(6);
220        assert_eq!(iter_children.len(), 16);
221    }
222
223    #[test]
224    fn test_address_children_parent_root_eq() {
225        let left = Address::first(1);
226        let right = left.next().unwrap();
227        assert_eq!(left.parent().unwrap(), Address::root());
228        assert_eq!(right.parent().unwrap(), Address::root());
229        assert_eq!(left.parent(), right.parent());
230    }
231}
mina_tree/address/mod.rs

mina_tree/address/
mod.rs
