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

miden_core/mast/node/
call_node.rs
