oxgraph_layout_util/integrity.rs
1//! Read-time offset-integrity primitives.
2//!
3//! View-open validation walks borrowed offset and value arrays
4//! ([`check_offsets_monotonic`], [`check_value_range`],
5//! [`check_offset_section`]) and converts already-validated indexes
6//! infallibly ([`index_to_usize_validated`], [`usize_to_index_validated`]).
7//!
8//! Helpers return the small typed [`OffsetIntegrityIssue`] enum instead of
9//! crate-specific error types; callers map the issue to their own typed error
10//! at the boundary.
11
12use core::{error::Error, fmt};
13
14use crate::{LayoutIndex, ZerocopyWord};
15
16/// Reasons a borrowed offset or value array failed structural validation.
17///
18/// # Performance
19///
20/// Formatting is `O(message length)`.
21#[derive(Clone, Copy, Debug, Eq, PartialEq)]
22#[non_exhaustive]
23pub enum OffsetIntegrityIssue {
24 /// Length did not match `count + 1`.
25 Length {
26 /// Expected length (`count + 1`).
27 expected: usize,
28 /// Observed length.
29 actual: usize,
30 },
31 /// `expected_count + 1` overflowed `usize`, so no valid length exists.
32 CountOverflow {
33 /// The element count whose successor overflowed.
34 count: usize,
35 },
36 /// `offsets[0]` was not zero.
37 FirstNonZero {
38 /// Observed first offset.
39 actual: usize,
40 },
41 /// `offsets[index] < offsets[index - 1]`.
42 NonMonotonic {
43 /// Index where monotonicity failed.
44 index: usize,
45 /// Offset at `index - 1`.
46 previous: usize,
47 /// Offset at `index`.
48 actual: usize,
49 },
50 /// `offsets[count]` did not match `value_len`.
51 FinalMismatch {
52 /// Observed final offset.
53 final_offset: usize,
54 /// Length of the values array.
55 value_len: usize,
56 },
57 /// A value at `index` was not less than the dense `bound`.
58 ValueOutOfRange {
59 /// Index of the offending value.
60 index: usize,
61 /// Observed value.
62 value: usize,
63 /// Exclusive upper bound.
64 bound: usize,
65 },
66 /// A word's value at `index` did not fit in `usize` on the current target.
67 UsizeOverflow {
68 /// Slice position of the offending word.
69 index: usize,
70 },
71}
72
73impl fmt::Display for OffsetIntegrityIssue {
74 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
75 match self {
76 Self::Length { expected, actual } => write!(
77 formatter,
78 "offsets length {actual} does not match expected {expected}"
79 ),
80 Self::CountOverflow { count } => {
81 write!(formatter, "element count {count} + 1 overflows usize")
82 }
83 Self::FirstNonZero { actual } => {
84 write!(formatter, "first offset {actual} must be zero")
85 }
86 Self::NonMonotonic {
87 index,
88 previous,
89 actual,
90 } => write!(
91 formatter,
92 "offsets[{index}] = {actual} is less than offsets[{}] = {previous}",
93 index - 1
94 ),
95 Self::FinalMismatch {
96 final_offset,
97 value_len,
98 } => write!(
99 formatter,
100 "final offset {final_offset} does not match values length {value_len}"
101 ),
102 Self::ValueOutOfRange {
103 index,
104 value,
105 bound,
106 } => write!(
107 formatter,
108 "values[{index}] = {value} is not less than bound {bound}"
109 ),
110 Self::UsizeOverflow { index } => write!(
111 formatter,
112 "word at slice index {index} did not fit in usize"
113 ),
114 }
115 }
116}
117
118impl Error for OffsetIntegrityIssue {}
119
120/// Converts an already-validated index into `usize`.
121///
122/// Returns `None` only when the value does not fit in `usize`. Call sites that
123/// have proven the value fits (because a prior validation pass enforced it)
124/// should `unwrap_or_else(|| unreachable!("validated …"))` with a proof comment;
125/// this helper deliberately does not embed that `unreachable!`, because the
126/// proof obligation belongs to the validated call site, not the shared helper.
127///
128/// # Performance
129///
130/// This function is `O(1)`.
131#[inline]
132#[must_use]
133pub fn index_to_usize_validated<I: LayoutIndex>(value: I) -> Option<usize> {
134 value.to_usize()
135}
136
137/// Converts an already-validated `usize` slot into the target index width.
138///
139/// Returns `None` only when the value does not fit. See
140/// [`index_to_usize_validated`] for the proof-obligation convention.
141///
142/// # Performance
143///
144/// This function is `O(1)`.
145#[inline]
146#[must_use]
147pub fn usize_to_index_validated<I: LayoutIndex>(value: usize) -> Option<I> {
148 I::from_usize(value)
149}
150
151/// Verifies `offsets[0] == 0` and that `offsets` is non-decreasing.
152///
153/// # Errors
154///
155/// Returns [`OffsetIntegrityIssue::FirstNonZero`] when the first offset is
156/// non-zero, [`OffsetIntegrityIssue::NonMonotonic`] when an offset decreases
157/// from the previous, and [`OffsetIntegrityIssue::UsizeOverflow`] when a
158/// word's value does not fit in `usize`.
159///
160/// # Performance
161///
162/// This function is `O(offsets.len())`.
163pub fn check_offsets_monotonic<W: ZerocopyWord>(offsets: &[W]) -> Result<(), OffsetIntegrityIssue> {
164 let mut previous: usize = 0;
165 for (index, word) in offsets.iter().copied().enumerate() {
166 let offset = word
167 .read_as_usize()
168 .ok_or(OffsetIntegrityIssue::UsizeOverflow { index })?;
169 if index == 0 {
170 if offset != 0 {
171 return Err(OffsetIntegrityIssue::FirstNonZero { actual: offset });
172 }
173 } else if offset < previous {
174 return Err(OffsetIntegrityIssue::NonMonotonic {
175 index,
176 previous,
177 actual: offset,
178 });
179 }
180 previous = offset;
181 }
182 Ok(())
183}
184
185/// Verifies every value in `values` is less than `bound`.
186///
187/// # Errors
188///
189/// Returns [`OffsetIntegrityIssue::ValueOutOfRange`] when a value is at or
190/// above `bound`, and [`OffsetIntegrityIssue::UsizeOverflow`] when a word's
191/// value does not fit in `usize`.
192///
193/// # Performance
194///
195/// This function is `O(values.len())`.
196pub fn check_value_range<W: ZerocopyWord>(
197 values: &[W],
198 bound: usize,
199) -> Result<(), OffsetIntegrityIssue> {
200 for (index, word) in values.iter().copied().enumerate() {
201 let value = word
202 .read_as_usize()
203 .ok_or(OffsetIntegrityIssue::UsizeOverflow { index })?;
204 if value >= bound {
205 return Err(OffsetIntegrityIssue::ValueOutOfRange {
206 index,
207 value,
208 bound,
209 });
210 }
211 }
212 Ok(())
213}
214
215/// Validates one offset section against `expected_count` rows and a backing
216/// values array of length `value_len`.
217///
218/// Performs four checks: length matches `expected_count + 1`, first offset is
219/// zero, offsets are non-decreasing, and the final offset matches `value_len`.
220/// Because offsets are monotonic and the final offset equals `value_len`, every
221/// interior offset is implied to be `<= value_len`; the borrowed-view slicing in
222/// CSR/BCSR relies on that consequence and the proofs assert it directly.
223///
224/// # Errors
225///
226/// Returns the first [`OffsetIntegrityIssue`] encountered. Reports
227/// [`OffsetIntegrityIssue::CountOverflow`] when `expected_count + 1` overflows.
228///
229/// # Performance
230///
231/// This function is `O(offsets.len())`.
232pub fn check_offset_section<W: ZerocopyWord>(
233 offsets: &[W],
234 expected_count: usize,
235 value_len: usize,
236) -> Result<(), OffsetIntegrityIssue> {
237 let Some(expected) = expected_count.checked_add(1) else {
238 return Err(OffsetIntegrityIssue::CountOverflow {
239 count: expected_count,
240 });
241 };
242 if offsets.len() != expected {
243 return Err(OffsetIntegrityIssue::Length {
244 expected,
245 actual: offsets.len(),
246 });
247 }
248 check_offsets_monotonic(offsets)?;
249 let final_index = offsets.len() - 1;
250 let final_offset = offsets[final_index]
251 .read_as_usize()
252 .ok_or(OffsetIntegrityIssue::UsizeOverflow { index: final_index })?;
253 if final_offset != value_len {
254 return Err(OffsetIntegrityIssue::FinalMismatch {
255 final_offset,
256 value_len,
257 });
258 }
259 Ok(())
260}