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}