hurray_core/layout/
csf.rs

1//! CSF (Compressed Sparse Fiber) layout descriptor.
2//!
3//! Tag `0x09`. Rank MUST be ≥ 3. Buffer count = 2·rank+1 (values + rank pos arrays + rank crd arrays).
4//! See `docs/spec/layouts/csf.md`.
5
6/// Descriptor for the CSF (Compressed Sparse Fiber) sparse layout.
7///
8/// CSF is the rank-N generalisation of CSR/CSC, storing a sparse tensor as a
9/// tree of `rank` levels. Each level compresses one mode with a `(pos, crd)` pair;
10/// the `values` buffer holds non-zero values at the leaves.
11///
12/// CSF is **defined only for rank ≥ 3 tensors** in this version of the specification.
13/// Rank-2 sparse matrices are served by CSR/CSC; see [`crate::layout::CsrLayout`].
14///
15/// `buffer_count = 2·rank+1` comes from the layout descriptor alone because
16/// `mode_order.len()` equals the tensor rank — the rank is embedded in the field,
17/// not repeated separately.
18///
19/// # Buffer table
20///
21/// | Buffer index | Name | Element type | Length |
22/// |---|---|---|---|
23/// | `0` | `values` | tensor element type | `nnz` elements |
24/// | `2L + 1` | `pos_L` | `uint64` | `n_{L-1} + 1` elements (`2` for L=0) |
25/// | `2L + 2` | `crd_L` | `uint64` | `n_L` elements (`nnz` for the leaf level) |
26///
27/// where `n_L` is the count of tree nodes at level `L`, `n_{-1} = 1` (virtual root),
28/// and `n_{rank-1} = nnz`.
29///
30/// The `byte_offset` field MUST be `0` for CSF tensors — the first element is
31/// reached by descending the tree, not at a fixed offset.
32///
33/// # Examples
34///
35/// ```
36/// use hurray_core::layout::{CsfLayout, LayoutDescriptor};
37///
38/// // Rank-3 sparse tensor with 4 non-zeros, identity mode_order.
39/// let layout = CsfLayout::new(4, vec![0, 1, 2]);
40/// let desc = LayoutDescriptor::Csf(layout);
41/// assert_eq!(desc.tag(), 0x09);
42/// // 2*rank+1 = 2*3+1 = 7 buffers.
43/// assert_eq!(desc.buffer_count().map(|n| n.get()), Some(7));
44/// ```
45#[derive(Debug, Clone, PartialEq, Eq, Hash)]
46#[non_exhaustive]
47pub struct CsfLayout {
48    /// Number of stored (non-zero) elements. MAY be 0 for an empty sparse tensor.
49    pub nnz: u64,
50
51    /// Permutation of `0..rank-1`; `mode_order[L]` is the logical dimension stored at
52    /// tree level `L`. The tensor rank equals `mode_order.len()`.
53    ///
54    /// `mode_order` is stored here (rather than just `rank`) because buffer_count()
55    /// and validate_against_shape() both need it, and carrying the full permutation
56    /// avoids a separate rank field while making the accessor surface explicit.
57    // WHY mode_order carries rank: buffer_count() = 2·rank+1 needs rank, and the
58    // permutation is always validated to have length == rank anyway — no duplication.
59    pub mode_order: Vec<u32>,
60}
61
62impl CsfLayout {
63    /// Creates a new [`CsfLayout`] with the given number of non-zeros and mode order.
64    ///
65    /// This constructor does not validate that `mode_order` is a valid permutation
66    /// of `0..mode_order.len()` or that `mode_order.len() >= 3`; call
67    /// [`crate::layout::LayoutDescriptor::validate_against_shape`] with the tensor
68    /// shape to perform those checks.
69    ///
70    /// # Examples
71    ///
72    /// ```
73    /// use hurray_core::layout::CsfLayout;
74    ///
75    /// // Rank-3 tensor, identity mode order, 10 non-zeros.
76    /// let c = CsfLayout::new(10, vec![0, 1, 2]);
77    /// assert_eq!(c.nnz, 10);
78    /// assert_eq!(c.mode_order, [0, 1, 2]);
79    ///
80    /// // Rank-4 tensor with reordered modes.
81    /// let c4 = CsfLayout::new(0, vec![3, 0, 1, 2]);
82    /// assert_eq!(c4.mode_order.len(), 4);
83    /// ```
84    pub fn new(nnz: u64, mode_order: Vec<u32>) -> Self {
85        Self { nnz, mode_order }
86    }
87}
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92    use crate::layout::LayoutDescriptor;
93    use std::num::NonZeroU8;
94
95    // ── Tag ──────────────────────────────────────────────────────────────────
96
97    /// Spec §csf.md: layout tag MUST be 0x09.
98    #[test]
99    fn csf_tag_is_0x09() {
100        let layout = LayoutDescriptor::Csf(CsfLayout::new(0, vec![0, 1, 2]));
101        assert_eq!(layout.tag(), 0x09);
102    }
103
104    /// Tag is independent of nnz and mode_order content.
105    #[test]
106    fn csf_tag_is_0x09_for_varying_nnz_and_permutation() {
107        let layout = LayoutDescriptor::Csf(CsfLayout::new(999, vec![2, 0, 1, 3]));
108        assert_eq!(layout.tag(), 0x09);
109    }
110
111    // ── Buffer count ─────────────────────────────────────────────────────────
112
113    /// Spec §csf.md §Buffer Table: buffer_count = 2·rank+1.
114    /// rank=3 → 2*3+1 = 7.
115    #[test]
116    fn csf_buffer_count_rank3_is_7() {
117        let layout = LayoutDescriptor::Csf(CsfLayout::new(5, vec![0, 1, 2]));
118        assert_eq!(layout.buffer_count(), Some(NonZeroU8::new(7).unwrap()));
119    }
120
121    /// rank=4 → 2*4+1 = 9.
122    #[test]
123    fn csf_buffer_count_rank4_is_9() {
124        let layout = LayoutDescriptor::Csf(CsfLayout::new(0, vec![0, 1, 2, 3]));
125        assert_eq!(layout.buffer_count(), Some(NonZeroU8::new(9).unwrap()));
126    }
127
128    /// rank=5 → 2*5+1 = 11.
129    #[test]
130    fn csf_buffer_count_rank5_is_11() {
131        let layout = LayoutDescriptor::Csf(CsfLayout::new(0, vec![0, 1, 2, 3, 4]));
132        assert_eq!(layout.buffer_count(), Some(NonZeroU8::new(11).unwrap()));
133    }
134
135    /// buffer_count is derived from mode_order.len(), not a separate rank field.
136    #[test]
137    fn csf_buffer_count_derived_from_mode_order_len() {
138        // Non-identity permutation: rank still equals mode_order.len().
139        let layout = LayoutDescriptor::Csf(CsfLayout::new(10, vec![2, 0, 1]));
140        // 2*3+1 = 7
141        assert_eq!(layout.buffer_count(), Some(NonZeroU8::new(7).unwrap()));
142    }
143
144    // ── CsfLayout::new stores fields faithfully ───────────────────────────────
145
146    #[test]
147    fn csf_layout_new_stores_nnz() {
148        let c = CsfLayout::new(42, vec![0, 1, 2]);
149        assert_eq!(c.nnz, 42);
150    }
151
152    #[test]
153    fn csf_layout_new_stores_mode_order() {
154        let mo = vec![2u32, 0, 1];
155        let c = CsfLayout::new(0, mo.clone());
156        assert_eq!(c.mode_order, mo);
157    }
158
159    #[test]
160    fn csf_layout_new_nnz_zero_is_valid() {
161        let c = CsfLayout::new(0, vec![0, 1, 2]);
162        assert_eq!(c.nnz, 0);
163    }
164
165    // ── validate_against_shape ───────────────────────────────────────────────
166
167    /// Spec §csf.md §Validity Constraints: rank MUST be >= 3.
168    #[test]
169    fn csf_validate_accepts_rank3() {
170        let layout = LayoutDescriptor::Csf(CsfLayout::new(0, vec![0, 1, 2]));
171        let shape = crate::Shape::new(vec![2u64, 3, 4]).unwrap();
172        assert!(layout.validate_against_shape(&shape).is_ok());
173    }
174
175    #[test]
176    fn csf_validate_accepts_rank4() {
177        let layout = LayoutDescriptor::Csf(CsfLayout::new(0, vec![0, 1, 2, 3]));
178        let shape = crate::Shape::new(vec![2u64, 3, 4, 5]).unwrap();
179        assert!(layout.validate_against_shape(&shape).is_ok());
180    }
181
182    #[test]
183    fn csf_validate_accepts_rank5() {
184        let layout = LayoutDescriptor::Csf(CsfLayout::new(0, vec![0, 1, 2, 3, 4]));
185        let shape = crate::Shape::new(vec![2u64, 3, 4, 5, 6]).unwrap();
186        assert!(layout.validate_against_shape(&shape).is_ok());
187    }
188
189    /// Spec §csf.md: CSF MUST NOT be used below rank 3.
190    #[test]
191    fn csf_validate_rejects_rank0() {
192        let layout = LayoutDescriptor::Csf(CsfLayout::new(0, vec![]));
193        assert!(matches!(
194            layout.validate_against_shape(&crate::Shape::scalar()),
195            Err(crate::Error::InvalidLayout(_))
196        ));
197    }
198
199    #[test]
200    fn csf_validate_rejects_rank1() {
201        let layout = LayoutDescriptor::Csf(CsfLayout::new(0, vec![0]));
202        let shape = crate::Shape::new(vec![10u64]).unwrap();
203        assert!(matches!(
204            layout.validate_against_shape(&shape),
205            Err(crate::Error::InvalidLayout(_))
206        ));
207    }
208
209    #[test]
210    fn csf_validate_rejects_rank2() {
211        let layout = LayoutDescriptor::Csf(CsfLayout::new(0, vec![0, 1]));
212        let shape = crate::Shape::new(vec![4u64, 5]).unwrap();
213        assert!(matches!(
214            layout.validate_against_shape(&shape),
215            Err(crate::Error::InvalidLayout(_))
216        ));
217    }
218
219    /// mode_order.len() must equal shape.rank().
220    #[test]
221    fn csf_validate_rejects_mode_order_len_not_equal_to_rank() {
222        // mode_order has 4 entries but shape has rank 3.
223        let layout = LayoutDescriptor::Csf(CsfLayout::new(0, vec![0, 1, 2, 3]));
224        let shape = crate::Shape::new(vec![2u64, 3, 4]).unwrap();
225        assert!(matches!(
226            layout.validate_against_shape(&shape),
227            Err(crate::Error::InvalidLayout(_))
228        ));
229    }
230
231    /// mode_order out-of-range value (>= rank) must be rejected.
232    #[test]
233    fn csf_validate_rejects_mode_order_out_of_range_value() {
234        // mode_order[2]=3 is out of range for rank=3.
235        let layout = LayoutDescriptor::Csf(CsfLayout::new(0, vec![0, 1, 3]));
236        let shape = crate::Shape::new(vec![2u64, 3, 4]).unwrap();
237        assert!(matches!(
238            layout.validate_against_shape(&shape),
239            Err(crate::Error::InvalidLayout(_))
240        ));
241    }
242
243    /// mode_order with a repeated value (not a permutation) must be rejected.
244    #[test]
245    fn csf_validate_rejects_mode_order_repeated_value() {
246        // [0, 1, 1] repeats dimension 1.
247        let layout = LayoutDescriptor::Csf(CsfLayout::new(0, vec![0, 1, 1]));
248        let shape = crate::Shape::new(vec![2u64, 3, 4]).unwrap();
249        assert!(matches!(
250            layout.validate_against_shape(&shape),
251            Err(crate::Error::InvalidLayout(_))
252        ));
253    }
254
255    /// Non-identity permutation [2, 0, 1] must be accepted.
256    #[test]
257    fn csf_validate_accepts_non_identity_permutation() {
258        let layout = LayoutDescriptor::Csf(CsfLayout::new(4, vec![2, 0, 1]));
259        let shape = crate::Shape::new(vec![2u64, 3, 4]).unwrap();
260        assert!(layout.validate_against_shape(&shape).is_ok());
261    }
262
263    /// Reverse permutation [2, 1, 0] must be accepted.
264    #[test]
265    fn csf_validate_accepts_reverse_permutation() {
266        let layout = LayoutDescriptor::Csf(CsfLayout::new(0, vec![2, 1, 0]));
267        let shape = crate::Shape::new(vec![2u64, 3, 4]).unwrap();
268        assert!(layout.validate_against_shape(&shape).is_ok());
269    }
270
271    // ── PartialEq / Clone / Debug derives ────────────────────────────────────
272
273    #[test]
274    fn csf_layout_partial_eq() {
275        let a = CsfLayout::new(4, vec![0, 1, 2]);
276        let b = CsfLayout::new(4, vec![0, 1, 2]);
277        assert_eq!(a, b);
278    }
279
280    #[test]
281    fn csf_layout_ne_different_nnz() {
282        let a = CsfLayout::new(4, vec![0, 1, 2]);
283        let b = CsfLayout::new(0, vec![0, 1, 2]);
284        assert_ne!(a, b);
285    }
286
287    #[test]
288    fn csf_layout_clone_is_equal() {
289        let orig = CsfLayout::new(10, vec![2, 0, 1]);
290        assert_eq!(orig.clone(), orig);
291    }
292
293    #[test]
294    fn csf_layout_debug_is_non_empty() {
295        let c = CsfLayout::new(0, vec![0, 1, 2]);
296        assert!(!format!("{c:?}").is_empty());
297    }
298}
hurray_core/layout/csf.rs

hurray_core/layout/
csf.rs
