miden_air/trace/
rows.rs

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

miden_air/trace/
rows.rs
