1use arrow_array::builder::BooleanBufferBuilder;
6use arrow_buffer::Buffer;
7use arrow_buffer::bit_chunk_iterator::UnalignedBitChunk;
8use arrow_buffer::bit_util::compress;
9use bytes::Bytes;
10
11use crate::arrow::buffer::bit_util::count_set_bits;
12use crate::basic::Encoding;
13use crate::column::reader::decoder::{
14 ColumnLevelDecoder, DefinitionLevelDecoder, DefinitionLevelDecoderImpl,
15};
16use crate::encodings::rle::run_len;
17use crate::errors::{ParquetError, Result};
18use crate::schema::types::ColumnDescPtr;
19
20enum BufferInner {
21 Full {
23 levels: Vec<i16>,
24 nulls: BooleanBufferBuilder,
25 max_level: i16,
26 },
27 Mask { nulls: BooleanBufferBuilder },
33}
34
35pub struct DefinitionLevelBuffer {
36 inner: BufferInner,
37
38 len: usize,
42}
43
44impl DefinitionLevelBuffer {
45 pub fn new(desc: &ColumnDescPtr, null_mask_only: bool) -> Self {
46 let inner = match null_mask_only {
47 true => {
48 assert_eq!(
49 desc.max_def_level(),
50 1,
51 "max definition level must be 1 to only compute null bitmask"
52 );
53
54 assert_eq!(
55 desc.max_rep_level(),
56 0,
57 "max repetition level must be 0 to only compute null bitmask"
58 );
59
60 BufferInner::Mask {
61 nulls: BooleanBufferBuilder::new(0),
62 }
63 }
64 false => BufferInner::Full {
65 levels: Vec::new(),
66 nulls: BooleanBufferBuilder::new(0),
67 max_level: desc.max_def_level(),
68 },
69 };
70
71 Self { inner, len: 0 }
72 }
73
74 pub fn consume_levels(&mut self) -> Option<Vec<i16>> {
76 match &mut self.inner {
77 BufferInner::Full { levels, .. } => Some(std::mem::take(levels)),
78 BufferInner::Mask { .. } => None,
79 }
80 }
81
82 pub fn consume_bitmask(&mut self) -> Option<Buffer> {
84 self.len = 0;
85 let nulls = match &mut self.inner {
86 BufferInner::Full { nulls, .. } => nulls,
87 BufferInner::Mask { nulls } => nulls,
88 };
89
90 let buffer = nulls.finish().into_inner();
92
93 if buffer.is_empty() {
95 return None;
96 }
97
98 Some(buffer)
99 }
100
101 pub fn nulls(&self) -> &BooleanBufferBuilder {
102 match &self.inner {
103 BufferInner::Full { nulls, .. } => nulls,
104 BufferInner::Mask { nulls } => nulls,
105 }
106 }
107
108 pub fn levels(&self) -> Option<&[i16]> {
111 match &self.inner {
112 BufferInner::Full { levels, .. } => Some(levels.as_slice()),
113 BufferInner::Mask { .. } => None,
114 }
115 }
116}
117
118pub(crate) fn build_filtered_validity_bitmap(
131 def_levels: &[i16],
132 rep_filter: Option<(&[i16], i16)>,
133 include_threshold: Option<i16>,
134 value_level: i16,
135 bitmap: &mut BooleanBufferBuilder,
136) -> usize {
137 const CHUNKS: usize = u64::BITS as usize;
138 if include_threshold.is_none() && rep_filter.is_none() {
140 let (chunks, remainder) = def_levels.as_chunks::<CHUNKS>();
141 for chunk in chunks {
142 let mut word: u64 = 0;
143 for (i, &d) in chunk.iter().enumerate() {
144 word |= ((d >= value_level) as u64) << i;
145 }
146 bitmap.append_word(word, u64::BITS as usize);
147 }
148 for &d in remainder {
149 bitmap.append(d >= value_level);
150 }
151 return def_levels.len();
152 }
153
154 let mut item_count: usize = 0;
156 let (chunks, remainder) = def_levels.as_chunks::<CHUNKS>();
157 let remainder_offset = def_levels.len() - remainder.len();
158
159 for (chunk_idx, chunk) in chunks.iter().enumerate() {
160 let base = chunk_idx * u64::BITS as usize;
161 let mut include_mask: u64 = 0;
162 let mut value_mask: u64 = 0;
163 for (i, &d) in chunk.iter().enumerate() {
164 let include = include_threshold.is_none_or(|threshold| threshold <= d)
165 && rep_filter.is_none_or(|(reps, max_rep)| reps[base + i] <= max_rep);
166 include_mask |= (include as u64) << i;
167 value_mask |= ((d >= value_level) as u64) << i;
168 }
169
170 let count = include_mask.count_ones() as usize;
171 let compact = compress(value_mask, include_mask);
172 bitmap.append_word(compact, count);
173 item_count += count;
174 }
175
176 for idx in remainder_offset..def_levels.len() {
177 let d = def_levels[idx];
178 if let Some(threshold) = include_threshold
179 && d < threshold
180 {
181 continue;
182 }
183 if let Some((reps, max_rep)) = rep_filter
184 && reps[idx] > max_rep
185 {
186 continue;
187 }
188 bitmap.append(d >= value_level);
189 item_count += 1;
190 }
191
192 item_count
193}
194
195enum MaybePacked {
196 Packed(PackedDecoder),
197 Fallback(DefinitionLevelDecoderImpl),
198}
199
200pub struct DefinitionLevelBufferDecoder {
201 max_level: i16,
202 decoder: MaybePacked,
203}
204
205impl DefinitionLevelBufferDecoder {
206 pub fn new(max_level: i16, packed: bool) -> Self {
207 let decoder = match packed {
208 true => MaybePacked::Packed(PackedDecoder::new(max_level)),
209 false => MaybePacked::Fallback(DefinitionLevelDecoderImpl::new(max_level)),
210 };
211
212 Self { max_level, decoder }
213 }
214}
215
216impl ColumnLevelDecoder for DefinitionLevelBufferDecoder {
217 type Buffer = DefinitionLevelBuffer;
218
219 fn set_data(&mut self, encoding: Encoding, data: Bytes) -> Result<()> {
220 match &mut self.decoder {
221 MaybePacked::Packed(d) => d.set_data(encoding, data),
222 MaybePacked::Fallback(d) => d.set_data(encoding, data)?,
223 }
224 Ok(())
225 }
226}
227
228impl DefinitionLevelDecoder for DefinitionLevelBufferDecoder {
229 fn read_def_levels(
230 &mut self,
231 writer: &mut Self::Buffer,
232 num_levels: usize,
233 ) -> Result<(usize, usize)> {
234 match (&mut writer.inner, &mut self.decoder) {
235 (
236 BufferInner::Full {
237 levels,
238 nulls,
239 max_level,
240 },
241 MaybePacked::Fallback(decoder),
242 ) => {
243 assert_eq!(self.max_level, *max_level);
244
245 let start = levels.len();
246 let (values_read, levels_read) = decoder.read_def_levels(levels, num_levels)?;
247
248 if values_read == levels_read {
249 nulls.append_n(levels_read, true);
251 } else if values_read == 0 {
252 nulls.append_n(levels_read, false);
254 } else {
255 unsafe {
257 nulls.extend_trusted_len(
258 levels[start..].iter().map(|level| level == max_level),
259 );
260 }
261 }
262
263 Ok((values_read, levels_read))
264 }
265 (BufferInner::Mask { nulls }, MaybePacked::Packed(decoder)) => {
266 assert_eq!(self.max_level, 1);
267
268 if let Some(count) = decoder.try_consume_all_valid(num_levels)? {
272 nulls.append_n(count, true);
273 return Ok((count, count)); }
275
276 let start = nulls.len();
278 let levels_read = decoder.read(nulls, num_levels)?;
279
280 let values_read = count_set_bits(nulls.as_slice(), start..start + levels_read);
281 Ok((values_read, levels_read))
282 }
283 _ => unreachable!("inconsistent null mask"),
284 }
285 }
286
287 fn skip_def_levels(&mut self, num_levels: usize) -> Result<(usize, usize)> {
288 match &mut self.decoder {
289 MaybePacked::Fallback(decoder) => decoder.skip_def_levels(num_levels),
290 MaybePacked::Packed(decoder) => decoder.skip(num_levels),
291 }
292 }
293}
294
295struct PackedDecoder {
310 data: Bytes,
311 data_offset: usize,
312 rle_left: usize,
313 rle_value: bool,
314 packed_count: usize,
315 packed_offset: usize,
316}
317
318impl PackedDecoder {
319 fn next_rle_block(&mut self) -> Result<()> {
320 let indicator_value = self.decode_header()?;
321 let num_values = run_len(indicator_value as u64)? as usize;
322 if indicator_value & 1 == 1 {
323 let packed_bytes = num_values / 8;
324 let remaining = self.data.len().saturating_sub(self.data_offset);
327 if packed_bytes > remaining {
328 return Err(ParquetError::EOF(format!(
329 "unexpected end of file whilst decoding definition levels bit-packed run: expected {packed_bytes} bytes, found {remaining}"
330 )));
331 }
332 self.packed_count = num_values;
333 self.packed_offset = 0;
334 } else {
335 self.rle_left = num_values;
336 let byte = *self.data.as_ref().get(self.data_offset).ok_or_else(|| {
337 ParquetError::EOF(
338 "unexpected end of file whilst decoding definition levels rle value".into(),
339 )
340 })?;
341
342 self.data_offset += 1;
343 self.rle_value = byte != 0;
344 }
345 Ok(())
346 }
347
348 fn decode_header(&mut self) -> Result<i64> {
350 let mut offset = 0;
351 let mut v: i64 = 0;
352 while offset < 10 {
353 let byte = *self
354 .data
355 .as_ref()
356 .get(self.data_offset + offset)
357 .ok_or_else(|| {
358 ParquetError::EOF(
359 "unexpected end of file whilst decoding definition levels rle header"
360 .into(),
361 )
362 })?;
363
364 v |= ((byte & 0x7F) as i64) << (offset * 7);
365 offset += 1;
366 if byte & 0x80 == 0 {
367 self.data_offset += offset;
368 return Ok(v);
369 }
370 }
371 Err(general_err!("too many bytes for VLQ"))
372 }
373}
374
375impl PackedDecoder {
376 fn new(max_level: i16) -> Self {
377 assert_eq!(
378 max_level, 1,
379 "packed definition-level decoding requires max level 1"
380 );
381
382 Self {
383 data: Bytes::from(vec![]),
384 data_offset: 0,
385 rle_left: 0,
386 rle_value: false,
387 packed_count: 0,
388 packed_offset: 0,
389 }
390 }
391
392 fn set_data(&mut self, encoding: Encoding, data: Bytes) {
393 self.rle_left = 0;
394 self.rle_value = false;
395 self.packed_offset = 0;
396 self.packed_count = match encoding {
397 Encoding::RLE => 0,
398 #[expect(deprecated)]
399 Encoding::BIT_PACKED => data.len() * 8,
400 _ => unreachable!("invalid level encoding: {}", encoding),
401 };
402 self.data = data;
403 self.data_offset = 0;
404 }
405
406 fn try_consume_all_valid(&mut self, len: usize) -> Result<Option<usize>> {
415 if self.rle_left == 0 && self.packed_count == self.packed_offset {
417 if self.data_offset < self.data.len() {
418 self.next_rle_block()?;
419 } else {
420 return Ok(None);
422 }
423 }
424
425 if self.rle_left >= len && self.rle_value {
428 self.rle_left -= len;
429 return Ok(Some(len));
430 }
431
432 Ok(None)
435 }
436
437 fn read(&mut self, buffer: &mut BooleanBufferBuilder, len: usize) -> Result<usize> {
438 let mut read = 0;
439 while read != len {
440 if self.rle_left != 0 {
441 let to_read = self.rle_left.min(len - read);
442 buffer.append_n(to_read, self.rle_value);
443 self.rle_left -= to_read;
444 read += to_read;
445 } else if self.packed_count != self.packed_offset {
446 let to_read = (self.packed_count - self.packed_offset).min(len - read);
447 let offset = self.data_offset * 8 + self.packed_offset;
448 buffer.append_packed_range(offset..offset + to_read, self.data.as_ref());
449 self.packed_offset += to_read;
450 read += to_read;
451
452 if self.packed_offset == self.packed_count {
453 self.data_offset += self.packed_count / 8;
454 }
455 } else if self.data_offset == self.data.len() {
456 break;
457 } else {
458 self.next_rle_block()?
459 }
460 }
461 Ok(read)
462 }
463
464 fn skip(&mut self, level_num: usize) -> Result<(usize, usize)> {
468 let mut skipped_value = 0;
469 let mut skipped_level = 0;
470 while skipped_level != level_num {
471 if self.rle_left != 0 {
472 let to_skip = self.rle_left.min(level_num - skipped_level);
473 self.rle_left -= to_skip;
474 skipped_level += to_skip;
475 if self.rle_value {
476 skipped_value += to_skip;
477 }
478 } else if self.packed_count != self.packed_offset {
479 let to_skip =
480 (self.packed_count - self.packed_offset).min(level_num - skipped_level);
481 let offset = self.data_offset * 8 + self.packed_offset;
482 let bit_chunk = UnalignedBitChunk::new(self.data.as_ref(), offset, to_skip);
483 skipped_value += bit_chunk.count_ones();
484 self.packed_offset += to_skip;
485 skipped_level += to_skip;
486 if self.packed_offset == self.packed_count {
487 self.data_offset += self.packed_count / 8;
488 }
489 } else if self.data_offset == self.data.len() {
490 break;
491 } else {
492 self.next_rle_block()?
493 }
494 }
495 Ok((skipped_value, skipped_level))
496 }
497}
498
499#[cfg(test)]
500mod tests {
501 use super::*;
502
503 use crate::encodings::rle::RleEncoder;
504 use crate::util::bit_util::BitWriter;
505 use rand::{RngExt, rng};
506
507 #[test]
508 fn test_build_validity_bitmap_unfiltered_word_chunk() {
509 let def_levels = (0..65)
512 .map(|i| if i % 3 == 0 { 2 } else { 1 })
513 .collect::<Vec<_>>();
514 let mut bitmap = BooleanBufferBuilder::new(0);
515
516 assert_eq!(
517 build_filtered_validity_bitmap(&def_levels, None, None, 2, &mut bitmap),
518 def_levels.len()
519 );
520
521 let bitmap = bitmap.finish();
522 for (idx, def) in def_levels.iter().enumerate() {
523 assert_eq!(bitmap.value(idx), *def >= 2);
524 }
525 }
526
527 #[test]
528 #[should_panic(expected = "packed definition-level decoding requires max level 1")]
529 fn test_packed_decoder_zero_max_level() {
530 PackedDecoder::new(0);
531 }
532
533 #[test]
534 #[should_panic(expected = "packed definition-level decoding requires max level 1")]
535 fn test_packed_decoder_multiple_max_levels() {
536 PackedDecoder::new(2);
537 }
538
539 #[test]
540 #[should_panic(expected = "packed definition-level decoding requires max level 1")]
541 fn test_definition_level_buffer_decoder_invalid_packed_max_level() {
542 DefinitionLevelBufferDecoder::new(2, true);
543 }
544
545 #[test]
546 fn test_definition_level_buffer_decoder_modes() {
547 let packed = DefinitionLevelBufferDecoder::new(1, true);
548 assert!(matches!(packed.decoder, MaybePacked::Packed(_)));
549
550 let fallback = DefinitionLevelBufferDecoder::new(2, false);
551 assert!(matches!(fallback.decoder, MaybePacked::Fallback(_)));
552 }
553
554 #[test]
555 fn test_packed_decoder() {
556 let mut rng = rng();
557 let len: usize = rng.random_range(512..1024);
558
559 let mut expected = BooleanBufferBuilder::new(len);
560 let mut encoder = RleEncoder::new(1, 1024);
561 for _ in 0..len {
562 let bool = rng.random_bool(0.8);
563 encoder.put(bool as u64);
564 expected.append(bool);
565 }
566 assert_eq!(expected.len(), len);
567
568 let encoded = encoder.consume();
569 let mut decoder = PackedDecoder::new(1);
570 decoder.set_data(Encoding::RLE, encoded.into());
571
572 let mut decoded = BooleanBufferBuilder::new(len);
574 loop {
575 let remaining = len - decoded.len();
576 if remaining == 0 {
577 break;
578 }
579
580 let to_read = rng.random_range(1..=remaining);
581 decoder.read(&mut decoded, to_read).unwrap();
582 }
583
584 assert_eq!(decoded.len(), len);
585 assert_eq!(decoded.as_slice(), expected.as_slice());
586 }
587
588 #[test]
589 fn test_packed_decoder_skip() {
590 let mut rng = rng();
591 let len: usize = rng.random_range(512..1024);
592
593 let mut expected = BooleanBufferBuilder::new(len);
594 let mut encoder = RleEncoder::new(1, 1024);
595
596 let mut total_value = 0;
597 for _ in 0..len {
598 let bool = rng.random_bool(0.8);
599 encoder.put(bool as u64);
600 expected.append(bool);
601 if bool {
602 total_value += 1;
603 }
604 }
605 assert_eq!(expected.len(), len);
606
607 let encoded = encoder.consume();
608 let mut decoder = PackedDecoder::new(1);
609 decoder.set_data(Encoding::RLE, encoded.into());
610
611 let mut skip_value = 0;
612 let mut read_value = 0;
613 let mut skip_level = 0;
614 let mut read_level = 0;
615
616 loop {
617 let offset = skip_level + read_level;
618 let remaining_levels = len - offset;
619 if remaining_levels == 0 {
620 break;
621 }
622 let to_read_or_skip_level = rng.random_range(1..=remaining_levels);
623 if rng.random_bool(0.5) {
624 let (skip_val_num, skip_level_num) = decoder.skip(to_read_or_skip_level).unwrap();
625 skip_value += skip_val_num;
626 skip_level += skip_level_num
627 } else {
628 let mut decoded = BooleanBufferBuilder::new(to_read_or_skip_level);
629 let read_level_num = decoder.read(&mut decoded, to_read_or_skip_level).unwrap();
630 read_level += read_level_num;
631 for i in 0..read_level_num {
632 assert!(!decoded.is_empty());
633 let read_bit = decoded.get_bit(i);
635 if read_bit {
636 read_value += 1;
637 }
638 let expect_bit = expected.get_bit(i + offset);
639 assert_eq!(read_bit, expect_bit);
640 }
641 }
642 }
643 assert_eq!(read_level + skip_level, len);
644 assert_eq!(read_value + skip_value, total_value);
645 }
646
647 #[test]
648 fn test_packed_decoder_truncated_run_returns_error() {
649 let mut decoder = PackedDecoder::new(1);
651 decoder.set_data(Encoding::RLE, Bytes::from_static(&[0x7F, 0x55, 0x55, 0x55]));
652
653 let mut decoded = BooleanBufferBuilder::new(504);
654 let result = decoder.read(&mut decoded, 504);
655
656 assert!(matches!(result, Err(ParquetError::EOF(_))));
657 }
658
659 #[test]
660 fn test_packed_decoder_skip_truncated_run_returns_error() {
661 let mut decoder = PackedDecoder::new(1);
663 decoder.set_data(Encoding::RLE, Bytes::from_static(&[0x7F, 0x55, 0x55, 0x55]));
664
665 let result = decoder.skip(504);
666
667 assert!(matches!(result, Err(ParquetError::EOF(_))));
668 }
669
670 #[test]
671 fn test_try_consume_all_valid() {
672 let len = 100;
674 let mut encoder = RleEncoder::new(1, 1024);
675 for _ in 0..len {
676 encoder.put(1); }
678 let encoded = encoder.consume();
679 let mut decoder = PackedDecoder::new(1);
680 decoder.set_data(Encoding::RLE, encoded.into());
681
682 let result = decoder.try_consume_all_valid(len).unwrap();
684 assert_eq!(result, Some(len));
685
686 let mut encoder = RleEncoder::new(1, 1024);
688 for _ in 0..len {
689 encoder.put(0); }
691 let encoded = encoder.consume();
692 let mut decoder = PackedDecoder::new(1);
693 decoder.set_data(Encoding::RLE, encoded.into());
694
695 let result = decoder.try_consume_all_valid(len).unwrap();
697 assert_eq!(result, None);
698
699 let mut encoder = RleEncoder::new(1, 1024);
701 for _ in 0..10 {
702 encoder.put(1); }
704 for _ in 0..10 {
705 encoder.put(0); }
707 let encoded = encoder.consume();
708 let mut decoder = PackedDecoder::new(1);
709 decoder.set_data(Encoding::RLE, encoded.into());
710
711 let result = decoder.try_consume_all_valid(20).unwrap();
714 assert_eq!(result, None);
715
716 decoder.set_data(Encoding::RLE, {
718 let mut encoder = RleEncoder::new(1, 1024);
719 for _ in 0..10 {
720 encoder.put(1);
721 }
722 for _ in 0..10 {
723 encoder.put(0);
724 }
725 encoder.consume().into()
726 });
727
728 let result = decoder.try_consume_all_valid(5).unwrap();
729 assert_eq!(result, Some(5));
730
731 let result = decoder.try_consume_all_valid(5).unwrap();
733 assert_eq!(result, Some(5));
734
735 let result = decoder.try_consume_all_valid(5).unwrap();
737 assert_eq!(result, None);
738 }
739
740 #[test]
741 fn test_packed_decoder_invalid_run_len() {
742 let mut writer = BitWriter::new(16);
743 writer.put_vlq_int(u64::MAX);
744 let mut decoder = PackedDecoder::new(1);
745 decoder.set_data(Encoding::RLE, writer.consume().into());
746
747 let mut decoded = BooleanBufferBuilder::new(8);
748 let err = decoder.read(&mut decoded, 8).unwrap_err();
749 assert_eq!(
750 err.to_string(),
751 "Parquet error: Invalid or corrupted RLE run length 18446744073709551615. Max allowed is 2147483647"
752 );
753 }
754}