commonware_storage/adb/operation/fixed/
ordered.rs

1use crate::{
2    adb::operation::{self, fixed::FixedOperation},
3    mmr::Location,
4};
5use bytes::{Buf, BufMut};
6use commonware_codec::{
7    util::at_least, CodecFixed, Error as CodecError, FixedSize, Read, ReadExt as _, Write,
8};
9use commonware_utils::{hex, Array};
10use core::fmt::Display;
11
12/// An operation applied to an authenticated database with a fixed size value that supports
13/// exclusion proofs over ordered keys.
14#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
15pub enum Operation<K: Array + Ord, V: CodecFixed> {
16    /// Indicates the key no longer has a value.
17    Delete(K),
18
19    /// Indicates the key within the wrapped structure has the associated value and next-key.
20    Update(KeyData<K, V>),
21
22    /// Indicates all prior operations are no longer subject to rollback, and the floor on inactive
23    /// operations has been raised to the wrapped value.
24    CommitFloor(Location),
25}
26
27/// Data about a key in an ordered database or an ordered database operation.
28#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
29pub struct KeyData<K: Array + Ord, V: CodecFixed> {
30    /// The key that exists in the database or in the database operation.
31    pub key: K,
32    /// The value of `key` in the database or operation.
33    pub value: V,
34    /// The next-key of `key` in the database or operation.
35    ///
36    /// The next-key is the next active key that lexicographically follows it in the key space. If
37    /// the key is the lexicographically-last active key, then next-key is the
38    /// lexicographically-first of all active keys (in a DB with only one key, this means its
39    /// next-key is itself)
40    pub next_key: K,
41}
42
43impl<K: Array + Ord, V: CodecFixed> Operation<K, V> {
44    // For a compile-time assertion that operation's array size is large enough to handle the commit
45    // operation, which requires 9 bytes.
46    const _MIN_OPERATION_LEN: usize = 9;
47
48    /// Asserts that the size of `Self` is greater than the minimum operation size.
49    #[inline(always)]
50    const fn assert_valid_size() {
51        assert!(
52            Self::SIZE >= Self::_MIN_OPERATION_LEN,
53            "array size too small for commit op"
54        );
55    }
56}
57
58impl<K: Array + Ord, V: CodecFixed> Write for Operation<K, V> {
59    fn write(&self, buf: &mut impl BufMut) {
60        match &self {
61            Self::Delete(k) => {
62                operation::DELETE_CONTEXT.write(buf);
63                k.write(buf);
64                // Pad with 0 up to [Self::SIZE]
65                buf.put_bytes(0, Self::SIZE - 1 - K::SIZE);
66            }
67            Self::Update(data) => {
68                operation::UPDATE_CONTEXT.write(buf);
69                data.key.write(buf);
70                data.value.write(buf);
71                data.next_key.write(buf);
72            }
73            Self::CommitFloor(floor_loc) => {
74                operation::COMMIT_FLOOR_CONTEXT.write(buf);
75                buf.put_slice(&floor_loc.to_be_bytes());
76                // Pad with 0 up to [Self::SIZE]
77                buf.put_bytes(0, Self::SIZE - 1 - u64::SIZE);
78            }
79        }
80    }
81}
82
83impl<K: Array + Ord, V: CodecFixed> FixedSize for Operation<K, V> {
84    const SIZE: usize = u8::SIZE + K::SIZE + V::SIZE + K::SIZE;
85}
86
87impl<K: Array + Ord, V: CodecFixed<Cfg = ()>> FixedOperation for Operation<K, V> {
88    type Key = K;
89    type Value = V;
90
91    fn commit_floor(&self) -> Option<Location> {
92        match self {
93            Self::CommitFloor(loc) => Some(*loc),
94            _ => None,
95        }
96    }
97
98    fn key(&self) -> Option<&Self::Key> {
99        // TODO: Re-evaluate assertion placement after `generic_const_exprs` is stable.
100        const {
101            Self::assert_valid_size();
102        }
103
104        match self {
105            Self::Delete(key) => Some(key),
106            Self::Update(data) => Some(&data.key),
107            Self::CommitFloor(_) => None,
108        }
109    }
110
111    fn value(&self) -> Option<&Self::Value> {
112        // TODO: Re-evaluate assertion placement after `generic_const_exprs` is stable.
113        const {
114            Self::assert_valid_size();
115        }
116
117        match self {
118            Self::Delete(_) => None,
119            Self::Update(data) => Some(&data.value),
120            Self::CommitFloor(_) => None,
121        }
122    }
123
124    fn into_value(self) -> Option<Self::Value> {
125        // TODO: Re-evaluate assertion placement after `generic_const_exprs` is stable.
126        const {
127            Self::assert_valid_size();
128        }
129
130        match self {
131            Self::Delete(_) => None,
132            Self::Update(data) => Some(data.value),
133            Self::CommitFloor(_) => None,
134        }
135    }
136}
137
138impl<K: Array + Ord, V: CodecFixed> Read for Operation<K, V> {
139    type Cfg = <V as Read>::Cfg;
140
141    fn read_cfg(buf: &mut impl Buf, cfg: &Self::Cfg) -> Result<Self, CodecError> {
142        at_least(buf, Self::SIZE)?;
143
144        match u8::read(buf)? {
145            operation::UPDATE_CONTEXT => {
146                let key = K::read(buf)?;
147                let value = V::read_cfg(buf, cfg)?;
148                let next_key = K::read(buf)?;
149                Ok(Self::Update(KeyData {
150                    key,
151                    value,
152                    next_key,
153                }))
154            }
155            operation::DELETE_CONTEXT => {
156                let key = K::read(buf)?;
157                // Check that the value is all zeroes
158                for _ in 0..(Self::SIZE - 1 - K::SIZE) {
159                    if u8::read(buf)? != 0 {
160                        return Err(CodecError::Invalid(
161                            "storage::adb::operation::FixedOrdered",
162                            "delete value non-zero",
163                        ));
164                    }
165                }
166                Ok(Self::Delete(key))
167            }
168            operation::COMMIT_FLOOR_CONTEXT => {
169                let floor_loc = u64::read(buf)?;
170                let floor_loc = Location::new(floor_loc).ok_or_else(|| {
171                    CodecError::Invalid(
172                        "storage::adb::operation::fixed::ordered::Operation",
173                        "commit floor location overflow",
174                    )
175                })?;
176                for _ in 0..(Self::SIZE - 1 - u64::SIZE) {
177                    if u8::read(buf)? != 0 {
178                        return Err(CodecError::Invalid(
179                            "storage::adb::operation::fixed::ordered::Operation",
180                            "commit value non-zero",
181                        ));
182                    }
183                }
184                Ok(Self::CommitFloor(floor_loc))
185            }
186            e => Err(CodecError::InvalidEnum(e)),
187        }
188    }
189}
190
191impl<K: Array + Ord, V: CodecFixed> Display for Operation<K, V> {
192    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
193        match self {
194            Self::Delete(key) => write!(f, "[key:{key} <deleted>]"),
195            Self::Update(data) => {
196                write!(
197                    f,
198                    "[key:{} next_key:{} value:{}]",
199                    data.key,
200                    data.next_key,
201                    hex(&data.value.encode())
202                )
203            }
204            Self::CommitFloor(loc) => write!(f, "[commit with inactivity floor: {loc}]"),
205        }
206    }
207}
commonware_storage/adb/operation/fixed/ordered.rs

commonware_storage/adb/operation/fixed/
ordered.rs
