Skip to main content

parquet/column/chunker/
cdc.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#[cfg(feature = "arrow")]
6use crate::column::writer::LevelDataRef;
7use crate::errors::{ParquetError, Result};
8use crate::file::properties::CdcOptions;
9use crate::schema::types::ColumnDescriptor;
10
11use super::CdcChunk;
12use super::cdc_generated::{GEARHASH_TABLE, NUM_GEARHASH_TABLES};
13
14/// CDC (Content-Defined Chunking) divides data into variable-sized chunks based on
15/// content rather than fixed-size boundaries.
16///
17/// For example, given this sequence of values in a column:
18///
19/// ```text
20/// File1:    [1,2,3,   4,5,6,   7,8,9]
21///            chunk1   chunk2   chunk3
22/// ```
23///
24/// If a value is inserted between 3 and 4:
25///
26/// ```text
27/// File2:    [1,2,3,0,   4,5,6,   7,8,9]
28///            new-chunk  chunk2   chunk3
29/// ```
30///
31/// The chunking process adjusts to maintain stable boundaries across data modifications.
32/// Each chunk defines a new parquet data page which is contiguously written to the file.
33/// Since each page is compressed independently, the files' contents look like:
34///
35/// ```text
36/// File1:    [Page1][Page2][Page3]...
37/// File2:    [Page4][Page2][Page3]...
38/// ```
39///
40/// When uploaded to a content-addressable storage (CAS) system, the CAS splits the byte
41/// stream into content-defined blobs with unique identifiers. Identical blobs are stored
42/// only once, so Page2 and Page3 are deduplicated across File1 and File2.
43///
44/// ## Implementation
45///
46/// Only the parquet writer needs to be aware of content-defined chunking; the reader is
47/// unaffected. Each parquet column writer holds a `ContentDefinedChunker` instance
48/// depending on the writer's properties. The chunker's state is maintained across the
49/// entire column without being reset between pages and row groups.
50///
51/// This implements a [FastCDC]-inspired algorithm using gear hashing. The input data is
52/// fed byte-by-byte into a rolling hash; when the hash matches a predefined mask, a new
53/// chunk boundary candidate is recorded. To reduce the exponential variance of chunk
54/// sizes inherent in a single gear hash, the algorithm requires **8 consecutive mask
55/// matches** — each against a different pre-computed gear hash table — before committing
56/// to a boundary. This [central-limit-theorem normalization] makes the chunk size
57/// distribution approximately normal between `min_chunk_size` and `max_chunk_size`.
58///
59/// The chunker receives the record-shredded column data (def_levels, rep_levels, values)
60/// and iterates over the (def_level, rep_level, value) triplets while adjusting the
61/// column-global rolling hash. Whenever the rolling hash matches, the chunker creates a
62/// new chunk. For nested data (lists, maps, structs) chunk boundaries are restricted to
63/// top-level record boundaries (`rep_level == 0`) so that a nested row is never split
64/// across chunks.
65///
66/// Note that boundaries are deterministically calculated exclusively based on the data
67/// itself, so the same data always produces the same chunks given the same configuration.
68///
69/// Ported from the C++ implementation in apache/arrow#45360
70/// (`cpp/src/parquet/chunker_internal.cc`).
71///
72/// [FastCDC]: https://www.usenix.org/conference/atc16/technical-sessions/presentation/xia
73/// [central-limit-theorem normalization]: https://www.cidrdb.org/cidr2023/papers/p43-low.pdf
74#[derive(Debug)]
75pub(crate) struct ContentDefinedChunker {
76    /// Maximum definition level for this column.
77    max_def_level: i16,
78    /// Maximum repetition level for this column.
79    max_rep_level: i16,
80    /// Definition level at the nearest REPEATED ancestor.
81    repeated_ancestor_def_level: i16,
82
83    /// Minimum chunk size in bytes.
84    /// The rolling hash will not be updated until this size is reached for each chunk.
85    /// All data sent through the hash function counts towards the chunk size, including
86    /// definition and repetition levels if present.
87    min_chunk_size: i64,
88    /// Maximum chunk size in bytes.
89    /// A new chunk is created whenever the chunk size exceeds this value. The chunk size
90    /// distribution approximates a normal distribution between `min_chunk_size` and
91    /// `max_chunk_size`. Note that the parquet writer has a related `data_pagesize`
92    /// property that controls the maximum size of a parquet data page after encoding.
93    /// While setting `data_pagesize` smaller than `max_chunk_size` doesn't affect
94    /// chunking effectiveness, it results in more small parquet data pages.
95    max_chunk_size: i64,
96    /// Mask for matching against the rolling hash.
97    rolling_hash_mask: u64,
98
99    /// Rolling hash state, never reset — initialized once for the entire column.
100    rolling_hash: u64,
101    /// Whether the rolling hash has matched the mask since the last chunk boundary.
102    has_matched: bool,
103    /// Current run count for the central-limit-theorem normalization.
104    nth_run: usize,
105    /// Current chunk size in bytes.
106    chunk_size: i64,
107}
108
109impl ContentDefinedChunker {
110    pub fn new(desc: &ColumnDescriptor, options: &CdcOptions) -> Result<Self> {
111        let rolling_hash_mask = Self::calculate_mask(
112            options.min_chunk_size as i64,
113            options.max_chunk_size as i64,
114            options.norm_level,
115        )?;
116        Ok(Self {
117            max_def_level: desc.max_def_level(),
118            max_rep_level: desc.max_rep_level(),
119            repeated_ancestor_def_level: desc.repeated_ancestor_def_level(),
120            min_chunk_size: options.min_chunk_size as i64,
121            max_chunk_size: options.max_chunk_size as i64,
122            rolling_hash_mask,
123            rolling_hash: 0,
124            has_matched: false,
125            nth_run: 0,
126            chunk_size: 0,
127        })
128    }
129
130    /// Calculate the mask used to determine chunk boundaries from the rolling hash.
131    ///
132    /// The mask is calculated so that the expected chunk size distribution approximates
133    /// a normal distribution between min and max chunk sizes.
134    fn calculate_mask(min_chunk_size: i64, max_chunk_size: i64, norm_level: i32) -> Result<u64> {
135        if min_chunk_size < 0 {
136            return Err(ParquetError::General(
137                "min_chunk_size must be non-negative".to_string(),
138            ));
139        }
140        if max_chunk_size <= min_chunk_size {
141            return Err(ParquetError::General(
142                "max_chunk_size must be greater than min_chunk_size".to_string(),
143            ));
144        }
145
146        let avg_chunk_size = min_chunk_size.midpoint(max_chunk_size);
147        // Target size after subtracting the min-size skip window and dividing by the
148        // number of hash tables (for central-limit-theorem normalization).
149        let target_size = (avg_chunk_size - min_chunk_size) / NUM_GEARHASH_TABLES as i64;
150
151        // floor(log2(target_size)) — equivalent to C++ NumRequiredBits(target_size) - 1
152        let mask_bits = if target_size > 0 {
153            63 - target_size.leading_zeros() as i32
154        } else {
155            0
156        };
157
158        let effective_bits = mask_bits - norm_level;
159
160        if !(1..=63).contains(&effective_bits) {
161            return Err(ParquetError::General(format!(
162                "The number of bits in the CDC mask must be between 1 and 63, got {effective_bits}"
163            )));
164        }
165
166        // Create the mask by setting the top `effective_bits` bits.
167        Ok(u64::MAX << (64 - effective_bits))
168    }
169
170    /// Feed raw bytes into the rolling hash.
171    ///
172    /// The byte count always accumulates toward `chunk_size`, but the actual hash
173    /// update is skipped until `min_chunk_size` has been reached. This "skip window"
174    /// is the FastCDC optimization that prevents boundaries from appearing too early
175    /// in a chunk.
176    #[inline]
177    fn roll(&mut self, bytes: &[u8]) {
178        self.chunk_size += bytes.len() as i64;
179        if self.chunk_size < self.min_chunk_size {
180            return;
181        }
182        for &b in bytes {
183            self.rolling_hash = self
184                .rolling_hash
185                .wrapping_shl(1)
186                .wrapping_add(GEARHASH_TABLE[self.nth_run][b as usize]);
187            self.has_matched =
188                self.has_matched || ((self.rolling_hash & self.rolling_hash_mask) == 0);
189        }
190    }
191
192    /// Feed exactly `N` bytes into the rolling hash (compile-time width).
193    ///
194    /// Like [`roll`](Self::roll), but the byte count is known at compile time,
195    /// allowing the compiler to unroll the inner loop.
196    #[inline(always)]
197    fn roll_fixed<const N: usize>(&mut self, bytes: &[u8; N]) {
198        self.chunk_size += N as i64;
199        if self.chunk_size < self.min_chunk_size {
200            return;
201        }
202        for j in 0..N {
203            self.rolling_hash = self
204                .rolling_hash
205                .wrapping_shl(1)
206                .wrapping_add(GEARHASH_TABLE[self.nth_run][bytes[j] as usize]);
207            self.has_matched =
208                self.has_matched || ((self.rolling_hash & self.rolling_hash_mask) == 0);
209        }
210    }
211
212    /// Feed a definition or repetition level (i16) into the rolling hash.
213    #[inline]
214    fn roll_level(&mut self, level: i16) {
215        self.roll_fixed(&level.to_le_bytes());
216    }
217
218    /// Check whether a new chunk boundary should be created.
219    ///
220    /// A boundary is created when **either** of two conditions holds:
221    ///
222    /// 1. **CLT normalization**: The rolling hash has matched the mask (`has_matched`)
223    ///    *and* this is the 8th consecutive such match (`nth_run` reaches
224    ///    `NUM_GEARHASH_TABLES`). Each match advances to the next gear hash table, so
225    ///    8 independent matches are required. A single hash table would yield
226    ///    exponentially distributed chunk sizes; requiring 8 independent matches
227    ///    approximates a normal (Gaussian) distribution by the central limit theorem.
228    ///
229    /// 2. **Hard size limit**: `chunk_size` has reached `max_chunk_size`. This caps
230    ///    chunk size even if the CLT normalization sequence has not completed.
231    ///
232    /// Note: when `max_chunk_size` forces a boundary, `nth_run` is **not** reset, so
233    /// the CLT sequence continues from where it left off in the next chunk. This
234    /// matches the C++ behavior.
235    #[inline]
236    fn need_new_chunk(&mut self) -> bool {
237        if self.has_matched {
238            self.has_matched = false;
239            self.nth_run += 1;
240            if self.nth_run >= NUM_GEARHASH_TABLES {
241                self.nth_run = 0;
242                self.chunk_size = 0;
243                return true;
244            }
245        }
246        if self.chunk_size >= self.max_chunk_size {
247            self.chunk_size = 0;
248            return true;
249        }
250        false
251    }
252
253    /// Compute chunk boundaries for the given column data.
254    ///
255    /// The chunking state is maintained across the entire column without being
256    /// reset between pages and row groups. This enables the chunking process to
257    /// be continued between different write calls.
258    ///
259    /// We go over the (def_level, rep_level, value) triplets one by one while
260    /// adjusting the column-global rolling hash based on the triplet. Whenever
261    /// the rolling hash matches a predefined mask it sets `has_matched` to true.
262    ///
263    /// After each triplet [`need_new_chunk`](Self::need_new_chunk) is called to
264    /// evaluate if we need to create a new chunk.
265    fn calculate<F>(
266        &mut self,
267        def_levels: LevelDataRef<'_>,
268        rep_levels: LevelDataRef<'_>,
269        num_levels: usize,
270        mut roll_value: F,
271    ) -> Vec<CdcChunk>
272    where
273        F: FnMut(&mut Self, usize),
274    {
275        let has_def_levels = self.max_def_level > 0;
276        let has_rep_levels = self.max_rep_level > 0;
277
278        let mut chunks = Vec::new();
279        let mut prev_offset: usize = 0;
280        let mut prev_value_offset: usize = 0;
281        let mut value_offset: usize = 0;
282
283        if !has_rep_levels && !has_def_levels {
284            // Fastest path: non-nested, non-null data.
285            // Every level corresponds to exactly one non-null value, so
286            // value_offset == level_offset and num_values == num_levels.
287            //
288            // Example: required Int32, array = [10, 20, 30]
289            //   level:         0   1   2
290            //   value_offset:  0   1   2
291            for offset in 0..num_levels {
292                roll_value(self, offset);
293                if self.need_new_chunk() {
294                    chunks.push(CdcChunk {
295                        level_offset: prev_offset,
296                        num_levels: offset - prev_offset,
297                        value_offset: prev_offset,
298                        num_values: offset - prev_offset,
299                    });
300                    prev_offset = offset;
301                }
302            }
303            prev_value_offset = prev_offset;
304            value_offset = num_levels;
305        } else if !has_rep_levels {
306            // Non-nested data with nulls. value_offset only increments for
307            // non-null values (def == max_def), so it diverges from the
308            // level offset when nulls are present.
309            //
310            // Example: optional Int32, array = [1, null, 2, null, 3]
311            //   def_levels:    [1, 0, 1, 0, 1]
312            //   level:          0  1  2  3  4
313            //   value_offset:   0     1     2  (only increments on def==1)
314            for offset in 0..num_levels {
315                let def_level = def_levels
316                    .value_at(offset)
317                    .expect("def_levels required when max_def_level > 0");
318                self.roll_level(def_level);
319                if def_level == self.max_def_level {
320                    // For non-nested data, the leaf array has one slot per
321                    // level (nulls are array elements), so `offset` (the
322                    // level index) is the correct array index for hashing.
323                    roll_value(self, offset);
324                }
325                // Check boundary before incrementing value_offset so that
326                // num_values reflects only entries in the completed chunk.
327                if self.need_new_chunk() {
328                    chunks.push(CdcChunk {
329                        level_offset: prev_offset,
330                        num_levels: offset - prev_offset,
331                        value_offset: prev_value_offset,
332                        num_values: value_offset - prev_value_offset,
333                    });
334                    prev_offset = offset;
335                    prev_value_offset = value_offset;
336                }
337                if def_level == self.max_def_level {
338                    value_offset += 1;
339                }
340            }
341        } else {
342            // Nested data with nulls. Two counters are needed:
343            //
344            //   leaf_offset: index into the leaf values array for hashing,
345            //     incremented for all leaf slots (def >= repeated_ancestor_def_level),
346            //     including null elements.
347            //
348            //   value_offset: index into non_null_indices for chunk boundaries,
349            //     incremented only for non-null leaf values (def == max_def_level).
350            //
351            // These diverge when nullable elements exist inside lists.
352            //
353            // Example: List<Int32?> with repeated_ancestor_def_level=2, max_def=3
354            //   row 0: [1, null, 2]   (3 leaf slots, 2 non-null)
355            //   row 1: [3]            (1 leaf slot, 1 non-null)
356            //
357            //   leaf array:    [1, null, 2, 3]
358            //   def_levels:    [3,  2,   3, 3]
359            //   rep_levels:    [0,  1,   1, 0]
360            //
361            //   level  def  leaf_offset  value_offset  action
362            //   ─────  ───  ───────────  ────────────  ──────────────────────────
363            //     0     3       0             0        roll_value(0), value++, leaf++
364            //     1     2       1             1        leaf++ only (null element)
365            //     2     3       2             1        roll_value(2), value++, leaf++
366            //     3     3       3             2        roll_value(3), value++, leaf++
367            //
368            // roll_value(2) correctly indexes leaf array position 2 (value "2").
369            // Using value_offset=1 would index position 1 (the null slot).
370            //
371            // Using value_offset for roll_value would hash the wrong array slot.
372            let mut leaf_offset: usize = 0;
373
374            for offset in 0..num_levels {
375                let def_level = def_levels
376                    .value_at(offset)
377                    .expect("def_levels required for nested data");
378                let rep_level = rep_levels
379                    .value_at(offset)
380                    .expect("rep_levels required for nested data");
381
382                self.roll_level(def_level);
383                self.roll_level(rep_level);
384                if def_level == self.max_def_level {
385                    roll_value(self, leaf_offset);
386                }
387
388                // Check boundary before incrementing value_offset so that
389                // num_values reflects only entries in the completed chunk.
390                if rep_level == 0 && self.need_new_chunk() {
391                    let levels_to_write = offset - prev_offset;
392                    if levels_to_write > 0 {
393                        chunks.push(CdcChunk {
394                            level_offset: prev_offset,
395                            num_levels: levels_to_write,
396                            value_offset: prev_value_offset,
397                            num_values: value_offset - prev_value_offset,
398                        });
399                        prev_offset = offset;
400                        prev_value_offset = value_offset;
401                    }
402                }
403                if def_level == self.max_def_level {
404                    value_offset += 1;
405                }
406                if def_level >= self.repeated_ancestor_def_level {
407                    leaf_offset += 1;
408                }
409            }
410        }
411
412        // Add the last chunk if we have any levels left.
413        if prev_offset < num_levels {
414            chunks.push(CdcChunk {
415                level_offset: prev_offset,
416                num_levels: num_levels - prev_offset,
417                value_offset: prev_value_offset,
418                num_values: value_offset - prev_value_offset,
419            });
420        }
421
422        #[cfg(debug_assertions)]
423        self.validate_chunks(&chunks, num_levels, value_offset);
424
425        chunks
426    }
427
428    /// Compute CDC chunk boundaries by dispatching on the Arrow array's data type
429    /// to feed value bytes into the rolling hash.
430    #[cfg(feature = "arrow")]
431    pub(crate) fn get_arrow_chunks(
432        &mut self,
433        def_levels: LevelDataRef<'_>,
434        rep_levels: LevelDataRef<'_>,
435        array: &dyn arrow_array::Array,
436    ) -> Result<Vec<CdcChunk>> {
437        use arrow_array::cast::AsArray;
438        use arrow_schema::DataType;
439
440        // For nested (list) data, null list entries can own non-zero child
441        // ranges in the leaf array, so `array.len()` may exceed the number of
442        // levels.  Always drive the loop by the level count; fall back to the
443        // array length only when there are no levels at all.
444        let num_levels = match (def_levels.len(), rep_levels.len()) {
445            (0, 0) => array.len(),
446            (d, r) => d.max(r),
447        };
448
449        macro_rules! fixed_width {
450            ($N:literal) => {{
451                let data = array.to_data();
452                let buffer = data.buffers()[0].as_slice();
453                let values = &buffer[data.offset() * $N..];
454                self.calculate(def_levels, rep_levels, num_levels, |c, i| {
455                    let offset = i * $N;
456                    let slice = &values[offset..offset + $N];
457                    c.roll_fixed::<$N>(slice.try_into().unwrap());
458                })
459            }};
460        }
461
462        macro_rules! binary_like {
463            ($a:expr) => {{
464                let a = $a;
465                self.calculate(def_levels, rep_levels, num_levels, |c, i| {
466                    c.roll(a.value(i).as_ref());
467                })
468            }};
469        }
470
471        let dtype = array.data_type();
472        let chunks = match dtype {
473            DataType::Null => self.calculate(def_levels, rep_levels, num_levels, |_, _| {}),
474            DataType::Boolean => {
475                let a = array.as_boolean();
476                self.calculate(def_levels, rep_levels, num_levels, |c, i| {
477                    c.roll_fixed(&[a.value(i) as u8]);
478                })
479            }
480            DataType::Int8 | DataType::UInt8 => fixed_width!(1),
481            DataType::Int16 | DataType::UInt16 | DataType::Float16 => fixed_width!(2),
482            DataType::Int32
483            | DataType::UInt32
484            | DataType::Float32
485            | DataType::Date32
486            | DataType::Time32(_)
487            | DataType::Interval(arrow_schema::IntervalUnit::YearMonth)
488            | DataType::Decimal32(_, _) => fixed_width!(4),
489            DataType::Int64
490            | DataType::UInt64
491            | DataType::Float64
492            | DataType::Date64
493            | DataType::Time64(_)
494            | DataType::Timestamp(_, _)
495            | DataType::Duration(_)
496            | DataType::Interval(arrow_schema::IntervalUnit::DayTime)
497            | DataType::Decimal64(_, _) => fixed_width!(8),
498            DataType::Interval(arrow_schema::IntervalUnit::MonthDayNano)
499            | DataType::Decimal128(_, _) => fixed_width!(16),
500            DataType::Decimal256(_, _) => fixed_width!(32),
501            DataType::FixedSizeBinary(_) => binary_like!(array.as_fixed_size_binary()),
502            DataType::Binary => binary_like!(array.as_binary::<i32>()),
503            DataType::LargeBinary => binary_like!(array.as_binary::<i64>()),
504            DataType::Utf8 => binary_like!(array.as_string::<i32>()),
505            DataType::LargeUtf8 => binary_like!(array.as_string::<i64>()),
506            DataType::BinaryView => binary_like!(array.as_binary_view()),
507            DataType::Utf8View => binary_like!(array.as_string_view()),
508            DataType::Dictionary(_, _) => {
509                let dict = array.as_any_dictionary();
510                self.get_arrow_chunks(def_levels, rep_levels, dict.keys())?
511            }
512            _ => {
513                return Err(ParquetError::General(format!(
514                    "content-defined chunking is not supported for data type {dtype:?}",
515                )));
516            }
517        };
518        Ok(chunks)
519    }
520
521    #[cfg(debug_assertions)]
522    fn validate_chunks(&self, chunks: &[CdcChunk], num_levels: usize, total_values: usize) {
523        assert!(!chunks.is_empty(), "chunks must be non-empty");
524
525        let first = &chunks[0];
526        assert_eq!(first.level_offset, 0, "first chunk must start at level 0");
527        assert_eq!(first.value_offset, 0, "first chunk must start at value 0");
528
529        let mut sum_levels = first.num_levels;
530        let mut sum_values = first.num_values;
531        for i in 1..chunks.len() {
532            let chunk = &chunks[i];
533            let prev = &chunks[i - 1];
534            assert!(chunk.num_levels > 0, "chunk must have levels");
535            assert_eq!(
536                chunk.level_offset,
537                prev.level_offset + prev.num_levels,
538                "level offsets must be contiguous"
539            );
540            assert_eq!(
541                chunk.value_offset,
542                prev.value_offset + prev.num_values,
543                "value offsets must be contiguous"
544            );
545            sum_levels += chunk.num_levels;
546            sum_values += chunk.num_values;
547        }
548        assert_eq!(sum_levels, num_levels, "chunks must cover all levels");
549        assert_eq!(sum_values, total_values, "chunks must cover all values");
550
551        let last = chunks.last().unwrap();
552        assert_eq!(
553            last.level_offset + last.num_levels,
554            num_levels,
555            "last chunk must end at num_levels"
556        );
557    }
558}
559
560#[cfg(test)]
561mod tests {
562    use super::*;
563    use crate::basic::Type as PhysicalType;
564    #[cfg(feature = "arrow")]
565    use crate::column::writer::LevelDataRef;
566    use crate::schema::types::{ColumnPath, Type};
567    use std::sync::Arc;
568
569    fn make_desc(max_def_level: i16, max_rep_level: i16) -> ColumnDescriptor {
570        let tp = Type::primitive_type_builder("col", PhysicalType::INT32)
571            .build()
572            .unwrap();
573        ColumnDescriptor::new(
574            Arc::new(tp),
575            max_def_level,
576            max_rep_level,
577            ColumnPath::new(vec![]),
578        )
579    }
580
581    #[test]
582    fn test_calculate_mask_defaults() {
583        let mask = ContentDefinedChunker::calculate_mask(256 * 1024, 1024 * 1024, 0).unwrap();
584        // avg = 640 KiB, target = (640-256)*1024/8 = 49152, log2(49152) = 15
585        // mask = u64::MAX << (64 - 15) = top 15 bits set
586        let expected = u64::MAX << (64 - 15);
587        assert_eq!(mask, expected);
588    }
589
590    #[test]
591    fn test_calculate_mask_with_norm_level() {
592        let mask = ContentDefinedChunker::calculate_mask(256 * 1024, 1024 * 1024, 1).unwrap();
593        let expected = u64::MAX << (64 - 14);
594        assert_eq!(mask, expected);
595    }
596
597    #[test]
598    fn test_calculate_mask_invalid() {
599        assert!(ContentDefinedChunker::calculate_mask(-1, 100, 0).is_err());
600        assert!(ContentDefinedChunker::calculate_mask(100, 50, 0).is_err());
601        assert!(ContentDefinedChunker::calculate_mask(100, 100, 0).is_err());
602    }
603
604    #[test]
605    fn test_non_nested_non_null_single_chunk() {
606        let options = CdcOptions {
607            min_chunk_size: 8,
608            max_chunk_size: 1024,
609            norm_level: 0,
610        };
611        let mut chunker = ContentDefinedChunker::new(&make_desc(0, 0), &options).unwrap();
612
613        // Write a small amount of data — should produce exactly 1 chunk.
614        let num_values = 4;
615        let chunks = chunker.calculate(
616            LevelDataRef::Absent,
617            LevelDataRef::Absent,
618            num_values,
619            |c, i| {
620                c.roll_fixed::<4>(&(i as i32).to_le_bytes());
621            },
622        );
623        assert_eq!(chunks.len(), 1);
624        assert_eq!(chunks[0].level_offset, 0);
625        assert_eq!(chunks[0].value_offset, 0);
626        assert_eq!(chunks[0].num_levels, 4);
627    }
628
629    #[test]
630    fn test_max_chunk_size_forces_boundary() {
631        let options = CdcOptions {
632            min_chunk_size: 256,
633            max_chunk_size: 1024,
634            norm_level: 0,
635        };
636        let mut chunker = ContentDefinedChunker::new(&make_desc(0, 0), &options).unwrap();
637
638        // Write enough data to exceed max_chunk_size multiple times.
639        // Each i32 = 4 bytes, max_chunk_size=1024, so ~256 values per chunk max.
640        let num_values = 2000;
641        let chunks = chunker.calculate(
642            LevelDataRef::Absent,
643            LevelDataRef::Absent,
644            num_values,
645            |c, i| {
646                c.roll_fixed::<4>(&(i as i32).to_le_bytes());
647            },
648        );
649
650        // Should have multiple chunks
651        assert!(chunks.len() > 1);
652
653        // Verify contiguity
654        let mut total_levels = 0;
655        for (i, chunk) in chunks.iter().enumerate() {
656            assert_eq!(chunk.level_offset, total_levels);
657            if i < chunks.len() - 1 {
658                assert!(chunk.num_levels > 0);
659            }
660            total_levels += chunk.num_levels;
661        }
662        assert_eq!(total_levels, num_values);
663    }
664
665    #[test]
666    fn test_deterministic_chunks() {
667        let options = CdcOptions {
668            min_chunk_size: 4,
669            max_chunk_size: 64,
670            norm_level: 0,
671        };
672
673        let roll = |c: &mut ContentDefinedChunker, i: usize| {
674            c.roll_fixed::<8>(&(i as i64).to_le_bytes());
675        };
676
677        let mut chunker1 = ContentDefinedChunker::new(&make_desc(0, 0), &options).unwrap();
678        let chunks1 = chunker1.calculate(LevelDataRef::Absent, LevelDataRef::Absent, 200, roll);
679
680        let mut chunker2 = ContentDefinedChunker::new(&make_desc(0, 0), &options).unwrap();
681        let chunks2 = chunker2.calculate(LevelDataRef::Absent, LevelDataRef::Absent, 200, roll);
682
683        assert_eq!(chunks1.len(), chunks2.len());
684        for (a, b) in chunks1.iter().zip(chunks2.iter()) {
685            assert_eq!(a.level_offset, b.level_offset);
686            assert_eq!(a.num_levels, b.num_levels);
687            assert_eq!(a.value_offset, b.value_offset);
688            assert_eq!(a.num_values, b.num_values);
689        }
690    }
691
692    #[test]
693    fn test_nullable_non_nested() {
694        let options = CdcOptions {
695            min_chunk_size: 4,
696            max_chunk_size: 64,
697            norm_level: 0,
698        };
699        let mut chunker = ContentDefinedChunker::new(&make_desc(1, 0), &options).unwrap();
700
701        let num_levels = 20;
702        // def_level=1 means non-null, def_level=0 means null
703        // Pattern: null at indices 0, 3, 6, 9, 12, 15, 18 → 7 nulls, 13 non-null
704        let def_levels: Vec<i16> = (0..num_levels).map(|i| i16::from(i % 3 != 0)).collect();
705        let expected_non_null: usize = def_levels.iter().filter(|&&d| d == 1).count();
706
707        let chunks = chunker.calculate(
708            LevelDataRef::Materialized(&def_levels),
709            LevelDataRef::Absent,
710            num_levels,
711            |c, i| {
712                c.roll_fixed::<4>(&(i as i32).to_le_bytes());
713            },
714        );
715
716        assert!(!chunks.is_empty());
717        let total_levels: usize = chunks.iter().map(|c| c.num_levels).sum();
718        let total_values: usize = chunks.iter().map(|c| c.num_values).sum();
719        assert_eq!(total_levels, num_levels);
720        assert_eq!(total_values, expected_non_null);
721        // With nulls present, total_values < total_levels
722        assert!(total_values < total_levels);
723    }
724}
725
726/// Integration tests that exercise CDC through the Arrow writer/reader roundtrip.
727/// Ported from the C++ test suite in `chunker_internal_test.cc`.
728#[cfg(all(test, feature = "arrow"))]
729mod arrow_tests {
730    use std::borrow::Borrow;
731    use std::cmp::Ordering;
732    use std::sync::Arc;
733
734    use arrow::util::data_gen::create_random_batch;
735    use arrow_array::cast::AsArray;
736    use arrow_array::{Array, ArrayRef, BooleanArray, Int32Array, RecordBatch};
737    use arrow_buffer::Buffer;
738    use arrow_data::ArrayData;
739    use arrow_schema::{DataType, Field, Fields, Schema};
740
741    use crate::arrow::arrow_reader::ParquetRecordBatchReaderBuilder;
742    use crate::arrow::arrow_writer::ArrowWriter;
743    use crate::column::writer::LevelDataRef;
744    use crate::file::properties::{
745        CdcOptions, WriterProperties, WriterPropertiesBuilder, WriterVersion,
746    };
747    use crate::file::reader::{FileReader, SerializedFileReader};
748
749    // --- Constants matching C++ TestCDCSingleRowGroup ---
750
751    const CDC_MIN_CHUNK_SIZE: usize = 4 * 1024;
752    const CDC_MAX_CHUNK_SIZE: usize = 16 * 1024;
753    const CDC_PART_SIZE: usize = 128 * 1024;
754    const CDC_EDIT_SIZE: usize = 128;
755    const CDC_ROW_GROUP_LENGTH: usize = 1024 * 1024;
756
757    // --- Helpers ---
758
759    /// Deterministic hash function matching the C++ test generator.
760    fn test_hash(seed: u64, index: u64) -> u64 {
761        let mut h = (index.wrapping_add(seed)).wrapping_mul(0xc4ceb9fe1a85ec53u64);
762        h ^= h >> 33;
763        h = h.wrapping_mul(0xff51afd7ed558ccdu64);
764        h ^= h >> 33;
765        h = h.wrapping_mul(0xc4ceb9fe1a85ec53u64);
766        h ^= h >> 33;
767        h
768    }
769
770    /// Generate a deterministic array for any supported data type, matching C++ `GenerateArray`.
771    fn generate_array(dtype: &DataType, nullable: bool, length: usize, seed: u64) -> ArrayRef {
772        macro_rules! gen_primitive {
773            ($array_type:ty, $cast:expr) => {{
774                if nullable {
775                    let arr: $array_type = (0..length)
776                        .map(|i| {
777                            let val = test_hash(seed, i as u64);
778                            if val % 10 == 0 {
779                                None
780                            } else {
781                                Some($cast(val))
782                            }
783                        })
784                        .collect();
785                    Arc::new(arr) as ArrayRef
786                } else {
787                    let arr: $array_type = (0..length)
788                        .map(|i| Some($cast(test_hash(seed, i as u64))))
789                        .collect();
790                    Arc::new(arr) as ArrayRef
791                }
792            }};
793        }
794
795        match dtype {
796            DataType::Boolean => {
797                if nullable {
798                    let arr: BooleanArray = (0..length)
799                        .map(|i| {
800                            let val = test_hash(seed, i as u64);
801                            if val.is_multiple_of(10) {
802                                None
803                            } else {
804                                Some(val.is_multiple_of(2))
805                            }
806                        })
807                        .collect();
808                    Arc::new(arr)
809                } else {
810                    let arr: BooleanArray = (0..length)
811                        .map(|i| Some(test_hash(seed, i as u64).is_multiple_of(2)))
812                        .collect();
813                    Arc::new(arr)
814                }
815            }
816            DataType::Int32 => gen_primitive!(Int32Array, |v: u64| v as i32),
817            DataType::Int64 => {
818                gen_primitive!(arrow_array::Int64Array, |v: u64| v as i64)
819            }
820            DataType::Float64 => {
821                gen_primitive!(arrow_array::Float64Array, |v: u64| (v % 100000) as f64
822                    / 1000.0)
823            }
824            DataType::Utf8 => {
825                let arr: arrow_array::StringArray = if nullable {
826                    (0..length)
827                        .map(|i| {
828                            let val = test_hash(seed, i as u64);
829                            if val.is_multiple_of(10) {
830                                None
831                            } else {
832                                Some(format!("str_{val}"))
833                            }
834                        })
835                        .collect()
836                } else {
837                    (0..length)
838                        .map(|i| Some(format!("str_{}", test_hash(seed, i as u64))))
839                        .collect()
840                };
841                Arc::new(arr)
842            }
843            DataType::Binary => {
844                let arr: arrow_array::BinaryArray = if nullable {
845                    (0..length)
846                        .map(|i| {
847                            let val = test_hash(seed, i as u64);
848                            if val.is_multiple_of(10) {
849                                None
850                            } else {
851                                Some(format!("bin_{val}").into_bytes())
852                            }
853                        })
854                        .collect()
855                } else {
856                    (0..length)
857                        .map(|i| Some(format!("bin_{}", test_hash(seed, i as u64)).into_bytes()))
858                        .collect()
859                };
860                Arc::new(arr)
861            }
862            DataType::FixedSizeBinary(size) => {
863                let size = *size;
864                let mut builder = arrow_array::builder::FixedSizeBinaryBuilder::new(size);
865                for i in 0..length {
866                    let val = test_hash(seed, i as u64);
867                    if nullable && val.is_multiple_of(10) {
868                        builder.append_null();
869                    } else {
870                        let s = format!("bin_{val}");
871                        let bytes = s.as_bytes();
872                        let mut buf = vec![0u8; size as usize];
873                        let copy_len = bytes.len().min(size as usize);
874                        buf[..copy_len].copy_from_slice(&bytes[..copy_len]);
875                        builder.append_value(&buf).unwrap();
876                    }
877                }
878                Arc::new(builder.finish())
879            }
880            DataType::Date32 => {
881                gen_primitive!(arrow_array::Date32Array, |v: u64| v as i32)
882            }
883            DataType::Timestamp(arrow_schema::TimeUnit::Nanosecond, _) => {
884                gen_primitive!(arrow_array::TimestampNanosecondArray, |v: u64| v as i64)
885            }
886            _ => panic!("Unsupported test data type: {dtype:?}"),
887        }
888    }
889
890    /// Generate a RecordBatch with the given schema, matching C++ `GenerateTable`.
891    fn generate_table(schema: &Arc<Schema>, length: usize, seed: u64) -> RecordBatch {
892        let arrays: Vec<ArrayRef> = schema
893            .fields()
894            .iter()
895            .enumerate()
896            .map(|(i, field)| {
897                generate_array(
898                    field.data_type(),
899                    field.is_nullable(),
900                    length,
901                    seed + i as u64 * 10,
902                )
903            })
904            .collect();
905        RecordBatch::try_new(schema.clone(), arrays).unwrap()
906    }
907
908    /// Compute the CDC byte width for a data type, matching C++ `bytes_per_record`.
909    /// Returns 0 for variable-length types.
910    fn cdc_byte_width(dtype: &DataType) -> usize {
911        match dtype {
912            DataType::Boolean => 1,
913            DataType::Int8 | DataType::UInt8 => 1,
914            DataType::Int16 | DataType::UInt16 | DataType::Float16 => 2,
915            DataType::Int32
916            | DataType::UInt32
917            | DataType::Float32
918            | DataType::Date32
919            | DataType::Time32(_) => 4,
920            DataType::Int64
921            | DataType::UInt64
922            | DataType::Float64
923            | DataType::Date64
924            | DataType::Time64(_)
925            | DataType::Timestamp(_, _)
926            | DataType::Duration(_) => 8,
927            DataType::Decimal128(_, _) => 16,
928            DataType::Decimal256(_, _) => 32,
929            DataType::FixedSizeBinary(n) => *n as usize,
930            _ => 0, // variable-length
931        }
932    }
933
934    /// Compute bytes_per_record for determining part/edit lengths, matching C++.
935    fn bytes_per_record(dtype: &DataType, nullable: bool) -> usize {
936        let bw = cdc_byte_width(dtype);
937        if bw > 0 {
938            if nullable { bw + 2 } else { bw }
939        } else {
940            16 // variable-length fallback, matching C++
941        }
942    }
943
944    /// Compute the CDC chunk size for an array slice, matching C++ `CalculateCdcSize`.
945    fn calculate_cdc_size(array: &dyn Array, nullable: bool) -> i64 {
946        let dtype = array.data_type();
947        let bw = cdc_byte_width(dtype);
948        let result = if bw > 0 {
949            // Fixed-width: count only non-null values
950            let valid_count = array.len() - array.null_count();
951            (valid_count * bw) as i64
952        } else {
953            // Variable-length: sum of actual byte lengths
954            match dtype {
955                DataType::Utf8 => {
956                    let a = array.as_string::<i32>();
957                    (0..a.len())
958                        .filter(|&i| a.is_valid(i))
959                        .map(|i| a.value(i).len() as i64)
960                        .sum()
961                }
962                DataType::Binary => {
963                    let a = array.as_binary::<i32>();
964                    (0..a.len())
965                        .filter(|&i| a.is_valid(i))
966                        .map(|i| a.value(i).len() as i64)
967                        .sum()
968                }
969                DataType::LargeBinary => {
970                    let a = array.as_binary::<i64>();
971                    (0..a.len())
972                        .filter(|&i| a.is_valid(i))
973                        .map(|i| a.value(i).len() as i64)
974                        .sum()
975                }
976                _ => panic!("CDC size calculation not implemented for {dtype:?}"),
977            }
978        };
979
980        if nullable {
981            // Add 2 bytes per element for definition levels
982            result + array.len() as i64 * 2
983        } else {
984            result
985        }
986    }
987
988    /// Page-level metadata for a single column within a row group.
989    struct ColumnInfo {
990        page_lengths: Vec<i64>,
991        has_dictionary_page: bool,
992    }
993
994    /// Extract per-row-group column info from Parquet data.
995    fn get_column_info(data: &[u8], column_index: usize) -> Vec<ColumnInfo> {
996        let reader = SerializedFileReader::new(bytes::Bytes::from(data.to_vec())).unwrap();
997        let metadata = reader.metadata();
998        let mut result = Vec::new();
999        for rg in 0..metadata.num_row_groups() {
1000            let rg_reader = reader.get_row_group(rg).unwrap();
1001            let col_reader = rg_reader.get_column_page_reader(column_index).unwrap();
1002            let mut info = ColumnInfo {
1003                page_lengths: Vec::new(),
1004                has_dictionary_page: false,
1005            };
1006            for page in col_reader {
1007                let page = page.unwrap();
1008                match page.page_type() {
1009                    crate::basic::PageType::DATA_PAGE | crate::basic::PageType::DATA_PAGE_V2 => {
1010                        info.page_lengths.push(page.num_values() as i64);
1011                    }
1012                    crate::basic::PageType::DICTIONARY_PAGE => {
1013                        info.has_dictionary_page = true;
1014                    }
1015                    crate::basic::PageType::INDEX_PAGE => {}
1016                }
1017            }
1018            result.push(info);
1019        }
1020        result
1021    }
1022
1023    /// Assert that CDC chunk sizes are within the expected range.
1024    /// Equivalent to C++ `AssertContentDefinedChunkSizes`.
1025    fn assert_cdc_chunk_sizes(
1026        array: &ArrayRef,
1027        info: &ColumnInfo,
1028        nullable: bool,
1029        min_chunk_size: usize,
1030        max_chunk_size: usize,
1031        expect_dictionary_page: bool,
1032    ) {
1033        // Boolean columns never produce dictionary pages.
1034        let expect_dict = match array.data_type() {
1035            DataType::Boolean => false,
1036            _ => expect_dictionary_page,
1037        };
1038        assert_eq!(
1039            info.has_dictionary_page,
1040            expect_dict,
1041            "dictionary page mismatch for {:?}",
1042            array.data_type()
1043        );
1044
1045        let page_lengths = &info.page_lengths;
1046        assert!(
1047            page_lengths.len() > 1,
1048            "CDC should produce multiple pages, got {page_lengths:?}"
1049        );
1050
1051        let bw = cdc_byte_width(array.data_type());
1052        // Only do exact CDC size validation for fixed-width and base binary-like types
1053        if bw > 0
1054            || matches!(
1055                array.data_type(),
1056                DataType::Utf8 | DataType::Binary | DataType::LargeBinary
1057            )
1058        {
1059            let mut offset = 0i64;
1060            for (i, &page_len) in page_lengths.iter().enumerate() {
1061                let slice = array.slice(offset as usize, page_len as usize);
1062                let cdc_size = calculate_cdc_size(slice.as_ref(), nullable);
1063                if i < page_lengths.len() - 1 {
1064                    assert!(
1065                        cdc_size >= min_chunk_size as i64,
1066                        "Page {i}: CDC size {cdc_size} < min {min_chunk_size}, pages={page_lengths:?}"
1067                    );
1068                }
1069                assert!(
1070                    cdc_size <= max_chunk_size as i64,
1071                    "Page {i}: CDC size {cdc_size} > max {max_chunk_size}, pages={page_lengths:?}"
1072                );
1073                offset += page_len;
1074            }
1075            assert_eq!(
1076                offset,
1077                array.len() as i64,
1078                "page lengths must sum to array length"
1079            );
1080        }
1081    }
1082
1083    /// Write batches with CDC options and validate roundtrip.
1084    /// Matches C++ `WriteTableToBuffer`.
1085    fn write_with_cdc_options(
1086        batches: &[&RecordBatch],
1087        min_chunk_size: usize,
1088        max_chunk_size: usize,
1089        max_row_group_rows: Option<usize>,
1090        enable_dictionary: bool,
1091    ) -> Vec<u8> {
1092        assert!(!batches.is_empty());
1093        let schema = batches[0].schema();
1094        let mut builder = WriterProperties::builder()
1095            .set_dictionary_enabled(enable_dictionary)
1096            .set_content_defined_chunking(Some(CdcOptions {
1097                min_chunk_size,
1098                max_chunk_size,
1099                norm_level: 0,
1100            }));
1101        if let Some(max_rows) = max_row_group_rows {
1102            builder = builder.set_max_row_group_row_count(Some(max_rows));
1103        }
1104        let props = builder.build();
1105        let mut buf = Vec::new();
1106        let mut writer = ArrowWriter::try_new(&mut buf, schema.clone(), Some(props)).unwrap();
1107        for batch in batches {
1108            writer.write(batch).unwrap();
1109        }
1110        writer.close().unwrap();
1111
1112        // Roundtrip validation (matching C++ WriteTableToBuffer)
1113        let readback = read_batches(&buf);
1114        let original_rows: usize = batches.iter().map(|b| b.num_rows()).sum();
1115        let readback_rows: usize = readback.iter().map(|b| b.num_rows()).sum();
1116        assert_eq!(original_rows, readback_rows, "Roundtrip row count mismatch");
1117        if original_rows > 0 {
1118            let original = concat_batches(batches.iter().copied());
1119            let roundtrip = concat_batches(&readback);
1120            assert_eq!(original, roundtrip, "Roundtrip validation failed");
1121        }
1122
1123        buf
1124    }
1125
1126    /// Write a batch with common CDC settings and test-specific writer properties.
1127    fn write_cdc_batch(batch: &RecordBatch, builder: WriterPropertiesBuilder) -> Vec<u8> {
1128        let props = builder
1129            .set_writer_version(WriterVersion::PARQUET_2_0)
1130            .set_content_defined_chunking(Some(CdcOptions {
1131                min_chunk_size: 8 * 1024,
1132                max_chunk_size: 16 * 1024,
1133                norm_level: 0,
1134            }))
1135            .build();
1136
1137        let mut buf = Vec::new();
1138        let mut writer = ArrowWriter::try_new(&mut buf, batch.schema(), Some(props)).unwrap();
1139        writer.write(batch).unwrap();
1140        writer.close().unwrap();
1141        buf
1142    }
1143
1144    fn assert_multiple_nonempty_data_pages(data: &[u8]) {
1145        let info = get_column_info(data, 0);
1146        let total: usize = info.iter().map(|c| c.page_lengths.len()).sum();
1147        let empty = info
1148            .iter()
1149            .flat_map(|c| c.page_lengths.iter())
1150            .filter(|&&n| n == 0)
1151            .count();
1152
1153        assert!(
1154            total > 1,
1155            "CDC should produce multiple data pages, got {total}"
1156        );
1157        assert_eq!(empty, 0, "forced CDC page breaks must not emit empty pages");
1158    }
1159
1160    #[test]
1161    #[cfg_attr(miri, ignore)] // large enough to hit CDC chunk boundaries
1162    fn cdc_boolean_small_pages_does_not_panic() {
1163        let num_rows = 32_768;
1164        let values: Vec<bool> = (0..num_rows).map(|i| i % 7 == 0).collect();
1165        let col = Arc::new(BooleanArray::from(values)) as ArrayRef;
1166        let batch = RecordBatch::try_from_iter([("flag", col)]).unwrap();
1167
1168        let props = WriterProperties::builder().set_data_page_size_limit(1024);
1169        let data = write_cdc_batch(&batch, props);
1170        assert_multiple_nonempty_data_pages(&data);
1171
1172        let readback = read_batches(&data);
1173        let rows: usize = readback.iter().map(|b| b.num_rows()).sum();
1174        assert_eq!(rows, num_rows);
1175    }
1176
1177    #[test]
1178    #[cfg_attr(miri, ignore)] // large enough to hit CDC chunk boundaries
1179    fn cdc_int32_row_count_limit_does_not_emit_empty_pages() {
1180        let values: Vec<i32> = (0..8_192).map(|i| i % 97).collect();
1181        let col = Arc::new(Int32Array::from(values)) as ArrayRef;
1182        let batch = RecordBatch::try_from_iter([("a", col)]).unwrap();
1183
1184        let props = WriterProperties::builder()
1185            .set_dictionary_enabled(false)
1186            .set_data_page_row_count_limit(128);
1187        let data = write_cdc_batch(&batch, props);
1188        assert_multiple_nonempty_data_pages(&data);
1189    }
1190
1191    #[test]
1192    fn cdc_all_null_arrow_column_writes_data_pages() {
1193        let array = Arc::new(Int32Array::from(vec![None::<i32>; 4096])) as ArrayRef;
1194        let schema = Arc::new(Schema::new(vec![Field::new("f0", DataType::Int32, true)]));
1195        let batch = RecordBatch::try_new(schema, vec![array.clone()]).unwrap();
1196
1197        let data = write_with_cdc_options(&[&batch], 64, 256, Some(4096), false);
1198        let info = get_column_info(&data, 0);
1199
1200        assert_eq!(info.len(), 1);
1201        assert!(
1202            !info[0].page_lengths.is_empty(),
1203            "all-null CDC write should still emit data pages"
1204        );
1205        assert_eq!(
1206            info[0].page_lengths.iter().sum::<i64>(),
1207            array.len() as i64,
1208            "all-null CDC pages should account for every input row"
1209        );
1210    }
1211
1212    fn read_batches(data: &[u8]) -> Vec<RecordBatch> {
1213        let reader = ParquetRecordBatchReaderBuilder::try_new(bytes::Bytes::from(data.to_vec()))
1214            .unwrap()
1215            .build()
1216            .unwrap();
1217        reader.collect::<std::result::Result<Vec<_>, _>>().unwrap()
1218    }
1219
1220    fn concat_batches(batches: impl IntoIterator<Item = impl Borrow<RecordBatch>>) -> RecordBatch {
1221        let batches: Vec<_> = batches.into_iter().collect();
1222        let schema = batches[0].borrow().schema();
1223        let batches = batches.iter().map(|b| b.borrow());
1224        arrow_select::concat::concat_batches(&schema, batches).unwrap()
1225    }
1226
1227    /// LCS-based diff between two sequences of page lengths (ported from C++).
1228    /// Includes the merge-adjacent-diffs post-processing from C++.
1229    fn find_differences(first: &[i64], second: &[i64]) -> Vec<(Vec<i64>, Vec<i64>)> {
1230        let n = first.len();
1231        let m = second.len();
1232        let mut dp = vec![vec![0usize; m + 1]; n + 1];
1233        for i in 0..n {
1234            for j in 0..m {
1235                if first[i] == second[j] {
1236                    dp[i + 1][j + 1] = dp[i][j] + 1;
1237                } else {
1238                    dp[i + 1][j + 1] = dp[i + 1][j].max(dp[i][j + 1]);
1239                }
1240            }
1241        }
1242        let mut common = Vec::new();
1243        let (mut i, mut j) = (n, m);
1244        while i > 0 && j > 0 {
1245            if first[i - 1] == second[j - 1] {
1246                common.push((i - 1, j - 1));
1247                i -= 1;
1248                j -= 1;
1249            } else if dp[i - 1][j] >= dp[i][j - 1] {
1250                i -= 1;
1251            } else {
1252                j -= 1;
1253            }
1254        }
1255        common.reverse();
1256
1257        let mut result = Vec::new();
1258        let (mut last_i, mut last_j) = (0usize, 0usize);
1259        for (ci, cj) in &common {
1260            if *ci > last_i || *cj > last_j {
1261                result.push((first[last_i..*ci].to_vec(), second[last_j..*cj].to_vec()));
1262            }
1263            last_i = ci + 1;
1264            last_j = cj + 1;
1265        }
1266        if last_i < n || last_j < m {
1267            result.push((first[last_i..].to_vec(), second[last_j..].to_vec()));
1268        }
1269
1270        // Merge adjacent diffs (matching C++ post-processing)
1271        let mut merged: Vec<(Vec<i64>, Vec<i64>)> = Vec::new();
1272        for diff in result {
1273            if let Some(prev) = merged.last_mut() {
1274                if prev.0.is_empty() && diff.1.is_empty() {
1275                    prev.0 = diff.0;
1276                    continue;
1277                } else if prev.1.is_empty() && diff.0.is_empty() {
1278                    prev.1 = diff.1;
1279                    continue;
1280                }
1281            }
1282            merged.push(diff);
1283        }
1284        merged
1285    }
1286
1287    /// Assert exact page length differences between original and modified files.
1288    /// Matches C++ `AssertPageLengthDifferences` (full version).
1289    fn assert_page_length_differences(
1290        original: &ColumnInfo,
1291        modified: &ColumnInfo,
1292        exact_equal_diffs: usize,
1293        exact_larger_diffs: usize,
1294        exact_smaller_diffs: usize,
1295        edit_length: i64,
1296    ) {
1297        let diffs = find_differences(&original.page_lengths, &modified.page_lengths);
1298        let expected = exact_equal_diffs + exact_larger_diffs + exact_smaller_diffs;
1299
1300        if diffs.len() != expected {
1301            eprintln!("Original: {:?}", original.page_lengths);
1302            eprintln!("Modified: {:?}", modified.page_lengths);
1303            for d in &diffs {
1304                eprintln!("  Diff: {:?} vs {:?}", d.0, d.1);
1305            }
1306        }
1307        assert_eq!(
1308            diffs.len(),
1309            expected,
1310            "Expected {expected} diffs, got {}",
1311            diffs.len()
1312        );
1313
1314        let (mut eq, mut larger, mut smaller) = (0usize, 0usize, 0usize);
1315        for (left, right) in &diffs {
1316            let left_sum: i64 = left.iter().sum();
1317            let right_sum: i64 = right.iter().sum();
1318            match left_sum.cmp(&right_sum) {
1319                Ordering::Equal => eq += 1,
1320                Ordering::Less => {
1321                    larger += 1;
1322                    assert_eq!(
1323                        left_sum + edit_length,
1324                        right_sum,
1325                        "Larger diff mismatch: {left_sum} + {edit_length} != {right_sum}"
1326                    );
1327                }
1328                Ordering::Greater => {
1329                    smaller += 1;
1330                    assert_eq!(
1331                        left_sum,
1332                        right_sum + edit_length,
1333                        "Smaller diff mismatch: {left_sum} != {right_sum} + {edit_length}"
1334                    );
1335                }
1336            }
1337        }
1338
1339        assert_eq!(eq, exact_equal_diffs, "equal diffs count");
1340        assert_eq!(larger, exact_larger_diffs, "larger diffs count");
1341        assert_eq!(smaller, exact_smaller_diffs, "smaller diffs count");
1342    }
1343
1344    /// Assert page length differences for update cases (simplified version).
1345    /// Matches C++ `AssertPageLengthDifferences` (max_equal_diffs overload).
1346    fn assert_page_length_differences_update(
1347        original: &ColumnInfo,
1348        modified: &ColumnInfo,
1349        max_equal_diffs: usize,
1350    ) {
1351        let diffs = find_differences(&original.page_lengths, &modified.page_lengths);
1352        assert!(
1353            diffs.len() <= max_equal_diffs,
1354            "Expected at most {max_equal_diffs} diffs, got {}",
1355            diffs.len()
1356        );
1357        for (left, right) in &diffs {
1358            let left_sum: i64 = left.iter().sum();
1359            let right_sum: i64 = right.iter().sum();
1360            assert_eq!(
1361                left_sum, right_sum,
1362                "Update diff should not change total row count"
1363            );
1364        }
1365    }
1366
1367    // --- FindDifferences tests (ported from C++) ---
1368
1369    #[test]
1370    fn test_find_differences_basic() {
1371        let diffs = find_differences(&[1, 2, 3, 4, 5], &[1, 7, 8, 4, 5]);
1372        assert_eq!(diffs.len(), 1);
1373        assert_eq!(diffs[0].0, vec![2, 3]);
1374        assert_eq!(diffs[0].1, vec![7, 8]);
1375    }
1376
1377    #[test]
1378    fn test_find_differences_multiple() {
1379        let diffs = find_differences(&[1, 2, 3, 4, 5, 6, 7], &[1, 8, 9, 4, 10, 6, 11]);
1380        assert_eq!(diffs.len(), 3);
1381        assert_eq!(diffs[0].0, vec![2, 3]);
1382        assert_eq!(diffs[0].1, vec![8, 9]);
1383        assert_eq!(diffs[1].0, vec![5]);
1384        assert_eq!(diffs[1].1, vec![10]);
1385        assert_eq!(diffs[2].0, vec![7]);
1386        assert_eq!(diffs[2].1, vec![11]);
1387    }
1388
1389    #[test]
1390    fn test_find_differences_different_lengths() {
1391        let diffs = find_differences(&[1, 2, 3], &[1, 2, 3, 4, 5]);
1392        assert_eq!(diffs.len(), 1);
1393        assert!(diffs[0].0.is_empty());
1394        assert_eq!(diffs[0].1, vec![4, 5]);
1395    }
1396
1397    #[test]
1398    fn test_find_differences_empty() {
1399        let diffs = find_differences(&[], &[]);
1400        assert!(diffs.is_empty());
1401    }
1402
1403    #[test]
1404    fn test_find_differences_changes_at_both_ends() {
1405        let diffs = find_differences(&[1, 2, 3, 4, 5, 6, 7, 8, 9], &[0, 0, 2, 3, 4, 5, 7, 7, 8]);
1406        assert_eq!(diffs.len(), 3);
1407        assert_eq!(diffs[0].0, vec![1]);
1408        assert_eq!(diffs[0].1, vec![0, 0]);
1409        assert_eq!(diffs[1].0, vec![6]);
1410        assert_eq!(diffs[1].1, vec![7]);
1411        assert_eq!(diffs[2].0, vec![9]);
1412        assert!(diffs[2].1.is_empty());
1413    }
1414
1415    #[test]
1416    fn test_find_differences_additional() {
1417        let diffs = find_differences(
1418            &[445, 312, 393, 401, 410, 138, 558, 457],
1419            &[445, 312, 393, 393, 410, 138, 558, 457],
1420        );
1421        assert_eq!(diffs.len(), 1);
1422        assert_eq!(diffs[0].0, vec![401]);
1423        assert_eq!(diffs[0].1, vec![393]);
1424    }
1425
1426    // --- Parameterized single-row-group tests via macro ---
1427
1428    macro_rules! cdc_single_rg_tests {
1429        ($mod_name:ident, $dtype:expr, $nullable:expr) => {
1430            mod $mod_name {
1431                use super::*;
1432
1433                fn config() -> (DataType, bool, usize, usize) {
1434                    let dtype: DataType = $dtype;
1435                    let nullable: bool = $nullable;
1436                    let bpr = bytes_per_record(&dtype, nullable);
1437                    let part_length = CDC_PART_SIZE / bpr;
1438                    let edit_length = CDC_EDIT_SIZE / bpr;
1439                    (dtype, nullable, part_length, edit_length)
1440                }
1441
1442                fn make_schema(dtype: &DataType, nullable: bool) -> Arc<Schema> {
1443                    Arc::new(Schema::new(vec![Field::new("f0", dtype.clone(), nullable)]))
1444                }
1445
1446                #[test]
1447                #[cfg_attr(miri, ignore)] // Takes too long
1448                fn delete_once() {
1449                    let (dtype, nullable, part_length, edit_length) = config();
1450                    let schema = make_schema(&dtype, nullable);
1451
1452                    let part1 = generate_table(&schema, part_length, 0);
1453                    let part2 = generate_table(&schema, edit_length, 1);
1454                    let part3 = generate_table(&schema, part_length, part_length as u64);
1455
1456                    let base = concat_batches([&part1, &part2, &part3]);
1457                    let modified = concat_batches([&part1, &part3]);
1458
1459                    for enable_dictionary in [false, true] {
1460                        let base_data = write_with_cdc_options(
1461                            &[&base],
1462                            CDC_MIN_CHUNK_SIZE,
1463                            CDC_MAX_CHUNK_SIZE,
1464                            Some(CDC_ROW_GROUP_LENGTH),
1465                            enable_dictionary,
1466                        );
1467                        let mod_data = write_with_cdc_options(
1468                            &[&modified],
1469                            CDC_MIN_CHUNK_SIZE,
1470                            CDC_MAX_CHUNK_SIZE,
1471                            Some(CDC_ROW_GROUP_LENGTH),
1472                            enable_dictionary,
1473                        );
1474
1475                        let base_info = get_column_info(&base_data, 0);
1476                        let mod_info = get_column_info(&mod_data, 0);
1477                        assert_eq!(base_info.len(), 1);
1478                        assert_eq!(mod_info.len(), 1);
1479
1480                        assert_cdc_chunk_sizes(
1481                            &base.column(0).clone(),
1482                            &base_info[0],
1483                            nullable,
1484                            CDC_MIN_CHUNK_SIZE,
1485                            CDC_MAX_CHUNK_SIZE,
1486                            enable_dictionary,
1487                        );
1488                        assert_cdc_chunk_sizes(
1489                            &modified.column(0).clone(),
1490                            &mod_info[0],
1491                            nullable,
1492                            CDC_MIN_CHUNK_SIZE,
1493                            CDC_MAX_CHUNK_SIZE,
1494                            enable_dictionary,
1495                        );
1496
1497                        assert_page_length_differences(
1498                            &base_info[0],
1499                            &mod_info[0],
1500                            0,
1501                            0,
1502                            1,
1503                            edit_length as i64,
1504                        );
1505                    }
1506                }
1507
1508                #[test]
1509                #[cfg_attr(miri, ignore)] // Takes too long
1510                fn delete_twice() {
1511                    let (dtype, nullable, part_length, edit_length) = config();
1512                    let schema = make_schema(&dtype, nullable);
1513
1514                    let part1 = generate_table(&schema, part_length, 0);
1515                    let part2 = generate_table(&schema, edit_length, 1);
1516                    let part3 = generate_table(&schema, part_length, part_length as u64);
1517                    let part4 = generate_table(&schema, edit_length, 2);
1518                    let part5 = generate_table(&schema, part_length, 2 * part_length as u64);
1519
1520                    let base = concat_batches([&part1, &part2, &part3, &part4, &part5]);
1521                    let modified = concat_batches([&part1, &part3, &part5]);
1522
1523                    for enable_dictionary in [false, true] {
1524                        let base_data = write_with_cdc_options(
1525                            &[&base],
1526                            CDC_MIN_CHUNK_SIZE,
1527                            CDC_MAX_CHUNK_SIZE,
1528                            Some(CDC_ROW_GROUP_LENGTH),
1529                            enable_dictionary,
1530                        );
1531                        let mod_data = write_with_cdc_options(
1532                            &[&modified],
1533                            CDC_MIN_CHUNK_SIZE,
1534                            CDC_MAX_CHUNK_SIZE,
1535                            Some(CDC_ROW_GROUP_LENGTH),
1536                            enable_dictionary,
1537                        );
1538
1539                        let base_info = get_column_info(&base_data, 0);
1540                        let mod_info = get_column_info(&mod_data, 0);
1541                        assert_eq!(base_info.len(), 1);
1542                        assert_eq!(mod_info.len(), 1);
1543
1544                        assert_cdc_chunk_sizes(
1545                            &base.column(0).clone(),
1546                            &base_info[0],
1547                            nullable,
1548                            CDC_MIN_CHUNK_SIZE,
1549                            CDC_MAX_CHUNK_SIZE,
1550                            enable_dictionary,
1551                        );
1552                        assert_cdc_chunk_sizes(
1553                            &modified.column(0).clone(),
1554                            &mod_info[0],
1555                            nullable,
1556                            CDC_MIN_CHUNK_SIZE,
1557                            CDC_MAX_CHUNK_SIZE,
1558                            enable_dictionary,
1559                        );
1560
1561                        assert_page_length_differences(
1562                            &base_info[0],
1563                            &mod_info[0],
1564                            0,
1565                            0,
1566                            2,
1567                            edit_length as i64,
1568                        );
1569                    }
1570                }
1571
1572                #[test]
1573                #[cfg_attr(miri, ignore)] // Takes too long
1574                fn insert_once() {
1575                    let (dtype, nullable, part_length, edit_length) = config();
1576                    let schema = make_schema(&dtype, nullable);
1577
1578                    let part1 = generate_table(&schema, part_length, 0);
1579                    let part2 = generate_table(&schema, edit_length, 1);
1580                    let part3 = generate_table(&schema, part_length, part_length as u64);
1581
1582                    let base = concat_batches([&part1, &part3]);
1583                    let modified = concat_batches([&part1, &part2, &part3]);
1584
1585                    for enable_dictionary in [false, true] {
1586                        let base_data = write_with_cdc_options(
1587                            &[&base],
1588                            CDC_MIN_CHUNK_SIZE,
1589                            CDC_MAX_CHUNK_SIZE,
1590                            Some(CDC_ROW_GROUP_LENGTH),
1591                            enable_dictionary,
1592                        );
1593                        let mod_data = write_with_cdc_options(
1594                            &[&modified],
1595                            CDC_MIN_CHUNK_SIZE,
1596                            CDC_MAX_CHUNK_SIZE,
1597                            Some(CDC_ROW_GROUP_LENGTH),
1598                            enable_dictionary,
1599                        );
1600
1601                        let base_info = get_column_info(&base_data, 0);
1602                        let mod_info = get_column_info(&mod_data, 0);
1603                        assert_eq!(base_info.len(), 1);
1604                        assert_eq!(mod_info.len(), 1);
1605
1606                        assert_cdc_chunk_sizes(
1607                            &base.column(0).clone(),
1608                            &base_info[0],
1609                            nullable,
1610                            CDC_MIN_CHUNK_SIZE,
1611                            CDC_MAX_CHUNK_SIZE,
1612                            enable_dictionary,
1613                        );
1614                        assert_cdc_chunk_sizes(
1615                            &modified.column(0).clone(),
1616                            &mod_info[0],
1617                            nullable,
1618                            CDC_MIN_CHUNK_SIZE,
1619                            CDC_MAX_CHUNK_SIZE,
1620                            enable_dictionary,
1621                        );
1622
1623                        assert_page_length_differences(
1624                            &base_info[0],
1625                            &mod_info[0],
1626                            0,
1627                            1,
1628                            0,
1629                            edit_length as i64,
1630                        );
1631                    }
1632                }
1633
1634                #[test]
1635                #[cfg_attr(miri, ignore)] // Takes too long
1636                fn insert_twice() {
1637                    let (dtype, nullable, part_length, edit_length) = config();
1638                    let schema = make_schema(&dtype, nullable);
1639
1640                    let part1 = generate_table(&schema, part_length, 0);
1641                    let part2 = generate_table(&schema, edit_length, 1);
1642                    let part3 = generate_table(&schema, part_length, part_length as u64);
1643                    let part4 = generate_table(&schema, edit_length, 2);
1644                    let part5 = generate_table(&schema, part_length, 2 * part_length as u64);
1645
1646                    let base = concat_batches([&part1, &part3, &part5]);
1647                    let modified = concat_batches([&part1, &part2, &part3, &part4, &part5]);
1648
1649                    for enable_dictionary in [false, true] {
1650                        let base_data = write_with_cdc_options(
1651                            &[&base],
1652                            CDC_MIN_CHUNK_SIZE,
1653                            CDC_MAX_CHUNK_SIZE,
1654                            Some(CDC_ROW_GROUP_LENGTH),
1655                            enable_dictionary,
1656                        );
1657                        let mod_data = write_with_cdc_options(
1658                            &[&modified],
1659                            CDC_MIN_CHUNK_SIZE,
1660                            CDC_MAX_CHUNK_SIZE,
1661                            Some(CDC_ROW_GROUP_LENGTH),
1662                            enable_dictionary,
1663                        );
1664
1665                        let base_info = get_column_info(&base_data, 0);
1666                        let mod_info = get_column_info(&mod_data, 0);
1667                        assert_eq!(base_info.len(), 1);
1668                        assert_eq!(mod_info.len(), 1);
1669
1670                        assert_cdc_chunk_sizes(
1671                            &base.column(0).clone(),
1672                            &base_info[0],
1673                            nullable,
1674                            CDC_MIN_CHUNK_SIZE,
1675                            CDC_MAX_CHUNK_SIZE,
1676                            enable_dictionary,
1677                        );
1678                        assert_cdc_chunk_sizes(
1679                            &modified.column(0).clone(),
1680                            &mod_info[0],
1681                            nullable,
1682                            CDC_MIN_CHUNK_SIZE,
1683                            CDC_MAX_CHUNK_SIZE,
1684                            enable_dictionary,
1685                        );
1686
1687                        assert_page_length_differences(
1688                            &base_info[0],
1689                            &mod_info[0],
1690                            0,
1691                            2,
1692                            0,
1693                            edit_length as i64,
1694                        );
1695                    }
1696                }
1697
1698                #[test]
1699                #[cfg_attr(miri, ignore)] // Takes too long
1700                fn update_once() {
1701                    let (dtype, nullable, part_length, edit_length) = config();
1702                    let schema = make_schema(&dtype, nullable);
1703
1704                    let part1 = generate_table(&schema, part_length, 0);
1705                    let part2 = generate_table(&schema, edit_length, 1);
1706                    let part3 = generate_table(&schema, part_length, part_length as u64);
1707                    let part4 = generate_table(&schema, edit_length, 2);
1708
1709                    let base = concat_batches([&part1, &part2, &part3]);
1710                    let modified = concat_batches([&part1, &part4, &part3]);
1711
1712                    for enable_dictionary in [false, true] {
1713                        let base_data = write_with_cdc_options(
1714                            &[&base],
1715                            CDC_MIN_CHUNK_SIZE,
1716                            CDC_MAX_CHUNK_SIZE,
1717                            Some(CDC_ROW_GROUP_LENGTH),
1718                            enable_dictionary,
1719                        );
1720                        let mod_data = write_with_cdc_options(
1721                            &[&modified],
1722                            CDC_MIN_CHUNK_SIZE,
1723                            CDC_MAX_CHUNK_SIZE,
1724                            Some(CDC_ROW_GROUP_LENGTH),
1725                            enable_dictionary,
1726                        );
1727
1728                        let base_info = get_column_info(&base_data, 0);
1729                        let mod_info = get_column_info(&mod_data, 0);
1730                        assert_eq!(base_info.len(), 1);
1731                        assert_eq!(mod_info.len(), 1);
1732
1733                        assert_cdc_chunk_sizes(
1734                            &base.column(0).clone(),
1735                            &base_info[0],
1736                            nullable,
1737                            CDC_MIN_CHUNK_SIZE,
1738                            CDC_MAX_CHUNK_SIZE,
1739                            enable_dictionary,
1740                        );
1741                        assert_cdc_chunk_sizes(
1742                            &modified.column(0).clone(),
1743                            &mod_info[0],
1744                            nullable,
1745                            CDC_MIN_CHUNK_SIZE,
1746                            CDC_MAX_CHUNK_SIZE,
1747                            enable_dictionary,
1748                        );
1749
1750                        assert_page_length_differences_update(&base_info[0], &mod_info[0], 1);
1751                    }
1752                }
1753
1754                #[test]
1755                #[cfg_attr(miri, ignore)] // Takes too long
1756                fn update_twice() {
1757                    let (dtype, nullable, part_length, edit_length) = config();
1758                    let schema = make_schema(&dtype, nullable);
1759
1760                    let part1 = generate_table(&schema, part_length, 0);
1761                    let part2 = generate_table(&schema, edit_length, 1);
1762                    let part3 = generate_table(&schema, part_length, part_length as u64);
1763                    let part4 = generate_table(&schema, edit_length, 2);
1764                    let part5 = generate_table(&schema, part_length, 2 * part_length as u64);
1765                    let part6 = generate_table(&schema, edit_length, 3);
1766                    let part7 = generate_table(&schema, edit_length, 4);
1767
1768                    let base = concat_batches([&part1, &part2, &part3, &part4, &part5]);
1769                    let modified = concat_batches([&part1, &part6, &part3, &part7, &part5]);
1770
1771                    for enable_dictionary in [false, true] {
1772                        let base_data = write_with_cdc_options(
1773                            &[&base],
1774                            CDC_MIN_CHUNK_SIZE,
1775                            CDC_MAX_CHUNK_SIZE,
1776                            Some(CDC_ROW_GROUP_LENGTH),
1777                            enable_dictionary,
1778                        );
1779                        let mod_data = write_with_cdc_options(
1780                            &[&modified],
1781                            CDC_MIN_CHUNK_SIZE,
1782                            CDC_MAX_CHUNK_SIZE,
1783                            Some(CDC_ROW_GROUP_LENGTH),
1784                            enable_dictionary,
1785                        );
1786
1787                        let base_info = get_column_info(&base_data, 0);
1788                        let mod_info = get_column_info(&mod_data, 0);
1789                        assert_eq!(base_info.len(), 1);
1790                        assert_eq!(mod_info.len(), 1);
1791
1792                        assert_cdc_chunk_sizes(
1793                            &base.column(0).clone(),
1794                            &base_info[0],
1795                            nullable,
1796                            CDC_MIN_CHUNK_SIZE,
1797                            CDC_MAX_CHUNK_SIZE,
1798                            enable_dictionary,
1799                        );
1800                        assert_cdc_chunk_sizes(
1801                            &modified.column(0).clone(),
1802                            &mod_info[0],
1803                            nullable,
1804                            CDC_MIN_CHUNK_SIZE,
1805                            CDC_MAX_CHUNK_SIZE,
1806                            enable_dictionary,
1807                        );
1808
1809                        assert_page_length_differences_update(&base_info[0], &mod_info[0], 2);
1810                    }
1811                }
1812
1813                #[test]
1814                #[cfg_attr(miri, ignore)] // Takes too long
1815                fn prepend() {
1816                    let (dtype, nullable, part_length, edit_length) = config();
1817                    let schema = make_schema(&dtype, nullable);
1818
1819                    let part1 = generate_table(&schema, part_length, 0);
1820                    let part2 = generate_table(&schema, edit_length, 1);
1821                    let part3 = generate_table(&schema, part_length, part_length as u64);
1822                    let part4 = generate_table(&schema, edit_length, 2);
1823
1824                    let base = concat_batches([&part1, &part2, &part3]);
1825                    let modified = concat_batches([&part4, &part1, &part2, &part3]);
1826
1827                    for enable_dictionary in [false, true] {
1828                        let base_data = write_with_cdc_options(
1829                            &[&base],
1830                            CDC_MIN_CHUNK_SIZE,
1831                            CDC_MAX_CHUNK_SIZE,
1832                            Some(CDC_ROW_GROUP_LENGTH),
1833                            enable_dictionary,
1834                        );
1835                        let mod_data = write_with_cdc_options(
1836                            &[&modified],
1837                            CDC_MIN_CHUNK_SIZE,
1838                            CDC_MAX_CHUNK_SIZE,
1839                            Some(CDC_ROW_GROUP_LENGTH),
1840                            enable_dictionary,
1841                        );
1842
1843                        let base_info = get_column_info(&base_data, 0);
1844                        let mod_info = get_column_info(&mod_data, 0);
1845                        assert_eq!(base_info.len(), 1);
1846                        assert_eq!(mod_info.len(), 1);
1847
1848                        assert_cdc_chunk_sizes(
1849                            &base.column(0).clone(),
1850                            &base_info[0],
1851                            nullable,
1852                            CDC_MIN_CHUNK_SIZE,
1853                            CDC_MAX_CHUNK_SIZE,
1854                            enable_dictionary,
1855                        );
1856                        assert_cdc_chunk_sizes(
1857                            &modified.column(0).clone(),
1858                            &mod_info[0],
1859                            nullable,
1860                            CDC_MIN_CHUNK_SIZE,
1861                            CDC_MAX_CHUNK_SIZE,
1862                            enable_dictionary,
1863                        );
1864
1865                        assert!(
1866                            mod_info[0].page_lengths.len() >= base_info[0].page_lengths.len(),
1867                            "Modified should have same or more pages"
1868                        );
1869
1870                        assert_page_length_differences(
1871                            &base_info[0],
1872                            &mod_info[0],
1873                            0,
1874                            1,
1875                            0,
1876                            edit_length as i64,
1877                        );
1878                    }
1879                }
1880
1881                #[test]
1882                #[cfg_attr(miri, ignore)] // Takes too long
1883                fn append() {
1884                    let (dtype, nullable, part_length, edit_length) = config();
1885                    let schema = make_schema(&dtype, nullable);
1886
1887                    let part1 = generate_table(&schema, part_length, 0);
1888                    let part2 = generate_table(&schema, edit_length, 1);
1889                    let part3 = generate_table(&schema, part_length, part_length as u64);
1890                    let part4 = generate_table(&schema, edit_length, 2);
1891
1892                    let base = concat_batches([&part1, &part2, &part3]);
1893                    let modified = concat_batches([&part1, &part2, &part3, &part4]);
1894
1895                    for enable_dictionary in [false, true] {
1896                        let base_data = write_with_cdc_options(
1897                            &[&base],
1898                            CDC_MIN_CHUNK_SIZE,
1899                            CDC_MAX_CHUNK_SIZE,
1900                            Some(CDC_ROW_GROUP_LENGTH),
1901                            enable_dictionary,
1902                        );
1903                        let mod_data = write_with_cdc_options(
1904                            &[&modified],
1905                            CDC_MIN_CHUNK_SIZE,
1906                            CDC_MAX_CHUNK_SIZE,
1907                            Some(CDC_ROW_GROUP_LENGTH),
1908                            enable_dictionary,
1909                        );
1910
1911                        let base_info = get_column_info(&base_data, 0);
1912                        let mod_info = get_column_info(&mod_data, 0);
1913                        assert_eq!(base_info.len(), 1);
1914                        assert_eq!(mod_info.len(), 1);
1915
1916                        assert_cdc_chunk_sizes(
1917                            &base.column(0).clone(),
1918                            &base_info[0],
1919                            nullable,
1920                            CDC_MIN_CHUNK_SIZE,
1921                            CDC_MAX_CHUNK_SIZE,
1922                            enable_dictionary,
1923                        );
1924                        assert_cdc_chunk_sizes(
1925                            &modified.column(0).clone(),
1926                            &mod_info[0],
1927                            nullable,
1928                            CDC_MIN_CHUNK_SIZE,
1929                            CDC_MAX_CHUNK_SIZE,
1930                            enable_dictionary,
1931                        );
1932
1933                        let bp = &base_info[0].page_lengths;
1934                        let mp = &mod_info[0].page_lengths;
1935                        assert!(mp.len() >= bp.len());
1936                        for i in 0..bp.len() - 1 {
1937                            assert_eq!(bp[i], mp[i], "Page {i} should be identical");
1938                        }
1939                        assert!(mp[bp.len() - 1] >= bp[bp.len() - 1]);
1940                    }
1941                }
1942
1943                #[test]
1944                fn empty_table() {
1945                    let (dtype, nullable, _, _) = config();
1946                    let schema = make_schema(&dtype, nullable);
1947
1948                    let empty = RecordBatch::new_empty(schema);
1949                    for enable_dictionary in [false, true] {
1950                        let data = write_with_cdc_options(
1951                            &[&empty],
1952                            CDC_MIN_CHUNK_SIZE,
1953                            CDC_MAX_CHUNK_SIZE,
1954                            Some(CDC_ROW_GROUP_LENGTH),
1955                            enable_dictionary,
1956                        );
1957                        let info = get_column_info(&data, 0);
1958                        // Empty table: either no row groups or one with no data pages
1959                        if !info.is_empty() {
1960                            assert!(info[0].page_lengths.is_empty());
1961                        }
1962                    }
1963                }
1964
1965                #[test]
1966                #[cfg_attr(miri, ignore)] // Takes too long
1967                fn array_offsets() {
1968                    let (dtype, nullable, part_length, edit_length) = config();
1969                    let schema = make_schema(&dtype, nullable);
1970
1971                    let table = concat_batches([
1972                        &generate_table(&schema, part_length, 0),
1973                        &generate_table(&schema, edit_length, 1),
1974                        &generate_table(&schema, part_length, part_length as u64),
1975                    ]);
1976
1977                    for offset in [0usize, 512, 1024] {
1978                        if offset >= table.num_rows() {
1979                            continue;
1980                        }
1981                        let sliced = table.slice(offset, table.num_rows() - offset);
1982                        let data = write_with_cdc_options(
1983                            &[&sliced],
1984                            CDC_MIN_CHUNK_SIZE,
1985                            CDC_MAX_CHUNK_SIZE,
1986                            Some(CDC_ROW_GROUP_LENGTH),
1987                            true,
1988                        );
1989                        let info = get_column_info(&data, 0);
1990                        assert_eq!(info.len(), 1);
1991
1992                        // Verify CDC actually produced content-defined chunks
1993                        assert_cdc_chunk_sizes(
1994                            &sliced.column(0).clone(),
1995                            &info[0],
1996                            nullable,
1997                            CDC_MIN_CHUNK_SIZE,
1998                            CDC_MAX_CHUNK_SIZE,
1999                            true,
2000                        );
2001                    }
2002                }
2003            }
2004        };
2005    }
2006
2007    // Instantiate for representative types matching C++ categories
2008    cdc_single_rg_tests!(cdc_bool_non_null, DataType::Boolean, false);
2009    cdc_single_rg_tests!(cdc_i32_non_null, DataType::Int32, false);
2010    cdc_single_rg_tests!(cdc_i64_nullable, DataType::Int64, true);
2011    cdc_single_rg_tests!(cdc_f64_nullable, DataType::Float64, true);
2012    cdc_single_rg_tests!(cdc_utf8_non_null, DataType::Utf8, false);
2013    cdc_single_rg_tests!(cdc_binary_nullable, DataType::Binary, true);
2014    cdc_single_rg_tests!(cdc_fsb16_nullable, DataType::FixedSizeBinary(16), true);
2015    cdc_single_rg_tests!(cdc_date32_non_null, DataType::Date32, false);
2016    cdc_single_rg_tests!(
2017        cdc_timestamp_nullable,
2018        DataType::Timestamp(arrow_schema::TimeUnit::Nanosecond, None),
2019        true
2020    );
2021
2022    // --- Multiple row group tests matching C++ TestCDCMultipleRowGroups ---
2023
2024    mod cdc_multiple_row_groups {
2025        use super::*;
2026
2027        const PART_LENGTH: usize = 128 * 1024;
2028        const EDIT_LENGTH: usize = 128;
2029        const ROW_GROUP_LENGTH: usize = 64 * 1024;
2030
2031        fn schema() -> Arc<Schema> {
2032            Arc::new(Schema::new(vec![
2033                Field::new("int32", DataType::Int32, true),
2034                Field::new("float64", DataType::Float64, true),
2035                Field::new("bool", DataType::Boolean, false),
2036            ]))
2037        }
2038
2039        #[test]
2040        #[cfg_attr(miri, ignore)] // Takes too long
2041        fn insert_once() {
2042            let s = schema();
2043            let part1 = generate_table(&s, PART_LENGTH, 0);
2044            let part2 = generate_table(&s, PART_LENGTH, 2);
2045            let part3 = generate_table(&s, PART_LENGTH, 4);
2046            let edit1 = generate_table(&s, EDIT_LENGTH, 1);
2047            let edit2 = generate_table(&s, EDIT_LENGTH, 3);
2048
2049            let base = concat_batches([&part1, &edit1, &part2, &part3]);
2050            let modified = concat_batches([&part1, &edit1, &edit2, &part2, &part3]);
2051            assert_eq!(modified.num_rows(), base.num_rows() + EDIT_LENGTH);
2052
2053            let base_data = write_with_cdc_options(
2054                &[&base],
2055                CDC_MIN_CHUNK_SIZE,
2056                CDC_MAX_CHUNK_SIZE,
2057                Some(ROW_GROUP_LENGTH),
2058                false,
2059            );
2060            let mod_data = write_with_cdc_options(
2061                &[&modified],
2062                CDC_MIN_CHUNK_SIZE,
2063                CDC_MAX_CHUNK_SIZE,
2064                Some(ROW_GROUP_LENGTH),
2065                false,
2066            );
2067
2068            for col in 0..s.fields().len() {
2069                let base_info = get_column_info(&base_data, col);
2070                let mod_info = get_column_info(&mod_data, col);
2071
2072                assert_eq!(base_info.len(), 7, "expected 7 row groups for col {col}");
2073                assert_eq!(mod_info.len(), 7);
2074
2075                // First two row groups should be identical
2076                assert_eq!(base_info[0].page_lengths, mod_info[0].page_lengths);
2077                assert_eq!(base_info[1].page_lengths, mod_info[1].page_lengths);
2078
2079                // Middle row groups: 1 larger + 1 smaller diff
2080                for i in 2..mod_info.len() - 1 {
2081                    assert_page_length_differences(
2082                        &base_info[i],
2083                        &mod_info[i],
2084                        0,
2085                        1,
2086                        1,
2087                        EDIT_LENGTH as i64,
2088                    );
2089                }
2090                // Last row group: just larger
2091                assert_page_length_differences(
2092                    base_info.last().unwrap(),
2093                    mod_info.last().unwrap(),
2094                    0,
2095                    1,
2096                    0,
2097                    EDIT_LENGTH as i64,
2098                );
2099            }
2100        }
2101
2102        #[test]
2103        #[cfg_attr(miri, ignore)] // Takes too long
2104        fn delete_once() {
2105            let s = schema();
2106            let part1 = generate_table(&s, PART_LENGTH, 0);
2107            let part2 = generate_table(&s, PART_LENGTH, 2);
2108            let part3 = generate_table(&s, PART_LENGTH, 4);
2109            let edit1 = generate_table(&s, EDIT_LENGTH, 1);
2110            let edit2 = generate_table(&s, EDIT_LENGTH, 3);
2111
2112            let base = concat_batches([&part1, &edit1, &part2, &part3, &edit2]);
2113            let modified = concat_batches([&part1, &part2, &part3, &edit2]);
2114
2115            let base_data = write_with_cdc_options(
2116                &[&base],
2117                CDC_MIN_CHUNK_SIZE,
2118                CDC_MAX_CHUNK_SIZE,
2119                Some(ROW_GROUP_LENGTH),
2120                false,
2121            );
2122            let mod_data = write_with_cdc_options(
2123                &[&modified],
2124                CDC_MIN_CHUNK_SIZE,
2125                CDC_MAX_CHUNK_SIZE,
2126                Some(ROW_GROUP_LENGTH),
2127                false,
2128            );
2129
2130            for col in 0..s.fields().len() {
2131                let base_info = get_column_info(&base_data, col);
2132                let mod_info = get_column_info(&mod_data, col);
2133
2134                assert_eq!(base_info.len(), 7);
2135                assert_eq!(mod_info.len(), 7);
2136
2137                assert_eq!(base_info[0].page_lengths, mod_info[0].page_lengths);
2138                assert_eq!(base_info[1].page_lengths, mod_info[1].page_lengths);
2139
2140                for i in 2..mod_info.len() - 1 {
2141                    assert_page_length_differences(
2142                        &base_info[i],
2143                        &mod_info[i],
2144                        0,
2145                        1,
2146                        1,
2147                        EDIT_LENGTH as i64,
2148                    );
2149                }
2150                assert_page_length_differences(
2151                    base_info.last().unwrap(),
2152                    mod_info.last().unwrap(),
2153                    0,
2154                    0,
2155                    1,
2156                    EDIT_LENGTH as i64,
2157                );
2158            }
2159        }
2160
2161        #[test]
2162        #[cfg_attr(miri, ignore)] // Takes too long
2163        fn update_once() {
2164            let s = schema();
2165            let part1 = generate_table(&s, PART_LENGTH, 0);
2166            let part2 = generate_table(&s, PART_LENGTH, 2);
2167            let part3 = generate_table(&s, PART_LENGTH, 4);
2168            let edit1 = generate_table(&s, EDIT_LENGTH, 1);
2169            let edit2 = generate_table(&s, EDIT_LENGTH, 3);
2170            let edit3 = generate_table(&s, EDIT_LENGTH, 5);
2171
2172            let base = concat_batches([&part1, &edit1, &part2, &part3, &edit2]);
2173            let modified = concat_batches([&part1, &edit3, &part2, &part3, &edit2]);
2174
2175            let base_data = write_with_cdc_options(
2176                &[&base],
2177                CDC_MIN_CHUNK_SIZE,
2178                CDC_MAX_CHUNK_SIZE,
2179                Some(ROW_GROUP_LENGTH),
2180                false,
2181            );
2182            let mod_data = write_with_cdc_options(
2183                &[&modified],
2184                CDC_MIN_CHUNK_SIZE,
2185                CDC_MAX_CHUNK_SIZE,
2186                Some(ROW_GROUP_LENGTH),
2187                false,
2188            );
2189
2190            for col in 0..s.fields().len() {
2191                let nullable = s.field(col).is_nullable();
2192                let base_info = get_column_info(&base_data, col);
2193                let mod_info = get_column_info(&mod_data, col);
2194
2195                assert_eq!(base_info.len(), 7);
2196                assert_eq!(mod_info.len(), 7);
2197
2198                // Validate CDC chunk sizes on at least the first row group
2199                assert_cdc_chunk_sizes(
2200                    &base.column(col).slice(0, ROW_GROUP_LENGTH),
2201                    &base_info[0],
2202                    nullable,
2203                    CDC_MIN_CHUNK_SIZE,
2204                    CDC_MAX_CHUNK_SIZE,
2205                    false,
2206                );
2207
2208                assert_eq!(base_info[0].page_lengths, mod_info[0].page_lengths);
2209                assert_eq!(base_info[1].page_lengths, mod_info[1].page_lengths);
2210
2211                // Row group containing the edit
2212                assert_page_length_differences_update(&base_info[2], &mod_info[2], 1);
2213
2214                // Remaining row groups should be identical
2215                for i in 3..mod_info.len() {
2216                    assert_eq!(base_info[i].page_lengths, mod_info[i].page_lengths);
2217                }
2218            }
2219        }
2220
2221        #[test]
2222        #[cfg_attr(miri, ignore)] // Takes too long
2223        fn append() {
2224            let s = schema();
2225            let part1 = generate_table(&s, PART_LENGTH, 0);
2226            let part2 = generate_table(&s, PART_LENGTH, 2);
2227            let part3 = generate_table(&s, PART_LENGTH, 4);
2228            let edit1 = generate_table(&s, EDIT_LENGTH, 1);
2229            let edit2 = generate_table(&s, EDIT_LENGTH, 3);
2230
2231            let base = concat_batches([&part1, &edit1, &part2, &part3]);
2232            let modified = concat_batches([&part1, &edit1, &part2, &part3, &edit2]);
2233
2234            let base_data = write_with_cdc_options(
2235                &[&base],
2236                CDC_MIN_CHUNK_SIZE,
2237                CDC_MAX_CHUNK_SIZE,
2238                Some(ROW_GROUP_LENGTH),
2239                false,
2240            );
2241            let mod_data = write_with_cdc_options(
2242                &[&modified],
2243                CDC_MIN_CHUNK_SIZE,
2244                CDC_MAX_CHUNK_SIZE,
2245                Some(ROW_GROUP_LENGTH),
2246                false,
2247            );
2248
2249            for col in 0..s.fields().len() {
2250                let nullable = s.field(col).is_nullable();
2251                let base_info = get_column_info(&base_data, col);
2252                let mod_info = get_column_info(&mod_data, col);
2253
2254                assert_eq!(base_info.len(), 7);
2255                assert_eq!(mod_info.len(), 7);
2256
2257                // Validate CDC chunk sizes on the first row group
2258                assert_cdc_chunk_sizes(
2259                    &base.column(col).slice(0, ROW_GROUP_LENGTH),
2260                    &base_info[0],
2261                    nullable,
2262                    CDC_MIN_CHUNK_SIZE,
2263                    CDC_MAX_CHUNK_SIZE,
2264                    false,
2265                );
2266
2267                // All row groups except last should be identical
2268                for i in 0..base_info.len() - 1 {
2269                    assert_eq!(base_info[i].page_lengths, mod_info[i].page_lengths);
2270                }
2271
2272                // Last row group: pages should be identical except last
2273                let bp = &base_info.last().unwrap().page_lengths;
2274                let mp = &mod_info.last().unwrap().page_lengths;
2275                assert!(mp.len() >= bp.len());
2276                for i in 0..bp.len() - 1 {
2277                    assert_eq!(bp[i], mp[i]);
2278                }
2279            }
2280        }
2281    }
2282
2283    // --- Direct chunker test (kept from original) ---
2284
2285    #[test]
2286    #[cfg_attr(miri, ignore)] // Takes too long
2287    fn test_cdc_array_offsets_direct() {
2288        use crate::basic::Type as PhysicalType;
2289        use crate::schema::types::{ColumnDescriptor, ColumnPath, Type};
2290
2291        let options = CdcOptions {
2292            min_chunk_size: CDC_MIN_CHUNK_SIZE,
2293            max_chunk_size: CDC_MAX_CHUNK_SIZE,
2294            norm_level: 0,
2295        };
2296        let desc = {
2297            let tp = Type::primitive_type_builder("col", PhysicalType::INT32)
2298                .build()
2299                .unwrap();
2300            ColumnDescriptor::new(Arc::new(tp), 0, 0, ColumnPath::new(vec![]))
2301        };
2302
2303        let bpr = bytes_per_record(&DataType::Int32, false);
2304        let n = CDC_PART_SIZE / bpr;
2305        let offset = 10usize;
2306
2307        let array: Int32Array = (0..n).map(|i| test_hash(0, i as u64) as i32).collect();
2308        let mut chunker = super::ContentDefinedChunker::new(&desc, &options).unwrap();
2309        let chunks = chunker
2310            .get_arrow_chunks(LevelDataRef::Absent, LevelDataRef::Absent, &array)
2311            .unwrap();
2312
2313        let sliced = array.slice(offset, n - offset);
2314        let mut chunker2 = super::ContentDefinedChunker::new(&desc, &options).unwrap();
2315        let chunks2 = chunker2
2316            .get_arrow_chunks(LevelDataRef::Absent, LevelDataRef::Absent, &sliced)
2317            .unwrap();
2318
2319        let values: Vec<usize> = chunks.iter().map(|c| c.num_values).collect();
2320        let values2: Vec<usize> = chunks2.iter().map(|c| c.num_values).collect();
2321
2322        assert!(values.len() > 1, "expected multiple chunks, got {values:?}");
2323        assert_eq!(values.len(), values2.len(), "chunk count must match");
2324
2325        assert_eq!(
2326            values[0] - values2[0],
2327            offset,
2328            "offsetted first chunk should be {offset} values shorter"
2329        );
2330        assert_eq!(
2331            &values[1..],
2332            &values2[1..],
2333            "all chunks after the first must be identical"
2334        );
2335    }
2336
2337    /// Regression test for <https://github.com/apache/arrow-rs/issues/9637>
2338    ///
2339    /// Writing nested list data with CDC enabled panicked with an out-of-bounds
2340    /// slice access when null list entries had non-zero child ranges.
2341    #[test]
2342    #[cfg_attr(miri, ignore)] // Takes too long
2343    fn test_cdc_list_roundtrip() {
2344        let schema = Arc::new(Schema::new(vec![
2345            Field::new(
2346                "_1",
2347                DataType::List(Arc::new(Field::new_list_field(DataType::Int32, true))),
2348                true,
2349            ),
2350            Field::new(
2351                "_2",
2352                DataType::List(Arc::new(Field::new_list_field(DataType::Boolean, true))),
2353                true,
2354            ),
2355            Field::new(
2356                "_3",
2357                DataType::LargeList(Arc::new(Field::new_list_field(DataType::Utf8, true))),
2358                true,
2359            ),
2360        ]));
2361        let batch = create_random_batch(schema, 10_000, 0.25, 0.75).unwrap();
2362        write_with_cdc_options(
2363            &[&batch],
2364            CDC_MIN_CHUNK_SIZE,
2365            CDC_MAX_CHUNK_SIZE,
2366            None,
2367            true,
2368        );
2369    }
2370
2371    /// Test CDC with deeply nested types: List<List<Int32>>, List<Struct<List<Int32>>>
2372    #[test]
2373    #[cfg_attr(miri, ignore)] // Takes too long
2374    fn test_cdc_deeply_nested_roundtrip() {
2375        let inner_field = Field::new_list_field(DataType::Int32, true);
2376        let inner_type = DataType::List(Arc::new(inner_field));
2377        let outer_field = Field::new_list_field(inner_type.clone(), true);
2378        let list_list_type = DataType::List(Arc::new(outer_field));
2379
2380        let struct_inner_field = Field::new_list_field(DataType::Int32, true);
2381        let struct_inner_type = DataType::List(Arc::new(struct_inner_field));
2382        let struct_fields = Fields::from(vec![Field::new("a", struct_inner_type, true)]);
2383        let struct_type = DataType::Struct(struct_fields);
2384        let struct_list_field = Field::new_list_field(struct_type, true);
2385        let list_struct_type = DataType::List(Arc::new(struct_list_field));
2386
2387        let schema = Arc::new(Schema::new(vec![
2388            Field::new("list_list", list_list_type, true),
2389            Field::new("list_struct_list", list_struct_type, true),
2390        ]));
2391        let batch = create_random_batch(schema, 10_000, 0.25, 0.75).unwrap();
2392        write_with_cdc_options(
2393            &[&batch],
2394            CDC_MIN_CHUNK_SIZE,
2395            CDC_MAX_CHUNK_SIZE,
2396            None,
2397            true,
2398        );
2399    }
2400
2401    /// Test CDC with list arrays that have non-empty null segments.
2402    ///
2403    /// Per the Arrow columnar format spec: "a null value may correspond to a
2404    /// non-empty segment in the child array". This test constructs such arrays
2405    /// manually and verifies the CDC writer handles them correctly.
2406    #[test]
2407    fn test_cdc_list_non_empty_null_segments() {
2408        // Build List<Int32> where null entries own non-zero child ranges:
2409        //   row 0: [1, 2]     offsets[0..2]  valid
2410        //   row 1: null        offsets[2..5]  null, but owns 3 child values
2411        //   row 2: [6, 7]     offsets[5..7]  valid
2412        //   row 3: null        offsets[7..9]  null, but owns 2 child values
2413        //   row 4: [10]        offsets[9..10] valid
2414        let values = Int32Array::from(vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
2415        let offsets = Buffer::from_iter([0_i32, 2, 5, 7, 9, 10]);
2416        let null_bitmap = Buffer::from([0b00010101]); // rows 0, 2, 4 valid
2417
2418        let list_type = DataType::List(Arc::new(Field::new_list_field(DataType::Int32, false)));
2419        let list_data = unsafe {
2420            ArrayData::new_unchecked(
2421                list_type.clone(),
2422                5,
2423                None,
2424                Some(null_bitmap),
2425                0,
2426                vec![offsets],
2427                vec![values.to_data()],
2428            )
2429        };
2430        let list_array = arrow_array::make_array(list_data);
2431
2432        let schema = Arc::new(Schema::new(vec![Field::new("col", list_type, true)]));
2433        let batch = RecordBatch::try_new(schema, vec![list_array]).unwrap();
2434
2435        let buf = write_with_cdc_options(
2436            &[&batch],
2437            CDC_MIN_CHUNK_SIZE,
2438            CDC_MAX_CHUNK_SIZE,
2439            None,
2440            true,
2441        );
2442        let read = concat_batches(read_batches(&buf));
2443        let read_list = read.column(0).as_list::<i32>();
2444        assert_eq!(read_list.len(), 5);
2445        assert!(read_list.is_valid(0));
2446        assert!(read_list.is_null(1));
2447        assert!(read_list.is_valid(2));
2448        assert!(read_list.is_null(3));
2449        assert!(read_list.is_valid(4));
2450
2451        let get_vals = |i: usize| -> Vec<i32> {
2452            read_list
2453                .value(i)
2454                .as_primitive::<arrow_array::types::Int32Type>()
2455                .values()
2456                .iter()
2457                .copied()
2458                .collect()
2459        };
2460        assert_eq!(get_vals(0), vec![1, 2]);
2461        assert_eq!(get_vals(2), vec![6, 7]);
2462        assert_eq!(get_vals(4), vec![10]);
2463    }
2464}