miden_processor/host/advice/
mod.rs

1use alloc::{
2    collections::{BTreeMap, BTreeSet},
3    vec::Vec,
4};
5
6use miden_core::{
7    Felt, Word,
8    advice::{AdviceInputs, AdviceMap, AdviceStack},
9    chiplets::hasher,
10    crypto::merkle::{InnerNodeInfo, MerkleError, MerklePath, MerkleStore, NodeIndex},
11};
12#[cfg(test)]
13use miden_core::{crypto::hash::Blake3_256, serde::Serializable};
14
15mod errors;
16pub use errors::AdviceError;
17
18use crate::{ExecutionOptions, host::AdviceMutation, processor::AdviceProviderInterface};
19
20// CONSTANTS
21// ================================================================================================
22
23const FELT_SIZE_BYTES: usize = Word::SERIALIZED_SIZE / Word::NUM_ELEMENTS;
24// A Merkle store entry contains the node value and its two children.
25const INTERNAL_NODE_SIZE_BYTES: usize = 3 * Word::SERIALIZED_SIZE;
26
27trait MerkleStoreBudget {
28    fn contains_internal_node(&self, root: Word) -> bool;
29
30    fn new_internal_node_count<I>(&self, roots: I) -> usize
31    where
32        I: IntoIterator<Item = Word>;
33
34    fn new_path_node_count(
35        &self,
36        index: u64,
37        node: Word,
38        path: &MerklePath,
39    ) -> Result<usize, MerkleError>;
40}
41
42impl MerkleStoreBudget for MerkleStore {
43    fn contains_internal_node(&self, root: Word) -> bool {
44        self.get_node(root, NodeIndex::root()).is_ok()
45    }
46
47    fn new_internal_node_count<I>(&self, roots: I) -> usize
48    where
49        I: IntoIterator<Item = Word>,
50    {
51        let mut seen_roots = BTreeSet::new();
52        let mut count = 0;
53
54        for root in roots {
55            if seen_roots.insert(root) && !self.contains_internal_node(root) {
56                count += 1;
57            }
58        }
59
60        count
61    }
62
63    fn new_path_node_count(
64        &self,
65        index: u64,
66        node: Word,
67        path: &MerklePath,
68    ) -> Result<usize, MerkleError> {
69        path.authenticated_nodes(index, node)
70            .map(|nodes| self.new_internal_node_count(nodes.map(|node| node.value)))
71    }
72}
73
74// ADVICE PROVIDER
75// ================================================================================================
76
77/// An advice provider is a component through which the VM can request nondeterministic inputs from
78/// the host (i.e., result of a computation performed outside of the VM), as well as insert new data
79/// into the advice provider to be recovered by the host after the program has finished executing.
80///
81/// The combined advice-provider size limit is enforced here because it is part of execution policy.
82/// The provider tracks logical byte usage across initial advice, host mutations, and system-event
83/// inserts.
84///
85/// An advice provider consists of the following components:
86/// 1. Advice stack, which is a LIFO data structure. The processor can move the elements from the
87///    advice stack onto the operand stack, as well as push new elements onto the advice stack. The
88///    Its elements count toward the combined advice-provider byte budget.
89/// 2. Advice map, which is a key-value map where keys are words (4 field elements) and values are
90///    vectors of field elements. The processor can push the values from the map onto the advice
91///    stack, as well as insert new values into the map.
92/// 3. Merkle store, which contains structured data reducible to Merkle paths. The VM can request
93///    Merkle paths from the store, as well as mutate it by updating or merging nodes contained in
94///    the store.
95#[derive(Debug, Clone, PartialEq, Eq)]
96pub struct AdviceProvider {
97    stack: AdviceStack,
98    map: AdviceMap,
99    store: MerkleStore,
100    merkle_store_node_count: usize,
101    advice_size_bytes: usize,
102    max_advice_size_bytes: usize,
103}
104
105impl Default for AdviceProvider {
106    fn default() -> Self {
107        Self::empty(&ExecutionOptions::default())
108    }
109}
110
111impl AdviceProvider {
112    /// Creates a new advice provider from the provided inputs and execution options.
113    ///
114    /// The advice map limits in `options` are enforced while loading the initial advice inputs.
115    pub fn new(inputs: AdviceInputs, options: &ExecutionOptions) -> Result<Self, AdviceError> {
116        let (stack, map, store) = inputs.into_parts();
117        let mut provider = Self::empty(options);
118        provider.check_advice_size_addition(0)?;
119        provider.extend_advice_stack(stack)?;
120        provider.extend_merkle_store(store.inner_nodes())?;
121        provider.extend_map(&map)?;
122        Ok(provider)
123    }
124
125    fn empty(options: &ExecutionOptions) -> Self {
126        let store = MerkleStore::default();
127        let merkle_store_node_count = store.num_internal_nodes();
128        let advice_size_bytes = merkle_store_node_count * INTERNAL_NODE_SIZE_BYTES;
129        Self {
130            stack: AdviceStack::new(),
131            map: AdviceMap::default(),
132            store,
133            merkle_store_node_count,
134            advice_size_bytes,
135            max_advice_size_bytes: options.max_advice_size_bytes(),
136        }
137    }
138
139    pub(crate) fn set_options(&mut self, options: &ExecutionOptions) -> Result<(), AdviceError> {
140        let advice_size_bytes = self.compute_advice_size_bytes()?;
141        let max = options.max_advice_size_bytes();
142        if advice_size_bytes > max {
143            return Err(AdviceError::SizeBudgetExceeded {
144                current: advice_size_bytes,
145                added: 0,
146                max,
147            });
148        }
149
150        self.advice_size_bytes = advice_size_bytes;
151        self.max_advice_size_bytes = max;
152        Ok(())
153    }
154
155    /// Applies the mutations given in order to the `AdviceProvider`.
156    pub fn apply_mutations(
157        &mut self,
158        mutations: impl IntoIterator<Item = AdviceMutation>,
159    ) -> Result<(), AdviceError> {
160        let mutations = mutations.into_iter().collect::<Vec<_>>();
161        self.validate_mutations(&mutations)?;
162        mutations.into_iter().try_for_each(|mutation| self.apply_mutation(mutation))
163    }
164
165    fn validate_mutations(&self, mutations: &[AdviceMutation]) -> Result<(), AdviceError> {
166        let mut added_bytes = 0usize;
167        let mut new_map_entries = BTreeMap::<Word, &[Felt]>::new();
168        let mut new_merkle_nodes = BTreeSet::new();
169
170        for mutation in mutations {
171            match mutation {
172                AdviceMutation::ExtendStack { stack } => {
173                    let added = Self::felt_bytes(stack.len())?;
174                    added_bytes = added_bytes
175                        .checked_add(added)
176                        .ok_or_else(|| self.budget_error(usize::MAX))?;
177                },
178                AdviceMutation::ExtendMap { map } => {
179                    for (key, values) in map.iter() {
180                        let values = values.as_ref();
181                        let existing_values = self
182                            .map
183                            .get(key)
184                            .map(AsRef::as_ref)
185                            .or_else(|| new_map_entries.get(key).copied());
186                        if let Some(existing_values) = existing_values {
187                            if existing_values != values {
188                                return Err(AdviceError::MapKeyAlreadyPresent {
189                                    key: *key,
190                                    prev_values: existing_values.to_vec(),
191                                    new_values: values.to_vec(),
192                                });
193                            }
194                            continue;
195                        }
196
197                        new_map_entries.insert(*key, values);
198                        let added = Self::map_entry_bytes(values.len())?;
199                        added_bytes = added_bytes
200                            .checked_add(added)
201                            .ok_or_else(|| self.budget_error(usize::MAX))?;
202                    }
203                },
204                AdviceMutation::ExtendMerkleStore { inner_nodes } => {
205                    for node in inner_nodes {
206                        if !self.store.contains_internal_node(node.value)
207                            && new_merkle_nodes.insert(node.value)
208                        {
209                            added_bytes = added_bytes
210                                .checked_add(INTERNAL_NODE_SIZE_BYTES)
211                                .ok_or_else(|| self.budget_error(usize::MAX))?;
212                        }
213                    }
214                },
215            }
216        }
217
218        self.check_advice_size_addition(added_bytes)
219    }
220
221    fn apply_mutation(&mut self, mutation: AdviceMutation) -> Result<(), AdviceError> {
222        match mutation {
223            AdviceMutation::ExtendStack { stack } => {
224                self.extend_advice_stack(stack)?;
225            },
226            AdviceMutation::ExtendMap { map } => {
227                self.extend_map(&map)?;
228            },
229            AdviceMutation::ExtendMerkleStore { inner_nodes } => {
230                self.extend_merkle_store(inner_nodes)?;
231            },
232        }
233        Ok(())
234    }
235
236    /// Returns a stable fingerprint of the advice state.
237    ///
238    /// The fingerprint is insensitive to advice-map insertion order and Merkle-store insertion
239    /// order, but it still reflects advice-stack order.
240    #[cfg(test)]
241    #[must_use]
242    pub(crate) fn fingerprint(&self) -> [u8; 32] {
243        let stack = self.stack.iter().copied().collect::<Vec<_>>().to_bytes();
244        let map = self.map.to_bytes();
245        let mut store_nodes = self
246            .store
247            .inner_nodes()
248            .map(|info| (info.value, info.left, info.right))
249            .collect::<Vec<_>>();
250        store_nodes.sort_unstable_by(|lhs, rhs| {
251            lhs.0
252                .cmp(&rhs.0)
253                .then_with(|| lhs.1.cmp(&rhs.1))
254                .then_with(|| lhs.2.cmp(&rhs.2))
255        });
256        let store = store_nodes
257            .into_iter()
258            .flat_map(|(value, left, right)| [value, left, right])
259            .collect::<Vec<_>>()
260            .to_bytes();
261        Blake3_256::hash_iter([stack.as_slice(), map.as_slice(), store.as_slice()].into_iter())
262            .into()
263    }
264
265    // ADVICE STACK
266    // --------------------------------------------------------------------------------------------
267
268    /// Pops an element from the advice stack and returns it.
269    ///
270    /// # Errors
271    /// Returns an error if the advice stack is empty.
272    fn pop_stack(&mut self) -> Result<Felt, AdviceError> {
273        let value = self.stack.consume_element().ok_or(AdviceError::StackReadFailed)?;
274        self.advice_size_bytes -= FELT_SIZE_BYTES;
275        Ok(value)
276    }
277
278    /// Pops a word (4 elements) from the advice stack and returns it.
279    ///
280    /// Note: a word is popped off the stack element-by-element. For example, a `[d, c, b, a, ...]`
281    /// stack (i.e., `d` is at the top of the stack) will yield `[d, c, b, a]`.
282    ///
283    /// # Errors
284    /// Returns an error if the advice stack does not contain a full word.
285    fn pop_stack_word(&mut self) -> Result<Word, AdviceError> {
286        let value = self.stack.consume_word().ok_or(AdviceError::StackReadFailed)?;
287        self.advice_size_bytes -= Word::SERIALIZED_SIZE;
288        Ok(value)
289    }
290
291    /// Pops a double word (8 elements) from the advice stack and returns them.
292    ///
293    /// Note: words are popped off the stack element-by-element. For example, a
294    /// `[h, g, f, e, d, c, b, a, ...]` stack (i.e., `h` is at the top of the stack) will yield
295    /// two words: `[h, g, f,e ], [d, c, b, a]`.
296    ///
297    /// # Errors
298    /// Returns an error if the advice stack does not contain two words.
299    fn pop_stack_dword(&mut self) -> Result<[Word; 2], AdviceError> {
300        let value = self.stack.consume_dword().ok_or(AdviceError::StackReadFailed)?;
301        self.advice_size_bytes -= 2 * Word::SERIALIZED_SIZE;
302        Ok(value)
303    }
304
305    /// Checks that pushing `count` elements would not exceed the advice-provider size limit.
306    fn check_stack_capacity(&self, count: usize) -> Result<(), AdviceError> {
307        self.check_advice_size_addition(Self::felt_bytes(count)?)
308    }
309
310    /// Pushes a single value onto the advice stack.
311    pub fn push_stack(&mut self, value: Felt) -> Result<(), AdviceError> {
312        self.check_stack_capacity(1)?;
313        self.stack.push_element(value);
314        self.advice_size_bytes += FELT_SIZE_BYTES;
315        Ok(())
316    }
317
318    /// Pushes a word (4 elements) onto the stack.
319    pub fn push_stack_word(&mut self, word: &Word) -> Result<(), AdviceError> {
320        self.check_stack_capacity(Word::NUM_ELEMENTS)?;
321        self.stack.prepend_word(*word);
322        self.advice_size_bytes += Word::SERIALIZED_SIZE;
323        Ok(())
324    }
325
326    /// Fetches a list of elements under the specified key from the advice map and pushes them onto
327    /// the advice stack.
328    ///
329    /// If `include_len` is set to true, this also pushes the number of elements onto the advice
330    /// stack.
331    ///
332    /// If `pad_to` is not equal to 0, the elements list obtained from the advice map will be padded
333    /// with zeros, increasing its length to the next multiple of `pad_to`.
334    ///
335    /// Note: this operation doesn't consume the map element so it can be called multiple times
336    /// for the same key.
337    ///
338    /// # Example
339    /// Given an advice stack `[a, b, c, ...]`, and a map `x |-> [d, e, f]`:
340    ///
341    /// A call `push_stack(AdviceSource::Map { key: x, include_len: false, pad_to: 0 })` will result
342    /// in advice stack: `[d, e, f, a, b, c, ...]`.
343    ///
344    /// A call `push_stack(AdviceSource::Map { key: x, include_len: true, pad_to: 0 })` will result
345    /// in advice stack: `[3, d, e, f, a, b, c, ...]`.
346    ///
347    /// A call `push_stack(AdviceSource::Map { key: x, include_len: true, pad_to: 4 })` will result
348    /// in advice stack: `[3, d, e, f, 0, a, b, c, ...]`.
349    ///
350    /// # Errors
351    /// Returns an error if the key was not found in the key-value map.
352    pub fn push_from_map(
353        &mut self,
354        key: Word,
355        include_len: bool,
356        pad_to: u8,
357    ) -> Result<(), AdviceError> {
358        let values = self.map.get(&key).ok_or(AdviceError::MapKeyNotFound { key })?;
359
360        // Calculate total elements to push including padding and optional length prefix
361        let num_pad_elements = if pad_to != 0 {
362            values.len().next_multiple_of(pad_to as usize) - values.len()
363        } else {
364            0
365        };
366        let total_push = values
367            .len()
368            .checked_add(num_pad_elements)
369            .and_then(|n| n.checked_add(if include_len { 1 } else { 0 }))
370            .ok_or_else(|| self.budget_error(usize::MAX))?;
371        self.check_stack_capacity(total_push)?;
372
373        let mut stack = AdviceStack::new();
374        if include_len {
375            stack.append_element(Felt::new_unchecked(values.len() as u64));
376        }
377        stack.append_elements(values.iter().copied());
378
379        // if pad_to was provided (not equal 0), push some zeros to the advice stack so that the
380        // final (padded) elements list length will be the next multiple of pad_to
381        for _ in 0..num_pad_elements {
382            stack.append_element(Felt::default());
383        }
384        self.stack.prepend_stack(stack);
385        self.advice_size_bytes += Self::felt_bytes(total_push)?;
386        Ok(())
387    }
388
389    /// Returns the current stack as a vector ordered from top (index 0) to bottom.
390    pub fn stack(&self) -> Vec<Felt> {
391        self.stack.iter().copied().collect()
392    }
393
394    /// Extends the stack with typed advice stack values.
395    pub fn extend_advice_stack(&mut self, stack: AdviceStack) -> Result<(), AdviceError> {
396        self.check_stack_capacity(stack.len())?;
397        let added = Self::felt_bytes(stack.len())?;
398        self.stack.prepend_stack(stack);
399        self.advice_size_bytes += added;
400        Ok(())
401    }
402
403    // ADVICE MAP
404    // --------------------------------------------------------------------------------------------
405
406    /// Returns true if the key has a corresponding value in the map.
407    pub fn contains_map_key(&self, key: &Word) -> bool {
408        self.map.contains_key(key)
409    }
410
411    /// Returns a reference to the value(s) associated with the specified key in the advice map.
412    pub fn get_mapped_values(&self, key: &Word) -> Option<&[Felt]> {
413        self.map.get(key).map(AsRef::as_ref)
414    }
415
416    /// Returns the current advice map.
417    pub fn map(&self) -> &AdviceMap {
418        &self.map
419    }
420
421    fn budget_error(&self, added: usize) -> AdviceError {
422        AdviceError::SizeBudgetExceeded {
423            current: self.advice_size_bytes,
424            added,
425            max: self.max_advice_size_bytes,
426        }
427    }
428
429    fn felt_bytes(count: usize) -> Result<usize, AdviceError> {
430        count.checked_mul(FELT_SIZE_BYTES).ok_or(AdviceError::SizeBudgetExceeded {
431            current: 0,
432            added: usize::MAX,
433            max: 0,
434        })
435    }
436
437    fn map_entry_bytes(value_len: usize) -> Result<usize, AdviceError> {
438        Self::felt_bytes(value_len)?
439            .checked_add(Word::SERIALIZED_SIZE)
440            .ok_or(AdviceError::SizeBudgetExceeded { current: 0, added: usize::MAX, max: 0 })
441    }
442
443    fn merkle_node_bytes(count: usize) -> Result<usize, AdviceError> {
444        count
445            .checked_mul(INTERNAL_NODE_SIZE_BYTES)
446            .ok_or(AdviceError::SizeBudgetExceeded { current: 0, added: usize::MAX, max: 0 })
447    }
448
449    fn compute_advice_size_bytes(&self) -> Result<usize, AdviceError> {
450        let stack = Self::felt_bytes(self.stack.len())?;
451        let map_elements = self
452            .map
453            .total_element_count()
454            .ok_or(AdviceError::SizeBudgetExceeded { current: 0, added: usize::MAX, max: 0 })?;
455        let map = Self::felt_bytes(map_elements)?;
456        let store = Self::merkle_node_bytes(self.merkle_store_node_count)?;
457        stack.checked_add(map).and_then(|size| size.checked_add(store)).ok_or(
458            AdviceError::SizeBudgetExceeded {
459                current: 0,
460                added: usize::MAX,
461                max: self.max_advice_size_bytes,
462            },
463        )
464    }
465
466    fn check_advice_size_addition(&self, added: usize) -> Result<(), AdviceError> {
467        let Some(new_total) = self.advice_size_bytes.checked_add(added) else {
468            return Err(self.budget_error(added));
469        };
470        if new_total > self.max_advice_size_bytes {
471            return Err(self.budget_error(added));
472        }
473        Ok(())
474    }
475
476    fn check_merkle_store_node_addition(&self, added: usize) -> Result<(), AdviceError> {
477        self.check_advice_size_addition(Self::merkle_node_bytes(added)?)
478    }
479
480    pub(crate) fn check_map_value_allocation(&self, value_len: usize) -> Result<(), AdviceError> {
481        let added = Self::map_entry_bytes(value_len)?;
482        self.check_advice_size_addition(added)
483    }
484
485    /// Stores a VM-computed value, replacing any existing entry only after checking its budget.
486    /// Ordinary advice insertion retains its conflicting-value checks.
487    pub(crate) fn replace_into_map(
488        &mut self,
489        key: Word,
490        values: Vec<Felt>,
491    ) -> Result<(), AdviceError> {
492        let old_bytes =
493            self.map.get(&key).map_or(Ok(0), |values| Self::map_entry_bytes(values.len()))?;
494        let new_bytes = Self::map_entry_bytes(values.len())?;
495        self.check_advice_size_addition(new_bytes.saturating_sub(old_bytes))?;
496        self.map.insert(key, values);
497        self.advice_size_bytes = self.advice_size_bytes - old_bytes + new_bytes;
498        Ok(())
499    }
500
501    /// Inserts the provided value into the advice map under the specified key.
502    ///
503    /// The values in the advice map can be moved onto the advice stack by invoking
504    /// the [AdviceProvider::push_from_map()] method.
505    ///
506    /// Returns an error if the specified key is already present in the advice map.
507    pub fn insert_into_map(&mut self, key: Word, values: Vec<Felt>) -> Result<(), AdviceError> {
508        match self.map.get(&key) {
509            Some(existing_values) => {
510                let existing_values = existing_values.as_ref();
511                if existing_values != values {
512                    return Err(AdviceError::MapKeyAlreadyPresent {
513                        key,
514                        prev_values: existing_values.to_vec(),
515                        new_values: values,
516                    });
517                }
518            },
519            None => {
520                let added = Self::map_entry_bytes(values.len())?;
521                self.check_advice_size_addition(added)?;
522                self.map.insert(key, values);
523                self.advice_size_bytes += added;
524            },
525        }
526        Ok(())
527    }
528
529    /// Merges all entries from the given [`AdviceMap`] into the current advice map.
530    ///
531    /// Returns an error if any new entry already exists with the same key but a different value
532    /// than the one currently stored. The current map remains unchanged.
533    pub fn extend_map(&mut self, other: &AdviceMap) -> Result<(), AdviceError> {
534        let mut added = 0usize;
535        for (key, values) in other.iter() {
536            if let Some(existing_values) = self.map.get(key) {
537                if existing_values.as_ref() != values.as_ref() {
538                    return Err(AdviceError::MapKeyAlreadyPresent {
539                        key: *key,
540                        prev_values: existing_values.to_vec(),
541                        new_values: values.to_vec(),
542                    });
543                }
544                continue;
545            }
546
547            let entry_bytes = Self::map_entry_bytes(values.len())?;
548            added = added.checked_add(entry_bytes).ok_or_else(|| self.budget_error(usize::MAX))?;
549        }
550        self.check_advice_size_addition(added)?;
551
552        self.map.merge(other).map_err(|((key, prev_values), new_values)| {
553            AdviceError::MapKeyAlreadyPresent {
554                key,
555                prev_values: prev_values.to_vec(),
556                new_values: new_values.to_vec(),
557            }
558        })?;
559        self.advice_size_bytes += added;
560        Ok(())
561    }
562
563    // MERKLE STORE
564    // --------------------------------------------------------------------------------------------
565
566    /// Returns a node at the specified depth and index in a Merkle tree with the given root.
567    ///
568    /// # Errors
569    /// Returns an error if:
570    /// - A Merkle tree for the specified root cannot be found in this advice provider.
571    /// - The specified depth is either zero or greater than the depth of the Merkle tree identified
572    ///   by the specified root.
573    /// - Value of the node at the specified depth and index is not known to this advice provider.
574    pub fn get_tree_node(&self, root: Word, depth: Felt, index: Felt) -> Result<Word, AdviceError> {
575        let index = NodeIndex::from_elements(&depth, &index)
576            .map_err(|_| AdviceError::InvalidMerkleTreeNodeIndex { depth, index })?;
577        self.store.get_node(root, index).map_err(AdviceError::MerkleStoreLookupFailed)
578    }
579
580    /// Returns true if a path to a node at the specified depth and index in a Merkle tree with the
581    /// specified root exists in this Merkle store.
582    ///
583    /// # Errors
584    /// Returns an error if accessing the Merkle store fails.
585    pub fn has_merkle_path(
586        &self,
587        root: Word,
588        depth: Felt,
589        index: Felt,
590    ) -> Result<bool, AdviceError> {
591        let index = NodeIndex::from_elements(&depth, &index)
592            .map_err(|_| AdviceError::InvalidMerkleTreeNodeIndex { depth, index })?;
593
594        Ok(self.store.has_path(root, index))
595    }
596
597    /// Returns a path to a node at the specified depth and index in a Merkle tree with the
598    /// specified root.
599    ///
600    /// # Errors
601    /// Returns an error if:
602    /// - A Merkle tree for the specified root cannot be found in this advice provider.
603    /// - The specified depth is either zero or greater than the depth of the Merkle tree identified
604    ///   by the specified root.
605    /// - Path to the node at the specified depth and index is not known to this advice provider.
606    pub fn get_merkle_path(
607        &self,
608        root: Word,
609        depth: Felt,
610        index: Felt,
611    ) -> Result<MerklePath, AdviceError> {
612        let index = NodeIndex::from_elements(&depth, &index)
613            .map_err(|_| AdviceError::InvalidMerkleTreeNodeIndex { depth, index })?;
614        self.store
615            .get_path(root, index)
616            .map(|value| value.path)
617            .map_err(AdviceError::MerkleStoreLookupFailed)
618    }
619
620    /// Updates a node at the specified depth and index in a Merkle tree with the specified root;
621    /// returns the Merkle path from the updated node to the new root, together with the new root.
622    ///
623    /// # Errors
624    /// Returns an error if:
625    /// - A Merkle tree for the specified root cannot be found in this advice provider.
626    /// - The specified depth is either zero or greater than the depth of the Merkle tree identified
627    ///   by the specified root.
628    /// - Path to the leaf at the specified index in the specified Merkle tree is not known to this
629    ///   advice provider.
630    pub fn update_merkle_node(
631        &mut self,
632        root: Word,
633        depth: Felt,
634        index: Felt,
635        value: Word,
636    ) -> Result<(MerklePath, Word), AdviceError> {
637        let node_index = NodeIndex::from_elements(&depth, &index)
638            .map_err(|_| AdviceError::InvalidMerkleTreeNodeIndex { depth, index })?;
639        let proof = self
640            .store
641            .get_path(root, node_index)
642            .map_err(AdviceError::MerkleStoreUpdateFailed)?;
643        let path = proof.path;
644
645        if proof.value == value {
646            return Ok((path, root));
647        }
648
649        let added = self
650            .store
651            .new_path_node_count(node_index.position(), value, &path)
652            .map_err(AdviceError::MerkleStoreUpdateFailed)?;
653        self.check_merkle_store_node_addition(added)?;
654
655        let new_root = self
656            .store
657            .add_merkle_path(node_index.position(), value, path.clone())
658            .map_err(AdviceError::MerkleStoreUpdateFailed)?;
659        self.merkle_store_node_count += added;
660        self.advice_size_bytes += Self::merkle_node_bytes(added)?;
661        Ok((path, new_root))
662    }
663
664    /// Creates a new Merkle tree in the advice provider by combining Merkle trees with the
665    /// specified roots. The root of the new tree is defined as `hash(left_root, right_root)`.
666    ///
667    /// After the operation, both the original trees and the new tree remains in the advice
668    /// provider (i.e., the input trees are not removed).
669    ///
670    /// It is not checked whether a Merkle tree for either of the specified roots can be found in
671    /// this advice provider.
672    pub fn merge_roots(&mut self, lhs: Word, rhs: Word) -> Result<Word, AdviceError> {
673        let root = hasher::merge(&[lhs, rhs]);
674        let added = self.store.new_internal_node_count([root]);
675        self.check_merkle_store_node_addition(added)?;
676
677        let root = self.store.merge_roots(lhs, rhs).map_err(AdviceError::MerkleStoreMergeFailed)?;
678        self.merkle_store_node_count += added;
679        self.advice_size_bytes += Self::merkle_node_bytes(added)?;
680        Ok(root)
681    }
682
683    /// Returns true if the Merkle root exists for the advice provider Merkle store.
684    pub fn has_merkle_root(&self, root: Word) -> bool {
685        self.store.get_node(root, NodeIndex::root()).is_ok()
686    }
687
688    /// Extends the [MerkleStore] with the given nodes.
689    pub fn extend_merkle_store<I>(&mut self, iter: I) -> Result<(), AdviceError>
690    where
691        I: IntoIterator<Item = InnerNodeInfo>,
692    {
693        let nodes = iter.into_iter().collect::<Vec<_>>();
694        let added = self.store.new_internal_node_count(nodes.iter().map(|node| node.value));
695        self.check_merkle_store_node_addition(added)?;
696
697        self.store.extend(nodes);
698        self.merkle_store_node_count += added;
699        self.advice_size_bytes += Self::merkle_node_bytes(added)?;
700        Ok(())
701    }
702
703    // MUTATORS
704    // --------------------------------------------------------------------------------------------
705
706    /// Extends the contents of this instance with the contents of an `AdviceInputs`.
707    pub fn extend_from_inputs(&mut self, inputs: &AdviceInputs) -> Result<(), AdviceError> {
708        self.apply_mutations([
709            AdviceMutation::extend_advice_stack(inputs.stack()),
710            AdviceMutation::extend_merkle_store(inputs.store().inner_nodes()),
711            AdviceMutation::extend_map(inputs.map().clone()),
712        ])
713    }
714
715    /// Consumes `self` and return its parts (stack, map, store).
716    ///
717    /// The returned stack vector is ordered from top (index 0) to bottom.
718    pub fn into_parts(self) -> (Vec<Felt>, AdviceMap, MerkleStore) {
719        (self.stack.into_elements(), self.map, self.store)
720    }
721}
722
723// ADVICE PROVIDER INTERFACE IMPLEMENTATION
724// ================================================================================================
725
726impl AdviceProviderInterface for AdviceProvider {
727    #[inline(always)]
728    fn pop_stack(&mut self) -> Result<Felt, AdviceError> {
729        self.pop_stack()
730    }
731
732    #[inline(always)]
733    fn pop_stack_word(&mut self) -> Result<Word, AdviceError> {
734        self.pop_stack_word()
735    }
736
737    #[inline(always)]
738    fn pop_stack_dword(&mut self) -> Result<[Word; 2], AdviceError> {
739        self.pop_stack_dword()
740    }
741
742    #[inline(always)]
743    fn get_merkle_path(
744        &self,
745        root: Word,
746        depth: Felt,
747        index: Felt,
748    ) -> Result<Option<MerklePath>, AdviceError> {
749        self.get_merkle_path(root, depth, index).map(Some)
750    }
751
752    #[inline(always)]
753    fn update_merkle_node(
754        &mut self,
755        root: Word,
756        depth: Felt,
757        index: Felt,
758        value: Word,
759    ) -> Result<Option<MerklePath>, AdviceError> {
760        self.update_merkle_node(root, depth, index, value).map(|(path, _)| Some(path))
761    }
762}
763
764#[cfg(test)]
765mod tests {
766    use alloc::{collections::BTreeMap, vec, vec::Vec};
767
768    use miden_core::WORD_SIZE;
769
770    use super::AdviceProvider;
771    use crate::{
772        AdviceInputs, ExecutionOptions, Felt, Word,
773        advice::{AdviceError, AdviceMap, AdviceMutation, AdviceStack},
774        crypto::merkle::{MerkleStore, MerkleTree},
775    };
776
777    fn make_leaf(seed: u64) -> Word {
778        [
779            Felt::new_unchecked(seed),
780            Felt::new_unchecked(seed + 1),
781            Felt::new_unchecked(seed + 2),
782            Felt::new_unchecked(seed + 3),
783        ]
784        .into()
785    }
786
787    #[test]
788    fn fingerprint_is_stable_across_merkle_store_insertion_order() {
789        let tree_a =
790            MerkleTree::new([make_leaf(1), make_leaf(5), make_leaf(9), make_leaf(13)]).unwrap();
791        let tree_b =
792            MerkleTree::new([make_leaf(17), make_leaf(21), make_leaf(25), make_leaf(29)]).unwrap();
793
794        let mut store_a = MerkleStore::default();
795        store_a.extend(tree_a.inner_nodes());
796        store_a.extend(tree_b.inner_nodes());
797
798        let mut store_b = MerkleStore::default();
799        store_b.extend(tree_b.inner_nodes());
800        store_b.extend(tree_a.inner_nodes());
801
802        assert_eq!(store_a, store_b);
803
804        let provider_a = AdviceProvider::new(
805            AdviceInputs::default().with_merkle_store(store_a),
806            &Default::default(),
807        )
808        .unwrap();
809        let provider_b = AdviceProvider::new(
810            AdviceInputs::default().with_merkle_store(store_b),
811            &Default::default(),
812        )
813        .unwrap();
814
815        assert_eq!(provider_a, provider_b);
816        assert_eq!(provider_a.fingerprint(), provider_b.fingerprint());
817    }
818
819    #[test]
820    fn typed_advice_stack_mutation_prepends_values() {
821        let mut initial_stack = AdviceStack::new();
822        initial_stack.append_elements([Felt::new_unchecked(3), Felt::new_unchecked(4)]);
823        let mut mutation_stack = AdviceStack::new();
824        mutation_stack.append_elements([Felt::new_unchecked(1), Felt::new_unchecked(2)]);
825        let mut provider = AdviceProvider::new(
826            AdviceInputs::default().with_stack(initial_stack),
827            &Default::default(),
828        )
829        .unwrap();
830
831        provider
832            .apply_mutations([AdviceMutation::extend_advice_stack(mutation_stack)])
833            .unwrap();
834
835        assert_eq!(
836            provider.stack(),
837            vec![
838                Felt::new_unchecked(1),
839                Felt::new_unchecked(2),
840                Felt::new_unchecked(3),
841                Felt::new_unchecked(4)
842            ]
843        );
844    }
845
846    #[test]
847    fn default_advice_budget_accepts_protocol_lower_bound_and_rejects_over_limit() {
848        const NUM_NOTES: u64 = 1024;
849        const STORAGE_FELTS_PER_NOTE: usize = 1024;
850
851        let map = (0..NUM_NOTES).map(|seed| {
852            let key = make_leaf(seed * WORD_SIZE as u64);
853            (key, vec![Felt::ZERO; STORAGE_FELTS_PER_NOTE])
854        });
855        let inputs = AdviceInputs::default()
856            .with_stack(AdviceStack::from(vec![Felt::ZERO]))
857            .with_map(map);
858        let provider = AdviceProvider::new(inputs, &ExecutionOptions::default()).unwrap();
859        assert!(provider.advice_size_bytes > 8_445_856);
860
861        let base_size_bytes = AdviceProvider::default().advice_size_bytes;
862        let max_size_bytes = ExecutionOptions::DEFAULT_MAX_ADVICE_SIZE_BYTES;
863        assert_eq!(max_size_bytes, 16 * 1024 * 1024);
864        let felt_size_bytes = AdviceProvider::felt_bytes(1).unwrap();
865        let stack_len = (max_size_bytes - base_size_bytes) / felt_size_bytes + 1;
866        let inputs =
867            AdviceInputs::default().with_stack(AdviceStack::from(vec![Felt::ZERO; stack_len]));
868        let err = AdviceProvider::new(inputs, &ExecutionOptions::default()).unwrap_err();
869        assert!(matches!(
870            err,
871            AdviceError::SizeBudgetExceeded { max, .. } if max == max_size_bytes
872        ));
873    }
874
875    #[test]
876    fn advice_map_insert_respects_combined_budget() {
877        let base = AdviceProvider::default().advice_size_bytes;
878        let entry_bytes = AdviceProvider::map_entry_bytes(1).unwrap();
879        let options = ExecutionOptions::default().with_max_advice_size_bytes(base + entry_bytes);
880        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
881
882        provider.insert_into_map(make_leaf(0), vec![Felt::ONE]).unwrap();
883
884        let err = provider.insert_into_map(make_leaf(1), vec![Felt::ONE]).unwrap_err();
885        assert!(matches!(
886            err,
887            AdviceError::SizeBudgetExceeded { current, added, max }
888                if current == base + entry_bytes
889                    && added == entry_bytes
890                    && max == base + entry_bytes
891        ));
892
893        assert_eq!(provider.map.len(), 1);
894        assert!(provider.contains_map_key(&make_leaf(0)));
895        assert!(!provider.contains_map_key(&make_leaf(1)));
896    }
897
898    #[test]
899    fn advice_map_replace_accounts_for_growth_shrinkage_and_failure() {
900        for (old_len, new_len, below_limit) in [
901            (None, 3, false),
902            (None, 3, true),
903            (Some(1), 3, false),
904            (Some(1), 3, true),
905            (Some(3), 3, false),
906            (Some(5), 2, false),
907            (Some(0), 0, false),
908        ] {
909            let mut provider = AdviceProvider::default();
910            // Advice-stack storage remains charged when a map value is replaced.
911            provider.push_stack(Felt::ONE).unwrap();
912            let base = provider.advice_size_bytes;
913            let key = make_leaf(0);
914            if let Some(old_len) = old_len {
915                provider.insert_into_map(key, vec![Felt::ONE; old_len]).unwrap();
916            }
917            let expected = base + AdviceProvider::map_entry_bytes(new_len).unwrap();
918            let max = base
919                + AdviceProvider::map_entry_bytes(new_len.max(old_len.unwrap_or(0))).unwrap()
920                - usize::from(below_limit);
921            provider
922                .set_options(&ExecutionOptions::default().with_max_advice_size_bytes(max))
923                .unwrap();
924            let before = provider.clone();
925            let values = vec![Felt::from_u32(2); new_len];
926            let result = provider.replace_into_map(key, values.clone());
927            if below_limit {
928                assert!(
929                    matches!(result, Err(AdviceError::SizeBudgetExceeded { current, added, max: limit })
930                    if current == before.advice_size_bytes && added == expected - current && limit == max)
931                );
932                assert_eq!(provider, before);
933            } else {
934                result.unwrap();
935                assert_eq!(provider.get_mapped_values(&key), Some(values.as_slice()));
936                assert_eq!(provider.advice_size_bytes, expected);
937                assert_eq!(
938                    provider.advice_size_bytes,
939                    provider.compute_advice_size_bytes().unwrap()
940                );
941                // Repeated equal replacements are budget-neutral even at the exact ceiling.
942                provider.replace_into_map(key, values).unwrap();
943                for _ in 0..old_len.unwrap_or(0).saturating_sub(new_len) {
944                    provider.push_stack(Felt::ONE).unwrap();
945                }
946                assert!(matches!(
947                    provider.push_stack(Felt::ONE),
948                    Err(AdviceError::SizeBudgetExceeded { .. })
949                ));
950            }
951        }
952    }
953
954    #[test]
955    fn advice_map_extend_respects_combined_budget_atomically() {
956        let base = AdviceProvider::default().advice_size_bytes;
957        let entry_bytes = AdviceProvider::map_entry_bytes(1).unwrap();
958        let options =
959            ExecutionOptions::default().with_max_advice_size_bytes(base + 2 * entry_bytes);
960        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
961        provider.insert_into_map(make_leaf(0), vec![Felt::ONE]).unwrap();
962        let other = advice_map_from_entries(1..3, 1);
963
964        let err = provider.extend_map(&other).unwrap_err();
965        assert!(matches!(
966            err,
967            AdviceError::SizeBudgetExceeded { current, added, max }
968                if current == base + entry_bytes
969                    && added == 2 * entry_bytes
970                    && max == base + 2 * entry_bytes
971        ));
972
973        assert_eq!(provider.map.len(), 1);
974        assert!(provider.contains_map_key(&make_leaf(0)));
975        assert!(!provider.contains_map_key(&make_leaf(1)));
976        assert!(!provider.contains_map_key(&make_leaf(2)));
977    }
978
979    #[test]
980    fn initial_inputs_respect_combined_budget() {
981        let base = AdviceProvider::default().advice_size_bytes;
982        let stack = AdviceStack::from(vec![Felt::ONE]);
983        let inputs = AdviceInputs::default()
984            .with_stack(stack)
985            .with_map([(make_leaf(0), vec![Felt::ONE])]);
986        let felt_bytes = AdviceProvider::felt_bytes(1).unwrap();
987        let required = base + felt_bytes + AdviceProvider::map_entry_bytes(1).unwrap();
988        AdviceProvider::new(
989            inputs.clone(),
990            &ExecutionOptions::default().with_max_advice_size_bytes(required),
991        )
992        .unwrap();
993
994        let err = AdviceProvider::new(
995            inputs,
996            &ExecutionOptions::default().with_max_advice_size_bytes(required - felt_bytes),
997        )
998        .unwrap_err();
999        assert!(matches!(
1000            err,
1001            AdviceError::SizeBudgetExceeded { max, .. } if max == required - felt_bytes
1002        ));
1003    }
1004
1005    #[test]
1006    fn initial_merkle_store_respects_combined_budget() {
1007        let tree = merkle_tree_from_leaves(0..4);
1008        let store = merkle_store_from_tree(&tree);
1009        let node_bytes = AdviceProvider::merkle_node_bytes(1).unwrap();
1010        let required = AdviceProvider::merkle_node_bytes(store.num_internal_nodes()).unwrap();
1011        let options = ExecutionOptions::default().with_max_advice_size_bytes(required - node_bytes);
1012        let inputs = AdviceInputs::default().with_merkle_store(store);
1013
1014        let err = AdviceProvider::new(inputs, &options).unwrap_err();
1015        assert!(matches!(
1016            err,
1017            AdviceError::SizeBudgetExceeded { max, .. }
1018                if max == options.max_advice_size_bytes()
1019        ));
1020    }
1021
1022    #[test]
1023    fn merkle_store_extend_respects_combined_budget_atomically() {
1024        let base_node_count = MerkleStore::default().num_internal_nodes();
1025        let base = AdviceProvider::merkle_node_bytes(base_node_count).unwrap();
1026        let node_bytes = AdviceProvider::merkle_node_bytes(1).unwrap();
1027        let options = ExecutionOptions::default().with_max_advice_size_bytes(base + node_bytes);
1028        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
1029        let tree = merkle_tree_from_leaves(0..4);
1030
1031        let err = provider.extend_merkle_store(tree.inner_nodes()).unwrap_err();
1032        assert!(matches!(
1033            err,
1034            AdviceError::SizeBudgetExceeded { current, max, .. }
1035                if current == base && max == base + node_bytes
1036        ));
1037
1038        assert_eq!(provider.merkle_store_node_count, base_node_count);
1039        assert!(!provider.has_merkle_root(tree.root()));
1040    }
1041
1042    #[test]
1043    fn merkle_store_extend_allows_exact_combined_budget() {
1044        let base_node_count = MerkleStore::default().num_internal_nodes();
1045        let tree = merkle_tree_from_leaves(0..2);
1046        let options = ExecutionOptions::default().with_max_advice_size_bytes(
1047            AdviceProvider::merkle_node_bytes(base_node_count + 1).unwrap(),
1048        );
1049        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
1050
1051        provider.extend_merkle_store(tree.inner_nodes()).unwrap();
1052
1053        assert_eq!(provider.merkle_store_node_count, base_node_count + 1);
1054        assert!(provider.has_merkle_root(tree.root()));
1055    }
1056
1057    #[test]
1058    fn merkle_store_extend_counts_only_new_unique_nodes() {
1059        let base_node_count = MerkleStore::default().num_internal_nodes();
1060        let tree = merkle_tree_from_leaves(0..2);
1061        let options = ExecutionOptions::default().with_max_advice_size_bytes(
1062            AdviceProvider::merkle_node_bytes(base_node_count + 1).unwrap(),
1063        );
1064        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
1065        let nodes = tree.inner_nodes().collect::<Vec<_>>();
1066
1067        provider
1068            .extend_merkle_store(nodes.iter().cloned().chain(nodes.iter().cloned()))
1069            .unwrap();
1070        provider.extend_merkle_store(nodes).unwrap();
1071
1072        assert_eq!(provider.merkle_store_node_count, base_node_count + 1);
1073        assert!(provider.has_merkle_root(tree.root()));
1074    }
1075
1076    #[test]
1077    fn merkle_store_merge_respects_combined_budget_atomically() {
1078        let base_node_count = MerkleStore::default().num_internal_nodes();
1079        let base = AdviceProvider::merkle_node_bytes(base_node_count).unwrap();
1080        let node_bytes = AdviceProvider::merkle_node_bytes(1).unwrap();
1081        let options = ExecutionOptions::default().with_max_advice_size_bytes(base);
1082        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
1083
1084        let err = provider.merge_roots(make_leaf(0), make_leaf(4)).unwrap_err();
1085        assert!(matches!(
1086            err,
1087            AdviceError::SizeBudgetExceeded { current, added, max }
1088                if current == base && added == node_bytes && max == base
1089        ));
1090
1091        assert_eq!(provider.merkle_store_node_count, base_node_count);
1092    }
1093
1094    #[test]
1095    fn merkle_store_merge_counts_existing_parent_once() {
1096        let lhs = make_leaf(0);
1097        let rhs = make_leaf(4);
1098        let mut store = MerkleStore::default();
1099        let root = store.merge_roots(lhs, rhs).unwrap();
1100        let node_count = store.num_internal_nodes();
1101        let max_advice_size = AdviceProvider::merkle_node_bytes(node_count).unwrap();
1102        let options = ExecutionOptions::default().with_max_advice_size_bytes(max_advice_size);
1103        let mut provider =
1104            AdviceProvider::new(AdviceInputs::default().with_merkle_store(store), &options)
1105                .unwrap();
1106
1107        assert_eq!(provider.merge_roots(lhs, rhs).unwrap(), root);
1108        assert_eq!(provider.merkle_store_node_count, node_count);
1109    }
1110
1111    #[test]
1112    fn merkle_store_update_respects_combined_budget_atomically() {
1113        let tree = merkle_tree_from_leaves(0..4);
1114        let store = merkle_store_from_tree(&tree);
1115        let node_count = store.num_internal_nodes();
1116        let required = AdviceProvider::merkle_node_bytes(node_count).unwrap();
1117        let options = ExecutionOptions::default().with_max_advice_size_bytes(required);
1118        let inputs = AdviceInputs::default().with_merkle_store(store);
1119        let mut provider = AdviceProvider::new(inputs, &options).unwrap();
1120
1121        let err = provider
1122            .update_merkle_node(tree.root(), Felt::new_unchecked(2), Felt::ZERO, make_leaf(100))
1123            .unwrap_err();
1124        assert!(matches!(
1125            err,
1126            AdviceError::SizeBudgetExceeded { current, max, .. }
1127                if current == required && max == required
1128        ));
1129
1130        assert_eq!(provider.merkle_store_node_count, node_count);
1131        assert_eq!(
1132            provider.get_tree_node(tree.root(), Felt::new_unchecked(2), Felt::ZERO).unwrap(),
1133            make_leaf(0)
1134        );
1135    }
1136
1137    #[test]
1138    fn merkle_store_update_allows_exact_combined_budget() {
1139        let tree = merkle_tree_from_leaves(0..4);
1140        let store = merkle_store_from_tree(&tree);
1141        let mut staged = store.clone();
1142        staged
1143            .set_node(
1144                tree.root(),
1145                miden_core::crypto::merkle::NodeIndex::new(2, 0).unwrap(),
1146                make_leaf(100),
1147            )
1148            .unwrap();
1149        let options = ExecutionOptions::default().with_max_advice_size_bytes(
1150            AdviceProvider::merkle_node_bytes(staged.num_internal_nodes()).unwrap(),
1151        );
1152        let inputs = AdviceInputs::default().with_merkle_store(store);
1153        let mut provider = AdviceProvider::new(inputs, &options).unwrap();
1154
1155        provider
1156            .update_merkle_node(tree.root(), Felt::new_unchecked(2), Felt::ZERO, make_leaf(100))
1157            .unwrap();
1158
1159        assert_eq!(provider.merkle_store_node_count, staged.num_internal_nodes());
1160    }
1161
1162    #[test]
1163    fn stack_pop_releases_capacity_for_map_growth() {
1164        let base = AdviceProvider::default().advice_size_bytes;
1165        let entry_bytes = AdviceProvider::map_entry_bytes(1).unwrap();
1166        let stack = AdviceStack::from(vec![Felt::ONE; WORD_SIZE + 1]);
1167        let options = ExecutionOptions::default().with_max_advice_size_bytes(base + entry_bytes);
1168        let mut provider =
1169            AdviceProvider::new(AdviceInputs::default().with_stack(stack), &options).unwrap();
1170
1171        assert!(provider.insert_into_map(make_leaf(0), vec![Felt::ONE]).is_err());
1172        for _ in 0..WORD_SIZE + 1 {
1173            provider.pop_stack().unwrap();
1174        }
1175        provider.insert_into_map(make_leaf(0), vec![Felt::ONE]).unwrap();
1176    }
1177
1178    #[test]
1179    fn mutation_batches_are_atomic() {
1180        let base = AdviceProvider::default().advice_size_bytes;
1181        let options = ExecutionOptions::default()
1182            .with_max_advice_size_bytes(base + AdviceProvider::felt_bytes(1).unwrap());
1183        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
1184        let before = provider.clone();
1185        let mutations = [
1186            AdviceMutation::extend_advice_stack(AdviceStack::from(vec![Felt::ONE])),
1187            AdviceMutation::extend_advice_stack(AdviceStack::from(vec![Felt::ONE])),
1188        ];
1189
1190        assert!(provider.apply_mutations(mutations).is_err());
1191        assert_eq!(provider, before);
1192    }
1193
1194    #[test]
1195    fn mutation_batches_are_atomic_on_map_conflict() {
1196        let key = make_leaf(0);
1197        let mut provider = AdviceProvider::new(
1198            AdviceInputs::default().with_map([(key, vec![Felt::ONE])]),
1199            &ExecutionOptions::default(),
1200        )
1201        .unwrap();
1202        let before = provider.clone();
1203        let mutations = [
1204            AdviceMutation::extend_advice_stack(AdviceStack::from(vec![Felt::ONE])),
1205            AdviceMutation::extend_map(
1206                [(key, vec![Felt::new_unchecked(2)])]
1207                    .into_iter()
1208                    .collect::<BTreeMap<_, _>>()
1209                    .into(),
1210            ),
1211        ];
1212
1213        assert!(provider.apply_mutations(mutations).is_err());
1214        assert_eq!(provider, before);
1215    }
1216
1217    #[test]
1218    fn replacing_options_rejects_a_limit_below_current_usage() {
1219        let mut provider = AdviceProvider::default();
1220        let current = provider.advice_size_bytes;
1221        let err = provider
1222            .set_options(&ExecutionOptions::default().with_max_advice_size_bytes(current - 1))
1223            .unwrap_err();
1224        assert!(matches!(
1225            err,
1226            AdviceError::SizeBudgetExceeded { current: actual, added: 0, max }
1227                if actual == current && max == current - 1
1228        ));
1229    }
1230
1231    fn advice_map_from_entries(keys: impl Iterator<Item = u64>, value_len: usize) -> AdviceMap {
1232        keys.map(|key| {
1233            let values = (0..value_len)
1234                .map(|offset| Felt::new_unchecked(key + offset as u64))
1235                .collect::<Vec<_>>();
1236            (make_leaf(key), values)
1237        })
1238        .collect::<BTreeMap<_, _>>()
1239        .into()
1240    }
1241
1242    fn merkle_tree_from_leaves(keys: impl Iterator<Item = u64>) -> MerkleTree {
1243        MerkleTree::new(keys.map(make_leaf).collect::<Vec<_>>()).unwrap()
1244    }
1245
1246    fn merkle_store_from_tree(tree: &MerkleTree) -> MerkleStore {
1247        let mut store = MerkleStore::default();
1248        store.extend(tree.inner_nodes());
1249        store
1250    }
1251}
miden_processor/host/advice/mod.rs

miden_processor/host/advice/
mod.rs
