miden_core/advice/
map.rs

1use alloc::{
2    collections::{
3        BTreeMap,
4        btree_map::{Entry, IntoIter},
5    },
6    sync::Arc,
7    vec::Vec,
8};
9
10#[cfg(feature = "serde")]
11use serde::{Deserialize, Serialize};
12
13use crate::{
14    Felt, WORD_SIZE, Word,
15    crypto::hash::Poseidon2,
16    serde::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable},
17};
18
19// ADVICE MAP
20// ================================================================================================
21
22/// Defines a set of non-deterministic (advice) inputs which the VM can access by their keys.
23///
24/// Each key maps to one or more field element. To access the elements, the VM can move the values
25/// associated with a given key onto the advice stack using `adv.push_mapval` instruction. The VM
26/// can also insert new values into the advice map during execution.
27///
28/// This type is a policy-free container. Execution-specific size limits for live advice map state
29/// are enforced by the processor's `AdviceProvider`, which owns the active execution options and
30/// live resource accounting.
31#[derive(Debug, Clone, Default, PartialEq, Eq)]
32#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
33#[cfg_attr(feature = "serde", serde(transparent))]
34#[cfg_attr(
35    all(feature = "arbitrary", test),
36    miden_test_serde_macros::serde_test(binary_serde(true))
37)]
38pub struct AdviceMap(BTreeMap<Word, Arc<[Felt]>>);
39
40/// Pair representing a key-value entry in an [`AdviceMap`]
41type MapEntry = (Word, Arc<[Felt]>);
42
43impl AdviceMap {
44    /// Returns the values associated with given key.
45    pub fn get(&self, key: &Word) -> Option<&Arc<[Felt]>> {
46        self.0.get(key)
47    }
48
49    /// Returns true if the key has a corresponding value in the map.
50    pub fn contains_key(&self, key: &Word) -> bool {
51        self.0.contains_key(key)
52    }
53
54    /// Inserts a value, returning the previous value if the key was already set.
55    pub fn insert(&mut self, key: Word, value: impl Into<Arc<[Felt]>>) -> Option<Arc<[Felt]>> {
56        self.0.insert(key, value.into())
57    }
58
59    /// Removes the value associated with the key and returns the removed element.
60    pub fn remove(&mut self, key: &Word) -> Option<Arc<[Felt]>> {
61        self.0.remove(key)
62    }
63
64    /// Return an iteration over all entries in the map.
65    pub fn iter(&self) -> impl Iterator<Item = (&Word, &Arc<[Felt]>)> {
66        self.0.iter()
67    }
68
69    /// Returns the number of key value pairs in the advice map.
70    pub fn len(&self) -> usize {
71        self.0.len()
72    }
73
74    /// Returns true if the advice map is empty.
75    pub fn is_empty(&self) -> bool {
76        self.0.is_empty()
77    }
78
79    /// Returns the total number of field elements stored in this advice map's keys and values.
80    ///
81    /// Each key is a word, so every entry contributes [`WORD_SIZE`] key elements plus the number
82    /// of value elements associated with that key. Returns `None` if the count overflows `usize`.
83    pub fn total_element_count(&self) -> Option<usize> {
84        self.0.values().try_fold(0usize, |total, values| {
85            WORD_SIZE
86                .checked_add(values.len())
87                .and_then(|entry_elements| total.checked_add(entry_elements))
88        })
89    }
90
91    /// Returns a commitment to this advice map.
92    ///
93    /// Entries are committed in key order. Each entry is hashed as the key elements followed by the
94    /// value elements. [`Poseidon2::hash_elements`] binds the entry length, and
95    /// [`Poseidon2::merge_many`] folds the ordered entry commitments into the final map
96    /// commitment.
97    pub fn commitment(&self) -> Word {
98        let entry_commitments = self
99            .iter()
100            .map(|(key, values)| {
101                let mut elements = Vec::with_capacity(WORD_SIZE + values.len());
102                elements.extend_from_slice(key.as_elements());
103                elements.extend_from_slice(values);
104                Poseidon2::hash_elements(&elements)
105            })
106            .collect::<Vec<_>>();
107
108        Poseidon2::merge_many(&entry_commitments)
109    }
110
111    /// Gets the given key's corresponding entry in the map for in-place manipulation.
112    pub fn entry(&mut self, key: Word) -> Entry<'_, Word, Arc<[Felt]>> {
113        self.0.entry(key)
114    }
115
116    /// Merges all entries from the given [`AdviceMap`] into the current advice map.
117    ///
118    /// If an entry from the new map already exists with the same key but different value,
119    /// an error is returned containing the existing entry along with the value that would replace
120    /// it. The current map remains unchanged.
121    pub fn merge(&mut self, other: &Self) -> Result<(), (MapEntry, Arc<[Felt]>)> {
122        if let Some(conflict) = self.find_conflicting_entry(other) {
123            Err(conflict)
124        } else {
125            self.merge_new(other);
126            Ok(())
127        }
128    }
129
130    /// Merges entries from `other`, but only for keys not already present in `self`.
131    fn merge_new(&mut self, other: &Self) {
132        for (key, value) in other.iter() {
133            self.0.entry(*key).or_insert_with(|| value.clone());
134        }
135    }
136
137    /// Finds the first key that exists in both `self` and `other` with different values.
138    ///
139    /// # Returns
140    /// - `Some` containing the conflicting key, its value from `self`, and the value from `other`.
141    /// - `None` if there are no conflicting values.
142    fn find_conflicting_entry(&self, other: &Self) -> Option<(MapEntry, Arc<[Felt]>)> {
143        for (key, new_value) in other.iter() {
144            if let Some(existing_value) = self.get(key)
145                && existing_value != new_value
146            {
147                // Found a conflict.
148                return Some(((*key, existing_value.clone()), new_value.clone()));
149            }
150        }
151        // No conflicts found.
152        None
153    }
154}
155
156impl From<BTreeMap<Word, Arc<[Felt]>>> for AdviceMap {
157    fn from(value: BTreeMap<Word, Arc<[Felt]>>) -> Self {
158        Self(value)
159    }
160}
161
162impl From<BTreeMap<Word, Vec<Felt>>> for AdviceMap {
163    fn from(value: BTreeMap<Word, Vec<Felt>>) -> Self {
164        value.into_iter().collect()
165    }
166}
167
168impl IntoIterator for AdviceMap {
169    type Item = (Word, Arc<[Felt]>);
170    type IntoIter = IntoIter<Word, Arc<[Felt]>>;
171
172    fn into_iter(self) -> Self::IntoIter {
173        self.0.into_iter()
174    }
175}
176
177impl<V> FromIterator<(Word, V)> for AdviceMap
178where
179    V: Into<Arc<[Felt]>>,
180{
181    fn from_iter<I>(iter: I) -> Self
182    where
183        I: IntoIterator<Item = (Word, V)>,
184    {
185        iter.into_iter()
186            .map(|(key, value)| (key, value.into()))
187            .collect::<BTreeMap<Word, Arc<[Felt]>>>()
188            .into()
189    }
190}
191
192impl<V> Extend<(Word, V)> for AdviceMap
193where
194    V: Into<Arc<[Felt]>>,
195{
196    fn extend<I>(&mut self, iter: I)
197    where
198        I: IntoIterator<Item = (Word, V)>,
199    {
200        self.0.extend(iter.into_iter().map(|(key, value)| (key, value.into())))
201    }
202}
203
204impl Serializable for AdviceMap {
205    fn write_into<W: ByteWriter>(&self, target: &mut W) {
206        target.write_usize(self.0.len());
207        for (key, values) in self.0.iter() {
208            target.write((key, values.to_vec()));
209        }
210    }
211}
212
213impl Deserializable for AdviceMap {
214    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
215        let mut map = BTreeMap::new();
216        let count = source.read_usize()?;
217        for _ in 0..count {
218            let (key, values): (Word, Vec<Felt>) = source.read()?;
219            map.insert(key, Arc::from(values));
220        }
221        Ok(Self(map))
222    }
223}
224
225#[cfg(test)]
226mod tests {
227    use super::*;
228
229    #[test]
230    fn test_advice_map_serialization() {
231        let mut map1 = AdviceMap::default();
232        map1.insert(Word::default(), vec![Felt::from_u32(1), Felt::from_u32(2)]);
233
234        let bytes = map1.to_bytes();
235
236        let map2 = AdviceMap::read_from_bytes(&bytes).unwrap();
237
238        assert_eq!(map1, map2);
239    }
240}
miden_core/advice/map.rs

miden_core/advice/
map.rs
