miden_core/mast/node/
call_node.rs

1use alloc::{boxed::Box, vec::Vec};
2use core::fmt;
3
4use miden_formatting::{
5    hex::ToHex,
6    prettier::{Document, PrettyPrint, const_text, nl, text},
7};
8#[cfg(feature = "serde")]
9use serde::{Deserialize, Serialize};
10
11use super::{MastForestContributor, MastNodeExt};
12#[cfg(debug_assertions)]
13use crate::mast::MastNode;
14use crate::{
15    Felt, Word,
16    chiplets::hasher,
17    mast::{
18        DecoratorId, DecoratorStore, MastForest, MastForestError, MastNodeFingerprint, MastNodeId,
19    },
20    operations::opcodes,
21    utils::{Idx, LookupByIdx},
22};
23
24// CALL NODE
25// ================================================================================================
26
27/// A Call node describes a function call such that the callee is executed in a different execution
28/// context from the currently executing code.
29///
30/// A call node can be of two types:
31/// - A simple call: the callee is executed in the new user context.
32/// - A syscall: the callee is executed in the root context.
33#[derive(Debug, Clone, PartialEq, Eq)]
34#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
35#[cfg_attr(all(feature = "arbitrary", test), miden_test_serde_macros::serde_test)]
36pub struct CallNode {
37    callee: MastNodeId,
38    is_syscall: bool,
39    digest: Word,
40    decorator_store: DecoratorStore,
41}
42
43//-------------------------------------------------------------------------------------------------
44/// Constants
45impl CallNode {
46    /// The domain of the call block (used for control block hashing).
47    pub const CALL_DOMAIN: Felt = Felt::new(opcodes::CALL as u64);
48    /// The domain of the syscall block (used for control block hashing).
49    pub const SYSCALL_DOMAIN: Felt = Felt::new(opcodes::SYSCALL as u64);
50}
51
52//-------------------------------------------------------------------------------------------------
53/// Public accessors
54impl CallNode {
55    /// Returns the ID of the node to be invoked by this call node.
56    pub fn callee(&self) -> MastNodeId {
57        self.callee
58    }
59
60    /// Returns true if this call node represents a syscall.
61    pub fn is_syscall(&self) -> bool {
62        self.is_syscall
63    }
64
65    /// Returns the domain of this call node.
66    pub fn domain(&self) -> Felt {
67        if self.is_syscall() {
68            Self::SYSCALL_DOMAIN
69        } else {
70            Self::CALL_DOMAIN
71        }
72    }
73}
74
75// PRETTY PRINTING
76// ================================================================================================
77
78impl CallNode {
79    pub(super) fn to_pretty_print<'a>(
80        &'a self,
81        mast_forest: &'a MastForest,
82    ) -> impl PrettyPrint + 'a {
83        CallNodePrettyPrint { node: self, mast_forest }
84    }
85
86    pub(super) fn to_display<'a>(&'a self, mast_forest: &'a MastForest) -> impl fmt::Display + 'a {
87        CallNodePrettyPrint { node: self, mast_forest }
88    }
89}
90
91struct CallNodePrettyPrint<'a> {
92    node: &'a CallNode,
93    mast_forest: &'a MastForest,
94}
95
96impl CallNodePrettyPrint<'_> {
97    /// Concatenates the provided decorators in a single line. If the list of decorators is not
98    /// empty, prepends `prepend` and appends `append` to the decorator document.
99    fn concatenate_decorators(
100        &self,
101        decorator_ids: &[DecoratorId],
102        prepend: Document,
103        append: Document,
104    ) -> Document {
105        let decorators = decorator_ids
106            .iter()
107            .map(|&decorator_id| self.mast_forest[decorator_id].render())
108            .reduce(|acc, doc| acc + const_text(" ") + doc)
109            .unwrap_or_default();
110
111        if decorators.is_empty() {
112            decorators
113        } else {
114            prepend + decorators + append
115        }
116    }
117
118    fn single_line_pre_decorators(&self) -> Document {
119        self.concatenate_decorators(
120            self.node.before_enter(self.mast_forest),
121            Document::Empty,
122            const_text(" "),
123        )
124    }
125
126    fn single_line_post_decorators(&self) -> Document {
127        self.concatenate_decorators(
128            self.node.after_exit(self.mast_forest),
129            const_text(" "),
130            Document::Empty,
131        )
132    }
133
134    fn multi_line_pre_decorators(&self) -> Document {
135        self.concatenate_decorators(self.node.before_enter(self.mast_forest), Document::Empty, nl())
136    }
137
138    fn multi_line_post_decorators(&self) -> Document {
139        self.concatenate_decorators(self.node.after_exit(self.mast_forest), nl(), Document::Empty)
140    }
141}
142
143impl PrettyPrint for CallNodePrettyPrint<'_> {
144    fn render(&self) -> Document {
145        let call_or_syscall = {
146            let callee_digest = self.mast_forest[self.node.callee].digest();
147            if self.node.is_syscall {
148                const_text("syscall")
149                    + const_text(".")
150                    + text(callee_digest.as_bytes().to_hex_with_prefix())
151            } else {
152                const_text("call")
153                    + const_text(".")
154                    + text(callee_digest.as_bytes().to_hex_with_prefix())
155            }
156        };
157
158        let single_line = self.single_line_pre_decorators()
159            + call_or_syscall.clone()
160            + self.single_line_post_decorators();
161        let multi_line =
162            self.multi_line_pre_decorators() + call_or_syscall + self.multi_line_post_decorators();
163
164        single_line | multi_line
165    }
166}
167
168impl fmt::Display for CallNodePrettyPrint<'_> {
169    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
170        use crate::prettier::PrettyPrint;
171        self.pretty_print(f)
172    }
173}
174
175// MAST NODE TRAIT IMPLEMENTATION
176// ================================================================================================
177
178impl MastNodeExt for CallNode {
179    /// Returns a commitment to this Call node.
180    ///
181    /// The commitment is computed as a hash of the callee and an empty word ([ZERO; 4]) in the
182    /// domain defined by either [Self::CALL_DOMAIN] or [Self::SYSCALL_DOMAIN], depending on
183    /// whether the node represents a simple call or a syscall - i.e.,:
184    /// ```
185    /// # use miden_core::mast::CallNode;
186    /// # use miden_crypto::{Word, hash::poseidon2::Poseidon2 as Hasher};
187    /// # let callee_digest = Word::default();
188    /// Hasher::merge_in_domain(&[callee_digest, Word::default()], CallNode::CALL_DOMAIN);
189    /// ```
190    /// or
191    /// ```
192    /// # use miden_core::mast::CallNode;
193    /// # use miden_crypto::{Word, hash::poseidon2::Poseidon2 as Hasher};
194    /// # let callee_digest = Word::default();
195    /// Hasher::merge_in_domain(&[callee_digest, Word::default()], CallNode::SYSCALL_DOMAIN);
196    /// ```
197    fn digest(&self) -> Word {
198        self.digest
199    }
200
201    /// Returns the decorators to be executed before this node is executed.
202    fn before_enter<'a>(&'a self, forest: &'a MastForest) -> &'a [DecoratorId] {
203        #[cfg(debug_assertions)]
204        self.verify_node_in_forest(forest);
205        self.decorator_store.before_enter(forest)
206    }
207
208    /// Returns the decorators to be executed after this node is executed.
209    fn after_exit<'a>(&'a self, forest: &'a MastForest) -> &'a [DecoratorId] {
210        #[cfg(debug_assertions)]
211        self.verify_node_in_forest(forest);
212        self.decorator_store.after_exit(forest)
213    }
214
215    fn to_display<'a>(&'a self, mast_forest: &'a MastForest) -> Box<dyn fmt::Display + 'a> {
216        Box::new(CallNode::to_display(self, mast_forest))
217    }
218
219    fn to_pretty_print<'a>(&'a self, mast_forest: &'a MastForest) -> Box<dyn PrettyPrint + 'a> {
220        Box::new(CallNode::to_pretty_print(self, mast_forest))
221    }
222
223    fn has_children(&self) -> bool {
224        true
225    }
226
227    fn append_children_to(&self, target: &mut Vec<MastNodeId>) {
228        target.push(self.callee());
229    }
230
231    fn for_each_child<F>(&self, mut f: F)
232    where
233        F: FnMut(MastNodeId),
234    {
235        f(self.callee());
236    }
237
238    fn domain(&self) -> Felt {
239        self.domain()
240    }
241
242    type Builder = CallNodeBuilder;
243
244    fn to_builder(self, forest: &MastForest) -> Self::Builder {
245        // Extract decorators from decorator_store if in Owned state
246        match self.decorator_store {
247            DecoratorStore::Owned { before_enter, after_exit, .. } => {
248                let mut builder = if self.is_syscall {
249                    CallNodeBuilder::new_syscall(self.callee)
250                } else {
251                    CallNodeBuilder::new(self.callee)
252                };
253                builder = builder.with_before_enter(before_enter).with_after_exit(after_exit);
254                builder
255            },
256            DecoratorStore::Linked { id } => {
257                // Extract decorators from forest storage when in Linked state
258                let before_enter = forest.before_enter_decorators(id).to_vec();
259                let after_exit = forest.after_exit_decorators(id).to_vec();
260                let mut builder = if self.is_syscall {
261                    CallNodeBuilder::new_syscall(self.callee)
262                } else {
263                    CallNodeBuilder::new(self.callee)
264                };
265                builder = builder.with_before_enter(before_enter).with_after_exit(after_exit);
266                builder
267            },
268        }
269    }
270
271    #[cfg(debug_assertions)]
272    fn verify_node_in_forest(&self, forest: &MastForest) {
273        if let Some(id) = self.decorator_store.linked_id() {
274            // Verify that this node is the one stored at the given ID in the forest
275            let self_ptr = self as *const Self;
276            let forest_node = &forest.nodes[id];
277            let forest_node_ptr = match forest_node {
278                MastNode::Call(call_node) => call_node as *const CallNode as *const (),
279                _ => panic!("Node type mismatch at {:?}", id),
280            };
281            let self_as_void = self_ptr as *const ();
282            debug_assert_eq!(
283                self_as_void, forest_node_ptr,
284                "Node pointer mismatch: expected node at {:?} to be self",
285                id
286            );
287        }
288    }
289}
290
291// ARBITRARY IMPLEMENTATION
292// ================================================================================================
293
294#[cfg(all(feature = "arbitrary", test))]
295impl proptest::prelude::Arbitrary for CallNode {
296    type Parameters = ();
297
298    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
299        use proptest::prelude::*;
300
301        use crate::Felt;
302
303        // Generate callee, digest, and whether it's a syscall
304        (any::<MastNodeId>(), any::<[u64; 4]>(), any::<bool>())
305            .prop_map(|(callee, digest_array, is_syscall)| {
306                // Generate a random digest
307                let digest = Word::from(digest_array.map(Felt::new));
308                // Construct directly to avoid MastForest validation for arbitrary data
309                CallNode {
310                    callee,
311                    is_syscall,
312                    digest,
313                    decorator_store: DecoratorStore::default(),
314                }
315            })
316            .no_shrink()  // Pure random values, no meaningful shrinking pattern
317            .boxed()
318    }
319
320    type Strategy = proptest::prelude::BoxedStrategy<Self>;
321}
322
323// ------------------------------------------------------------------------------------------------
324/// Builder for creating [`CallNode`] instances with decorators.
325#[derive(Debug)]
326pub struct CallNodeBuilder {
327    callee: MastNodeId,
328    is_syscall: bool,
329    before_enter: Vec<DecoratorId>,
330    after_exit: Vec<DecoratorId>,
331    digest: Option<Word>,
332}
333
334impl CallNodeBuilder {
335    /// Creates a new builder for a CallNode with the specified callee.
336    pub fn new(callee: MastNodeId) -> Self {
337        Self {
338            callee,
339            is_syscall: false,
340            before_enter: Vec::new(),
341            after_exit: Vec::new(),
342            digest: None,
343        }
344    }
345
346    /// Creates a new builder for a syscall CallNode with the specified callee.
347    pub fn new_syscall(callee: MastNodeId) -> Self {
348        Self {
349            callee,
350            is_syscall: true,
351            before_enter: Vec::new(),
352            after_exit: Vec::new(),
353            digest: None,
354        }
355    }
356
357    /// Builds the CallNode with the specified decorators.
358    pub fn build(self, mast_forest: &MastForest) -> Result<CallNode, MastForestError> {
359        if self.callee.to_usize() >= mast_forest.nodes.len() {
360            return Err(MastForestError::NodeIdOverflow(self.callee, mast_forest.nodes.len()));
361        }
362
363        // Use the forced digest if provided, otherwise compute the digest
364        let digest = if let Some(forced_digest) = self.digest {
365            forced_digest
366        } else {
367            let callee_digest = mast_forest[self.callee].digest();
368            let domain = if self.is_syscall {
369                CallNode::SYSCALL_DOMAIN
370            } else {
371                CallNode::CALL_DOMAIN
372            };
373
374            hasher::merge_in_domain(&[callee_digest, Word::default()], domain)
375        };
376
377        Ok(CallNode {
378            callee: self.callee,
379            is_syscall: self.is_syscall,
380            digest,
381            decorator_store: DecoratorStore::new_owned_with_decorators(
382                self.before_enter,
383                self.after_exit,
384            ),
385        })
386    }
387}
388
389impl MastForestContributor for CallNodeBuilder {
390    fn add_to_forest(self, forest: &mut MastForest) -> Result<MastNodeId, MastForestError> {
391        if self.callee.to_usize() >= forest.nodes.len() {
392            return Err(MastForestError::NodeIdOverflow(self.callee, forest.nodes.len()));
393        }
394
395        // Determine the node ID that will be assigned
396        let future_node_id = MastNodeId::new_unchecked(forest.nodes.len() as u32);
397
398        // Use the forced digest if provided, otherwise compute the digest directly
399        let digest = if let Some(forced_digest) = self.digest {
400            forced_digest
401        } else {
402            let callee_digest = forest[self.callee].digest();
403            let domain = if self.is_syscall {
404                CallNode::SYSCALL_DOMAIN
405            } else {
406                CallNode::CALL_DOMAIN
407            };
408
409            hasher::merge_in_domain(&[callee_digest, Word::default()], domain)
410        };
411
412        // Store node-level decorators in the centralized NodeToDecoratorIds for efficient access
413        forest.register_node_decorators(future_node_id, &self.before_enter, &self.after_exit);
414
415        // Create the node in the forest with Linked variant from the start
416        // Move the data directly without intermediate Owned node creation
417        let node_id = forest
418            .nodes
419            .push(
420                CallNode {
421                    callee: self.callee,
422                    is_syscall: self.is_syscall,
423                    digest,
424                    decorator_store: DecoratorStore::Linked { id: future_node_id },
425                }
426                .into(),
427            )
428            .map_err(|_| MastForestError::TooManyNodes)?;
429
430        Ok(node_id)
431    }
432
433    fn fingerprint_for_node(
434        &self,
435        forest: &MastForest,
436        hash_by_node_id: &impl LookupByIdx<MastNodeId, MastNodeFingerprint>,
437    ) -> Result<MastNodeFingerprint, MastForestError> {
438        // Use the fingerprint_from_parts helper function
439        crate::mast::node_fingerprint::fingerprint_from_parts(
440            forest,
441            hash_by_node_id,
442            &self.before_enter,
443            &self.after_exit,
444            &[self.callee],
445            // Use the forced digest if available, otherwise compute the digest
446            if let Some(forced_digest) = self.digest {
447                forced_digest
448            } else {
449                let callee_digest = forest[self.callee].digest();
450                let domain = if self.is_syscall {
451                    CallNode::SYSCALL_DOMAIN
452                } else {
453                    CallNode::CALL_DOMAIN
454                };
455
456                crate::chiplets::hasher::merge_in_domain(
457                    &[callee_digest, miden_crypto::Word::default()],
458                    domain,
459                )
460            },
461        )
462    }
463
464    fn remap_children(self, remapping: &impl LookupByIdx<MastNodeId, MastNodeId>) -> Self {
465        CallNodeBuilder {
466            callee: *remapping.get(self.callee).unwrap_or(&self.callee),
467            is_syscall: self.is_syscall,
468            before_enter: self.before_enter,
469            after_exit: self.after_exit,
470            digest: self.digest,
471        }
472    }
473
474    fn with_before_enter(mut self, decorators: impl Into<Vec<DecoratorId>>) -> Self {
475        self.before_enter = decorators.into();
476        self
477    }
478
479    fn with_after_exit(mut self, decorators: impl Into<Vec<DecoratorId>>) -> Self {
480        self.after_exit = decorators.into();
481        self
482    }
483
484    fn append_before_enter(&mut self, decorators: impl IntoIterator<Item = DecoratorId>) {
485        self.before_enter.extend(decorators);
486    }
487
488    fn append_after_exit(&mut self, decorators: impl IntoIterator<Item = DecoratorId>) {
489        self.after_exit.extend(decorators);
490    }
491
492    fn with_digest(mut self, digest: crate::Word) -> Self {
493        self.digest = Some(digest);
494        self
495    }
496}
497
498impl CallNodeBuilder {
499    /// Add this node to a forest using relaxed validation.
500    ///
501    /// This method is used during deserialization where nodes may reference child nodes
502    /// that haven't been added to the forest yet. The child node IDs have already been
503    /// validated against the expected final node count during the `try_into_mast_node_builder`
504    /// step, so we can safely skip validation here.
505    ///
506    /// Note: This is not part of the `MastForestContributor` trait because it's only
507    /// intended for internal use during deserialization.
508    pub(in crate::mast) fn add_to_forest_relaxed(
509        self,
510        forest: &mut MastForest,
511    ) -> Result<MastNodeId, MastForestError> {
512        // Use the forced digest if provided, otherwise use a default digest
513        // The actual digest computation will be handled when the forest is complete
514        let Some(digest) = self.digest else {
515            return Err(MastForestError::DigestRequiredForDeserialization);
516        };
517
518        let future_node_id = MastNodeId::new_unchecked(forest.nodes.len() as u32);
519
520        // Create the node in the forest with Linked variant from the start
521        // Note: Decorators are already in forest.debug_info from deserialization
522        // Move the data directly without intermediate cloning
523        let node_id = forest
524            .nodes
525            .push(
526                CallNode {
527                    callee: self.callee,
528                    is_syscall: self.is_syscall,
529                    digest,
530                    decorator_store: DecoratorStore::Linked { id: future_node_id },
531                }
532                .into(),
533            )
534            .map_err(|_| MastForestError::TooManyNodes)?;
535
536        Ok(node_id)
537    }
538}
539
540#[cfg(any(test, feature = "arbitrary"))]
541impl proptest::prelude::Arbitrary for CallNodeBuilder {
542    type Parameters = CallNodeBuilderParams;
543    type Strategy = proptest::strategy::BoxedStrategy<Self>;
544
545    fn arbitrary_with(params: Self::Parameters) -> Self::Strategy {
546        use proptest::prelude::*;
547
548        (
549            any::<MastNodeId>(),
550            any::<bool>(),
551            proptest::collection::vec(
552                super::arbitrary::decorator_id_strategy(params.max_decorator_id_u32),
553                0..=params.max_decorators,
554            ),
555            proptest::collection::vec(
556                super::arbitrary::decorator_id_strategy(params.max_decorator_id_u32),
557                0..=params.max_decorators,
558            ),
559        )
560            .prop_map(|(callee, is_syscall, before_enter, after_exit)| {
561                let mut builder = if is_syscall {
562                    Self::new_syscall(callee)
563                } else {
564                    Self::new(callee)
565                };
566                builder = builder.with_before_enter(before_enter).with_after_exit(after_exit);
567                builder
568            })
569            .boxed()
570    }
571}
572
573/// Parameters for generating CallNodeBuilder instances
574#[cfg(any(test, feature = "arbitrary"))]
575#[derive(Clone, Debug)]
576pub struct CallNodeBuilderParams {
577    pub max_decorators: usize,
578    pub max_decorator_id_u32: u32,
579}
580
581#[cfg(any(test, feature = "arbitrary"))]
582impl Default for CallNodeBuilderParams {
583    fn default() -> Self {
584        Self {
585            max_decorators: 4,
586            max_decorator_id_u32: 10,
587        }
588    }
589}
miden_core/mast/node/call_node.rs

miden_core/mast/node/
call_node.rs
