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, text},
7};
8#[cfg(feature = "serde")]
9use serde::{Deserialize, Serialize};
10
11use super::{
12    MastForestContributor, MastNodeContext, MastNodeExt, fingerprint_with_child_fingerprints,
13};
14use crate::{
15    Felt, Word,
16    chiplets::hasher,
17    mast::{MastForest, MastForestError, MastNodeId},
18    operations::opcodes,
19    utils::LookupByIdx,
20};
21
22// CALL NODE
23// ================================================================================================
24
25/// A Call node describes a function call such that the callee is executed in a different execution
26/// context from the currently executing code.
27///
28/// A call node can be of two types:
29/// - A simple call: the callee is executed in the new user context.
30/// - A syscall: the callee is executed in the root context.
31#[derive(Debug, Clone, PartialEq, Eq)]
32#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
33#[cfg_attr(all(feature = "arbitrary", test), miden_test_serde_macros::serde_test)]
34pub struct CallNode {
35    callee: MastNodeId,
36    is_syscall: bool,
37    digest: Word,
38}
39
40//-------------------------------------------------------------------------------------------------
41/// Constants
42impl CallNode {
43    /// The domain of the call block (used for control block hashing).
44    pub const CALL_DOMAIN: Felt = Felt::new_unchecked(opcodes::CALL as u64);
45    /// The domain of the syscall block (used for control block hashing).
46    pub const SYSCALL_DOMAIN: Felt = Felt::new_unchecked(opcodes::SYSCALL as u64);
47}
48
49//-------------------------------------------------------------------------------------------------
50/// Public accessors
51impl CallNode {
52    /// Returns the ID of the node to be invoked by this call node.
53    pub fn callee(&self) -> MastNodeId {
54        self.callee
55    }
56
57    /// Returns true if this call node represents a syscall.
58    pub fn is_syscall(&self) -> bool {
59        self.is_syscall
60    }
61
62    /// Returns the domain of this call node.
63    pub fn domain(&self) -> Felt {
64        if self.is_syscall() {
65            Self::SYSCALL_DOMAIN
66        } else {
67            Self::CALL_DOMAIN
68        }
69    }
70}
71
72// PRETTY PRINTING
73// ================================================================================================
74
75impl CallNode {
76    pub(super) fn to_pretty_print<'a>(
77        &'a self,
78        mast_forest: &'a MastForest,
79    ) -> impl PrettyPrint + 'a {
80        CallNodePrettyPrint { node: self, mast_forest }
81    }
82
83    pub(super) fn to_display<'a>(&'a self, mast_forest: &'a MastForest) -> impl fmt::Display + 'a {
84        CallNodePrettyPrint { node: self, mast_forest }
85    }
86}
87
88struct CallNodePrettyPrint<'a> {
89    node: &'a CallNode,
90    mast_forest: &'a MastForest,
91}
92
93impl PrettyPrint for CallNodePrettyPrint<'_> {
94    fn render(&self) -> Document {
95        let callee_digest = self.mast_forest[self.node.callee].digest();
96        if self.node.is_syscall {
97            const_text("syscall")
98                + const_text(".")
99                + text(callee_digest.as_bytes().to_hex_with_prefix())
100        } else {
101            const_text("call")
102                + const_text(".")
103                + text(callee_digest.as_bytes().to_hex_with_prefix())
104        }
105    }
106}
107
108impl fmt::Display for CallNodePrettyPrint<'_> {
109    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
110        use crate::prettier::PrettyPrint;
111        self.pretty_print(f)
112    }
113}
114
115// MAST NODE TRAIT IMPLEMENTATION
116// ================================================================================================
117
118impl MastNodeExt for CallNode {
119    /// Returns a commitment to this Call node.
120    ///
121    /// The commitment is computed as a hash of the callee and an empty word ([ZERO; 4]) in the
122    /// domain defined by either [Self::CALL_DOMAIN] or [Self::SYSCALL_DOMAIN], depending on
123    /// whether the node represents a simple call or a syscall - i.e.,:
124    /// ```
125    /// # use miden_core::mast::CallNode;
126    /// # use miden_crypto::{Word, hash::poseidon2::Poseidon2 as Hasher};
127    /// # let callee_digest = Word::default();
128    /// Hasher::merge_in_domain(&[callee_digest, Word::default()], CallNode::CALL_DOMAIN);
129    /// ```
130    /// or
131    /// ```
132    /// # use miden_core::mast::CallNode;
133    /// # use miden_crypto::{Word, hash::poseidon2::Poseidon2 as Hasher};
134    /// # let callee_digest = Word::default();
135    /// Hasher::merge_in_domain(&[callee_digest, Word::default()], CallNode::SYSCALL_DOMAIN);
136    /// ```
137    fn digest(&self) -> Word {
138        self.digest
139    }
140
141    fn to_display<'a>(&'a self, mast_forest: &'a MastForest) -> Box<dyn fmt::Display + 'a> {
142        Box::new(CallNode::to_display(self, mast_forest))
143    }
144
145    fn to_pretty_print<'a>(&'a self, mast_forest: &'a MastForest) -> Box<dyn PrettyPrint + 'a> {
146        Box::new(CallNode::to_pretty_print(self, mast_forest))
147    }
148
149    fn has_children(&self) -> bool {
150        true
151    }
152
153    fn append_children_to(&self, target: &mut Vec<MastNodeId>) {
154        target.push(self.callee());
155    }
156
157    fn for_each_child<F>(&self, mut f: F)
158    where
159        F: FnMut(MastNodeId),
160    {
161        f(self.callee());
162    }
163
164    fn domain(&self) -> Felt {
165        self.domain()
166    }
167
168    type Builder = CallNodeBuilder;
169
170    fn to_builder(self, _forest: &MastForest) -> Self::Builder {
171        let builder = if self.is_syscall {
172            CallNodeBuilder::new_syscall(self.callee)
173        } else {
174            CallNodeBuilder::new(self.callee)
175        };
176        builder.with_digest(self.digest)
177    }
178}
179
180// ARBITRARY IMPLEMENTATION
181// ================================================================================================
182
183#[cfg(all(feature = "arbitrary", test))]
184impl proptest::prelude::Arbitrary for CallNode {
185    type Parameters = ();
186
187    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
188        use proptest::prelude::*;
189
190        use crate::Felt;
191
192        // Generate callee, digest, and whether it's a syscall
193        (any::<MastNodeId>(), any::<[u64; 4]>(), any::<bool>())
194            .prop_map(|(callee, digest_array, is_syscall)| {
195                // Generate a random digest
196                let digest = Word::from(digest_array.map(Felt::new_unchecked));
197                // Construct directly to avoid MastForest validation for arbitrary data
198                CallNode {
199                    callee,
200                    is_syscall,
201                    digest,
202                }
203            })
204            .no_shrink()  // Pure random values, no meaningful shrinking pattern
205            .boxed()
206    }
207
208    type Strategy = proptest::prelude::BoxedStrategy<Self>;
209}
210
211// ------------------------------------------------------------------------------------------------
212/// Builder for creating [`CallNode`] instances.
213#[derive(Debug)]
214pub struct CallNodeBuilder {
215    callee: MastNodeId,
216    is_syscall: bool,
217    digest: Option<Word>,
218}
219
220impl CallNodeBuilder {
221    /// Creates a new builder for a CallNode with the specified callee.
222    pub fn new(callee: MastNodeId) -> Self {
223        Self { callee, is_syscall: false, digest: None }
224    }
225
226    /// Creates a new builder for a syscall CallNode with the specified callee.
227    pub fn new_syscall(callee: MastNodeId) -> Self {
228        Self { callee, is_syscall: true, digest: None }
229    }
230
231    /// Builds the CallNode.
232    pub fn build(self, context: &impl MastNodeContext) -> Result<CallNode, MastForestError> {
233        let callee = context
234            .get_node_by_id(self.callee)
235            .ok_or_else(|| MastForestError::NodeIdOverflow(self.callee, context.node_count()))?;
236
237        // Use the forced digest if provided, otherwise compute the digest
238        let digest = if let Some(forced_digest) = self.digest {
239            forced_digest
240        } else {
241            let callee_digest = callee.digest();
242            let domain = if self.is_syscall {
243                CallNode::SYSCALL_DOMAIN
244            } else {
245                CallNode::CALL_DOMAIN
246            };
247
248            hasher::merge_in_domain(&[callee_digest, Word::default()], domain)
249        };
250
251        Ok(CallNode {
252            callee: self.callee,
253            is_syscall: self.is_syscall,
254            digest,
255        })
256    }
257
258    pub(in crate::mast) fn build_linked(self) -> Result<CallNode, MastForestError> {
259        Ok(CallNode {
260            callee: self.callee,
261            is_syscall: self.is_syscall,
262            digest: self.digest.ok_or(MastForestError::DigestRequiredForDeserialization)?,
263        })
264    }
265}
266
267#[cfg(any(test, feature = "arbitrary"))]
268impl CallNodeBuilder {
269    /// Adds this builder to a mutable forest for test and arbitrary data construction.
270    pub fn add_to_forest(self, forest: &mut MastForest) -> Result<MastNodeId, MastForestError> {
271        let node = self.build(forest)?;
272        forest.nodes.push(node.into()).map_err(|_| MastForestError::TooManyNodes)
273    }
274}
275
276impl MastForestContributor for CallNodeBuilder {
277    fn fingerprint_for_node(
278        &self,
279        context: &impl MastNodeContext,
280        hash_by_node_id: &impl LookupByIdx<MastNodeId, Word>,
281    ) -> Result<Word, MastForestError> {
282        let node_digest = if let Some(forced_digest) = self.digest {
283            forced_digest
284        } else {
285            let callee_digest = context
286                .get_node_by_id(self.callee)
287                .ok_or_else(|| MastForestError::NodeIdOverflow(self.callee, context.node_count()))?
288                .digest();
289            let domain = if self.is_syscall {
290                CallNode::SYSCALL_DOMAIN
291            } else {
292                CallNode::CALL_DOMAIN
293            };
294
295            hasher::merge_in_domain(&[callee_digest, Word::default()], domain)
296        };
297
298        fingerprint_with_child_fingerprints(node_digest, &[self.callee], context, hash_by_node_id)
299    }
300
301    fn remap_children(self, remapping: &impl LookupByIdx<MastNodeId, MastNodeId>) -> Self {
302        CallNodeBuilder {
303            callee: *remapping.get(self.callee).unwrap_or(&self.callee),
304            is_syscall: self.is_syscall,
305            digest: self.digest,
306        }
307    }
308
309    fn with_digest(mut self, digest: Word) -> Self {
310        self.digest = Some(digest);
311        self
312    }
313}
314
315#[cfg(any(test, feature = "arbitrary"))]
316impl proptest::prelude::Arbitrary for CallNodeBuilder {
317    type Parameters = ();
318    type Strategy = proptest::strategy::BoxedStrategy<Self>;
319
320    fn arbitrary_with(_params: Self::Parameters) -> Self::Strategy {
321        use proptest::prelude::*;
322
323        (any::<MastNodeId>(), any::<bool>())
324            .prop_map(|(callee, is_syscall)| {
325                if is_syscall {
326                    Self::new_syscall(callee)
327                } else {
328                    Self::new(callee)
329                }
330            })
331            .boxed()
332    }
333}
miden_core/mast/node/call_node.rs

miden_core/mast/node/
call_node.rs
