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

linera_views/
common.rs
