Skip to main content

parquet/column/reader/
decoder.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 bytes::Bytes;
6
7use crate::basic::{Encoding, EncodingMask, Type};
8use crate::data_type::DataType;
9use crate::encodings::{
10    decoding::{Decoder, DictDecoder, PlainDecoder, get_decoder},
11    rle::RleDecoder,
12};
13use crate::errors::{ParquetError, Result};
14use crate::schema::types::ColumnDescPtr;
15use crate::util::bit_util::{BitReader, num_required_bits};
16
17/// Decodes level data
18pub trait ColumnLevelDecoder {
19    type Buffer;
20
21    /// Set data for this [`ColumnLevelDecoder`]
22    fn set_data(&mut self, encoding: Encoding, data: Bytes) -> Result<()>;
23}
24
25pub trait RepetitionLevelDecoder: ColumnLevelDecoder {
26    /// Reads up to `num_records` records, and at most `num_levels` levels, of repetition
27    /// level data into `out`, returning the number of complete records and levels read.
28    ///
29    /// A record only ends when the data contains a subsequent repetition level of 0;
30    /// it is therefore left to the caller to delimit the final record in a column.
31    fn read_rep_levels(
32        &mut self,
33        out: &mut Self::Buffer,
34        num_records: usize,
35        num_levels: usize,
36    ) -> Result<(usize, usize)>;
37
38    /// Skips over up to `num_levels` repetition levels corresponding to `num_records`
39    /// records, where a record is delimited by a repetition level of 0.
40    ///
41    /// Returns the number of records skipped, and the number of levels skipped.
42    ///
43    /// A record only ends when the data contains a subsequent repetition level of 0;
44    /// it is therefore left to the caller to delimit the final record in a column.
45    fn skip_rep_levels(&mut self, num_records: usize, num_levels: usize) -> Result<(usize, usize)>;
46
47    /// Flush any partially read or skipped record.
48    ///
49    /// Returns true if there was such a record, which the caller should count
50    /// as complete.
51    fn flush_partial(&mut self) -> bool;
52}
53
54pub trait DefinitionLevelDecoder: ColumnLevelDecoder {
55    /// Read up to `num_levels` definition levels into `out`.
56    ///
57    /// Returns the number of values read, and the number of levels read.
58    fn read_def_levels(
59        &mut self,
60        out: &mut Self::Buffer,
61        num_levels: usize,
62    ) -> Result<(usize, usize)>;
63
64    /// Skips over `num_levels` definition levels.
65    ///
66    /// Returns the number of values skipped, and the number of levels skipped.
67    fn skip_def_levels(&mut self, num_levels: usize) -> Result<(usize, usize)>;
68}
69
70/// Decodes value data
71pub trait ColumnValueDecoder {
72    type Buffer;
73
74    /// Create a new [`ColumnValueDecoder`]
75    fn new(col: &ColumnDescPtr) -> Self;
76
77    /// Set the current dictionary page
78    fn set_dict(
79        &mut self,
80        buf: Bytes,
81        num_values: u32,
82        encoding: Encoding,
83        is_sorted: bool,
84    ) -> Result<()>;
85
86    /// Set the current data page
87    ///
88    /// - `encoding` - the encoding of the page
89    /// - `data` - a point to the page's uncompressed value data
90    /// - `num_levels` - the number of levels contained within the page, i.e. values including nulls
91    /// - `num_values` - the number of non-null values contained within the page (V2 page only)
92    ///
93    /// Note: data encoded with [`Encoding::RLE`] may not know its exact length, as the final
94    /// run may be zero-padded. As such if `num_values` is not provided (i.e. `None`),
95    /// subsequent calls to `ColumnValueDecoder::read` may yield more values than
96    /// non-null definition levels within the page
97    fn set_data(
98        &mut self,
99        encoding: Encoding,
100        data: Bytes,
101        num_levels: usize,
102        num_values: Option<usize>,
103    ) -> Result<()>;
104
105    /// Read up to `num_values` values into `out`.
106    fn read(&mut self, out: &mut Self::Buffer, num_values: usize) -> Result<usize>;
107
108    /// Skips over `num_values` values
109    ///
110    /// Returns the number of values skipped
111    fn skip_values(&mut self, num_values: usize) -> Result<usize>;
112}
113
114fn fixed_len_byte_array_payload_size(
115    num_values: usize,
116    type_length: usize,
117    page: &str,
118) -> Result<usize> {
119    num_values.checked_mul(type_length).ok_or_else(|| {
120        general_err!(
121            "FIXED_LEN_BYTE_ARRAY {} payload size overflow: {} values of {} bytes",
122            page,
123            num_values,
124            type_length
125        )
126    })
127}
128
129/// Validate a complete decompressed PLAIN FLBA value section, excluding levels.
130/// `num_values` must count physical non-null values, not rows or requested values.
131/// Canonical payloads are returned unchanged, even if values resemble prefixes.
132pub(crate) fn normalize_fixed_len_byte_array_payload(
133    data: Bytes,
134    num_values: usize,
135    type_length: usize,
136    page: &str,
137) -> Result<Bytes> {
138    let expected_len = fixed_len_byte_array_payload_size(num_values, type_length, page)?;
139    if data.len() == expected_len {
140        return Ok(data);
141    }
142
143    // Temporary mitigation for arrow-rs #11261, reached only for a noncanonical
144    // size. Keep the repair separate from ordinary validation and value decoding.
145    super::legacy_fixed_len_byte_array::decode_length_prefixed_plain(
146        data,
147        num_values,
148        type_length,
149        expected_len,
150        page,
151    )
152}
153
154/// Prepare a complete FLBA data-page value section after extracting the levels.
155/// PLAIN requires exact size validation; other compliant encodings are unchanged.
156pub(crate) fn normalize_fixed_len_byte_array_data(
157    data: Bytes,
158    num_values: usize,
159    type_length: usize,
160    encoding: Encoding,
161) -> Result<(Encoding, Bytes)> {
162    match encoding {
163        Encoding::PLAIN => Ok((
164            encoding,
165            normalize_fixed_len_byte_array_payload(
166                data,
167                num_values,
168                type_length,
169                "PLAIN data page",
170            )?,
171        )),
172        Encoding::DELTA_LENGTH_BYTE_ARRAY => {
173            // Temporary mitigation only: this encoding is not defined for FLBA.
174            // Do not add support for it to the ordinary value decoders.
175            let expected_len = fixed_len_byte_array_payload_size(
176                num_values,
177                type_length,
178                "DELTA_LENGTH_BYTE_ARRAY data page",
179            )?;
180            let data = super::legacy_fixed_len_byte_array::decode_delta_length(
181                data,
182                num_values,
183                type_length,
184                expected_len,
185            )?;
186            Ok((Encoding::PLAIN, data))
187        }
188        _ => Ok((encoding, data)),
189    }
190}
191
192/// A value section ready for its ordinary decoder. When `validate_count` is set,
193/// account for its physical values during normal level decoding.
194pub(super) struct PreparedFixedLenByteArrayPage {
195    pub(super) encoding: Encoding,
196    pub(super) data: Bytes,
197    pub(super) validate_count: bool,
198}
199
200/// Prepare V1 FLBA values without teaching the column reader historical layouts.
201/// `definition_levels` contains the maximum level, encoding and encoded levels;
202/// absent levels mean that the page's physical count is already known.
203pub(super) fn prepare_v1_fixed_len_byte_array(
204    data: Bytes,
205    num_levels: usize,
206    type_length: usize,
207    encoding: Encoding,
208    definition_levels: Option<(i16, Encoding, &Bytes)>,
209) -> Result<PreparedFixedLenByteArrayPage> {
210    let Some((max_level, level_encoding, levels)) = definition_levels else {
211        let (encoding, data) =
212            normalize_fixed_len_byte_array_data(data, num_levels, type_length, encoding)?;
213        return Ok(PreparedFixedLenByteArrayPage {
214            encoding,
215            data,
216            validate_count: false,
217        });
218    };
219
220    // This callback is lazy: ordinary nullable pages do not create a second
221    // decoder or traverse their levels before normal reading begins.
222    let count_values = || {
223        let mut counter = DefinitionLevelDecoderImpl::new(max_level);
224        counter.set_data(level_encoding, levels.clone())?;
225        let (values, read) = counter.skip_def_levels(num_levels)?;
226        if read != num_levels {
227            return Err(general_err!(
228                "Invalid FIXED_LEN_BYTE_ARRAY {encoding} data page: \
229                 expected {num_levels} definition levels, got {read}"
230            ));
231        }
232        Ok(values)
233    };
234
235    let mut page = PreparedFixedLenByteArrayPage {
236        encoding,
237        data,
238        validate_count: false,
239    };
240    // Temporary compatibility hook. Removing it leaves the canonical path and
241    // its physical-value validation intact.
242    if super::legacy_fixed_len_byte_array::prepare_v1_page(
243        &mut page,
244        num_levels,
245        type_length,
246        &count_values,
247    )? {
248        return Ok(page);
249    }
250
251    if encoding == Encoding::PLAIN {
252        if num_levels == 0 || type_length == 0 {
253            // Preserve empty-page header validation and avoid a zero-width
254            // byte budget, which cannot establish the physical value count.
255            page.data = normalize_fixed_len_byte_array_payload(
256                page.data,
257                count_values()?,
258                type_length,
259                "PLAIN data page",
260            )?;
261        } else {
262            if !page.data.len().is_multiple_of(type_length) {
263                return Err(general_err!(
264                    "Invalid FIXED_LEN_BYTE_ARRAY PLAIN data page payload length: \
265                     {} bytes is not a multiple of {type_length}",
266                    page.data.len()
267                ));
268            }
269            page.validate_count = true;
270        }
271    }
272    Ok(page)
273}
274
275/// Bucket-based storage for decoder instances keyed by `Encoding`.
276///
277/// This replaces `HashMap` lookups with direct indexing to avoid hashing overhead in the
278/// hot decoding paths.
279const ENCODING_SLOTS: usize = Encoding::MAX_DISCRIMINANT as usize + 1;
280
281/// An implementation of [`ColumnValueDecoder`] for `[T::T]`
282pub struct ColumnValueDecoderImpl<T: DataType> {
283    descr: ColumnDescPtr,
284
285    current_encoding: Option<Encoding>,
286
287    /// Cache of decoders for existing encodings.
288    /// Uses `EncodingMask` and dense storage keyed by encoding discriminant.
289    decoder_mask: EncodingMask,
290    decoders: [Option<Box<dyn Decoder<T>>>; ENCODING_SLOTS],
291}
292
293impl<T: DataType> ColumnValueDecoder for ColumnValueDecoderImpl<T> {
294    type Buffer = Vec<T::T>;
295
296    fn new(descr: &ColumnDescPtr) -> Self {
297        Self {
298            descr: descr.clone(),
299            current_encoding: None,
300            decoder_mask: EncodingMask::default(),
301            decoders: std::array::from_fn(|_| None),
302        }
303    }
304
305    fn set_dict(
306        &mut self,
307        buf: Bytes,
308        num_values: u32,
309        mut encoding: Encoding,
310        _is_sorted: bool,
311    ) -> Result<()> {
312        if encoding == Encoding::PLAIN || encoding == Encoding::PLAIN_DICTIONARY {
313            encoding = Encoding::RLE_DICTIONARY
314        }
315
316        if self.decoder_mask.is_set(encoding) {
317            return Err(general_err!("Column cannot have more than one dictionary"));
318        }
319
320        if encoding == Encoding::RLE_DICTIONARY {
321            let buf = if self.descr.physical_type() == Type::FIXED_LEN_BYTE_ARRAY {
322                normalize_fixed_len_byte_array_payload(
323                    buf,
324                    num_values as usize,
325                    self.descr.type_length() as usize,
326                    "dictionary page",
327                )?
328            } else {
329                buf
330            };
331            let mut dictionary = PlainDecoder::<T>::new(self.descr.type_length());
332            dictionary.set_data(buf, num_values as usize)?;
333
334            let mut decoder = DictDecoder::new();
335            decoder.set_dict(Box::new(dictionary))?;
336            self.decoders[encoding as usize] = Some(Box::new(decoder));
337            self.decoder_mask.insert(encoding);
338            Ok(())
339        } else {
340            Err(nyi_err!(
341                "Invalid/Unsupported encoding type for dictionary: {}",
342                encoding
343            ))
344        }
345    }
346
347    fn set_data(
348        &mut self,
349        mut encoding: Encoding,
350        data: Bytes,
351        num_levels: usize,
352        num_values: Option<usize>,
353    ) -> Result<()> {
354        if encoding == Encoding::PLAIN_DICTIONARY {
355            encoding = Encoding::RLE_DICTIONARY;
356        }
357
358        let decoder = if encoding == Encoding::RLE_DICTIONARY {
359            self.decoders[encoding as usize]
360                .as_mut()
361                .expect("Decoder for dict should have been set")
362        } else {
363            let slot = encoding as usize;
364            if self.decoders[slot].is_none() {
365                let data_decoder = get_decoder::<T>(self.descr.clone(), encoding)?;
366                self.decoders[slot] = Some(data_decoder);
367                self.decoder_mask.insert(encoding);
368            }
369            self.decoders[slot]
370                .as_mut()
371                .expect("decoder should have been inserted")
372        };
373
374        decoder.set_data(data, num_values.unwrap_or(num_levels))?;
375        self.current_encoding = Some(encoding);
376        Ok(())
377    }
378
379    fn read(&mut self, out: &mut Self::Buffer, num_values: usize) -> Result<usize> {
380        let encoding = self
381            .current_encoding
382            .expect("current_encoding should be set");
383
384        let current_decoder = self.decoders[encoding as usize]
385            .as_mut()
386            .unwrap_or_else(|| panic!("decoder for encoding {encoding} should be set"));
387
388        // TODO: Push vec into decoder (#5177)
389        let start = out.len();
390        out.resize(start + num_values, T::T::default());
391        let read = current_decoder.get(&mut out[start..])?;
392        out.truncate(start + read);
393        Ok(read)
394    }
395
396    fn skip_values(&mut self, num_values: usize) -> Result<usize> {
397        let encoding = self
398            .current_encoding
399            .expect("current_encoding should be set");
400
401        let current_decoder = self.decoders[encoding as usize]
402            .as_mut()
403            .unwrap_or_else(|| panic!("decoder for encoding {encoding} should be set"));
404
405        current_decoder.skip(num_values)
406    }
407}
408
409enum LevelDecoder {
410    Packed(BitReader, u8),
411    Rle(RleDecoder),
412}
413
414impl LevelDecoder {
415    fn new(encoding: Encoding, data: Bytes, bit_width: u8) -> Result<Self> {
416        match encoding {
417            Encoding::RLE => {
418                let mut decoder = RleDecoder::new(bit_width);
419                decoder.set_data(data)?;
420                Ok(Self::Rle(decoder))
421            }
422            #[expect(deprecated)]
423            Encoding::BIT_PACKED => Ok(Self::Packed(BitReader::new(data), bit_width)),
424            _ => unreachable!("invalid level encoding: {}", encoding),
425        }
426    }
427
428    fn read(&mut self, out: &mut [i16]) -> Result<usize> {
429        match self {
430            Self::Packed(reader, bit_width) => {
431                Ok(reader.get_batch::<i16>(out, *bit_width as usize))
432            }
433            Self::Rle(reader) => Ok(reader.get_batch(out)?),
434        }
435    }
436}
437
438/// An implementation of [`DefinitionLevelDecoder`] for `[i16]`
439pub struct DefinitionLevelDecoderImpl {
440    decoder: Option<LevelDecoder>,
441    bit_width: u8,
442    max_level: i16,
443}
444
445impl DefinitionLevelDecoderImpl {
446    pub fn new(max_level: i16) -> Self {
447        let bit_width = num_required_bits(max_level as u64);
448        Self {
449            decoder: None,
450            bit_width,
451            max_level,
452        }
453    }
454}
455
456impl ColumnLevelDecoder for DefinitionLevelDecoderImpl {
457    type Buffer = Vec<i16>;
458
459    fn set_data(&mut self, encoding: Encoding, data: Bytes) -> Result<()> {
460        self.decoder = Some(LevelDecoder::new(encoding, data, self.bit_width)?);
461        Ok(())
462    }
463}
464
465impl DefinitionLevelDecoder for DefinitionLevelDecoderImpl {
466    fn read_def_levels(
467        &mut self,
468        out: &mut Self::Buffer,
469        num_levels: usize,
470    ) -> Result<(usize, usize)> {
471        // TODO: Push vec into decoder (#5177)
472        let start = out.len();
473        out.resize(start + num_levels, 0);
474        let levels_read = self.decoder.as_mut().unwrap().read(&mut out[start..])?;
475        out.truncate(start + levels_read);
476
477        let values_read = count_levels_eq(&out[start..], self.max_level);
478        Ok((values_read, levels_read))
479    }
480
481    fn skip_def_levels(&mut self, num_levels: usize) -> Result<(usize, usize)> {
482        if num_levels == 0 {
483            return Ok((0, 0));
484        }
485        match self.decoder.as_mut().unwrap() {
486            LevelDecoder::Rle(reader) => reader.skip_and_count(num_levels, self.max_level),
487            LevelDecoder::Packed(reader, 1) => Ok(reader.skip_and_count_ones(num_levels)),
488            LevelDecoder::Packed(reader, bit_width) => {
489                Ok(reader.skip_and_count(num_levels, *bit_width as usize, self.max_level))
490            }
491        }
492    }
493}
494
495/// Returns the number of levels equal to `level`.
496///
497/// Summing into a `u16`, over chunks short enough that the sum cannot
498/// overflow, helps the compiler vectorize the count better than summing into
499/// a `usize`.
500fn count_levels_eq(levels: &[i16], level: i16) -> usize {
501    levels
502        .chunks(u16::MAX as usize)
503        .map(|chunk| chunk.iter().map(|&l| u16::from(l == level)).sum::<u16>() as usize)
504        .sum()
505}
506
507pub(crate) const REPETITION_LEVELS_BATCH_SIZE: usize = 1024;
508
509/// An implementation of [`RepetitionLevelDecoder`] for `[i16]`
510pub struct RepetitionLevelDecoderImpl {
511    decoder: Option<LevelDecoder>,
512    bit_width: u8,
513    buffer: Box<[i16; REPETITION_LEVELS_BATCH_SIZE]>,
514    buffer_len: usize,
515    buffer_offset: usize,
516    /// Whether the levels read so far end with a record that has not ended yet
517    has_partial: bool,
518}
519
520impl RepetitionLevelDecoderImpl {
521    pub fn new(max_level: i16) -> Self {
522        let bit_width = num_required_bits(max_level as u64);
523        Self {
524            decoder: None,
525            bit_width,
526            buffer: Box::new([0; REPETITION_LEVELS_BATCH_SIZE]),
527            buffer_offset: 0,
528            buffer_len: 0,
529            has_partial: false,
530        }
531    }
532
533    fn fill_buf(&mut self) -> Result<()> {
534        let read = self.decoder.as_mut().unwrap().read(self.buffer.as_mut())?;
535        self.buffer_offset = 0;
536        self.buffer_len = read;
537        Ok(())
538    }
539
540    /// Counts the records that end within the unread levels in `self.buffer`,
541    /// looking at no more than `num_levels` of them and stopping once
542    /// `records_to_read` records have ended.
543    ///
544    /// Each repetition level of 0 starts a new record, which ends the record
545    /// before it. If `self.has_partial` is set, the levels before the first 0
546    /// continue a record started by an earlier call.
547    ///
548    /// Returns `(partial, records_read, levels_read)`:
549    /// - If it finds the end of the last requested record
550    ///   (`records_read == records_to_read`), `partial` is false and
551    ///   `levels_read` is the number of levels in the requested records, so the
552    ///   0 that starts the next record is left unread.
553    /// - Otherwise `partial` is true and `levels_read` is the number of levels
554    ///   inspected. The last record in those levels has not ended yet, and is
555    ///   not counted in `records_read`.
556    fn count_records(&self, records_to_read: usize, num_levels: usize) -> (bool, usize, usize) {
557        let levels = num_levels.min(self.buffer_len - self.buffer_offset);
558        let buf = &self.buffer[self.buffer_offset..self.buffer_offset + levels];
559
560        // Unless a previous call left a record partially read, the first level
561        // starts a record rather than completing one, so skip it
562        let mut scan_start = usize::from(!self.has_partial && !buf.is_empty());
563
564        // Skip over chunks that complete fewer records than are still needed,
565        // counting the 0s in each chunk rather than checking each level. Chunks
566        // are kept small so that a short read does not count many levels past
567        // where it ends, but not so small that the per-chunk overhead slows
568        // down long reads.
569        const CHUNK_SIZE: usize = 32;
570        let mut records_read = 0;
571        for chunk in buf[scan_start..].chunks(CHUNK_SIZE) {
572            let complete = count_levels_eq(chunk, 0);
573            if records_read + complete >= records_to_read {
574                break;
575            }
576            records_read += complete;
577            scan_start += chunk.len();
578        }
579
580        // Find where the last requested record ends, if it ends in `buf`
581        for (idx, item) in buf.iter().enumerate().skip(scan_start) {
582            if *item == 0 {
583                records_read += 1;
584
585                if records_read == records_to_read {
586                    return (false, records_read, idx);
587                }
588            }
589        }
590        // Either ran out of space in `num_levels` or data in `self.buffer`
591        (true, records_read, levels)
592    }
593}
594
595impl ColumnLevelDecoder for RepetitionLevelDecoderImpl {
596    type Buffer = Vec<i16>;
597
598    fn set_data(&mut self, encoding: Encoding, data: Bytes) -> Result<()> {
599        self.decoder = Some(LevelDecoder::new(encoding, data, self.bit_width)?);
600        self.buffer_len = 0;
601        self.buffer_offset = 0;
602        Ok(())
603    }
604}
605
606impl RepetitionLevelDecoder for RepetitionLevelDecoderImpl {
607    fn read_rep_levels(
608        &mut self,
609        out: &mut Self::Buffer,
610        num_records: usize,
611        num_levels: usize,
612    ) -> Result<(usize, usize)> {
613        let mut total_records_read = 0;
614        let mut total_levels_read = 0;
615
616        while total_records_read < num_records && total_levels_read < num_levels {
617            if self.buffer_len == self.buffer_offset {
618                self.fill_buf()?;
619                if self.buffer_len == 0 {
620                    break;
621                }
622            }
623
624            let (partial, records_read, levels_read) = self.count_records(
625                num_records - total_records_read,
626                num_levels - total_levels_read,
627            );
628
629            out.extend_from_slice(
630                &self.buffer[self.buffer_offset..self.buffer_offset + levels_read],
631            );
632
633            total_levels_read += levels_read;
634            total_records_read += records_read;
635            self.buffer_offset += levels_read;
636            self.has_partial = partial;
637        }
638        Ok((total_records_read, total_levels_read))
639    }
640
641    fn skip_rep_levels(&mut self, num_records: usize, num_levels: usize) -> Result<(usize, usize)> {
642        let mut total_records_read = 0;
643        let mut total_levels_read = 0;
644
645        while total_records_read < num_records && total_levels_read < num_levels {
646            if self.buffer_len == self.buffer_offset {
647                self.fill_buf()?;
648                if self.buffer_len == 0 {
649                    break;
650                }
651            }
652
653            let (partial, records_read, levels_read) = self.count_records(
654                num_records - total_records_read,
655                num_levels - total_levels_read,
656            );
657
658            total_levels_read += levels_read;
659            total_records_read += records_read;
660            self.buffer_offset += levels_read;
661            self.has_partial = partial;
662        }
663        Ok((total_records_read, total_levels_read))
664    }
665
666    fn flush_partial(&mut self) -> bool {
667        std::mem::take(&mut self.has_partial)
668    }
669}
670
671#[cfg(test)]
672mod tests {
673    use super::*;
674    use crate::encodings::rle::RleEncoder;
675    use rand::{prelude::*, rng};
676
677    #[test]
678    fn fixed_len_payload_validation() {
679        let mut rng = StdRng::seed_from_u64(11262);
680        for page in ["dictionary page", "PLAIN data page"] {
681            for width in [0, 1, 4, 8, 16, 32] {
682                for count in [0, 1, 2, 33] {
683                    let raw: Bytes = (0..width * count).map(|_| rng.random::<u8>()).collect();
684                    let result =
685                        normalize_fixed_len_byte_array_payload(raw.clone(), count, width, page)
686                            .unwrap();
687                    assert_eq!(result, raw);
688                    assert_eq!(
689                        result.as_ptr(),
690                        raw.as_ptr(),
691                        "canonical data must stay zero-copy"
692                    );
693                }
694            }
695            // These are two canonical values, not one length-prefixed value.
696            let raw = Bytes::from_static(b"\x04\0\0\0abcd");
697            assert_eq!(
698                normalize_fixed_len_byte_array_payload(raw.clone(), 2, 4, page).unwrap(),
699                raw
700            );
701            // Truncated and trailing data must still be rejected.
702            for data in [b"abcdefg".as_slice(), b"abcdefghi"] {
703                assert!(
704                    normalize_fixed_len_byte_array_payload(
705                        Bytes::copy_from_slice(data),
706                        2,
707                        4,
708                        page
709                    )
710                    .is_err()
711                );
712            }
713            assert!(
714                normalize_fixed_len_byte_array_payload(Bytes::from_static(b"x"), 0, 4, page)
715                    .is_err()
716            );
717            assert!(
718                normalize_fixed_len_byte_array_payload(Bytes::new(), 1, usize::MAX, page).is_err()
719            );
720            let err = normalize_fixed_len_byte_array_payload(Bytes::new(), usize::MAX, 2, page)
721                .unwrap_err()
722                .to_string();
723            assert!(err.contains("payload size overflow"), "{err}");
724            assert!(err.contains(page), "{err}");
725        }
726    }
727
728    #[test]
729    fn fixed_len_other_encodings_unchanged() {
730        // No compatibility interpretation applies to other encodings.
731        for encoding in [
732            Encoding::DELTA_BYTE_ARRAY,
733            Encoding::BYTE_STREAM_SPLIT,
734            Encoding::RLE_DICTIONARY,
735        ] {
736            let data = Bytes::from_static(b"\x04\0\0\0abcd");
737            let (actual_encoding, actual) =
738                normalize_fixed_len_byte_array_data(data.clone(), 1, 4, encoding).unwrap();
739            assert_eq!(actual_encoding, encoding);
740            assert_eq!(actual.as_ptr(), data.as_ptr());
741            assert_eq!(actual, data);
742        }
743    }
744
745    #[test]
746    #[expect(deprecated, reason = "Cover legacy BIT_PACKED definition levels")]
747    fn test_skip_def_levels() {
748        use crate::util::bit_util::BitWriter;
749
750        // A multiple of eight avoids ambiguous padding in the final packed run.
751        let num_levels = 2056;
752        for max_level in [1, 2, 3, 7, 255, 32767] {
753            let bit_width = num_required_bits(max_level as u64);
754            for levels in [
755                vec![0; num_levels],
756                vec![max_level; num_levels],
757                (0..num_levels)
758                    .map(|i| (i % (max_level as usize + 1)) as i16)
759                    .collect(),
760            ] {
761                for encoding in [Encoding::RLE, Encoding::BIT_PACKED] {
762                    let data = match encoding {
763                        Encoding::RLE => {
764                            let mut encoder = RleEncoder::new(bit_width, 1024);
765                            for &level in &levels {
766                                encoder.put(level as u64);
767                            }
768                            Bytes::from(encoder.consume())
769                        }
770                        Encoding::BIT_PACKED => {
771                            let mut encoder = BitWriter::new(num_levels);
772                            for &level in &levels {
773                                encoder.put_value(level as u64, bit_width as usize);
774                            }
775                            Bytes::from(encoder.consume())
776                        }
777                        _ => unreachable!(),
778                    };
779                    for requested in [
780                        0,
781                        1,
782                        63,
783                        64,
784                        65,
785                        1023,
786                        1024,
787                        1025,
788                        num_levels,
789                        num_levels + 17,
790                        usize::MAX,
791                    ] {
792                        let mut decoder = DefinitionLevelDecoderImpl::new(max_level);
793                        decoder.set_data(encoding, data.clone()).unwrap();
794                        let expected_levels = requested.min(num_levels);
795                        let expected_values = levels[..expected_levels]
796                            .iter()
797                            .filter(|&&level| level == max_level)
798                            .count();
799                        assert_eq!(
800                            decoder.skip_def_levels(requested).unwrap(),
801                            (expected_values, expected_levels),
802                            "{encoding}, max_level={max_level}, requested={requested}"
803                        );
804
805                        let mut remaining = vec![];
806                        let expected_remaining = &levels[expected_levels..];
807                        assert_eq!(
808                            decoder
809                                .read_def_levels(&mut remaining, expected_remaining.len())
810                                .unwrap(),
811                            (
812                                expected_remaining
813                                    .iter()
814                                    .filter(|&&level| level == max_level)
815                                    .count(),
816                                expected_remaining.len(),
817                            )
818                        );
819                        assert_eq!(remaining, expected_remaining);
820                        assert_eq!(decoder.skip_def_levels(1).unwrap(), (0, 0));
821                    }
822                }
823            }
824        }
825    }
826
827    #[test]
828    fn test_skip_padding() {
829        let mut encoder = RleEncoder::new(1, 1024);
830        encoder.put(0);
831        (0..3).for_each(|_| encoder.put(1));
832        let data = Bytes::from(encoder.consume());
833
834        let mut decoder = RepetitionLevelDecoderImpl::new(1);
835        decoder.set_data(Encoding::RLE, data.clone()).unwrap();
836        let (_, levels) = decoder.skip_rep_levels(100, 4).unwrap();
837        assert_eq!(levels, 4);
838
839        // The length of the final bit packed run is ambiguous, so without the correct
840        // levels limit, it will decode zero padding
841        let mut decoder = RepetitionLevelDecoderImpl::new(1);
842        decoder.set_data(Encoding::RLE, data).unwrap();
843        let (_, levels) = decoder.skip_rep_levels(100, 6).unwrap();
844        assert_eq!(levels, 6);
845    }
846
847    #[test]
848    #[cfg_attr(miri, ignore)] // Takes too long
849    fn test_count_levels_eq() {
850        let chunk = u16::MAX as usize;
851        for len in [0, 1, chunk, chunk + 1, 3 * chunk + 7] {
852            assert_eq!(count_levels_eq(&vec![2; len], 2), len);
853
854            let levels: Vec<i16> = (0..len).map(|i| (i % 3) as i16).collect();
855            let expected = levels.iter().filter(|l| **l == 1).count();
856            assert_eq!(count_levels_eq(&levels, 1), expected);
857        }
858    }
859
860    #[test]
861    #[cfg_attr(miri, ignore)] // Takes too long
862    fn test_skip_rep_levels() {
863        for _ in 0..10 {
864            let mut rng = rng();
865            let total_len = 10000_usize;
866            // Records of random lengths, mostly short in some iterations and
867            // mostly long in others
868            let new_record = rng.random_range(0.01..0.5);
869            let mut encoded: Vec<i16> = (0..total_len)
870                .map(|_| {
871                    if rng.random_bool(new_record) {
872                        0
873                    } else {
874                        rng.random_range(1..5)
875                    }
876                })
877                .collect();
878            encoded[0] = 0;
879            let mut encoder = RleEncoder::new(3, 1024);
880            for v in &encoded {
881                encoder.put(*v as _)
882            }
883            let data = Bytes::from(encoder.consume());
884
885            let mut decoder = RepetitionLevelDecoderImpl::new(5);
886            decoder.set_data(Encoding::RLE, data).unwrap();
887
888            let total_records = encoded.iter().filter(|x| **x == 0).count();
889            let mut remaining_records = total_records;
890            let mut remaining_levels = encoded.len();
891            loop {
892                let skip = rng.random_bool(0.5);
893                // Mix reads of a few records with reads of many records
894                let max_records = if rng.random_bool(0.5) { 5 } else { 500 };
895                let records = rng.random_range(1..=remaining_records.min(max_records));
896                let (records_read, levels_read) = if skip {
897                    decoder.skip_rep_levels(records, remaining_levels).unwrap()
898                } else {
899                    let mut decoded = Vec::new();
900                    let (records_read, levels_read) = decoder
901                        .read_rep_levels(&mut decoded, records, remaining_levels)
902                        .unwrap();
903
904                    assert_eq!(
905                        decoded,
906                        encoded[encoded.len() - remaining_levels..][..levels_read]
907                    );
908                    (records_read, levels_read)
909                };
910
911                remaining_levels = remaining_levels.checked_sub(levels_read).unwrap();
912                if remaining_levels == 0 {
913                    assert_eq!(records_read + 1, records);
914                    assert_eq!(records, remaining_records);
915                    break;
916                }
917                assert_eq!(records_read, records);
918                remaining_records -= records;
919                assert_ne!(remaining_records, 0);
920            }
921        }
922    }
923}