1use crate::column::chunker::CdcChunk;
31use crate::column::writer::LevelDataRef;
32use crate::errors::{ParquetError, Result};
33use arrow_array::cast::AsArray;
34use arrow_array::types::RunEndIndexType;
35use arrow_array::{Array, ArrayRef, Int32Array, OffsetSizeTrait, RunArray, downcast_run_array};
36use arrow_buffer::bit_iterator::BitIndexIterator;
37use arrow_buffer::{NullBuffer, OffsetBuffer, ScalarBuffer};
38use arrow_schema::{DataType, Field};
39use arrow_select::take::take;
40use std::ops::Range;
41use std::sync::Arc;
42
43fn expand_ree_array(array: &ArrayRef) -> Result<ArrayRef> {
48 downcast_run_array!(
49 array => expand_typed_ree(array),
50 _ => unreachable!("expand_ree_array called on non-REE array"),
51 )
52}
53
54fn expand_typed_ree<R: RunEndIndexType>(run_array: &RunArray<R>) -> Result<ArrayRef> {
55 let run_ends = run_array.run_ends();
56 let values = run_array.values();
57 let len = run_array.len();
58 let indices: Int32Array = (0..len)
59 .map(|i| run_ends.get_physical_index(i) as i32)
60 .collect();
61 take(values.as_ref(), &indices, None)
62 .map_err(|e| arrow_err!("Failed to expand REE array: {}", e))
63}
64
65pub(crate) fn calculate_array_levels(array: &ArrayRef, field: &Field) -> Result<Vec<ArrayLevels>> {
68 let mut builder = LevelInfoBuilder::try_new(field, Default::default(), array)?;
69 builder.write(0..array.len());
70 Ok(builder.finish())
71}
72
73fn is_leaf(data_type: &DataType) -> bool {
76 matches!(
77 data_type,
78 DataType::Null
79 | DataType::Boolean
80 | DataType::Int8
81 | DataType::Int16
82 | DataType::Int32
83 | DataType::Int64
84 | DataType::UInt8
85 | DataType::UInt16
86 | DataType::UInt32
87 | DataType::UInt64
88 | DataType::Float16
89 | DataType::Float32
90 | DataType::Float64
91 | DataType::Utf8
92 | DataType::Utf8View
93 | DataType::LargeUtf8
94 | DataType::Timestamp(_, _)
95 | DataType::Date32
96 | DataType::Date64
97 | DataType::Time32(_)
98 | DataType::Time64(_)
99 | DataType::Duration(_)
100 | DataType::Interval(_)
101 | DataType::Binary
102 | DataType::LargeBinary
103 | DataType::BinaryView
104 | DataType::Decimal32(_, _)
105 | DataType::Decimal64(_, _)
106 | DataType::Decimal128(_, _)
107 | DataType::Decimal256(_, _)
108 | DataType::FixedSizeBinary(_)
109 )
110}
111
112#[derive(Debug, Default, Clone, Copy)]
114struct LevelContext {
115 rep_level: i16,
117 def_level: i16,
119}
120
121#[derive(Debug)]
123enum LevelInfoBuilder {
124 Required(Box<LevelInfoBuilder>, NullBuffer, String),
126 Primitive(ArrayLevels),
128 List(
130 Box<LevelInfoBuilder>, LevelContext, OffsetBuffer<i32>, Option<NullBuffer>, bool, ),
136 LargeList(
138 Box<LevelInfoBuilder>, LevelContext, OffsetBuffer<i64>, Option<NullBuffer>, bool, ),
144 FixedSizeList(
146 Box<LevelInfoBuilder>, LevelContext, usize, Option<NullBuffer>, ),
151 ListView(
153 Box<LevelInfoBuilder>, LevelContext, ScalarBuffer<i32>, ScalarBuffer<i32>, Option<NullBuffer>, ),
159 LargeListView(
161 Box<LevelInfoBuilder>, LevelContext, ScalarBuffer<i64>, ScalarBuffer<i64>, Option<NullBuffer>, ),
167 Struct(Vec<LevelInfoBuilder>, LevelContext, Option<NullBuffer>),
169}
170
171const BULK_FILL_MIN_LEN: usize = 64;
177
178fn logical_type(mut data_type: &DataType) -> (&DataType, bool) {
179 let mut nullable = false;
180 loop {
181 match data_type {
182 DataType::Dictionary(_, value) => data_type = value,
183 DataType::RunEndEncoded(_, value) => {
184 nullable |= value.is_nullable();
185 data_type = value.data_type();
186 }
187 _ => return (data_type, nullable),
188 }
189 }
190}
191
192impl LevelInfoBuilder {
193 fn try_new(field: &Field, parent_ctx: LevelContext, array: &ArrayRef) -> Result<Self> {
195 let builder = Self::build(field, parent_ctx, array)?;
196 let (_, nullable) = logical_type(field.data_type());
197 if !field.is_nullable()
198 && !nullable
199 && !matches!(
200 array.data_type(),
201 DataType::RunEndEncoded(_, _) | DataType::Dictionary(_, _)
202 )
203 && let Some(nulls) = array.logical_nulls().filter(|n| n.null_count() != 0)
204 {
205 Ok(Self::Required(
206 Box::new(builder),
207 nulls,
208 field.name().clone(),
209 ))
210 } else if !field.is_nullable()
211 && !nullable
212 && matches!(array.data_type(), DataType::Dictionary(_, value) if is_leaf(value))
213 && let Some(nulls) = array.logical_nulls().filter(|n| n.null_count() != 0)
214 {
215 Ok(Self::Required(
216 Box::new(builder),
217 nulls,
218 field.name().clone(),
219 ))
220 } else {
221 Ok(builder)
222 }
223 }
224
225 fn build(field: &Field, parent_ctx: LevelContext, array: &ArrayRef) -> Result<Self> {
226 let (data_type, nullable) = logical_type(field.data_type());
227 if data_type != field.data_type() {
228 let field = field
229 .clone()
230 .with_data_type(data_type.clone())
231 .with_nullable(field.is_nullable() || nullable);
232 return Self::try_new(&field, parent_ctx, array);
233 }
234 if !Self::types_compatible(field.data_type(), array.data_type()) {
235 return Err(arrow_err!(format!(
236 "Incompatible type. Field '{}' has type {}, array has type {}",
237 field.name(),
238 field.data_type(),
239 array.data_type(),
240 )));
241 }
242
243 let is_nullable = field.is_nullable();
244
245 match array.data_type() {
246 d if is_leaf(d) => {
247 let levels = ArrayLevels::new(parent_ctx, is_nullable, array.clone());
248 Ok(Self::Primitive(levels))
249 }
250 DataType::Dictionary(_, v) if is_leaf(v.as_ref()) => {
251 let levels = ArrayLevels::new(parent_ctx, is_nullable, array.clone());
252 Ok(Self::Primitive(levels))
253 }
254 DataType::RunEndEncoded(_, _) => {
255 let flat = expand_ree_array(array)?;
256 Self::try_new(field, parent_ctx, &flat)
257 }
258 DataType::Dictionary(_, _) => {
259 let dictionary = array.as_any_dictionary();
260 let flat = take(dictionary.values(), dictionary.keys(), None)?;
261 Self::try_new(field, parent_ctx, &flat)
262 }
263 DataType::Struct(_) => {
264 let DataType::Struct(children) = field.data_type() else {
265 unreachable!()
266 };
267 let array = array.as_struct();
268 let def_level = match is_nullable {
269 true => parent_ctx.def_level + 1,
270 false => parent_ctx.def_level,
271 };
272
273 let ctx = LevelContext {
274 rep_level: parent_ctx.rep_level,
275 def_level,
276 };
277
278 let children = children
279 .iter()
280 .zip(array.columns())
281 .map(|(f, a)| Self::try_new(f, ctx, a))
282 .collect::<Result<_>>()?;
283
284 Ok(Self::Struct(children, ctx, array.nulls().cloned()))
285 }
286 DataType::List(_)
287 | DataType::LargeList(_)
288 | DataType::Map(_, _)
289 | DataType::FixedSizeList(_, _)
290 | DataType::ListView(_)
291 | DataType::LargeListView(_) => {
292 let (DataType::List(child)
293 | DataType::LargeList(child)
294 | DataType::Map(child, _)
295 | DataType::FixedSizeList(child, _)
296 | DataType::ListView(child)
297 | DataType::LargeListView(child)) = field.data_type()
298 else {
299 unreachable!()
300 };
301 let def_level = match is_nullable {
302 true => parent_ctx.def_level + 2,
303 false => parent_ctx.def_level + 1,
304 };
305
306 let ctx = LevelContext {
307 rep_level: parent_ctx.rep_level + 1,
308 def_level,
309 };
310
311 Ok(match field.data_type() {
312 DataType::List(_) => {
313 let list = array.as_list();
314 let child = Self::try_new(child.as_ref(), ctx, list.values())?;
315 let is_last = child.child_has_no_nested_rep();
316 let offsets = list.offsets().clone();
317 Self::List(
318 Box::new(child),
319 ctx,
320 offsets,
321 list.nulls().cloned(),
322 is_last,
323 )
324 }
325 DataType::LargeList(_) => {
326 let list = array.as_list();
327 let child = Self::try_new(child.as_ref(), ctx, list.values())?;
328 let is_last = child.child_has_no_nested_rep();
329 let offsets = list.offsets().clone();
330 let nulls = list.nulls().cloned();
331 Self::LargeList(Box::new(child), ctx, offsets, nulls, is_last)
332 }
333 DataType::Map(_, _) => {
334 let map = array.as_map();
335 let entries = Arc::new(map.entries().clone()) as ArrayRef;
336 let child = Self::try_new(child.as_ref(), ctx, &entries)?;
337 let is_last = child.child_has_no_nested_rep();
338 let offsets = map.offsets().clone();
339 Self::List(Box::new(child), ctx, offsets, map.nulls().cloned(), is_last)
340 }
341 DataType::FixedSizeList(_, size) => {
342 let list = array.as_fixed_size_list();
343 let child = Self::try_new(child.as_ref(), ctx, list.values())?;
344 let nulls = list.nulls().cloned();
345 Self::FixedSizeList(Box::new(child), ctx, *size as _, nulls)
346 }
347 DataType::ListView(_) => {
348 let list = array.as_list_view();
349 let child = Self::try_new(child.as_ref(), ctx, list.values())?;
350 let offsets = list.offsets().clone();
351 let sizes = list.sizes().clone();
352 let nulls = list.nulls().cloned();
353 Self::ListView(Box::new(child), ctx, offsets, sizes, nulls)
354 }
355 DataType::LargeListView(_) => {
356 let list = array.as_list_view();
357 let child = Self::try_new(child.as_ref(), ctx, list.values())?;
358 let offsets = list.offsets().clone();
359 let sizes = list.sizes().clone();
360 let nulls = list.nulls().cloned();
361 Self::LargeListView(Box::new(child), ctx, offsets, sizes, nulls)
362 }
363 _ => unreachable!(),
364 })
365 }
366 d => Err(nyi_err!("Datatype {} is not yet supported", d)),
367 }
368 }
369
370 fn finish(self) -> Vec<ArrayLevels> {
373 match self {
374 LevelInfoBuilder::Required(v, _, _) => v.finish(),
375 LevelInfoBuilder::Primitive(v) => vec![v],
376 LevelInfoBuilder::List(v, _, _, _, _)
377 | LevelInfoBuilder::LargeList(v, _, _, _, _)
378 | LevelInfoBuilder::FixedSizeList(v, _, _, _)
379 | LevelInfoBuilder::ListView(v, _, _, _, _)
380 | LevelInfoBuilder::LargeListView(v, _, _, _, _) => v.finish(),
381 LevelInfoBuilder::Struct(v, _, _) => v.into_iter().flat_map(|l| l.finish()).collect(),
382 }
383 }
384
385 fn write(&mut self, range: Range<usize>) {
387 match self {
388 LevelInfoBuilder::Required(child, nulls, name) => {
389 if let Some(index) = range.clone().find(|&index| nulls.is_null(index)) {
390 let message =
391 format!("Found null at index {index} for required field '{name}'");
392 child.visit_leaves(|leaf| {
393 if leaf.validation_error.is_none() {
394 leaf.validation_error = Some(message.clone());
395 }
396 });
397 }
398 child.write(range);
401 }
402 LevelInfoBuilder::Primitive(info) => Self::write_leaf(info, range),
403 LevelInfoBuilder::List(child, ctx, offsets, nulls, is_last) => {
404 Self::write_list(child, ctx, offsets, nulls.as_ref(), range, *is_last)
405 }
406 LevelInfoBuilder::LargeList(child, ctx, offsets, nulls, is_last) => {
407 Self::write_list(child, ctx, offsets, nulls.as_ref(), range, *is_last)
408 }
409 LevelInfoBuilder::FixedSizeList(child, ctx, size, nulls) => {
410 Self::write_fixed_size_list(child, ctx, *size, nulls.as_ref(), range)
411 }
412 LevelInfoBuilder::ListView(child, ctx, offsets, sizes, nulls) => {
413 Self::write_list_view(child, ctx, offsets, sizes, nulls.as_ref(), range)
414 }
415 LevelInfoBuilder::LargeListView(child, ctx, offsets, sizes, nulls) => {
416 Self::write_list_view(child, ctx, offsets, sizes, nulls.as_ref(), range)
417 }
418 LevelInfoBuilder::Struct(children, ctx, nulls) => {
419 Self::write_struct(children, ctx, nulls.as_ref(), range)
420 }
421 }
422 }
423
424 fn child_has_no_nested_rep(&self) -> bool {
428 match self {
429 LevelInfoBuilder::Required(child, _, _) => child.child_has_no_nested_rep(),
430 LevelInfoBuilder::Primitive(_) => true,
431 LevelInfoBuilder::Struct(children, _, _) => {
432 children.iter().all(|c| c.child_has_no_nested_rep())
433 }
434 _ => false,
435 }
436 }
437
438 fn write_list<O: OffsetSizeTrait>(
442 child: &mut LevelInfoBuilder,
443 ctx: &LevelContext,
444 offsets: &[O],
445 nulls: Option<&NullBuffer>,
446 range: Range<usize>,
447 is_last_level: bool,
448 ) {
449 if nulls.is_some_and(|nulls| nulls.null_count() == nulls.len()) {
451 let count = range.end - range.start;
452 child.visit_leaves(|leaf| {
453 leaf.extend_uniform_levels(ctx.def_level - 2, ctx.rep_level - 1, count);
454 });
455 return;
456 }
457
458 if is_last_level {
461 Self::write_list_direct(child, ctx, offsets, nulls, range);
462 } else {
463 Self::write_list_scan(child, ctx, offsets, nulls, range);
464 }
465 }
466
467 fn write_list_direct<O: OffsetSizeTrait>(
471 child: &mut LevelInfoBuilder,
472 ctx: &LevelContext,
473 offsets: &[O],
474 nulls: Option<&NullBuffer>,
475 range: Range<usize>,
476 ) {
477 let list_start_rep = ctx.rep_level - 1;
478
479 let emit_non_empty_run = |child: &mut LevelInfoBuilder, run_offsets: &[O]| {
480 debug_assert!(run_offsets.len() >= 2);
481 let values_start = run_offsets[0].as_usize();
482 let values_end = run_offsets[run_offsets.len() - 1].as_usize();
483 debug_assert!(values_end > values_start);
484
485 child.write(values_start..values_end);
486
487 child.visit_leaves(|leaf| {
492 debug_assert_eq!(leaf.max_rep_level, ctx.rep_level);
493 let rep_levels = leaf.rep_levels.materialize_mut().unwrap();
494 let batch_len = values_end - values_start;
495 let batch_base = rep_levels.len() - batch_len;
496 for slot_offset in run_offsets.iter().take(run_offsets.len() - 1) {
497 let pos = batch_base + (slot_offset.as_usize() - values_start);
498 rep_levels[pos] = list_start_rep;
499 }
500 });
501 };
502
503 Self::write_list_impl(child, ctx, offsets, nulls, range, emit_non_empty_run);
504 }
505
506 fn write_list_scan<O: OffsetSizeTrait>(
513 child: &mut LevelInfoBuilder,
514 ctx: &LevelContext,
515 offsets: &[O],
516 nulls: Option<&NullBuffer>,
517 range: Range<usize>,
518 ) {
519 let list_start_rep = ctx.rep_level - 1;
520
521 let emit_non_empty_run = |child: &mut LevelInfoBuilder, run_offsets: &[O]| {
522 debug_assert!(run_offsets.len() >= 2);
523 let values_start = run_offsets[0].as_usize();
524 let values_end = run_offsets[run_offsets.len() - 1].as_usize();
525 debug_assert!(values_end > values_start);
526
527 child.write(values_start..values_end);
528
529 child.visit_leaves(|leaf| {
530 let rep_levels = leaf.rep_levels.materialize_mut().unwrap();
531
532 if leaf.max_rep_level == ctx.rep_level {
533 let batch_len = values_end - values_start;
537 let batch_base = rep_levels.len() - batch_len;
538 for slot_offset in run_offsets.iter().take(run_offsets.len() - 1) {
539 let pos = batch_base + (slot_offset.as_usize() - values_start);
540 rep_levels[pos] = list_start_rep;
541 }
542 } else {
543 let mut slot_bounds = run_offsets[..run_offsets.len() - 1].iter().rev();
546 let mut next_stamp_at = values_end - slot_bounds.next().unwrap().as_usize();
547 let mut seen = 0usize;
548
549 for rep in rep_levels.iter_mut().rev() {
550 debug_assert!(*rep >= ctx.rep_level);
553 if *rep <= ctx.rep_level {
559 seen += 1;
560 if seen == next_stamp_at {
561 *rep = list_start_rep;
562 match slot_bounds.next() {
563 Some(offset) => next_stamp_at = values_end - offset.as_usize(),
564 None => break,
565 }
566 }
567 }
568 }
569 }
570 });
571 };
572
573 Self::write_list_impl(child, ctx, offsets, nulls, range, emit_non_empty_run);
574 }
575
576 fn write_list_impl<O: OffsetSizeTrait>(
580 child: &mut LevelInfoBuilder,
581 ctx: &LevelContext,
582 offsets: &[O],
583 nulls: Option<&NullBuffer>,
584 range: Range<usize>,
585 mut emit_non_empty_run: impl FnMut(&mut LevelInfoBuilder, &[O]),
586 ) {
587 let null_offset = range.start;
588 let offsets = &offsets[range.start..range.end + 1];
589 let list_start_rep = ctx.rep_level - 1;
590
591 let emit_nulls = |child: &mut LevelInfoBuilder, count: usize| {
592 child.visit_leaves(|leaf| {
593 leaf.append_rep_level_run(list_start_rep, count);
594 leaf.append_def_level_run(ctx.def_level - 2, count);
595 });
596 };
597
598 let emit_empties = |child: &mut LevelInfoBuilder, count: usize| {
599 child.visit_leaves(|leaf| {
600 leaf.append_rep_level_run(list_start_rep, count);
601 leaf.append_def_level_run(ctx.def_level - 1, count);
602 });
603 };
604
605 #[derive(Clone, Copy, PartialEq)]
607 enum SlotKind {
608 Null,
609 Empty,
610 NonEmpty,
611 }
612
613 let num_slots = offsets.len() - 1;
614 if num_slots == 0 {
615 return;
616 }
617
618 macro_rules! classify {
619 ($i:expr, $nulls:expr) => {
620 if !$nulls.is_valid($i + null_offset) {
621 SlotKind::Null
622 } else if offsets[$i] == offsets[$i + 1] {
623 SlotKind::Empty
624 } else {
625 SlotKind::NonEmpty
626 }
627 };
628 }
629
630 macro_rules! flush_run {
631 ($kind:expr, $start:expr, $end:expr) => {
632 match $kind {
633 SlotKind::Null => emit_nulls(child, $end - $start),
634 SlotKind::Empty => emit_empties(child, $end - $start),
635 SlotKind::NonEmpty => emit_non_empty_run(child, &offsets[$start..$end + 1]),
636 }
637 };
638 }
639
640 match nulls {
641 Some(nulls) if nulls.null_count() > 0 => {
644 let mut run_kind = classify!(0, nulls);
645 let mut run_start: usize = 0;
646 for i in 1..num_slots {
647 let kind = classify!(i, nulls);
648 if kind != run_kind {
649 flush_run!(run_kind, run_start, i);
650 run_kind = kind;
651 run_start = i;
652 }
653 }
654 flush_run!(run_kind, run_start, num_slots);
655 }
656 _ => {
657 let mut run_kind = if offsets[0] == offsets[1] {
658 SlotKind::Empty
659 } else {
660 SlotKind::NonEmpty
661 };
662 let mut run_start: usize = 0;
663 for i in 1..num_slots {
664 let kind = if offsets[i] == offsets[i + 1] {
665 SlotKind::Empty
666 } else {
667 SlotKind::NonEmpty
668 };
669 if kind != run_kind {
670 flush_run!(run_kind, run_start, i);
671 run_kind = kind;
672 run_start = i;
673 }
674 }
675 flush_run!(run_kind, run_start, num_slots);
676 }
677 }
678 }
679
680 fn write_list_view<O: OffsetSizeTrait>(
682 child: &mut LevelInfoBuilder,
683 ctx: &LevelContext,
684 offsets: &[O],
685 sizes: &[O],
686 nulls: Option<&NullBuffer>,
687 range: Range<usize>,
688 ) {
689 let offsets = &offsets[range.clone()];
690 let sizes = &sizes[range.clone()];
691
692 let write_non_null_slice =
693 |child: &mut LevelInfoBuilder, start_idx: usize, end_idx: usize| {
694 child.write(start_idx..end_idx);
695 child.visit_leaves(|leaf| {
696 let rep_levels = leaf.rep_levels.materialize_mut().unwrap();
697 let mut rev = rep_levels.iter_mut().rev();
698 let mut remaining = end_idx - start_idx;
699
700 loop {
701 let next = rev.next().unwrap();
702 if *next > ctx.rep_level {
703 continue;
705 }
706
707 remaining -= 1;
708 if remaining == 0 {
709 *next = ctx.rep_level - 1;
710 break;
711 }
712 }
713 })
714 };
715
716 let write_empty_slice = |child: &mut LevelInfoBuilder| {
717 child.visit_leaves(|leaf| {
718 leaf.append_rep_level_run(ctx.rep_level - 1, 1);
719 leaf.append_def_level_run(ctx.def_level - 1, 1);
720 })
721 };
722
723 let write_null_slice = |child: &mut LevelInfoBuilder| {
724 child.visit_leaves(|leaf| {
725 leaf.append_rep_level_run(ctx.rep_level - 1, 1);
726 leaf.append_def_level_run(ctx.def_level - 2, 1);
727 })
728 };
729
730 match nulls {
731 Some(nulls) => {
732 let null_offset = range.start;
733 for (idx, (offset, size)) in offsets.iter().zip(sizes.iter()).enumerate() {
735 let is_valid = nulls.is_valid(idx + null_offset);
736 let start_idx = offset.as_usize();
737 let size = size.as_usize();
738 let end_idx = start_idx + size;
739 if !is_valid {
740 write_null_slice(child)
741 } else if size == 0 {
742 write_empty_slice(child)
743 } else {
744 write_non_null_slice(child, start_idx, end_idx)
745 }
746 }
747 }
748 None => {
749 for (offset, size) in offsets.iter().zip(sizes.iter()) {
750 let start_idx = offset.as_usize();
751 let size = size.as_usize();
752 let end_idx = start_idx + size;
753 if size == 0 {
754 write_empty_slice(child)
755 } else {
756 write_non_null_slice(child, start_idx, end_idx)
757 }
758 }
759 }
760 }
761 }
762
763 fn write_struct(
765 children: &mut [LevelInfoBuilder],
766 ctx: &LevelContext,
767 nulls: Option<&NullBuffer>,
768 range: Range<usize>,
769 ) {
770 let write_null = |children: &mut [LevelInfoBuilder], range: Range<usize>| {
771 let len = range.end - range.start;
772 for child in children {
773 child.visit_leaves(|info| {
774 info.extend_uniform_levels(ctx.def_level - 1, ctx.rep_level, len);
775 })
776 }
777 };
778
779 if nulls.is_some_and(|nulls| nulls.null_count() == nulls.len()) {
781 write_null(children, range);
782 return;
783 }
784
785 let write_non_null = |children: &mut [LevelInfoBuilder], range: Range<usize>| {
786 for child in children {
787 child.write(range.clone())
788 }
789 };
790
791 match nulls {
792 Some(validity) => {
793 let mut last_non_null_idx = None;
794 let mut last_null_idx = None;
795
796 for i in range.clone() {
798 match validity.is_valid(i) {
799 true => {
800 if let Some(last_idx) = last_null_idx.take() {
801 write_null(children, last_idx..i)
802 }
803 last_non_null_idx.get_or_insert(i);
804 }
805 false => {
806 if let Some(last_idx) = last_non_null_idx.take() {
807 write_non_null(children, last_idx..i)
808 }
809 last_null_idx.get_or_insert(i);
810 }
811 }
812 }
813
814 if let Some(last_idx) = last_null_idx.take() {
815 write_null(children, last_idx..range.end)
816 }
817
818 if let Some(last_idx) = last_non_null_idx.take() {
819 write_non_null(children, last_idx..range.end)
820 }
821 }
822 None => write_non_null(children, range),
823 }
824 }
825
826 fn write_fixed_size_list(
828 child: &mut LevelInfoBuilder,
829 ctx: &LevelContext,
830 fixed_size: usize,
831 nulls: Option<&NullBuffer>,
832 range: Range<usize>,
833 ) {
834 if nulls.is_some_and(|nulls| nulls.null_count() == nulls.len()) {
836 let count = range.end - range.start;
837 child.visit_leaves(|leaf| {
838 leaf.extend_uniform_levels(ctx.def_level - 2, ctx.rep_level - 1, count);
839 });
840 return;
841 }
842
843 let write_non_null = |child: &mut LevelInfoBuilder, start_idx: usize, end_idx: usize| {
844 let values_start = start_idx * fixed_size;
845 let values_end = end_idx * fixed_size;
846 child.write(values_start..values_end);
847
848 child.visit_leaves(|leaf| {
849 let rep_levels = leaf.rep_levels.materialize_mut().unwrap();
850
851 let row_indices = (0..fixed_size)
852 .rev()
853 .cycle()
854 .take(values_end - values_start);
855
856 rep_levels
858 .iter_mut()
859 .rev()
860 .filter(|&&mut r| r == ctx.rep_level)
862 .zip(row_indices)
863 .for_each(|(r, idx)| {
864 if idx == 0 {
865 *r = ctx.rep_level - 1;
866 }
867 });
868 })
869 };
870
871 let write_empty = |child: &mut LevelInfoBuilder, start_idx: usize, end_idx: usize| {
873 let len = end_idx - start_idx;
874 child.visit_leaves(|leaf| {
875 leaf.append_rep_level_run(ctx.rep_level - 1, len);
876 leaf.append_def_level_run(ctx.def_level - 1, len);
877 })
878 };
879
880 let write_rows = |child: &mut LevelInfoBuilder, start_idx: usize, end_idx: usize| {
881 if fixed_size > 0 {
882 write_non_null(child, start_idx, end_idx)
883 } else {
884 write_empty(child, start_idx, end_idx)
885 }
886 };
887
888 match nulls {
889 Some(nulls) => {
890 let mut start_idx = None;
891 for idx in range.clone() {
892 if nulls.is_valid(idx) {
893 start_idx.get_or_insert(idx);
895 } else {
896 if let Some(start) = start_idx.take() {
898 write_rows(child, start, idx);
899 }
900 child.visit_leaves(|leaf| {
902 leaf.append_rep_level_run(ctx.rep_level - 1, 1);
903 leaf.append_def_level_run(ctx.def_level - 2, 1);
904 })
905 }
906 }
907 if let Some(start) = start_idx.take() {
909 write_rows(child, start, range.end);
910 }
911 }
912 None => write_rows(child, range.start, range.end),
914 }
915 }
916
917 fn write_leaf(info: &mut ArrayLevels, range: Range<usize>) {
919 let len = range.end - range.start;
920
921 if let Some(nulls) = &info.logical_nulls
923 && !matches!(info.def_levels, LevelData::Absent)
924 && nulls.null_count() == nulls.len()
925 {
926 info.extend_uniform_levels(info.max_def_level - 1, info.max_rep_level, len);
927 return;
928 }
929
930 if matches!(info.def_levels, LevelData::Absent) {
931 info.non_null_indices.extend(range.clone());
932 } else {
933 let max_def_level = info.max_def_level;
934 match &info.logical_nulls {
935 Some(nulls) => {
936 assert!(range.end <= nulls.len());
937 if len >= BULK_FILL_MIN_LEN && nulls.null_count() * 2 >= nulls.len() {
942 let range_nulls = nulls.slice(range.start, len);
943 let valid_in_range = len - range_nulls.null_count();
944 let null_def_level = max_def_level - 1;
945 let buf = info
946 .def_levels
947 .materialize_mut()
948 .expect("definition levels present");
949 let base = buf.len();
950 buf.resize(base + len, null_def_level);
951 for i in range_nulls.valid_indices() {
952 buf[base + i] = max_def_level;
953 }
954 info.non_null_indices.reserve(valid_in_range);
955 info.non_null_indices
956 .extend(range_nulls.valid_indices().map(|i| i + range.start));
957 } else {
958 let bits = nulls.inner();
959 info.def_levels.extend_from_iter(range.clone().map(|i| {
960 let valid = unsafe { bits.value_unchecked(i) };
962 max_def_level - (!valid as i16)
963 }));
964 info.non_null_indices.reserve(len);
965 info.non_null_indices.extend(
966 BitIndexIterator::new(bits.inner(), bits.offset() + range.start, len)
967 .map(|i| i + range.start),
968 );
969 }
970 }
971 None => {
972 info.append_def_level_run(max_def_level, len);
973 info.non_null_indices.reserve(len);
974 info.non_null_indices.extend(range.clone());
975 }
976 }
977 }
978
979 if !matches!(info.rep_levels, LevelData::Absent) {
980 info.append_rep_level_run(info.max_rep_level, len);
981 }
982 }
983
984 fn visit_leaves(&mut self, visit: impl Fn(&mut ArrayLevels) + Copy) {
986 match self {
987 LevelInfoBuilder::Required(child, _, _) => child.visit_leaves(visit),
988 LevelInfoBuilder::Primitive(info) => visit(info),
989 LevelInfoBuilder::List(c, _, _, _, _)
990 | LevelInfoBuilder::LargeList(c, _, _, _, _)
991 | LevelInfoBuilder::FixedSizeList(c, _, _, _)
992 | LevelInfoBuilder::ListView(c, _, _, _, _)
993 | LevelInfoBuilder::LargeListView(c, _, _, _, _) => c.visit_leaves(visit),
994 LevelInfoBuilder::Struct(children, _, _) => {
995 for c in children {
996 c.visit_leaves(visit)
997 }
998 }
999 }
1000 }
1001
1002 fn types_compatible(left: &DataType, right: &DataType) -> bool {
1010 let (left, _) = logical_type(left);
1011 let (right, _) = logical_type(right);
1012 match (left, right) {
1013 (DataType::Struct(left_fields), DataType::Struct(right_fields)) => {
1014 left_fields.len() == right_fields.len()
1015 && left_fields
1016 .iter()
1017 .zip(right_fields)
1018 .all(|(left_field, right_field)| {
1019 Self::types_compatible(left_field.data_type(), right_field.data_type())
1020 })
1021 }
1022 (DataType::List(left_field), DataType::List(right_field))
1023 | (DataType::LargeList(left_field), DataType::LargeList(right_field))
1024 | (DataType::ListView(left_field), DataType::ListView(right_field))
1025 | (DataType::LargeListView(left_field), DataType::LargeListView(right_field)) => {
1026 Self::types_compatible(left_field.data_type(), right_field.data_type())
1027 }
1028 (
1029 DataType::FixedSizeList(left_field, left_len),
1030 DataType::FixedSizeList(right_field, right_len),
1031 ) if left_len == right_len => {
1032 Self::types_compatible(left_field.data_type(), right_field.data_type())
1033 }
1034 (DataType::Map(left_field, left_sorted), DataType::Map(right_field, right_sorted))
1035 if left_sorted == right_sorted =>
1036 {
1037 Self::types_compatible(left_field.data_type(), right_field.data_type())
1038 }
1039 (
1040 DataType::Utf8 | DataType::Utf8View | DataType::LargeUtf8,
1041 DataType::Utf8 | DataType::Utf8View | DataType::LargeUtf8,
1042 )
1043 | (
1044 DataType::Binary | DataType::BinaryView | DataType::LargeBinary,
1045 DataType::Binary | DataType::BinaryView | DataType::LargeBinary,
1046 ) => true,
1047 _ => left.equals_datatype(right),
1048 }
1049 }
1050}
1051
1052#[derive(Debug, Clone)]
1055pub(crate) enum LevelData {
1056 Absent,
1057 Materialized(Vec<i16>),
1058 Uniform { value: i16, count: usize },
1059}
1060
1061impl PartialEq for LevelData {
1064 fn eq(&self, other: &Self) -> bool {
1065 match (self, other) {
1066 (Self::Absent, Self::Absent) => true,
1067 (Self::Materialized(a), Self::Materialized(b)) => a == b,
1068 (Self::Uniform { value: v, count: n }, Self::Materialized(b))
1069 | (Self::Materialized(b), Self::Uniform { value: v, count: n }) => {
1070 b.len() == *n && b.iter().all(|x| x == v)
1071 }
1072 (
1073 Self::Uniform {
1074 value: v1,
1075 count: n1,
1076 },
1077 Self::Uniform {
1078 value: v2,
1079 count: n2,
1080 },
1081 ) => v1 == v2 && n1 == n2,
1082 _ => false,
1083 }
1084 }
1085}
1086
1087impl Eq for LevelData {}
1088
1089impl LevelData {
1090 fn new(present: bool) -> Self {
1091 match present {
1092 true => Self::Materialized(Vec::new()),
1093 false => Self::Absent,
1094 }
1095 }
1096
1097 pub(crate) fn as_ref(&self) -> LevelDataRef<'_> {
1098 match self {
1099 Self::Absent => LevelDataRef::Absent,
1100 Self::Materialized(values) => LevelDataRef::Materialized(values),
1101 Self::Uniform { value, count } => LevelDataRef::Uniform {
1102 value: *value,
1103 count: *count,
1104 },
1105 }
1106 }
1107
1108 pub(crate) fn slice(&self, offset: usize, len: usize) -> Self {
1109 match self {
1110 Self::Absent => Self::Absent,
1111 Self::Materialized(values) => Self::Materialized(values[offset..offset + len].to_vec()),
1112 Self::Uniform { value, .. } => Self::Uniform {
1113 value: *value,
1114 count: len,
1115 },
1116 }
1117 }
1118
1119 fn append_run(&mut self, value: i16, count: usize) {
1120 if count == 0 {
1121 return;
1122 }
1123
1124 match self {
1125 Self::Absent => {}
1128 Self::Materialized(values) if values.is_empty() => {
1131 *self = Self::Uniform { value, count };
1132 }
1133 Self::Materialized(values) => values.extend(std::iter::repeat_n(value, count)),
1135 Self::Uniform {
1138 value: uniform_value,
1139 count: uniform_count,
1140 } if *uniform_value == value => {
1141 *uniform_count += count;
1142 }
1143 Self::Uniform { .. } => {
1146 let values = self.materialize_mut().unwrap();
1147 values.extend(std::iter::repeat_n(value, count));
1148 }
1149 }
1150 }
1151
1152 fn extend_from_iter<I>(&mut self, iter: I)
1153 where
1154 I: IntoIterator<Item = i16>,
1155 {
1156 if let Some(values) = self.materialize_mut() {
1157 values.extend(iter);
1158 }
1159 }
1160
1161 fn materialize_mut(&mut self) -> Option<&mut Vec<i16>> {
1164 match self {
1165 Self::Absent => None,
1166 Self::Materialized(values) => Some(values),
1167 Self::Uniform { value, count } => {
1168 let values = vec![*value; *count];
1169 *self = Self::Materialized(values);
1170 match self {
1171 Self::Materialized(values) => Some(values),
1172 _ => unreachable!(),
1173 }
1174 }
1175 }
1176 }
1177}
1178
1179#[derive(Debug, Clone)]
1180pub(crate) struct ArrayLevels {
1181 def_levels: LevelData,
1185
1186 rep_levels: LevelData,
1190
1191 non_null_indices: Vec<usize>,
1194
1195 max_def_level: i16,
1197
1198 max_rep_level: i16,
1200
1201 array: ArrayRef,
1203
1204 logical_nulls: Option<NullBuffer>,
1206 validation_error: Option<String>,
1207}
1208
1209impl PartialEq for ArrayLevels {
1210 fn eq(&self, other: &Self) -> bool {
1211 self.def_levels == other.def_levels
1212 && self.rep_levels == other.rep_levels
1213 && self.non_null_indices == other.non_null_indices
1214 && self.max_def_level == other.max_def_level
1215 && self.max_rep_level == other.max_rep_level
1216 && self.array.as_ref() == other.array.as_ref()
1217 && self.logical_nulls.as_ref() == other.logical_nulls.as_ref()
1218 }
1219}
1220impl Eq for ArrayLevels {}
1221
1222impl ArrayLevels {
1223 pub(crate) fn validate(&self) -> Result<()> {
1224 match &self.validation_error {
1225 Some(message) => Err(ParquetError::ArrowError(message.clone())),
1226 None => Ok(()),
1227 }
1228 }
1229
1230 fn new(ctx: LevelContext, is_nullable: bool, array: ArrayRef) -> Self {
1231 let max_rep_level = ctx.rep_level;
1232 let max_def_level = match is_nullable {
1233 true => ctx.def_level + 1,
1234 false => ctx.def_level,
1235 };
1236
1237 let logical_nulls = array.logical_nulls();
1238
1239 Self {
1240 def_levels: LevelData::new(max_def_level != 0),
1241 rep_levels: LevelData::new(max_rep_level != 0),
1242 non_null_indices: vec![],
1243 max_def_level,
1244 max_rep_level,
1245 array,
1246 logical_nulls,
1247 validation_error: None,
1248 }
1249 }
1250
1251 pub fn array(&self) -> &ArrayRef {
1252 &self.array
1253 }
1254
1255 pub(crate) fn def_level_data(&self) -> &LevelData {
1256 &self.def_levels
1257 }
1258
1259 pub(crate) fn rep_level_data(&self) -> &LevelData {
1260 &self.rep_levels
1261 }
1262
1263 pub fn non_null_indices(&self) -> &[usize] {
1264 &self.non_null_indices
1265 }
1266
1267 pub(crate) fn slice_for_chunk(&self, chunk: &CdcChunk) -> Self {
1273 let def_levels = self.def_levels.slice(chunk.level_offset, chunk.num_levels);
1274 let rep_levels = self.rep_levels.slice(chunk.level_offset, chunk.num_levels);
1275
1276 let nni = &self.non_null_indices[chunk.value_offset..chunk.value_offset + chunk.num_values];
1278 let start = nni.first().copied().unwrap_or(0);
1283 let end = nni.last().map_or(0, |&i| i + 1);
1284 let non_null_indices = nni.iter().map(|&idx| idx - start).collect();
1286 let array = self.array.slice(start, end - start);
1288 let logical_nulls = array.logical_nulls();
1289
1290 Self {
1291 def_levels,
1292 rep_levels,
1293 non_null_indices,
1294 max_def_level: self.max_def_level,
1295 max_rep_level: self.max_rep_level,
1296 array,
1297 logical_nulls,
1298 validation_error: None,
1299 }
1300 }
1301
1302 fn extend_uniform_levels(&mut self, def_val: i16, rep_val: i16, count: usize) {
1304 self.def_levels.append_run(def_val, count);
1305 self.rep_levels.append_run(rep_val, count);
1306 }
1307
1308 fn append_def_level_run(&mut self, value: i16, count: usize) {
1309 self.def_levels.append_run(value, count);
1310 }
1311
1312 fn append_rep_level_run(&mut self, value: i16, count: usize) {
1313 self.rep_levels.append_run(value, count);
1314 }
1315}
1316
1317#[cfg(test)]
1318mod tests {
1319 use super::*;
1320 use crate::column::chunker::CdcChunk;
1321
1322 use arrow_array::builder::*;
1323 use arrow_array::types::Int32Type;
1324 use arrow_array::*;
1325 use arrow_buffer::{Buffer, ToByteSlice};
1326 use arrow_cast::display::array_value_to_string;
1327 use arrow_data::{ArrayData, ArrayDataBuilder};
1328 use arrow_schema::{Fields, Schema};
1329
1330 #[test]
1331 fn test_calculate_array_levels_twitter_example() {
1332 let leaf_type = Field::new_list_field(DataType::Int32, false);
1336 let inner_type = DataType::List(Arc::new(leaf_type));
1337 let inner_field = Field::new("l2", inner_type.clone(), false);
1338 let outer_type = DataType::List(Arc::new(inner_field));
1339 let outer_field = Field::new("l1", outer_type.clone(), false);
1340
1341 let primitives = Int32Array::from_iter(0..10);
1342
1343 let offsets = Buffer::from_iter([0_i32, 3, 7, 8, 10]);
1345 let inner_list = ArrayDataBuilder::new(inner_type)
1346 .len(4)
1347 .add_buffer(offsets)
1348 .add_child_data(primitives.to_data())
1349 .build()
1350 .unwrap();
1351
1352 let offsets = Buffer::from_iter([0_i32, 2, 4]);
1353 let outer_list = ArrayDataBuilder::new(outer_type)
1354 .len(2)
1355 .add_buffer(offsets)
1356 .add_child_data(inner_list)
1357 .build()
1358 .unwrap();
1359 let outer_list = make_array(outer_list);
1360
1361 let levels = calculate_array_levels(&outer_list, &outer_field).unwrap();
1362 assert_eq!(levels.len(), 1);
1363
1364 let expected = ArrayLevels {
1365 def_levels: LevelData::Materialized(vec![2; 10]),
1366 rep_levels: LevelData::Materialized(vec![0, 2, 2, 1, 2, 2, 2, 0, 1, 2]),
1367 non_null_indices: vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
1368 max_def_level: 2,
1369 max_rep_level: 2,
1370 array: Arc::new(primitives),
1371 logical_nulls: None,
1372 validation_error: None,
1373 };
1374 assert_eq!(&levels[0], &expected);
1375 }
1376
1377 #[test]
1378 fn test_calculate_one_level_1() {
1379 let array = Arc::new(Int32Array::from_iter(0..10)) as ArrayRef;
1381 let field = Field::new_list_field(DataType::Int32, false);
1382
1383 let levels = calculate_array_levels(&array, &field).unwrap();
1384 assert_eq!(levels.len(), 1);
1385
1386 let expected_levels = ArrayLevels {
1387 def_levels: LevelData::Absent,
1388 rep_levels: LevelData::Absent,
1389 non_null_indices: (0..10).collect(),
1390 max_def_level: 0,
1391 max_rep_level: 0,
1392 array,
1393 logical_nulls: None,
1394 validation_error: None,
1395 };
1396 assert_eq!(&levels[0], &expected_levels);
1397 }
1398
1399 #[test]
1400 fn test_calculate_one_level_2() {
1401 let array = Arc::new(Int32Array::from_iter([
1403 Some(0),
1404 None,
1405 Some(0),
1406 Some(0),
1407 None,
1408 ])) as ArrayRef;
1409 let field = Field::new_list_field(DataType::Int32, true);
1410
1411 let levels = calculate_array_levels(&array, &field).unwrap();
1412 assert_eq!(levels.len(), 1);
1413
1414 let logical_nulls = array.logical_nulls();
1415 let expected_levels = ArrayLevels {
1416 def_levels: LevelData::Materialized(vec![1, 0, 1, 1, 0]),
1417 rep_levels: LevelData::Absent,
1418 non_null_indices: vec![0, 2, 3],
1419 max_def_level: 1,
1420 max_rep_level: 0,
1421 array,
1422 logical_nulls,
1423 validation_error: None,
1424 };
1425 assert_eq!(&levels[0], &expected_levels);
1426 }
1427
1428 #[test]
1429 fn test_calculate_array_levels_1() {
1430 let leaf_field = Field::new_list_field(DataType::Int32, false);
1431 let list_type = DataType::List(Arc::new(leaf_field));
1432
1433 let leaf_array = Int32Array::from_iter(0..5);
1437 let offsets = Buffer::from_iter(0_i32..6);
1439 let list = ArrayDataBuilder::new(list_type.clone())
1440 .len(5)
1441 .add_buffer(offsets)
1442 .add_child_data(leaf_array.to_data())
1443 .build()
1444 .unwrap();
1445 let list = make_array(list);
1446
1447 let list_field = Field::new("list", list_type.clone(), false);
1448 let levels = calculate_array_levels(&list, &list_field).unwrap();
1449 assert_eq!(levels.len(), 1);
1450
1451 let expected_levels = ArrayLevels {
1452 def_levels: LevelData::Materialized(vec![1; 5]),
1453 rep_levels: LevelData::Materialized(vec![0; 5]),
1454 non_null_indices: (0..5).collect(),
1455 max_def_level: 1,
1456 max_rep_level: 1,
1457 array: Arc::new(leaf_array),
1458 logical_nulls: None,
1459 validation_error: None,
1460 };
1461 assert_eq!(&levels[0], &expected_levels);
1462
1463 let leaf_array = Int32Array::from_iter([0, 0, 2, 2, 3, 3, 3, 3, 4, 4, 4]);
1472 let offsets = Buffer::from_iter([0_i32, 2, 2, 4, 8, 11]);
1473 let list = ArrayDataBuilder::new(list_type.clone())
1474 .len(5)
1475 .add_buffer(offsets)
1476 .add_child_data(leaf_array.to_data())
1477 .null_bit_buffer(Some(Buffer::from([0b00011101])))
1478 .build()
1479 .unwrap();
1480 let list = make_array(list);
1481
1482 let list_field = Field::new("list", list_type, true);
1483 let levels = calculate_array_levels(&list, &list_field).unwrap();
1484 assert_eq!(levels.len(), 1);
1485
1486 let expected_levels = ArrayLevels {
1487 def_levels: LevelData::Materialized(vec![2, 2, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2]),
1488 rep_levels: LevelData::Materialized(vec![0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1]),
1489 non_null_indices: (0..11).collect(),
1490 max_def_level: 2,
1491 max_rep_level: 1,
1492 array: Arc::new(leaf_array),
1493 logical_nulls: None,
1494 validation_error: None,
1495 };
1496 assert_eq!(&levels[0], &expected_levels);
1497 }
1498
1499 #[test]
1500 fn test_calculate_array_levels_2() {
1501 let leaf = Int32Array::from_iter(0..11);
1515 let leaf_field = Field::new("leaf", DataType::Int32, false);
1516
1517 let list_type = DataType::List(Arc::new(leaf_field));
1518 let list = ArrayData::builder(list_type.clone())
1519 .len(5)
1520 .add_child_data(leaf.to_data())
1521 .add_buffer(Buffer::from_iter([0_i32, 2, 2, 4, 8, 11]))
1522 .build()
1523 .unwrap();
1524
1525 let list = make_array(list);
1526 let list_field = Arc::new(Field::new("list", list_type, true));
1527
1528 let struct_array =
1529 StructArray::from((vec![(list_field, list)], Buffer::from([0b00011010])));
1530 let array = Arc::new(struct_array) as ArrayRef;
1531
1532 let struct_field = Field::new("struct", array.data_type().clone(), true);
1533
1534 let levels = calculate_array_levels(&array, &struct_field).unwrap();
1535 assert_eq!(levels.len(), 1);
1536
1537 let expected_levels = ArrayLevels {
1538 def_levels: LevelData::Materialized(vec![0, 2, 0, 3, 3, 3, 3, 3, 3, 3]),
1539 rep_levels: LevelData::Materialized(vec![0, 0, 0, 0, 1, 1, 1, 0, 1, 1]),
1540 non_null_indices: (4..11).collect(),
1541 max_def_level: 3,
1542 max_rep_level: 1,
1543 array: Arc::new(leaf),
1544 logical_nulls: None,
1545 validation_error: None,
1546 };
1547
1548 assert_eq!(&levels[0], &expected_levels);
1549
1550 let leaf = Int32Array::from_iter(100..122);
1559 let leaf_field = Field::new("leaf", DataType::Int32, true);
1560
1561 let l1_type = DataType::List(Arc::new(leaf_field));
1562 let offsets = Buffer::from_iter([0_i32, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22]);
1563 let l1 = ArrayData::builder(l1_type.clone())
1564 .len(11)
1565 .add_child_data(leaf.to_data())
1566 .add_buffer(offsets)
1567 .build()
1568 .unwrap();
1569
1570 let l1_field = Field::new("l1", l1_type, true);
1571 let l2_type = DataType::List(Arc::new(l1_field));
1572 let l2 = ArrayData::builder(l2_type)
1573 .len(5)
1574 .add_child_data(l1)
1575 .add_buffer(Buffer::from_iter([0, 2, 2, 4, 8, 11]))
1576 .build()
1577 .unwrap();
1578
1579 let l2 = make_array(l2);
1580 let l2_field = Field::new("l2", l2.data_type().clone(), true);
1581
1582 let levels = calculate_array_levels(&l2, &l2_field).unwrap();
1583 assert_eq!(levels.len(), 1);
1584
1585 let expected_levels = ArrayLevels {
1586 def_levels: LevelData::Materialized(vec![
1587 5, 5, 5, 5, 1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1588 ]),
1589 rep_levels: LevelData::Materialized(vec![
1590 0, 2, 1, 2, 0, 0, 2, 1, 2, 0, 2, 1, 2, 1, 2, 1, 2, 0, 2, 1, 2, 1, 2,
1591 ]),
1592 non_null_indices: (0..22).collect(),
1593 max_def_level: 5,
1594 max_rep_level: 2,
1595 array: Arc::new(leaf),
1596 logical_nulls: None,
1597 validation_error: None,
1598 };
1599
1600 assert_eq!(&levels[0], &expected_levels);
1601 }
1602
1603 #[test]
1604 fn test_calculate_array_levels_nested_list() {
1605 let leaf_field = Field::new("leaf", DataType::Int32, false);
1606 let list_type = DataType::List(Arc::new(leaf_field));
1607
1608 let leaf = Int32Array::from_iter([0; 4]);
1616 let list = ArrayData::builder(list_type.clone())
1617 .len(4)
1618 .add_buffer(Buffer::from_iter(0_i32..5))
1619 .add_child_data(leaf.to_data())
1620 .build()
1621 .unwrap();
1622 let list = make_array(list);
1623
1624 let list_field = Field::new("list", list_type.clone(), false);
1625 let levels = calculate_array_levels(&list, &list_field).unwrap();
1626 assert_eq!(levels.len(), 1);
1627
1628 let expected_levels = ArrayLevels {
1629 def_levels: LevelData::Materialized(vec![1; 4]),
1630 rep_levels: LevelData::Materialized(vec![0; 4]),
1631 non_null_indices: (0..4).collect(),
1632 max_def_level: 1,
1633 max_rep_level: 1,
1634 array: Arc::new(leaf),
1635 logical_nulls: None,
1636 validation_error: None,
1637 };
1638 assert_eq!(&levels[0], &expected_levels);
1639
1640 let leaf = Int32Array::from_iter(0..8);
1645 let list = ArrayData::builder(list_type.clone())
1646 .len(4)
1647 .add_buffer(Buffer::from_iter([0_i32, 0, 3, 5, 7]))
1648 .null_bit_buffer(Some(Buffer::from([0b00001110])))
1649 .add_child_data(leaf.to_data())
1650 .build()
1651 .unwrap();
1652 let list = make_array(list);
1653 let list_field = Arc::new(Field::new("list", list_type, true));
1654
1655 let struct_array = StructArray::from(vec![(list_field, list)]);
1656 let array = Arc::new(struct_array) as ArrayRef;
1657
1658 let struct_field = Field::new("struct", array.data_type().clone(), true);
1659 let levels = calculate_array_levels(&array, &struct_field).unwrap();
1660 assert_eq!(levels.len(), 1);
1661
1662 let expected_levels = ArrayLevels {
1663 def_levels: LevelData::Materialized(vec![1, 3, 3, 3, 3, 3, 3, 3]),
1664 rep_levels: LevelData::Materialized(vec![0, 0, 1, 1, 0, 1, 0, 1]),
1665 non_null_indices: (0..7).collect(),
1666 max_def_level: 3,
1667 max_rep_level: 1,
1668 array: Arc::new(leaf),
1669 logical_nulls: None,
1670 validation_error: None,
1671 };
1672 assert_eq!(&levels[0], &expected_levels);
1673
1674 let leaf = Int32Array::from_iter(201..216);
1682 let leaf_field = Field::new("leaf", DataType::Int32, false);
1683 let list_1_type = DataType::List(Arc::new(leaf_field));
1684 let list_1 = ArrayData::builder(list_1_type.clone())
1685 .len(7)
1686 .add_buffer(Buffer::from_iter([0_i32, 1, 3, 3, 6, 10, 10, 15]))
1687 .add_child_data(leaf.to_data())
1688 .build()
1689 .unwrap();
1690
1691 let list_1_field = Field::new("l1", list_1_type, true);
1692 let list_2_type = DataType::List(Arc::new(list_1_field));
1693 let list_2 = ArrayData::builder(list_2_type.clone())
1694 .len(4)
1695 .add_buffer(Buffer::from_iter([0_i32, 0, 3, 5, 7]))
1696 .null_bit_buffer(Some(Buffer::from([0b00001110])))
1697 .add_child_data(list_1)
1698 .build()
1699 .unwrap();
1700
1701 let list_2 = make_array(list_2);
1702 let list_2_field = Arc::new(Field::new("list_2", list_2_type, true));
1703
1704 let struct_array =
1705 StructArray::from((vec![(list_2_field, list_2)], Buffer::from([0b00001111])));
1706 let struct_field = Field::new("struct", struct_array.data_type().clone(), true);
1707
1708 let array = Arc::new(struct_array) as ArrayRef;
1709 let levels = calculate_array_levels(&array, &struct_field).unwrap();
1710 assert_eq!(levels.len(), 1);
1711
1712 let expected_levels = ArrayLevels {
1713 def_levels: LevelData::Materialized(vec![
1714 1, 5, 5, 5, 4, 5, 5, 5, 5, 5, 5, 5, 4, 5, 5, 5, 5, 5,
1715 ]),
1716 rep_levels: LevelData::Materialized(vec![
1717 0, 0, 1, 2, 1, 0, 2, 2, 1, 2, 2, 2, 0, 1, 2, 2, 2, 2,
1718 ]),
1719 non_null_indices: (0..15).collect(),
1720 max_def_level: 5,
1721 max_rep_level: 2,
1722 array: Arc::new(leaf),
1723 logical_nulls: None,
1724 validation_error: None,
1725 };
1726 assert_eq!(&levels[0], &expected_levels);
1727 }
1728
1729 #[test]
1730 fn test_calculate_nested_struct_levels() {
1731 let c = Int32Array::from_iter([Some(1), None, Some(3), None, Some(5), Some(6)]);
1741 let leaf = Arc::new(c) as ArrayRef;
1742 let c_field = Arc::new(Field::new("c", DataType::Int32, true));
1743 let b = StructArray::from(((vec![(c_field, leaf.clone())]), Buffer::from([0b00110111])));
1744
1745 let b_field = Arc::new(Field::new("b", b.data_type().clone(), true));
1746 let a = StructArray::from((
1747 (vec![(b_field, Arc::new(b) as ArrayRef)]),
1748 Buffer::from([0b00101111]),
1749 ));
1750
1751 let a_field = Field::new("a", a.data_type().clone(), true);
1752 let a_array = Arc::new(a) as ArrayRef;
1753
1754 let levels = calculate_array_levels(&a_array, &a_field).unwrap();
1755 assert_eq!(levels.len(), 1);
1756
1757 let logical_nulls = leaf.logical_nulls();
1758 let expected_levels = ArrayLevels {
1759 def_levels: LevelData::Materialized(vec![3, 2, 3, 1, 0, 3]),
1760 rep_levels: LevelData::Absent,
1761 non_null_indices: vec![0, 2, 5],
1762 max_def_level: 3,
1763 max_rep_level: 0,
1764 array: leaf,
1765 logical_nulls,
1766 validation_error: None,
1767 };
1768 assert_eq!(&levels[0], &expected_levels);
1769 }
1770
1771 #[test]
1772 fn list_single_column() {
1773 let a_values = Int32Array::from(vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
1776 let a_value_offsets = arrow::buffer::Buffer::from_iter([0_i32, 1, 3, 3, 6, 10]);
1777 let a_list_type = DataType::List(Arc::new(Field::new_list_field(DataType::Int32, true)));
1778 let a_list_data = ArrayData::builder(a_list_type.clone())
1779 .len(5)
1780 .add_buffer(a_value_offsets)
1781 .null_bit_buffer(Some(Buffer::from([0b00011011])))
1782 .add_child_data(a_values.to_data())
1783 .build()
1784 .unwrap();
1785
1786 assert_eq!(a_list_data.null_count(), 1);
1787
1788 let a = ListArray::from(a_list_data);
1789
1790 let item_field = Field::new_list_field(a_list_type, true);
1791 let mut builder = levels(&item_field, a);
1792 builder.write(2..4);
1793 let levels = builder.finish();
1794
1795 assert_eq!(levels.len(), 1);
1796
1797 let list_level = &levels[0];
1798
1799 let expected_level = ArrayLevels {
1800 def_levels: LevelData::Materialized(vec![0, 3, 3, 3]),
1801 rep_levels: LevelData::Materialized(vec![0, 0, 1, 1]),
1802 non_null_indices: vec![3, 4, 5],
1803 max_def_level: 3,
1804 max_rep_level: 1,
1805 array: Arc::new(a_values),
1806 logical_nulls: None,
1807 validation_error: None,
1808 };
1809 assert_eq!(list_level, &expected_level);
1810 }
1811
1812 #[test]
1813 fn mixed_struct_list() {
1814 let struct_field_d = Arc::new(Field::new("d", DataType::Float64, true));
1818 let struct_field_f = Arc::new(Field::new("f", DataType::Float32, true));
1819 let struct_field_g = Arc::new(Field::new(
1820 "g",
1821 DataType::List(Arc::new(Field::new("items", DataType::Int16, false))),
1822 false,
1823 ));
1824 let struct_field_e = Arc::new(Field::new(
1825 "e",
1826 DataType::Struct(vec![struct_field_f.clone(), struct_field_g.clone()].into()),
1827 true,
1828 ));
1829 let schema = Schema::new(vec![
1830 Field::new("a", DataType::Int32, false),
1831 Field::new("b", DataType::Int32, true),
1832 Field::new(
1833 "c",
1834 DataType::Struct(vec![struct_field_d.clone(), struct_field_e.clone()].into()),
1835 true, ),
1837 ]);
1838
1839 let a = Int32Array::from(vec![1, 2, 3, 4, 5]);
1841 let b = Int32Array::from(vec![Some(1), None, None, Some(4), Some(5)]);
1842 let d = Float64Array::from(vec![None, None, None, Some(1.0), None]);
1843 let f = Float32Array::from(vec![Some(0.0), None, Some(333.3), None, Some(5.25)]);
1844
1845 let g_value = Int16Array::from(vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
1846
1847 let g_value_offsets = arrow::buffer::Buffer::from([0, 1, 3, 3, 6, 10].to_byte_slice());
1850
1851 let g_list_data = ArrayData::builder(struct_field_g.data_type().clone())
1853 .len(5)
1854 .add_buffer(g_value_offsets)
1855 .add_child_data(g_value.into_data())
1856 .build()
1857 .unwrap();
1858 let g = ListArray::from(g_list_data);
1859
1860 let e = StructArray::from(vec![
1861 (struct_field_f, Arc::new(f.clone()) as ArrayRef),
1862 (struct_field_g, Arc::new(g) as ArrayRef),
1863 ]);
1864
1865 let c = StructArray::from(vec![
1866 (struct_field_d, Arc::new(d.clone()) as ArrayRef),
1867 (struct_field_e, Arc::new(e) as ArrayRef),
1868 ]);
1869
1870 let batch = RecordBatch::try_new(
1872 Arc::new(schema),
1873 vec![Arc::new(a.clone()), Arc::new(b.clone()), Arc::new(c)],
1874 )
1875 .unwrap();
1876
1877 let mut levels = vec![];
1880 batch
1881 .columns()
1882 .iter()
1883 .zip(batch.schema().fields())
1884 .for_each(|(array, field)| {
1885 let mut array_levels = calculate_array_levels(array, field).unwrap();
1886 levels.append(&mut array_levels);
1887 });
1888 assert_eq!(levels.len(), 5);
1889
1890 let list_level = &levels[0];
1892
1893 let expected_level = ArrayLevels {
1894 def_levels: LevelData::Absent,
1895 rep_levels: LevelData::Absent,
1896 non_null_indices: vec![0, 1, 2, 3, 4],
1897 max_def_level: 0,
1898 max_rep_level: 0,
1899 array: Arc::new(a),
1900 logical_nulls: None,
1901 validation_error: None,
1902 };
1903 assert_eq!(list_level, &expected_level);
1904
1905 let list_level = levels.get(1).unwrap();
1907
1908 let b_logical_nulls = b.logical_nulls();
1909 let expected_level = ArrayLevels {
1910 def_levels: LevelData::Materialized(vec![1, 0, 0, 1, 1]),
1911 rep_levels: LevelData::Absent,
1912 non_null_indices: vec![0, 3, 4],
1913 max_def_level: 1,
1914 max_rep_level: 0,
1915 array: Arc::new(b),
1916 logical_nulls: b_logical_nulls,
1917 validation_error: None,
1918 };
1919 assert_eq!(list_level, &expected_level);
1920
1921 let list_level = levels.get(2).unwrap();
1923
1924 let d_logical_nulls = d.logical_nulls();
1925 let expected_level = ArrayLevels {
1926 def_levels: LevelData::Materialized(vec![1, 1, 1, 2, 1]),
1927 rep_levels: LevelData::Absent,
1928 non_null_indices: vec![3],
1929 max_def_level: 2,
1930 max_rep_level: 0,
1931 array: Arc::new(d),
1932 logical_nulls: d_logical_nulls,
1933 validation_error: None,
1934 };
1935 assert_eq!(list_level, &expected_level);
1936
1937 let list_level = levels.get(3).unwrap();
1939
1940 let f_logical_nulls = f.logical_nulls();
1941 let expected_level = ArrayLevels {
1942 def_levels: LevelData::Materialized(vec![3, 2, 3, 2, 3]),
1943 rep_levels: LevelData::Absent,
1944 non_null_indices: vec![0, 2, 4],
1945 max_def_level: 3,
1946 max_rep_level: 0,
1947 array: Arc::new(f),
1948 logical_nulls: f_logical_nulls,
1949 validation_error: None,
1950 };
1951 assert_eq!(list_level, &expected_level);
1952 }
1953
1954 #[test]
1955 fn test_null_vs_nonnull_struct() {
1956 let offset_field = Arc::new(Field::new("offset", DataType::Int32, true));
1958 let schema = Schema::new(vec![Field::new(
1959 "some_nested_object",
1960 DataType::Struct(vec![offset_field.clone()].into()),
1961 false,
1962 )]);
1963
1964 let offset = Int32Array::from(vec![1, 2, 3, 4, 5]);
1966
1967 let some_nested_object =
1968 StructArray::from(vec![(offset_field, Arc::new(offset) as ArrayRef)]);
1969
1970 let batch =
1972 RecordBatch::try_new(Arc::new(schema), vec![Arc::new(some_nested_object)]).unwrap();
1973
1974 let struct_null_level =
1975 calculate_array_levels(batch.column(0), batch.schema().field(0)).unwrap();
1976
1977 let offset_field = Arc::new(Field::new("offset", DataType::Int32, true));
1980 let schema = Schema::new(vec![Field::new(
1981 "some_nested_object",
1982 DataType::Struct(vec![offset_field.clone()].into()),
1983 true,
1984 )]);
1985
1986 let offset = Int32Array::from(vec![1, 2, 3, 4, 5]);
1988
1989 let some_nested_object =
1990 StructArray::from(vec![(offset_field, Arc::new(offset) as ArrayRef)]);
1991
1992 let batch =
1994 RecordBatch::try_new(Arc::new(schema), vec![Arc::new(some_nested_object)]).unwrap();
1995
1996 let struct_non_null_level =
1997 calculate_array_levels(batch.column(0), batch.schema().field(0)).unwrap();
1998
1999 if struct_non_null_level == struct_null_level {
2001 panic!("Levels should not be equal, to reflect the difference in struct nullness");
2002 }
2003 }
2004
2005 #[test]
2006 fn test_map_array() {
2007 let json_content = r#"
2009 {"stocks":{"long": "$AAA", "short": "$BBB"}}
2010 {"stocks":{"long": "$CCC", "short": null}}
2011 {"stocks":{"hedged": "$YYY", "long": null, "short": "$D"}}
2012 "#;
2013 let entries_struct_type = DataType::Struct(Fields::from(vec![
2014 Field::new(Field::MAP_KEY_FIELD_DEFAULT_NAME, DataType::Utf8, false),
2015 Field::new(Field::MAP_VALUE_FIELD_DEFAULT_NAME, DataType::Utf8, true),
2016 ]));
2017 let stocks_field = Field::new(
2018 "stocks",
2019 DataType::Map(
2020 Arc::new(Field::new(
2021 Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
2022 entries_struct_type,
2023 false,
2024 )),
2025 false,
2026 ),
2027 false,
2029 );
2030 let schema = Arc::new(Schema::new(vec![stocks_field]));
2031 let builder = arrow::json::ReaderBuilder::new(schema).with_batch_size(64);
2032 let mut reader = builder.build(std::io::Cursor::new(json_content)).unwrap();
2033
2034 let batch = reader.next().unwrap().unwrap();
2035
2036 let mut levels = vec![];
2038 batch
2039 .columns()
2040 .iter()
2041 .zip(batch.schema().fields())
2042 .for_each(|(array, field)| {
2043 let mut array_levels = calculate_array_levels(array, field).unwrap();
2044 levels.append(&mut array_levels);
2045 });
2046 assert_eq!(levels.len(), 2);
2047
2048 let map = batch.column(0).as_map();
2049 let map_keys_logical_nulls = map.keys().logical_nulls();
2050
2051 let list_level = &levels[0];
2053
2054 let expected_level = ArrayLevels {
2055 def_levels: LevelData::Materialized(vec![1; 7]),
2056 rep_levels: LevelData::Materialized(vec![0, 1, 0, 1, 0, 1, 1]),
2057 non_null_indices: vec![0, 1, 2, 3, 4, 5, 6],
2058 max_def_level: 1,
2059 max_rep_level: 1,
2060 array: map.keys().clone(),
2061 logical_nulls: map_keys_logical_nulls,
2062 validation_error: None,
2063 };
2064 assert_eq!(list_level, &expected_level);
2065
2066 let list_level = levels.get(1).unwrap();
2068 let map_values_logical_nulls = map.values().logical_nulls();
2069
2070 let expected_level = ArrayLevels {
2071 def_levels: LevelData::Materialized(vec![2, 2, 2, 1, 2, 1, 2]),
2072 rep_levels: LevelData::Materialized(vec![0, 1, 0, 1, 0, 1, 1]),
2073 non_null_indices: vec![0, 1, 2, 4, 6],
2074 max_def_level: 2,
2075 max_rep_level: 1,
2076 array: map.values().clone(),
2077 logical_nulls: map_values_logical_nulls,
2078 validation_error: None,
2079 };
2080 assert_eq!(list_level, &expected_level);
2081 }
2082
2083 #[test]
2084 fn test_list_of_struct() {
2085 let int_field = Field::new("a", DataType::Int32, true);
2087 let fields = Fields::from([Arc::new(int_field)]);
2088 let item_field = Field::new_list_field(DataType::Struct(fields.clone()), true);
2089 let list_field = Field::new("list", DataType::List(Arc::new(item_field)), true);
2090
2091 let int_builder = Int32Builder::with_capacity(10);
2092 let struct_builder = StructBuilder::new(fields, vec![Box::new(int_builder)]);
2093 let mut list_builder = ListBuilder::new(struct_builder);
2094
2095 let values = list_builder.values();
2099 values
2100 .field_builder::<Int32Builder>(0)
2101 .unwrap()
2102 .append_value(1);
2103 values.append(true);
2104 list_builder.append(true);
2105
2106 list_builder.append(true);
2108
2109 list_builder.append(false);
2111
2112 let values = list_builder.values();
2114 values
2115 .field_builder::<Int32Builder>(0)
2116 .unwrap()
2117 .append_null();
2118 values.append(false);
2119 values
2120 .field_builder::<Int32Builder>(0)
2121 .unwrap()
2122 .append_null();
2123 values.append(false);
2124 list_builder.append(true);
2125
2126 let values = list_builder.values();
2128 values
2129 .field_builder::<Int32Builder>(0)
2130 .unwrap()
2131 .append_null();
2132 values.append(true);
2133 list_builder.append(true);
2134
2135 let values = list_builder.values();
2137 values
2138 .field_builder::<Int32Builder>(0)
2139 .unwrap()
2140 .append_value(2);
2141 values.append(true);
2142 list_builder.append(true);
2143
2144 let array = Arc::new(list_builder.finish());
2145
2146 let values = array.values().as_struct().column(0).clone();
2147 let values_len = values.len();
2148 assert_eq!(values_len, 5);
2149
2150 let schema = Arc::new(Schema::new(vec![list_field]));
2151
2152 let rb = RecordBatch::try_new(schema, vec![array]).unwrap();
2153
2154 let levels = calculate_array_levels(rb.column(0), rb.schema().field(0)).unwrap();
2155 let list_level = &levels[0];
2156
2157 let logical_nulls = values.logical_nulls();
2158 let expected_level = ArrayLevels {
2159 def_levels: LevelData::Materialized(vec![4, 1, 0, 2, 2, 3, 4]),
2160 rep_levels: LevelData::Materialized(vec![0, 0, 0, 0, 1, 0, 0]),
2161 non_null_indices: vec![0, 4],
2162 max_def_level: 4,
2163 max_rep_level: 1,
2164 array: values,
2165 logical_nulls,
2166 validation_error: None,
2167 };
2168
2169 assert_eq!(list_level, &expected_level);
2170 }
2171
2172 #[test]
2173 fn test_struct_mask_list() {
2174 let inner = ListArray::from_iter_primitive::<Int32Type, _, _>(vec![
2176 Some(vec![Some(1), Some(2)]),
2177 Some(vec![None]),
2178 Some(vec![]),
2179 Some(vec![Some(3), None]), Some(vec![Some(4), Some(5)]),
2181 None, None,
2183 ]);
2184 let values = inner.values().clone();
2185
2186 assert_eq!(inner.values().len(), 7);
2188
2189 let field = Arc::new(Field::new("list", inner.data_type().clone(), true));
2190 let array = Arc::new(inner) as ArrayRef;
2191 let nulls = Buffer::from([0b01010111]);
2192 let struct_a = StructArray::from((vec![(field, array)], nulls));
2193
2194 let field = Field::new("struct", struct_a.data_type().clone(), true);
2195 let array = Arc::new(struct_a) as ArrayRef;
2196 let levels = calculate_array_levels(&array, &field).unwrap();
2197
2198 assert_eq!(levels.len(), 1);
2199
2200 let logical_nulls = values.logical_nulls();
2201 let expected_level = ArrayLevels {
2202 def_levels: LevelData::Materialized(vec![4, 4, 3, 2, 0, 4, 4, 0, 1]),
2203 rep_levels: LevelData::Materialized(vec![0, 1, 0, 0, 0, 0, 1, 0, 0]),
2204 non_null_indices: vec![0, 1, 5, 6],
2205 max_def_level: 4,
2206 max_rep_level: 1,
2207 array: values,
2208 logical_nulls,
2209 validation_error: None,
2210 };
2211
2212 assert_eq!(&levels[0], &expected_level);
2213 }
2214
2215 #[test]
2216 fn test_list_mask_struct() {
2217 let a1 = ListArray::from_iter_primitive::<Int32Type, _, _>(vec![
2221 Some(vec![None]), Some(vec![]), Some(vec![Some(3), None]),
2224 Some(vec![Some(4), Some(5), None, Some(6)]), None,
2226 None,
2227 ]);
2228 let a1_values = a1.values().clone();
2229 let a1 = Arc::new(a1) as ArrayRef;
2230
2231 let a2 = Arc::new(Int32Array::from_iter(vec![
2232 Some(1), Some(2), None,
2235 Some(4), Some(5),
2237 None,
2238 ])) as ArrayRef;
2239 let a2_values = a2.clone();
2240
2241 let field_a1 = Arc::new(Field::new("list", a1.data_type().clone(), true));
2242 let field_a2 = Arc::new(Field::new("integers", a2.data_type().clone(), true));
2243
2244 let nulls = Buffer::from([0b00110111]);
2245 let struct_a = Arc::new(StructArray::from((
2246 vec![(field_a1, a1), (field_a2, a2)],
2247 nulls,
2248 ))) as ArrayRef;
2249
2250 let offsets = Buffer::from_iter([0_i32, 0, 2, 2, 3, 5, 5]);
2251 let nulls = Buffer::from([0b00111100]);
2252
2253 let list_type = DataType::List(Arc::new(Field::new(
2254 "struct",
2255 struct_a.data_type().clone(),
2256 true,
2257 )));
2258
2259 let data = ArrayDataBuilder::new(list_type.clone())
2260 .len(6)
2261 .null_bit_buffer(Some(nulls))
2262 .add_buffer(offsets)
2263 .add_child_data(struct_a.into_data())
2264 .build()
2265 .unwrap();
2266
2267 let list = make_array(data);
2268 let list_field = Field::new("col", list_type, true);
2269
2270 let expected = vec![
2271 String::new(),
2272 String::new(),
2273 "[]".to_string(),
2274 "[{list: [3, ], integers: }]".to_string(),
2275 "[, {list: , integers: 5}]".to_string(),
2276 "[]".to_string(),
2277 ];
2278
2279 let actual: Vec<_> = (0..6)
2280 .map(|x| array_value_to_string(&list, x).unwrap())
2281 .collect();
2282 assert_eq!(actual, expected);
2283
2284 let levels = calculate_array_levels(&list, &list_field).unwrap();
2285
2286 assert_eq!(levels.len(), 2);
2287
2288 let a1_logical_nulls = a1_values.logical_nulls();
2289 let expected_level = ArrayLevels {
2290 def_levels: LevelData::Materialized(vec![0, 0, 1, 6, 5, 2, 3, 1]),
2291 rep_levels: LevelData::Materialized(vec![0, 0, 0, 0, 2, 0, 1, 0]),
2292 non_null_indices: vec![1],
2293 max_def_level: 6,
2294 max_rep_level: 2,
2295 array: a1_values,
2296 logical_nulls: a1_logical_nulls,
2297 validation_error: None,
2298 };
2299
2300 assert_eq!(&levels[0], &expected_level);
2301
2302 let a2_logical_nulls = a2_values.logical_nulls();
2303 let expected_level = ArrayLevels {
2304 def_levels: LevelData::Materialized(vec![0, 0, 1, 3, 2, 4, 1]),
2305 rep_levels: LevelData::Materialized(vec![0, 0, 0, 0, 0, 1, 0]),
2306 non_null_indices: vec![4],
2307 max_def_level: 4,
2308 max_rep_level: 1,
2309 array: a2_values,
2310 logical_nulls: a2_logical_nulls,
2311 validation_error: None,
2312 };
2313
2314 assert_eq!(&levels[1], &expected_level);
2315 }
2316
2317 #[test]
2318 fn test_fixed_size_list() {
2319 let mut builder = FixedSizeListBuilder::new(Int32Builder::new(), 2);
2321 builder.values().append_slice(&[1, 2]);
2322 builder.append(true);
2323 builder.values().append_slice(&[3, 4]);
2324 builder.append(false);
2325 builder.values().append_slice(&[5, 6]);
2326 builder.append(false);
2327 builder.values().append_slice(&[7, 8]);
2328 builder.append(true);
2329 builder.values().append_slice(&[9, 10]);
2330 builder.append(false);
2331 let a = builder.finish();
2332 let values = a.values().clone();
2333
2334 let item_field = Field::new_list_field(a.data_type().clone(), true);
2335 let mut builder = levels(&item_field, a);
2336 builder.write(1..4);
2337 let levels = builder.finish();
2338
2339 assert_eq!(levels.len(), 1);
2340
2341 let list_level = &levels[0];
2342
2343 let logical_nulls = values.logical_nulls();
2344 let expected_level = ArrayLevels {
2345 def_levels: LevelData::Materialized(vec![0, 0, 3, 3]),
2346 rep_levels: LevelData::Materialized(vec![0, 0, 0, 1]),
2347 non_null_indices: vec![6, 7],
2348 max_def_level: 3,
2349 max_rep_level: 1,
2350 array: values,
2351 logical_nulls,
2352 validation_error: None,
2353 };
2354 assert_eq!(list_level, &expected_level);
2355 }
2356
2357 #[test]
2358 fn test_fixed_size_list_of_struct() {
2359 let field_a = Field::new("a", DataType::Int32, true);
2361 let field_b = Field::new("b", DataType::Int64, false);
2362 let fields = Fields::from([Arc::new(field_a), Arc::new(field_b)]);
2363 let item_field = Field::new_list_field(DataType::Struct(fields.clone()), true);
2364 let list_field = Field::new(
2365 "list",
2366 DataType::FixedSizeList(Arc::new(item_field), 2),
2367 true,
2368 );
2369
2370 let builder_a = Int32Builder::with_capacity(10);
2371 let builder_b = Int64Builder::with_capacity(10);
2372 let struct_builder =
2373 StructBuilder::new(fields, vec![Box::new(builder_a), Box::new(builder_b)]);
2374 let mut list_builder = FixedSizeListBuilder::new(struct_builder, 2);
2375
2376 let values = list_builder.values();
2385 values
2387 .field_builder::<Int32Builder>(0)
2388 .unwrap()
2389 .append_value(1);
2390 values
2391 .field_builder::<Int64Builder>(1)
2392 .unwrap()
2393 .append_value(2);
2394 values.append(true);
2395 values
2397 .field_builder::<Int32Builder>(0)
2398 .unwrap()
2399 .append_null();
2400 values
2401 .field_builder::<Int64Builder>(1)
2402 .unwrap()
2403 .append_value(0);
2404 values.append(false);
2405 list_builder.append(true);
2406
2407 let values = list_builder.values();
2409 values
2411 .field_builder::<Int32Builder>(0)
2412 .unwrap()
2413 .append_null();
2414 values
2415 .field_builder::<Int64Builder>(1)
2416 .unwrap()
2417 .append_value(0);
2418 values.append(false);
2419 values
2421 .field_builder::<Int32Builder>(0)
2422 .unwrap()
2423 .append_null();
2424 values
2425 .field_builder::<Int64Builder>(1)
2426 .unwrap()
2427 .append_value(0);
2428 values.append(false);
2429 list_builder.append(false);
2430
2431 let values = list_builder.values();
2433 values
2435 .field_builder::<Int32Builder>(0)
2436 .unwrap()
2437 .append_null();
2438 values
2439 .field_builder::<Int64Builder>(1)
2440 .unwrap()
2441 .append_value(0);
2442 values.append(false);
2443 values
2445 .field_builder::<Int32Builder>(0)
2446 .unwrap()
2447 .append_null();
2448 values
2449 .field_builder::<Int64Builder>(1)
2450 .unwrap()
2451 .append_value(0);
2452 values.append(false);
2453 list_builder.append(true);
2454
2455 let values = list_builder.values();
2457 values
2459 .field_builder::<Int32Builder>(0)
2460 .unwrap()
2461 .append_null();
2462 values
2463 .field_builder::<Int64Builder>(1)
2464 .unwrap()
2465 .append_value(3);
2466 values.append(true);
2467 values
2469 .field_builder::<Int32Builder>(0)
2470 .unwrap()
2471 .append_value(2);
2472 values
2473 .field_builder::<Int64Builder>(1)
2474 .unwrap()
2475 .append_value(4);
2476 values.append(true);
2477 list_builder.append(true);
2478
2479 let array = Arc::new(list_builder.finish());
2480
2481 assert_eq!(array.values().len(), 8);
2482 assert_eq!(array.len(), 4);
2483
2484 let struct_values = array.values().as_struct();
2485 let values_a = struct_values.column(0).clone();
2486 let values_b = struct_values.column(1).clone();
2487
2488 let schema = Arc::new(Schema::new(vec![list_field]));
2489 let rb = RecordBatch::try_new(schema, vec![array]).unwrap();
2490
2491 let levels = calculate_array_levels(rb.column(0), rb.schema().field(0)).unwrap();
2492 let a_levels = &levels[0];
2493 let b_levels = &levels[1];
2494
2495 let values_a_logical_nulls = values_a.logical_nulls();
2497 let expected_a = ArrayLevels {
2498 def_levels: LevelData::Materialized(vec![4, 2, 0, 2, 2, 3, 4]),
2499 rep_levels: LevelData::Materialized(vec![0, 1, 0, 0, 1, 0, 1]),
2500 non_null_indices: vec![0, 7],
2501 max_def_level: 4,
2502 max_rep_level: 1,
2503 array: values_a,
2504 logical_nulls: values_a_logical_nulls,
2505 validation_error: None,
2506 };
2507 let values_b_logical_nulls = values_b.logical_nulls();
2509 let expected_b = ArrayLevels {
2510 def_levels: LevelData::Materialized(vec![3, 2, 0, 2, 2, 3, 3]),
2511 rep_levels: LevelData::Materialized(vec![0, 1, 0, 0, 1, 0, 1]),
2512 non_null_indices: vec![0, 6, 7],
2513 max_def_level: 3,
2514 max_rep_level: 1,
2515 array: values_b,
2516 logical_nulls: values_b_logical_nulls,
2517 validation_error: None,
2518 };
2519
2520 assert_eq!(a_levels, &expected_a);
2521 assert_eq!(b_levels, &expected_b);
2522 }
2523
2524 #[test]
2525 fn test_fixed_size_list_empty() {
2526 let mut builder = FixedSizeListBuilder::new(Int32Builder::new(), 0);
2527 builder.append(true);
2528 builder.append(false);
2529 builder.append(true);
2530 let array = builder.finish();
2531 let values = array.values().clone();
2532
2533 let item_field = Field::new_list_field(array.data_type().clone(), true);
2534 let mut builder = levels(&item_field, array);
2535 builder.write(0..3);
2536 let levels = builder.finish();
2537
2538 assert_eq!(levels.len(), 1);
2539
2540 let list_level = &levels[0];
2541
2542 let logical_nulls = values.logical_nulls();
2543 let expected_level = ArrayLevels {
2544 def_levels: LevelData::Materialized(vec![1, 0, 1]),
2545 rep_levels: LevelData::Materialized(vec![0, 0, 0]),
2546 non_null_indices: vec![],
2547 max_def_level: 3,
2548 max_rep_level: 1,
2549 array: values,
2550 logical_nulls,
2551 validation_error: None,
2552 };
2553 assert_eq!(list_level, &expected_level);
2554 }
2555
2556 #[test]
2557 fn test_fixed_size_list_of_var_lists() {
2558 let mut builder = FixedSizeListBuilder::new(ListBuilder::new(Int32Builder::new()), 2);
2560 builder.values().append_value([Some(1), None, Some(3)]);
2561 builder.values().append_null();
2562 builder.append(true);
2563 builder.values().append_value([Some(4)]);
2564 builder.values().append_value([]);
2565 builder.append(true);
2566 builder.values().append_value([Some(5), Some(6)]);
2567 builder.values().append_value([None, None]);
2568 builder.append(true);
2569 builder.values().append_null();
2570 builder.values().append_null();
2571 builder.append(false);
2572 let a = builder.finish();
2573 let values = a.values().as_list::<i32>().values().clone();
2574
2575 let item_field = Field::new_list_field(a.data_type().clone(), true);
2576 let mut builder = levels(&item_field, a);
2577 builder.write(0..4);
2578 let levels = builder.finish();
2579
2580 let logical_nulls = values.logical_nulls();
2581 let expected_level = ArrayLevels {
2582 def_levels: LevelData::Materialized(vec![5, 4, 5, 2, 5, 3, 5, 5, 4, 4, 0]),
2583 rep_levels: LevelData::Materialized(vec![0, 2, 2, 1, 0, 1, 0, 2, 1, 2, 0]),
2584 non_null_indices: vec![0, 2, 3, 4, 5],
2585 max_def_level: 5,
2586 max_rep_level: 2,
2587 array: values,
2588 logical_nulls,
2589 validation_error: None,
2590 };
2591
2592 assert_eq!(levels[0], expected_level);
2593 }
2594
2595 #[test]
2596 fn test_null_dictionary_values() {
2597 let values = Int32Array::new(
2598 vec![1, 2, 3, 4].into(),
2599 Some(NullBuffer::from(vec![true, false, true, true])),
2600 );
2601 let keys = Int32Array::new(
2602 vec![1, 54, 2, 0].into(),
2603 Some(NullBuffer::from(vec![true, false, true, true])),
2604 );
2605 let dict = DictionaryArray::new(keys, Arc::new(values));
2607
2608 let item_field = Field::new_list_field(dict.data_type().clone(), true);
2609
2610 let mut builder = levels(&item_field, dict.clone());
2611 builder.write(0..4);
2612 let levels = builder.finish();
2613
2614 let logical_nulls = dict.logical_nulls();
2615 let expected_level = ArrayLevels {
2616 def_levels: LevelData::Materialized(vec![0, 0, 1, 1]),
2617 rep_levels: LevelData::Absent,
2618 non_null_indices: vec![2, 3],
2619 max_def_level: 1,
2620 max_rep_level: 0,
2621 array: Arc::new(dict),
2622 logical_nulls,
2623 validation_error: None,
2624 };
2625 assert_eq!(levels[0], expected_level);
2626 }
2627
2628 #[test]
2629 fn mismatched_types() {
2630 let array = Arc::new(Int32Array::from_iter(0..10)) as ArrayRef;
2631 let field = Field::new_list_field(DataType::Float64, false);
2632
2633 let err = LevelInfoBuilder::try_new(&field, Default::default(), &array)
2634 .unwrap_err()
2635 .to_string();
2636
2637 assert_eq!(
2638 err,
2639 "Arrow: Incompatible type. Field 'item' has type Float64, array has type Int32",
2640 );
2641 }
2642
2643 fn levels<T: Array + 'static>(field: &Field, array: T) -> LevelInfoBuilder {
2644 let v = Arc::new(array) as ArrayRef;
2645 LevelInfoBuilder::try_new(field, Default::default(), &v).unwrap()
2646 }
2647
2648 #[test]
2649 fn test_slice_for_chunk_flat() {
2650 let array: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 3, 4, 5, 6]));
2655 let logical_nulls = array.logical_nulls();
2656 let levels = ArrayLevels {
2657 def_levels: LevelData::Absent,
2658 rep_levels: LevelData::Absent,
2659 non_null_indices: vec![0, 1, 2, 3, 4, 5],
2660 max_def_level: 0,
2661 max_rep_level: 0,
2662 array,
2663 logical_nulls,
2664 validation_error: None,
2665 };
2666 let sliced = levels.slice_for_chunk(&CdcChunk {
2667 level_offset: 0,
2668 num_levels: 0,
2669 value_offset: 2,
2670 num_values: 3,
2671 });
2672 assert!(matches!(sliced.def_levels, LevelData::Absent));
2673 assert!(matches!(sliced.rep_levels, LevelData::Absent));
2674 assert_eq!(sliced.non_null_indices, vec![0, 1, 2]);
2675 assert_eq!(sliced.array.len(), 3);
2676
2677 let array: ArrayRef = Arc::new(Int32Array::from(vec![
2683 Some(1),
2684 None,
2685 Some(3),
2686 None,
2687 Some(5),
2688 Some(6),
2689 ]));
2690 let logical_nulls = array.logical_nulls();
2691 let levels = ArrayLevels {
2692 def_levels: LevelData::Materialized(vec![1, 0, 1, 0, 1, 1]),
2693 rep_levels: LevelData::Absent,
2694 non_null_indices: vec![0, 2, 4, 5],
2695 max_def_level: 1,
2696 max_rep_level: 0,
2697 array,
2698 logical_nulls,
2699 validation_error: None,
2700 };
2701 let sliced = levels.slice_for_chunk(&CdcChunk {
2702 level_offset: 1,
2703 num_levels: 3,
2704 value_offset: 1,
2705 num_values: 1,
2706 });
2707 assert_eq!(sliced.def_levels, LevelData::Materialized(vec![0, 1, 0]));
2708 assert!(matches!(sliced.rep_levels, LevelData::Absent));
2709 assert_eq!(sliced.non_null_indices, vec![0]); assert_eq!(sliced.array.len(), 1);
2711 }
2712
2713 #[test]
2714 fn test_slice_for_chunk_nested_with_nulls() {
2715 let array: ArrayRef = Arc::new(Int32Array::from(vec![
2734 Some(1), None, None, Some(2), None, None, None, None, Some(4), Some(5), ]));
2745 let logical_nulls = array.logical_nulls();
2746 let levels = ArrayLevels {
2747 def_levels: LevelData::Materialized(vec![3, 0, 3, 2, 0, 3, 3]),
2748 rep_levels: LevelData::Materialized(vec![0, 0, 0, 1, 0, 0, 1]),
2749 non_null_indices: vec![0, 3, 8, 9],
2750 max_def_level: 3,
2751 max_rep_level: 1,
2752 array,
2753 logical_nulls,
2754 validation_error: None,
2755 };
2756
2757 let chunk0 = levels.slice_for_chunk(&CdcChunk {
2759 level_offset: 0,
2760 num_levels: 2,
2761 value_offset: 0,
2762 num_values: 1,
2763 });
2764 assert_eq!(chunk0.non_null_indices, vec![0]);
2765 assert_eq!(chunk0.array.len(), 1);
2766
2767 let chunk1 = levels.slice_for_chunk(&CdcChunk {
2769 level_offset: 2,
2770 num_levels: 3,
2771 value_offset: 1,
2772 num_values: 1,
2773 });
2774 assert_eq!(chunk1.non_null_indices, vec![0]);
2775 assert_eq!(chunk1.array.len(), 1);
2776
2777 let chunk2 = levels.slice_for_chunk(&CdcChunk {
2779 level_offset: 5,
2780 num_levels: 2,
2781 value_offset: 2,
2782 num_values: 2,
2783 });
2784 assert_eq!(chunk2.non_null_indices, vec![0, 1]);
2785 assert_eq!(chunk2.array.len(), 2);
2786 }
2787
2788 #[test]
2789 fn test_slice_for_chunk_all_null() {
2790 let array: ArrayRef = Arc::new(Int32Array::from(vec![Some(1), None, None, Some(4)]));
2792 let logical_nulls = array.logical_nulls();
2793 let levels = ArrayLevels {
2794 def_levels: LevelData::Materialized(vec![1, 0, 0, 1]),
2795 rep_levels: LevelData::Absent,
2796 non_null_indices: vec![0, 3],
2797 max_def_level: 1,
2798 max_rep_level: 0,
2799 array,
2800 logical_nulls,
2801 validation_error: None,
2802 };
2803 let sliced = levels.slice_for_chunk(&CdcChunk {
2805 level_offset: 1,
2806 num_levels: 2,
2807 value_offset: 1,
2808 num_values: 0,
2809 });
2810 assert_eq!(sliced.def_levels, LevelData::Materialized(vec![0, 0]));
2811 assert_eq!(sliced.non_null_indices, Vec::<usize>::new());
2812 assert_eq!(sliced.array.len(), 0);
2813 }
2814
2815 #[test]
2816 fn test_all_null_list() {
2817 let item_field = Arc::new(Field::new_list_field(DataType::Int32, true));
2823 let list = ListArray::new_null(item_field, 4);
2824 let values = list.values().clone();
2825 let field = Field::new("list", list.data_type().clone(), true);
2826 let array = Arc::new(list) as ArrayRef;
2827
2828 let levels = calculate_array_levels(&array, &field).unwrap();
2829 assert_eq!(levels.len(), 1);
2830
2831 let logical_nulls = values.logical_nulls();
2832 let expected = ArrayLevels {
2833 def_levels: LevelData::Uniform { value: 0, count: 4 },
2834 rep_levels: LevelData::Uniform { value: 0, count: 4 },
2835 non_null_indices: vec![],
2836 max_def_level: 3,
2837 max_rep_level: 1,
2838 array: values,
2839 logical_nulls,
2840 validation_error: None,
2841 };
2842 assert_eq!(&levels[0], &expected);
2843 }
2844
2845 #[test]
2846 fn test_all_null_fixed_size_list() {
2847 let item_field = Arc::new(Field::new_list_field(DataType::Int32, true));
2853 let list = FixedSizeListArray::new_null(item_field, 2, 3);
2854 let values = list.values().clone();
2855 let field = Field::new("list", list.data_type().clone(), true);
2856 let array = Arc::new(list) as ArrayRef;
2857
2858 let levels = calculate_array_levels(&array, &field).unwrap();
2859 assert_eq!(levels.len(), 1);
2860
2861 let logical_nulls = values.logical_nulls();
2862 let expected = ArrayLevels {
2863 def_levels: LevelData::Uniform { value: 0, count: 3 },
2864 rep_levels: LevelData::Uniform { value: 0, count: 3 },
2865 non_null_indices: vec![],
2866 max_def_level: 3,
2867 max_rep_level: 1,
2868 array: values,
2869 logical_nulls,
2870 validation_error: None,
2871 };
2872 assert_eq!(&levels[0], &expected);
2873 }
2874
2875 #[test]
2876 fn test_all_null_struct() {
2877 let c = Int32Array::from(vec![None::<i32>; 4]);
2884 let leaf = Arc::new(c) as ArrayRef;
2885 let c_field = Arc::new(Field::new("c", DataType::Int32, true));
2886 let a = StructArray::from((vec![(c_field, leaf.clone())], Buffer::from([0b00000000])));
2887 let a_field = Field::new("a", a.data_type().clone(), true);
2888 let a_array = Arc::new(a) as ArrayRef;
2889
2890 let levels = calculate_array_levels(&a_array, &a_field).unwrap();
2891 assert_eq!(levels.len(), 1);
2892
2893 let expected = ArrayLevels {
2894 def_levels: LevelData::Uniform { value: 0, count: 4 },
2895 rep_levels: LevelData::Absent,
2896 non_null_indices: vec![],
2897 max_def_level: 2,
2898 max_rep_level: 0,
2899 array: leaf,
2900 logical_nulls: Some(NullBuffer::new_null(4)),
2901 validation_error: None,
2902 };
2903 assert_eq!(&levels[0], &expected);
2904 }
2905
2906 #[test]
2907 fn test_all_null_nested_struct() {
2908 let c = Int32Array::from(vec![None::<i32>; 3]);
2914 let leaf = Arc::new(c) as ArrayRef;
2915 let c_field = Arc::new(Field::new("c", DataType::Int32, true));
2916 let b = StructArray::from((vec![(c_field, leaf.clone())], Buffer::from([0b00000000])));
2917 let b_field = Arc::new(Field::new("b", b.data_type().clone(), true));
2918 let a = StructArray::from((
2919 vec![(b_field, Arc::new(b) as ArrayRef)],
2920 Buffer::from([0b00000000]),
2921 ));
2922 let a_field = Field::new("a", a.data_type().clone(), true);
2923 let a_array = Arc::new(a) as ArrayRef;
2924
2925 let levels = calculate_array_levels(&a_array, &a_field).unwrap();
2926 assert_eq!(levels.len(), 1);
2927
2928 let expected = ArrayLevels {
2929 def_levels: LevelData::Uniform { value: 0, count: 3 },
2930 rep_levels: LevelData::Absent,
2931 non_null_indices: vec![],
2932 max_def_level: 3,
2933 max_rep_level: 0,
2934 array: leaf,
2935 logical_nulls: Some(NullBuffer::new_null(3)),
2936 validation_error: None,
2937 };
2938 assert_eq!(&levels[0], &expected);
2939 }
2940
2941 #[test]
2942 fn test_all_null_struct_multiple_children() {
2943 let c1 = Arc::new(Int32Array::from(vec![None::<i32>; 2])) as ArrayRef;
2949 let c2 = Arc::new(Int32Array::from(vec![None::<i32>; 2])) as ArrayRef;
2950 let c1_field = Arc::new(Field::new("c1", DataType::Int32, true));
2951 let c2_field = Arc::new(Field::new("c2", DataType::Int32, true));
2952 let a = StructArray::from((
2953 vec![(c1_field, c1.clone()), (c2_field, c2.clone())],
2954 Buffer::from([0b00000000]),
2955 ));
2956 let a_field = Field::new("a", a.data_type().clone(), true);
2957 let a_array = Arc::new(a) as ArrayRef;
2958
2959 let levels = calculate_array_levels(&a_array, &a_field).unwrap();
2960 assert_eq!(levels.len(), 2);
2961
2962 for (i, leaf) in [c1, c2].into_iter().enumerate() {
2963 let expected = ArrayLevels {
2964 def_levels: LevelData::Uniform { value: 0, count: 2 },
2965 rep_levels: LevelData::Absent,
2966 non_null_indices: vec![],
2967 max_def_level: 2,
2968 max_rep_level: 0,
2969 array: leaf,
2970 logical_nulls: Some(NullBuffer::new_null(2)),
2971 validation_error: None,
2972 };
2973 assert_eq!(&levels[i], &expected, "leaf {i} mismatch");
2974 }
2975 }
2976}