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

miden_air/trace/
rows.rs
