miden_core/mast/node/
split_node.rs

1use alloc::{boxed::Box, vec::Vec};
2use core::fmt;
3
4#[cfg(feature = "serde")]
5use serde::{Deserialize, Serialize};
6
7use super::{
8    MastForestContributor, MastNodeContext, MastNodeExt, fingerprint_with_child_fingerprints,
9};
10use crate::{
11    Felt, Word,
12    chiplets::hasher,
13    mast::{MastForest, MastForestError, MastNodeId},
14    operations::opcodes,
15    prettier::PrettyPrint,
16    utils::LookupByIdx,
17};
18
19// SPLIT NODE
20// ================================================================================================
21
22/// A Split node defines conditional execution. When the VM encounters a Split node it executes
23/// either the `on_true` child or `on_false` child.
24///
25/// Which child is executed is determined based on the top of the stack. If the value is `1`, then
26/// the `on_true` child is executed. If the value is `0`, then the `on_false` child is executed. If
27/// the value is neither `0` nor `1`, the execution fails.
28#[derive(Debug, Clone, PartialEq, Eq)]
29#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
30#[cfg_attr(all(feature = "arbitrary", test), miden_test_serde_macros::serde_test)]
31pub struct SplitNode {
32    branches: [MastNodeId; 2],
33    digest: Word,
34}
35
36/// Constants
37impl SplitNode {
38    /// The domain of the split node (used for control block hashing).
39    pub const DOMAIN: Felt = Felt::new_unchecked(opcodes::SPLIT as u64);
40}
41
42/// Public accessors
43impl SplitNode {
44    /// Returns the ID of the node which is to be executed if the top of the stack is `1`.
45    pub fn on_true(&self) -> MastNodeId {
46        self.branches[0]
47    }
48
49    /// Returns the ID of the node which is to be executed if the top of the stack is `0`.
50    pub fn on_false(&self) -> MastNodeId {
51        self.branches[1]
52    }
53}
54
55// PRETTY PRINTING
56// ================================================================================================
57
58impl SplitNode {
59    pub(super) fn to_display<'a>(&'a self, mast_forest: &'a MastForest) -> impl fmt::Display + 'a {
60        SplitNodePrettyPrint { split_node: self, mast_forest }
61    }
62
63    pub(super) fn to_pretty_print<'a>(
64        &'a self,
65        mast_forest: &'a MastForest,
66    ) -> impl PrettyPrint + 'a {
67        SplitNodePrettyPrint { split_node: self, mast_forest }
68    }
69}
70
71struct SplitNodePrettyPrint<'a> {
72    split_node: &'a SplitNode,
73    mast_forest: &'a MastForest,
74}
75
76impl PrettyPrint for SplitNodePrettyPrint<'_> {
77    #[rustfmt::skip]
78    fn render(&self) -> crate::prettier::Document {
79        use crate::prettier::*;
80
81        let true_branch = self.mast_forest[self.split_node.on_true()].to_pretty_print(self.mast_forest);
82        let false_branch = self.mast_forest[self.split_node.on_false()].to_pretty_print(self.mast_forest);
83
84        let mut doc = Document::Empty;
85        doc += indent(4, const_text("if.true") + nl() + true_branch.render()) + nl();
86        doc += indent(4, const_text("else") + nl() + false_branch.render());
87        doc += nl() + const_text("end");
88        doc
89    }
90}
91
92impl fmt::Display for SplitNodePrettyPrint<'_> {
93    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
94        use crate::prettier::PrettyPrint;
95        self.pretty_print(f)
96    }
97}
98
99// MAST NODE TRAIT IMPLEMENTATION
100// ================================================================================================
101
102impl MastNodeExt for SplitNode {
103    /// Returns a commitment to this Split node.
104    ///
105    /// The commitment is computed as a hash of the `on_true` and `on_false` child nodes in the
106    /// domain defined by [Self::DOMAIN] - i..e,:
107    /// ```
108    /// # use miden_core::mast::SplitNode;
109    /// # use miden_crypto::{Word, hash::poseidon2::Poseidon2 as Hasher};
110    /// # let on_true_digest = Word::default();
111    /// # let on_false_digest = Word::default();
112    /// Hasher::merge_in_domain(&[on_true_digest, on_false_digest], SplitNode::DOMAIN);
113    /// ```
114    fn digest(&self) -> Word {
115        self.digest
116    }
117
118    fn to_display<'a>(&'a self, mast_forest: &'a MastForest) -> Box<dyn fmt::Display + 'a> {
119        Box::new(SplitNode::to_display(self, mast_forest))
120    }
121
122    fn to_pretty_print<'a>(&'a self, mast_forest: &'a MastForest) -> Box<dyn PrettyPrint + 'a> {
123        Box::new(SplitNode::to_pretty_print(self, mast_forest))
124    }
125
126    fn has_children(&self) -> bool {
127        true
128    }
129
130    fn append_children_to(&self, target: &mut Vec<MastNodeId>) {
131        target.push(self.on_true());
132        target.push(self.on_false());
133    }
134
135    fn for_each_child<F>(&self, mut f: F)
136    where
137        F: FnMut(MastNodeId),
138    {
139        f(self.on_true());
140        f(self.on_false());
141    }
142
143    fn domain(&self) -> Felt {
144        Self::DOMAIN
145    }
146
147    type Builder = SplitNodeBuilder;
148
149    fn to_builder(self, _forest: &MastForest) -> Self::Builder {
150        SplitNodeBuilder::new(self.branches).with_digest(self.digest)
151    }
152}
153
154// ARBITRARY IMPLEMENTATION
155// ================================================================================================
156
157#[cfg(all(feature = "arbitrary", test))]
158impl proptest::prelude::Arbitrary for SplitNode {
159    type Parameters = ();
160
161    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
162        use proptest::prelude::*;
163
164        use crate::Felt;
165
166        // Generate two MastNodeId values and digest for the children
167        (any::<MastNodeId>(), any::<MastNodeId>(), any::<[u64; 4]>())
168            .prop_map(|(true_branch, false_branch, digest_array)| {
169                // Generate a random digest
170                let digest = Word::from(digest_array.map(Felt::new_unchecked));
171                // Construct directly to avoid MastForest validation for arbitrary data
172                SplitNode {
173                    branches: [true_branch, false_branch],
174                    digest,
175                }
176            })
177            .no_shrink()  // Pure random values, no meaningful shrinking pattern
178            .boxed()
179    }
180
181    type Strategy = proptest::prelude::BoxedStrategy<Self>;
182}
183
184// ------------------------------------------------------------------------------------------------
185/// Builder for creating [`SplitNode`] instances.
186#[derive(Debug)]
187pub struct SplitNodeBuilder {
188    branches: [MastNodeId; 2],
189    digest: Option<Word>,
190}
191
192impl SplitNodeBuilder {
193    /// Creates a new builder for a SplitNode with the specified branches.
194    pub fn new(branches: [MastNodeId; 2]) -> Self {
195        Self { branches, digest: None }
196    }
197
198    /// Builds the SplitNode.
199    pub fn build(self, context: &impl MastNodeContext) -> Result<SplitNode, MastForestError> {
200        let true_branch = context.get_node_by_id(self.branches[0]).ok_or_else(|| {
201            MastForestError::NodeIdOverflow(self.branches[0], context.node_count())
202        })?;
203        let false_branch = context.get_node_by_id(self.branches[1]).ok_or_else(|| {
204            MastForestError::NodeIdOverflow(self.branches[1], context.node_count())
205        })?;
206
207        // Use the forced digest if provided, otherwise compute the digest
208        let digest = if let Some(forced_digest) = self.digest {
209            forced_digest
210        } else {
211            let true_branch_hash = true_branch.digest();
212            let false_branch_hash = false_branch.digest();
213
214            hasher::merge_in_domain(&[true_branch_hash, false_branch_hash], SplitNode::DOMAIN)
215        };
216
217        Ok(SplitNode { branches: self.branches, digest })
218    }
219
220    pub(in crate::mast) fn build_linked(self) -> Result<SplitNode, MastForestError> {
221        Ok(SplitNode {
222            branches: self.branches,
223            digest: self.digest.ok_or(MastForestError::DigestRequiredForDeserialization)?,
224        })
225    }
226}
227
228#[cfg(any(test, feature = "arbitrary"))]
229impl SplitNodeBuilder {
230    /// Adds this builder to a mutable forest for test and arbitrary data construction.
231    pub fn add_to_forest(self, forest: &mut MastForest) -> Result<MastNodeId, MastForestError> {
232        let node = self.build(forest)?;
233        forest.nodes.push(node.into()).map_err(|_| MastForestError::TooManyNodes)
234    }
235}
236
237impl MastForestContributor for SplitNodeBuilder {
238    fn fingerprint_for_node(
239        &self,
240        context: &impl MastNodeContext,
241        hash_by_node_id: &impl LookupByIdx<MastNodeId, Word>,
242    ) -> Result<Word, MastForestError> {
243        let node_digest = if let Some(forced_digest) = self.digest {
244            forced_digest
245        } else {
246            let if_branch_hash = context
247                .get_node_by_id(self.branches[0])
248                .ok_or_else(|| {
249                    MastForestError::NodeIdOverflow(self.branches[0], context.node_count())
250                })?
251                .digest();
252            let else_branch_hash = context
253                .get_node_by_id(self.branches[1])
254                .ok_or_else(|| {
255                    MastForestError::NodeIdOverflow(self.branches[1], context.node_count())
256                })?
257                .digest();
258
259            hasher::merge_in_domain(&[if_branch_hash, else_branch_hash], SplitNode::DOMAIN)
260        };
261
262        fingerprint_with_child_fingerprints(node_digest, &self.branches, context, hash_by_node_id)
263    }
264
265    fn remap_children(self, remapping: &impl LookupByIdx<MastNodeId, MastNodeId>) -> Self {
266        SplitNodeBuilder {
267            branches: [
268                *remapping.get(self.branches[0]).unwrap_or(&self.branches[0]),
269                *remapping.get(self.branches[1]).unwrap_or(&self.branches[1]),
270            ],
271            digest: self.digest,
272        }
273    }
274
275    fn with_digest(mut self, digest: Word) -> Self {
276        self.digest = Some(digest);
277        self
278    }
279}
280
281#[cfg(any(test, feature = "arbitrary"))]
282impl proptest::prelude::Arbitrary for SplitNodeBuilder {
283    type Parameters = ();
284    type Strategy = proptest::strategy::BoxedStrategy<Self>;
285
286    fn arbitrary_with(_params: Self::Parameters) -> Self::Strategy {
287        use proptest::prelude::*;
288
289        any::<[MastNodeId; 2]>().prop_map(Self::new).boxed()
290    }
291}
miden_core/mast/node/split_node.rs

miden_core/mast/node/
split_node.rs
