miden_core/mast/serialization/
info.rs

1use super::{NodeDataOffset, basic_blocks::BasicBlockDataDecoder};
2#[cfg(test)]
3use crate::mast::node::MastNodeExt;
4use crate::{
5    mast::{MastForestContributor, MastNode, MastNodeId, Word, node::MastNodeBuilder},
6    serde::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable},
7};
8
9// CONSTANTS
10// ================================================================================================
11
12const JOIN: u8 = 0;
13const SPLIT: u8 = 1;
14const LOOP: u8 = 2;
15const BLOCK: u8 = 3;
16const CALL: u8 = 4;
17const SYSCALL: u8 = 5;
18const DYN: u8 = 6;
19const DYNCALL: u8 = 7;
20const EXTERNAL: u8 = 8;
21
22// MAST NODE ENTRIES
23// ================================================================================================
24
25/// Fixed-width structural metadata for a serialized [`MastNode`].
26///
27/// This is the random-access portion of the node table. Digests are intentionally modeled
28/// separately so the wire format can move them into dedicated sections.
29///
30/// Child indices for `Join`, `Split`, `Loop`, `Call`, and `SysCall` are stored inline so random
31/// access does not need any extra pointer chasing.
32///
33/// The serialized representation is always 8 bytes, which keeps the node-entry table fixed-width
34/// on the wire.
35#[derive(Debug, Clone, Copy, PartialEq, Eq)]
36#[repr(u8)]
37#[cfg_attr(
38    all(feature = "arbitrary", test),
39    miden_test_serialization_macros::serialization_test
40)]
41pub enum MastNodeEntry {
42    Join {
43        left_child_id: u32,
44        right_child_id: u32,
45    } = JOIN,
46    Split {
47        if_branch_id: u32,
48        else_branch_id: u32,
49    } = SPLIT,
50    Loop {
51        body_id: u32,
52    } = LOOP,
53    Block {
54        // offset of operations in node data
55        ops_offset: u32,
56    } = BLOCK,
57    Call {
58        callee_id: u32,
59    } = CALL,
60    SysCall {
61        callee_id: u32,
62    } = SYSCALL,
63    Dyn = DYN,
64    Dyncall = DYNCALL,
65    External = EXTERNAL,
66}
67
68/// Constructors
69impl MastNodeEntry {
70    /// Serialized byte size of one fixed-width MAST node entry.
71    pub const SERIALIZED_SIZE: usize = 8;
72
73    /// Constructs a new [`MastNodeEntry`] from a [`MastNode`].
74    pub fn new(mast_node: &MastNode, ops_offset: NodeDataOffset) -> Self {
75        use MastNode::*;
76
77        if !matches!(mast_node, &Block(_)) {
78            debug_assert_eq!(ops_offset, 0);
79        }
80
81        match mast_node {
82            Block(_) => Self::Block { ops_offset },
83            Join(join_node) => Self::Join {
84                left_child_id: join_node.first().0,
85                right_child_id: join_node.second().0,
86            },
87            Split(split_node) => Self::Split {
88                if_branch_id: split_node.on_true().0,
89                else_branch_id: split_node.on_false().0,
90            },
91            Loop(loop_node) => Self::Loop { body_id: loop_node.body().0 },
92            Call(call_node) => {
93                if call_node.is_syscall() {
94                    Self::SysCall { callee_id: call_node.callee().0 }
95                } else {
96                    Self::Call { callee_id: call_node.callee().0 }
97                }
98            },
99            Dyn(dyn_node) => {
100                if dyn_node.is_dyncall() {
101                    Self::Dyncall
102                } else {
103                    Self::Dyn
104                }
105            },
106            External(_) => Self::External,
107        }
108    }
109
110    /// Attempts to convert this [`MastNodeEntry`] into a [`MastNodeBuilder`].
111    ///
112    /// The `node_count` is the total expected number of nodes in the
113    /// [`crate::mast::MastForest`] **after deserialization**.
114    pub fn try_into_mast_node_builder(
115        self,
116        node_count: usize,
117        basic_block_data_decoder: &BasicBlockDataDecoder,
118        digest: Word,
119    ) -> Result<MastNodeBuilder, DeserializationError> {
120        match self {
121            Self::Block { ops_offset } => {
122                let op_batches = basic_block_data_decoder.decode_operations(ops_offset)?;
123                let builder =
124                    crate::mast::node::BasicBlockNodeBuilder::from_op_batches(op_batches, digest);
125                Ok(MastNodeBuilder::BasicBlock(builder))
126            },
127            Self::Join { left_child_id, right_child_id } => {
128                let left_child = MastNodeId::from_u32_with_node_count(left_child_id, node_count)?;
129                let right_child = MastNodeId::from_u32_with_node_count(right_child_id, node_count)?;
130                let builder = crate::mast::node::JoinNodeBuilder::new([left_child, right_child])
131                    .with_digest(digest);
132                Ok(MastNodeBuilder::Join(builder))
133            },
134            Self::Split { if_branch_id, else_branch_id } => {
135                let if_branch = MastNodeId::from_u32_with_node_count(if_branch_id, node_count)?;
136                let else_branch = MastNodeId::from_u32_with_node_count(else_branch_id, node_count)?;
137                let builder = crate::mast::node::SplitNodeBuilder::new([if_branch, else_branch])
138                    .with_digest(digest);
139                Ok(MastNodeBuilder::Split(builder))
140            },
141            Self::Loop { body_id } => {
142                let body_id = MastNodeId::from_u32_with_node_count(body_id, node_count)?;
143                let builder = crate::mast::node::LoopNodeBuilder::new(body_id).with_digest(digest);
144                Ok(MastNodeBuilder::Loop(builder))
145            },
146            Self::Call { callee_id } => {
147                let callee_id = MastNodeId::from_u32_with_node_count(callee_id, node_count)?;
148                let builder =
149                    crate::mast::node::CallNodeBuilder::new(callee_id).with_digest(digest);
150                Ok(MastNodeBuilder::Call(builder))
151            },
152            Self::SysCall { callee_id } => {
153                let callee_id = MastNodeId::from_u32_with_node_count(callee_id, node_count)?;
154                let builder =
155                    crate::mast::node::CallNodeBuilder::new_syscall(callee_id).with_digest(digest);
156                Ok(MastNodeBuilder::Call(builder))
157            },
158            Self::Dyn => Ok(MastNodeBuilder::Dyn(
159                crate::mast::node::DynNodeBuilder::new_dyn().with_digest(digest),
160            )),
161            Self::Dyncall => Ok(MastNodeBuilder::Dyn(
162                crate::mast::node::DynNodeBuilder::new_dyncall().with_digest(digest),
163            )),
164            Self::External => {
165                Ok(MastNodeBuilder::External(crate::mast::node::ExternalNodeBuilder::new(digest)))
166            },
167        }
168    }
169}
170
171impl Serializable for MastNodeEntry {
172    fn write_into<W: ByteWriter>(&self, target: &mut W) {
173        let discriminant = self.discriminant() as u64;
174        assert!(discriminant <= 0b1111);
175
176        let payload = match *self {
177            Self::Join {
178                left_child_id: left,
179                right_child_id: right,
180            } => Self::encode_u32_pair(left, right),
181            Self::Split {
182                if_branch_id: if_branch,
183                else_branch_id: else_branch,
184            } => Self::encode_u32_pair(if_branch, else_branch),
185            Self::Loop { body_id: body } => Self::encode_u32_payload(body),
186            Self::Block { ops_offset } => Self::encode_u32_payload(ops_offset),
187            Self::Call { callee_id } => Self::encode_u32_payload(callee_id),
188            Self::SysCall { callee_id } => Self::encode_u32_payload(callee_id),
189            Self::Dyn | Self::Dyncall | Self::External => 0,
190        };
191
192        let value = (discriminant << 60) | payload;
193        target.write_u64(value);
194    }
195}
196
197impl Deserializable for MastNodeEntry {
198    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
199        let (discriminant, payload) = {
200            let value = source.read_u64()?;
201
202            let discriminant = (value >> 60) as u8;
203            let payload = value & 0x0f_ff_ff_ff_ff_ff_ff_ff;
204
205            (discriminant, payload)
206        };
207
208        match discriminant {
209            JOIN => {
210                let (left_child_id, right_child_id) = Self::decode_u32_pair(payload);
211                Ok(Self::Join { left_child_id, right_child_id })
212            },
213            SPLIT => {
214                let (if_branch_id, else_branch_id) = Self::decode_u32_pair(payload);
215                Ok(Self::Split { if_branch_id, else_branch_id })
216            },
217            LOOP => {
218                let body_id = Self::decode_u32_payload(payload)?;
219                Ok(Self::Loop { body_id })
220            },
221            BLOCK => {
222                let ops_offset = Self::decode_u32_payload(payload)?;
223                Ok(Self::Block { ops_offset })
224            },
225            CALL => {
226                let callee_id = Self::decode_u32_payload(payload)?;
227                Ok(Self::Call { callee_id })
228            },
229            SYSCALL => {
230                let callee_id = Self::decode_u32_payload(payload)?;
231                Ok(Self::SysCall { callee_id })
232            },
233            DYN => Ok(Self::Dyn),
234            DYNCALL => Ok(Self::Dyncall),
235            EXTERNAL => Ok(Self::External),
236            _ => Err(DeserializationError::InvalidValue(format!(
237                "Invalid tag for MAST node: {discriminant}"
238            ))),
239        }
240    }
241
242    /// Returns the fixed serialized size: always 8 bytes (u64).
243    fn min_serialized_size() -> usize {
244        Self::SERIALIZED_SIZE
245    }
246}
247
248/// Serialization helpers
249impl MastNodeEntry {
250    fn discriminant(&self) -> u8 {
251        // SAFETY: This is safe because we have given this enum a primitive representation with
252        // #[repr(u8)], with the first field of the underlying union-of-structs the discriminant.
253        //
254        // See the section on "accessing the numeric value of the discriminant"
255        // here: https://doc.rust-lang.org/std/mem/fn.discriminant.html
256        unsafe { *<*const _>::from(self).cast::<u8>() }
257    }
258
259    /// Encodes two u32 numbers in the first 60 bits of a `u64`.
260    ///
261    /// # Panics
262    /// - Panics if either `left_value` or `right_value` doesn't fit in 30 bits.
263    fn encode_u32_pair(left_value: u32, right_value: u32) -> u64 {
264        assert!(
265            left_value.leading_zeros() >= 2,
266            "MastNodeEntry::encode_u32_pair: left value doesn't fit in 30 bits: {left_value}",
267        );
268        assert!(
269            right_value.leading_zeros() >= 2,
270            "MastNodeEntry::encode_u32_pair: right value doesn't fit in 30 bits: {right_value}",
271        );
272
273        ((left_value as u64) << 30) | (right_value as u64)
274    }
275
276    fn encode_u32_payload(payload: u32) -> u64 {
277        payload as u64
278    }
279}
280
281/// Deserialization helpers
282impl MastNodeEntry {
283    /// Decodes two `u32` numbers from a 60-bit payload.
284    fn decode_u32_pair(payload: u64) -> (u32, u32) {
285        let left_value = (payload >> 30) as u32;
286        let right_value = (payload & 0x3f_ff_ff_ff) as u32;
287
288        (left_value, right_value)
289    }
290
291    /// Decodes one `u32` number from a 60-bit payload.
292    ///
293    /// Returns an error if the payload doesn't fit in a `u32`.
294    pub fn decode_u32_payload(payload: u64) -> Result<u32, DeserializationError> {
295        payload.try_into().map_err(|_| {
296            DeserializationError::InvalidValue(format!(
297                "Invalid payload: expected to fit in u32, but was {payload}"
298            ))
299        })
300    }
301}
302
303// MAST NODE INFO
304// ================================================================================================
305
306/// Logical node metadata combining fixed-width structure and a digest value.
307///
308/// This is a convenience type for APIs that want both pieces together. The wire format does not
309/// require `MastNodeInfo` to appear as one contiguous fixed-width section.
310#[derive(Debug, Clone, Copy, PartialEq, Eq)]
311#[cfg_attr(
312    all(feature = "arbitrary", test),
313    miden_test_serialization_macros::serialization_test
314)]
315pub struct MastNodeInfo {
316    entry: MastNodeEntry,
317    digest: Word,
318}
319
320impl MastNodeInfo {
321    /// Constructs a new [`MastNodeInfo`] from a [`MastNode`], along with an `ops_offset`
322    ///
323    /// For non-basic block nodes, `ops_offset` is ignored, and should be set to 0.
324    #[cfg(test)]
325    pub(super) fn new(mast_node: &MastNode, ops_offset: NodeDataOffset) -> Self {
326        Self {
327            entry: MastNodeEntry::new(mast_node, ops_offset),
328            digest: mast_node.digest(),
329        }
330    }
331
332    /// Returns the fixed-width structural node entry.
333    pub fn node_entry(&self) -> MastNodeEntry {
334        self.entry
335    }
336
337    /// Returns the stored node digest.
338    pub fn digest(&self) -> Word {
339        self.digest
340    }
341
342    /// Builds node metadata directly from serialized components.
343    pub(crate) fn from_entry(entry: MastNodeEntry, digest: Word) -> Self {
344        Self { entry, digest }
345    }
346}
347
348#[cfg(test)]
349impl Serializable for MastNodeInfo {
350    fn write_into<W: ByteWriter>(&self, target: &mut W) {
351        self.entry.write_into(target);
352        self.digest.write_into(target);
353    }
354}
355
356#[cfg(test)]
357impl Deserializable for MastNodeInfo {
358    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
359        let entry = MastNodeEntry::read_from(source)?;
360        let digest = Word::read_from(source)?;
361        Ok(Self { entry, digest })
362    }
363
364    /// Returns the minimum serialized size: 8 bytes for `MastNodeEntry` + 32 bytes for `Word`.
365    fn min_serialized_size() -> usize {
366        MastNodeEntry::min_serialized_size() + Word::min_serialized_size()
367    }
368}
369
370// ARBITRARY (proptest)
371// ===============================================================================================
372
373#[cfg(any(test, feature = "arbitrary"))]
374mod arbitrary {
375    use proptest::prelude::*;
376
377    use super::{MastNodeEntry, MastNodeInfo};
378    use crate::Word;
379
380    impl Arbitrary for MastNodeEntry {
381        type Parameters = ();
382        type Strategy = BoxedStrategy<Self>;
383
384        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
385            // Join/Split child ids must fit in 30 bits (encode_u32_pair asserts
386            // leading_zeros >= 2); single-payload variants accept any u32. The edge-biased id
387            // strategy hits the 30-bit bounds (0 and 2^30 - 1) deliberately instead of relying
388            // on flat sampling. prop_oneof exercises every discriminant, including the
389            // payload-less Dyn/Dyncall/External forms.
390            fn node_id() -> impl Strategy<Value = u32> {
391                prop_oneof![Just(0), Just((1 << 30) - 1), (0u32..(1 << 30)).boxed(),]
392            }
393
394            prop_oneof![
395                (node_id(), node_id())
396                    .prop_map(|(left, right)| Self::Join {
397                        left_child_id: left,
398                        right_child_id: right,
399                    })
400                    .boxed(),
401                (node_id(), node_id())
402                    .prop_map(|(if_branch, else_branch)| Self::Split {
403                        if_branch_id: if_branch,
404                        else_branch_id: else_branch,
405                    })
406                    .boxed(),
407                any::<u32>().prop_map(|body| Self::Loop { body_id: body }).boxed(),
408                any::<u32>().prop_map(|offset| Self::Block { ops_offset: offset }).boxed(),
409                any::<u32>().prop_map(|callee| Self::Call { callee_id: callee }).boxed(),
410                any::<u32>().prop_map(|callee| Self::SysCall { callee_id: callee }).boxed(),
411                Just(Self::Dyn),
412                Just(Self::Dyncall),
413                Just(Self::External),
414            ]
415            .boxed()
416        }
417    }
418
419    impl Arbitrary for MastNodeInfo {
420        type Parameters = ();
421        type Strategy = BoxedStrategy<Self>;
422
423        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
424            // Entry and digest are independent on the wire; both components are valid for any
425            // value, so no construction invariant exists.
426            (any::<MastNodeEntry>(), any::<Word>())
427                .prop_map(|(entry, digest)| Self::from_entry(entry, digest))
428                .boxed()
429        }
430    }
431}
432
433// TESTS
434// ================================================================================================
435
436#[cfg(test)]
437mod tests {
438    use alloc::vec::Vec;
439    use core::assert_matches;
440
441    use super::*;
442
443    #[test]
444    fn serialize_deserialize_60_bit_payload() {
445        // each child needs 30 bits
446        let mast_node_entry = MastNodeEntry::Join {
447            left_child_id: 0x3f_ff_ff_ff,
448            right_child_id: 0x3f_ff_ff_ff,
449        };
450
451        let serialized = mast_node_entry.to_bytes();
452        let deserialized = MastNodeEntry::read_from_bytes(&serialized).unwrap();
453
454        assert_eq!(mast_node_entry, deserialized);
455    }
456
457    #[test]
458    #[should_panic]
459    fn serialize_large_payloads_fails_1() {
460        // left child needs 31 bits
461        let mast_node_entry = MastNodeEntry::Join {
462            left_child_id: 0x4f_ff_ff_ff,
463            right_child_id: 0x0,
464        };
465
466        // must panic
467        let _serialized = mast_node_entry.to_bytes();
468    }
469
470    #[test]
471    #[should_panic]
472    fn serialize_large_payloads_fails_2() {
473        // right child needs 31 bits
474        let mast_node_entry = MastNodeEntry::Join {
475            left_child_id: 0x0,
476            right_child_id: 0x4f_ff_ff_ff,
477        };
478
479        // must panic
480        let _serialized = mast_node_entry.to_bytes();
481    }
482
483    #[test]
484    fn deserialize_large_payloads_fails() {
485        // Serialized `CALL` with a 33-bit payload
486        let serialized = {
487            let serialized_value = ((CALL as u64) << 60) | (u32::MAX as u64 + 1_u64);
488
489            let mut serialized_buffer: Vec<u8> = Vec::new();
490            serialized_value.write_into(&mut serialized_buffer);
491
492            serialized_buffer
493        };
494
495        let deserialized_result = MastNodeEntry::read_from_bytes(&serialized);
496
497        assert_matches!(deserialized_result, Err(DeserializationError::InvalidValue(_)));
498    }
499}
miden_core/mast/serialization/info.rs

miden_core/mast/serialization/
info.rs
