commonware_storage/qmdb/any/operation/
mod.rs

1use crate::{
2    merkle::{Family, Location},
3    qmdb::{any::value::ValueEncoding, operation::Committable},
4};
5use commonware_codec::{Encode as _, Error as CodecError, Read, Write};
6use commonware_formatting::hex;
7use commonware_runtime::{Buf, BufMut};
8use std::fmt;
9
10pub(crate) mod fixed;
11pub(crate) mod update;
12pub(crate) mod variable;
13pub use update::Update;
14
15pub(crate) const DELETE_CONTEXT: u8 = 0xD1;
16pub(crate) const UPDATE_CONTEXT: u8 = 0xD2;
17pub(crate) const COMMIT_CONTEXT: u8 = 0xD3;
18
19pub type Ordered<F, K, V> = Operation<F, update::Ordered<K, V>>;
20pub type Unordered<F, K, V> = Operation<F, update::Unordered<K, V>>;
21
22/// Delegates Operation-level codec (Write, Read) to the value encoding.
23///
24/// Fixed and variable encodings have different wire formats. Fixed pads to a uniform size,
25/// variable does not. A single blanket `impl Write for Operation<F, S>` dispatches here, while the
26/// two impls of this trait (on FixedEncoding and VariableEncoding) live on different Self types
27/// and therefore do not overlap.
28pub trait OperationCodec<F: Family, S: Update<ValueEncoding = Self>>:
29    ValueEncoding + Sized
30{
31    type ReadCfg: Clone + Send + Sync + 'static;
32
33    fn write_operation(op: &Operation<F, S>, buf: &mut impl BufMut);
34    fn read_operation(
35        buf: &mut impl Buf,
36        cfg: &Self::ReadCfg,
37    ) -> Result<Operation<F, S>, CodecError>;
38}
39
40#[derive(Clone, PartialEq, Debug)]
41pub enum Operation<F: Family, S: Update> {
42    Delete(S::Key),
43    Update(S),
44    CommitFloor(Option<S::Value>, Location<F>),
45}
46
47#[cfg(feature = "arbitrary")]
48impl<F: Family, S: Update> arbitrary::Arbitrary<'_> for Operation<F, S>
49where
50    S::Key: for<'a> arbitrary::Arbitrary<'a>,
51    S::Value: for<'a> arbitrary::Arbitrary<'a>,
52    S: for<'a> arbitrary::Arbitrary<'a>,
53{
54    fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
55        let choice = u.int_in_range(0..=2)?;
56        match choice {
57            0 => Ok(Self::Delete(u.arbitrary()?)),
58            1 => Ok(Self::Update(u.arbitrary()?)),
59            2 => Ok(Self::CommitFloor(u.arbitrary()?, u.arbitrary()?)),
60            _ => unreachable!(),
61        }
62    }
63}
64
65impl<F: Family, S: Update> crate::qmdb::operation::Operation<F> for Operation<F, S> {
66    type Key = S::Key;
67
68    fn key(&self) -> Option<&Self::Key> {
69        match self {
70            Self::Delete(k) => Some(k),
71            Self::Update(p) => Some(p.key()),
72            Self::CommitFloor(_, _) => None,
73        }
74    }
75
76    fn into_key(self) -> Option<Self::Key> {
77        match self {
78            Self::Delete(k) => Some(k),
79            Self::Update(p) => Some(p.into_key()),
80            Self::CommitFloor(_, _) => None,
81        }
82    }
83
84    fn is_update(&self) -> bool {
85        matches!(self, Self::Update(_))
86    }
87
88    fn is_delete(&self) -> bool {
89        matches!(self, Self::Delete(_))
90    }
91}
92
93impl<F: Family, S: Update> crate::qmdb::operation::Floored<F> for Operation<F, S> {
94    fn has_floor(&self) -> Option<Location<F>> {
95        match self {
96            Self::CommitFloor(_, loc) => Some(*loc),
97            _ => None,
98        }
99    }
100}
101
102impl<F: Family, S: Update> Committable for Operation<F, S> {
103    fn is_commit(&self) -> bool {
104        matches!(self, Self::CommitFloor(_, _))
105    }
106}
107
108// Blanket Write via delegation.
109impl<F: Family, S: Update> Write for Operation<F, S>
110where
111    S::ValueEncoding: OperationCodec<F, S>,
112{
113    fn write(&self, buf: &mut impl BufMut) {
114        S::ValueEncoding::write_operation(self, buf)
115    }
116}
117
118// Blanket Read via delegation.
119impl<F: Family, S: Update> Read for Operation<F, S>
120where
121    S::ValueEncoding: OperationCodec<F, S>,
122{
123    type Cfg = <S::ValueEncoding as OperationCodec<F, S>>::ReadCfg;
124
125    fn read_cfg(buf: &mut impl Buf, cfg: &Self::Cfg) -> Result<Self, CodecError> {
126        S::ValueEncoding::read_operation(buf, cfg)
127    }
128}
129
130impl<F: Family, S: Update> fmt::Display for Operation<F, S> {
131    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
132        match self {
133            Self::Delete(key) => write!(f, "[key:{} <deleted>]", hex(key)),
134            Self::Update(payload) => payload.fmt(f),
135            Self::CommitFloor(value, loc) => {
136                if let Some(value) = value {
137                    write!(
138                        f,
139                        "[commit {} with inactivity floor: {loc}]",
140                        hex(&value.encode())
141                    )
142                } else {
143                    write!(f, "[commit with inactivity floor: {loc}]")
144                }
145            }
146        }
147    }
148}
149
150#[cfg(test)]
151mod tests {
152    use super::*;
153    use crate::qmdb::any::value::{FixedEncoding, VariableEncoding};
154    use commonware_codec::{Codec, Decode, FixedSize, RangeCfg, Read};
155    use commonware_utils::sequence::FixedBytes;
156
157    type F = crate::merkle::mmr::Family;
158
159    fn roundtrip<T>(value: &T, cfg: &<T as Read>::Cfg)
160    where
161        T: Codec + PartialEq + std::fmt::Debug,
162    {
163        let encoded = value.encode();
164        let decoded = T::decode_cfg(encoded.clone(), cfg).expect("decode");
165        assert_eq!(decoded, *value);
166        let encoded2 = decoded.encode();
167        assert_eq!(encoded, encoded2);
168    }
169
170    #[test]
171    fn ordered_fixed_roundtrip() {
172        type K = FixedBytes<4>;
173        type V = u64;
174        type Op = Ordered<F, K, FixedEncoding<V>>;
175
176        let delete = Op::Delete(FixedBytes::from([1, 2, 3, 4]));
177        let update = Op::Update(update::Ordered {
178            key: FixedBytes::from([4, 3, 2, 1]),
179            value: 0xdead_beef_u64,
180            next_key: FixedBytes::from([9, 9, 9, 9]),
181        });
182        let commit_some = Op::CommitFloor(Some(123u64), crate::mmr::Location::new(5));
183        let commit_none = Op::CommitFloor(None, crate::mmr::Location::new(7));
184
185        roundtrip(&delete, &());
186        roundtrip(&update, &());
187        roundtrip(&commit_some, &());
188        roundtrip(&commit_none, &());
189    }
190
191    #[test]
192    fn unordered_fixed_roundtrip() {
193        type K = FixedBytes<4>;
194        type V = u64;
195        type Op = Unordered<F, K, FixedEncoding<V>>;
196
197        let delete = Op::Delete(FixedBytes::from([0, 0, 0, 1]));
198        let update = Op::Update(update::Unordered(FixedBytes::from([9, 8, 7, 6]), 77u64));
199        let commit = Op::CommitFloor(Some(555u64), crate::mmr::Location::new(3));
200
201        roundtrip(&delete, &());
202        roundtrip(&update, &());
203        roundtrip(&commit, &());
204    }
205
206    #[test]
207    fn fixed_commit_nonzero_trailing_padding_rejected() {
208        type K = FixedBytes<8>;
209        type V = u64;
210        type Op = Ordered<F, K, FixedEncoding<V>>;
211
212        // With 8-byte keys the update variant is the largest, so commit records carry trailing
213        // padding beyond the commit payload.
214        let op = Op::CommitFloor(None, crate::mmr::Location::new(7));
215        let mut buf: Vec<u8> = op.encode().to_vec();
216        assert!(buf.len() > 1 + 1 + u64::SIZE + u64::SIZE);
217        *buf.last_mut().unwrap() = 0x01;
218        assert!(Op::decode_cfg(buf.as_ref(), &()).is_err());
219    }
220
221    #[test]
222    fn ordered_variable_roundtrip() {
223        type K = FixedBytes<4>;
224        type V = Vec<u8>;
225        type Op = Ordered<F, K, VariableEncoding<V>>;
226        let cfg = ((), (RangeCfg::from(..), ()));
227
228        let delete = Op::Delete(FixedBytes::from([1, 1, 1, 1]));
229        let update = Op::Update(update::Ordered {
230            key: FixedBytes::from([2, 2, 2, 2]),
231            value: vec![1, 2, 3, 4, 5],
232            next_key: FixedBytes::from([3, 3, 3, 3]),
233        });
234        let commit_some = Op::CommitFloor(Some(vec![9, 9, 9]), crate::mmr::Location::new(9));
235        let commit_none = Op::CommitFloor(None, crate::mmr::Location::new(10));
236
237        roundtrip(&delete, &cfg);
238        roundtrip(&update, &cfg);
239        roundtrip(&commit_some, &cfg);
240        roundtrip(&commit_none, &cfg);
241    }
242
243    #[test]
244    fn unordered_variable_roundtrip() {
245        type K = FixedBytes<4>;
246        type V = Vec<u8>;
247        type Op = Unordered<F, K, VariableEncoding<V>>;
248        let cfg = ((), (RangeCfg::from(..), ()));
249
250        let delete = Op::Delete(FixedBytes::from([4, 4, 4, 4]));
251        let update = Op::Update(update::Unordered(
252            FixedBytes::from([5, 5, 5, 5]),
253            vec![7, 7, 7, 7],
254        ));
255        let commit = Op::CommitFloor(Some(vec![8, 8]), crate::mmr::Location::new(12));
256
257        roundtrip(&delete, &cfg);
258        roundtrip(&update, &cfg);
259        roundtrip(&commit, &cfg);
260    }
261
262    #[cfg(feature = "arbitrary")]
263    mod conformance {
264        use super::*;
265        use crate::{
266            merkle::{mmb, mmr},
267            qmdb::any::{
268                ordered::Operation as OrderedOperation, unordered::Operation as UnorderedOperation,
269            },
270        };
271        use commonware_codec::conformance::CodecConformance;
272        use commonware_utils::sequence::U64;
273
274        commonware_conformance::conformance_tests! {
275            CodecConformance<OrderedOperation<mmr::Family, U64, FixedEncoding<U64>>>,
276            CodecConformance<OrderedOperation<mmr::Family, U64, VariableEncoding<Vec<u8>>>>,
277            CodecConformance<UnorderedOperation<mmr::Family, U64, FixedEncoding<U64>>>,
278            CodecConformance<UnorderedOperation<mmr::Family, U64, VariableEncoding<Vec<u8>>>>,
279            CodecConformance<OrderedOperation<mmb::Family, U64, FixedEncoding<U64>>>,
280            CodecConformance<OrderedOperation<mmb::Family, U64, VariableEncoding<Vec<u8>>>>,
281            CodecConformance<UnorderedOperation<mmb::Family, U64, FixedEncoding<U64>>>,
282            CodecConformance<UnorderedOperation<mmb::Family, U64, VariableEncoding<Vec<u8>>>>,
283        }
284    }
285}
commonware_storage/qmdb/any/operation/mod.rs

commonware_storage/qmdb/any/operation/
mod.rs
