miden_core/mast/node/
dyn_node.rs

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

miden_core/mast/node/
dyn_node.rs
