darkfi_serial/types/
bridgetree.rs

1/* This file is part of DarkFi (https://dark.fi)
2 *
3 * Copyright (C) 2020-2026 Dyne.org foundation
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU Affero General Public License as
7 * published by the Free Software Foundation, either version 3 of the
8 * License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 * GNU Affero General Public License for more details.
14 *
15 * You should have received a copy of the GNU Affero General Public License
16 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
17 */
18
19use core::fmt::Debug;
20use std::io::{Error, Read, Result, Write};
21
22#[cfg(feature = "async")]
23use crate::{AsyncDecodable, AsyncEncodable};
24#[cfg(feature = "async")]
25use async_trait::async_trait;
26#[cfg(feature = "async")]
27use futures_lite::{AsyncRead, AsyncWrite};
28
29use crate::{Decodable, Encodable};
30
31impl Encodable for bridgetree::Position {
32    fn encode<S: Write>(&self, s: &mut S) -> Result<usize> {
33        u64::from(*self).encode(s)
34    }
35}
36
37#[cfg(feature = "async")]
38#[async_trait]
39impl AsyncEncodable for bridgetree::Position {
40    async fn encode_async<S: AsyncWrite + Unpin + Send>(&self, s: &mut S) -> Result<usize> {
41        u64::from(*self).encode_async(s).await
42    }
43}
44
45impl Decodable for bridgetree::Position {
46    fn decode<D: Read>(d: &mut D) -> Result<Self> {
47        let dec: u64 = Decodable::decode(d)?;
48        Ok(Self::from(dec))
49    }
50}
51
52#[cfg(feature = "async")]
53#[async_trait]
54impl AsyncDecodable for bridgetree::Position {
55    async fn decode_async<D: AsyncRead + Unpin + Send>(d: &mut D) -> Result<Self> {
56        let dec: u64 = AsyncDecodable::decode_async(d).await?;
57        Ok(Self::from(dec))
58    }
59}
60
61impl Encodable for bridgetree::Address {
62    fn encode<S: Write>(&self, s: &mut S) -> Result<usize> {
63        let mut len = 0;
64        len += u8::from(self.level()).encode(s)?;
65        len += self.index().encode(s)?;
66        Ok(len)
67    }
68}
69
70#[cfg(feature = "async")]
71#[async_trait]
72impl AsyncEncodable for bridgetree::Address {
73    async fn encode_async<S: AsyncWrite + Unpin + Send>(&self, s: &mut S) -> Result<usize> {
74        let mut len = 0;
75        len += u8::from(self.level()).encode_async(s).await?;
76        len += self.index().encode_async(s).await?;
77        Ok(len)
78    }
79}
80
81impl Decodable for bridgetree::Address {
82    fn decode<D: Read>(d: &mut D) -> Result<Self> {
83        let level: u8 = Decodable::decode(d)?;
84        let index = Decodable::decode(d)?;
85        Ok(Self::from_parts(level.into(), index))
86    }
87}
88
89#[cfg(feature = "async")]
90#[async_trait]
91impl AsyncDecodable for bridgetree::Address {
92    async fn decode_async<D: AsyncRead + Unpin + Send>(d: &mut D) -> Result<Self> {
93        let level: u8 = AsyncDecodable::decode_async(d).await?;
94        let index = AsyncDecodable::decode_async(d).await?;
95        Ok(Self::from_parts(level.into(), index))
96    }
97}
98
99impl<H: Encodable + Ord + Clone> Encodable for bridgetree::NonEmptyFrontier<H> {
100    fn encode<S: Write>(&self, s: &mut S) -> Result<usize> {
101        let mut len = 0;
102        len += self.position().encode(s)?;
103        len += self.leaf().encode(s)?;
104        len += self.ommers().to_vec().encode(s)?;
105        Ok(len)
106    }
107}
108
109#[cfg(feature = "async")]
110#[async_trait]
111impl<H: AsyncEncodable + Sync + Send + Ord + Clone> AsyncEncodable
112    for bridgetree::NonEmptyFrontier<H>
113{
114    async fn encode_async<S: AsyncWrite + Unpin + Send>(&self, s: &mut S) -> Result<usize> {
115        let mut len = 0;
116        len += self.position().encode_async(s).await?;
117        len += self.leaf().encode_async(s).await?;
118        len += self.ommers().to_vec().encode_async(s).await?;
119        Ok(len)
120    }
121}
122
123impl<H: Decodable + Ord + Clone> Decodable for bridgetree::NonEmptyFrontier<H> {
124    fn decode<D: Read>(d: &mut D) -> Result<Self> {
125        let position = Decodable::decode(d)?;
126        let leaf = Decodable::decode(d)?;
127        let ommers = Decodable::decode(d)?;
128
129        match Self::from_parts(position, leaf, ommers) {
130            Ok(v) => Ok(v),
131            Err(_) => Err(Error::other("FrontierError")),
132        }
133    }
134}
135
136#[cfg(feature = "async")]
137#[async_trait]
138impl<H: AsyncDecodable + Send + Ord + Clone> AsyncDecodable for bridgetree::NonEmptyFrontier<H> {
139    async fn decode_async<D: AsyncRead + Unpin + Send>(d: &mut D) -> Result<Self> {
140        let position = AsyncDecodable::decode_async(d).await?;
141        let leaf = AsyncDecodable::decode_async(d).await?;
142        let ommers = AsyncDecodable::decode_async(d).await?;
143
144        match Self::from_parts(position, leaf, ommers) {
145            Ok(v) => Ok(v),
146            Err(_) => Err(Error::other("FrontierError")),
147        }
148    }
149}
150
151impl<H: Encodable + Ord + Clone> Encodable for bridgetree::MerkleBridge<H> {
152    fn encode<S: Write>(&self, s: &mut S) -> Result<usize> {
153        let mut len = 0;
154        len += self.prior_position().encode(s)?;
155        len += self.tracking().encode(s)?;
156        len += self.ommers().encode(s)?;
157        len += self.frontier().encode(s)?;
158        Ok(len)
159    }
160}
161
162#[cfg(feature = "async")]
163#[async_trait]
164impl<H: AsyncEncodable + Sync + Send + Ord + Clone> AsyncEncodable for bridgetree::MerkleBridge<H> {
165    async fn encode_async<S: AsyncWrite + Unpin + Send>(&self, s: &mut S) -> Result<usize> {
166        let mut len = 0;
167        len += self.prior_position().encode_async(s).await?;
168        len += self.tracking().encode_async(s).await?;
169        len += self.ommers().encode_async(s).await?;
170        len += self.frontier().encode_async(s).await?;
171        Ok(len)
172    }
173}
174
175impl<H: Decodable + Ord + Clone> Decodable for bridgetree::MerkleBridge<H> {
176    fn decode<D: Read>(d: &mut D) -> Result<Self> {
177        let prior_position = Decodable::decode(d)?;
178        let tracking = Decodable::decode(d)?;
179        let ommers = Decodable::decode(d)?;
180        let frontier = Decodable::decode(d)?;
181        Ok(Self::from_parts(prior_position, tracking, ommers, frontier))
182    }
183}
184
185#[cfg(feature = "async")]
186#[async_trait]
187impl<H: AsyncDecodable + Send + Ord + Clone> AsyncDecodable for bridgetree::MerkleBridge<H> {
188    async fn decode_async<D: AsyncRead + Unpin + Send>(d: &mut D) -> Result<Self> {
189        let prior_position = AsyncDecodable::decode_async(d).await?;
190        let tracking = AsyncDecodable::decode_async(d).await?;
191        let ommers = AsyncDecodable::decode_async(d).await?;
192        let frontier = AsyncDecodable::decode_async(d).await?;
193        Ok(Self::from_parts(prior_position, tracking, ommers, frontier))
194    }
195}
196
197impl<C: Encodable> Encodable for bridgetree::Checkpoint<C> {
198    fn encode<S: Write>(&self, s: &mut S) -> Result<usize> {
199        let mut len = 0;
200        len += self.id().encode(s)?;
201        len += self.bridges_len().encode(s)?;
202        len += self.marked().encode(s)?;
203        len += self.forgotten().encode(s)?;
204        Ok(len)
205    }
206}
207
208#[cfg(feature = "async")]
209#[async_trait]
210impl<C: AsyncEncodable + Sync> AsyncEncodable for bridgetree::Checkpoint<C> {
211    async fn encode_async<S: AsyncWrite + Unpin + Send>(&self, s: &mut S) -> Result<usize> {
212        let mut len = 0;
213        len += self.id().encode_async(s).await?;
214        len += self.bridges_len().encode_async(s).await?;
215        len += self.marked().encode_async(s).await?;
216        len += self.forgotten().encode_async(s).await?;
217        Ok(len)
218    }
219}
220
221impl<C: Decodable> Decodable for bridgetree::Checkpoint<C> {
222    fn decode<D: Read>(d: &mut D) -> Result<Self> {
223        let id = Decodable::decode(d)?;
224        let bridges_len = Decodable::decode(d)?;
225        let marked = Decodable::decode(d)?;
226        let forgotten = Decodable::decode(d)?;
227        Ok(Self::from_parts(id, bridges_len, marked, forgotten))
228    }
229}
230
231#[cfg(feature = "async")]
232#[async_trait]
233impl<C: AsyncDecodable + Send> AsyncDecodable for bridgetree::Checkpoint<C> {
234    async fn decode_async<D: AsyncRead + Unpin + Send>(d: &mut D) -> Result<Self> {
235        let id = AsyncDecodable::decode_async(d).await?;
236        let bridges_len = AsyncDecodable::decode_async(d).await?;
237        let marked = AsyncDecodable::decode_async(d).await?;
238        let forgotten = AsyncDecodable::decode_async(d).await?;
239        Ok(Self::from_parts(id, bridges_len, marked, forgotten))
240    }
241}
242
243impl<H: Encodable + Ord + Clone, C: Encodable + Debug, const DEPTH: u8> Encodable
244    for bridgetree::BridgeTree<H, C, DEPTH>
245{
246    fn encode<S: Write>(&self, s: &mut S) -> Result<usize> {
247        let mut len = 0;
248        len += self.prior_bridges().to_vec().encode(s)?;
249        len += self.current_bridge().encode(s)?;
250        len += self.marked_indices().encode(s)?;
251        len += self.checkpoints().encode(s)?;
252        len += self.max_checkpoints().encode(s)?;
253        Ok(len)
254    }
255}
256
257#[cfg(feature = "async")]
258#[async_trait]
259impl<
260        H: AsyncEncodable + Sync + Send + Ord + Clone,
261        C: AsyncEncodable + Sync + Debug,
262        const DEPTH: u8,
263    > AsyncEncodable for bridgetree::BridgeTree<H, C, DEPTH>
264{
265    async fn encode_async<S: AsyncWrite + Unpin + Send>(&self, s: &mut S) -> Result<usize> {
266        let mut len = 0;
267        len += self.prior_bridges().to_vec().encode_async(s).await?;
268        len += self.current_bridge().encode_async(s).await?;
269        len += self.marked_indices().encode_async(s).await?;
270        len += self.checkpoints().encode_async(s).await?;
271        len += self.max_checkpoints().encode_async(s).await?;
272        Ok(len)
273    }
274}
275
276impl<
277        H: Decodable + Clone + Ord + bridgetree::Hashable,
278        C: Decodable + Clone + Ord + Eq + Debug,
279        const DEPTH: u8,
280    > Decodable for bridgetree::BridgeTree<H, C, DEPTH>
281{
282    fn decode<D: Read>(d: &mut D) -> Result<Self> {
283        let prior_bridges = Decodable::decode(d)?;
284        let current_bridge = Decodable::decode(d)?;
285        let saved = Decodable::decode(d)?;
286        let checkpoints = Decodable::decode(d)?;
287        let max_checkpoints = Decodable::decode(d)?;
288        match Self::from_parts(prior_bridges, current_bridge, saved, checkpoints, max_checkpoints) {
289            Ok(v) => Ok(v),
290            Err(_) => Err(Error::other("BridgeTreeError")),
291        }
292    }
293}
294
295#[cfg(feature = "async")]
296#[async_trait]
297impl<
298        H: AsyncDecodable + Send + Clone + Ord + bridgetree::Hashable,
299        C: AsyncDecodable + Send + Clone + Ord + Eq + Debug,
300        const DEPTH: u8,
301    > AsyncDecodable for bridgetree::BridgeTree<H, C, DEPTH>
302{
303    async fn decode_async<D: AsyncRead + Unpin + Send>(d: &mut D) -> Result<Self> {
304        let prior_bridges = AsyncDecodable::decode_async(d).await?;
305        let current_bridge = AsyncDecodable::decode_async(d).await?;
306        let saved = AsyncDecodable::decode_async(d).await?;
307        let checkpoints = AsyncDecodable::decode_async(d).await?;
308        let max_checkpoints = AsyncDecodable::decode_async(d).await?;
309        match Self::from_parts(prior_bridges, current_bridge, saved, checkpoints, max_checkpoints) {
310            Ok(v) => Ok(v),
311            Err(_) => Err(Error::other("BridgeTreeError")),
312        }
313    }
314}
315
316#[cfg(test)]
317mod tests {
318    use crate::{async_trait, deserialize, serialize, SerialDecodable, SerialEncodable};
319    use bridgetree::{BridgeTree, Hashable, Level};
320
321    #[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, SerialEncodable, SerialDecodable)]
322    struct Node(String);
323
324    impl Hashable for Node {
325        fn empty_leaf() -> Self {
326            Self("_".to_string())
327        }
328
329        fn combine(_: Level, a: &Self, b: &Self) -> Self {
330            Self(a.0.to_string() + &b.0)
331        }
332    }
333
334    #[test]
335    fn serialize_desrialize_inc_merkle_tree() {
336        const DEPTH: u8 = 8;
337
338        // Fill the tree with 100 leaves
339        let mut tree: BridgeTree<Node, usize, DEPTH> = BridgeTree::new(100);
340        for i in 0..100 {
341            tree.append(Node(format!("test{}", i)));
342            tree.mark();
343            tree.checkpoint(i);
344        }
345        let serial_tree = serialize(&tree);
346        let deserial_tree: BridgeTree<Node, usize, DEPTH> = deserialize(&serial_tree).unwrap();
347
348        // Empty tree
349        let tree2: BridgeTree<Node, usize, DEPTH> = BridgeTree::new(100);
350        let serial_tree2 = serialize(&tree2);
351        let deserial_tree2: BridgeTree<Node, usize, DEPTH> = deserialize(&serial_tree2).unwrap();
352
353        // Max leaves
354        let mut tree3: BridgeTree<Node, usize, DEPTH> = BridgeTree::new(100);
355        for i in 0..2_i32.pow(DEPTH as u32) {
356            tree3.append(Node(format!("test{}", i)));
357            tree3.mark();
358            tree3.checkpoint(i.try_into().unwrap());
359        }
360        let serial_tree3 = serialize(&tree3);
361        let deserial_tree3: BridgeTree<Node, usize, DEPTH> = deserialize(&serial_tree3).unwrap();
362
363        assert!(tree == deserial_tree);
364        assert!(tree2 == deserial_tree2);
365        assert!(tree3 == deserial_tree3);
366    }
367}
darkfi_serial/types/bridgetree.rs

darkfi_serial/types/
bridgetree.rs
