massa_models/
datastore.rs

1// Copyright (c) 2022 MASSA LABS <info@massa.net>
2
3use crate::error::ModelsError;
4use crate::serialization::{VecU8Deserializer, VecU8Serializer};
5use massa_serialization::{
6    Deserializer, SerializeError, Serializer, U64VarIntDeserializer, U64VarIntSerializer,
7};
8use nom::error::{context, ContextError, ParseError};
9use nom::multi::length_count;
10use nom::sequence::tuple;
11use nom::{IResult, Parser};
12use std::collections::BTreeMap;
13use std::ops::Bound::{self, Included};
14
15/// Datastore entry for Ledger & `ExecuteSC` Operation
16/// A Datastore is a Key Value store where
17/// Key: Byte array (max length should be 255)
18/// Value: Byte array
19/// What is stored can be arbitrary bytes but can often be smart contract bytecode (aka WASM binary)
20pub type Datastore = BTreeMap<Vec<u8>, Vec<u8>>;
21
22/// Serializer for `Datastore`
23#[derive(Default)]
24pub struct DatastoreSerializer {
25    u64_serializer: U64VarIntSerializer,
26    vec_u8_serializer: VecU8Serializer,
27}
28
29impl DatastoreSerializer {
30    /// Creates a new `DatastoreSerializer`
31    pub fn new() -> Self {
32        Self {
33            u64_serializer: U64VarIntSerializer::new(),
34            vec_u8_serializer: VecU8Serializer::new(),
35        }
36    }
37}
38
39impl Serializer<Datastore> for DatastoreSerializer {
40    /// ## Example
41    /// ```rust
42    /// use std::collections::BTreeMap;
43    /// use massa_models::datastore::DatastoreSerializer;
44    /// use massa_serialization::Serializer;
45    ///
46    /// let serializer = DatastoreSerializer::new();
47    /// let mut buffer = Vec::new();
48    /// let mut datastore = BTreeMap::new();
49    /// datastore.insert(vec![1, 2, 3], vec![4, 5, 6]);
50    /// datastore.insert(vec![3, 4, 5], vec![6, 7, 8]);
51    /// serializer.serialize(&datastore, &mut buffer).unwrap();
52    /// ```
53    fn serialize(
54        &self,
55        value: &BTreeMap<Vec<u8>, Vec<u8>>,
56        buffer: &mut Vec<u8>,
57    ) -> Result<(), SerializeError> {
58        let entry_count: u64 = value.len().try_into().map_err(|err| {
59            SerializeError::GeneralError(format!(
60                "too many entries in ConsensusLedgerSubset: {}",
61                err
62            ))
63        })?;
64        self.u64_serializer.serialize(&entry_count, buffer)?;
65        for (key, value) in value.iter() {
66            self.vec_u8_serializer.serialize(key, buffer)?;
67            self.vec_u8_serializer.serialize(value, buffer)?;
68        }
69        Ok(())
70    }
71}
72
73/// Deserializer for `Datastore` field in `LedgerEntry`
74pub struct DatastoreDeserializer {
75    length_deserializer: U64VarIntDeserializer,
76    key_deserializer: VecU8Deserializer,
77    value_deserializer: VecU8Deserializer,
78}
79
80impl DatastoreDeserializer {
81    /// Creates a new `DatastoreDeserializer`
82    pub fn new(
83        max_datastore_entry_count: u64,
84        max_datastore_key_length: u8,
85        max_datastore_value_length: u64,
86    ) -> Self {
87        Self {
88            length_deserializer: U64VarIntDeserializer::new(
89                Included(u64::MIN),
90                Included(max_datastore_entry_count),
91            ),
92            key_deserializer: VecU8Deserializer::new(
93                Included(u64::MIN),
94                Included(max_datastore_key_length as u64),
95            ),
96            value_deserializer: VecU8Deserializer::new(
97                Included(u64::MIN),
98                Included(max_datastore_value_length),
99            ),
100        }
101    }
102}
103
104impl Deserializer<Datastore> for DatastoreDeserializer {
105    /// ## Example
106    /// ```rust
107    /// use std::collections::BTreeMap;
108    /// use massa_models::datastore::{DatastoreDeserializer, DatastoreSerializer};
109    /// use massa_serialization::{Serializer, Deserializer, DeserializeError};
110    ///
111    /// let serializer = DatastoreSerializer::new();
112    /// let deserializer = DatastoreDeserializer::new(10000, 255, 10000);
113    /// let mut buffer = Vec::new();
114    /// let mut datastore = BTreeMap::new();
115    /// datastore.insert(vec![1, 2, 3], vec![4, 5, 6]);
116    /// datastore.insert(vec![3, 4, 5], vec![6, 7, 8]);
117    /// serializer.serialize(&datastore, &mut buffer).unwrap();
118    /// let (rest, deserialized) = deserializer.deserialize::<DeserializeError>(&buffer).unwrap();
119    /// assert_eq!(rest.len(), 0);
120    /// assert_eq!(deserialized, datastore);
121    /// ```
122    fn deserialize<'a, E: ParseError<&'a [u8]> + ContextError<&'a [u8]>>(
123        &self,
124        buffer: &'a [u8],
125    ) -> IResult<&'a [u8], BTreeMap<Vec<u8>, Vec<u8>>, E> {
126        context(
127            "Failed Datastore deserialization",
128            length_count(
129                context("Failed length deserialization", |input| {
130                    self.length_deserializer.deserialize(input)
131                }),
132                tuple((
133                    context("Failed key deserialization", |input| {
134                        self.key_deserializer.deserialize(input)
135                    }),
136                    context("Failed value deserialization", |input| {
137                        self.value_deserializer.deserialize(input)
138                    }),
139                )),
140            ),
141        )
142        // Note: unsorted key/value pairs, and duplicate keys (last occurrence wins), on the wire
143        // still deserialize to the same normalized BTreeMap. So different raw bytes / OperationIds can
144        // encode the same logical action. Massa is malleability-resistant by construction: nothing
145        // relies on canonical encodings, and only the signer can produce such variants (who can already
146        // produce distinct ids for the same action anyway), so this is not exploitable.
147        // Rejecting non-canonical encodings would be a breaking change for no security gain.
148        .map(|elements| elements.into_iter().collect())
149        .parse(buffer)
150    }
151}
152
153/// For lexicographically ordered keys,
154/// gets the upper and lower bound of keys matching a prefix.
155pub fn get_prefix_bounds(prefix: &[u8]) -> (std::ops::Bound<Vec<u8>>, std::ops::Bound<Vec<u8>>) {
156    if prefix.is_empty() {
157        return (std::ops::Bound::Unbounded, std::ops::Bound::Unbounded);
158    }
159    let n_keep = prefix
160        .iter()
161        .enumerate()
162        .rev()
163        .find_map(|(i, v)| if v < &255 { Some(i + 1) } else { None })
164        .unwrap_or(0);
165    let mut prefix_end = prefix[..n_keep].to_vec();
166    if let Some(v) = prefix_end.last_mut() {
167        *v += 1;
168    }
169    (
170        std::ops::Bound::Included(prefix.to_vec()),
171        if !prefix_end.is_empty() {
172            std::ops::Bound::Excluded(prefix_end)
173        } else {
174            std::ops::Bound::Unbounded
175        },
176    )
177}
178
179/// Return the intersection of two ranges
180pub fn range_intersection<T: Ord>(
181    r1: (std::ops::Bound<T>, std::ops::Bound<T>),
182    r2: (std::ops::Bound<T>, std::ops::Bound<T>),
183) -> Option<(std::ops::Bound<T>, std::ops::Bound<T>)> {
184    use std::cmp::{max, min};
185    use std::ops::Bound;
186
187    let (r1s, r1e) = r1;
188    let (r2s, r2e) = r2;
189
190    // Determine the start of the intersection
191    let start = match (r1s, r2s) {
192        (Bound::Included(a), Bound::Included(b)) => Bound::Included(max(a, b)),
193        (Bound::Included(a), Bound::Excluded(b)) => {
194            if a > b {
195                Bound::Included(a)
196            } else {
197                Bound::Excluded(b)
198            }
199        }
200        (Bound::Excluded(a), Bound::Included(b)) => {
201            if b > a {
202                Bound::Included(b)
203            } else {
204                Bound::Excluded(a)
205            }
206        }
207        (Bound::Excluded(a), Bound::Excluded(b)) => Bound::Excluded(max(a, b)),
208        (Bound::Unbounded, other) => other,
209        (other, Bound::Unbounded) => other,
210    };
211
212    // Determine the end of the intersection
213    let end = match (r1e, r2e) {
214        (Bound::Included(a), Bound::Included(b)) => Bound::Included(min(a, b)),
215        (Bound::Included(a), Bound::Excluded(b)) => {
216            if a < b {
217                Bound::Included(a)
218            } else {
219                Bound::Excluded(b)
220            }
221        }
222        (Bound::Excluded(a), Bound::Included(b)) => {
223            if b < a {
224                Bound::Included(b)
225            } else {
226                Bound::Excluded(a)
227            }
228        }
229        (Bound::Excluded(a), Bound::Excluded(b)) => Bound::Excluded(min(a, b)),
230        (Bound::Unbounded, other) => other,
231        (other, Bound::Unbounded) => other,
232    };
233
234    // Ensure the resulting range is valid
235    match (&start, &end) {
236        (Bound::Included(a), Bound::Included(b)) if a > b => None,
237        (Bound::Included(a), Bound::Excluded(b)) if a >= b => None,
238        (Bound::Excluded(a), Bound::Included(b)) if a >= b => None,
239        (Bound::Excluded(a), Bound::Excluded(b)) if a >= b => None,
240        _ => Some((start, end)),
241    }
242}
243
244/// Checks and cleans up a datastore key range query
245/// Returns: (prefix, start_bound, end_bound, count) or error
246/// The returned count is the effective item count limit: it falls back to the
247/// configured maximum when the caller did not provide one, so that callers can
248/// forward it to the datastore scan instead of running an unbounded enumeration.
249/// Note: only useful to cleanup user-supplied requests (API/ABI)
250#[allow(clippy::type_complexity)]
251pub fn cleanup_datastore_key_range_query(
252    prefix: &[u8],
253    start_bound: Bound<Vec<u8>>,
254    end_bound: Bound<Vec<u8>>,
255    count: Option<u32>,
256    max_datastore_key_length: u8,
257    max_datastore_query_config: Option<u32>,
258) -> Result<(Vec<u8>, Bound<Vec<u8>>, Bound<Vec<u8>>, Option<u32>), ModelsError> {
259    // check item count
260    let count = count.or(max_datastore_query_config);
261    if let (Some(cnt), Some(max_cnt)) = (count.as_ref(), max_datastore_query_config.as_ref()) {
262        if cnt > max_cnt {
263            return Err(ModelsError::ErrorRaised(format!(
264                "max item count in datastore key query is {} but {} items were queried",
265                max_cnt, cnt
266            )));
267        }
268    }
269
270    // check prefix length
271    let prefix = if prefix.len() > max_datastore_key_length as usize {
272        // prefix is too long: it won't match anything. Adjust bounds to reflect this.
273        return Ok((
274            Vec::new(),
275            std::ops::Bound::Excluded(Vec::new()),
276            std::ops::Bound::Excluded(Vec::new()),
277            count,
278        ));
279    } else {
280        prefix.to_vec()
281    };
282
283    // If the key is longer than the max possible length
284    // it will be by definition excluded
285    // and since its truncation is before, it will also be excluded
286    let start_bound = match start_bound {
287        std::ops::Bound::Unbounded => std::ops::Bound::Unbounded,
288        std::ops::Bound::Excluded(mut k) => {
289            k.truncate(max_datastore_key_length as usize);
290            Bound::Excluded(k)
291        }
292        std::ops::Bound::Included(mut k) => {
293            if k.len() > max_datastore_key_length as usize {
294                k.truncate(max_datastore_key_length as usize);
295                Bound::Excluded(k)
296            } else {
297                Bound::Included(k)
298            }
299        }
300    };
301
302    // If the key is longer than the max possible length
303    // it will be by definition excluded
304    // but its truncation is included
305    let end_bound = match end_bound {
306        std::ops::Bound::Unbounded => std::ops::Bound::Unbounded,
307        std::ops::Bound::Included(mut k) => {
308            k.truncate(max_datastore_key_length as usize);
309            Bound::Included(k)
310        }
311        std::ops::Bound::Excluded(mut k) => {
312            if k.len() > max_datastore_key_length as usize {
313                k.truncate(max_datastore_key_length as usize);
314                Bound::Included(k)
315            } else {
316                Bound::Excluded(k)
317            }
318        }
319    };
320
321    Ok((prefix, start_bound, end_bound, count))
322}
323
324#[cfg(test)]
325mod tests {
326
327    use crate::config::{
328        MAX_OPERATION_DATASTORE_ENTRY_COUNT, MAX_OPERATION_DATASTORE_KEY_LENGTH,
329        MAX_OPERATION_DATASTORE_VALUE_LENGTH,
330    };
331
332    use super::*;
333    use massa_serialization::DeserializeError;
334    use serde::{Deserialize, Serialize};
335    use serde_with::serde_as;
336
337    #[serde_as]
338    #[derive(Debug, Serialize, Deserialize, PartialEq)]
339    struct SerdeWrapper(#[serde_as(as = "Vec<(_, _)>")] Datastore);
340
341    #[test]
342    fn test_ser_der() {
343        let datastore = BTreeMap::from([
344            (vec![1, 2], vec![3, 4]),
345            (vec![5, 6, 7], vec![8]),
346            (vec![9], vec![10, 11, 12, 13, 14]),
347            (vec![], vec![]),
348        ]);
349
350        let datastore_serializer = DatastoreSerializer::new();
351        let mut buffer = Vec::new();
352        datastore_serializer
353            .serialize(&datastore, &mut buffer)
354            .expect("Should not fail while serializing Datastore");
355
356        let datastore_deserializer = DatastoreDeserializer::new(
357            MAX_OPERATION_DATASTORE_ENTRY_COUNT,
358            MAX_OPERATION_DATASTORE_KEY_LENGTH,
359            MAX_OPERATION_DATASTORE_VALUE_LENGTH,
360        );
361        let (_, datastore_der) = datastore_deserializer
362            .deserialize::<DeserializeError>(&buffer)
363            .unwrap();
364        assert_eq!(datastore, datastore_der);
365    }
366
367    #[test]
368    #[should_panic]
369    fn test_der_fail() {
370        let max_operation_datastore_entry_count: usize = 10;
371
372        // a datastore too much entries
373        let datastore = std::iter::repeat(())
374            .enumerate()
375            .map(|(i, _)| (vec![i as u8, 1, 2], vec![33, 44, 55]))
376            .take(max_operation_datastore_entry_count + 1)
377            .collect();
378
379        let datastore_serializer = DatastoreSerializer::new();
380        let mut buffer = Vec::new();
381        datastore_serializer
382            .serialize(&datastore, &mut buffer)
383            .expect("Should not fail while serializing Datastore");
384
385        let datastore_deserializer = DatastoreDeserializer::new(
386            max_operation_datastore_entry_count as u64,
387            MAX_OPERATION_DATASTORE_KEY_LENGTH,
388            MAX_OPERATION_DATASTORE_VALUE_LENGTH,
389        );
390        let (_, _datastore_der) = datastore_deserializer
391            .deserialize::<DeserializeError>(&buffer)
392            .unwrap();
393    }
394
395    #[test]
396    fn test_datastore_serde() {
397        let expected_datastore: Datastore = BTreeMap::from([
398            (vec![1, 2], vec![3, 4]),
399            (vec![5, 6, 7], vec![8]),
400            (vec![9], vec![10, 11, 12, 13, 14]),
401            (vec![], vec![]),
402        ]);
403
404        let wrapper = SerdeWrapper(expected_datastore.clone());
405        let serialized = serde_json::to_string(&wrapper).unwrap();
406        let actual_wrapper: SerdeWrapper = serde_json::from_str(&serialized).unwrap();
407
408        assert_eq!(actual_wrapper.0, expected_datastore);
409    }
410
411    #[test]
412    fn test_range_intersection() {
413        // Overlapping ranges
414        {
415            let r1 = (std::ops::Bound::Included(1), std::ops::Bound::Included(5));
416            let r2 = (std::ops::Bound::Included(3), std::ops::Bound::Included(7));
417            let expected = (std::ops::Bound::Included(3), std::ops::Bound::Included(5));
418            assert_eq!(range_intersection(r1, r2), Some(expected));
419        }
420
421        // Fully overlapping ranges
422        {
423            let r1 = (std::ops::Bound::Included(1), std::ops::Bound::Included(10));
424            let r2 = (std::ops::Bound::Included(3), std::ops::Bound::Included(7));
425            let expected = (std::ops::Bound::Included(3), std::ops::Bound::Included(7));
426            assert_eq!(range_intersection(r1, r2), Some(expected));
427        }
428
429        // Adjacent ranges (no overlap)
430        {
431            let r1 = (std::ops::Bound::Included(1), std::ops::Bound::Excluded(5));
432            let r2 = (std::ops::Bound::Included(5), std::ops::Bound::Included(10));
433            assert_eq!(range_intersection(r1, r2), None);
434        }
435
436        // Exact match
437        {
438            let r1 = (std::ops::Bound::Included(1), std::ops::Bound::Included(5));
439            let r2 = (std::ops::Bound::Included(1), std::ops::Bound::Included(5));
440            let expected = (std::ops::Bound::Included(1), std::ops::Bound::Included(5));
441            assert_eq!(range_intersection(r1, r2), Some(expected));
442        }
443
444        // Unbounded start
445        {
446            let r1 = (std::ops::Bound::Unbounded, std::ops::Bound::Included(5));
447            let r2 = (std::ops::Bound::Included(3), std::ops::Bound::Included(7));
448            let expected = (std::ops::Bound::Included(3), std::ops::Bound::Included(5));
449            assert_eq!(range_intersection(r1, r2), Some(expected));
450        }
451
452        // Unbounded end
453        {
454            let r1 = (std::ops::Bound::Included(1), std::ops::Bound::Unbounded);
455            let r2 = (std::ops::Bound::Included(3), std::ops::Bound::Included(7));
456            let expected = (std::ops::Bound::Included(3), std::ops::Bound::Included(7));
457            assert_eq!(range_intersection(r1, r2), Some(expected));
458        }
459
460        // Both ranges unbounded
461        {
462            let r1 = (std::ops::Bound::Unbounded, std::ops::Bound::Unbounded);
463            let r2 = (std::ops::Bound::Included(3), std::ops::Bound::Included(7));
464            let expected = (std::ops::Bound::Included(3), std::ops::Bound::Included(7));
465            assert_eq!(range_intersection(r1, r2), Some(expected));
466        }
467
468        // Non-overlapping ranges
469        {
470            let r1 = (std::ops::Bound::Included(1), std::ops::Bound::Included(5));
471            let r2 = (std::ops::Bound::Included(6), std::ops::Bound::Included(10));
472            assert_eq!(range_intersection(r1, r2), None);
473        }
474
475        // Empty range
476        {
477            let r1 = (std::ops::Bound::Included(1), std::ops::Bound::Included(5));
478            let r2 = (std::ops::Bound::Included(5), std::ops::Bound::Excluded(5));
479            assert_eq!(range_intersection(r1, r2), None);
480        }
481
482        // Edge case: Excluded bounds
483        {
484            let r1 = (std::ops::Bound::Excluded(1), std::ops::Bound::Included(5));
485            let r2 = (std::ops::Bound::Excluded(1), std::ops::Bound::Excluded(5));
486            let expected = (std::ops::Bound::Excluded(1), std::ops::Bound::Excluded(5));
487            assert_eq!(range_intersection(r1, r2), Some(expected));
488        }
489    }
490
491    #[test]
492    fn test_cleanup_datastore_key_range_query() {
493        // Case 1: Valid inputs
494        let prefix = b"prfx".to_vec();
495        let start_bound = Bound::Included(b"start_key".to_vec());
496        let end_bound = Bound::Excluded(b"end_key".to_vec());
497        let count = Some(10);
498        let max_length = 20;
499        let max_query_config = Some(50);
500
501        let result = cleanup_datastore_key_range_query(
502            &prefix,
503            start_bound.clone(),
504            end_bound.clone(),
505            count,
506            max_length,
507            max_query_config,
508        );
509        assert!(result.is_ok());
510        let (res_prefix, res_start, res_end, res_count) = result.unwrap();
511        assert_eq!(res_prefix, prefix);
512        assert_eq!(res_start, start_bound);
513        assert_eq!(res_end, end_bound);
514        assert_eq!(res_count, count);
515
516        // Case 2: Prefix length exceeds max length
517        let long_prefix = vec![b'a'; 30];
518        let result = cleanup_datastore_key_range_query(
519            &long_prefix,
520            start_bound.clone(),
521            end_bound.clone(),
522            None,
523            10,
524            None,
525        );
526        assert!(result.is_ok());
527        let (res_prefix, res_start, res_end, res_count) = result.unwrap();
528        assert!(res_prefix.is_empty());
529        assert_eq!(res_count, None);
530        assert_eq!(res_start, Bound::Excluded(Vec::new()));
531        assert_eq!(res_end, Bound::Excluded(Vec::new()));
532
533        // Case 3: Keys exceeding max length in bounds
534        let long_key = vec![b'b'; 25];
535        let start_bound = Bound::Included(long_key.clone());
536        let end_bound = Bound::Excluded(long_key.clone());
537        let result = cleanup_datastore_key_range_query(
538            &prefix,
539            start_bound.clone(),
540            end_bound.clone(),
541            None,
542            10,
543            None,
544        );
545        assert!(result.is_ok());
546        let (res_prefix, res_start, res_end, res_count) = result.unwrap();
547        assert_eq!(res_prefix, prefix);
548        assert_eq!(res_count, None);
549        assert_eq!(
550            res_start,
551            Bound::Excluded(long_key[0..10].to_vec()) // Start key truncated
552        );
553        assert_eq!(
554            res_end,
555            Bound::Included(long_key[0..10].to_vec()) // End key truncated
556        );
557
558        // Case 4: Count exceeds max query config
559        let result = cleanup_datastore_key_range_query(
560            &prefix,
561            Bound::Unbounded,
562            Bound::Unbounded,
563            Some(100),
564            10,
565            Some(50),
566        );
567        assert!(result.is_err());
568        if let Err(ModelsError::ErrorRaised(msg)) = result {
569            assert!(msg.contains(
570                "max item count in datastore key query is 50 but 100 items were queried"
571            ));
572        } else {
573            panic!("Expected ModelsError::ErrorRaised");
574        }
575
576        // Case 5: No count or max query config provided
577        let result = cleanup_datastore_key_range_query(
578            &prefix,
579            Bound::Unbounded,
580            Bound::Unbounded,
581            None,
582            10,
583            None,
584        );
585        assert!(result.is_ok());
586        let (res_prefix, res_start, res_end, res_count) = result.unwrap();
587        assert_eq!(res_prefix, prefix);
588        assert_eq!(res_start, Bound::Unbounded);
589        assert_eq!(res_end, Bound::Unbounded);
590        assert_eq!(res_count, None);
591
592        // Case 6: No count provided but a max query config is set:
593        // the configured maximum is used as the effective count so that the
594        // datastore scan stays bounded.
595        let result = cleanup_datastore_key_range_query(
596            &prefix,
597            Bound::Unbounded,
598            Bound::Unbounded,
599            None,
600            10,
601            Some(50),
602        );
603        assert!(result.is_ok());
604        let (_res_prefix, _res_start, _res_end, res_count) = result.unwrap();
605        assert_eq!(res_count, Some(50));
606    }
607}
massa_models/datastore.rs

massa_models/
datastore.rs
