merkle_search_tree/diff/
page_range.rs

1use std::fmt::Display;
2
3use crate::{digest::PageDigest, Page};
4
5/// A serialised representation of the range of keys contained within the
6/// sub-tree rooted at a given [`Page`], and the associated [`PageDigest`].
7///
8/// A [`PageRange`] contains all the information needed to perform a tree
9/// difference calculation, used as the input to the [`diff()`] function.
10///
11/// The contents of this type can be serialised and transmitted over the
12/// network, and reconstructed by the receiver by calling [`PageRange::new()`]
13/// with the serialised values.
14///
15/// # Exchanging Between Peers
16///
17/// Exchange the ordered sets of [`PageRange`] between peers by serialising
18/// their content, accessed through the accessor methods:
19///
20/// ```rust
21/// # use std::ops::Deref;
22/// # use merkle_search_tree::{*, diff::PageRange};
23/// #
24/// /// A network wire representation used by the application.
25/// struct NetworkPage {
26///     start_bounds: String,
27///     end_bounds: String,
28///     hash: [u8; 16],
29/// }
30///
31/// let mut t = MerkleSearchTree::default();
32/// t.upsert("bananas".to_string(), &"platanos".to_string());
33/// t.root_hash();
34///
35/// let network_request: Vec<NetworkPage> = t
36///     .serialise_page_ranges()
37///     .unwrap()
38///     .into_iter()
39///     .map(|page| NetworkPage {
40///         start_bounds: page.start().clone(),
41///         end_bounds: page.end().clone(),
42///         hash: *page.hash().as_bytes(),
43///     })
44///     .collect();
45///
46/// // Send network_request to a peer over the network
47/// ```
48///
49/// And reconstruct the [`PageRange`] on the receiver:
50///
51/// ```rust
52/// # use merkle_search_tree::diff::PageRange;
53/// # use merkle_search_tree::digest::*;
54/// #
55/// # struct NetworkPage {
56/// #     start_bounds: String,
57/// #     end_bounds: String,
58/// #     hash: [u8; 16],
59/// # }
60/// #
61/// # let network_request: Vec<NetworkPage> = vec![];
62/// // Receive network_request from a peer over the network
63///
64/// // PageRange construction is zero-copy for the page keys, borrowing the keys
65/// // from the underlying network request.
66/// let page_refs = network_request
67///     .iter()
68///     .map(|p| {
69///         // If this request is coming from an untrusted source, validate that
70///         // start <= end to avoid the PageRange constructor panic.
71///         PageRange::new(&p.start_bounds, &p.end_bounds, PageDigest::new(p.hash))
72///     })
73///     .collect::<Vec<_>>();
74///
75/// // Feed page_refs into diff()
76/// ```
77///
78/// # Borrowed vs. Owned
79///
80/// A [`PageRange`] borrows the keys from the tree to avoid unnecessary clones,
81/// retaining an immutable reference to the tree.
82///
83/// If an owned / long-lived set of [`PageRange`] is desired (avoiding the
84/// immutable reference to the tree), generate a [`PageRangeSnapshot`] from the
85/// set of [`PageRange`].
86///
87/// [`diff()`]: crate::diff::diff
88/// [`PageRangeSnapshot`]: crate::diff::PageRangeSnapshot
89#[derive(Debug, PartialEq)]
90pub struct PageRange<'a, K> {
91    /// The inclusive start & end key bounds of this range.
92    start: &'a K,
93    end: &'a K,
94
95    /// The hash of this page, and the sub-tree rooted at it.
96    hash: PageDigest,
97}
98
99impl<'a, K> Display for PageRange<'a, K>
100where
101    K: Display,
102{
103    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
104        f.write_fmt(format_args!("({}, {})", self.start, self.end))
105    }
106}
107
108impl<'a, K> Clone for PageRange<'a, K> {
109    fn clone(&self) -> Self {
110        Self {
111            start: self.start,
112            end: self.end,
113            hash: self.hash.clone(),
114        }
115    }
116}
117
118impl<'a, const N: usize, K> From<&'a Page<N, K>> for PageRange<'a, K> {
119    #[inline(always)]
120    fn from(page: &'a Page<N, K>) -> Self {
121        PageRange {
122            start: page.min_subtree_key(),
123            end: page.max_subtree_key(),
124            hash: page
125                .hash()
126                .expect("page visitor requires prior hash regeneration")
127                .clone(),
128        }
129    }
130}
131
132impl<'a, K> PageRange<'a, K> {
133    /// Construct a [`PageRange`] for the given key interval and [`PageDigest`].
134    ///
135    /// # Panics
136    ///
137    /// If `start` is greater than `end`, this method panics.
138    pub fn new(start: &'a K, end: &'a K, hash: PageDigest) -> Self
139    where
140        K: PartialOrd,
141    {
142        assert!(start <= end);
143        Self { start, end, hash }
144    }
145
146    /// Returns the inclusive start of this [`PageRange`].
147    pub fn start(&self) -> &'a K {
148        self.start
149    }
150
151    /// Returns the inclusive end of this [`PageRange`]
152    pub fn end(&self) -> &'a K {
153        self.end
154    }
155
156    /// Returns true if `self` is a superset of `other` (not a strict superset -
157    /// equal ranges are treated as supersets of each other).
158    pub(crate) fn is_superset_of(&self, other: &Self) -> bool
159    where
160        K: PartialOrd,
161    {
162        self.start <= other.start && other.end <= self.end
163    }
164
165    /// Returns the [`PageDigest`] of this page, representing the content of the
166    /// page and all pages within the sub-tree rooted at it.
167    pub fn hash(&self) -> &PageDigest {
168        &self.hash
169    }
170
171    /// Consume this [`PageRange`], returning the [`PageDigest`] that covers the
172    /// subtree rooted at this page.
173    pub fn into_hash(self) -> PageDigest {
174        self.hash
175    }
176}
177
178#[cfg(test)]
179mod tests {
180    use super::*;
181    use crate::{digest::Digest, MerkleSearchTree};
182
183    /// Ensure the public API allows for serialisation & deserialisation of
184    /// [`PageRange`].
185    #[test]
186    fn test_round_trip_api() {
187        struct NetworkPage {
188            start_bounds: String,
189            end_bounds: String,
190            hash: [u8; 16],
191        }
192
193        let mut t = MerkleSearchTree::default();
194        t.upsert("bananas".to_string(), &"platanos".to_string());
195        t.root_hash();
196
197        let page_ranges = t.serialise_page_ranges().unwrap();
198
199        // Serialise
200        let network_pages: Vec<NetworkPage> = page_ranges
201            .iter()
202            .map(|v| NetworkPage {
203                start_bounds: v.start().clone(),
204                end_bounds: v.end().clone(),
205                hash: *v.hash().as_bytes(),
206            })
207            .collect();
208
209        // Deserialise
210        let got: Vec<PageRange<'_, String>> = network_pages
211            .iter()
212            .map(|v| PageRange::new(&v.start_bounds, &v.end_bounds, PageDigest::new(v.hash)))
213            .collect();
214
215        assert_eq!(page_ranges, got);
216    }
217
218    #[test]
219    #[should_panic(expected = "start <= end")]
220    fn test_start_gt_end_panic() {
221        let _p = PageRange::new(
222            &42,
223            &24,
224            PageDigest::from(Digest::new([
225                1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
226            ])),
227        );
228    }
229}