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

linera_views/
common.rs
