miden_core/mast/node/
dyn_node.rs

1use alloc::{boxed::Box, vec::Vec};
2use core::fmt;
3
4#[cfg(feature = "serde")]
5use serde::{Deserialize, Serialize};
6
7use super::{MastForestContributor, MastNodeContext, MastNodeExt};
8use crate::{
9    Felt, Word,
10    mast::{MastForest, MastForestError, MastNodeId},
11    operations::opcodes,
12    prettier::{Document, PrettyPrint, const_text},
13    utils::LookupByIdx,
14};
15
16// DYN NODE
17// ================================================================================================
18
19/// A Dyn node specifies that the node to be executed next is defined dynamically via the stack.
20#[derive(Debug, Clone, PartialEq, Eq)]
21#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
22#[cfg_attr(all(feature = "arbitrary", test), miden_test_serde_macros::serde_test)]
23pub struct DynNode {
24    is_dyncall: bool,
25    digest: Word,
26}
27
28/// Constants
29impl DynNode {
30    /// The domain of the Dyn block (used for control block hashing).
31    pub const DYN_DOMAIN: Felt = Felt::new_unchecked(opcodes::DYN as u64);
32
33    /// The domain of the Dyncall block (used for control block hashing).
34    pub const DYNCALL_DOMAIN: Felt = Felt::new_unchecked(opcodes::DYNCALL as u64);
35}
36
37/// Default digest constants
38impl DynNode {
39    /// The default digest for a DynNode representing a dyncall operation.
40    pub const DYNCALL_DEFAULT_DIGEST: Word = Word::new([
41        Felt::new_unchecked(16830415514927835337),
42        Felt::new_unchecked(12164645914672292987),
43        Felt::new_unchecked(13192574193032437705),
44        Felt::new_unchecked(4604554596675732269),
45    ]);
46
47    /// The default digest for a DynNode representing a dynexec operation.
48    pub const DYN_DEFAULT_DIGEST: Word = Word::new([
49        Felt::new_unchecked(16952228088962355159),
50        Felt::new_unchecked(5793482471479538911),
51        Felt::new_unchecked(14446299416172848527),
52        Felt::new_unchecked(13522295374716441620),
53    ]);
54}
55
56/// Public accessors
57impl DynNode {
58    /// Returns true if the [`DynNode`] represents a dyncall operation, and false for dynexec.
59    pub fn is_dyncall(&self) -> bool {
60        self.is_dyncall
61    }
62
63    /// Returns the domain of this dyn node.
64    pub fn domain(&self) -> Felt {
65        if self.is_dyncall() {
66            Self::DYNCALL_DOMAIN
67        } else {
68            Self::DYN_DOMAIN
69        }
70    }
71}
72
73// PRETTY PRINTING
74// ================================================================================================
75
76impl DynNode {
77    pub(super) fn to_display<'a>(&'a self, _mast_forest: &'a MastForest) -> impl fmt::Display + 'a {
78        self.clone()
79    }
80
81    pub(super) fn to_pretty_print<'a>(
82        &'a self,
83        _mast_forest: &'a MastForest,
84    ) -> impl PrettyPrint + 'a {
85        self.clone()
86    }
87}
88
89impl PrettyPrint for DynNode {
90    fn render(&self) -> Document {
91        if self.is_dyncall() {
92            const_text("dyncall")
93        } else {
94            const_text("dyn")
95        }
96    }
97}
98
99impl fmt::Display for DynNode {
100    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
101        self.pretty_print(f)
102    }
103}
104
105// MAST NODE TRAIT IMPLEMENTATION
106// ================================================================================================
107
108impl MastNodeExt for DynNode {
109    /// Returns a commitment to a Dyn node.
110    fn digest(&self) -> Word {
111        self.digest
112    }
113
114    fn to_display<'a>(&'a self, mast_forest: &'a MastForest) -> Box<dyn fmt::Display + 'a> {
115        Box::new(DynNode::to_display(self, mast_forest))
116    }
117
118    fn to_pretty_print<'a>(&'a self, mast_forest: &'a MastForest) -> Box<dyn PrettyPrint + 'a> {
119        Box::new(DynNode::to_pretty_print(self, mast_forest))
120    }
121
122    fn has_children(&self) -> bool {
123        false
124    }
125
126    fn append_children_to(&self, _target: &mut Vec<MastNodeId>) {
127        // No children for dyn nodes
128    }
129
130    fn for_each_child<F>(&self, _f: F)
131    where
132        F: FnMut(MastNodeId),
133    {
134        // DynNode has no children
135    }
136
137    fn domain(&self) -> Felt {
138        self.domain()
139    }
140
141    type Builder = DynNodeBuilder;
142
143    fn to_builder(self, _forest: &MastForest) -> Self::Builder {
144        let builder = if self.is_dyncall {
145            DynNodeBuilder::new_dyncall()
146        } else {
147            DynNodeBuilder::new_dyn()
148        };
149        builder.with_digest(self.digest)
150    }
151}
152
153// ARBITRARY IMPLEMENTATION
154// ================================================================================================
155
156#[cfg(all(feature = "arbitrary", test))]
157impl proptest::prelude::Arbitrary for DynNode {
158    type Parameters = ();
159
160    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
161        use proptest::prelude::*;
162
163        // Generate whether it's a dyncall or dynexec
164        any::<bool>()
165            .prop_map(|is_dyncall| {
166                if is_dyncall {
167                    DynNodeBuilder::new_dyncall().build()
168                } else {
169                    DynNodeBuilder::new_dyn().build()
170                }
171            })
172            .no_shrink()  // Pure random values, no meaningful shrinking pattern
173            .boxed()
174    }
175
176    type Strategy = proptest::prelude::BoxedStrategy<Self>;
177}
178
179// ------------------------------------------------------------------------------------------------
180/// Builder for creating [`DynNode`] instances.
181#[derive(Debug)]
182pub struct DynNodeBuilder {
183    is_dyncall: bool,
184    digest: Option<Word>,
185}
186
187impl DynNodeBuilder {
188    /// Creates a new builder for a DynNode representing a dynexec operation.
189    pub fn new_dyn() -> Self {
190        Self { is_dyncall: false, digest: None }
191    }
192
193    /// Creates a new builder for a DynNode representing a dyncall operation.
194    pub fn new_dyncall() -> Self {
195        Self { is_dyncall: true, digest: None }
196    }
197
198    /// Builds the DynNode.
199    pub fn build(self) -> DynNode {
200        // Use the forced digest if provided, otherwise use the default digest
201        let digest = if let Some(forced_digest) = self.digest {
202            forced_digest
203        } else if self.is_dyncall {
204            DynNode::DYNCALL_DEFAULT_DIGEST
205        } else {
206            DynNode::DYN_DEFAULT_DIGEST
207        };
208
209        DynNode { is_dyncall: self.is_dyncall, digest }
210    }
211}
212
213#[cfg(any(test, feature = "arbitrary"))]
214impl DynNodeBuilder {
215    /// Adds this builder to a mutable forest for test and arbitrary data construction.
216    pub fn add_to_forest(self, forest: &mut MastForest) -> Result<MastNodeId, MastForestError> {
217        let node = self.build();
218        forest.nodes.push(node.into()).map_err(|_| MastForestError::TooManyNodes)
219    }
220}
221
222impl MastForestContributor for DynNodeBuilder {
223    fn fingerprint_for_node(
224        &self,
225        _context: &impl MastNodeContext,
226        _hash_by_node_id: &impl LookupByIdx<MastNodeId, Word>,
227    ) -> Result<Word, MastForestError> {
228        Ok(if let Some(forced_digest) = self.digest {
229            forced_digest
230        } else if self.is_dyncall {
231            DynNode::DYNCALL_DEFAULT_DIGEST
232        } else {
233            DynNode::DYN_DEFAULT_DIGEST
234        })
235    }
236
237    fn remap_children(self, _remapping: &impl LookupByIdx<MastNodeId, MastNodeId>) -> Self {
238        // DynNode has no children to remap, but preserve the digest
239        self
240    }
241
242    fn with_digest(mut self, digest: Word) -> Self {
243        self.digest = Some(digest);
244        self
245    }
246}
247
248#[cfg(any(test, feature = "arbitrary"))]
249impl proptest::prelude::Arbitrary for DynNodeBuilder {
250    type Parameters = ();
251    type Strategy = proptest::strategy::BoxedStrategy<Self>;
252
253    fn arbitrary_with(_params: Self::Parameters) -> Self::Strategy {
254        use proptest::prelude::*;
255
256        any::<bool>()
257            .prop_map(|is_dyncall| {
258                if is_dyncall {
259                    Self::new_dyncall()
260                } else {
261                    Self::new_dyn()
262                }
263            })
264            .boxed()
265    }
266}
267
268#[cfg(test)]
269mod tests {
270    use miden_crypto::hash::poseidon2::Poseidon2;
271
272    use super::*;
273
274    /// Ensures that the hash of `DynNode` is indeed the hash of 2 empty words, in the `DynNode`
275    /// domain.
276    #[test]
277    pub fn test_dyn_node_digest() {
278        let mut forest = crate::mast::DenseMastForestBuilder::new();
279        let dyn_node_id = forest.push_node(DynNodeBuilder::new_dyn()).unwrap();
280        let dyn_node = forest.get_node_by_id(dyn_node_id).unwrap().unwrap_dyn();
281        assert_eq!(
282            dyn_node.digest(),
283            Poseidon2::merge_in_domain(&[Word::default(), Word::default()], DynNode::DYN_DOMAIN)
284        );
285
286        let dyncall_node_id = forest.push_node(DynNodeBuilder::new_dyncall()).unwrap();
287        let dyncall_node = forest.get_node_by_id(dyncall_node_id).unwrap().unwrap_dyn();
288        assert_eq!(
289            dyncall_node.digest(),
290            Poseidon2::merge_in_domain(
291                &[Word::default(), Word::default()],
292                DynNode::DYNCALL_DOMAIN
293            )
294        );
295    }
296}
miden_core/mast/node/dyn_node.rs

miden_core/mast/node/
dyn_node.rs
