linera_views/
common.rs

1// Copyright (c) Zefchain Labs, Inc.
2// SPDX-License-Identifier: Apache-2.0
3
4//! This provides some common code for the linera-views.
5
6use std::{
7    collections::BTreeSet,
8    ops::{
9        Bound,
10        Bound::{Excluded, Included, Unbounded},
11    },
12    slice::ChunksExact,
13};
14
15use itertools::Either;
16use serde::de::DeserializeOwned;
17
18use crate::ViewError;
19
20type HasherOutputSize = <sha3::Sha3_256 as sha3::digest::OutputSizeUser>::OutputSize;
21#[doc(hidden)]
22#[allow(deprecated)]
23pub type HasherOutput = generic_array::GenericArray<u8, HasherOutputSize>;
24
25#[derive(Clone, Debug)]
26/// An update, for example to a view.
27pub enum Update<T> {
28    /// The entry is removed.
29    Removed,
30    /// The entry is set to the following.
31    Set(T),
32}
33
34#[derive(Clone, Debug)]
35pub(crate) struct DeletionSet {
36    pub(crate) delete_storage_first: bool,
37    pub(crate) deleted_prefixes: BTreeSet<Vec<u8>>,
38}
39
40impl DeletionSet {
41    pub(crate) fn new() -> Self {
42        Self {
43            delete_storage_first: false,
44            deleted_prefixes: BTreeSet::new(),
45        }
46    }
47
48    pub(crate) fn clear(&mut self) {
49        self.delete_storage_first = true;
50        self.deleted_prefixes.clear();
51    }
52
53    pub(crate) fn rollback(&mut self) {
54        self.delete_storage_first = false;
55        self.deleted_prefixes.clear();
56    }
57
58    pub(crate) fn contains_prefix_of(&self, index: &[u8]) -> bool {
59        self.delete_storage_first || contains_prefix_of(&self.deleted_prefixes, index)
60    }
61
62    pub(crate) fn has_pending_changes(&self) -> bool {
63        self.delete_storage_first || !self.deleted_prefixes.is_empty()
64    }
65
66    pub(crate) fn insert_key_prefix(&mut self, key_prefix: Vec<u8>) {
67        if !self.delete_storage_first {
68            insert_key_prefix(&mut self.deleted_prefixes, key_prefix);
69        }
70    }
71}
72
73/// When wanting to find the entries in a `BTreeMap` with a specific prefix,
74/// one option is to iterate over all keys. Another is to select an interval
75/// that represents exactly the keys having that prefix. Which fortunately
76/// is possible with the way the comparison operators for vectors are built.
77///
78/// The statement is that `p` is a prefix of `v` if and only if `p <= v < upper_bound(p)`.
79pub(crate) fn get_upper_bound_option(key_prefix: &[u8]) -> Option<Vec<u8>> {
80    let len = key_prefix.len();
81    for i in (0..len).rev() {
82        if key_prefix[i] < u8::MAX {
83            let mut upper_bound = key_prefix[0..=i].to_vec();
84            upper_bound[i] += 1;
85            return Some(upper_bound);
86        }
87    }
88    None
89}
90
91/// The upper bound that can be used in ranges when accessing
92/// a container. That is a vector `v` is a prefix of `p` if and only if
93/// `v` belongs to the interval `(Included(p), get_upper_bound(p))`.
94pub(crate) fn get_upper_bound(key_prefix: &[u8]) -> Bound<Vec<u8>> {
95    match get_upper_bound_option(key_prefix) {
96        None => Unbounded,
97        Some(upper_bound) => Excluded(upper_bound),
98    }
99}
100
101/// Computes an interval so that a vector has `key_prefix` as a prefix
102/// if and only if it belongs to the range.
103pub(crate) fn get_key_range_for_prefix(key_prefix: Vec<u8>) -> (Bound<Vec<u8>>, Bound<Vec<u8>>) {
104    let upper_bound = get_upper_bound(&key_prefix);
105    (Included(key_prefix), upper_bound)
106}
107
108/// Deserializes an optional vector of `u8`
109pub fn from_bytes_option<V: DeserializeOwned>(
110    key_opt: &Option<Vec<u8>>,
111) -> Result<Option<V>, bcs::Error> {
112    if let Some(bytes) = key_opt {
113        Ok(Some(bcs::from_bytes(bytes)?))
114    } else {
115        Ok(None)
116    }
117}
118
119pub(crate) fn from_bytes_option_or_default<V: DeserializeOwned + Default>(
120    key_opt: &Option<Vec<u8>>,
121) -> Result<V, bcs::Error> {
122    if let Some(bytes) = key_opt {
123        Ok(bcs::from_bytes(bytes)?)
124    } else {
125        Ok(V::default())
126    }
127}
128
129/// `SuffixClosedSetIterator` iterates over the entries of a container ordered
130/// lexicographically.
131///
132/// The function call `find_lower_bound(val)` returns a `Some(x)` where `x` is the highest
133/// entry such that `x <= val` for the lexicographic order. If none exists then None is
134/// returned. The function calls have to be done with increasing `val`.
135///
136/// The function call `find_key(val)` tests whether there exists a prefix p in the
137/// set of vectors such that p is a prefix of val.
138pub(crate) struct SuffixClosedSetIterator<'a, I> {
139    prefix_len: usize,
140    previous: Option<&'a Vec<u8>>,
141    current: Option<&'a Vec<u8>>,
142    iter: I,
143}
144
145impl<'a, I> SuffixClosedSetIterator<'a, I>
146where
147    I: Iterator<Item = &'a Vec<u8>>,
148{
149    pub(crate) fn new(prefix_len: usize, mut iter: I) -> Self {
150        let previous = None;
151        let current = iter.next();
152        Self {
153            prefix_len,
154            previous,
155            current,
156            iter,
157        }
158    }
159
160    pub(crate) fn find_lower_bound(&mut self, val: &[u8]) -> Option<&'a Vec<u8>> {
161        loop {
162            match &self.current {
163                None => {
164                    return self.previous;
165                }
166                Some(x) => {
167                    if &x[self.prefix_len..] > val {
168                        return self.previous;
169                    }
170                }
171            }
172            let current = self.iter.next();
173            self.previous = std::mem::replace(&mut self.current, current);
174        }
175    }
176
177    pub(crate) fn find_key(&mut self, index: &[u8]) -> bool {
178        let lower_bound = self.find_lower_bound(index);
179        match lower_bound {
180            None => false,
181            Some(key_prefix) => index.starts_with(&key_prefix[self.prefix_len..]),
182        }
183    }
184}
185
186pub(crate) fn contains_prefix_of(prefixes: &BTreeSet<Vec<u8>>, key: &[u8]) -> bool {
187    let iter = prefixes.iter();
188    let mut suffix_closed_set = SuffixClosedSetIterator::new(0, iter);
189    suffix_closed_set.find_key(key)
190}
191
192pub(crate) fn insert_key_prefix(prefixes: &mut BTreeSet<Vec<u8>>, prefix: Vec<u8>) {
193    if !contains_prefix_of(prefixes, &prefix) {
194        let key_prefix_list = prefixes
195            .range(get_key_range_for_prefix(prefix.clone()))
196            .map(|x| x.to_vec())
197            .collect::<Vec<_>>();
198        for key in key_prefix_list {
199            prefixes.remove(&key);
200        }
201        prefixes.insert(prefix);
202    }
203}
204
205#[test]
206fn suffix_closed_set_test1_the_lower_bound() {
207    let mut set = BTreeSet::<Vec<u8>>::new();
208    set.insert(vec![4]);
209    set.insert(vec![7]);
210    set.insert(vec![8]);
211    set.insert(vec![10]);
212    set.insert(vec![24]);
213    set.insert(vec![40]);
214
215    let mut suffix_closed_set = SuffixClosedSetIterator::new(0, set.iter());
216    assert_eq!(suffix_closed_set.find_lower_bound(&[3]), None);
217    assert_eq!(
218        suffix_closed_set.find_lower_bound(&[15]),
219        Some(vec![10]).as_ref()
220    );
221    assert_eq!(
222        suffix_closed_set.find_lower_bound(&[17]),
223        Some(vec![10]).as_ref()
224    );
225    assert_eq!(
226        suffix_closed_set.find_lower_bound(&[25]),
227        Some(vec![24]).as_ref()
228    );
229    assert_eq!(
230        suffix_closed_set.find_lower_bound(&[27]),
231        Some(vec![24]).as_ref()
232    );
233    assert_eq!(
234        suffix_closed_set.find_lower_bound(&[42]),
235        Some(vec![40]).as_ref()
236    );
237}
238
239#[test]
240fn suffix_closed_set_test2_find_key() {
241    let mut set = BTreeSet::<Vec<u8>>::new();
242    set.insert(vec![4]);
243    set.insert(vec![0, 3]);
244    set.insert(vec![5]);
245
246    let mut suffix_closed_set = SuffixClosedSetIterator::new(0, set.iter());
247    assert!(!suffix_closed_set.find_key(&[0]));
248    assert!(suffix_closed_set.find_key(&[0, 3]));
249    assert!(suffix_closed_set.find_key(&[0, 3, 4]));
250    assert!(!suffix_closed_set.find_key(&[1]));
251    assert!(suffix_closed_set.find_key(&[4]));
252}
253
254#[test]
255fn suffix_closed_set_test3_find_key_prefix_len() {
256    let mut set = BTreeSet::<Vec<u8>>::new();
257    set.insert(vec![0, 4]);
258    set.insert(vec![0, 3]);
259    set.insert(vec![0, 0, 1]);
260
261    let mut suffix_closed_set = SuffixClosedSetIterator::new(1, set.iter());
262    assert!(!suffix_closed_set.find_key(&[0]));
263    assert!(suffix_closed_set.find_key(&[0, 1]));
264    assert!(suffix_closed_set.find_key(&[0, 1, 4]));
265    assert!(suffix_closed_set.find_key(&[3]));
266    assert!(!suffix_closed_set.find_key(&[5]));
267}
268
269#[test]
270fn insert_key_prefix_test1() {
271    let mut set = BTreeSet::<Vec<u8>>::new();
272    set.insert(vec![0, 4]);
273
274    insert_key_prefix(&mut set, vec![0, 4, 5]);
275    let keys = set.iter().cloned().collect::<Vec<_>>();
276    assert_eq!(keys, vec![vec![0, 4]]);
277}
278
279/// Sometimes we need a serialization that is different from the usual one and
280/// for example preserves order.
281/// `{to/from}_custom_bytes` has to be coherent with the `Borrow` trait.
282pub trait CustomSerialize: Sized {
283    /// Serializes the value
284    fn to_custom_bytes(&self) -> Result<Vec<u8>, ViewError>;
285
286    /// Deserialize the vector
287    fn from_custom_bytes(short_key: &[u8]) -> Result<Self, ViewError>;
288}
289
290impl CustomSerialize for u128 {
291    fn to_custom_bytes(&self) -> Result<Vec<u8>, ViewError> {
292        let mut bytes = bcs::to_bytes(&self)?;
293        bytes.reverse();
294        Ok(bytes)
295    }
296
297    fn from_custom_bytes(bytes: &[u8]) -> Result<Self, ViewError> {
298        let mut bytes = bytes.to_vec();
299        bytes.reverse();
300        let value = bcs::from_bytes(&bytes)?;
301        Ok(value)
302    }
303}
304
305/// This computes the offset of the BCS serialization of a vector.
306/// The formula that should be satisfied is
307/// `serialized_size(vec![v_1, ...., v_n]) = get_uleb128_size(n)`
308///  `+ serialized_size(v_1)? + .... serialized_size(v_n)?`
309pub(crate) const fn get_uleb128_size(len: usize) -> usize {
310    let mut power = 128;
311    let mut expo = 1;
312    while len >= power {
313        power *= 128;
314        expo += 1;
315    }
316    expo
317}
318
319/// Extention trait for slices.
320pub trait SliceExt<T> {
321    /// Same as `chunks_exact` but we allow the `chunk_size` to be zero when the slice is empty.
322    fn chunks_exact_or_repeat(
323        &self,
324        chunk_size: usize,
325    ) -> Either<ChunksExact<'_, T>, std::iter::Repeat<&[T]>>;
326}
327
328impl<T> SliceExt<T> for [T] {
329    fn chunks_exact_or_repeat(
330        &self,
331        chunk_size: usize,
332    ) -> Either<ChunksExact<'_, T>, std::iter::Repeat<&[T]>> {
333        if chunk_size > 0 {
334            Either::Left(self.chunks_exact(chunk_size))
335        } else if self.is_empty() {
336            Either::Right(std::iter::repeat(&[]))
337        } else {
338            panic!("chunk_size must be nonzero unless the slice is empty")
339        }
340    }
341}
342
343#[cfg(test)]
344mod tests {
345    use std::collections::BTreeSet;
346
347    use linera_views::common::CustomSerialize;
348    use rand::Rng;
349
350    #[test]
351    fn test_ordering_serialization() {
352        let mut rng = crate::random::make_deterministic_rng();
353        let n = 1000;
354        let mut set = BTreeSet::new();
355        for _ in 0..n {
356            let val = rng.gen::<u128>();
357            set.insert(val);
358        }
359        let mut vec = Vec::new();
360        for val in set {
361            vec.push(val);
362        }
363        for i in 1..vec.len() {
364            let val1 = vec[i - 1];
365            let val2 = vec[i];
366            assert!(val1 < val2);
367            let vec1 = val1.to_custom_bytes().unwrap();
368            let vec2 = val2.to_custom_bytes().unwrap();
369            assert!(vec1 < vec2);
370            let val_ret1 = u128::from_custom_bytes(&vec1).unwrap();
371            let val_ret2 = u128::from_custom_bytes(&vec2).unwrap();
372            assert_eq!(val1, val_ret1);
373            assert_eq!(val2, val_ret2);
374        }
375    }
376}
377
378#[test]
379fn test_upper_bound() {
380    assert_eq!(get_upper_bound(&[255]), Unbounded);
381    assert_eq!(get_upper_bound(&[255, 255, 255, 255]), Unbounded);
382    assert_eq!(get_upper_bound(&[0, 2]), Excluded(vec![0, 3]));
383    assert_eq!(get_upper_bound(&[0, 255]), Excluded(vec![1]));
384    assert_eq!(get_upper_bound(&[255, 0]), Excluded(vec![255, 1]));
385}
linera_views/common.rs

linera_views/
common.rs
