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,
15    utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable},
16};
17
18// ADVICE MAP
19// ================================================================================================
20
21/// Defines a set of non-deterministic (advice) inputs which the VM can access by their keys.
22///
23/// Each key maps to one or more field element. To access the elements, the VM can move the values
24/// associated with a given key onto the advice stack using `adv.push_mapval` instruction. The VM
25/// can also insert new values into the advice map during execution.
26#[derive(Debug, Clone, Default, PartialEq, Eq)]
27#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
28#[cfg_attr(feature = "serde", serde(transparent))]
29#[cfg_attr(
30    all(feature = "arbitrary", test),
31    miden_test_serde_macros::serde_test(winter_serde(true))
32)]
33pub struct AdviceMap(BTreeMap<Word, Arc<[Felt]>>);
34
35/// Pair representing a key-value entry in an [`AdviceMap`]
36type MapEntry = (Word, Arc<[Felt]>);
37
38impl AdviceMap {
39    /// Returns the values associated with given key.
40    pub fn get(&self, key: &Word) -> Option<&Arc<[Felt]>> {
41        self.0.get(key)
42    }
43
44    /// Returns true if the key has a corresponding value in the map.
45    pub fn contains_key(&self, key: &Word) -> bool {
46        self.0.contains_key(key)
47    }
48
49    /// Inserts a value, returning the previous value if the key was already set.
50    pub fn insert(&mut self, key: Word, value: impl Into<Arc<[Felt]>>) -> Option<Arc<[Felt]>> {
51        self.0.insert(key, value.into())
52    }
53
54    /// Removes the value associated with the key and returns the removed element.
55    pub fn remove(&mut self, key: &Word) -> Option<Arc<[Felt]>> {
56        self.0.remove(key)
57    }
58
59    /// Return an iteration over all entries in the map.
60    pub fn iter(&self) -> impl Iterator<Item = (&Word, &Arc<[Felt]>)> {
61        self.0.iter()
62    }
63
64    /// Returns the number of key value pairs in the advice map.
65    pub fn len(&self) -> usize {
66        self.0.len()
67    }
68
69    /// Returns true if the advice map is empty.
70    pub fn is_empty(&self) -> bool {
71        self.0.is_empty()
72    }
73
74    /// Gets the given key's corresponding entry in the map for in-place manipulation.
75    pub fn entry(&mut self, key: Word) -> Entry<'_, Word, Arc<[Felt]>> {
76        self.0.entry(key)
77    }
78
79    /// Merges all entries from the given [`AdviceMap`] into the current advice map.
80    ///
81    /// If an entry from the new map already exists with the same key but different value,
82    /// an error is returned containing the existing entry along with the value that would replace
83    /// it. The current map remains unchanged.
84    pub fn merge(&mut self, other: &Self) -> Result<(), (MapEntry, Arc<[Felt]>)> {
85        if let Some(conflict) = self.find_conflicting_entry(other) {
86            Err(conflict)
87        } else {
88            self.merge_new(other);
89            Ok(())
90        }
91    }
92
93    /// Merges entries from `other`, but only for keys not already present in `self`.
94    fn merge_new(&mut self, other: &Self) {
95        for (key, value) in other.iter() {
96            self.0.entry(*key).or_insert_with(|| value.clone());
97        }
98    }
99
100    /// Finds the first key that exists in both `self` and `other` with different values.
101    ///
102    /// # Returns
103    /// - `Some` containing the conflicting key, its value from `self`, and the value from `other`.
104    /// - `None` if there are no conflicting values.
105    fn find_conflicting_entry(&self, other: &Self) -> Option<(MapEntry, Arc<[Felt]>)> {
106        for (key, new_value) in other.iter() {
107            if let Some(existing_value) = self.get(key)
108                && existing_value != new_value
109            {
110                // Found a conflict.
111                return Some(((*key, existing_value.clone()), new_value.clone()));
112            }
113        }
114        // No conflicts found.
115        None
116    }
117}
118
119impl From<BTreeMap<Word, Arc<[Felt]>>> for AdviceMap {
120    fn from(value: BTreeMap<Word, Arc<[Felt]>>) -> Self {
121        Self(value)
122    }
123}
124
125impl From<BTreeMap<Word, Vec<Felt>>> for AdviceMap {
126    fn from(value: BTreeMap<Word, Vec<Felt>>) -> Self {
127        value.into_iter().collect()
128    }
129}
130
131impl IntoIterator for AdviceMap {
132    type Item = (Word, Arc<[Felt]>);
133    type IntoIter = IntoIter<Word, Arc<[Felt]>>;
134
135    fn into_iter(self) -> Self::IntoIter {
136        self.0.into_iter()
137    }
138}
139
140impl<V> FromIterator<(Word, V)> for AdviceMap
141where
142    V: Into<Arc<[Felt]>>,
143{
144    fn from_iter<I>(iter: I) -> Self
145    where
146        I: IntoIterator<Item = (Word, V)>,
147    {
148        iter.into_iter()
149            .map(|(key, value)| (key, value.into()))
150            .collect::<BTreeMap<Word, Arc<[Felt]>>>()
151            .into()
152    }
153}
154
155impl<V> Extend<(Word, V)> for AdviceMap
156where
157    V: Into<Arc<[Felt]>>,
158{
159    fn extend<I>(&mut self, iter: I)
160    where
161        I: IntoIterator<Item = (Word, V)>,
162    {
163        self.0.extend(iter.into_iter().map(|(key, value)| (key, value.into())))
164    }
165}
166
167impl Serializable for AdviceMap {
168    fn write_into<W: ByteWriter>(&self, target: &mut W) {
169        target.write_usize(self.0.len());
170        for (key, values) in self.0.iter() {
171            target.write((key, values.to_vec()));
172        }
173    }
174}
175
176impl Deserializable for AdviceMap {
177    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
178        let mut map = BTreeMap::new();
179        let count = source.read_usize()?;
180        for _ in 0..count {
181            let (key, values): (Word, Vec<Felt>) = source.read()?;
182            map.insert(key, Arc::from(values));
183        }
184        Ok(Self(map))
185    }
186}
187
188#[cfg(test)]
189mod tests {
190    use super::*;
191
192    #[test]
193    fn test_advice_map_serialization() {
194        let mut map1 = AdviceMap::default();
195        map1.insert(Word::default(), vec![Felt::from(1u32), Felt::from(2u32)]);
196
197        let bytes = map1.to_bytes();
198
199        let map2 = AdviceMap::read_from_bytes(&bytes).unwrap();
200
201        assert_eq!(map1, map2);
202    }
203}
miden_core/advice/map.rs

miden_core/advice/
map.rs
