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, Codec, EncodeSize, Error as CodecError, FixedSize, Read, ReadExt, Write,
9};
10use commonware_utils::Array;
11use std::{
12    cmp::{Ord, PartialOrd},
13    fmt::{Debug, Display},
14    hash::Hash,
15};
16use thiserror::Error;
17
18// Context byte prefixes for identifying the operation type.
19const DELETE_CONTEXT: u8 = 0;
20const UPDATE_CONTEXT: u8 = 1;
21const COMMIT_FLOOR_CONTEXT: u8 = 2;
22const SET_CONTEXT: u8 = 3;
23const COMMIT_CONTEXT: u8 = 4;
24
25/// Errors returned by operation functions.
26#[derive(Error, Debug)]
27pub enum Error {
28    #[error("invalid length")]
29    InvalidLength,
30    #[error("invalid key: {0}")]
31    InvalidKey(CodecError),
32    #[error("invalid value: {0}")]
33    InvalidValue(CodecError),
34    #[error("invalid context byte")]
35    InvalidContextByte,
36    #[error("delete operation has non-zero value")]
37    InvalidDeleteOp,
38    #[error("commit floor operation has non-zero bytes after location")]
39    InvalidCommitFloorOp,
40}
41
42/// An operation applied to an authenticated database with a fixed size value.
43#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
44pub enum Fixed<K: Array, V: Array> {
45    /// Indicates the key no longer has a value.
46    Delete(K),
47
48    /// Indicates the key now has the wrapped value.
49    Update(K, V),
50
51    /// Indicates all prior operations are no longer subject to rollback, and the floor on inactive
52    /// operations has been raised to the wrapped value.
53    CommitFloor(u64),
54}
55
56/// An operation applied to an authenticated database with a variable size value.
57#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
58pub enum Variable<K: Array, V: Codec> {
59    // Operations for immutable stores.
60    Set(K, V),
61    Commit(),
62    // Operations for mutable stores.
63    Delete(K),
64    Update(K, V),
65    CommitFloor(u64),
66}
67
68impl<K: Array, V: Array> FixedSize for Fixed<K, V> {
69    const SIZE: usize = u8::SIZE + K::SIZE + V::SIZE;
70}
71
72impl<K: Array, V: Codec> EncodeSize for Variable<K, V> {
73    fn encode_size(&self) -> usize {
74        match self {
75            Variable::Delete(_) => 1 + K::SIZE,
76            Variable::Update(_, v) => 1 + K::SIZE + v.encode_size(),
77            Variable::CommitFloor(_) => 1 + u64::SIZE,
78            Variable::Set(_, v) => 1 + K::SIZE + v.encode_size(),
79            Variable::Commit() => 1,
80        }
81    }
82}
83
84impl<K: Array, V: Array> Fixed<K, V> {
85    // A compile-time assertion that operation's array size is large enough to handle the commit
86    // operation, which requires 9 bytes.
87    const _MIN_OPERATION_LEN: usize = 9;
88    const _COMMIT_OP_ASSERT: () = assert!(
89        Self::SIZE >= Self::_MIN_OPERATION_LEN,
90        "array size too small for commit op"
91    );
92
93    /// If this is a [Fixed::Update] or [Fixed::Delete] operation, returns the key.
94    /// Otherwise, returns None.
95    pub fn to_key(&self) -> Option<&K> {
96        match self {
97            Fixed::Delete(key) => Some(key),
98            Fixed::Update(key, _) => Some(key),
99            Fixed::CommitFloor(_) => None,
100        }
101    }
102
103    ///If this is a [Fixed::Update] operation, returns the value.
104    /// Otherwise, returns None.
105    pub fn to_value(&self) -> Option<&V> {
106        match self {
107            Fixed::Delete(_) => None,
108            Fixed::Update(_, value) => Some(value),
109            Fixed::CommitFloor(_) => None,
110        }
111    }
112}
113
114impl<K: Array, V: Codec> Variable<K, V> {
115    /// If this is an operation involving a key, returns the key. Otherwise, returns None.
116    pub fn to_key(&self) -> Option<&K> {
117        match self {
118            Variable::Set(key, _) => Some(key),
119            Variable::Commit() => None,
120            Variable::Delete(key) => Some(key),
121            Variable::Update(key, _) => Some(key),
122            Variable::CommitFloor(_) => None,
123        }
124    }
125
126    /// If this is an operation involving a value, returns the value. Otherwise, returns None.
127    pub fn to_value(&self) -> Option<&V> {
128        match self {
129            Variable::Set(_, value) => Some(value),
130            Variable::Commit() => None,
131            Variable::Delete(_) => None,
132            Variable::Update(_, value) => Some(value),
133            Variable::CommitFloor(_) => None,
134        }
135    }
136}
137
138impl<K: Array, V: Array> Write for Fixed<K, V> {
139    fn write(&self, buf: &mut impl BufMut) {
140        match &self {
141            Fixed::Delete(k) => {
142                buf.put_u8(DELETE_CONTEXT);
143                k.write(buf);
144                // Pad with 0 up to [Self::SIZE]
145                buf.put_bytes(0, V::SIZE);
146            }
147            Fixed::Update(k, v) => {
148                buf.put_u8(UPDATE_CONTEXT);
149                k.write(buf);
150                v.write(buf);
151            }
152            Fixed::CommitFloor(floor_loc) => {
153                buf.put_u8(COMMIT_FLOOR_CONTEXT);
154                buf.put_slice(&floor_loc.to_be_bytes());
155                // Pad with 0 up to [Self::SIZE]
156                buf.put_bytes(0, Self::SIZE - 1 - u64::SIZE);
157            }
158        }
159    }
160}
161
162impl<K: Array, V: Codec> Write for Variable<K, V> {
163    fn write(&self, buf: &mut impl BufMut) {
164        match &self {
165            Variable::Set(k, v) => {
166                buf.put_u8(SET_CONTEXT);
167                k.write(buf);
168                v.write(buf);
169            }
170            Variable::Commit() => {
171                buf.put_u8(COMMIT_CONTEXT);
172            }
173            Variable::Delete(k) => {
174                buf.put_u8(DELETE_CONTEXT);
175                k.write(buf);
176            }
177            Variable::Update(k, v) => {
178                buf.put_u8(UPDATE_CONTEXT);
179                k.write(buf);
180                v.write(buf);
181            }
182            Variable::CommitFloor(floor_loc) => {
183                buf.put_u8(COMMIT_FLOOR_CONTEXT);
184                buf.put_slice(&floor_loc.to_be_bytes());
185            }
186        }
187    }
188}
189
190impl<K: Array, V: Array> Read for Fixed<K, V> {
191    type Cfg = ();
192
193    fn read_cfg(buf: &mut impl Buf, _: &()) -> Result<Self, CodecError> {
194        at_least(buf, Self::SIZE)?;
195
196        match u8::read(buf)? {
197            UPDATE_CONTEXT => {
198                let key = K::read(buf)?;
199                let value = V::read(buf)?;
200                Ok(Self::Update(key, value))
201            }
202            DELETE_CONTEXT => {
203                let key = K::read(buf)?;
204                // Check that the value is all zeroes
205                for _ in 0..V::SIZE {
206                    if u8::read(buf)? != 0 {
207                        return Err(CodecError::Invalid(
208                            "storage::adb::Operation",
209                            "delete value non-zero",
210                        ));
211                    }
212                }
213                Ok(Self::Delete(key))
214            }
215            COMMIT_FLOOR_CONTEXT => {
216                let floor_loc = u64::read(buf)?;
217                for _ in 0..(Self::SIZE - 1 - u64::SIZE) {
218                    if u8::read(buf)? != 0 {
219                        return Err(CodecError::Invalid(
220                            "storage::adb::Operation",
221                            "commit value non-zero",
222                        ));
223                    }
224                }
225                Ok(Self::CommitFloor(floor_loc))
226            }
227            e => Err(CodecError::InvalidEnum(e)),
228        }
229    }
230}
231
232impl<K: Array, V: Codec> Read for Variable<K, V> {
233    type Cfg = <V as Read>::Cfg;
234
235    fn read_cfg(buf: &mut impl Buf, cfg: &Self::Cfg) -> Result<Self, CodecError> {
236        match u8::read(buf)? {
237            SET_CONTEXT => {
238                let key = K::read(buf)?;
239                let value = V::read_cfg(buf, cfg)?;
240                Ok(Self::Set(key, value))
241            }
242            COMMIT_CONTEXT => Ok(Self::Commit()),
243            DELETE_CONTEXT => {
244                let key = K::read(buf)?;
245                Ok(Self::Delete(key))
246            }
247            UPDATE_CONTEXT => {
248                let key = K::read(buf)?;
249                let value = V::read_cfg(buf, cfg)?;
250                Ok(Self::Update(key, value))
251            }
252            COMMIT_FLOOR_CONTEXT => {
253                let floor_loc = u64::read(buf)?;
254                Ok(Self::CommitFloor(floor_loc))
255            }
256            e => Err(CodecError::InvalidEnum(e)),
257        }
258    }
259}
260
261impl<K: Array, V: Array> Display for Fixed<K, V> {
262    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
263        match self {
264            Fixed::Delete(key) => write!(f, "[key:{key} <deleted>]"),
265            Fixed::Update(key, value) => write!(f, "[key:{key} value:{value}]"),
266            Fixed::CommitFloor(loc) => write!(f, "[commit with inactivity floor: {loc}]"),
267        }
268    }
269}
270
271impl<K: Array, V: Array> Display for Variable<K, V> {
272    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
273        match self {
274            Variable::Set(key, value) => write!(f, "[key:{key} value:{value}]"),
275            Variable::Commit() => write!(f, "[commit]"),
276            Variable::Delete(key) => write!(f, "[key:{key} <deleted>]"),
277            Variable::Update(key, value) => write!(f, "[key:{key} value:{value}]"),
278            Variable::CommitFloor(loc) => write!(f, "[commit with inactivity floor: {loc}]"),
279        }
280    }
281}
282
283#[cfg(test)]
284mod tests {
285    use super::*;
286    use commonware_codec::{DecodeExt, Encode};
287    use commonware_utils::sequence::U64;
288
289    #[test]
290    fn test_to_key() {
291        let key = U64::new(1234);
292        let value = U64::new(56789);
293
294        let update_op = Fixed::Update(key.clone(), value.clone());
295        assert_eq!(&key, update_op.to_key().unwrap());
296
297        let delete_op = Fixed::<U64, U64>::Delete(key.clone());
298        assert_eq!(&key, delete_op.to_key().unwrap());
299
300        let commit_op = Fixed::<U64, U64>::CommitFloor(42);
301        assert_eq!(None, commit_op.to_key());
302    }
303
304    #[test]
305    fn test_to_value() {
306        let key = U64::new(1234);
307        let value = U64::new(56789);
308
309        let update_op = Fixed::Update(key.clone(), value.clone());
310        assert_eq!(&value, update_op.to_value().unwrap());
311
312        let delete_op = Fixed::<U64, U64>::Delete(key.clone());
313        assert_eq!(None, delete_op.to_value());
314
315        let commit_op = Fixed::<U64, U64>::CommitFloor(42);
316        assert_eq!(None, commit_op.to_value());
317    }
318
319    #[test]
320    fn test_operation_array_basic() {
321        let key = U64::new(1234);
322        let value = U64::new(56789);
323
324        let update_op = Fixed::Update(key.clone(), value.clone());
325        assert_eq!(&key, update_op.to_key().unwrap());
326        assert_eq!(&value, update_op.to_value().unwrap());
327
328        let from = Fixed::<U64, U64>::decode(update_op.encode()).unwrap();
329        assert_eq!(&key, from.to_key().unwrap());
330        assert_eq!(&value, from.to_value().unwrap());
331        assert_eq!(update_op, from);
332
333        let key2 = U64::new(42);
334        let delete_op = Fixed::<U64, U64>::Delete(key2.clone());
335        let from = Fixed::<U64, U64>::decode(delete_op.encode()).unwrap();
336        assert_eq!(&key2, from.to_key().unwrap());
337        assert_eq!(None, from.to_value());
338        assert_eq!(delete_op, from);
339
340        let commit_op = Fixed::<U64, U64>::CommitFloor(42);
341        let from = Fixed::<U64, U64>::decode(commit_op.encode()).unwrap();
342        assert_eq!(None, from.to_value());
343        assert!(matches!(from, Fixed::CommitFloor(42)));
344        assert_eq!(commit_op, from);
345
346        // test non-zero byte detection in delete operation
347        let mut invalid = delete_op.encode();
348        invalid[U64::SIZE + 4] = 0xFF;
349        let decoded = Fixed::<U64, U64>::decode(invalid.as_ref());
350        assert!(matches!(decoded.unwrap_err(), CodecError::Invalid(_, _)));
351
352        // test invalid context byte detection
353        let mut invalid = delete_op.encode();
354        invalid[0] = 0xFF;
355        let decoded = Fixed::<U64, U64>::decode(invalid.as_ref());
356        assert!(matches!(
357            decoded.unwrap_err(),
358            CodecError::InvalidEnum(0xFF)
359        ));
360
361        // test invalid length detection
362        let mut invalid = delete_op.encode().to_vec();
363        invalid.pop();
364        let decoded = Fixed::<U64, U64>::decode(invalid.as_ref());
365        assert!(matches!(decoded.unwrap_err(), CodecError::EndOfBuffer));
366    }
367
368    #[test]
369    fn test_operation_array_display() {
370        let key = U64::new(1234);
371        let value = U64::new(56789);
372        let update_op = Fixed::Update(key.clone(), value.clone());
373        assert_eq!(format!("{update_op}"), format!("[key:{key} value:{value}]"));
374
375        let key2 = U64::new(42);
376        let delete_op = Fixed::<U64, U64>::Delete(key2.clone());
377        assert_eq!(format!("{delete_op}"), format!("[key:{key2} <deleted>]"));
378    }
379
380    #[test]
381    fn test_operation_array_codec() {
382        let key = U64::new(1234);
383        let value = U64::new(5678);
384        let update_op = Fixed::Update(key, value);
385
386        let encoded = update_op.encode();
387        assert_eq!(encoded.len(), Fixed::<U64, U64>::SIZE);
388
389        let decoded = Fixed::<U64, U64>::decode(encoded).unwrap();
390        assert_eq!(update_op, decoded);
391    }
392}
commonware_storage/store/operation.rs

commonware_storage/store/
operation.rs
