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}