merkle_search_tree/diff/
page_range_snapshot.rs

1use super::PageRange;
2use crate::digest::PageDigest;
3
4/// An owned point-in-time snapshot of the [`PageRange`] returned from a call to
5/// [`MerkleSearchTree::serialise_page_ranges()`].
6///
7/// Generating a [`PageRangeSnapshot`] from a set of [`PageRange`] instances
8/// clones all the bounding keys in each [`PageRange`], and therefore can only
9/// be generated if the key type `K` implements [`Clone`].
10///
11/// ```
12/// # use merkle_search_tree::{*, diff::*};
13/// #
14/// let mut t = MerkleSearchTree::default();
15/// t.upsert("bananas", &42);
16///
17/// // Rehash the tree before generating the page ranges
18/// let _ = t.root_hash();
19///
20/// // Generate the hashes & page ranges, immutably borrowing the tree
21/// let ranges = t.serialise_page_ranges().unwrap();
22///
23/// // Obtain an owned PageRangeSnapshot from the borrowed PageRange, in turn
24/// // releasing the immutable reference to the tree.
25/// let snap = PageRangeSnapshot::from(ranges);
26///
27/// // The tree is now mutable again.
28/// t.upsert("platanos", &42);
29/// ```
30///
31/// A [`PageRangeSnapshot`] can also be generated from owned key values using
32/// the [`OwnedPageRange`] type to eliminate clones where unnecessary.
33///
34/// [`MerkleSearchTree::serialise_page_ranges()`]:
35///     crate::MerkleSearchTree::serialise_page_ranges
36#[derive(Debug, Clone, PartialEq)]
37pub struct PageRangeSnapshot<K>(Vec<OwnedPageRange<K>>);
38
39impl<K> PageRangeSnapshot<K> {
40    /// Return an iterator of [`PageRange`] from the snapshot content.
41    pub fn iter(&self) -> impl ExactSizeIterator<Item = PageRange<'_, K>>
42    where
43        K: PartialOrd,
44    {
45        self.0
46            .iter()
47            .map(|v| PageRange::new(&v.start, &v.end, v.hash.clone()))
48    }
49}
50
51impl<'a, K> From<Vec<PageRange<'a, K>>> for PageRangeSnapshot<K>
52where
53    K: Clone,
54{
55    fn from(value: Vec<PageRange<'a, K>>) -> Self {
56        value.into_iter().collect()
57    }
58}
59
60impl<'a, K> FromIterator<PageRange<'a, K>> for PageRangeSnapshot<K>
61where
62    K: Clone + 'a,
63{
64    fn from_iter<T: IntoIterator<Item = PageRange<'a, K>>>(iter: T) -> Self {
65        Self(iter.into_iter().map(OwnedPageRange::from).collect())
66    }
67}
68
69impl<K> From<Vec<OwnedPageRange<K>>> for PageRangeSnapshot<K> {
70    fn from(value: Vec<OwnedPageRange<K>>) -> Self {
71        value.into_iter().collect()
72    }
73}
74
75impl<K> FromIterator<OwnedPageRange<K>> for PageRangeSnapshot<K> {
76    fn from_iter<T: IntoIterator<Item = OwnedPageRange<K>>>(iter: T) -> Self {
77        Self(iter.into_iter().map(OwnedPageRange::from).collect())
78    }
79}
80
81/// An owned representation of a [`PageRange`] containing an owned key interval
82/// & page hash.
83///
84/// This type can be used to construct a [`PageRangeSnapshot`] from owned values
85/// (eliminating key/hash clones).
86#[derive(Debug, Clone, PartialEq, Eq)]
87pub struct OwnedPageRange<K> {
88    start: K,
89    end: K,
90    hash: PageDigest,
91}
92
93impl<K> OwnedPageRange<K>
94where
95    K: PartialOrd,
96{
97    /// Initialise a new [`OwnedPageRange`] for the given inclusive key
98    /// interval, and page hash covering the key range.
99    ///
100    /// # Panics
101    ///
102    /// If `start` is greater than `end`, this method panics.
103    pub fn new(start: K, end: K, hash: PageDigest) -> Self {
104        assert!(start <= end);
105        Self { start, end, hash }
106    }
107}
108
109impl<'a, K> From<PageRange<'a, K>> for OwnedPageRange<K>
110where
111    K: Clone,
112{
113    fn from(v: PageRange<'a, K>) -> Self {
114        Self {
115            start: v.start().clone(),
116            end: v.end().clone(),
117            hash: v.into_hash(),
118        }
119    }
120}
121
122#[cfg(test)]
123mod tests {
124    use assert_matches::assert_matches;
125
126    use super::*;
127    use crate::{diff::diff, MerkleSearchTree};
128
129    #[test]
130    fn test_owned_usage() {
131        let mut a = MerkleSearchTree::default();
132        let mut b = MerkleSearchTree::default();
133
134        a.upsert("bananas", &42);
135        b.upsert("bananas", &24);
136
137        // Rehash the tree
138        let _ = a.root_hash();
139        let _ = b.root_hash();
140
141        // Generate owned snapshots from the borrowed page ranges
142        let snap_a = PageRangeSnapshot::from(a.serialise_page_ranges().unwrap());
143        let snap_b = PageRangeSnapshot::from(b.serialise_page_ranges().unwrap());
144
145        // Tree should be mutable whilst snapshots are in scope
146        a.upsert("bananas", &13);
147        b.upsert("bananas", &13);
148
149        // Which should be usable for diff generation (and not reflect the
150        // updated state since the trees were mutated).
151        assert_matches!(diff(snap_a.iter(), snap_b.iter()).as_slice(), [range] => {
152            assert_eq!(range.start(), &"bananas");
153            assert_eq!(range.end(), &"bananas");
154        });
155    }
156
157    #[test]
158    fn test_collect_equivalence_refs() {
159        let a1 = vec![
160            PageRange::new(
161                &"a",
162                &"b",
163                PageDigest::new([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]),
164            ),
165            PageRange::new(
166                &"c",
167                &"d",
168                PageDigest::new([2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]),
169            ),
170        ];
171
172        let a2 = a1.clone().into_iter().collect::<PageRangeSnapshot<_>>();
173        let a1 = PageRangeSnapshot::from(a1);
174
175        assert_eq!(a1, a2)
176    }
177
178    #[test]
179    fn test_collect_equivalence_owned() {
180        let a1 = vec![
181            OwnedPageRange::new(
182                "a",
183                "b",
184                PageDigest::new([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]),
185            ),
186            OwnedPageRange::new(
187                "c",
188                "d",
189                PageDigest::new([2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]),
190            ),
191        ];
192
193        let a2 = a1.clone().into_iter().collect::<PageRangeSnapshot<_>>();
194        let a1 = PageRangeSnapshot::from(a1);
195
196        assert_eq!(a1, a2)
197    }
198
199    #[test]
200    fn test_owned_ref_page_equivalence() {
201        let ref_pages = [
202            PageRange::new(
203                &"a",
204                &"b",
205                PageDigest::new([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]),
206            ),
207            PageRange::new(
208                &"c",
209                &"d",
210                PageDigest::new([2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]),
211            ),
212        ];
213
214        let owned_pages = [
215            OwnedPageRange::new(
216                "a",
217                "b",
218                PageDigest::new([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]),
219            ),
220            OwnedPageRange::new(
221                "c",
222                "d",
223                PageDigest::new([2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]),
224            ),
225        ];
226
227        let ref_pages = ref_pages.into_iter().collect::<PageRangeSnapshot<_>>();
228        let owned_pages = owned_pages.into_iter().collect::<PageRangeSnapshot<_>>();
229
230        assert_eq!(ref_pages, owned_pages);
231    }
232
233    #[test]
234    fn test_exact_size_iter() {
235        let pages = [
236            PageRange::new(
237                &"a",
238                &"b",
239                PageDigest::new([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]),
240            ),
241            PageRange::new(
242                &"c",
243                &"d",
244                PageDigest::new([2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]),
245            ),
246        ];
247
248        let pages = pages.into_iter().collect::<PageRangeSnapshot<_>>();
249        assert_eq!(pages.iter().len(), 2);
250    }
251}
merkle_search_tree/diff/page_range_snapshot.rs

merkle_search_tree/diff/
page_range_snapshot.rs
