miden_air/trace/
rows.rs

1use alloc::{boxed::Box, vec::Vec};
2use core::{
3    fmt::{Display, Formatter},
4    ops::{Add, AddAssign, Bound, Index, IndexMut, Mul, RangeBounds, Sub, SubAssign},
5};
6
7use miden_core::{
8    Felt,
9    serde::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable},
10};
11
12// ROW INDEX
13// ================================================================================================
14
15/// Represents the types of errors that can occur when converting from and into [`RowIndex`] and
16/// using its operations.
17#[derive(Debug, thiserror::Error)]
18pub enum RowIndexError {
19    // This uses Box<str> rather than String because its stack size is 8 bytes smaller.
20    #[error("value {0} is larger than u32::MAX so it cannot be converted into a RowIndex")]
21    InvalidSize(Box<str>),
22}
23
24/// A newtype wrapper around a usize value representing a step in the execution trace.
25#[derive(Debug, Default, Copy, Clone, Eq, Ord, PartialOrd)]
26#[cfg_attr(
27    all(feature = "arbitrary", test),
28    miden_test_serialization_macros::serialization_test
29)]
30pub struct RowIndex(u32);
31
32impl RowIndex {
33    pub fn as_usize(&self) -> usize {
34        self.0 as usize
35    }
36
37    pub fn as_u32(&self) -> u32 {
38        self.0
39    }
40}
41
42impl Display for RowIndex {
43    fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
44        write!(f, "{}", self.0)
45    }
46}
47
48// FROM ROW INDEX
49// ================================================================================================
50
51impl From<RowIndex> for u32 {
52    fn from(step: RowIndex) -> u32 {
53        step.0
54    }
55}
56
57impl From<RowIndex> for u64 {
58    fn from(step: RowIndex) -> u64 {
59        step.0 as u64
60    }
61}
62
63impl From<RowIndex> for usize {
64    fn from(step: RowIndex) -> usize {
65        step.0 as usize
66    }
67}
68
69impl From<RowIndex> for Felt {
70    fn from(step: RowIndex) -> Felt {
71        Felt::from_u32(step.0)
72    }
73}
74
75// INTO ROW INDEX
76// ================================================================================================
77
78/// Converts a usize value into a [`RowIndex`].
79///
80/// # Panics
81///
82/// This function will panic if the number represented by the usize is greater than the maximum
83/// [`RowIndex`] value, [`u32::MAX`].
84impl From<usize> for RowIndex {
85    fn from(value: usize) -> Self {
86        let value = u32::try_from(value)
87            .map_err(|_| RowIndexError::InvalidSize(format!("{value}_usize").into()))
88            .unwrap();
89        value.into()
90    }
91}
92
93/// Converts a u64 value into a [`RowIndex`].
94///
95/// # Errors
96///
97/// This function returns an error if the number represented by the u64 is greater than the
98/// maximum [`RowIndex`] value, [`u32::MAX`].
99impl TryFrom<u64> for RowIndex {
100    type Error = RowIndexError;
101
102    fn try_from(value: u64) -> Result<Self, Self::Error> {
103        let value = u32::try_from(value)
104            .map_err(|_| RowIndexError::InvalidSize(format!("{value}_u64").into()))?;
105        Ok(RowIndex::from(value))
106    }
107}
108
109impl From<u32> for RowIndex {
110    fn from(value: u32) -> Self {
111        Self(value)
112    }
113}
114
115impl miden_utils_indexing::Idx for RowIndex {}
116
117impl Serializable for RowIndex {
118    fn write_into<W: ByteWriter>(&self, target: &mut W) {
119        self.0.write_into(target);
120    }
121}
122
123impl Deserializable for RowIndex {
124    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
125        Ok(Self(u32::read_from(source)?))
126    }
127
128    fn min_serialized_size() -> usize {
129        u32::min_serialized_size()
130    }
131}
132
133/// Converts an i32 value into a [`RowIndex`].
134///
135/// # Panics
136///
137/// This function will panic if the number represented by the i32 is less than 0.
138impl From<i32> for RowIndex {
139    fn from(value: i32) -> Self {
140        let value = u32::try_from(value)
141            .map_err(|_| RowIndexError::InvalidSize(format!("{value}_i32").into()))
142            .unwrap();
143        RowIndex(value)
144    }
145}
146
147// ROW INDEX OPS
148// ================================================================================================
149
150/// Subtracts a usize from a [`RowIndex`].
151///
152/// # Panics
153///
154/// This function will panic if the number represented by the usize is greater than the maximum
155/// [`RowIndex`] value, `u32::MAX`.
156impl Sub<usize> for RowIndex {
157    type Output = RowIndex;
158
159    fn sub(self, rhs: usize) -> Self::Output {
160        let rhs = u32::try_from(rhs)
161            .map_err(|_| RowIndexError::InvalidSize(format!("{rhs}_usize").into()))
162            .unwrap();
163        RowIndex(self.0 - rhs)
164    }
165}
166
167impl SubAssign<u32> for RowIndex {
168    fn sub_assign(&mut self, rhs: u32) {
169        self.0 -= rhs;
170    }
171}
172
173impl Sub<RowIndex> for RowIndex {
174    type Output = usize;
175
176    fn sub(self, rhs: RowIndex) -> Self::Output {
177        (self.0 - rhs.0) as usize
178    }
179}
180
181impl RowIndex {
182    pub fn saturating_sub(self, rhs: u32) -> Self {
183        RowIndex(self.0.saturating_sub(rhs))
184    }
185
186    pub fn max(self, other: RowIndex) -> Self {
187        RowIndex(self.0.max(other.0))
188    }
189}
190
191/// Adds a usize to a [`RowIndex`].
192///
193/// # Panics
194///
195/// This function will panic if the number represented by the usize is greater than the maximum
196/// [`RowIndex`] value, `u32::MAX`.
197impl Add<usize> for RowIndex {
198    type Output = RowIndex;
199
200    fn add(self, rhs: usize) -> Self::Output {
201        let rhs = u32::try_from(rhs)
202            .map_err(|_| RowIndexError::InvalidSize(format!("{rhs}_usize").into()))
203            .unwrap();
204        RowIndex(self.0 + rhs)
205    }
206}
207
208impl Add<RowIndex> for u32 {
209    type Output = RowIndex;
210
211    fn add(self, rhs: RowIndex) -> Self::Output {
212        RowIndex(self + rhs.0)
213    }
214}
215
216/// Adds a u32 value to a RowIndex in place.
217///
218/// # Panics
219///
220/// This function will panic if the internal value of the [`RowIndex`] would exceed the maximum
221/// value `u32::MAX`.
222impl AddAssign<u32> for RowIndex {
223    fn add_assign(&mut self, rhs: u32) {
224        self.0 += rhs;
225    }
226}
227
228/// Adds a usize value to a RowIndex in place.
229///
230/// # Panics
231///
232/// This function will panic if the internal value of the [`RowIndex`] would exceed the maximum
233/// value `u32::MAX`.
234impl AddAssign<usize> for RowIndex {
235    fn add_assign(&mut self, rhs: usize) {
236        let rhs = u32::try_from(rhs)
237            .map_err(|_| RowIndexError::InvalidSize(format!("{rhs}_usize").into()))
238            .unwrap();
239        self.0 += rhs;
240    }
241}
242
243impl Mul<RowIndex> for usize {
244    type Output = RowIndex;
245
246    fn mul(self, rhs: RowIndex) -> Self::Output {
247        (self * rhs.0 as usize).into()
248    }
249}
250
251// ROW INDEX EQUALITY AND ORDERING
252// ================================================================================================
253
254impl PartialEq<RowIndex> for RowIndex {
255    fn eq(&self, rhs: &RowIndex) -> bool {
256        self.0 == rhs.0
257    }
258}
259
260impl PartialEq<usize> for RowIndex {
261    fn eq(&self, rhs: &usize) -> bool {
262        self.0
263            == u32::try_from(*rhs)
264                .map_err(|_| RowIndexError::InvalidSize(format!("{}_usize", *rhs).into()))
265                .unwrap()
266    }
267}
268
269impl PartialEq<RowIndex> for i32 {
270    fn eq(&self, rhs: &RowIndex) -> bool {
271        *self as u32 == u32::from(*rhs)
272    }
273}
274
275impl PartialOrd<usize> for RowIndex {
276    fn partial_cmp(&self, rhs: &usize) -> Option<core::cmp::Ordering> {
277        let rhs = u32::try_from(*rhs)
278            .map_err(|_| RowIndexError::InvalidSize(format!("{}_usize", *rhs).into()))
279            .unwrap();
280        self.0.partial_cmp(&rhs)
281    }
282}
283
284impl<T> Index<RowIndex> for [T] {
285    type Output = T;
286    fn index(&self, i: RowIndex) -> &Self::Output {
287        &self[i.0 as usize]
288    }
289}
290
291impl<T> IndexMut<RowIndex> for [T] {
292    fn index_mut(&mut self, i: RowIndex) -> &mut Self::Output {
293        &mut self[i.0 as usize]
294    }
295}
296
297impl<T> Index<RowIndex> for Vec<T> {
298    type Output = T;
299    fn index(&self, i: RowIndex) -> &Self::Output {
300        &self.as_slice()[i]
301    }
302}
303
304impl RangeBounds<RowIndex> for RowIndex {
305    fn start_bound(&self) -> Bound<&Self> {
306        Bound::Included(self)
307    }
308    fn end_bound(&self) -> Bound<&Self> {
309        Bound::Included(self)
310    }
311}
312
313// TESTS
314// ================================================================================================
315
316// ARBITRARY (proptest)
317// ================================================================================================
318
319#[cfg(any(test, feature = "arbitrary"))]
320mod arbitrary {
321    use proptest::prelude::*;
322
323    use super::RowIndex;
324
325    impl Arbitrary for RowIndex {
326        type Parameters = ();
327        type Strategy = BoxedStrategy<Self>;
328
329        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
330            // Any u32 is a valid trace row index.
331            any::<u32>().prop_map(RowIndex).boxed()
332        }
333    }
334}
335
336#[cfg(test)]
337mod tests {
338    use alloc::collections::BTreeMap;
339
340    use miden_core::serde::{Deserializable, Serializable};
341
342    #[test]
343    fn row_index_ops() {
344        use super::RowIndex;
345
346        // Equality
347        assert_eq!(RowIndex(5), 5);
348        assert_eq!(RowIndex(5), RowIndex(5));
349        assert!(RowIndex(5) == RowIndex(5));
350        assert!(RowIndex(5) >= RowIndex(5));
351        assert!(RowIndex(6) >= RowIndex(5));
352        assert!(RowIndex(5) > RowIndex(4));
353        assert!(RowIndex(5) <= RowIndex(5));
354        assert!(RowIndex(4) <= RowIndex(5));
355        assert!(RowIndex(5) < RowIndex(6));
356
357        // Arithmetic
358        assert_eq!(RowIndex(5) + 3, 8);
359        assert_eq!(RowIndex(5) - 3, 2);
360        assert_eq!(3 + RowIndex(5), 8);
361        assert_eq!(2 * RowIndex(5), 10);
362
363        // Add assign
364        let mut step = RowIndex(5);
365        step += 5_u32;
366        assert_eq!(step, 10);
367    }
368
369    #[test]
370    fn row_index_range() {
371        use super::RowIndex;
372        let mut tree: BTreeMap<RowIndex, usize> = BTreeMap::new();
373        tree.insert(RowIndex(0), 0);
374        tree.insert(RowIndex(1), 1);
375        tree.insert(RowIndex(2), 2);
376        let acc =
377            tree.range(RowIndex::from(0)..RowIndex::from(tree.len()))
378                .fold(0, |acc, (key, val)| {
379                    assert_eq!(*key, RowIndex::from(acc));
380                    assert_eq!(*val, acc);
381                    acc + 1
382                });
383        assert_eq!(acc, 3);
384    }
385
386    #[test]
387    fn row_index_display() {
388        assert_eq!(format!("{}", super::RowIndex(5)), "5");
389    }
390
391    #[test]
392    fn row_index_serialization_roundtrip() {
393        let original = super::RowIndex(u32::MAX);
394        let bytes = original.to_bytes();
395
396        assert_eq!(bytes, u32::MAX.to_bytes());
397        assert_eq!(super::RowIndex::read_from_bytes(&bytes).unwrap(), original);
398    }
399}
miden_air/trace/rows.rs

miden_air/trace/
rows.rs
