1use serde::{Deserialize, Serialize};
11
12use crate::utils::require;
13use crate::{DeltaResult, Error};
14
15const KB: i64 = 1024;
16const MB: i64 = KB * 1024;
17const GB: i64 = MB * 1024;
18
19#[rustfmt::skip]
32const DEFAULT_BIN_BOUNDARIES: [i64; 95] = [
33 0,
34 8 * KB, 16 * KB, 32 * KB, 64 * KB, 128 * KB, 256 * KB, 512 * KB,
36 MB, 2 * MB, 4 * MB,
37 8 * MB, 12 * MB, 16 * MB, 20 * MB, 24 * MB, 28 * MB, 32 * MB, 36 * MB, 40 * MB,
39 48 * MB, 56 * MB, 64 * MB, 72 * MB, 80 * MB, 88 * MB, 96 * MB, 104 * MB, 112 * MB, 120 * MB,
41 124 * MB, 128 * MB, 132 * MB, 136 * MB, 140 * MB, 144 * MB,
43 160 * MB, 176 * MB, 192 * MB, 208 * MB, 224 * MB, 240 * MB, 256 * MB, 272 * MB,
45 288 * MB, 304 * MB, 320 * MB, 336 * MB, 352 * MB, 368 * MB, 384 * MB, 400 * MB,
46 416 * MB, 432 * MB, 448 * MB, 464 * MB, 480 * MB, 496 * MB, 512 * MB, 528 * MB,
47 544 * MB, 560 * MB, 576 * MB,
48 640 * MB, 704 * MB, 768 * MB, 832 * MB, 896 * MB, 960 * MB, 1024 * MB, 1088 * MB,
50 1152 * MB, 1216 * MB, 1280 * MB, 1344 * MB, 1408 * MB,
51 1536 * MB, 1664 * MB, 1792 * MB, 1920 * MB, 2048 * MB,
53 2304 * MB, 2560 * MB, 2816 * MB, 3072 * MB, 3328 * MB, 3584 * MB, 3840 * MB, 4096 * MB,
55 8 * GB, 16 * GB, 32 * GB, 64 * GB, 128 * GB, 256 * GB,
57];
58
59#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
69#[serde(rename_all = "camelCase")]
70pub struct FileSizeHistogram {
71 pub(crate) sorted_bin_boundaries: Vec<i64>,
75 pub(crate) file_counts: Vec<i64>,
77 pub(crate) total_bytes: Vec<i64>,
79}
80
81impl FileSizeHistogram {
82 pub fn sorted_bin_boundaries(&self) -> &[i64] {
88 &self.sorted_bin_boundaries
89 }
90
91 pub fn file_counts(&self) -> &[i64] {
96 &self.file_counts
97 }
98
99 pub fn total_bytes(&self) -> &[i64] {
104 &self.total_bytes
105 }
106
107 pub(crate) fn try_new(
114 sorted_bin_boundaries: Vec<i64>,
115 file_counts: Vec<i64>,
116 total_bytes: Vec<i64>,
117 ) -> DeltaResult<Self> {
118 require!(
119 sorted_bin_boundaries.len() >= 2,
120 Error::internal_error(format!(
121 "sorted_bin_boundaries must have at least 2 elements, got {}",
122 sorted_bin_boundaries.len()
123 ))
124 );
125 require!(
126 sorted_bin_boundaries[0] == 0,
127 Error::internal_error(format!(
128 "First boundary must be 0, got {}",
129 sorted_bin_boundaries[0]
130 ))
131 );
132 require!(
133 sorted_bin_boundaries.len() == file_counts.len()
134 && sorted_bin_boundaries.len() == total_bytes.len(),
135 Error::internal_error(format!(
136 "All arrays must have the same length: boundaries={}, file_counts={}, total_bytes={}",
137 sorted_bin_boundaries.len(),
138 file_counts.len(),
139 total_bytes.len()
140 ))
141 );
142 require!(
143 sorted_bin_boundaries.windows(2).all(|w| w[0] < w[1]),
144 Error::internal_error(
145 "sorted_bin_boundaries must be sorted in strictly ascending order"
146 )
147 );
148 Ok(Self {
149 sorted_bin_boundaries,
150 file_counts,
151 total_bytes,
152 })
153 }
154
155 pub(crate) fn create_empty_with_boundaries(
160 sorted_bin_boundaries: Vec<i64>,
161 ) -> DeltaResult<Self> {
162 let len = sorted_bin_boundaries.len();
163 Self::try_new(sorted_bin_boundaries, vec![0; len], vec![0; len])
164 }
165
166 pub(crate) fn create_default() -> Self {
170 let len = DEFAULT_BIN_BOUNDARIES.len();
171 Self {
172 sorted_bin_boundaries: DEFAULT_BIN_BOUNDARIES.to_vec(),
173 file_counts: vec![0; len],
174 total_bytes: vec![0; len],
175 }
176 }
177
178 fn get_bin_index(&self, file_size: i64) -> usize {
183 debug_assert!(file_size >= 0);
184 match self.sorted_bin_boundaries.binary_search(&file_size) {
185 Ok(idx) => idx,
186 Err(insertion_point) => insertion_point - 1,
190 }
191 }
192
193 pub(crate) fn insert(&mut self, file_size: i64) -> DeltaResult<()> {
196 require!(
197 file_size >= 0,
198 Error::internal_error(format!("File size must be non-negative, got {}", file_size))
199 );
200 let idx = self.get_bin_index(file_size);
201 self.file_counts[idx] += 1;
202 self.total_bytes[idx] += file_size;
203 Ok(())
204 }
205
206 pub(crate) fn remove(&mut self, file_size: i64) -> DeltaResult<()> {
212 require!(
213 file_size >= 0,
214 Error::internal_error(format!("File size must be non-negative, got {}", file_size))
215 );
216 let idx = self.get_bin_index(file_size);
217 self.file_counts[idx] -= 1;
218 self.total_bytes[idx] -= file_size;
219 Ok(())
220 }
221
222 pub(crate) fn try_apply_delta(
229 &self,
230 delta: &FileSizeHistogram,
231 ) -> DeltaResult<FileSizeHistogram> {
232 require!(
233 self.sorted_bin_boundaries == delta.sorted_bin_boundaries,
234 Error::internal_error("Cannot add histograms with different bin boundaries")
235 );
236 let len = self.sorted_bin_boundaries.len();
237 let mut file_counts = Vec::with_capacity(len);
238 let mut total_bytes = Vec::with_capacity(len);
239 for i in 0..len {
240 let count = self.file_counts[i] + delta.file_counts[i];
241 let bytes = self.total_bytes[i] + delta.total_bytes[i];
242 require!(
243 count >= 0 && bytes >= 0,
244 Error::internal_error(format!(
245 "Merge would result in negative counts or bytes at bin {}",
246 i
247 ))
248 );
249 file_counts.push(count);
250 total_bytes.push(bytes);
251 }
252 Ok(FileSizeHistogram {
253 sorted_bin_boundaries: self.sorted_bin_boundaries.clone(),
254 file_counts,
255 total_bytes,
256 })
257 }
258
259 pub(crate) fn check_non_negative(self) -> DeltaResult<Self> {
265 for i in 0..self.sorted_bin_boundaries.len() {
266 require!(
267 self.file_counts[i] >= 0 && self.total_bytes[i] >= 0,
268 Error::internal_error(format!(
269 "Histogram has negative counts or bytes at bin {}",
270 i
271 ))
272 );
273 }
274 Ok(self)
275 }
276}
277
278#[cfg(test)]
279mod tests {
280 use rstest::rstest;
281 use test_utils::assert_result_error_with_message;
282
283 use super::*;
284
285 #[test]
288 fn create_default_has_95_bins_starting_at_zero() {
289 let hist = FileSizeHistogram::create_default();
290 assert_eq!(hist.sorted_bin_boundaries.len(), 95);
291 assert_eq!(hist.file_counts.len(), 95);
292 assert_eq!(hist.total_bytes.len(), 95);
293 assert_eq!(hist.sorted_bin_boundaries[0], 0);
294 assert!(hist.file_counts.iter().all(|&c| c == 0));
295 assert!(hist.total_bytes.iter().all(|&b| b == 0));
296 }
297
298 #[test]
299 fn create_empty_with_boundaries_produces_zeroed_histogram() {
300 let hist = FileSizeHistogram::create_empty_with_boundaries(vec![0, 100, 1000]).unwrap();
301 assert_eq!(hist.sorted_bin_boundaries, vec![0, 100, 1000]);
302 assert_eq!(hist.file_counts, vec![0, 0, 0]);
303 assert_eq!(hist.total_bytes, vec![0, 0, 0]);
304 }
305
306 #[test]
307 fn try_new_valid_histogram() {
308 let hist = FileSizeHistogram::try_new(vec![0, 100], vec![5, 3], vec![200, 900]).unwrap();
309 assert_eq!(hist.sorted_bin_boundaries, vec![0, 100]);
310 assert_eq!(hist.file_counts, vec![5, 3]);
311 assert_eq!(hist.total_bytes, vec![200, 900]);
312 }
313
314 #[rstest]
315 #[case::empty_boundaries(vec![], vec![], vec![], "at least 2 elements")]
316 #[case::single_boundary(vec![0], vec![0], vec![0], "at least 2 elements")]
317 #[case::nonzero_first_boundary(vec![1, 100], vec![0, 0], vec![0, 0], "First boundary must be 0")]
318 #[case::mismatched_array_lengths(vec![0, 100], vec![0], vec![0, 0], "same length")]
319 #[case::unsorted_boundaries(vec![0, 200, 100], vec![0, 0, 0], vec![0, 0, 0], "strictly ascending")]
320 #[case::duplicate_boundaries(vec![0, 100, 100], vec![0, 0, 0], vec![0, 0, 0], "strictly ascending")]
321 fn try_new_rejects_invalid_inputs(
322 #[case] boundaries: Vec<i64>,
323 #[case] file_counts: Vec<i64>,
324 #[case] total_bytes: Vec<i64>,
325 #[case] expected_msg: &str,
326 ) {
327 assert_result_error_with_message(
328 FileSizeHistogram::try_new(boundaries, file_counts, total_bytes),
329 expected_msg,
330 );
331 }
332
333 #[test]
336 fn get_bin_index_exact_boundary_match() {
337 let hist = FileSizeHistogram::try_new(vec![0, 100, 200], vec![0; 3], vec![0; 3]).unwrap();
338 assert_eq!(hist.get_bin_index(0), 0);
339 assert_eq!(hist.get_bin_index(100), 1);
340 assert_eq!(hist.get_bin_index(200), 2);
341 }
342
343 #[test]
344 fn get_bin_index_between_boundaries() {
345 let hist = FileSizeHistogram::try_new(vec![0, 100, 200], vec![0; 3], vec![0; 3]).unwrap();
346 assert_eq!(hist.get_bin_index(50), 0);
347 assert_eq!(hist.get_bin_index(99), 0);
348 assert_eq!(hist.get_bin_index(150), 1);
349 assert_eq!(hist.get_bin_index(199), 1);
350 }
351
352 #[test]
353 fn get_bin_index_beyond_max_boundary_returns_last_bin() {
354 let hist = FileSizeHistogram::try_new(vec![0, 100, 200], vec![0; 3], vec![0; 3]).unwrap();
355 assert_eq!(hist.get_bin_index(999), 2);
356 assert_eq!(hist.get_bin_index(i64::MAX), 2);
357 }
358
359 #[test]
362 fn insert_increments_count_and_bytes() {
363 let mut hist =
364 FileSizeHistogram::try_new(vec![0, 100, 200], vec![0; 3], vec![0; 3]).unwrap();
365 hist.insert(50).unwrap();
366 hist.insert(75).unwrap();
367 hist.insert(150).unwrap();
368 assert_eq!(hist.file_counts, vec![2, 1, 0]);
369 assert_eq!(hist.total_bytes, vec![125, 150, 0]);
370 }
371
372 #[test]
373 fn insert_negative_size_returns_error() {
374 let mut hist = FileSizeHistogram::create_default();
375 assert_result_error_with_message(hist.insert(-1), "non-negative");
376 }
377
378 #[test]
379 fn remove_decrements_count_and_bytes() {
380 let mut hist =
381 FileSizeHistogram::try_new(vec![0, 100, 200], vec![2, 1, 0], vec![125, 150, 0])
382 .unwrap();
383 hist.remove(50).unwrap();
384 assert_eq!(hist.file_counts, vec![1, 1, 0]);
385 assert_eq!(hist.total_bytes, vec![75, 150, 0]);
386 }
387
388 #[test]
389 fn remove_allows_negative_bin_values() {
390 let mut hist = FileSizeHistogram::try_new(vec![0, 100], vec![0, 0], vec![0, 0]).unwrap();
391 hist.remove(50).unwrap();
392 assert_eq!(hist.file_counts, vec![-1, 0]);
393 assert_eq!(hist.total_bytes, vec![-50, 0]);
394 }
395
396 #[test]
397 fn remove_negative_size_returns_error() {
398 let mut hist = FileSizeHistogram::create_default();
399 assert_result_error_with_message(hist.remove(-1), "non-negative");
400 }
401
402 #[test]
405 fn try_apply_delta_combines_counts_and_bytes() {
406 let base = FileSizeHistogram::try_new(vec![0, 100], vec![2, 3], vec![50, 400]).unwrap();
407 let delta = FileSizeHistogram::try_new(vec![0, 100], vec![1, 4], vec![30, 600]).unwrap();
408 let result = base.try_apply_delta(&delta).unwrap();
409 assert_eq!(result.file_counts, vec![3, 7]);
410 assert_eq!(result.total_bytes, vec![80, 1000]);
411 assert_eq!(result.sorted_bin_boundaries, vec![0, 100]);
412 }
413
414 #[test]
415 fn try_apply_delta_with_negative_delta_succeeds() {
416 let base = FileSizeHistogram::try_new(vec![0, 100], vec![5, 8], vec![200, 900]).unwrap();
417 let delta =
418 FileSizeHistogram::try_new(vec![0, 100], vec![-2, -3], vec![-50, -400]).unwrap();
419 let result = base.try_apply_delta(&delta).unwrap();
420 assert_eq!(result.file_counts, vec![3, 5]);
421 assert_eq!(result.total_bytes, vec![150, 500]);
422 }
423
424 #[test]
425 fn try_apply_delta_mismatched_boundaries_returns_error() {
426 let a = FileSizeHistogram::try_new(vec![0, 100], vec![0; 2], vec![0; 2]).unwrap();
427 let b = FileSizeHistogram::try_new(vec![0, 200], vec![0; 2], vec![0; 2]).unwrap();
428 assert_result_error_with_message(a.try_apply_delta(&b), "different bin boundaries");
429 }
430
431 #[test]
432 fn try_apply_delta_rejects_negative_result_counts() {
433 let base = FileSizeHistogram::try_new(vec![0, 100], vec![1, 0], vec![50, 0]).unwrap();
434 let delta = FileSizeHistogram::try_new(vec![0, 100], vec![-2, 0], vec![-50, 0]).unwrap();
435 assert_result_error_with_message(base.try_apply_delta(&delta), "negative counts or bytes");
436 }
437
438 #[test]
439 fn try_apply_delta_rejects_negative_result_bytes() {
440 let base = FileSizeHistogram::try_new(vec![0, 100], vec![2, 0], vec![50, 0]).unwrap();
441 let delta = FileSizeHistogram::try_new(vec![0, 100], vec![-1, 0], vec![-100, 0]).unwrap();
442 assert_result_error_with_message(base.try_apply_delta(&delta), "negative counts or bytes");
443 }
444
445 #[test]
448 fn serde_round_trip_default_histogram() {
449 let hist = FileSizeHistogram::create_default();
450 let json = serde_json::to_string(&hist).unwrap();
451 let deserialized: FileSizeHistogram = serde_json::from_str(&json).unwrap();
452 assert_eq!(hist, deserialized);
453 }
454
455 #[test]
456 fn serde_round_trip_populated_histogram() {
457 let mut hist = FileSizeHistogram::create_default();
458 hist.insert(500).unwrap();
459 hist.insert(10_000_000).unwrap();
460 let json = serde_json::to_string(&hist).unwrap();
461 let deserialized: FileSizeHistogram = serde_json::from_str(&json).unwrap();
462 assert_eq!(hist, deserialized);
463 }
464
465 #[test]
466 fn serde_uses_camel_case_field_names() {
467 let hist = FileSizeHistogram::try_new(vec![0, 100], vec![1, 2], vec![10, 200]).unwrap();
468 let json_value = serde_json::to_value(&hist).unwrap();
469 assert!(json_value.get("sortedBinBoundaries").is_some());
470 assert!(json_value.get("fileCounts").is_some());
471 assert!(json_value.get("totalBytes").is_some());
472 assert!(json_value.get("sorted_bin_boundaries").is_none());
474 assert!(json_value.get("file_counts").is_none());
475 assert!(json_value.get("total_bytes").is_none());
476 }
477
478 #[test]
479 fn serde_deserialize_from_crc_json_format() {
480 let json = r#"{
481 "sortedBinBoundaries": [0, 8192, 16384],
482 "fileCounts": [10, 0, 0],
483 "totalBytes": [5259, 0, 0]
484 }"#;
485 let hist: FileSizeHistogram = serde_json::from_str(json).unwrap();
486 assert_eq!(hist.sorted_bin_boundaries, vec![0, 8192, 16384]);
487 assert_eq!(hist.file_counts, vec![10, 0, 0]);
488 assert_eq!(hist.total_bytes, vec![5259, 0, 0]);
489 }
490}