Skip to main content

parquet_variant/variant/
list.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5use crate::decoder::{OffsetSizeBytes, map_bytes_to_offsets};
6use crate::utils::{
7    first_byte_from_slice, overflow_error, slice_from_slice, slice_from_slice_at_offset,
8};
9use crate::variant::{MAX_NESTING_DEPTH, Variant, VariantMetadata};
10
11use arrow_schema::ArrowError;
12
13// The value header occupies one byte; use a named constant for readability
14const NUM_HEADER_BYTES: u32 = 1;
15
16/// A parsed version of the variant array value header byte.
17#[derive(Debug, Clone, PartialEq)]
18pub(crate) struct VariantListHeader {
19    num_elements_size: OffsetSizeBytes,
20    offset_size: OffsetSizeBytes,
21}
22
23impl VariantListHeader {
24    // Hide the ugly casting
25    const fn num_elements_size(&self) -> u32 {
26        self.num_elements_size as _
27    }
28    const fn offset_size(&self) -> u32 {
29        self.offset_size as _
30    }
31
32    // Avoid materializing this offset, since it's cheaply and safely computable
33    const fn first_offset_byte(&self) -> u32 {
34        NUM_HEADER_BYTES + self.num_elements_size()
35    }
36
37    pub(crate) fn try_new(header_byte: u8) -> Result<Self, ArrowError> {
38        // The 6 first bits to the left are the value_header and the 2 bits
39        // to the right are the basic type, so we shift to get only the value_header
40        let value_header = header_byte >> 2;
41        let is_large = (value_header & 0x04) != 0; // 3rd bit from the right
42        let field_offset_size_minus_one = value_header & 0x03; // Last two bits
43
44        // The size of the num_elements entry in the array value_data is 4 bytes if
45        // is_large is true, otherwise 1 byte.
46        let num_elements_size = match is_large {
47            true => OffsetSizeBytes::Four,
48            false => OffsetSizeBytes::One,
49        };
50        let offset_size = OffsetSizeBytes::try_new(field_offset_size_minus_one)?;
51
52        Ok(Self {
53            num_elements_size,
54            offset_size,
55        })
56    }
57}
58
59/// [`Variant`] Array.
60///
61/// See the [Variant spec] for details.
62///
63/// NOTE: The "list" naming differs from the variant spec -- which calls it "array" -- in order to be
64/// consistent with Parquet and Arrow type naming. Otherwise, the name would conflict with the
65/// `VariantArray : Array` we must eventually define for variant-typed arrow arrays.
66///
67/// # Validation
68///
69/// Every instance of variant list is either _valid_ or _invalid_. depending on whether the
70/// underlying bytes are a valid encoding of a variant array (see below).
71///
72/// Instances produced by [`Self::try_new`] or [`Self::with_full_validation`] are fully _validated_. They always
73/// contain _valid_ data, and infallible accesses such as iteration and indexing are panic-free. The
74/// validation cost is linear in the number of underlying bytes.
75///
76/// Instances produced by [`Self::new`] are _unvalidated_ and so they may contain either _valid_ or
77/// _invalid_ data. Infallible accesses such as iteration and indexing will panic if the underlying
78/// bytes are _invalid_, and fallible alternatives such as [`Self::iter_try`] and [`Self::get`] are
79/// provided as panic-free alternatives. [`Self::with_full_validation`] can also be used to _validate_ an
80/// _unvalidated_ instance, if desired.
81///
82/// _Unvalidated_ instances can be constructed in constant time. This can be useful if the caller
83/// knows the underlying bytes were already validated previously, or if the caller intends to
84/// perform a small number of (fallible) accesses to a large list.
85///
86/// A _validated_ variant list instance guarantees that:
87///
88/// - header byte is valid
89/// - num_elements is in bounds
90/// - offset array content is in-bounds
91/// - first offset is zero
92/// - last offset is in-bounds
93/// - all other offsets are in-bounds (*)
94/// - all offsets are monotonically increasing (*)
95/// - all values are (recursively) valid variant objects (*)
96/// - the associated variant metadata is [valid] (*)
97///
98/// NOTE: [`Self::new`] only skips expensive (non-constant cost) validation checks (marked by `(*)`
99/// in the list above); it panics any of the other checks fails.
100///
101/// # Safety
102///
103/// Even an _invalid_ variant list instance is still _safe_ to use in the Rust sense. Accessing
104/// it with infallible methods may cause panics but will never lead to undefined behavior.
105///
106/// [valid]: VariantMetadata#Validation
107/// [Variant spec]: https://github.com/apache/parquet-format/blob/master/VariantEncoding.md#value-data-for-array-basic_type3
108#[derive(Debug, Clone)]
109pub struct VariantList<'m, 'v> {
110    pub metadata: VariantMetadata<'m>,
111    pub value: &'v [u8],
112    header: VariantListHeader,
113    num_elements: u32,
114    first_value_byte: u32,
115    validated: bool,
116}
117
118// We don't want this to grow because it could increase the size of `Variant` and hurt performance.
119#[cfg(target_pointer_width = "64")]
120const _: () = crate::utils::expect_size_of::<VariantList>(64);
121
122#[cfg(target_pointer_width = "32")]
123const _: () = crate::utils::expect_size_of::<VariantList>(40);
124
125impl<'m, 'v> VariantList<'m, 'v> {
126    /// Attempts to interpret `value` as a variant array value.
127    ///
128    /// # Validation
129    ///
130    /// This constructor verifies that `value` points to a valid variant array value. In particular,
131    /// that all offsets are in-bounds and point to valid (recursively validated) objects.
132    pub fn try_new(metadata: VariantMetadata<'m>, value: &'v [u8]) -> Result<Self, ArrowError> {
133        Self::try_new_with_shallow_validation(metadata, value)?.with_full_validation()
134    }
135
136    /// Interprets `metadata` and `value` as a variant list, performing only basic
137    /// (constant-cost) [validation].
138    ///
139    /// # Panics
140    ///
141    /// Panics if basic validation fails. Use [`Self::try_new`] for a fallible version.
142    ///
143    /// [validation]: Self#Validation
144    pub fn new(metadata: VariantMetadata<'m>, value: &'v [u8]) -> Self {
145        Self::try_new_with_shallow_validation(metadata, value).expect("Invalid variant list value")
146    }
147
148    /// Attempts to interpret `metadata` and `value` as a variant array, performing only basic
149    /// (constant-cost) [validation].
150    ///
151    /// [validation]: Self#Validation
152    pub(crate) fn try_new_with_shallow_validation(
153        metadata: VariantMetadata<'m>,
154        value: &'v [u8],
155    ) -> Result<Self, ArrowError> {
156        let header_byte = first_byte_from_slice(value)?;
157        let header = VariantListHeader::try_new(header_byte)?;
158
159        // Skip the header byte to read the num_elements; the offset array immediately follows
160        let num_elements =
161            header
162                .num_elements_size
163                .unpack_u32_at_offset(value, NUM_HEADER_BYTES as _, 0)?;
164
165        // (num_elements + 1) * offset_size + first_offset_byte
166        let first_value_byte = num_elements
167            .checked_add(1)
168            .and_then(|n| n.checked_mul(header.offset_size()))
169            .and_then(|n| n.checked_add(header.first_offset_byte()))
170            .ok_or_else(|| overflow_error("offset of variant list values"))?;
171
172        let mut new_self = Self {
173            metadata,
174            value,
175            header,
176            num_elements,
177            first_value_byte,
178            validated: false,
179        };
180
181        // Validate just the first and last offset, ignoring the other offsets and all value bytes.
182        let first_offset = new_self.get_offset(0)?;
183        if first_offset != 0 {
184            return Err(ArrowError::InvalidArgumentError(format!(
185                "First offset is not zero: {first_offset}"
186            )));
187        }
188
189        // Use the last offset to upper-bound the value buffer
190        let last_offset = new_self
191            .get_offset(num_elements as _)?
192            .checked_add(first_value_byte)
193            .ok_or_else(|| overflow_error("variant array size"))?;
194        new_self.value = slice_from_slice(value, ..last_offset as _)?;
195        Ok(new_self)
196    }
197
198    /// True if this instance is fully [validated] for panic-free infallible accesses.
199    ///
200    /// [validated]: Self#Validation
201    pub fn is_fully_validated(&self) -> bool {
202        self.validated
203    }
204
205    /// Performs a full [validation] of this variant array and returns the result.
206    ///
207    /// Values nested more than [`MAX_NESTING_DEPTH`] deep are rejected.
208    ///
209    /// [validation]: Self#Validation
210    pub fn with_full_validation(self) -> Result<Self, ArrowError> {
211        self.with_full_validation_at_depth(0)
212    }
213
214    // Same as [`Self::with_full_validation`], tracking how deeply validation has recursed.
215    pub(crate) fn with_full_validation_at_depth(
216        mut self,
217        depth: usize,
218    ) -> Result<Self, ArrowError> {
219        if !self.validated {
220            if depth >= MAX_NESTING_DEPTH {
221                return Err(ArrowError::InvalidArgumentError(format!(
222                    "Variant nesting depth exceeds the maximum of {MAX_NESTING_DEPTH}"
223                )));
224            }
225
226            // Validate the metadata dictionary first, if not already validated, because we pass it
227            // by value to all the children (who would otherwise re-validate it repeatedly).
228            self.metadata = self.metadata.with_full_validation()?;
229
230            let offset_buffer = slice_from_slice(
231                self.value,
232                self.header.first_offset_byte() as _..self.first_value_byte as _,
233            )?;
234
235            let value_buffer = slice_from_slice(self.value, self.first_value_byte as _..)?;
236
237            // Validate whether values are valid variant objects
238            //
239            // Since we use offsets to slice into the value buffer, this also verifies all offsets are in-bounds
240            // and monotonically increasing
241            let mut offset_iter = map_bytes_to_offsets(offset_buffer, self.header.offset_size);
242            let mut current_offset = offset_iter.next().unwrap_or(0);
243
244            for next_offset in offset_iter {
245                let value_bytes = slice_from_slice(value_buffer, current_offset..next_offset)?;
246                Variant::try_new_with_metadata_at_depth(
247                    self.metadata.clone(),
248                    value_bytes,
249                    depth + 1,
250                )?;
251                current_offset = next_offset;
252            }
253
254            self.validated = true;
255        }
256        Ok(self)
257    }
258
259    /// Return the length of this array
260    pub fn len(&self) -> usize {
261        self.num_elements as _
262    }
263
264    /// Is the array of zero length
265    pub fn is_empty(&self) -> bool {
266        self.len() == 0
267    }
268
269    /// Returns element by index in `0..self.len()`, if any.
270    ///
271    /// # Panics
272    ///
273    /// Panics if this list is [invalid]. Use [`Self::try_get`] for a fallible version.
274    ///
275    /// [invalid]: Self#Validation
276    pub fn get(&self, index: usize) -> Option<Variant<'m, 'v>> {
277        (index < self.len()).then(|| {
278            self.try_get_with_shallow_validation(index)
279                .expect("Invalid variant array element")
280        })
281    }
282
283    /// Fallible version of `get`. Returns element by index, capturing validation errors
284    pub fn try_get(&self, index: usize) -> Result<Variant<'m, 'v>, ArrowError> {
285        self.try_get_with_shallow_validation(index)?
286            .with_full_validation()
287    }
288
289    // Fallible version of `get`, performing only basic (constant-time) validation.
290    fn try_get_with_shallow_validation(&self, index: usize) -> Result<Variant<'m, 'v>, ArrowError> {
291        // Fetch the value bytes between the two offsets for this index, from the value array region
292        // of the byte buffer
293        let byte_range = self.get_offset(index)? as _..self.get_offset(index + 1)? as _;
294        let value_bytes =
295            slice_from_slice_at_offset(self.value, self.first_value_byte as _, byte_range)?;
296        Variant::try_new_with_metadata_and_shallow_validation(self.metadata.clone(), value_bytes)
297    }
298
299    /// Iterates over the values of this list. When working with [unvalidated] input, consider
300    /// [`Self::iter_try`] to avoid panics due to invalid data.
301    ///
302    /// [unvalidated]: Self#Validation
303    ///
304    /// # Panics
305    ///
306    /// Panics if the underlying bytes are invalid. Use [`Self::iter_try`] for a
307    /// fallible version.
308    pub fn iter(&self) -> impl Iterator<Item = Variant<'m, 'v>> + '_ {
309        self.iter_try_with_shallow_validation()
310            .map(|result| result.expect("Invalid variant list entry"))
311    }
312
313    /// Fallible iteration over the elements of this list.
314    pub fn iter_try(&self) -> impl Iterator<Item = Result<Variant<'m, 'v>, ArrowError>> + '_ {
315        self.iter_try_with_shallow_validation()
316            .map(|result| result?.with_full_validation())
317    }
318
319    // Fallible iteration that only performs basic (constant-time) validation.
320    fn iter_try_with_shallow_validation(
321        &self,
322    ) -> impl Iterator<Item = Result<Variant<'m, 'v>, ArrowError>> + '_ {
323        (0..self.len()).map(|i| self.try_get_with_shallow_validation(i))
324    }
325
326    // Attempts to retrieve the ith offset from the offset array region of the byte buffer.
327    fn get_offset(&self, index: usize) -> Result<u32, ArrowError> {
328        let byte_range = self.header.first_offset_byte() as _..self.first_value_byte as _;
329        let offset_bytes = slice_from_slice(self.value, byte_range)?;
330        self.header.offset_size.unpack_u32(offset_bytes, index)
331    }
332}
333
334// Custom implementation of PartialEq for variant arrays
335//
336// Instead of comparing the raw bytes of 2 variant lists, this implementation recursively
337// checks whether their elements are equal.
338impl PartialEq for VariantList<'_, '_> {
339    fn eq(&self, other: &Self) -> bool {
340        if self.num_elements != other.num_elements {
341            return false;
342        }
343
344        self.iter().zip(other.iter()).all(|(a, b)| a == b)
345    }
346}
347
348#[cfg(test)]
349mod tests {
350    use super::*;
351    use crate::VariantBuilder;
352    use std::iter::repeat_n;
353    use std::ops::Range;
354
355    #[test]
356    fn test_variant_list_simple() {
357        // Create simple metadata (empty dictionary for this test)
358        let metadata_bytes = vec![
359            0x01, // header: version=1, sorted=0, offset_size_minus_one=0
360            0,    // dictionary_size = 0
361            0,    // offset[0] = 0 (end of dictionary)
362        ];
363        let metadata = VariantMetadata::try_new(&metadata_bytes).unwrap();
364
365        // Create list value data for: [42, true, "hi"]
366        // Header: basic_type=3 (array), field_offset_size_minus_one=0, is_large=0
367        // value_header = 0000_0_0_00 = 0x00
368        // So header byte = (0x00 << 2) | 3 = 0x03
369        let list_value = vec![
370            0x03, // header: basic_type=3, value_header=0x00
371            3,    // num_elements = 3
372            // Offsets (1 byte each): 4 offsets total
373            0, // offset to first value (int8)
374            2, // offset to second value (boolean true)
375            3, // offset to third value (short string)
376            6, // end offset
377            // Values:
378            0x0C,
379            42,   // int8: primitive_header=3, basic_type=0 -> (3 << 2) | 0 = 0x0C, then value 42
380            0x04, // boolean true: primitive_header=1, basic_type=0 -> (1 << 2) | 0 = 0x04
381            0x09, b'h', b'i', // short string: length=2, basic_type=1 -> (2 << 2) | 1 = 0x09
382        ];
383
384        let variant_list = VariantList::try_new(metadata, &list_value).unwrap();
385
386        // Test basic properties
387        assert_eq!(variant_list.len(), 3);
388        assert!(!variant_list.is_empty());
389
390        // Test individual element access
391        let elem0 = variant_list.get(0).unwrap();
392        assert_eq!(elem0.as_int8(), Some(42));
393
394        let elem1 = variant_list.get(1).unwrap();
395        assert_eq!(elem1.as_boolean(), Some(true));
396
397        let elem2 = variant_list.get(2).unwrap();
398        assert_eq!(elem2.as_string(), Some("hi"));
399
400        // Test out of bounds access
401        let out_of_bounds = variant_list.get(3);
402        assert!(out_of_bounds.is_none());
403
404        // Test values iterator
405        let values: Vec<_> = variant_list.iter().collect();
406        assert_eq!(values.len(), 3);
407        assert_eq!(values[0].as_int8(), Some(42));
408        assert_eq!(values[1].as_boolean(), Some(true));
409        assert_eq!(values[2].as_string(), Some("hi"));
410    }
411
412    #[test]
413    fn test_variant_list_empty() {
414        // Create simple metadata (empty dictionary)
415        let metadata_bytes = vec![
416            0x01, // header: version=1, sorted=0, offset_size_minus_one=0
417            0,    // dictionary_size = 0
418            0,    // offset[0] = 0 (end of dictionary)
419        ];
420        let metadata = VariantMetadata::try_new(&metadata_bytes).unwrap();
421
422        // Create empty list value data: []
423        let list_value = vec![
424            0x03, // header: basic_type=3, value_header=0x00
425            0,    // num_elements = 0
426            0,    // single offset pointing to end
427                  // No values
428        ];
429
430        let variant_list = VariantList::try_new(metadata, &list_value).unwrap();
431
432        // Test basic properties
433        assert_eq!(variant_list.len(), 0);
434        assert!(variant_list.is_empty());
435
436        // Test out of bounds access on empty list
437        let out_of_bounds = variant_list.get(0);
438        assert!(out_of_bounds.is_none());
439
440        // Test values iterator on empty list
441        let values: Vec<_> = variant_list.iter().collect();
442        assert_eq!(values.len(), 0);
443    }
444
445    #[test]
446    fn test_variant_list_large() {
447        // Create simple metadata (empty dictionary)
448        let metadata_bytes = vec![
449            0x01, // header: version=1, sorted=0, offset_size_minus_one=0
450            0,    // dictionary_size = 0
451            0,    // offset[0] = 0 (end of dictionary)
452        ];
453        let metadata = VariantMetadata::try_new(&metadata_bytes).unwrap();
454
455        // Create large list value data with 2-byte offsets: [null, false]
456        // Header: is_large=1, field_offset_size_minus_one=1, basic_type=3 (array)
457        let list_bytes = vec![
458            0x17, // header = 000_1_01_11 = 0x17
459            2, 0, 0, 0, // num_elements = 2 (4 bytes because is_large=1)
460            // Offsets (2 bytes each): 3 offsets total
461            0x00, 0x00, 0x01, 0x00, // first value (null)
462            0x02, 0x00, // second value (boolean false)
463            // Values:
464            0x00, // null: primitive_header=0, basic_type=0 -> (0 << 2) | 0 = 0x00
465            0x08, // boolean false: primitive_header=2, basic_type=0 -> (2 << 2) | 0 = 0x08
466        ];
467
468        let variant_list = VariantList::try_new(metadata, &list_bytes).unwrap();
469
470        // Test basic properties
471        assert_eq!(variant_list.len(), 2);
472        assert!(!variant_list.is_empty());
473
474        // Test individual element access
475        let elem0 = variant_list.get(0).unwrap();
476        assert_eq!(elem0.as_null(), Some(()));
477
478        let elem1 = variant_list.get(1).unwrap();
479        assert_eq!(elem1.as_boolean(), Some(false));
480    }
481
482    #[test]
483    fn test_large_variant_list_with_total_child_length_between_2_pow_8_and_2_pow_16() {
484        // all the tests below will set the total child size to ~500,
485        // which is larger than 2^8 but less than 2^16.
486        // total child size = list_size * single_child_item_len
487
488        let mut list_size: usize = 1;
489        let mut single_child_item_len: usize = 500;
490
491        // offset size will be OffSizeBytes::Two as the total child length between 2^8 and 2^16
492        let expected_offset_size = OffsetSizeBytes::Two;
493
494        test_large_variant_list_with_child_length(
495            list_size,             // the elements in the list
496            single_child_item_len, // this will control the total child size in the list
497            OffsetSizeBytes::One, // will be OffsetSizeBytes::One as the size of the list is less than 256
498            expected_offset_size,
499        );
500
501        list_size = 255;
502        single_child_item_len = 2;
503        test_large_variant_list_with_child_length(
504            list_size,
505            single_child_item_len,
506            OffsetSizeBytes::One, // will be OffsetSizeBytes::One as the size of the list is less than 256
507            expected_offset_size,
508        );
509
510        list_size = 256;
511        single_child_item_len = 2;
512        test_large_variant_list_with_child_length(
513            list_size,
514            single_child_item_len,
515            OffsetSizeBytes::Four, // will be OffsetSizeBytes::Four as the size of the list is bigger than 255
516            expected_offset_size,
517        );
518
519        list_size = 300;
520        single_child_item_len = 2;
521        test_large_variant_list_with_child_length(
522            list_size,
523            single_child_item_len,
524            OffsetSizeBytes::Four, // will be OffsetSizeBytes::Four as the size of the list is bigger than 255
525            expected_offset_size,
526        );
527    }
528
529    #[test]
530    fn test_large_variant_list_with_total_child_length_between_2_pow_16_and_2_pow_24() {
531        // all the tests below will set the total child size to ~70,000,
532        // which is larger than 2^16 but less than 2^24.
533        // total child size = list_size * single_child_item_len
534
535        let mut list_size: usize = 1;
536        let mut single_child_item_len: usize = 70000;
537
538        // offset size will be OffSizeBytes::Two as the total child length between 2^16 and 2^24
539        let expected_offset_size = OffsetSizeBytes::Three;
540
541        test_large_variant_list_with_child_length(
542            list_size,
543            single_child_item_len,
544            OffsetSizeBytes::One, // will be OffsetSizeBytes::One as the size of the list is less than 256
545            expected_offset_size,
546        );
547
548        list_size = 255;
549        single_child_item_len = 275;
550        // total child size = 255 * 275 = 70,125
551        test_large_variant_list_with_child_length(
552            list_size,
553            single_child_item_len,
554            OffsetSizeBytes::One, // will be OffsetSizeBytes::One as the size of the list is less than 256
555            expected_offset_size,
556        );
557
558        list_size = 256;
559        single_child_item_len = 274;
560        // total child size = 256 * 274 = 70,144
561        test_large_variant_list_with_child_length(
562            list_size,
563            single_child_item_len,
564            OffsetSizeBytes::Four, // will be OffsetSizeBytes::Four as the size of the list is bigger than 255
565            expected_offset_size,
566        );
567
568        list_size = 300;
569        single_child_item_len = 234;
570        // total child size = 300 * 234 = 70,200
571        test_large_variant_list_with_child_length(
572            list_size,
573            single_child_item_len,
574            OffsetSizeBytes::Four, // will be OffsetSizeBytes::Four as the size of the list is bigger than 255
575            expected_offset_size,
576        );
577    }
578
579    #[test]
580    fn test_large_variant_list_with_total_child_length_between_2_pow_24_and_2_pow_32() {
581        // all the tests below will set the total child size to ~20,000,000,
582        // which is larger than 2^24 but less than 2^32.
583        // total child size = list_size * single_child_item_len
584
585        let mut list_size: usize = 1;
586        let mut single_child_item_len: usize = 20000000;
587
588        // offset size will be OffSizeBytes::Two as the total child length between 2^24 and 2^32
589        let expected_offset_size = OffsetSizeBytes::Four;
590
591        test_large_variant_list_with_child_length(
592            list_size,
593            single_child_item_len,
594            OffsetSizeBytes::One, // will be OffsetSizeBytes::One as the size of the list is less than 256
595            expected_offset_size,
596        );
597
598        list_size = 255;
599        single_child_item_len = 78432;
600        // total child size = 255 * 78,432 = 20,000,160
601        test_large_variant_list_with_child_length(
602            list_size,
603            single_child_item_len,
604            OffsetSizeBytes::One, // will be OffsetSizeBytes::One as the size of the list is less than 256
605            expected_offset_size,
606        );
607
608        list_size = 256;
609        single_child_item_len = 78125;
610        // total child size = 256 * 78,125 = 20,000,000
611        test_large_variant_list_with_child_length(
612            list_size,
613            single_child_item_len,
614            OffsetSizeBytes::Four, // will be OffsetSizeBytes::Four as the size of the list is bigger than 255
615            expected_offset_size,
616        );
617
618        list_size = 300;
619        single_child_item_len = 66667;
620        // total child size = 300 * 66,667 = 20,000,100
621        test_large_variant_list_with_child_length(
622            list_size,
623            single_child_item_len,
624            OffsetSizeBytes::Four, // will be OffsetSizeBytes::Four as the size of the list is bigger than 255
625            expected_offset_size,
626        );
627    }
628
629    // this function will create a large variant list from VariantBuilder
630    // with specified size and each child item with the given length.
631    // and verify the content and some meta for the variant list in the final.
632    fn test_large_variant_list_with_child_length(
633        list_size: usize,
634        single_child_item_len: usize,
635        expected_num_element_size: OffsetSizeBytes,
636        expected_offset_size_bytes: OffsetSizeBytes,
637    ) {
638        let mut builder = VariantBuilder::new();
639        let mut list_builder = builder.new_list();
640
641        let mut expected_list = vec![];
642        for i in 0..list_size {
643            let random_string: String =
644                repeat_n(char::from((i % 256) as u8), single_child_item_len).collect();
645
646            list_builder.append_value(Variant::String(random_string.as_str()));
647            expected_list.push(random_string);
648        }
649
650        list_builder.finish();
651        // Finish the builder to get the metadata and value
652        let (metadata, value) = builder.finish();
653        // use the Variant API to verify the result
654        let variant = Variant::try_new(&metadata, &value).unwrap();
655
656        let variant_list = variant.as_list().unwrap();
657
658        // verify that the head is expected
659        assert_eq!(expected_offset_size_bytes, variant_list.header.offset_size);
660        assert_eq!(
661            expected_num_element_size,
662            variant_list.header.num_elements_size
663        );
664        assert_eq!(list_size, variant_list.num_elements as usize);
665
666        // verify the data in the variant
667        assert_eq!(list_size, variant_list.len());
668        for i in 0..list_size {
669            let item = variant_list.get(i).unwrap();
670            let item_str = item.as_string().unwrap();
671            assert_eq!(expected_list.get(i).unwrap(), item_str);
672        }
673    }
674
675    #[test]
676    fn test_variant_list_equality() {
677        // Create two lists with the same values (0..10)
678        let (metadata1, value1) = make_listi32(0..10);
679        let list1 = Variant::new(&metadata1, &value1);
680        let (metadata2, value2) = make_listi32(0..10);
681        let list2 = Variant::new(&metadata2, &value2);
682        // They should be equal
683        assert_eq!(list1, list2);
684    }
685
686    #[test]
687    fn test_variant_list_equality_different_length() {
688        // Create two lists with different lengths
689        let (metadata1, value1) = make_listi32(0..10);
690        let list1 = Variant::new(&metadata1, &value1);
691        let (metadata2, value2) = make_listi32(0..5);
692        let list2 = Variant::new(&metadata2, &value2);
693        // They should not be equal
694        assert_ne!(list1, list2);
695    }
696
697    #[test]
698    fn test_variant_list_equality_different_values() {
699        // Create two lists with different values
700        let (metadata1, value1) = make_listi32(0..10);
701        let list1 = Variant::new(&metadata1, &value1);
702        let (metadata2, value2) = make_listi32(5..15);
703        let list2 = Variant::new(&metadata2, &value2);
704        // They should not be equal
705        assert_ne!(list1, list2);
706    }
707
708    #[test]
709    fn test_variant_list_equality_different_types() {
710        // Create two lists with different types
711        let (metadata1, value1) = make_listi32(0i32..10i32);
712        let list1 = Variant::new(&metadata1, &value1);
713        let (metadata2, value2) = make_listi64(0..10);
714        let list2 = Variant::new(&metadata2, &value2);
715        // They should not be equal due to type mismatch
716        assert_ne!(list1, list2);
717    }
718
719    #[test]
720    fn test_variant_list_equality_slices() {
721        // Make an object like this and make sure equality works
722        // when the lists are sub fields
723        //
724        // {
725        //   "list1": [0, 1, 2, ..., 9],
726        //   "list2": [0, 1, 2, ..., 9],
727        //   "list3": [10, 11, 12, ..., 19],
728        //  }
729        let (metadata, value) = {
730            let mut builder = VariantBuilder::new();
731            let mut object_builder = builder.new_object();
732            // list1 (0..10)
733            let (metadata1, value1) = make_listi32(0i32..10i32);
734            object_builder.insert("list1", Variant::new(&metadata1, &value1));
735
736            // list2 (0..10)
737            let (metadata2, value2) = make_listi32(0i32..10i32);
738            object_builder.insert("list2", Variant::new(&metadata2, &value2));
739
740            // list3 (10..20)
741            let (metadata3, value3) = make_listi32(10i32..20i32);
742            object_builder.insert("list3", Variant::new(&metadata3, &value3));
743            object_builder.finish();
744            builder.finish()
745        };
746
747        let variant = Variant::try_new(&metadata, &value).unwrap();
748        let object = variant.as_object().unwrap();
749        // Check that list1 and list2 are equal
750        assert_eq!(object.get("list1").unwrap(), object.get("list2").unwrap());
751        // Check that list1 and list3 are not equal
752        assert_ne!(object.get("list1").unwrap(), object.get("list3").unwrap());
753    }
754
755    /// return the value bytes for `depth` single-element lists nested around a null
756    fn make_nested_lists(depth: usize) -> Vec<u8> {
757        let mut value = vec![0u8]; // null primitive
758        for _ in 0..depth {
759            // header: array basic type, 4-byte offsets, then num_elements=1 and two offsets
760            let mut outer = vec![0x0F, 1];
761            outer.extend_from_slice(&0u32.to_le_bytes());
762            outer.extend_from_slice(&(value.len() as u32).to_le_bytes());
763            outer.append(&mut value);
764            value = outer;
765        }
766        value
767    }
768
769    #[test]
770    fn test_variant_list_nesting_depth_limit() {
771        let metadata = [0x01, 0, 0]; // empty dictionary
772
773        let value = make_nested_lists(MAX_NESTING_DEPTH);
774        Variant::try_new(&metadata, &value).unwrap();
775
776        // One level deeper would recurse past the limit -- previously a stack overflow
777        let value = make_nested_lists(MAX_NESTING_DEPTH + 1);
778        let err = Variant::try_new(&metadata, &value).unwrap_err();
779        assert!(
780            err.to_string().contains("nesting depth exceeds"),
781            "unexpected error: {err}"
782        );
783    }
784
785    /// return metadata/value for a simple variant list with values in a range
786    fn make_listi32(range: Range<i32>) -> (Vec<u8>, Vec<u8>) {
787        let mut variant_builder = VariantBuilder::new();
788        let mut list_builder = variant_builder.new_list();
789        list_builder.extend(range);
790        list_builder.finish();
791        variant_builder.finish()
792    }
793
794    /// return metadata/value for a simple variant list with values in a range
795    fn make_listi64(range: Range<i64>) -> (Vec<u8>, Vec<u8>) {
796        let mut variant_builder = VariantBuilder::new();
797        let mut list_builder = variant_builder.new_list();
798        list_builder.extend(range);
799        list_builder.finish();
800        variant_builder.finish()
801    }
802}