1use crate::error::{Error, Result};
4use crate::resource::{
5 ResourceCategory, ResourceDimension, ResourceLimitError, ResourceOperation, ResourceStage,
6};
7
8pub const DEFAULT_MAX_ROWS: u64 = 1_048_576;
10pub const DEFAULT_MAX_COLUMNS: u64 = 16_384;
12pub const DEFAULT_MAX_CELLS: u64 = 10_000_000;
14pub const DEFAULT_MAX_OUTPUT_BYTES: u64 = 512 * 1024 * 1024;
16
17pub const HARD_MAX_ROWS: u64 = 1_048_576;
19pub const HARD_MAX_COLUMNS: u64 = 16_384;
21pub const HARD_MAX_CELLS: u64 = 100_000_000;
23pub const HARD_MAX_OUTPUT_BYTES: u64 = 2 * 1024 * 1024 * 1024;
25
26#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
28pub enum TraversalMode {
29 #[default]
31 Sparse,
32 Dense,
34}
35
36#[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 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 pub const fn max_rows(self) -> u64 {
86 self.max_rows
87 }
88
89 pub const fn max_columns(self) -> u64 {
91 self.max_columns
92 }
93
94 pub const fn max_cells(self) -> u64 {
96 self.max_cells
97 }
98
99 pub const fn max_output_bytes(self) -> u64 {
101 self.max_output_bytes
102 }
103}
104
105#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
107pub struct TraversalOptions {
108 mode: TraversalMode,
109 limits: TraversalLimits,
110}
111
112impl TraversalOptions {
113 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 pub const fn with_limits(mut self, limits: TraversalLimits) -> Self {
128 self.limits = limits;
129 self
130 }
131
132 pub const fn mode(self) -> TraversalMode {
134 self.mode
135 }
136
137 pub const fn limits(self) -> TraversalLimits {
139 self.limits
140 }
141}
142
143#[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 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 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
283pub 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
300pub 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
317pub 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}