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, Default, 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
108impl miden_utils_indexing::Idx for RowIndex {}
109
110/// Converts an i32 value into a [`RowIndex`].
111///
112/// # Panics
113///
114/// This function will panic if the number represented by the i32 is less than 0.
115impl From<i32> for RowIndex {
116    fn from(value: i32) -> Self {
117        let value = u32::try_from(value)
118            .map_err(|_| RowIndexError::InvalidSize(format!("{value}_i32").into()))
119            .unwrap();
120        RowIndex(value)
121    }
122}
123
124// ROW INDEX OPS
125// ================================================================================================
126
127/// Subtracts a usize from a [`RowIndex`].
128///
129/// # Panics
130///
131/// This function will panic if the number represented by the usize is greater than the maximum
132/// [`RowIndex`] value, `u32::MAX`.
133impl Sub<usize> for RowIndex {
134    type Output = RowIndex;
135
136    fn sub(self, rhs: usize) -> Self::Output {
137        let rhs = u32::try_from(rhs)
138            .map_err(|_| RowIndexError::InvalidSize(format!("{rhs}_usize").into()))
139            .unwrap();
140        RowIndex(self.0 - rhs)
141    }
142}
143
144impl SubAssign<u32> for RowIndex {
145    fn sub_assign(&mut self, rhs: u32) {
146        self.0 -= rhs;
147    }
148}
149
150impl Sub<RowIndex> for RowIndex {
151    type Output = usize;
152
153    fn sub(self, rhs: RowIndex) -> Self::Output {
154        (self.0 - rhs.0) as usize
155    }
156}
157
158impl RowIndex {
159    pub fn saturating_sub(self, rhs: u32) -> Self {
160        RowIndex(self.0.saturating_sub(rhs))
161    }
162
163    pub fn max(self, other: RowIndex) -> Self {
164        RowIndex(self.0.max(other.0))
165    }
166}
167
168/// Adds a usize to a [`RowIndex`].
169///
170/// # Panics
171///
172/// This function will panic if the number represented by the usize is greater than the maximum
173/// [`RowIndex`] value, `u32::MAX`.
174impl Add<usize> for RowIndex {
175    type Output = RowIndex;
176
177    fn add(self, rhs: usize) -> Self::Output {
178        let rhs = u32::try_from(rhs)
179            .map_err(|_| RowIndexError::InvalidSize(format!("{rhs}_usize").into()))
180            .unwrap();
181        RowIndex(self.0 + rhs)
182    }
183}
184
185impl Add<RowIndex> for u32 {
186    type Output = RowIndex;
187
188    fn add(self, rhs: RowIndex) -> Self::Output {
189        RowIndex(self + rhs.0)
190    }
191}
192
193/// Adds a u32 value to a RowIndex in place.
194///
195/// # Panics
196///
197/// This function will panic if the internal value of the [`RowIndex`] would exceed the maximum
198/// value `u32::MAX`.
199impl AddAssign<u32> for RowIndex {
200    fn add_assign(&mut self, rhs: u32) {
201        self.0 += rhs;
202    }
203}
204
205/// Adds a usize value to a RowIndex in place.
206///
207/// # Panics
208///
209/// This function will panic if the internal value of the [`RowIndex`] would exceed the maximum
210/// value `u32::MAX`.
211impl AddAssign<usize> for RowIndex {
212    fn add_assign(&mut self, rhs: usize) {
213        let rhs = u32::try_from(rhs)
214            .map_err(|_| RowIndexError::InvalidSize(format!("{rhs}_usize").into()))
215            .unwrap();
216        self.0 += rhs;
217    }
218}
219
220impl Mul<RowIndex> for usize {
221    type Output = RowIndex;
222
223    fn mul(self, rhs: RowIndex) -> Self::Output {
224        (self * rhs.0 as usize).into()
225    }
226}
227
228// ROW INDEX EQUALITY AND ORDERING
229// ================================================================================================
230
231impl PartialEq<RowIndex> for RowIndex {
232    fn eq(&self, rhs: &RowIndex) -> bool {
233        self.0 == rhs.0
234    }
235}
236
237impl PartialEq<usize> for RowIndex {
238    fn eq(&self, rhs: &usize) -> bool {
239        self.0
240            == u32::try_from(*rhs)
241                .map_err(|_| RowIndexError::InvalidSize(format!("{}_usize", *rhs).into()))
242                .unwrap()
243    }
244}
245
246impl PartialEq<RowIndex> for i32 {
247    fn eq(&self, rhs: &RowIndex) -> bool {
248        *self as u32 == u32::from(*rhs)
249    }
250}
251
252impl PartialOrd<usize> for RowIndex {
253    fn partial_cmp(&self, rhs: &usize) -> Option<core::cmp::Ordering> {
254        let rhs = u32::try_from(*rhs)
255            .map_err(|_| RowIndexError::InvalidSize(format!("{}_usize", *rhs).into()))
256            .unwrap();
257        self.0.partial_cmp(&rhs)
258    }
259}
260
261impl<T> Index<RowIndex> for [T] {
262    type Output = T;
263    fn index(&self, i: RowIndex) -> &Self::Output {
264        &self[i.0 as usize]
265    }
266}
267
268impl<T> IndexMut<RowIndex> for [T] {
269    fn index_mut(&mut self, i: RowIndex) -> &mut Self::Output {
270        &mut self[i.0 as usize]
271    }
272}
273
274impl RangeBounds<RowIndex> for RowIndex {
275    fn start_bound(&self) -> Bound<&Self> {
276        Bound::Included(self)
277    }
278    fn end_bound(&self) -> Bound<&Self> {
279        Bound::Included(self)
280    }
281}
282
283// TESTS
284// ================================================================================================
285#[cfg(test)]
286mod tests {
287    use alloc::collections::BTreeMap;
288
289    #[test]
290    fn row_index_conversions() {
291        use super::RowIndex;
292        // Into
293        let _: RowIndex = 5.into();
294        let _: RowIndex = 5u32.into();
295        let _: RowIndex = (5usize).into();
296
297        // From
298        let _: u32 = RowIndex(5).into();
299        let _: u64 = RowIndex(5).into();
300        let _: usize = RowIndex(5).into();
301    }
302
303    #[test]
304    fn row_index_ops() {
305        use super::RowIndex;
306
307        // Equality
308        assert_eq!(RowIndex(5), 5);
309        assert_eq!(RowIndex(5), RowIndex(5));
310        assert!(RowIndex(5) == RowIndex(5));
311        assert!(RowIndex(5) >= RowIndex(5));
312        assert!(RowIndex(6) >= RowIndex(5));
313        assert!(RowIndex(5) > RowIndex(4));
314        assert!(RowIndex(5) <= RowIndex(5));
315        assert!(RowIndex(4) <= RowIndex(5));
316        assert!(RowIndex(5) < RowIndex(6));
317
318        // Arithmetic
319        assert_eq!(RowIndex(5) + 3, 8);
320        assert_eq!(RowIndex(5) - 3, 2);
321        assert_eq!(3 + RowIndex(5), 8);
322        assert_eq!(2 * RowIndex(5), 10);
323
324        // Add assign
325        let mut step = RowIndex(5);
326        step += 5_u32;
327        assert_eq!(step, 10);
328    }
329
330    #[test]
331    fn row_index_range() {
332        use super::RowIndex;
333        let mut tree: BTreeMap<RowIndex, usize> = BTreeMap::new();
334        tree.insert(RowIndex(0), 0);
335        tree.insert(RowIndex(1), 1);
336        tree.insert(RowIndex(2), 2);
337        let acc =
338            tree.range(RowIndex::from(0)..RowIndex::from(tree.len()))
339                .fold(0, |acc, (key, val)| {
340                    assert_eq!(*key, RowIndex::from(acc));
341                    assert_eq!(*val, acc);
342                    acc + 1
343                });
344        assert_eq!(acc, 3);
345    }
346
347    #[test]
348    fn row_index_display() {
349        assert_eq!(format!("{}", super::RowIndex(5)), "5");
350    }
351}
miden_air/trace/rows.rs

miden_air/trace/
rows.rs
