miden_objects/account/delta/
storage.rs

1use alloc::{
2    collections::{BTreeMap, btree_map::Entry},
3    string::ToString,
4    vec::Vec,
5};
6
7use super::{
8    AccountDeltaError, ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable,
9    Word,
10};
11use crate::{
12    Digest, EMPTY_WORD,
13    account::{AccountStorage, StorageMap, StorageSlot},
14};
15// ACCOUNT STORAGE DELTA
16// ================================================================================================
17
18/// [AccountStorageDelta] stores the differences between two states of account storage.
19///
20/// The delta consists of two maps:
21/// - A map containing the updates to value storage slots. The keys in this map are indexes of the
22///   updated storage slots and the values are the new values for these slots.
23/// - A map containing updates to storage maps. The keys in this map are indexes of the updated
24///   storage slots and the values are corresponding storage map delta objects.
25#[derive(Clone, Debug, Default, PartialEq, Eq)]
26pub struct AccountStorageDelta {
27    values: BTreeMap<u8, Word>,
28    maps: BTreeMap<u8, StorageMapDelta>,
29}
30
31impl AccountStorageDelta {
32    /// Creates a new storage delta from the provided fields.
33    pub fn new(
34        values: BTreeMap<u8, Word>,
35        maps: BTreeMap<u8, StorageMapDelta>,
36    ) -> Result<Self, AccountDeltaError> {
37        let result = Self { values, maps };
38        result.validate()?;
39
40        Ok(result)
41    }
42
43    /// Returns a reference to the updated values in this storage delta.
44    pub fn values(&self) -> &BTreeMap<u8, Word> {
45        &self.values
46    }
47
48    /// Returns a reference to the updated maps in this storage delta.
49    pub fn maps(&self) -> &BTreeMap<u8, StorageMapDelta> {
50        &self.maps
51    }
52
53    /// Returns true if storage delta contains no updates.
54    pub fn is_empty(&self) -> bool {
55        self.values.is_empty() && self.maps.is_empty()
56    }
57
58    /// Tracks a slot change
59    pub fn set_item(&mut self, slot_index: u8, new_slot_value: Word) {
60        self.values.insert(slot_index, new_slot_value);
61    }
62
63    /// Tracks a map item change
64    pub fn set_map_item(&mut self, slot_index: u8, key: Digest, new_value: Word) {
65        self.maps.entry(slot_index).or_default().insert(key, new_value);
66    }
67
68    /// Merges another delta into this one, overwriting any existing values.
69    pub fn merge(&mut self, other: Self) -> Result<(), AccountDeltaError> {
70        self.values.extend(other.values);
71
72        // merge maps
73        for (slot, update) in other.maps.into_iter() {
74            match self.maps.entry(slot) {
75                Entry::Vacant(entry) => {
76                    entry.insert(update);
77                },
78                Entry::Occupied(mut entry) => entry.get_mut().merge(update),
79            }
80        }
81
82        self.validate()
83    }
84
85    /// Checks whether this storage delta is valid.
86    ///
87    /// # Errors:
88    /// - Any of the updated slot is referenced from both maps (e.g., updated twice).
89    fn validate(&self) -> Result<(), AccountDeltaError> {
90        for slot in self.maps.keys() {
91            if self.values.contains_key(slot) {
92                return Err(AccountDeltaError::StorageSlotUsedAsDifferentTypes(*slot));
93            }
94        }
95
96        Ok(())
97    }
98
99    /// Returns an iterator of all the cleared storage slots.
100    fn cleared_slots(&self) -> impl Iterator<Item = u8> + '_ {
101        self.values
102            .iter()
103            .filter(|&(_, value)| (value == &EMPTY_WORD))
104            .map(|(slot, _)| *slot)
105    }
106
107    /// Returns an iterator of all the updated storage slots.
108    fn updated_slots(&self) -> impl Iterator<Item = (&u8, &Word)> + '_ {
109        self.values.iter().filter(|&(_, value)| value != &EMPTY_WORD)
110    }
111}
112
113#[cfg(any(feature = "testing", test))]
114impl AccountStorageDelta {
115    /// Creates an [AccountStorageDelta] from the given iterators.
116    pub fn from_iters(
117        cleared_items: impl IntoIterator<Item = u8>,
118        updated_values: impl IntoIterator<Item = (u8, Word)>,
119        updated_maps: impl IntoIterator<Item = (u8, StorageMapDelta)>,
120    ) -> Self {
121        Self {
122            values: BTreeMap::from_iter(
123                cleared_items.into_iter().map(|key| (key, EMPTY_WORD)).chain(updated_values),
124            ),
125            maps: BTreeMap::from_iter(updated_maps),
126        }
127    }
128}
129
130/// Converts an [AccountStorage] into an [AccountStorageDelta] for initial delta construction.
131impl From<AccountStorage> for AccountStorageDelta {
132    fn from(storage: AccountStorage) -> Self {
133        let mut values = BTreeMap::new();
134        let mut maps = BTreeMap::new();
135        for (slot_idx, slot) in storage.into_iter().enumerate() {
136            let slot_idx: u8 = slot_idx.try_into().expect("slot index must fit into `u8`");
137            match slot {
138                StorageSlot::Value(value) => {
139                    values.insert(slot_idx, value);
140                },
141                StorageSlot::Map(map) => {
142                    maps.insert(slot_idx, map.into());
143                },
144            }
145        }
146
147        Self { values, maps }
148    }
149}
150
151impl Serializable for AccountStorageDelta {
152    fn write_into<W: ByteWriter>(&self, target: &mut W) {
153        let cleared: Vec<u8> = self.cleared_slots().collect();
154        let updated: Vec<(&u8, &Word)> = self.updated_slots().collect();
155
156        target.write_u8(cleared.len() as u8);
157        target.write_many(cleared.iter());
158
159        target.write_u8(updated.len() as u8);
160        target.write_many(updated.iter());
161
162        target.write_u8(self.maps.len() as u8);
163        target.write_many(self.maps.iter());
164    }
165
166    fn get_size_hint(&self) -> usize {
167        let u8_size = 0u8.get_size_hint();
168        let word_size = EMPTY_WORD.get_size_hint();
169
170        let mut storage_map_delta_size = 0;
171        for (slot, storage_map_delta) in self.maps.iter() {
172            // The serialized size of each entry is the combination of slot (key) and the delta
173            // (value).
174            storage_map_delta_size += slot.get_size_hint() + storage_map_delta.get_size_hint();
175        }
176
177        // Length Prefixes
178        u8_size * 3 +
179        // Cleared Slots
180        self.cleared_slots().count() * u8_size +
181        // Updated Slots
182        self.updated_slots().count() * (u8_size + word_size) +
183        // Storage Map Delta
184        storage_map_delta_size
185    }
186}
187
188impl Deserializable for AccountStorageDelta {
189    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
190        let mut values = BTreeMap::new();
191
192        let num_cleared_items = source.read_u8()? as usize;
193        for _ in 0..num_cleared_items {
194            let cleared_slot = source.read_u8()?;
195            values.insert(cleared_slot, EMPTY_WORD);
196        }
197
198        let num_updated_items = source.read_u8()? as usize;
199        for _ in 0..num_updated_items {
200            let (updated_slot, updated_value) = source.read()?;
201            values.insert(updated_slot, updated_value);
202        }
203
204        let num_maps = source.read_u8()? as usize;
205        let maps = source.read_many::<(u8, StorageMapDelta)>(num_maps)?.into_iter().collect();
206
207        Self::new(values, maps).map_err(|err| DeserializationError::InvalidValue(err.to_string()))
208    }
209}
210
211// STORAGE MAP DELTA
212// ================================================================================================
213
214/// [StorageMapDelta] stores the differences between two states of account storage maps.
215///
216/// The differences are represented as leaf updates: a map of updated item key ([Digest]) to
217/// value ([Word]). For cleared items the value is [EMPTY_WORD].
218#[derive(Clone, Debug, Default, PartialEq, Eq)]
219pub struct StorageMapDelta(BTreeMap<Digest, Word>);
220
221impl StorageMapDelta {
222    /// Creates a new storage map delta from the provided leaves.
223    pub fn new(map: BTreeMap<Digest, Word>) -> Self {
224        Self(map)
225    }
226
227    /// Returns a reference to the updated leaves in this storage map delta.
228    pub fn leaves(&self) -> &BTreeMap<Digest, Word> {
229        &self.0
230    }
231
232    /// Inserts an item into the storage map delta.
233    pub fn insert(&mut self, key: Digest, value: Word) {
234        self.0.insert(key, value);
235    }
236
237    /// Returns true if storage map delta contains no updates.
238    pub fn is_empty(&self) -> bool {
239        self.0.is_empty()
240    }
241
242    /// Merge `other` into this delta, giving precedence to `other`.
243    pub fn merge(&mut self, other: Self) {
244        // Aggregate the changes into a map such that `other` overwrites self.
245        self.0.extend(other.0);
246    }
247
248    /// Returns an iterator of all the cleared keys in the storage map.
249    fn cleared_keys(&self) -> impl Iterator<Item = &Digest> + '_ {
250        self.0.iter().filter(|&(_, value)| value == &EMPTY_WORD).map(|(key, _)| key)
251    }
252
253    /// Returns an iterator of all the updated entries in the storage map.
254    fn updated_entries(&self) -> impl Iterator<Item = (&Digest, &Word)> + '_ {
255        self.0.iter().filter(|&(_, value)| value != &EMPTY_WORD)
256    }
257}
258
259#[cfg(any(feature = "testing", test))]
260impl StorageMapDelta {
261    /// Creates a new [StorageMapDelta] from the provided iterators.
262    pub fn from_iters(
263        cleared_leaves: impl IntoIterator<Item = Word>,
264        updated_leaves: impl IntoIterator<Item = (Word, Word)>,
265    ) -> Self {
266        Self(BTreeMap::from_iter(
267            cleared_leaves
268                .into_iter()
269                .map(|key| (key.into(), EMPTY_WORD))
270                .chain(updated_leaves.into_iter().map(|(key, value)| (key.into(), value))),
271        ))
272    }
273}
274
275/// Converts a [StorageMap] into a [StorageMapDelta] for initial delta construction.
276impl From<StorageMap> for StorageMapDelta {
277    fn from(map: StorageMap) -> Self {
278        StorageMapDelta::new(map.into_entries())
279    }
280}
281
282impl Serializable for StorageMapDelta {
283    fn write_into<W: ByteWriter>(&self, target: &mut W) {
284        let cleared: Vec<&Digest> = self.cleared_keys().collect();
285        let updated: Vec<(&Digest, &Word)> = self.updated_entries().collect();
286
287        target.write_usize(cleared.len());
288        target.write_many(cleared.iter());
289
290        target.write_usize(updated.len());
291        target.write_many(updated.iter());
292    }
293
294    fn get_size_hint(&self) -> usize {
295        let word_size = EMPTY_WORD.get_size_hint();
296
297        let cleared_keys_count = self.cleared_keys().count();
298        let updated_entries_count = self.updated_entries().count();
299
300        // Cleared Keys
301        cleared_keys_count.get_size_hint() +
302        cleared_keys_count * Digest::SERIALIZED_SIZE +
303
304        // Updated Entries
305        updated_entries_count.get_size_hint() +
306        updated_entries_count * (Digest::SERIALIZED_SIZE + word_size)
307    }
308}
309
310impl Deserializable for StorageMapDelta {
311    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
312        let mut map = BTreeMap::new();
313
314        let cleared_count = source.read_usize()?;
315        for _ in 0..cleared_count {
316            let cleared_key = source.read()?;
317            map.insert(cleared_key, EMPTY_WORD);
318        }
319
320        let updated_count = source.read_usize()?;
321        for _ in 0..updated_count {
322            let (updated_key, updated_value) = source.read()?;
323            map.insert(updated_key, updated_value);
324        }
325
326        Ok(Self::new(map))
327    }
328}
329
330// TESTS
331// ================================================================================================
332
333#[cfg(test)]
334mod tests {
335    use super::{AccountStorageDelta, Deserializable, Serializable};
336    use crate::{
337        ONE, ZERO, account::StorageMapDelta, testing::storage::AccountStorageDeltaBuilder,
338    };
339
340    #[test]
341    fn account_storage_delta_validation() {
342        let delta = AccountStorageDelta::from_iters(
343            [1, 2, 3],
344            [(4, [ONE, ONE, ONE, ONE]), (5, [ONE, ONE, ONE, ZERO])],
345            [],
346        );
347        assert!(delta.validate().is_ok());
348
349        let bytes = delta.to_bytes();
350        assert_eq!(AccountStorageDelta::read_from_bytes(&bytes), Ok(delta));
351
352        // duplicate across cleared items and maps
353        let delta = AccountStorageDelta::from_iters(
354            [1, 2, 3],
355            [(2, [ONE, ONE, ONE, ONE]), (5, [ONE, ONE, ONE, ZERO])],
356            [(1, StorageMapDelta::default())],
357        );
358        assert!(delta.validate().is_err());
359
360        let bytes = delta.to_bytes();
361        assert!(AccountStorageDelta::read_from_bytes(&bytes).is_err());
362
363        // duplicate across updated items and maps
364        let delta = AccountStorageDelta::from_iters(
365            [1, 3],
366            [(2, [ONE, ONE, ONE, ONE]), (5, [ONE, ONE, ONE, ZERO])],
367            [(2, StorageMapDelta::default())],
368        );
369        assert!(delta.validate().is_err());
370
371        let bytes = delta.to_bytes();
372        assert!(AccountStorageDelta::read_from_bytes(&bytes).is_err());
373    }
374
375    #[test]
376    fn test_is_empty() {
377        let storage_delta = AccountStorageDelta::default();
378        assert!(storage_delta.is_empty());
379
380        let storage_delta = AccountStorageDelta::from_iters([1], [], []);
381        assert!(!storage_delta.is_empty());
382
383        let storage_delta = AccountStorageDelta::from_iters([], [(2, [ONE, ONE, ONE, ONE])], []);
384        assert!(!storage_delta.is_empty());
385
386        let storage_delta =
387            AccountStorageDelta::from_iters([], [], [(3, StorageMapDelta::default())]);
388        assert!(!storage_delta.is_empty());
389    }
390
391    #[test]
392    fn test_serde_account_storage_delta() {
393        let storage_delta = AccountStorageDelta::default();
394        let serialized = storage_delta.to_bytes();
395        let deserialized = AccountStorageDelta::read_from_bytes(&serialized).unwrap();
396        assert_eq!(deserialized, storage_delta);
397
398        let storage_delta = AccountStorageDelta::from_iters([1], [], []);
399        let serialized = storage_delta.to_bytes();
400        let deserialized = AccountStorageDelta::read_from_bytes(&serialized).unwrap();
401        assert_eq!(deserialized, storage_delta);
402
403        let storage_delta = AccountStorageDelta::from_iters([], [(2, [ONE, ONE, ONE, ONE])], []);
404        let serialized = storage_delta.to_bytes();
405        let deserialized = AccountStorageDelta::read_from_bytes(&serialized).unwrap();
406        assert_eq!(deserialized, storage_delta);
407
408        let storage_delta =
409            AccountStorageDelta::from_iters([], [], [(3, StorageMapDelta::default())]);
410        let serialized = storage_delta.to_bytes();
411        let deserialized = AccountStorageDelta::read_from_bytes(&serialized).unwrap();
412        assert_eq!(deserialized, storage_delta);
413    }
414
415    #[test]
416    fn test_serde_storage_map_delta() {
417        let storage_map_delta = StorageMapDelta::default();
418        let serialized = storage_map_delta.to_bytes();
419        let deserialized = StorageMapDelta::read_from_bytes(&serialized).unwrap();
420        assert_eq!(deserialized, storage_map_delta);
421
422        let storage_map_delta = StorageMapDelta::from_iters([[ONE, ONE, ONE, ONE]], []);
423        let serialized = storage_map_delta.to_bytes();
424        let deserialized = StorageMapDelta::read_from_bytes(&serialized).unwrap();
425        assert_eq!(deserialized, storage_map_delta);
426
427        let storage_map_delta =
428            StorageMapDelta::from_iters([], [([ZERO, ZERO, ZERO, ZERO], [ONE, ONE, ONE, ONE])]);
429        let serialized = storage_map_delta.to_bytes();
430        let deserialized = StorageMapDelta::read_from_bytes(&serialized).unwrap();
431        assert_eq!(deserialized, storage_map_delta);
432    }
433
434    #[rstest::rstest]
435    #[case::some_some(Some(1), Some(2), Some(2))]
436    #[case::none_some(None, Some(2), Some(2))]
437    #[case::some_none(Some(1), None, None)]
438    #[test]
439    fn merge_items(#[case] x: Option<u64>, #[case] y: Option<u64>, #[case] expected: Option<u64>) {
440        /// Creates a delta containing the item as an update if Some, else with the item cleared.
441        fn create_delta(item: Option<u64>) -> AccountStorageDelta {
442            const SLOT: u8 = 123;
443            let item = item.map(|x| (SLOT, [vm_core::Felt::new(x), ZERO, ZERO, ZERO]));
444
445            AccountStorageDeltaBuilder::default()
446                .add_cleared_items(item.is_none().then_some(SLOT))
447                .add_updated_values(item)
448                .build()
449                .unwrap()
450        }
451
452        let mut delta_x = create_delta(x);
453        let delta_y = create_delta(y);
454        let expected = create_delta(expected);
455
456        delta_x.merge(delta_y).unwrap();
457
458        assert_eq!(delta_x, expected);
459    }
460
461    #[rstest::rstest]
462    #[case::some_some(Some(1), Some(2), Some(2))]
463    #[case::none_some(None, Some(2), Some(2))]
464    #[case::some_none(Some(1), None, None)]
465    #[test]
466    fn merge_maps(#[case] x: Option<u64>, #[case] y: Option<u64>, #[case] expected: Option<u64>) {
467        fn create_delta(value: Option<u64>) -> StorageMapDelta {
468            let key = [vm_core::Felt::new(10), ZERO, ZERO, ZERO];
469            match value {
470                Some(value) => StorageMapDelta::from_iters(
471                    [],
472                    [(key, [vm_core::Felt::new(value), ZERO, ZERO, ZERO])],
473                ),
474                None => StorageMapDelta::from_iters([key], []),
475            }
476        }
477
478        let mut delta_x = create_delta(x);
479        let delta_y = create_delta(y);
480        let expected = create_delta(expected);
481
482        delta_x.merge(delta_y);
483
484        assert_eq!(delta_x, expected);
485    }
486}
miden_objects/account/delta/storage.rs

miden_objects/account/delta/
storage.rs
