xingo_sparse/
index.rs

1//! # Chapter 5.7 — Typed indices
2//!
3//! ## Purpose
4//! Columns and rows of a matrix are both numbered from zero, and passing a
5//! row number where a column number was expected is the classic silent
6//! bug of sparse codes. [`Col`] and [`Row`] are distinct newtypes, so the
7//! compiler rejects that confusion at no runtime cost. They lived in
8//! `xingo-core` (Chapter 1.1) until task L1.2; the containers (Chapter 5.8)
9//! and the basis references (Chapter 5.1) speak them, so they moved down
10//! with the containers and `xingo-core` re-exports them unchanged.
11//!
12//! ## Notation
13//! A matrix has `n` columns, indexed by `j ∈ {0, …, n−1}`, and `m` rows,
14//! indexed by `i ∈ {0, …, m−1}`. `Col(j)` names column `j` and `Row(i)`
15//! names row `i`. In the solver a column is a variable and a row a
16//! constraint.
17//!
18//! ## Representation
19//! Both are `u32` wrappers (`PLAN.md` §3.2; D-0080, Q3): 2³² − 1 entities
20//! is ample, and halving the width of `row_idx` compared with `usize`
21//! saves memory bandwidth in every sparse kernel. Offsets into nonzero
22//! arrays (`col_ptr`, `row_ptr`) are `usize`, because `nnz` may exceed
23//! 2³².
24//!
25//! ## Invariants
26//! (I1) Conversion from `usize` never truncates: [`Col::from_usize`] and
27//!      [`Row::from_usize`] panic beyond `u32::MAX`.
28//! (I2) Range validity (`j < n`, `i < m`) is a property of the structure
29//!      that stores the index and is checked by its `check_invariants()`.
30
31use std::fmt;
32
33use crate::SparseError;
34
35macro_rules! typed_index {
36    ($(#[$doc:meta])* $name:ident, $what:literal, $prefix:literal) => {
37        $(#[$doc])*
38        #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default)]
39        pub struct $name(pub u32);
40
41        impl $name {
42            #[doc = concat!("Builds a ", $what, " index from a `usize`.")]
43            ///
44            /// # Panics
45            /// If `i > u32::MAX` (invariant I1).
46            #[inline]
47            pub fn from_usize(i: usize) -> Self {
48                Self(u32::try_from(i).expect(concat!($what, " index exceeds u32::MAX")))
49            }
50
51            /// Returns the index as a `usize`, ready for slice indexing.
52            #[inline]
53            pub const fn index(self) -> usize {
54                self.0 as usize
55            }
56        }
57
58        impl From<u32> for $name {
59            #[inline]
60            fn from(i: u32) -> Self {
61                Self(i)
62            }
63        }
64
65        impl From<$name> for usize {
66            #[inline]
67            fn from(i: $name) -> usize {
68                i.index()
69            }
70        }
71
72        impl fmt::Display for $name {
73            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
74                write!(f, concat!($prefix, "{}"), self.0)
75            }
76        }
77    };
78}
79
80typed_index!(
81    /// Index of a column (in the solver: a variable), `0 ≤ j < n`.
82    Col,
83    "column",
84    "c"
85);
86
87typed_index!(
88    /// Index of a row (in the solver: a constraint), `0 ≤ i < m`.
89    Row,
90    "row",
91    "r"
92);
93
94/// Converts a dimension to `u32`, reporting [`SparseError::TooLarge`] on
95/// overflow.
96pub(crate) fn dim_to_u32(what: &'static str, value: usize) -> Result<u32, SparseError> {
97    u32::try_from(value).map_err(|_| SparseError::TooLarge { what, value })
98}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103
104    #[test]
105    fn round_trip_and_display() {
106        let j = Col::from_usize(7);
107        assert_eq!(j.index(), 7);
108        assert_eq!(usize::from(j), 7);
109        assert_eq!(j.to_string(), "c7");
110        assert_eq!(Row::from(3).to_string(), "r3");
111    }
112
113    #[test]
114    #[cfg(target_pointer_width = "64")]
115    #[should_panic(expected = "exceeds u32::MAX")]
116    fn from_usize_rejects_overflow() {
117        let _ = Row::from_usize(1 << 33);
118    }
119
120    #[test]
121    fn dim_to_u32_reports_overflow() {
122        assert_eq!(dim_to_u32("rows", 5), Ok(5));
123        #[cfg(target_pointer_width = "64")]
124        assert!(matches!(
125            dim_to_u32("rows", 1 << 33),
126            Err(SparseError::TooLarge { .. })
127        ));
128    }
129}
xingo_sparse/index.rs

xingo_sparse/
index.rs
