Skip to main content

parquet/arrow/arrow_writer/
levels.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5//! Parquet definition and repetition levels
6//!
7//! Contains the algorithm for computing definition and repetition levels.
8//! The algorithm works by tracking the slots of an array that should
9//! ultimately be populated when writing to Parquet.
10//! Parquet achieves nesting through definition levels and repetition levels \[1\].
11//! Definition levels specify how many optional fields in the part for the column
12//! are defined.
13//! Repetition levels specify at what repeated field (list) in the path a column
14//! is defined.
15//!
16//! In a nested data structure such as `a.b.c`, one can see levels as defining
17//! whether a record is defined at `a`, `a.b`, or `a.b.c`.
18//! Optional fields are nullable fields, thus if all 3 fields
19//! are nullable, the maximum definition could be = 3 if there are no lists.
20//!
21//! The algorithm in this module computes the necessary information to enable
22//! the writer to keep track of which columns are at which levels, and to extract
23//! the correct values at the correct slots from Arrow arrays.
24//!
25//! It works by walking a record batch's arrays, keeping track of what values
26//! are non-null, their positions and computing what their levels are.
27//!
28//! \[1\] [parquet-format#nested-encoding](https://github.com/apache/parquet-format#nested-encoding)
29
30use 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
43/// Expands a [`DataType::RunEndEncoded`] array into a flat (logical) array of its values type.
44///
45/// use `arrow_select::take` to materialize the  full-length flat array.
46/// This is intentionally simple (O(n)); efficiency can/should be improved
47fn 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
65/// Performs a depth-first scan of the children of `array`, constructing [`ArrayLevels`]
66/// for each leaf column encountered
67pub(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
73/// Returns true if the DataType can be represented as a primitive parquet column,
74/// i.e. a leaf array with no children
75fn 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/// The definition and repetition level of an array within a potentially nested hierarchy
113#[derive(Debug, Default, Clone, Copy)]
114struct LevelContext {
115    /// The current repetition level
116    rep_level: i16,
117    /// The current definition level
118    def_level: i16,
119}
120
121/// A helper to construct [`ArrayLevels`] from a potentially nested [`Field`]
122#[derive(Debug)]
123enum LevelInfoBuilder {
124    /// Validate required fields only at slots reached during traversal.
125    Required(Box<LevelInfoBuilder>, NullBuffer, String),
126    /// A primitive, leaf array
127    Primitive(ArrayLevels),
128    /// A list array
129    List(
130        Box<LevelInfoBuilder>, // Child Values
131        LevelContext,          // Context
132        OffsetBuffer<i32>,     // Offsets
133        Option<NullBuffer>,    // Nulls
134        bool,                  // is_last_level (child has no nested rep)
135    ),
136    /// A large list array
137    LargeList(
138        Box<LevelInfoBuilder>, // Child Values
139        LevelContext,          // Context
140        OffsetBuffer<i64>,     // Offsets
141        Option<NullBuffer>,    // Nulls
142        bool,                  // is_last_level (child has no nested rep)
143    ),
144    /// A fixed size list array
145    FixedSizeList(
146        Box<LevelInfoBuilder>, // Values
147        LevelContext,          // Context
148        usize,                 // List Size
149        Option<NullBuffer>,    // Nulls
150    ),
151    /// A list view array
152    ListView(
153        Box<LevelInfoBuilder>, // Child Values
154        LevelContext,          // Context
155        ScalarBuffer<i32>,     // Offsets
156        ScalarBuffer<i32>,     // Sizes
157        Option<NullBuffer>,    // Nulls
158    ),
159    /// A large list view array
160    LargeListView(
161        Box<LevelInfoBuilder>, // Child Values
162        LevelContext,          // Context
163        ScalarBuffer<i64>,     // Offsets
164        ScalarBuffer<i64>,     // Sizes
165        Option<NullBuffer>,    // Nulls
166    ),
167    /// A struct array
168    Struct(Vec<LevelInfoBuilder>, LevelContext, Option<NullBuffer>),
169}
170
171/// Minimum sub-range length before the bulk-fill fast path in `write_leaf`
172/// becomes profitable for null-heavy leaf columns. Below this, per-call
173/// slice + popcount overhead regresses list/struct paths that call
174/// `write_leaf` many times with tiny ranges. Picked via threshold sweep;
175/// see <https://github.com/apache/arrow-rs/pull/9967> for the rationale.
176const 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    /// Create a new [`LevelInfoBuilder`] for the given [`Field`] and parent [`LevelContext`]
194    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    /// Finish this [`LevelInfoBuilder`] returning the [`ArrayLevels`] for the leaf columns
371    /// as enumerated by a depth-first search
372    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    /// Given an `array`, write the level data for the elements in `range`
386    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                // Parents still need the child levels to backfill list boundaries;
399                // the recorded error prevents these invalid values from being encoded.
400                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    /// Returns `true` if the child contains no nested repetition levels, meaning
425    /// each child element produces exactly one rep_level entry in the leaf.
426    /// This is true for `Primitive` children and `Struct` trees with no list descendants.
427    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    /// Write `range` elements from ListArray `array`
439    ///
440    /// Note: MapArrays are `ListArray<i32>` under the hood and so are dispatched to this method
441    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        // Fast path: entire list array is null; emit bulk null rep/def levels
450        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        // Dispatch to separate functions so the compiler can optimize each
459        // hot loop independently (function body size affects codegen quality).
460        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    /// Batch write for lists whose child has no nested repetition.
468    ///
469    /// "direct" means writing the child rep levels using offsets without scanning.
470    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            // The first element of each list slot needs rep_level =
488            // list_start_rep to mark a new list boundary. Because there's a 1:1
489            // mapping between child elements and rep_level entries, the position
490            // of each slot's first element is directly computable from offsets.
491            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    /// Batch write for lists whose child has nested repetition.
507    ///
508    /// After batch-writing child elements, scans backward through rep_levels
509    /// counting child-element starts to find and stamp slot boundaries.
510    ///
511    /// Scan backward because we don't know start offset before writing.
512    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                    // This algorithm is the same as write_list_direct.
534                    // Use a separate function because the branch code size would affect codegen
535                    // quality of the hot loop of write_list_direct.
536                    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                    // Backward scan: count child-element starts (rep <= ctx.rep_level)
544                    // and stamp list_start_rep at slot boundaries.
545                    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                        // Asserting rep >= ctx.rep_level to ensure low level depth haven't
551                        // being written.
552                        debug_assert!(*rep >= ctx.rep_level);
553                        // Count element starts by skipping nested reps (rep > ctx.rep_level).
554                        //
555                        // `==` would also work here: the child is written before the
556                        // parent, so no entry within the batch has rep < ctx.rep_level.
557                        // Benchmarks show no difference, so keep the more defensive `<=`.
558                        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    /// Shared run-classification loop for write_list_direct and write_list_scan.
577    /// Monomorphized per `emit_non_empty_run` closure type, giving the compiler
578    /// separate optimization contexts for each backfill strategy.
579    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        // Classify each slot, detect run boundaries, flush on transition.
606        #[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            // A null buffer without any null can skip the per-slot validity
642            // checks and use the null-free classification loop below.
643            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    /// Write `range` elements from ListViewArray `array`
681    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                            // Nested element - ignore
704                            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                // TODO: Faster bitmask iteration (#1757)
734                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    /// Write `range` elements from StructArray `array`
764    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        // Fast path: entire struct array is null; emit bulk null def/rep levels
780        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                // TODO: Faster bitmask iteration (#1757)
797                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    /// Write `range` elements from FixedSizeListArray with child data `values` and null bitmap `nulls`.
827    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        // Fast path: entire fixed-size list array is null
835        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                // Step backward over the child rep levels and mark the start of each list
857                rep_levels
858                    .iter_mut()
859                    .rev()
860                    // Filter out reps from nested children
861                    .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        // If list size is 0, ignore values and just write rep/def levels.
872        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 a run of valid rows if not already inside of one
894                        start_idx.get_or_insert(idx);
895                    } else {
896                        // Write out any pending valid rows
897                        if let Some(start) = start_idx.take() {
898                            write_rows(child, start, idx);
899                        }
900                        // Add null row
901                        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                // Write out any remaining valid rows
908                if let Some(start) = start_idx.take() {
909                    write_rows(child, start, range.end);
910                }
911            }
912            // If all rows are valid then write the whole array
913            None => write_rows(child, range.start, range.end),
914        }
915    }
916
917    /// Write a primitive array, as defined by [`is_leaf`]
918    fn write_leaf(info: &mut ArrayLevels, range: Range<usize>) {
919        let len = range.end - range.start;
920
921        // Fast path: entire leaf array is null
922        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                    // Bulk-fill is profitable only on null-heavy ranges long enough to
938                    // amortize the slice/popcount cost; see `BULK_FILL_MIN_LEN` and the
939                    // PR description for the threshold sweep. The gate uses the cached
940                    // buffer-wide `null_count` (O(1)) to stay cheap on the cold path.
941                    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                            // Safety: range.end was asserted to be in bounds earlier
961                            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    /// Visits all children of this node in depth first order
985    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    /// Determine if the logical types are compatible for constructing [`LevelInfoBuilder`].
1003    ///
1004    /// Resolve dictionary and REE wrappers at each logical node, including nested children.
1005    /// Container variants must match, as must fixed-size list lengths and map sortedness.
1006    /// String and binary leaves may use different offset widths or view layouts. Child field
1007    /// names, metadata, and nullability are ignored here: the writer's target fields determine
1008    /// nullability and the resulting levels.
1009    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/// The data necessary to write a primitive Arrow array to parquet, taking into account
1053/// any non-primitive parents it may have in the arrow representation
1054#[derive(Debug, Clone)]
1055pub(crate) enum LevelData {
1056    Absent,
1057    Materialized(Vec<i16>),
1058    Uniform { value: i16, count: usize },
1059}
1060
1061// Compare logical level contents rather than physical representation, so a
1062// uniform run compares equal to the equivalent materialized buffer.
1063impl 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            // No physical level stream exists for this schema. Higher-level
1126            // traversal may still append implicit levels, so this remains a no-op.
1127            Self::Absent => {}
1128            // Start compact: the first appended run can be represented without
1129            // allocating a level buffer.
1130            Self::Materialized(values) if values.is_empty() => {
1131                *self = Self::Uniform { value, count };
1132            }
1133            // Already materialized, so preserve the buffer representation and append.
1134            Self::Materialized(values) => values.extend(std::iter::repeat_n(value, count)),
1135            // Preserve the compact representation while the appended run has
1136            // the same value.
1137            Self::Uniform {
1138                value: uniform_value,
1139                count: uniform_count,
1140            } if *uniform_value == value => {
1141                *uniform_count += count;
1142            }
1143            // A different value breaks the uniform representation. Materialize
1144            // the existing run, then append the new run to the buffer.
1145            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    /// Convert a uniform run into a materialized buffer if needed, then return
1162    /// the mutable level buffer. Returns `None` when no physical level stream exists.
1163    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    /// Array's definition levels
1182    ///
1183    /// Present if `max_def_level != 0`
1184    def_levels: LevelData,
1185
1186    /// Array's optional repetition levels
1187    ///
1188    /// Present if `max_rep_level != 0`
1189    rep_levels: LevelData,
1190
1191    /// The corresponding array identifying non-null slices of data
1192    /// from the primitive array
1193    non_null_indices: Vec<usize>,
1194
1195    /// The maximum definition level for this leaf column
1196    max_def_level: i16,
1197
1198    /// The maximum repetition for this leaf column
1199    max_rep_level: i16,
1200
1201    /// The arrow array
1202    array: ArrayRef,
1203
1204    /// cached logical nulls of the array.
1205    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    /// Create a sliced view of this `ArrayLevels` for a CDC chunk.
1268    ///
1269    /// The chunk's `value_offset`/`num_values` select the relevant slice of
1270    /// `non_null_indices`. The array is sliced to the range covered by
1271    /// those indices, and they are shifted to be relative to the slice.
1272    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        // Select the non-null indices for this chunk.
1277        let nni = &self.non_null_indices[chunk.value_offset..chunk.value_offset + chunk.num_values];
1278        // Compute the array range spanned by the non-null indices.
1279        // When nni is empty (all-null chunk), start=0, end=0 → zero-length
1280        // array slice; write_batch_internal will process only the def/rep
1281        // levels and write no values.
1282        let start = nni.first().copied().unwrap_or(0);
1283        let end = nni.last().map_or(0, |&i| i + 1);
1284        // Shift indices to be relative to the sliced array.
1285        let non_null_indices = nni.iter().map(|&idx| idx - start).collect();
1286        // Slice the array to the computed range.
1287        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    /// Bulk-emit `count` uniform def/rep levels.
1303    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        // based on the example at https://blog.twitter.com/engineering/en_us/a/2013/dremel-made-simple-with-parquet.html
1333        // [[a, b, c], [d, e, f, g]], [[h], [i,j]]
1334
1335        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        // Cannot use from_iter_primitive as always infers nullable
1344        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        // This test calculates the levels for a non-null primitive array
1380        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        // This test calculates the levels for a nullable primitive array
1402        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        // if all array values are defined (e.g. batch<list<_>>)
1434        // [[0], [1], [2], [3], [4]]
1435
1436        let leaf_array = Int32Array::from_iter(0..5);
1437        // Cannot use from_iter_primitive as always infers nullable
1438        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        // array: [[0, 0], NULL, [2, 2], [3, 3, 3, 3], [4, 4, 4]]
1464        // all values are defined as we do not have nulls on the root (batch)
1465        // repetition:
1466        //   0: 0, 1
1467        //   1: 0
1468        //   2: 0, 1
1469        //   3: 0, 1, 1, 1
1470        //   4: 0, 1, 1
1471        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        // If some values are null
1502        //
1503        // This emulates an array in the form: <struct<list<?>>
1504        // with values:
1505        // - 0: [0, 1], but is null because of the struct
1506        // - 1: []
1507        // - 2: [2, 3], but is null because of the struct
1508        // - 3: [4, 5, 6, 7]
1509        // - 4: [8, 9, 10]
1510        //
1511        // If the first values of a list are null due to a parent, we have to still account for them
1512        // while indexing, because they would affect the way the child is indexed
1513        // i.e. in the above example, we have to know that [0, 1] has to be skipped
1514        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        // nested lists
1551
1552        // 0: [[100, 101], [102, 103]]
1553        // 1: []
1554        // 2: [[104, 105], [106, 107]]
1555        // 3: [[108, 109], [110, 111], [112, 113], [114, 115]]
1556        // 4: [[116, 117], [118, 119], [120, 121]]
1557
1558        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        // if all array values are defined (e.g. batch<list<_>>)
1609        // The array at this level looks like:
1610        // 0: [a]
1611        // 1: [a]
1612        // 2: [a]
1613        // 3: [a]
1614
1615        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        // 0: null
1641        // 1: [1, 2, 3]
1642        // 2: [4, 5]
1643        // 3: [6, 7]
1644        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        // nested lists
1675        // In a JSON syntax with the schema: <struct<list<list<primitive>>>>, this translates into:
1676        // 0: {"struct": null }
1677        // 1: {"struct": [ [201], [202, 203], [] ]}
1678        // 2: {"struct": [ [204, 205, 206], [207, 208, 209, 210] ]}
1679        // 3: {"struct": [ [], [211, 212, 213, 214, 215] ]}
1680
1681        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        // tests a <struct[a]<struct[b]<int[c]>>
1732        // array:
1733        //  - {a: {b: {c: 1}}}
1734        //  - {a: {b: {c: null}}}
1735        //  - {a: {b: {c: 3}}}
1736        //  - {a: {b: null}}
1737        //  - {a: null}}
1738        //  - {a: {b: {c: 6}}}
1739
1740        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        // this tests the level generation from the arrow_writer equivalent test
1774
1775        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        // this tests the level generation from the equivalent arrow_writer_complex test
1815
1816        // define schema
1817        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, // https://github.com/apache/arrow-rs/issues/245
1836            ),
1837        ]);
1838
1839        // create some data
1840        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        // Construct a buffer for value offsets, for the nested array:
1848        //  [[1], [2, 3], null, [4, 5, 6], [7, 8, 9, 10]]
1849        let g_value_offsets = arrow::buffer::Buffer::from([0, 1, 3, 3, 6, 10].to_byte_slice());
1850
1851        // Construct a list array from the above two
1852        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        // build a record batch
1871        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        //////////////////////////////////////////////
1878        // calculate the list's level
1879        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        // test "a" levels
1891        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        // test "b" levels
1906        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        // test "d" levels
1922        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        // test "f" levels
1938        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        // define schema
1957        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        // create some data
1965        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        // build a record batch
1971        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        // create second batch
1978        // define schema
1979        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        // create some data
1987        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        // build a record batch
1993        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        // The 2 levels should not be the same
2000        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        // Note: we are using the JSON Arrow reader for brevity
2008        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            // not nullable, so the keys have max level = 1
2028            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        // calculate the map's level
2037        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        // test key levels
2052        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        // test values levels
2067        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        // define schema
2086        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        // [{a: 1}], [], null, [null, null], [{a: null}], [{a: 2}]
2096        //
2097        // [{a: 1}]
2098        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        // []
2107        list_builder.append(true);
2108
2109        // null
2110        list_builder.append(false);
2111
2112        // [null, null]
2113        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        // [{a: null}]
2127        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        // [{a: 2}]
2136        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        // Test the null mask of a struct array masking out non-empty slices of a child ListArray
2175        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]), // Masked by struct array
2180            Some(vec![Some(4), Some(5)]),
2181            None, // Masked by struct array
2182            None,
2183        ]);
2184        let values = inner.values().clone();
2185
2186        // This test assumes that nulls don't take up space
2187        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        // Test the null mask of a struct array and the null mask of a list array
2218        // masking out non-null elements of their children
2219
2220        let a1 = ListArray::from_iter_primitive::<Int32Type, _, _>(vec![
2221            Some(vec![None]), // Masked by list array
2222            Some(vec![]),     // Masked by list array
2223            Some(vec![Some(3), None]),
2224            Some(vec![Some(4), Some(5), None, Some(6)]), // Masked by struct array
2225            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), // Masked by list array
2233            Some(2), // Masked by list array
2234            None,
2235            Some(4), // Masked by struct array
2236            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        // [[1, 2], null, null, [7, 8], null]
2320        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        // define schema
2360        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        // [
2377        //   [{a: 1, b: 2}, null],
2378        //   null,
2379        //   [null, null],
2380        //   [{a: null, b: 3}, {a: 2, b: 4}]
2381        // ]
2382
2383        // [{a: 1, b: 2}, null]
2384        let values = list_builder.values();
2385        // {a: 1, b: 2}
2386        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        // null
2396        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        // null
2408        let values = list_builder.values();
2409        // null
2410        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        // null
2420        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        // [null, null]
2432        let values = list_builder.values();
2433        // null
2434        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        // null
2444        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        // [{a: null, b: 3}, {a: 2, b: 4}]
2456        let values = list_builder.values();
2457        // {a: null, b: 3}
2458        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        // {a: 2, b: 4}
2468        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        // [[{a: 1}, null], null, [null, null], [{a: null}, {a: 2}]]
2496        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        // [[{b: 2}, null], null, [null, null], [{b: 3}, {b: 4}]]
2508        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        // [[[1, null, 3], null], [[4], []], [[5, 6], [null, null]], null]
2559        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        // [NULL, NULL, 3, 0]
2606        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        // Case 1: required field (max_def_level=0, no def/rep levels stored).
2651        // Array has 6 values; all are non-null so non_null_indices covers every position.
2652        // value_offset=2, num_values=3 → non_null_indices[2..5] = [2,3,4].
2653        // Array is sliced (no def_levels → write_batch_internal uses values.len()).
2654        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        // Case 2: optional field (max_def_level=1, def levels present, no rep levels).
2678        // Array: [Some(1), None, Some(3), None, Some(5), Some(6)]
2679        // non_null_indices: [0, 2, 4, 5]
2680        // value_offset=1, num_values=1 → non_null_indices[1..2] = [2].
2681        // Array is not sliced (def_levels present → num_levels from def_levels.len()).
2682        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]); // [2] shifted by -2 (nni[0])
2710        assert_eq!(sliced.array.len(), 1);
2711    }
2712
2713    #[test]
2714    fn test_slice_for_chunk_nested_with_nulls() {
2715        // Regression test for https://github.com/apache/arrow-rs/issues/9637
2716        //
2717        // Simulates a List<Int32?> where null list entries have non-zero child
2718        // ranges (valid per Arrow spec: "a null value may correspond to a
2719        // non-empty segment in the child array"). This creates gaps in the
2720        // leaf array that don't correspond to any levels.
2721        //
2722        // 5 rows with 2 null list entries owning non-empty child ranges:
2723        //   row 0: [1]       → leaf[0]
2724        //   row 1: null list → owns leaf[1..3] (gap of 2)
2725        //   row 2: [2, null] → leaf[3], leaf[4]=null element
2726        //   row 3: null list → owns leaf[5..8] (gap of 3)
2727        //   row 4: [4, 5]   → leaf[8], leaf[9]
2728        //
2729        // def_levels: [3,  0,  3, 2,  0,  3, 3]
2730        // rep_levels: [0,  0,  0, 1,  0,  0, 1]
2731        // non_null_indices: [0, 3, 8, 9]
2732        //   gaps in array: 0→3 (skip 1,2), 3→8 (skip 5,6,7)
2733        let array: ArrayRef = Arc::new(Int32Array::from(vec![
2734            Some(1), // 0: row 0
2735            None,    // 1: gap (null list row 1)
2736            None,    // 2: gap (null list row 1)
2737            Some(2), // 3: row 2
2738            None,    // 4: row 2, null element
2739            None,    // 5: gap (null list row 3)
2740            None,    // 6: gap (null list row 3)
2741            None,    // 7: gap (null list row 3)
2742            Some(4), // 8: row 4
2743            Some(5), // 9: row 4
2744        ]));
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        // Chunk 0: rows 0-1, nni=[0] → array sliced to [0..1]
2758        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        // Chunk 1: rows 2-3, nni=[3] → array sliced to [3..4]
2768        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        // Chunk 2: row 4, nni=[8, 9] → array sliced to [8..10]
2778        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        // All-null chunk: num_values=0 → empty nni slice → zero-length array.
2791        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        // Chunk covering only the two null rows (levels 1..3), zero non-null values.
2804        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        // List<Int32> where every list slot is null.
2818        // Schema: list (nullable) -> item (int32, nullable)
2819        // Data: [null, null, null, null]
2820        //
2821        // Expected: max_def=3, max_rep=1, def/rep levels all 0.
2822        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        // FixedSizeList<Int32; 2> where every list slot is null.
2848        // Schema: list (nullable) -> item (int32, nullable)
2849        // Data: [null, null, null]
2850        //
2851        // Expected: max_def=3, max_rep=1, def/rep levels all 0.
2852        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        // Struct<Int32> where every struct slot is null.
2878        // Schema: a (struct, nullable) -> c (int32, nullable)
2879        // Data: [null, null, null, null]
2880        //
2881        // Expected: max_def=2, def_levels all 0 (struct is null → child never reached),
2882        // leaf values are empty.
2883        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        // Struct<Struct<Int32>> where the outer struct is entirely null.
2909        // Schema: a (struct, nullable) -> b (struct, nullable) -> c (int32, nullable)
2910        // Data: [null, null, null]
2911        //
2912        // Expected: max_def=3, def_levels all 0.
2913        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        // Struct with two leaf children, entirely null.
2944        // Schema: a (struct, nullable) -> { c1 (int32, nullable), c2 (int32, nullable) }
2945        // Data: [null, null]
2946        //
2947        // Both leaf columns should get uniform def_levels=0.
2948        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}