1use crate::errors::ParquetError;
6use crate::file::reader::{ChunkReader, Length};
7use bytes::Bytes;
8use std::cmp::Ordering;
9use std::collections::VecDeque;
10use std::fmt::Display;
11use std::ops::Range;
12
13#[derive(Debug, Clone, Default)]
39pub struct PushBuffers {
40 offset: u64,
42 file_len: u64,
44 ranges: VecDeque<Range<u64>>,
50 buffers: VecDeque<Bytes>,
53 max_len: MaxLen,
61 buffered_bytes: u64,
64}
65
66impl Display for PushBuffers {
67 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
68 writeln!(
69 f,
70 "Buffers (offset: {}, file_len: {})",
71 self.offset, self.file_len
72 )?;
73 writeln!(f, "Available Ranges (w/ offset):")?;
74 for range in &self.ranges {
75 writeln!(
76 f,
77 " {}..{} ({}..{}): {} bytes",
78 range.start,
79 range.end,
80 range.start + self.offset,
81 range.end + self.offset,
82 range.end - range.start
83 )?;
84 }
85
86 Ok(())
87 }
88}
89
90impl PushBuffers {
91 pub fn new(file_len: u64) -> Self {
97 Self {
98 offset: 0,
99 file_len,
100 ranges: VecDeque::new(),
101 buffers: VecDeque::new(),
102 max_len: MaxLen::default(),
103 buffered_bytes: 0,
104 }
105 }
106
107 pub fn push_ranges(
114 &mut self,
115 ranges: Vec<Range<u64>>,
116 buffers: Vec<Bytes>,
117 ) -> Result<(), ParquetError> {
118 if ranges.len() != buffers.len() {
119 return Err(general_err!(
120 "Number of ranges ({}) must match number of buffers ({})",
121 ranges.len(),
122 buffers.len()
123 ));
124 }
125 for (range, buffer) in ranges.into_iter().zip(buffers) {
126 self.push_range(range, buffer)?;
127 }
128 Ok(())
129 }
130
131 pub fn push_range(&mut self, range: Range<u64>, buffer: Bytes) -> Result<(), ParquetError> {
140 let expected = range.end.saturating_sub(range.start);
141 if expected != buffer.len() as u64 {
142 return Err(general_err!(
143 "Buffer length ({}) does not match length ({}) of range {}..{}",
144 buffer.len(),
145 expected,
146 range.start,
147 range.end
148 ));
149 }
150 if expected == 0 {
151 return Ok(());
152 }
153 let idx = self.ranges.partition_point(|r| r.start <= range.start);
156 self.max_len.add(expected);
157 self.buffered_bytes += expected;
158 self.ranges.insert(idx, range);
159 self.buffers.insert(idx, buffer);
160 Ok(())
161 }
162
163 pub(crate) fn has_range(&self, range: &Range<u64>) -> bool {
167 range.is_empty() || self.find(range.start, range.end).is_some()
168 }
169
170 fn find(&self, start: u64, end: u64) -> Option<usize> {
173 let candidates = self.ranges.partition_point(|r| r.start <= start);
200 self.ranges
201 .range(..candidates)
202 .enumerate()
203 .rev()
204 .take_while(|(_, r)| r.start.saturating_add(self.max_len.get()) >= end)
205 .find(|(_, r)| r.end >= end)
206 .map(|(idx, _)| idx)
207 }
208
209 pub(crate) fn file_len(&self) -> u64 {
211 self.file_len
212 }
213
214 fn with_offset(mut self, offset: u64) -> Self {
216 self.offset = offset;
217 self
218 }
219
220 #[cfg(feature = "arrow")]
227 pub(crate) fn buffered_bytes(&self) -> u64 {
228 self.buffered_bytes
229 }
230
231 #[cfg(feature = "arrow")]
236 pub(crate) fn clear_ranges(&mut self, ranges_to_clear: &[Range<u64>]) {
237 let mut remove = vec![];
240 for clear in ranges_to_clear {
241 let first = self.ranges.partition_point(|r| r.start < clear.start);
242 let same_start = self
243 .ranges
244 .range(first..)
245 .take_while(|r| r.start == clear.start);
246 remove.extend(
247 same_start
248 .enumerate()
249 .filter(|(_, r)| r.end == clear.end)
250 .map(|(idx, _)| first + idx),
251 );
252 }
253 remove.sort_unstable();
256 remove.dedup();
257 let (Some(&first), Some(&last)) = (remove.first(), remove.last()) else {
258 return;
259 };
260 let mut kept = first;
264 let mut remove = remove.into_iter().peekable();
265 for idx in first..=last {
266 if remove.next_if_eq(&idx).is_some() {
267 let len = self.ranges[idx].end.saturating_sub(self.ranges[idx].start);
268 self.buffered_bytes -= len;
269 self.max_len.remove(len);
270 } else {
271 self.ranges.swap(kept, idx);
272 self.buffers.swap(kept, idx);
273 kept += 1;
274 }
275 }
276 self.ranges.drain(kept..=last);
277 self.buffers.drain(kept..=last);
278 self.max_len
280 .rescan_if_stale(self.ranges.iter().map(|r| r.end.saturating_sub(r.start)));
281 }
282
283 #[cfg(feature = "arrow")]
298 pub(crate) fn release_ranges(&mut self, ranges: &[Range<u64>]) {
299 let release = merge_ranges(ranges);
300 if release.is_empty() {
301 return;
302 }
303 let overlaps = |range: &Range<u64>| {
304 !range.is_empty() && {
305 let first = release.partition_point(|r| r.end <= range.start);
306 release.get(first).is_some_and(|r| r.start < range.end)
307 }
308 };
309 let mut overlapping = vec![];
320 let mut visited = 0;
321 for r in &release {
322 let max_len = self.max_len.get();
323 let first = self
324 .ranges
325 .partition_point(|b| b.start.saturating_add(max_len) <= r.start);
326 let end = self.ranges.partition_point(|b| b.start < r.end);
327 overlapping
330 .extend((first.max(visited)..end).filter(|&idx| overlaps(&self.ranges[idx])));
331 visited = visited.max(end);
332 }
333 let (Some(&first), Some(&last)) = (overlapping.first(), overlapping.last()) else {
336 return;
337 };
338 let mut split = vec![];
343 let mut emptied = false;
344 for idx in overlapping {
345 let (range, buffer) = (&mut self.ranges[idx], &mut self.buffers[idx]);
346 let whole = range.clone();
347 self.max_len.remove(whole.end - whole.start);
349 let offset = |pos: u64| (pos - whole.start) as usize;
350 let first = release.partition_point(|r| r.end <= whole.start);
352 let mut kept = 0;
353 let mut first_part = None;
354 let mut keep = |part: Range<u64>| {
355 kept += part.end - part.start;
356 if first_part.is_none() {
357 first_part = Some(part);
358 } else {
359 let data = buffer.slice(offset(part.start)..offset(part.end));
360 split.push((part, data));
361 }
362 };
363 let mut start = whole.start;
364 for r in release[first..].iter().take_while(|r| r.start < whole.end) {
365 if start < r.start {
366 keep(start..r.start);
367 }
368 start = r.end;
369 }
370 if start < whole.end {
371 keep(start..whole.end);
372 }
373 self.buffered_bytes -= (whole.end - whole.start) - kept;
374 match first_part {
375 Some(part) => {
376 buffer.truncate(offset(part.end));
377 let _ = buffer.split_to(offset(part.start));
378 *range = part;
379 }
380 None => {
381 *buffer = Bytes::new();
382 *range = whole.start..whole.start;
383 emptied = true;
384 }
385 }
386 }
387 if emptied {
388 let span = first..last + 1;
390 let mut kept = span.start;
391 for idx in span.clone() {
392 if !self.ranges[idx].is_empty() {
393 self.ranges.swap(kept, idx);
394 self.buffers.swap(kept, idx);
395 kept += 1;
396 }
397 }
398 self.ranges.drain(kept..span.end);
399 self.buffers.drain(kept..span.end);
400 }
401 if !split.is_empty() {
407 let mut parts: Vec<_> = std::mem::take(&mut self.ranges)
408 .into_iter()
409 .zip(std::mem::take(&mut self.buffers))
410 .chain(split)
411 .collect();
412 parts.sort_by_key(|(range, _)| range.start);
413 (self.ranges, self.buffers) = parts.into_iter().unzip();
414 }
415 self.max_len
419 .rescan_if_stale(self.ranges.iter().map(|r| r.end.saturating_sub(r.start)));
420 }
421
422 #[cfg(feature = "arrow")]
427 pub(crate) fn retain_ranges(&mut self, keep: &[Range<u64>]) {
428 let mut release = vec![];
429 let mut start = 0;
430 for range in merge_ranges(keep) {
431 release.push(start..range.start);
432 start = range.end;
433 }
434 release.push(start..u64::MAX);
435 self.release_ranges(&release);
436 }
437
438 pub(crate) fn clear_all_ranges(&mut self) {
440 self.ranges.clear();
441 self.buffers.clear();
442 self.max_len = MaxLen::default();
443 self.buffered_bytes = 0;
444 }
445
446 #[cfg(test)]
449 #[track_caller]
450 fn assert_invariants(&self) {
451 assert_eq!(self.ranges.len(), self.buffers.len());
452 assert!(
453 self.ranges.iter().is_sorted_by_key(|r| r.start),
454 "not sorted: {:?}",
455 self.ranges
456 );
457 for (range, buffer) in self.ranges.iter().zip(&self.buffers) {
458 assert_eq!(range.end.saturating_sub(range.start), buffer.len() as u64);
459 }
460 let max_len = self
461 .ranges
462 .iter()
463 .map(|r| r.end.saturating_sub(r.start))
464 .max();
465 let max_len = max_len.unwrap_or(0);
466 assert_eq!(self.max_len.len, max_len);
467 let is_longest = |r: &&Range<u64>| r.end.saturating_sub(r.start) == max_len;
468 assert_eq!(
469 self.max_len.count,
470 self.ranges.iter().filter(is_longest).count()
471 );
472 assert!(
473 self.ranges.iter().all(|r| !r.is_empty()),
474 "empty buffer: {:?}",
475 self.ranges
476 );
477 }
478}
479
480#[cfg(feature = "arrow")]
483fn merge_ranges(ranges: &[Range<u64>]) -> Vec<Range<u64>> {
484 let mut sorted: Vec<Range<u64>> = ranges.iter().filter(|r| !r.is_empty()).cloned().collect();
485 sorted.sort_unstable_by_key(|r| r.start);
486 let mut merged: Vec<Range<u64>> = Vec::with_capacity(sorted.len());
487 for range in sorted {
488 match merged.last_mut() {
489 Some(last) if range.start <= last.end => last.end = last.end.max(range.end),
490 _ => merged.push(range),
491 }
492 }
493 merged
494}
495
496impl Length for PushBuffers {
497 fn len(&self) -> u64 {
498 self.file_len
499 }
500}
501
502impl std::io::Read for PushBuffers {
504 fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
505 if buf.is_empty() {
506 return Ok(0);
507 }
508 let found = self.find(self.offset, self.offset + buf.len() as u64);
510 if let Some(idx) = found {
511 let start_offset = (self.offset - self.ranges[idx].start) as usize;
513 let end_offset = start_offset + buf.len();
514 buf.copy_from_slice(&self.buffers[idx][start_offset..end_offset]);
515 self.offset += buf.len() as u64;
518 Ok(buf.len())
519 } else {
520 Err(std::io::Error::new(
521 std::io::ErrorKind::UnexpectedEof,
522 "No data available in Buffers",
523 ))
524 }
525 }
526}
527
528impl ChunkReader for PushBuffers {
529 type T = Self;
530
531 fn get_read(&self, start: u64) -> Result<Self::T, ParquetError> {
532 Ok(self.clone().with_offset(self.offset + start))
533 }
534
535 fn get_bytes(&self, start: u64, length: usize) -> Result<Bytes, ParquetError> {
536 if length == 0 {
538 return Ok(Bytes::new());
539 }
540 if let Some(idx) = self.find(start, start + length as u64) {
542 let start_offset = (start - self.ranges[idx].start) as usize;
544 return Ok(self.buffers[idx].slice(start_offset..start_offset + length));
545 }
546 let requested_end = start + length as u64;
548 Err(ParquetError::NeedMoreDataRange(start..requested_end))
549 }
550}
551
552#[derive(Debug, Default, Clone, Copy)]
559struct MaxLen {
560 len: u64,
561 count: usize,
562}
563
564impl MaxLen {
565 #[inline]
569 fn get(&self) -> u64 {
570 self.len
571 }
572
573 #[inline]
575 fn add(&mut self, len: u64) {
576 match len.cmp(&self.len) {
577 Ordering::Greater => (self.len, self.count) = (len, 1),
578 Ordering::Equal => self.count += 1,
579 Ordering::Less => {}
580 }
581 }
582
583 #[cfg(feature = "arrow")]
586 #[inline]
587 fn remove(&mut self, len: u64) {
588 if len == self.len {
589 self.count -= 1;
590 }
591 }
592
593 #[cfg(feature = "arrow")]
600 #[inline]
601 fn rescan_if_stale(&mut self, lens: impl IntoIterator<Item = u64>) {
602 if self.count == 0 {
603 *self = Self::default();
604 lens.into_iter().for_each(|len| self.add(len));
605 }
606 }
607}
608
609#[cfg(test)]
610mod tests {
611 use super::*;
612
613 #[cfg(feature = "arrow")]
615 fn release(buffers: &mut PushBuffers, range: Range<u64>) {
616 buffers.release_ranges(std::slice::from_ref(&range));
617 buffers.assert_invariants();
618 }
619
620 #[cfg(feature = "arrow")]
622 fn buffered_parts(buffers: &PushBuffers) -> Vec<(Range<u64>, Bytes)> {
623 let ranges = buffers.ranges.iter().cloned();
624 ranges.zip(buffers.buffers.iter().cloned()).collect()
625 }
626
627 #[test]
628 #[cfg(feature = "arrow")]
629 fn release_ranges_without_overlap_keeps_buffers() {
630 let mut buffers = PushBuffers::new(100);
631 buffers
632 .push_range(20..24, Bytes::from_static(b"abcd"))
633 .unwrap();
634 buffers
635 .push_range(0..10, Bytes::from_static(b"0123456789"))
636 .unwrap();
637
638 release(&mut buffers, 90..95);
639 release(&mut buffers, 10..20);
640 assert_eq!(buffers.ranges, vec![0..10, 20..24]);
641 assert_eq!(buffers.buffered_bytes(), 14);
642
643 release(&mut buffers, 22..24);
644 assert_eq!(buffers.ranges, vec![0..10, 20..22]);
645 assert_eq!(buffers.buffered_bytes(), 12);
646
647 buffers.clear_all_ranges();
648 assert_eq!(buffers.buffered_bytes(), 0);
649 }
650
651 #[test]
652 #[cfg(feature = "arrow")]
653 fn release_ranges_trims_and_splits_buffers() {
654 let mut buffers = PushBuffers::new(100);
655 buffers
656 .push_range(0..10, Bytes::from_static(b"0123456789"))
657 .unwrap();
658 buffers
659 .push_range(20..24, Bytes::from_static(b"abcd"))
660 .unwrap();
661
662 release(&mut buffers, 3..5);
664 assert_eq!(buffers.buffered_bytes(), 12);
665 assert!(buffers.has_range(&(0..3)));
666 assert!(buffers.has_range(&(5..10)));
667 assert!(!buffers.has_range(&(3..4)));
668 assert_eq!(
669 buffers.get_bytes(5, 5).unwrap(),
670 Bytes::from_static(b"56789")
671 );
672 assert!(buffers.has_range(&(20..24)));
673
674 release(&mut buffers, 8..22);
676 assert_eq!(buffers.buffered_bytes(), 3 + 3 + 2);
677 assert_eq!(buffers.get_bytes(5, 3).unwrap(), Bytes::from_static(b"567"));
678 assert_eq!(buffers.get_bytes(22, 2).unwrap(), Bytes::from_static(b"cd"));
679
680 buffers.release_ranges(&[50..60, 1..2, 0..1, 7..7]);
683 assert_eq!(buffers.buffered_bytes(), 1 + 3 + 2);
684 assert_eq!(buffers.get_bytes(2, 1).unwrap(), Bytes::from_static(b"2"));
685
686 release(&mut buffers, 0..100);
687 assert_eq!(buffers.buffered_bytes(), 0);
688 }
689
690 #[test]
691 #[cfg(feature = "arrow")]
692 fn release_ranges_removes_exact_and_overlapping_buffers() {
693 let mut buffers = PushBuffers::new(100);
694 for range in [10..20, 0..30, 10..15, 40..50] {
695 let data = Bytes::from(vec![0u8; (range.end - range.start) as usize]);
696 buffers.push_range(range, data).unwrap();
697 }
698 buffers.release_ranges(&[40..50, 10..15]);
699 buffers.assert_invariants();
700 assert_eq!(buffers.buffered_bytes(), 10 + 5 + 15);
701 assert!(buffers.has_range(&(0..10)));
702 assert!(buffers.has_range(&(15..30)));
703 assert!(!buffers.has_range(&(10..15)));
704 assert!(!buffers.has_range(&(40..50)));
705 }
706
707 #[test]
708 #[cfg(feature = "arrow")]
709 fn retain_ranges_keeps_only_the_given_bytes() {
710 let mut buffers = PushBuffers::new(100);
711 buffers
712 .push_range(0..10, Bytes::from_static(b"0123456789"))
713 .unwrap();
714 buffers
715 .push_range(20..24, Bytes::from_static(b"abcd"))
716 .unwrap();
717 buffers
718 .push_range(30..32, Bytes::from_static(b"xy"))
719 .unwrap();
720 buffers.retain_ranges(&[22..40, 2..4, 3..5, 8..9]);
722 assert_eq!(buffers.buffered_bytes(), 3 + 1 + 2 + 2);
723 assert_eq!(buffers.get_bytes(2, 3).unwrap(), Bytes::from_static(b"234"));
724 assert_eq!(buffers.get_bytes(8, 1).unwrap(), Bytes::from_static(b"8"));
725 assert!(!buffers.has_range(&(5..6)));
726 assert_eq!(buffers.get_bytes(22, 2).unwrap(), Bytes::from_static(b"cd"));
727 assert_eq!(buffers.get_bytes(30, 2).unwrap(), Bytes::from_static(b"xy"));
728 buffers.retain_ranges(&[]);
729 assert_eq!(buffers.buffered_bytes(), 0);
730 }
731
732 #[test]
735 #[cfg(feature = "arrow")]
736 fn retain_ranges_with_overlapping_buffers() {
737 let mut buffers = PushBuffers::new(100);
738 for range in [0..100, 3..70] {
739 let data = Bytes::from(vec![0u8; (range.end - range.start) as usize]);
740 buffers.push_range(range, data).unwrap();
741 }
742 buffers.retain_ranges(&[0..5, 50..60]);
743 buffers.assert_invariants();
744 assert_eq!(buffers.buffered_bytes(), 5 + 2 + 10 + 10);
745 assert!(buffers.has_range(&(0..5)));
746 assert!(buffers.has_range(&(50..60)));
747 assert!(!buffers.has_range(&(5..50)));
748 }
749
750 #[test]
751 fn push_range_accepts_matching_length() {
752 let mut buffers = PushBuffers::new(100);
753 buffers
754 .push_range(10..14, Bytes::from_static(b"abcd"))
755 .unwrap();
756 assert!(buffers.has_range(&(10..14)));
757 }
758
759 #[test]
760 fn push_range_rejects_short_buffer() {
761 let mut buffers = PushBuffers::new(100);
762 let err = buffers
763 .push_range(10..20, Bytes::from_static(b"abcd"))
764 .unwrap_err();
765 assert_eq!(
766 err.to_string(),
767 "Parquet error: Buffer length (4) does not match length (10) of range 10..20"
768 );
769 assert!(!buffers.has_range(&(10..20)));
770 }
771
772 fn file_bytes(range: Range<u64>) -> Bytes {
775 range.map(|i| (i % 251) as u8).collect::<Vec<u8>>().into()
776 }
777
778 fn push(buffers: &mut PushBuffers, range: Range<u64>) {
779 buffers
780 .push_range(range.clone(), file_bytes(range))
781 .unwrap();
782 }
783
784 #[track_caller]
787 fn assert_valid(buffers: &PushBuffers) {
788 buffers.assert_invariants();
789 for (range, buffer) in buffers.ranges.iter().zip(&buffers.buffers) {
790 assert_eq!(*buffer, file_bytes(range.clone()));
791 }
792 }
793
794 #[test]
795 fn overlapping_pushes_find_the_containing_buffer() {
796 let mut buffers = PushBuffers::new(1000);
797 for range in [50..60, 0..100, 55..58, 10..20] {
800 push(&mut buffers, range);
801 }
802 assert_valid(&buffers);
803 assert_eq!(buffers.get_bytes(55, 35).unwrap(), file_bytes(55..90));
805 assert!(buffers.has_range(&(0..100)));
806 assert!(buffers.has_range(&(99..100)));
807 assert!(!buffers.has_range(&(99..101)));
808 assert!(matches!(
809 buffers.get_bytes(90, 20),
810 Err(ParquetError::NeedMoreDataRange(r)) if r == (90..110)
811 ));
812
813 let mut reader = buffers.get_read(56).unwrap();
815 let mut out = [0u8; 30];
816 std::io::Read::read_exact(&mut reader, &mut out).unwrap();
817 assert_eq!(&out[..], &file_bytes(56..86)[..]);
818 }
819
820 #[test]
821 #[cfg(feature = "arrow")]
822 fn clear_ranges_drops_exact_matches_only() {
823 let mut buffers = PushBuffers::new(1000);
824 for range in [10..20, 0..30, 10..15, 40..50] {
825 push(&mut buffers, range);
826 }
827 buffers.clear_ranges(&[40..50, 10..15, 5..30]);
828 assert_valid(&buffers);
829 assert_eq!(buffers.ranges, vec![0..30, 10..20]);
830 }
831
832 #[test]
833 #[cfg(feature = "arrow")]
834 fn clear_ranges_with_buffers_of_the_same_start() {
835 let mut buffers = PushBuffers::new(1000);
836 for range in [0..5, 10..20, 10..15, 10..20, 10..30, 10..12, 40..50] {
837 push(&mut buffers, range);
838 }
839 buffers.clear_ranges(&[10..30, 10..20, 10..20, 60..70]);
842 assert_valid(&buffers);
843 assert_eq!(buffers.ranges, vec![0..5, 10..15, 10..12, 40..50]);
844 assert_eq!(buffers.buffered_bytes(), 22);
845
846 buffers.clear_ranges(&[10..20, 0..50]);
848 assert_valid(&buffers);
849 assert_eq!(buffers.ranges, vec![0..5, 10..15, 10..12, 40..50]);
850 }
851
852 #[test]
855 #[cfg(feature = "arrow")]
856 fn fuzz_matches_a_linear_scan() {
857 use rand::rngs::StdRng;
858 use rand::{RngExt, SeedableRng};
859
860 fn random_range(rng: &mut StdRng) -> Range<u64> {
861 let start = rng.random_range(0..500);
862 let len = [0, 1, 5, 20, 100, 300][rng.random_range(0..6)];
863 start..start + len
864 }
865
866 for seed in 0..200 {
867 let mut rng = StdRng::seed_from_u64(seed);
868 let mut buffers = PushBuffers::new(1000);
869 let mut model: Vec<Range<u64>> = vec![];
870 for _ in 0..60 {
871 match rng.random_range(0..10) {
872 0..4 => {
873 let range = random_range(&mut rng);
874 push(&mut buffers, range.clone());
875 if !range.is_empty() {
877 model.push(range);
878 }
879 }
880 4..6 => {
881 let mut clear: Vec<_> = (0..rng.random_range(1..4))
883 .map(|_| random_range(&mut rng))
884 .collect();
885 if !model.is_empty() {
886 clear.push(model[rng.random_range(0..model.len())].clone());
887 }
888 buffers.clear_ranges(&clear);
889 model.retain(|r| !clear.contains(r));
890 }
891 _ => {
892 let range = random_range(&mut rng);
893 let expected = range.is_empty()
894 || model
895 .iter()
896 .any(|r| r.start <= range.start && r.end >= range.end);
897 assert_eq!(buffers.has_range(&range), expected, "seed {seed} {range:?}");
898 if expected {
899 let len = (range.end - range.start) as usize;
900 assert_eq!(
901 buffers.get_bytes(range.start, len).unwrap(),
902 file_bytes(range.clone())
903 );
904 }
905 }
906 }
907 assert_valid(&buffers);
908 let mut actual = Vec::from(buffers.ranges.clone());
909 actual.sort_by_key(|r| (r.start, r.end));
910 model.sort_by_key(|r| (r.start, r.end));
911 assert_eq!(actual, model, "seed {seed}");
912 }
913 }
914 }
915
916 #[test]
917 fn push_ranges_rejects_mismatched_counts() {
918 let mut buffers = PushBuffers::new(100);
919 let err = buffers
920 .push_ranges(vec![0..4, 4..8], vec![Bytes::from_static(b"abcd")])
921 .unwrap_err();
922 assert_eq!(
923 err.to_string(),
924 "Parquet error: Number of ranges (2) must match number of buffers (1)"
925 );
926 }
927
928 #[cfg(feature = "arrow")]
930 fn release_by_rebuild(
931 buffers: &PushBuffers,
932 release: &[Range<u64>],
933 ) -> Vec<(Range<u64>, Bytes)> {
934 let release = merge_ranges(release);
935 let mut parts = vec![];
936 for (range, buffer) in &buffered_parts(buffers) {
937 let mut start = range.start;
938 let mut keep = |part: Range<u64>| {
939 let offset = |pos: u64| (pos - range.start) as usize;
940 parts.push((
941 part.clone(),
942 buffer.slice(offset(part.start)..offset(part.end)),
943 ));
944 };
945 for r in release
946 .iter()
947 .filter(|r| r.start < range.end && r.end > range.start)
948 {
949 if start < r.start {
950 keep(start..r.start);
951 }
952 start = start.max(r.end);
953 }
954 if start < range.end {
955 keep(start..range.end);
956 }
957 }
958 parts.sort_by_key(|(range, _)| range.start);
959 parts
960 }
961
962 #[test]
963 #[expect(clippy::reversed_empty_ranges)]
964 fn empty_ranges() {
965 use std::io::Read;
966 let mut buffers = PushBuffers::new(100);
968 assert!(buffers.has_range(&(50..50)));
969 assert_eq!(buffers.get_bytes(50, 0).unwrap(), Bytes::new());
970 assert_eq!(buffers.get_read(50).unwrap().read(&mut []).unwrap(), 0);
971
972 buffers.push_range(30..30, Bytes::new()).unwrap();
974 buffers.push_range(10..5, Bytes::new()).unwrap();
975 assert!(buffers.ranges.is_empty());
976 assert!(buffers.buffers.is_empty());
977 buffers.assert_invariants();
978
979 buffers
981 .push_range(20..25, Bytes::from_static(b"abcde"))
982 .unwrap();
983 buffers.push_range(22..22, Bytes::new()).unwrap();
984 buffers.assert_invariants();
985 assert_eq!(buffers.ranges, vec![20..25]);
986 assert!(buffers.has_range(&(21..24)));
987 assert_eq!(
988 buffers.get_bytes(21, 3).unwrap(),
989 Bytes::from_static(b"bcd")
990 );
991 let mut buf = [0; 2];
992 buffers.get_read(23).unwrap().read_exact(&mut buf).unwrap();
993 assert_eq!(&buf, b"de");
994 }
995
996 #[test]
997 #[cfg(feature = "arrow")]
998 #[expect(clippy::reversed_empty_ranges)]
999 fn release_ranges_splits_and_removes_empty_buffers() {
1000 let mut buffers = PushBuffers::new(100);
1001 buffers
1002 .push_range(0..20, Bytes::from_static(b"abcdefghijklmnopqrst"))
1003 .unwrap();
1004 buffers.push_range(30..30, Bytes::new()).unwrap();
1006 buffers.push_range(10..5, Bytes::new()).unwrap();
1007
1008 buffers.release_ranges(&[3..5, 8..10]);
1010 assert_eq!(buffers.ranges, vec![0..3, 5..8, 10..20]);
1011 assert_eq!(buffers.buffered_bytes(), 16);
1012 assert_eq!(buffers.get_bytes(5, 3).unwrap(), Bytes::from_static(b"fgh"));
1013
1014 release(&mut buffers, 5..8);
1016 assert_eq!(buffers.ranges, vec![0..3, 10..20]);
1017 assert_eq!(buffers.buffered_bytes(), 13);
1018 }
1019
1020 #[test]
1021 #[cfg(feature = "arrow")]
1022 fn fuzz_release_ranges_matches_rebuild() {
1023 use rand::{RngExt, SeedableRng, rngs::StdRng};
1024 let data: Vec<u8> = (0..=255).collect();
1025 let mut rng = StdRng::seed_from_u64(42);
1026 for _ in 0..2000 {
1027 let mut buffers = PushBuffers::new(256);
1028 for _ in 0..rng.random_range(0..6) {
1029 let start = rng.random_range(0..100u64);
1030 if rng.random_bool(0.1) {
1031 let end = start.saturating_sub(rng.random_range(1..5u64));
1033 buffers.push_range(start..end, Bytes::new()).unwrap();
1034 continue;
1035 }
1036 let end = start + rng.random_range(0..20u64);
1037 let bytes = Bytes::copy_from_slice(&data[start as usize..end as usize]);
1038 buffers.push_range(start..end, bytes).unwrap();
1039 }
1040 for _ in 0..3 {
1041 let release: Vec<_> = (0..rng.random_range(0..4))
1042 .map(|_| {
1043 let start = rng.random_range(0..110u64);
1044 start..start + rng.random_range(0..15u64)
1045 })
1046 .collect();
1047 let overlaps = buffers.ranges.iter().any(|range| {
1048 !range.is_empty()
1049 && release
1050 .iter()
1051 .any(|r| !r.is_empty() && r.start < range.end && r.end > range.start)
1052 });
1053 let before = buffered_parts(&buffers);
1054 let expected = release_by_rebuild(&buffers, &release);
1055
1056 buffers.release_ranges(&release);
1057 buffers.assert_invariants();
1058 let actual = buffered_parts(&buffers);
1059 if overlaps {
1060 let by_range = |mut parts: Vec<(Range<u64>, Bytes)>| {
1063 parts.sort_by_key(|(range, _)| (range.start, range.end));
1064 parts
1065 };
1066 assert_eq!(
1067 by_range(actual.clone()),
1068 by_range(expected),
1069 "release {release:?} of {before:?}"
1070 );
1071 } else {
1072 assert_eq!(actual, before, "release {release:?} of {before:?}");
1073 }
1074 for (range, buffer) in actual.iter().filter(|(range, _)| !range.is_empty()) {
1075 assert_eq!(
1076 &data[range.start as usize..range.end as usize],
1077 buffer.as_ref()
1078 );
1079 }
1080 let total: u64 = actual
1081 .iter()
1082 .map(|(r, _)| r.end.saturating_sub(r.start))
1083 .sum();
1084 assert_eq!(buffers.buffered_bytes(), total);
1085 }
1086 }
1087 }
1088}