omp_core/sparse_index.rs
1//! Index conversion traits for sparse containers.
2//!
3//! Defines `TrySparseIndex` for types that map to `usize` indices with
4//! validation, enabling enum keys, bounded integers, and other constrained
5//! index types.
6
7/// A trait for types that can be safely converted to and from indices.
8///
9/// This trait extends [`SparseIndex`] with fallible conversion methods,
10/// allowing for validation of index values during conversion. It's particularly
11/// useful for bounded types like small integers or enums with gaps in their
12/// value range.
13///
14/// # Examples
15///
16/// ```
17/// use omp_core::sparse_index::TrySparseIndex;
18///
19/// // u8 implements TrySparseIndex with bounds checking
20/// assert!(u8::try_from_index(255).is_ok());
21/// assert!(u8::try_from_index(256).is_err());
22/// ```
23pub trait TrySparseIndex: Sized {
24 /// The error type returned when index conversion fails.
25 type Error: std::error::Error;
26
27 /// Returns the index for this value.
28 fn index(&self) -> usize;
29
30 /// Converts an index to this type, assuming the index is valid.
31 ///
32 /// # Safety
33 ///
34 /// This method should only be called with indices that are known to be valid
35 /// for the type. For fallible conversion, use [`Self::try_from_index`].
36 fn from_index(index: usize) -> Self {
37 Self::try_from_index(index).unwrap()
38 }
39
40 /// Attempts to convert an index to this type.
41 ///
42 /// # Errors
43 ///
44 /// Returns an error if the index is not valid for this type.
45 fn try_from_index(index: usize) -> Result<Self, Self::Error>;
46
47 /// Validates that every index in a sorted iterator is valid for this type.
48 ///
49 /// The default checks each index individually: validity for an arbitrary
50 /// type (e.g. an enum with gaps) is not an interval, so probing only the
51 /// extremes is insufficient. Types whose valid indices form a contiguous
52 /// range (like the integer implementations) override this with an O(1)
53 /// min/max check.
54 fn validate_sorted(indices: impl DoubleEndedIterator<Item = usize>) -> Result<(), Self::Error> {
55 for index in indices {
56 Self::try_from_index(index)?;
57 }
58 Ok(())
59 }
60}
61
62/// Min/max bulk validation for types whose valid indices form a contiguous
63/// range: on a sorted iterator, checking the extremes covers every element.
64fn validate_extremes<T: TrySparseIndex>(
65 mut indices: impl DoubleEndedIterator<Item = usize>,
66) -> Result<(), T::Error> {
67 if let Some(max) = indices.next_back() {
68 T::try_from_index(max)?;
69 }
70 if let Some(min) = indices.next() {
71 T::try_from_index(min)?;
72 }
73 Ok(())
74}
75
76/// Blanket implementation of [`TrySparseIndex`] for all [`SparseIndex`] types.
77///
78/// This allows any infallible sparse index type to be used in contexts
79/// requiring [`TrySparseIndex`] without additional boilerplate.
80impl<T: SparseIndex> TrySparseIndex for T {
81 type Error = std::convert::Infallible;
82
83 fn index(&self) -> usize {
84 self.index()
85 }
86
87 fn from_index(index: usize) -> Self {
88 Self::from_index(index)
89 }
90
91 fn try_from_index(index: usize) -> Result<Self, Self::Error> {
92 Ok(Self::from_index(index))
93 }
94
95 fn validate_sorted(_: impl DoubleEndedIterator<Item = usize>) -> Result<(), Self::Error> {
96 Ok(())
97 }
98}
99
100/// A trait for types that can be infallibly converted to and from indices.
101///
102/// This trait is for types that have a bijective mapping with `usize` indices,
103/// where every possible index value is valid. Examples include most enums
104/// without gaps or wrapper types around indices.
105///
106/// For types that may have invalid index values, use [`TrySparseIndex`]
107/// instead.
108///
109/// # Examples
110///
111/// ```
112/// use omp_core::sparse_index::TrySparseIndex;
113///
114/// #[repr(usize)]
115/// #[derive(Copy, Clone, Debug)]
116/// enum Color {
117/// Red = 0,
118/// Green = 1,
119/// Blue = 2,
120/// }
121///
122/// #[derive(Debug)]
123/// struct ColorError(String);
124///
125/// impl std::fmt::Display for ColorError {
126/// fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
127/// write!(f, "{}", self.0)
128/// }
129/// }
130///
131/// impl std::error::Error for ColorError {}
132///
133/// impl TrySparseIndex for Color {
134/// type Error = ColorError;
135///
136/// fn index(&self) -> usize {
137/// *self as usize
138/// }
139///
140/// fn try_from_index(index: usize) -> Result<Self, Self::Error> {
141/// match index {
142/// 0 => Ok(Color::Red),
143/// 1 => Ok(Color::Green),
144/// 2 => Ok(Color::Blue),
145/// _ => Err(ColorError("Invalid color index".to_string())),
146/// }
147/// }
148/// }
149/// ```
150pub trait SparseIndex: Sized {
151 /// Returns the index for this value.
152 fn index(&self) -> usize;
153
154 /// Converts an index to this type.
155 ///
156 /// # Panics
157 ///
158 /// May panic if the index is not valid for this type. For fallible
159 /// conversion, implement [`TrySparseIndex`] instead.
160 fn from_index(index: usize) -> Self;
161}
162
163/// Error type for numeric index conversions that are out of bounds.
164#[derive(Debug, thiserror::Error)]
165pub enum NumericIndexError {
166 /// The provided index exceeds the maximum value for the target type.
167 #[error("index out of bounds: {received} is not in [0..{max}]")]
168 OutOfBounds {
169 /// Maximum valid index for the type.
170 max: usize,
171 /// Index that was provided.
172 received: usize,
173 },
174}
175
176/// Macro to implement [`TrySparseIndex`] for unsigned integer types.
177///
178/// This provides bounds-checked conversions for numeric types, ensuring
179/// that indices fit within the target type's range.
180macro_rules! impl_integers {
181 ($($u:ty => $i:ty),*) => {
182 $(
183 impl TrySparseIndex for $u {
184 type Error = NumericIndexError;
185
186 #[inline]
187 fn index(&self) -> usize {
188 *self as usize
189 }
190 #[inline]
191 fn from_index(index: usize) -> Self {
192 index as $u
193 }
194 #[inline]
195 fn try_from_index(index: usize) -> Result<Self, Self::Error> {
196 if index > <$u>::MAX as usize {
197 Err(NumericIndexError::OutOfBounds {
198 max: <$u>::MAX as usize,
199 received: index,
200 })
201 } else {
202 Ok(Self::from_index(index))
203 }
204 }
205 #[inline]
206 fn validate_sorted(
207 indices: impl DoubleEndedIterator<Item = usize>,
208 ) -> Result<(), Self::Error> {
209 validate_extremes::<Self>(indices)
210 }
211 }
212
213
214 impl TrySparseIndex for $i {
215 type Error = NumericIndexError;
216
217 #[inline]
218 fn index(&self) -> usize {
219 *self as usize
220 }
221 #[inline]
222 fn from_index(index: usize) -> Self {
223 index as $i
224 }
225 #[inline]
226 fn try_from_index(index: usize) -> Result<Self, Self::Error> {
227 if index > <$i>::MAX as usize {
228 Err(NumericIndexError::OutOfBounds {
229 max: <$i>::MAX as usize,
230 received: index,
231 })
232 } else {
233 Ok(Self::from_index(index))
234 }
235 }
236 #[inline]
237 fn validate_sorted(
238 indices: impl DoubleEndedIterator<Item = usize>,
239 ) -> Result<(), Self::Error> {
240 validate_extremes::<Self>(indices)
241 }
242 }
243
244 impl TrySparseIndex for std::num::NonZero<$i> {
245 type Error = NumericIndexError;
246
247 #[inline]
248 fn index(&self) -> usize {
249 self.get() as usize - 1
250 }
251 #[inline]
252 fn from_index(index: usize) -> Self {
253 // Checked add + checked conversion: truncating casts could
254 // otherwise produce 0 (e.g. index 255 for NonZeroI8 wrapping
255 // through 256), which NonZero must never hold.
256 let value = index
257 .checked_add(1)
258 .and_then(|v| <$i>::try_from(v).ok())
259 .expect("index out of range");
260 Self::new(value).expect("index + 1 is non-zero")
261 }
262 #[inline]
263 fn try_from_index(index: usize) -> Result<Self, Self::Error> {
264 if index >= <$i>::MAX as usize {
265 Err(NumericIndexError::OutOfBounds {
266 max: <$i>::MAX as usize - 1,
267 received: index,
268 })
269 } else {
270 Ok(Self::from_index(index))
271 }
272 }
273 #[inline]
274 fn validate_sorted(
275 indices: impl DoubleEndedIterator<Item = usize>,
276 ) -> Result<(), Self::Error> {
277 validate_extremes::<Self>(indices)
278 }
279 }
280
281 impl TrySparseIndex for std::num::NonZero<$u> {
282 type Error = NumericIndexError;
283
284 #[inline]
285 fn index(&self) -> usize {
286 self.get() as usize - 1
287 }
288 #[inline]
289 fn from_index(index: usize) -> Self {
290 // Checked add + checked conversion: truncating casts could
291 // otherwise produce 0 (e.g. index 255 for NonZeroU8 wrapping
292 // through 256), which NonZero must never hold.
293 let value = index
294 .checked_add(1)
295 .and_then(|v| <$u>::try_from(v).ok())
296 .expect("index out of range");
297 Self::new(value).expect("index + 1 is non-zero")
298 }
299 #[inline]
300 fn try_from_index(index: usize) -> Result<Self, Self::Error> {
301 if index >= <$u>::MAX as usize {
302 Err(NumericIndexError::OutOfBounds {
303 max: <$u>::MAX as usize - 1,
304 received: index,
305 })
306 } else {
307 Ok(Self::from_index(index))
308 }
309 }
310 #[inline]
311 fn validate_sorted(
312 indices: impl DoubleEndedIterator<Item = usize>,
313 ) -> Result<(), Self::Error> {
314 validate_extremes::<Self>(indices)
315 }
316 }
317 )*
318 };
319}
320
321impl_integers!(
322 u8 => i8,
323 u16 => i16,
324 u32 => i32,
325 u64 => i64,
326 usize => isize
327);