commonware_storage/store/
operation.rs

1//! Operations that can be applied to an authenticated database.
2//!
3//! The `Operation` enum implements the `Array` trait, allowing for a persistent log of operations
4//! based on a `crate::Journal`.
5
6use bytes::{Buf, BufMut};
7use commonware_codec::{
8    util::at_least, varint::UInt, Codec, CodecFixed, EncodeSize, Error as CodecError, FixedSize,
9    Read, ReadExt, Write,
10};
11use commonware_utils::{hex, Array};
12use std::{
13    cmp::{Ord, PartialOrd},
14    fmt::{Debug, Display},
15    hash::Hash,
16};
17use thiserror::Error;
18
19// Context byte prefixes for identifying the operation type.
20const DELETE_CONTEXT: u8 = 0;
21const UPDATE_CONTEXT: u8 = 1;
22const COMMIT_FLOOR_CONTEXT: u8 = 2;
23const SET_CONTEXT: u8 = 3;
24const COMMIT_CONTEXT: u8 = 4;
25const APPEND_CONTEXT: u8 = 5;
26
27/// Errors returned by operation functions.
28#[derive(Error, Debug)]
29pub enum Error {
30    #[error("invalid length")]
31    InvalidLength,
32    #[error("invalid key: {0}")]
33    InvalidKey(CodecError),
34    #[error("invalid value: {0}")]
35    InvalidValue(CodecError),
36    #[error("invalid context byte")]
37    InvalidContextByte,
38    #[error("delete operation has non-zero value")]
39    InvalidDeleteOp,
40    #[error("commit floor operation has non-zero bytes after location")]
41    InvalidCommitFloorOp,
42}
43
44/// An operation applied to an authenticated database with a fixed size value.
45#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
46pub enum Fixed<K: Array, V: CodecFixed> {
47    /// Indicates the key no longer has a value.
48    Delete(K),
49
50    /// Indicates the key now has the wrapped value.
51    Update(K, V),
52
53    /// Indicates all prior operations are no longer subject to rollback, and the floor on inactive
54    /// operations has been raised to the wrapped value.
55    CommitFloor(u64),
56}
57
58/// Operations for keyless stores.
59#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
60pub enum Keyless<V: Codec> {
61    /// Wraps the value appended to the database by this operation.
62    Append(V),
63
64    /// Indicates the database has been committed.
65    Commit(Option<V>),
66}
67
68impl<V: Codec> Keyless<V> {
69    /// Returns the value (if any) wrapped by this operation.
70    pub fn into_value(self) -> Option<V> {
71        match self {
72            Keyless::Append(value) => Some(value),
73            Keyless::Commit(value) => value,
74        }
75    }
76}
77
78/// An operation applied to an authenticated database with a variable size value.
79#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
80pub enum Variable<K: Array, V: Codec> {
81    // Operations for immutable stores.
82    Set(K, V),
83    Commit(Option<V>),
84    // Operations for mutable stores.
85    Delete(K),
86    Update(K, V),
87    CommitFloor(Option<V>, u64),
88}
89
90impl<K: Array, V: CodecFixed> FixedSize for Fixed<K, V> {
91    const SIZE: usize = u8::SIZE + K::SIZE + V::SIZE;
92}
93
94impl<K: Array, V: Codec> EncodeSize for Variable<K, V> {
95    fn encode_size(&self) -> usize {
96        1 + match self {
97            Variable::Delete(_) => K::SIZE,
98            Variable::Update(_, v) => K::SIZE + v.encode_size(),
99            Variable::CommitFloor(v, floor_loc) => v.encode_size() + UInt(*floor_loc).encode_size(),
100            Variable::Set(_, v) => K::SIZE + v.encode_size(),
101            Variable::Commit(v) => v.encode_size(),
102        }
103    }
104}
105
106impl<V: Codec> EncodeSize for Keyless<V> {
107    fn encode_size(&self) -> usize {
108        1 + match self {
109            Keyless::Append(v) => v.encode_size(),
110            Keyless::Commit(v) => v.encode_size(),
111        }
112    }
113}
114
115impl<K: Array, V: CodecFixed> Fixed<K, V> {
116    // A compile-time assertion that operation's array size is large enough to handle the commit
117    // operation, which requires 9 bytes.
118    const _MIN_OPERATION_LEN: usize = 9;
119    const _COMMIT_OP_ASSERT: () = assert!(
120        Self::SIZE >= Self::_MIN_OPERATION_LEN,
121        "array size too small for commit op"
122    );
123
124    /// If this is a [Fixed::Update] or [Fixed::Delete] operation, returns the key.
125    /// Otherwise, returns None.
126    pub fn key(&self) -> Option<&K> {
127        match self {
128            Fixed::Delete(key) => Some(key),
129            Fixed::Update(key, _) => Some(key),
130            Fixed::CommitFloor(_) => None,
131        }
132    }
133
134    /// If this is a [Fixed::Update] operation, returns the value.
135    /// Otherwise, returns None.
136    pub fn value(&self) -> Option<&V> {
137        match self {
138            Fixed::Delete(_) => None,
139            Fixed::Update(_, value) => Some(value),
140            Fixed::CommitFloor(_) => None,
141        }
142    }
143
144    /// If this is a [Fixed::Update] operation, returns the value.
145    /// Otherwise, returns None.
146    pub fn into_value(self) -> Option<V> {
147        match self {
148            Fixed::Delete(_) => None,
149            Fixed::Update(_, value) => Some(value),
150            Fixed::CommitFloor(_) => None,
151        }
152    }
153}
154
155impl<K: Array, V: Codec> Variable<K, V> {
156    /// If this is an operation involving a key, returns the key. Otherwise, returns None.
157    pub fn key(&self) -> Option<&K> {
158        match self {
159            Variable::Set(key, _) => Some(key),
160            Variable::Commit(_) => None,
161            Variable::Delete(key) => Some(key),
162            Variable::Update(key, _) => Some(key),
163            Variable::CommitFloor(_, _) => None,
164        }
165    }
166
167    /// If this is an operation involving a value, returns the value. Otherwise, returns None.
168    pub fn value(&self) -> Option<&V> {
169        match self {
170            Variable::Set(_, value) => Some(value),
171            Variable::Commit(value) => value.as_ref(),
172            Variable::Delete(_) => None,
173            Variable::Update(_, value) => Some(value),
174            Variable::CommitFloor(value, _) => value.as_ref(),
175        }
176    }
177
178    /// If this is an operation involving a value, returns the value. Otherwise, returns None.
179    pub fn into_value(self) -> Option<V> {
180        match self {
181            Variable::Set(_, value) => Some(value),
182            Variable::Commit(value) => value,
183            Variable::Delete(_) => None,
184            Variable::Update(_, value) => Some(value),
185            Variable::CommitFloor(value, _) => value,
186        }
187    }
188}
189
190impl<V: Codec> Write for Keyless<V> {
191    fn write(&self, buf: &mut impl BufMut) {
192        match &self {
193            Keyless::Append(value) => {
194                APPEND_CONTEXT.write(buf);
195                value.write(buf);
196            }
197            Keyless::Commit(metadata) => {
198                COMMIT_CONTEXT.write(buf);
199                metadata.write(buf);
200            }
201        }
202    }
203}
204
205impl<K: Array, V: CodecFixed> Write for Fixed<K, V> {
206    fn write(&self, buf: &mut impl BufMut) {
207        match &self {
208            Fixed::Delete(k) => {
209                DELETE_CONTEXT.write(buf);
210                k.write(buf);
211                // Pad with 0 up to [Self::SIZE]
212                buf.put_bytes(0, V::SIZE);
213            }
214            Fixed::Update(k, v) => {
215                UPDATE_CONTEXT.write(buf);
216                k.write(buf);
217                v.write(buf);
218            }
219            Fixed::CommitFloor(floor_loc) => {
220                COMMIT_FLOOR_CONTEXT.write(buf);
221                buf.put_slice(&floor_loc.to_be_bytes());
222                // Pad with 0 up to [Self::SIZE]
223                buf.put_bytes(0, Self::SIZE - 1 - u64::SIZE);
224            }
225        }
226    }
227}
228
229impl<K: Array, V: Codec> Write for Variable<K, V> {
230    fn write(&self, buf: &mut impl BufMut) {
231        match &self {
232            Variable::Set(k, v) => {
233                SET_CONTEXT.write(buf);
234                k.write(buf);
235                v.write(buf);
236            }
237            Variable::Commit(v) => {
238                COMMIT_CONTEXT.write(buf);
239                v.write(buf);
240            }
241            Variable::Delete(k) => {
242                DELETE_CONTEXT.write(buf);
243                k.write(buf);
244            }
245            Variable::Update(k, v) => {
246                UPDATE_CONTEXT.write(buf);
247                k.write(buf);
248                v.write(buf);
249            }
250            Variable::CommitFloor(v, floor_loc) => {
251                COMMIT_FLOOR_CONTEXT.write(buf);
252                v.write(buf);
253                UInt(*floor_loc).write(buf);
254            }
255        }
256    }
257}
258
259impl<V: Codec> Read for Keyless<V> {
260    type Cfg = <V as Read>::Cfg;
261
262    fn read_cfg(buf: &mut impl Buf, cfg: &Self::Cfg) -> Result<Self, CodecError> {
263        match u8::read(buf)? {
264            APPEND_CONTEXT => Ok(Self::Append(V::read_cfg(buf, cfg)?)),
265            COMMIT_CONTEXT => Ok(Self::Commit(Option::<V>::read_cfg(buf, cfg)?)),
266            e => Err(CodecError::InvalidEnum(e)),
267        }
268    }
269}
270
271impl<K: Array, V: CodecFixed> Read for Fixed<K, V> {
272    type Cfg = <V as Read>::Cfg;
273
274    fn read_cfg(buf: &mut impl Buf, cfg: &Self::Cfg) -> Result<Self, CodecError> {
275        at_least(buf, Self::SIZE)?;
276
277        match u8::read(buf)? {
278            UPDATE_CONTEXT => {
279                let key = K::read(buf)?;
280                let value = V::read_cfg(buf, cfg)?;
281                Ok(Self::Update(key, value))
282            }
283            DELETE_CONTEXT => {
284                let key = K::read(buf)?;
285                // Check that the value is all zeroes
286                for _ in 0..V::SIZE {
287                    if u8::read(buf)? != 0 {
288                        return Err(CodecError::Invalid(
289                            "storage::adb::operation::Fixed",
290                            "delete value non-zero",
291                        ));
292                    }
293                }
294                Ok(Self::Delete(key))
295            }
296            COMMIT_FLOOR_CONTEXT => {
297                let floor_loc = u64::read(buf)?;
298                for _ in 0..(Self::SIZE - 1 - u64::SIZE) {
299                    if u8::read(buf)? != 0 {
300                        return Err(CodecError::Invalid(
301                            "storage::adb::operation::Fixed",
302                            "commit value non-zero",
303                        ));
304                    }
305                }
306                Ok(Self::CommitFloor(floor_loc))
307            }
308            e => Err(CodecError::InvalidEnum(e)),
309        }
310    }
311}
312
313impl<K: Array, V: Codec> Read for Variable<K, V> {
314    type Cfg = <V as Read>::Cfg;
315
316    fn read_cfg(buf: &mut impl Buf, cfg: &Self::Cfg) -> Result<Self, CodecError> {
317        match u8::read(buf)? {
318            SET_CONTEXT => {
319                let key = K::read(buf)?;
320                let value = V::read_cfg(buf, cfg)?;
321                Ok(Self::Set(key, value))
322            }
323            COMMIT_CONTEXT => Ok(Self::Commit(Option::<V>::read_cfg(buf, cfg)?)),
324            DELETE_CONTEXT => {
325                let key = K::read(buf)?;
326                Ok(Self::Delete(key))
327            }
328            UPDATE_CONTEXT => {
329                let key = K::read(buf)?;
330                let value = V::read_cfg(buf, cfg)?;
331                Ok(Self::Update(key, value))
332            }
333            COMMIT_FLOOR_CONTEXT => {
334                let metadata = Option::<V>::read_cfg(buf, cfg)?;
335                let floor_loc = UInt::read(buf)?;
336                Ok(Self::CommitFloor(metadata, floor_loc.into()))
337            }
338            e => Err(CodecError::InvalidEnum(e)),
339        }
340    }
341}
342
343impl<V: Codec> Display for Keyless<V> {
344    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
345        match self {
346            Keyless::Append(value) => write!(f, "[append value:{}]", hex(&value.encode())),
347            Keyless::Commit(value) => {
348                if let Some(value) = value {
349                    write!(f, "[commit {}]", hex(&value.encode()))
350                } else {
351                    write!(f, "[commit]")
352                }
353            }
354        }
355    }
356}
357
358impl<K: Array, V: CodecFixed> Display for Fixed<K, V> {
359    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
360        match self {
361            Fixed::Delete(key) => write!(f, "[key:{key} <deleted>]"),
362            Fixed::Update(key, value) => write!(f, "[key:{key} value:{}]", hex(&value.encode())),
363            Fixed::CommitFloor(loc) => write!(f, "[commit with inactivity floor: {loc}]"),
364        }
365    }
366}
367
368impl<K: Array, V: Codec> Display for Variable<K, V> {
369    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
370        match self {
371            Variable::Set(key, value) => write!(f, "[key:{key} value:{}]", hex(&value.encode())),
372            Variable::Commit(value) => {
373                if let Some(value) = value {
374                    write!(f, "[commit {}]", hex(&value.encode()))
375                } else {
376                    write!(f, "[commit]")
377                }
378            }
379            Variable::Delete(key) => write!(f, "[key:{key} <deleted>]"),
380            Variable::Update(key, value) => write!(f, "[key:{key} value:{}]", hex(&value.encode())),
381            Variable::CommitFloor(value, loc) => {
382                if let Some(value) = value {
383                    write!(
384                        f,
385                        "[commit {} with inactivity floor: {loc}]",
386                        hex(&value.encode())
387                    )
388                } else {
389                    write!(f, "[commit with inactivity floor: {loc}]")
390                }
391            }
392        }
393    }
394}
395
396#[cfg(test)]
397mod tests {
398    use super::*;
399    use commonware_codec::{DecodeExt, Encode};
400    use commonware_utils::sequence::U64;
401
402    #[test]
403    fn test_to_key() {
404        let key = U64::new(1234);
405        let value = U64::new(56789);
406
407        let update_op = Fixed::Update(key.clone(), value.clone());
408        assert_eq!(&key, update_op.key().unwrap());
409
410        let delete_op = Fixed::<U64, U64>::Delete(key.clone());
411        assert_eq!(&key, delete_op.key().unwrap());
412
413        let commit_op = Fixed::<U64, U64>::CommitFloor(42);
414        assert_eq!(None, commit_op.key());
415    }
416
417    #[test]
418    fn test_to_value() {
419        let key = U64::new(1234);
420        let value = U64::new(56789);
421
422        let update_op = Fixed::Update(key.clone(), value.clone());
423        assert_eq!(&value, update_op.value().unwrap());
424
425        let delete_op = Fixed::<U64, U64>::Delete(key.clone());
426        assert_eq!(None, delete_op.value());
427
428        let commit_op = Fixed::<U64, U64>::CommitFloor(42);
429        assert_eq!(None, commit_op.value());
430    }
431
432    #[test]
433    fn test_operation_array_basic() {
434        let key = U64::new(1234);
435        let value = U64::new(56789);
436
437        let update_op = Fixed::Update(key.clone(), value.clone());
438        assert_eq!(&key, update_op.key().unwrap());
439        assert_eq!(&value, update_op.value().unwrap());
440
441        let from = Fixed::<U64, U64>::decode(update_op.encode()).unwrap();
442        assert_eq!(&key, from.key().unwrap());
443        assert_eq!(&value, from.value().unwrap());
444        assert_eq!(update_op, from);
445
446        let key2 = U64::new(42);
447        let delete_op = Fixed::<U64, U64>::Delete(key2.clone());
448        let from = Fixed::<U64, U64>::decode(delete_op.encode()).unwrap();
449        assert_eq!(&key2, from.key().unwrap());
450        assert_eq!(None, from.value());
451        assert_eq!(delete_op, from);
452
453        let commit_op = Fixed::<U64, U64>::CommitFloor(42);
454        let from = Fixed::<U64, U64>::decode(commit_op.encode()).unwrap();
455        assert_eq!(None, from.value());
456        assert!(matches!(from, Fixed::CommitFloor(42)));
457        assert_eq!(commit_op, from);
458
459        // test non-zero byte detection in delete operation
460        let mut invalid = delete_op.encode();
461        invalid[U64::SIZE + 4] = 0xFF;
462        let decoded = Fixed::<U64, U64>::decode(invalid.as_ref());
463        assert!(matches!(decoded.unwrap_err(), CodecError::Invalid(_, _)));
464
465        // test invalid context byte detection
466        let mut invalid = delete_op.encode();
467        invalid[0] = 0xFF;
468        let decoded = Fixed::<U64, U64>::decode(invalid.as_ref());
469        assert!(matches!(
470            decoded.unwrap_err(),
471            CodecError::InvalidEnum(0xFF)
472        ));
473
474        // test invalid length detection
475        let mut invalid = delete_op.encode().to_vec();
476        invalid.pop();
477        let decoded = Fixed::<U64, U64>::decode(invalid.as_ref());
478        assert!(matches!(decoded.unwrap_err(), CodecError::EndOfBuffer));
479    }
480
481    #[test]
482    fn test_operation_array_display() {
483        let key = U64::new(1234);
484        let value = U64::new(56789);
485        let update_op = Fixed::Update(key.clone(), value.clone());
486        assert_eq!(
487            format!("{update_op}"),
488            format!("[key:{key} value:{}]", hex(&value.encode()))
489        );
490
491        let key2 = U64::new(42);
492        let delete_op = Fixed::<U64, U64>::Delete(key2.clone());
493        assert_eq!(format!("{delete_op}"), format!("[key:{key2} <deleted>]"));
494    }
495
496    #[test]
497    fn test_operation_array_codec() {
498        let key = U64::new(1234);
499        let value = U64::new(5678);
500        let update_op = Fixed::Update(key, value);
501
502        let encoded = update_op.encode();
503        assert_eq!(encoded.len(), Fixed::<U64, U64>::SIZE);
504
505        let decoded = Fixed::<U64, U64>::decode(encoded).unwrap();
506        assert_eq!(update_op, decoded);
507    }
508
509    #[test]
510    fn test_keyless_append() {
511        let append_op = Keyless::Append(U64::new(12345));
512
513        let encoded = append_op.encode();
514        assert_eq!(encoded.len(), 1 + U64::SIZE);
515
516        let decoded = Keyless::<U64>::decode(encoded).unwrap();
517        assert_eq!(append_op, decoded);
518        assert_eq!(
519            format!("{append_op}"),
520            format!("[append value:{}]", hex(&U64::new(12345).encode()))
521        );
522    }
523
524    #[test]
525    fn test_keyless_commit() {
526        let metadata = Some(U64::new(12345));
527        let commit_op = Keyless::<U64>::Commit(metadata.clone());
528
529        let encoded = commit_op.encode();
530        assert_eq!(encoded.len(), 1 + metadata.encode_size());
531
532        let decoded = Keyless::<U64>::decode(encoded).unwrap();
533        let Keyless::Commit(metadata_decoded) = decoded else {
534            panic!("expected commit operation");
535        };
536        assert_eq!(metadata, metadata_decoded);
537    }
538
539    #[test]
540    fn test_keyless_invalid_context() {
541        let invalid = vec![0xFF; 1];
542        let decoded = Keyless::<U64>::decode(invalid.as_ref());
543        assert!(matches!(
544            decoded.unwrap_err(),
545            CodecError::InvalidEnum(0xFF)
546        ));
547    }
548}
commonware_storage/store/operation.rs

commonware_storage/store/
operation.rs
