bao_tree/io/
outboard.rs

1//! Implementations of the outboard traits
2//!
3//! A number of implementations for the sync and async outboard traits are provided.
4//! Implementations for in-memory outboards, for outboards where the data resides on disk,
5//! and a special implementation [EmptyOutboard] that just ignores all writes.
6use crate::{blake3, BaoTree, BlockSize, TreeNode};
7use std::io;
8
9/// An empty outboard, that just returns 0 hashes for all nodes.
10///
11/// Also allows you to write and will immediately discard the data, a bit like /dev/null
12#[derive(Debug)]
13pub struct EmptyOutboard {
14    /// tree defining the geometry
15    pub tree: BaoTree,
16    /// root hash
17    pub root: blake3::Hash,
18}
19
20impl crate::io::sync::Outboard for EmptyOutboard {
21    fn root(&self) -> blake3::Hash {
22        self.root
23    }
24    fn tree(&self) -> BaoTree {
25        self.tree
26    }
27    fn load(&self, node: TreeNode) -> io::Result<Option<(blake3::Hash, blake3::Hash)>> {
28        Ok(if self.tree.is_relevant_for_outboard(node) {
29            // behave as if it was an outboard file filled with 0s
30            Some((blake3::Hash::from([0; 32]), blake3::Hash::from([0; 32])))
31        } else {
32            None
33        })
34    }
35}
36
37#[cfg(feature = "tokio_fsm")]
38impl crate::io::fsm::Outboard for EmptyOutboard {
39    fn root(&self) -> blake3::Hash {
40        self.root
41    }
42    fn tree(&self) -> BaoTree {
43        self.tree
44    }
45    async fn load(&mut self, node: TreeNode) -> io::Result<Option<(blake3::Hash, blake3::Hash)>> {
46        Ok(if self.tree.is_relevant_for_outboard(node) {
47            // behave as if it was an outboard file filled with 0s
48            Some((blake3::Hash::from([0; 32]), blake3::Hash::from([0; 32])))
49        } else {
50            None
51        })
52    }
53}
54
55impl crate::io::sync::OutboardMut for EmptyOutboard {
56    fn save(&mut self, node: TreeNode, _pair: &(blake3::Hash, blake3::Hash)) -> io::Result<()> {
57        if self.tree.is_relevant_for_outboard(node) {
58            Ok(())
59        } else {
60            Err(io::Error::new(
61                io::ErrorKind::InvalidInput,
62                "invalid node for this outboard",
63            ))
64        }
65    }
66
67    fn sync(&mut self) -> io::Result<()> {
68        Ok(())
69    }
70}
71
72#[cfg(feature = "tokio_fsm")]
73impl crate::io::fsm::OutboardMut for EmptyOutboard {
74    async fn save(
75        &mut self,
76        node: TreeNode,
77        _pair: &(blake3::Hash, blake3::Hash),
78    ) -> io::Result<()> {
79        if self.tree.is_relevant_for_outboard(node) {
80            Ok(())
81        } else {
82            Err(io::Error::new(
83                io::ErrorKind::InvalidInput,
84                "invalid node for this outboard",
85            ))
86        }
87    }
88
89    async fn sync(&mut self) -> io::Result<()> {
90        Ok(())
91    }
92}
93
94/// A generic outboard in pre order
95///
96/// All fields are public, so an outboard does not enforce any invariants.
97/// This is necessary since we want outboards to exist in an incomplete state
98/// where data does not match the root hash.
99///
100/// Caution: unlike the outboard implementation in the bao crate, this
101/// implementation does not assume an 8 byte size prefix.
102#[derive(Debug, Clone)]
103pub struct PreOrderOutboard<D = Vec<u8>> {
104    /// root hash
105    pub root: blake3::Hash,
106    /// tree defining the data
107    pub tree: BaoTree,
108    /// hashes with length prefix
109    pub data: D,
110}
111
112impl<R: Default> Default for PreOrderOutboard<R> {
113    fn default() -> Self {
114        Self {
115            root: blake3::hash(&[]),
116            tree: BaoTree::new(0, BlockSize::ZERO),
117            data: Default::default(),
118        }
119    }
120}
121
122/// A generic outboard in post order
123///
124/// All fields are public, so an outboard does not enforce any invariants.
125/// This is necessary since we want outboards to exist in an incomplete state
126/// where data does not match the root hash.
127#[derive(Debug, Clone)]
128pub struct PostOrderOutboard<D = Vec<u8>> {
129    /// root hash
130    pub root: blake3::Hash,
131    /// tree defining the data
132    pub tree: BaoTree,
133    /// hashes with length prefix
134    pub data: D,
135}
136
137impl<D: Default> Default for PostOrderOutboard<D> {
138    fn default() -> Self {
139        Self {
140            root: blake3::hash(&[]),
141            tree: BaoTree::new(0, BlockSize::ZERO),
142            data: Default::default(),
143        }
144    }
145}
146
147/// A post order outboard that is optimized for memory storage.
148///
149/// The [PostOrderOutboard] will work just fine using e.g. a [`Vec<u8>`] as storage.
150/// However, it will not work for types such as [bytes::Bytes] or [bytes::BytesMut]
151/// that do not implement the io traits.
152///
153/// The traits are implemented for fixed size slices or mutable slices, so
154/// unlike the [PostOrderOutboard], you must make sure that the data is already
155/// the right size.
156#[derive(Debug, Clone, PartialEq, Eq)]
157pub struct PostOrderMemOutboard<T = Vec<u8>> {
158    /// root hash
159    pub root: blake3::Hash,
160    /// tree defining the data
161    pub tree: BaoTree,
162    /// hashes without length suffix
163    pub data: T,
164}
165
166impl<T: Default> Default for PostOrderMemOutboard<T> {
167    fn default() -> Self {
168        Self {
169            root: blake3::hash(&[]),
170            tree: BaoTree::new(0, BlockSize::ZERO),
171            data: Default::default(),
172        }
173    }
174}
175
176impl PostOrderMemOutboard {
177    /// Create a new outboard from `data` and a `block_size`.
178    ///
179    /// This will hash the data and create an outboard.
180    ///
181    /// It is just a shortcut that calls [crate::io::sync::outboard_post_order].
182    pub fn create(data: impl AsRef<[u8]>, block_size: BlockSize) -> Self {
183        let data = data.as_ref();
184        let size = data.len() as u64;
185        let tree = BaoTree::new(size, block_size);
186        let mut outboard = Vec::with_capacity(tree.outboard_size().try_into().unwrap());
187        let root = crate::io::sync::outboard_post_order(data, tree, &mut outboard).unwrap();
188        Self {
189            root,
190            tree,
191            data: outboard,
192        }
193    }
194
195    /// returns the outboard data, with the length suffix.
196    pub fn into_inner_with_suffix(self) -> Vec<u8> {
197        let mut res = self.data;
198        res.extend_from_slice(self.tree.size.to_le_bytes().as_slice());
199        res
200    }
201}
202
203impl<T> PostOrderMemOutboard<T> {
204    /// Map the outboard data to a new type.
205    pub fn map_data<F, U>(self, f: F) -> PostOrderMemOutboard<U>
206    where
207        F: FnOnce(T) -> U,
208        U: AsRef<[u8]>,
209    {
210        PostOrderMemOutboard {
211            root: self.root,
212            tree: self.tree,
213            data: f(self.data),
214        }
215    }
216
217    /// Flip the outboard to pre order.
218    pub fn flip(&self) -> PreOrderMemOutboard
219    where
220        T: AsRef<[u8]>,
221    {
222        let mut target = PreOrderMemOutboard {
223            root: self.root,
224            tree: self.tree,
225            data: vec![0; self.tree.outboard_size().try_into().unwrap()],
226        };
227        crate::io::sync::copy(self, &mut target).unwrap();
228        target
229    }
230}
231
232impl<T: AsRef<[u8]>> crate::io::sync::Outboard for PostOrderMemOutboard<T> {
233    fn root(&self) -> blake3::Hash {
234        self.root
235    }
236    fn tree(&self) -> BaoTree {
237        self.tree
238    }
239    fn load(&self, node: TreeNode) -> io::Result<Option<(blake3::Hash, blake3::Hash)>> {
240        Ok(load_post(&self.tree, self.data.as_ref(), node))
241    }
242}
243
244#[cfg(feature = "tokio_fsm")]
245impl<T: AsRef<[u8]>> crate::io::fsm::Outboard for PostOrderMemOutboard<T> {
246    fn root(&self) -> blake3::Hash {
247        self.root
248    }
249    fn tree(&self) -> BaoTree {
250        self.tree
251    }
252    async fn load(&mut self, node: TreeNode) -> io::Result<Option<(blake3::Hash, blake3::Hash)>> {
253        Ok(load_post(&self.tree, self.data.as_ref(), node))
254    }
255}
256
257impl<T: AsMut<[u8]>> crate::io::sync::OutboardMut for PostOrderMemOutboard<T> {
258    fn save(&mut self, node: TreeNode, pair: &(blake3::Hash, blake3::Hash)) -> io::Result<()> {
259        match self.tree.post_order_offset(node) {
260            Some(offset) => {
261                let offset = usize::try_from(offset.value() * 64).unwrap();
262                let data = self.data.as_mut();
263                data[offset..offset + 32].copy_from_slice(pair.0.as_bytes());
264                data[offset + 32..offset + 64].copy_from_slice(pair.1.as_bytes());
265                Ok(())
266            }
267            None => Err(io::Error::new(
268                io::ErrorKind::InvalidInput,
269                "invalid node for this outboard",
270            )),
271        }
272    }
273
274    fn sync(&mut self) -> io::Result<()> {
275        Ok(())
276    }
277}
278
279#[cfg(feature = "tokio_fsm")]
280impl<T: AsMut<[u8]>> crate::io::fsm::OutboardMut for PostOrderMemOutboard<T> {
281    async fn save(
282        &mut self,
283        node: TreeNode,
284        pair: &(blake3::Hash, blake3::Hash),
285    ) -> io::Result<()> {
286        match self.tree.post_order_offset(node) {
287            Some(offset) => {
288                let offset = usize::try_from(offset.value() * 64).unwrap();
289                let data = self.data.as_mut();
290                data[offset..offset + 32].copy_from_slice(pair.0.as_bytes());
291                data[offset + 32..offset + 64].copy_from_slice(pair.1.as_bytes());
292                Ok(())
293            }
294            None => Err(io::Error::new(
295                io::ErrorKind::InvalidInput,
296                "invalid node for this outboard",
297            )),
298        }
299    }
300
301    async fn sync(&mut self) -> io::Result<()> {
302        Ok(())
303    }
304}
305
306fn load_raw_post_mem(tree: &BaoTree, data: &[u8], node: TreeNode) -> Option<[u8; 64]> {
307    let offset = tree.post_order_offset(node)?.value();
308    let offset = usize::try_from(offset * 64).unwrap();
309    let slice = &data[offset..offset + 64];
310    Some(slice.try_into().unwrap())
311}
312
313fn load_post(tree: &BaoTree, data: &[u8], node: TreeNode) -> Option<(blake3::Hash, blake3::Hash)> {
314    load_raw_post_mem(tree, data, node).map(parse_hash_pair)
315}
316
317/// A pre order outboard that is optimized for memory storage.
318///
319/// The traits are implemented for fixed size slices or mutable slices, so you
320/// must make sure that the data is already the right size.
321#[derive(Debug, Clone, PartialEq, Eq)]
322pub struct PreOrderMemOutboard<T = Vec<u8>> {
323    /// root hash
324    pub root: blake3::Hash,
325    /// tree defining the data
326    pub tree: BaoTree,
327    /// hashes with length prefix
328    pub data: T,
329}
330
331impl<T: Default> Default for PreOrderMemOutboard<T> {
332    fn default() -> Self {
333        Self {
334            root: blake3::hash(&[]),
335            tree: BaoTree::new(0, BlockSize::ZERO),
336            data: Default::default(),
337        }
338    }
339}
340
341impl PreOrderMemOutboard {
342    /// returns the outboard data, with the length prefix added.
343    pub fn into_inner_with_prefix(self) -> Vec<u8> {
344        let mut res = self.data;
345        res.splice(0..0, self.tree.size.to_le_bytes());
346        res
347    }
348
349    /// Create a new outboard from `data` and a `block_size`.
350    ///
351    /// This will hash the data and create an outboard
352    pub fn create(data: impl AsRef<[u8]>, block_size: BlockSize) -> Self {
353        let data = data.as_ref();
354        let size = data.len() as u64;
355        let tree = BaoTree::new(size, block_size);
356        // the outboard impl for PreOrderMemOutboard requires just AsMut<[u8]>,
357        // so the data must already be the right size.
358        let outboard = vec![0u8; tree.outboard_size().try_into().unwrap()];
359        let mut res = Self {
360            root: blake3::Hash::from([0; 32]),
361            tree,
362            data: outboard,
363        };
364        let root = crate::io::sync::outboard(data, tree, &mut res).unwrap();
365        res.root = root;
366        res
367    }
368}
369
370impl<T> PreOrderMemOutboard<T> {
371    /// Map the outboard data to a new type.
372    pub fn map_data<F, U>(self, f: F) -> PreOrderMemOutboard<U>
373    where
374        F: FnOnce(T) -> U,
375        U: AsRef<[u8]>,
376    {
377        PreOrderMemOutboard {
378            root: self.root,
379            tree: self.tree,
380            data: f(self.data),
381        }
382    }
383
384    /// Flip the outboard to a post order outboard.
385    pub fn flip(&self) -> PostOrderMemOutboard
386    where
387        T: AsRef<[u8]>,
388    {
389        let mut target = PostOrderMemOutboard {
390            root: self.root,
391            tree: self.tree,
392            data: vec![0; self.tree.outboard_size().try_into().unwrap()],
393        };
394        crate::io::sync::copy(self, &mut target).unwrap();
395        target
396    }
397}
398
399impl<T: AsRef<[u8]>> crate::io::sync::Outboard for PreOrderMemOutboard<T> {
400    fn root(&self) -> blake3::Hash {
401        self.root
402    }
403    fn tree(&self) -> BaoTree {
404        self.tree
405    }
406    fn load(&self, node: TreeNode) -> io::Result<Option<(blake3::Hash, blake3::Hash)>> {
407        Ok(load_pre(&self.tree, self.data.as_ref(), node))
408    }
409}
410
411impl<T: AsMut<[u8]>> crate::io::sync::OutboardMut for PreOrderMemOutboard<T> {
412    fn save(&mut self, node: TreeNode, pair: &(blake3::Hash, blake3::Hash)) -> io::Result<()> {
413        match self.tree.pre_order_offset(node) {
414            Some(offset) => {
415                let offset_u64 = offset * 64;
416                let offset = usize::try_from(offset_u64).unwrap();
417                let data = self.data.as_mut();
418                data[offset..offset + 32].copy_from_slice(pair.0.as_bytes());
419                data[offset + 32..offset + 64].copy_from_slice(pair.1.as_bytes());
420                Ok(())
421            }
422            None => Err(io::Error::new(
423                io::ErrorKind::InvalidInput,
424                "invalid node for this outboard",
425            )),
426        }
427    }
428
429    fn sync(&mut self) -> io::Result<()> {
430        Ok(())
431    }
432}
433
434#[cfg(feature = "tokio_fsm")]
435impl<T: AsRef<[u8]>> crate::io::fsm::Outboard for PreOrderMemOutboard<T> {
436    fn root(&self) -> blake3::Hash {
437        self.root
438    }
439    fn tree(&self) -> BaoTree {
440        self.tree
441    }
442    async fn load(&mut self, node: TreeNode) -> io::Result<Option<(blake3::Hash, blake3::Hash)>> {
443        Ok(load_raw_pre_mem(&self.tree, self.data.as_ref(), node).map(parse_hash_pair))
444    }
445}
446
447#[cfg(feature = "tokio_fsm")]
448impl<T: AsMut<[u8]>> crate::io::fsm::OutboardMut for PreOrderMemOutboard<T> {
449    async fn save(
450        &mut self,
451        node: TreeNode,
452        pair: &(blake3::Hash, blake3::Hash),
453    ) -> io::Result<()> {
454        match self.tree.pre_order_offset(node) {
455            Some(offset) => {
456                let offset_u64 = offset * 64;
457                let offset = usize::try_from(offset_u64).unwrap();
458                let data = self.data.as_mut();
459                data[offset..offset + 32].copy_from_slice(pair.0.as_bytes());
460                data[offset + 32..offset + 64].copy_from_slice(pair.1.as_bytes());
461                Ok(())
462            }
463            None => Err(io::Error::new(
464                io::ErrorKind::InvalidInput,
465                "invalid node for this outboard",
466            )),
467        }
468    }
469
470    async fn sync(&mut self) -> io::Result<()> {
471        Ok(())
472    }
473}
474
475fn load_raw_pre_mem(tree: &BaoTree, data: &[u8], node: TreeNode) -> Option<[u8; 64]> {
476    // this is a bit slow because pre_order_offset uses a loop.
477    // pretty sure there is a way to write it as a single expression if you spend the time.
478    // but profiling still has this in the nanosecond range, so this is unlikely to be a
479    // bottleneck.
480    let offset = tree.pre_order_offset(node)?;
481    let offset = usize::try_from(offset * 64).unwrap();
482    let slice = &data[offset..offset + 64];
483    Some(slice.try_into().unwrap())
484}
485
486fn load_pre(tree: &BaoTree, data: &[u8], node: TreeNode) -> Option<(blake3::Hash, blake3::Hash)> {
487    load_raw_pre_mem(tree, data, node).map(parse_hash_pair)
488}
489
490pub(crate) fn parse_hash_pair(buf: [u8; 64]) -> (blake3::Hash, blake3::Hash) {
491    let l_hash = blake3::Hash::from(<[u8; 32]>::try_from(&buf[..32]).unwrap());
492    let r_hash = blake3::Hash::from(<[u8; 32]>::try_from(&buf[32..]).unwrap());
493    (l_hash, r_hash)
494}
bao_tree/io/outboard.rs

bao_tree/io/
outboard.rs
