Skip to main content

sheetkit_core/
traversal.rs

1//! Shared finite limits for traversing worksheet-shaped data.
2
3use crate::error::{Error, Result};
4use crate::resource::{
5    ResourceCategory, ResourceDimension, ResourceLimitError, ResourceOperation, ResourceStage,
6};
7
8/// Default maximum number of rows visited by one traversal.
9pub const DEFAULT_MAX_ROWS: u64 = 1_048_576;
10/// Default maximum number of columns visited by one traversal.
11pub const DEFAULT_MAX_COLUMNS: u64 = 16_384;
12/// Default maximum number of cells visited by one traversal.
13pub const DEFAULT_MAX_CELLS: u64 = 10_000_000;
14/// Default maximum number of bytes produced by one traversal.
15pub const DEFAULT_MAX_OUTPUT_BYTES: u64 = 512 * 1024 * 1024;
16
17/// Non-overridable maximum number of rows visited by one traversal.
18pub const HARD_MAX_ROWS: u64 = 1_048_576;
19/// Non-overridable maximum number of columns visited by one traversal.
20pub const HARD_MAX_COLUMNS: u64 = 16_384;
21/// Non-overridable maximum number of cells visited by one traversal.
22pub const HARD_MAX_CELLS: u64 = 100_000_000;
23/// Non-overridable maximum number of output bytes produced by one traversal.
24pub const HARD_MAX_OUTPUT_BYTES: u64 = 2 * 1024 * 1024 * 1024;
25
26/// Traversal layout policy.
27#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
28pub enum TraversalMode {
29    /// Visit and encode only occupied rows and cells.
30    #[default]
31    Sparse,
32    /// Visit the complete bounding rectangle, including empty positions.
33    Dense,
34}
35
36/// Finite resource limits shared by worksheet traversal operations.
37#[derive(Debug, Clone, Copy, PartialEq, Eq)]
38pub struct TraversalLimits {
39    max_rows: u64,
40    max_columns: u64,
41    max_cells: u64,
42    max_output_bytes: u64,
43}
44
45impl Default for TraversalLimits {
46    fn default() -> Self {
47        Self {
48            max_rows: DEFAULT_MAX_ROWS,
49            max_columns: DEFAULT_MAX_COLUMNS,
50            max_cells: DEFAULT_MAX_CELLS,
51            max_output_bytes: DEFAULT_MAX_OUTPUT_BYTES,
52        }
53    }
54}
55
56impl TraversalLimits {
57    /// Creates limits, rejecting zero values and values above hard ceilings.
58    pub fn new(
59        max_rows: u64,
60        max_columns: u64,
61        max_cells: u64,
62        max_output_bytes: u64,
63    ) -> Result<Self> {
64        validate_config(ResourceDimension::RowCount, max_rows, HARD_MAX_ROWS)?;
65        validate_config(
66            ResourceDimension::ColumnCount,
67            max_columns,
68            HARD_MAX_COLUMNS,
69        )?;
70        validate_config(ResourceDimension::CellCount, max_cells, HARD_MAX_CELLS)?;
71        validate_config(
72            ResourceDimension::OutputBytes,
73            max_output_bytes,
74            HARD_MAX_OUTPUT_BYTES,
75        )?;
76        Ok(Self {
77            max_rows,
78            max_columns,
79            max_cells,
80            max_output_bytes,
81        })
82    }
83
84    /// Returns the maximum row count.
85    pub const fn max_rows(self) -> u64 {
86        self.max_rows
87    }
88
89    /// Returns the maximum column count.
90    pub const fn max_columns(self) -> u64 {
91        self.max_columns
92    }
93
94    /// Returns the maximum cell count.
95    pub const fn max_cells(self) -> u64 {
96        self.max_cells
97    }
98
99    /// Returns the maximum output byte count.
100    pub const fn max_output_bytes(self) -> u64 {
101        self.max_output_bytes
102    }
103}
104
105/// Options controlling one worksheet traversal.
106#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
107pub struct TraversalOptions {
108    mode: TraversalMode,
109    limits: TraversalLimits,
110}
111
112impl TraversalOptions {
113    /// Creates options for a traversal mode using default finite limits.
114    pub const fn new(mode: TraversalMode) -> Self {
115        Self {
116            mode,
117            limits: TraversalLimits {
118                max_rows: DEFAULT_MAX_ROWS,
119                max_columns: DEFAULT_MAX_COLUMNS,
120                max_cells: DEFAULT_MAX_CELLS,
121                max_output_bytes: DEFAULT_MAX_OUTPUT_BYTES,
122            },
123        }
124    }
125
126    /// Replaces the finite traversal limits.
127    pub const fn with_limits(mut self, limits: TraversalLimits) -> Self {
128        self.limits = limits;
129        self
130    }
131
132    /// Returns the selected traversal mode.
133    pub const fn mode(self) -> TraversalMode {
134        self.mode
135    }
136
137    /// Returns the finite traversal limits.
138    pub const fn limits(self) -> TraversalLimits {
139        self.limits
140    }
141}
142
143/// A validated inclusive worksheet rectangle.
144#[derive(Debug, Clone, Copy, PartialEq, Eq)]
145pub struct CheckedRect {
146    min_row: u32,
147    max_row: u32,
148    min_col: u32,
149    max_col: u32,
150    row_count: u64,
151    column_count: u64,
152    cell_count: u64,
153}
154
155impl CheckedRect {
156    /// Validates coordinates and checked dimensions against finite limits.
157    pub fn new(
158        min_row: u32,
159        max_row: u32,
160        min_col: u32,
161        max_col: u32,
162        limits: TraversalLimits,
163    ) -> Result<Self> {
164        if min_row == 0 || max_row < min_row {
165            return Err(Error::InvalidRowNumber(min_row));
166        }
167        if min_col == 0 || max_col < min_col {
168            return Err(Error::InvalidColumnNumber(min_col));
169        }
170        check_limit(
171            ResourceDimension::RowCount,
172            HARD_MAX_ROWS,
173            u64::from(max_row),
174        )?;
175        check_limit(
176            ResourceDimension::ColumnCount,
177            HARD_MAX_COLUMNS,
178            u64::from(max_col),
179        )?;
180        let row_count = u64::from(max_row)
181            .checked_sub(u64::from(min_row))
182            .and_then(|span| span.checked_add(1))
183            .ok_or_else(|| limit_error(ResourceDimension::RowCount, limits.max_rows, None))?;
184        let column_count = u64::from(max_col)
185            .checked_sub(u64::from(min_col))
186            .and_then(|span| span.checked_add(1))
187            .ok_or_else(|| limit_error(ResourceDimension::ColumnCount, limits.max_columns, None))?;
188        check_limit(ResourceDimension::RowCount, limits.max_rows, row_count)?;
189        check_limit(
190            ResourceDimension::ColumnCount,
191            limits.max_columns,
192            column_count,
193        )?;
194        let cell_count = row_count
195            .checked_mul(column_count)
196            .ok_or_else(|| limit_error(ResourceDimension::CellCount, limits.max_cells, None))?;
197        check_limit(ResourceDimension::CellCount, limits.max_cells, cell_count)?;
198        Ok(Self {
199            min_row,
200            max_row,
201            min_col,
202            max_col,
203            row_count,
204            column_count,
205            cell_count,
206        })
207    }
208
209    /// Validates sparse bounds without charging the unvisited rectangle area.
210    pub fn new_sparse(
211        min_row: u32,
212        max_row: u32,
213        min_col: u32,
214        max_col: u32,
215        limits: TraversalLimits,
216    ) -> Result<Self> {
217        if min_row == 0 || max_row < min_row {
218            return Err(Error::InvalidRowNumber(min_row));
219        }
220        if min_col == 0 || max_col < min_col {
221            return Err(Error::InvalidColumnNumber(min_col));
222        }
223        check_limit(
224            ResourceDimension::RowCount,
225            HARD_MAX_ROWS,
226            u64::from(max_row),
227        )?;
228        check_limit(
229            ResourceDimension::ColumnCount,
230            HARD_MAX_COLUMNS,
231            u64::from(max_col),
232        )?;
233        let row_count = u64::from(max_row - min_row) + 1;
234        let column_count = u64::from(max_col - min_col) + 1;
235        check_limit(
236            ResourceDimension::ColumnCount,
237            limits.max_columns,
238            column_count,
239        )?;
240        let cell_count = row_count
241            .checked_mul(column_count)
242            .ok_or_else(|| limit_error(ResourceDimension::CellCount, limits.max_cells, None))?;
243        Ok(Self {
244            min_row,
245            max_row,
246            min_col,
247            max_col,
248            row_count,
249            column_count,
250            cell_count,
251        })
252    }
253
254    pub const fn min_row(self) -> u32 {
255        self.min_row
256    }
257
258    pub const fn max_row(self) -> u32 {
259        self.max_row
260    }
261
262    pub const fn min_col(self) -> u32 {
263        self.min_col
264    }
265
266    pub const fn max_col(self) -> u32 {
267        self.max_col
268    }
269
270    pub const fn row_count(self) -> u64 {
271        self.row_count
272    }
273
274    pub const fn column_count(self) -> u64 {
275        self.column_count
276    }
277
278    pub const fn cell_count(self) -> u64 {
279        self.cell_count
280    }
281}
282
283/// Adds byte counts without wrapping and checks the output budget.
284pub fn checked_output_add(current: u64, additional: u64, limits: TraversalLimits) -> Result<u64> {
285    let observed = current.checked_add(additional).ok_or_else(|| {
286        limit_error(
287            ResourceDimension::OutputBytes,
288            limits.max_output_bytes,
289            None,
290        )
291    })?;
292    check_limit(
293        ResourceDimension::OutputBytes,
294        limits.max_output_bytes,
295        observed,
296    )?;
297    Ok(observed)
298}
299
300/// Multiplies byte counts without wrapping and checks the output budget.
301pub fn checked_output_mul(left: u64, right: u64, limits: TraversalLimits) -> Result<u64> {
302    let observed = left.checked_mul(right).ok_or_else(|| {
303        limit_error(
304            ResourceDimension::OutputBytes,
305            limits.max_output_bytes,
306            None,
307        )
308    })?;
309    check_limit(
310        ResourceDimension::OutputBytes,
311        limits.max_output_bytes,
312        observed,
313    )?;
314    Ok(observed)
315}
316
317/// Checks a traversal count against its finite limit.
318pub fn check_limit(dimension: ResourceDimension, limit: u64, observed: u64) -> Result<()> {
319    if observed > limit {
320        return Err(limit_error(dimension, limit, Some(observed)));
321    }
322    Ok(())
323}
324
325fn validate_config(dimension: ResourceDimension, value: u64, hard_limit: u64) -> Result<()> {
326    if value == 0 {
327        return Err(limit_error(dimension, 0, Some(1)));
328    }
329    check_limit(dimension, hard_limit, value)
330}
331
332fn limit_error(dimension: ResourceDimension, limit: u64, observed: Option<u64>) -> Error {
333    let observed = observed.unwrap_or_else(|| limit.saturating_add(1));
334    match ResourceLimitError::exceeded(
335        ResourceOperation::DataTraverse,
336        ResourceCategory::Traversal,
337        dimension,
338        limit,
339        observed.max(limit.saturating_add(1)),
340        Some(ResourceStage::Serialize),
341    ) {
342        Some(metadata) => metadata.into(),
343        None => Error::Internal("invalid traversal resource limit".to_string()),
344    }
345}
346
347#[cfg(test)]
348mod tests {
349    use super::*;
350
351    fn metadata(error: Error) -> ResourceLimitError {
352        match error {
353            Error::ResourceLimitExceeded(metadata) => metadata,
354            other => panic!("expected resource limit error, got {other}"),
355        }
356    }
357
358    #[test]
359    fn defaults_are_finite_and_sparse() {
360        let options = TraversalOptions::default();
361        assert_eq!(options.mode(), TraversalMode::Sparse);
362        assert!(options.limits().max_rows() < u64::MAX);
363        assert!(options.limits().max_columns() < u64::MAX);
364        assert!(options.limits().max_cells() < u64::MAX);
365        assert!(options.limits().max_output_bytes() < u64::MAX);
366    }
367
368    #[test]
369    fn configuration_accepts_hard_ceiling_and_rejects_plus_one() {
370        TraversalLimits::new(
371            HARD_MAX_ROWS,
372            HARD_MAX_COLUMNS,
373            HARD_MAX_CELLS,
374            HARD_MAX_OUTPUT_BYTES,
375        )
376        .unwrap();
377        let error = TraversalLimits::new(
378            HARD_MAX_ROWS,
379            HARD_MAX_COLUMNS,
380            HARD_MAX_CELLS + 1,
381            HARD_MAX_OUTPUT_BYTES,
382        )
383        .unwrap_err();
384        let metadata = metadata(error);
385        assert_eq!(metadata.dimension(), ResourceDimension::CellCount);
386        assert_eq!(metadata.limit(), HARD_MAX_CELLS);
387        assert_eq!(metadata.observed(), HARD_MAX_CELLS + 1);
388    }
389
390    #[test]
391    fn checked_rectangle_accepts_exact_limit_and_rejects_plus_one() {
392        let limits = TraversalLimits::new(2, 3, 6, 1024).unwrap();
393        let rect = CheckedRect::new(1, 2, 1, 3, limits).unwrap();
394        assert_eq!(rect.row_count(), 2);
395        assert_eq!(rect.column_count(), 3);
396        assert_eq!(rect.cell_count(), 6);
397
398        let error = CheckedRect::new(1, 3, 1, 3, limits).unwrap_err();
399        assert_eq!(metadata(error).dimension(), ResourceDimension::RowCount);
400    }
401
402    #[test]
403    fn checked_rectangle_reports_each_dimension_boundary() {
404        let limits = TraversalLimits::new(2, 3, 6, 1024).unwrap();
405        let row_error = CheckedRect::new(1, 3, 1, 1, limits).unwrap_err();
406        assert_eq!(metadata(row_error).dimension(), ResourceDimension::RowCount);
407
408        let column_error = CheckedRect::new(1, 1, 1, 4, limits).unwrap_err();
409        assert_eq!(
410            metadata(column_error).dimension(),
411            ResourceDimension::ColumnCount
412        );
413
414        let cell_limits = TraversalLimits::new(1, 7, 6, 1024).unwrap();
415        let cell_error = CheckedRect::new(1, 1, 1, 7, cell_limits).unwrap_err();
416        let cell_metadata = metadata(cell_error);
417        assert_eq!(cell_metadata.dimension(), ResourceDimension::CellCount);
418        assert_eq!(cell_metadata.limit(), 6);
419        assert_eq!(cell_metadata.observed(), 7);
420    }
421
422    #[test]
423    fn checked_output_arithmetic_reports_overflow_as_bounded_error() {
424        let limits = TraversalLimits::default();
425        let error = checked_output_add(u64::MAX, 1, limits).unwrap_err();
426        let error_metadata = metadata(error);
427        assert_eq!(error_metadata.dimension(), ResourceDimension::OutputBytes);
428        assert_eq!(error_metadata.limit(), limits.max_output_bytes());
429        assert_eq!(error_metadata.observed(), limits.max_output_bytes() + 1);
430
431        let error = checked_output_mul(u64::MAX, 2, limits).unwrap_err();
432        assert_eq!(metadata(error).dimension(), ResourceDimension::OutputBytes);
433    }
434
435    #[test]
436    fn rectangles_reject_coordinates_outside_the_hard_grid() {
437        let limits = TraversalLimits::default();
438        let row_error = CheckedRect::new(
439            HARD_MAX_ROWS as u32 + 1,
440            HARD_MAX_ROWS as u32 + 1,
441            1,
442            1,
443            limits,
444        )
445        .unwrap_err();
446        let row_metadata = metadata(row_error);
447        assert_eq!(row_metadata.dimension(), ResourceDimension::RowCount);
448        assert_eq!(row_metadata.limit(), HARD_MAX_ROWS);
449
450        let column_error = CheckedRect::new_sparse(
451            1,
452            1,
453            HARD_MAX_COLUMNS as u32 + 1,
454            HARD_MAX_COLUMNS as u32 + 1,
455            limits,
456        )
457        .unwrap_err();
458        let column_metadata = metadata(column_error);
459        assert_eq!(column_metadata.dimension(), ResourceDimension::ColumnCount);
460        assert_eq!(column_metadata.limit(), HARD_MAX_COLUMNS);
461    }
462}