Skip to main content

parquet/util/
push_buffers.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5use 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/// Holds multiple non-contiguous, caller-provided buffers of file data.
14///
15/// This is the in-memory buffer used by the push-based Parquet decoders
16/// (`ParquetPushDecoder` and `ParquetMetaDataPushDecoder`). It can be
17/// constructed up front and handed to a builder so the decoder reuses bytes
18/// that have already been fetched.
19///
20/// Features:
21/// 1. Zero copy
22/// 2. non contiguous ranges of bytes
23///
24/// # Non Coalescing
25///
26/// This buffer does not coalesce  (merging adjacent ranges of bytes into a
27/// single range). Coalescing at this level would require copying the data but
28/// the caller may already have the needed data in a single buffer which would
29/// require no copying.
30///
31/// Thus, the implementation defers to the caller to coalesce subsequent requests
32/// if desired.
33///
34/// # Ordering
35///
36/// The buffers are sorted by the start of their range. Thus, lookups use a
37/// binary search, not a scan of all buffers. Pushed ranges can overlap.
38#[derive(Debug, Clone, Default)]
39pub struct PushBuffers {
40    /// the virtual "offset" of this buffers (added to any request)
41    offset: u64,
42    /// The total length of the file being decoded
43    file_len: u64,
44    /// The ranges of data that are available for decoding (not adjusted for
45    /// offset), sorted by `start`
46    ///
47    /// A `VecDeque`, because a scan pushes buffers at the end and releases
48    /// them at the start. Both are then `O(1)` for each buffer.
49    ranges: VecDeque<Range<u64>>,
50    /// The buffers of data that can be used to decode the Parquet file, in the
51    /// same order as `ranges`
52    buffers: VecDeque<Bytes>,
53    /// The length of the longest range in `ranges`.
54    ///
55    /// This keeps lookups fast in the common case: buffers that do not
56    /// overlap and have similar lengths. Pushed ranges can overlap, so a
57    /// lookup cannot stop at the nearest buffer. `max_len` tells the lookup
58    /// when no earlier buffer can reach the requested range, so it checks one
59    /// or two buffers, not all of them. See [`Self::find`].
60    max_len: MaxLen,
61    /// The sum of the lengths of `ranges`, kept up to date so that
62    /// [`Self::buffered_bytes`] does not scan all ranges.
63    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    /// Create a new, empty `PushBuffers` for a file of the given length.
92    ///
93    /// Use [`PushBuffers::default`] when the file length is unknown or
94    /// irrelevant (e.g. the push decoder, which tracks ranges by absolute
95    /// offset and never consults `file_len`).
96    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    /// Push all the ranges and buffers
108    ///
109    /// # Errors
110    /// Returns an error if the number of ranges does not match the number of
111    /// buffers, or if any buffer's length does not match its range (see
112    /// [`Self::push_range`]).
113    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    /// Push a new range and its associated buffer
132    ///
133    /// An empty range adds no bytes, so it is not stored. An empty range is
134    /// always available (see `has_range`).
135    ///
136    /// # Errors
137    /// Returns an error if the buffer's length does not match the range's
138    /// length, e.g. when a truncated (short) read is pushed.
139    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        // Insert after all buffers that start at or before `range.start`.
154        // Thus, ranges pushed in file order go at the end.
155        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    /// Returns true if the Buffers contains data for the given range
164    ///
165    /// An empty range needs no bytes, so it is always available.
166    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    /// Returns the index of a buffer that contains all bytes of `start..end`,
171    /// if any.
172    fn find(&self, start: u64, end: u64) -> Option<usize> {
173        // Common case: the buffers do not overlap. Then only the last buffer
174        // that starts at or before `start` can contain `start..end`:
175        //
176        //   buffers:  0..25    ├─────────┤
177        //             25..50             ├─────────┤
178        //             50..75                       ├─────────┤
179        //             75..100                                ├─────────┤
180        //   find:     55..70                         ├─────┤  only 50..75 can contain it
181        //
182        // But pushed buffers can overlap. Then a buffer that starts much
183        // earlier can be the one that contains `start..end`:
184        //
185        //   buffers:  0..100   ├───────────────────────────────────────┤
186        //             50..60                       ├───┤
187        //             55..58                         ├┤
188        //   find:     55..90                         ├─────────────┤  only 0..100 contains it
189        //
190        // Thus, scan back from the last buffer that starts at or before
191        // `start`. Without a limit, a lookup that finds nothing scans all
192        // earlier buffers. `max_len` gives the limit: a buffer that starts
193        // more than `max_len` bytes before `end` ends before `end`, and so do
194        // all buffers before it. Stop there.
195        //
196        // In the common case the scan stops after one or two buffers. It is
197        // long only if a caller pushes one large buffer and then many small
198        // buffers after its start.
199        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    /// return the file length of the Parquet file being read
210    pub(crate) fn file_len(&self) -> u64 {
211        self.file_len
212    }
213
214    /// Specify a new offset
215    fn with_offset(mut self, offset: u64) -> Self {
216        self.offset = offset;
217        self
218    }
219
220    /// Return the total length of all buffered ranges.
221    ///
222    /// This counts the bytes that the decoder can still read, not the
223    /// allocated memory. [`Self::release_ranges`] keeps the remaining parts of
224    /// a buffer as slices of the pushed [`Bytes`], and the allocation of a
225    /// pushed [`Bytes`] is freed only after all of its parts are released.
226    #[cfg(feature = "arrow")]
227    pub(crate) fn buffered_bytes(&self) -> u64 {
228        self.buffered_bytes
229    }
230
231    /// Clear any range and corresponding buffer that is exactly in the ranges_to_clear
232    ///
233    /// The cost is `O(log N)` in the number of buffers for each range to
234    /// clear.
235    #[cfg(feature = "arrow")]
236    pub(crate) fn clear_ranges(&mut self, ranges_to_clear: &[Range<u64>]) {
237        // The indexes of the buffers to remove. The buffers are sorted by
238        // start, so all buffers with the same start are adjacent.
239        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        // Buffers with the same start are not sorted by end, and
254        // `ranges_to_clear` can contain a range more than once.
255        remove.sort_unstable();
256        remove.dedup();
257        let (Some(&first), Some(&last)) = (remove.first(), remove.last()) else {
258            return;
259        };
260        // Move the kept buffers in `first..=last` to the start of that span,
261        // in order, then remove the rest of the span. The buffers outside the
262        // span are not visited.
263        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        // `max_len` changes only when no buffer of that length remains.
279        self.max_len
280            .rescan_if_stale(self.ranges.iter().map(|r| r.end.saturating_sub(r.start)));
281    }
282
283    /// Remove all buffered bytes in `ranges`.
284    ///
285    /// A buffer that overlaps a range is trimmed or split, and the parts
286    /// outside the range are kept. The kept parts are zero-copy slices, which
287    /// record the bytes that the decoder can still read. Thus, the allocator
288    /// frees the memory of a pushed [`Bytes`] only after all of its parts are
289    /// removed.
290    ///
291    /// The buffers stay sorted by start, which lookups require (see
292    /// [`Self::find`]). If no buffer overlaps `ranges`, the buffers do not
293    /// change.
294    ///
295    /// The cost is `O(log N)` in the number of buffers for each range in
296    /// `ranges`, plus the number of buffers that overlap `ranges`.
297    #[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        // Find the buffers that overlap a released range. The buffers are
310        // sorted by start, and no buffer is longer than `max_len`. Thus, a
311        // buffer can overlap `r` only if it starts before `r.end` and less
312        // than `max_len` bytes before `r.start`:
313        //
314        //   buffers:  0..25    ├─────────┤
315        //             25..50             ├─────────┤
316        //             50..75                       ├─────────┤
317        //             75..100                                ├─────────┤
318        //   release:  55..70                         ├─────┤  max_len is 25: check 50..75 only
319        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            // A buffer that an earlier released range visited is not visited
328            // again, because `overlaps` checks all released ranges.
329            overlapping
330                .extend((first.max(visited)..end).filter(|&idx| overlaps(&self.ranges[idx])));
331            visited = visited.max(end);
332        }
333        // Most calls release ranges that are no longer buffered. Return
334        // before changing the buffers.
335        let (Some(&first), Some(&last)) = (overlapping.first(), overlapping.last()) else {
336            return;
337        };
338        // Trim the buffers that overlap a released range in place, and do not
339        // clone or move the others. The parts after the first part of a split
340        // buffer go to `split`. A buffer that is released entirely becomes
341        // empty, and is removed below.
342        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            // Each kept part is shorter than `whole`.
348            self.max_len.remove(whole.end - whole.start);
349            let offset = |pos: u64| (pos - whole.start) as usize;
350            // The parts of `whole` between the released ranges.
351            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            // Remove the released buffers. They are all in `first..=last`.
389            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        // A trim moves the start of a buffer only past released bytes. Each
402        // other buffer that starts in those bytes is trimmed past them too,
403        // or is empty and removed. Thus, the buffers are still sorted, except
404        // for the split parts, which are appended. Splits are rare, so sort
405        // all buffers then.
406        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        // `max_len` changes only when no buffer of that length remains. Only
416        // then pay for the pass over all buffers, which keeps `max_len` exact
417        // (see `MaxLen::rescan_if_stale`).
418        self.max_len
419            .rescan_if_stale(self.ranges.iter().map(|r| r.end.saturating_sub(r.start)));
420    }
421
422    /// Remove all buffered bytes outside `keep`.
423    ///
424    /// This calls [`Self::release_ranges`] with the complement of `keep`, so
425    /// the same rules apply to the kept parts.
426    #[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    /// Clear all buffered ranges and their corresponding data
439    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    /// Panics if `ranges`, `buffers` and `max_len` do not agree, or if the
447    /// buffers are not sorted.
448    #[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/// Sort `ranges` by start, remove empty ranges, and merge ranges that
481/// overlap or are adjacent.
482#[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
502/// less efficient implementation of Read for Buffers
503impl 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        // Find the range that contains the start offset
509        let found = self.find(self.offset, self.offset + buf.len() as u64);
510        if let Some(idx) = found {
511            // Found the range, figure out the starting offset in the buffer
512            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            // If we found the range, we can return the number of bytes read
516            // advance our offset
517            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        // An empty range needs no bytes (see `has_range`)
537        if length == 0 {
538            return Ok(Bytes::new());
539        }
540        // find the range that contains the start offset
541        if let Some(idx) = self.find(start, start + length as u64) {
542            // Found the range, figure out the starting offset in the buffer
543            let start_offset = (start - self.ranges[idx].start) as usize;
544            return Ok(self.buffers[idx].slice(start_offset..start_offset + length));
545        }
546        // Signal that we need more data
547        let requested_end = start + length as u64;
548        Err(ParquetError::NeedMoreDataRange(start..requested_end))
549    }
550}
551
552/// The length of the longest buffered range, and the number of ranges of
553/// that length.
554///
555/// The two values change together, so only the methods of this type change
556/// them. The length can decrease only when the count goes to zero. Thus, a
557/// release does not scan all ranges while other ranges of that length remain.
558#[derive(Debug, Default, Clone, Copy)]
559struct MaxLen {
560    len: u64,
561    count: usize,
562}
563
564impl MaxLen {
565    /// The length of the longest range. It can be too large until the next
566    /// call to [`Self::rescan_if_stale`]. A length that is too large is still
567    /// correct, lookups only scan further.
568    #[inline]
569    fn get(&self) -> u64 {
570        self.len
571    }
572
573    /// Record a new range of length `len`.
574    #[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    /// Record that a range of length `len` was removed. Call
584    /// [`Self::rescan_if_stale`] after the removals.
585    #[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    /// If no range of the current length remains, set the length from the
594    /// lengths of the remaining ranges in `lens`.
595    ///
596    /// This update is for performance: a large buffer that was removed must
597    /// not slow down later lookups. The pass over `lens` occurs only when the
598    /// last range of the longest length is removed.
599    #[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    /// Release one range.
614    #[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    /// The buffered ranges and their data.
621    #[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        // Split the first buffer, and do not change the second buffer.
663        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        // One range that overlaps two buffers trims both of them.
675        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        // Ranges in any order, adjacent or empty, and bytes that are not
681        // buffered.
682        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        // Ranges in any order, overlapping, and outside the buffers.
721        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    /// Lookups stay correct when the kept parts of overlapping buffers
733    /// interleave.
734    #[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    /// The bytes of a fake file: byte `i` is `i % 251`, so any slice of it is
773    /// easy to build and to check.
774    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    /// Checks the invariants, and that each buffer still has the bytes of its
785    /// range.
786    #[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        // Small buffers inside a large one start closer to most offsets.
798        // The pushes are not in file order: `assert_valid` checks the sort.
799        for range in [50..60, 0..100, 55..58, 10..20] {
800            push(&mut buffers, range);
801        }
802        assert_valid(&buffers);
803        // 55..90 starts in 50..60 and 55..58, but only 0..100 contains it.
804        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        // `Read` finds the same buffer.
814        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 with the same start are not sorted by end. A range to clear
840        // can match more than one buffer, and can be given more than once.
841        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        // No buffer matches: the buffers do not change.
847        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    /// Random pushes, clears and lookups, compared with a list that is
853    /// scanned in full for each lookup.
854    #[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                        // An empty push is not stored.
876                        if !range.is_empty() {
877                            model.push(range);
878                        }
879                    }
880                    4..6 => {
881                        // Clear some pushed ranges and some other ranges.
882                        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    /// The result of `release_ranges`, computed by rebuilding all buffers.
929    #[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        // An empty range is available without any buffers.
967        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        // Pushing an empty or an inverted range is a no-op.
973        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        // Reads of real data still work after an empty push.
980        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        // An empty and an inverted range, which `push_range` accepts.
1005        buffers.push_range(30..30, Bytes::new()).unwrap();
1006        buffers.push_range(10..5, Bytes::new()).unwrap();
1007
1008        // Split one buffer into three parts.
1009        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 a whole buffer.
1015        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                    // An inverted range, which `push_range` accepts.
1032                    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                    // The order of buffers with the same start is not
1061                    // specified.
1062                    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}