Skip to main content

parquet_variant/variant/
object.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, try_binary_search_range_by,
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/// Header structure for [`VariantObject`]
17#[derive(Debug, Clone, PartialEq)]
18pub(crate) struct VariantObjectHeader {
19    num_elements_size: OffsetSizeBytes,
20    field_id_size: OffsetSizeBytes,
21    field_offset_size: OffsetSizeBytes,
22}
23
24impl VariantObjectHeader {
25    // Hide the ugly casting
26    const fn num_elements_size(&self) -> u32 {
27        self.num_elements_size as _
28    }
29    const fn field_id_size(&self) -> u32 {
30        self.field_id_size as _
31    }
32    const fn field_offset_size(&self) -> u32 {
33        self.field_offset_size as _
34    }
35
36    // Avoid materializing this offset, since it's cheaply and safely computable
37    const fn field_ids_start_byte(&self) -> u32 {
38        NUM_HEADER_BYTES + self.num_elements_size()
39    }
40
41    pub(crate) fn try_new(header_byte: u8) -> Result<Self, ArrowError> {
42        // Parse the header byte to get object parameters
43        let value_header = header_byte >> 2;
44        let field_offset_size_minus_one = value_header & 0x03; // Last 2 bits
45        let field_id_size_minus_one = (value_header >> 2) & 0x03; // Next 2 bits
46        let is_large = (value_header & 0x10) != 0; // 5th bit
47        let num_elements_size = match is_large {
48            true => OffsetSizeBytes::Four,
49            false => OffsetSizeBytes::One,
50        };
51        Ok(Self {
52            num_elements_size,
53            field_id_size: OffsetSizeBytes::try_new(field_id_size_minus_one)?,
54            field_offset_size: OffsetSizeBytes::try_new(field_offset_size_minus_one)?,
55        })
56    }
57}
58
59/// A [`Variant`] Object (struct with named fields).
60///
61/// See the [Variant spec] file for more information.
62///
63/// # Validation
64///
65/// Every instance of variant object is either _valid_ or _invalid_. depending on whether the
66/// underlying bytes are a valid encoding of a variant object subtype (see below).
67///
68/// Instances produced by [`Self::try_new`] or [`Self::with_full_validation`] are fully (and recursively)
69/// _validated_. They always contain _valid_ data, and infallible accesses such as iteration and
70/// indexing are panic-free. The validation cost is linear in the number of underlying bytes.
71///
72/// Instances produced by [`Self::new`] are _unvalidated_ and so they may contain either _valid_ or
73/// _invalid_ data. Infallible accesses such as iteration and indexing will panic if the underlying
74/// bytes are _invalid_, and fallible alternatives such as [`Self::iter_try`] and [`Self::get`] are
75/// provided as panic-free alternatives. [`Self::with_full_validation`] can also be used to _validate_ an
76/// _unvalidated_ instance, if desired.
77///
78/// _Unvalidated_ instances can be constructed in constant time. They can be useful if the caller
79/// knows the underlying bytes were already validated previously, or if the caller intends to
80/// perform a small number of (fallible) field accesses against a large object.
81///
82/// A _validated_ instance guarantees that:
83///
84/// - header byte is valid
85/// - num_elements is in bounds
86/// - field id array is in bounds
87/// - field offset array is in bounds
88/// - field value array is in bounds
89/// - all field ids are valid metadata dictionary entries (*)
90/// - field ids are lexically ordered according by their corresponding string values (*)
91/// - field names are unique; no field name appears more than once (*)
92/// - all field offsets are in bounds (*)
93/// - all field values are (recursively) _valid_ variant values (*)
94/// - the associated variant metadata is [valid] (*)
95///
96/// NOTE: [`Self::new`] only skips expensive (non-constant cost) validation checks (marked by `(*)`
97/// in the list above); it panics any of the other checks fails.
98///
99/// # Safety
100///
101/// Even an _invalid_ variant object instance is still _safe_ to use in the Rust sense. Accessing it
102/// with infallible methods may cause panics but will never lead to undefined behavior.
103///
104/// [valid]: VariantMetadata#Validation
105/// [Variant spec]: https://github.com/apache/parquet-format/blob/master/VariantEncoding.md#value-data-for-object-basic_type2
106#[derive(Debug, Clone)]
107pub struct VariantObject<'m, 'v> {
108    pub metadata: VariantMetadata<'m>,
109    pub value: &'v [u8],
110    header: VariantObjectHeader,
111    num_elements: u32,
112    first_field_offset_byte: u32,
113    first_value_byte: u32,
114    validated: bool,
115}
116
117// We don't want this to grow because it could increase the size of `Variant` and hurt performance.
118#[cfg(target_pointer_width = "64")]
119const _: () = crate::utils::expect_size_of::<VariantObject>(64);
120
121#[cfg(target_pointer_width = "32")]
122const _: () = crate::utils::expect_size_of::<VariantObject>(44);
123
124impl<'m, 'v> VariantObject<'m, 'v> {
125    /// Interprets `metadata` and `value` as a variant object, performing only basic
126    /// (constant-cost) [validation].
127    ///
128    /// # Panics
129    ///
130    /// Panics if basic validation fails. Use [`Self::try_new`] for a fallible version.
131    ///
132    /// [validation]: Self#Validation
133    pub fn new(metadata: VariantMetadata<'m>, value: &'v [u8]) -> Self {
134        Self::try_new_with_shallow_validation(metadata, value).expect("Invalid variant object")
135    }
136
137    /// Attempts to interpret `metadata` and `value` as a variant object.
138    ///
139    /// # Validation
140    ///
141    /// This constructor verifies that `value` points to a valid variant object value. In
142    /// particular, that all field ids exist in `metadata`, and all offsets are in-bounds and point
143    /// to valid objects.
144    pub fn try_new(metadata: VariantMetadata<'m>, value: &'v [u8]) -> Result<Self, ArrowError> {
145        Self::try_new_with_shallow_validation(metadata, value)?.with_full_validation()
146    }
147
148    /// Attempts to interpret `metadata` and `value` as a variant object, 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 = VariantObjectHeader::try_new(header_byte)?;
158
159        // Determine num_elements size based on is_large flag and fetch the value
160        let num_elements =
161            header
162                .num_elements_size
163                .unpack_u32_at_offset(value, NUM_HEADER_BYTES as _, 0)?;
164
165        // Calculate byte offsets for field offsets and values with overflow protection, and verify
166        // they're in bounds
167        let first_field_offset_byte = num_elements
168            .checked_mul(header.field_id_size())
169            .and_then(|n| n.checked_add(header.field_ids_start_byte()))
170            .ok_or_else(|| overflow_error("offset of variant object field offsets"))?;
171
172        let first_value_byte = num_elements
173            .checked_add(1)
174            .and_then(|n| n.checked_mul(header.field_offset_size()))
175            .and_then(|n| n.checked_add(first_field_offset_byte))
176            .ok_or_else(|| overflow_error("offset of variant object field values"))?;
177
178        let mut new_self = Self {
179            metadata,
180            value,
181            header,
182            num_elements,
183            first_field_offset_byte,
184            first_value_byte,
185            validated: false,
186        };
187
188        // Spec says: "The last field_offset points to the byte after the end of the last value"
189        //
190        // Use it to upper-bound the value bytes, which also verifies that the field id and field
191        // offset arrays are in bounds.
192        let last_offset = new_self
193            .get_offset(num_elements as _)?
194            .checked_add(first_value_byte)
195            .ok_or_else(|| overflow_error("variant object size"))?;
196        new_self.value = slice_from_slice(value, ..last_offset as _)?;
197        Ok(new_self)
198    }
199
200    /// True if this instance is fully [validated] for panic-free infallible accesses.
201    ///
202    /// [validated]: Self#Validation
203    pub fn is_fully_validated(&self) -> bool {
204        self.validated
205    }
206
207    /// Performs a full [validation] of this variant object.
208    ///
209    /// Values nested more than [`MAX_NESTING_DEPTH`] deep are rejected.
210    ///
211    /// [validation]: Self#Validation
212    pub fn with_full_validation(self) -> Result<Self, ArrowError> {
213        self.with_full_validation_at_depth(0)
214    }
215
216    // Same as [`Self::with_full_validation`], tracking how deeply validation has recursed.
217    pub(crate) fn with_full_validation_at_depth(
218        mut self,
219        depth: usize,
220    ) -> Result<Self, ArrowError> {
221        if !self.validated {
222            if depth >= MAX_NESTING_DEPTH {
223                return Err(ArrowError::InvalidArgumentError(format!(
224                    "Variant nesting depth exceeds the maximum of {MAX_NESTING_DEPTH}"
225                )));
226            }
227
228            // Validate the metadata dictionary first, if not already validated, because we pass it
229            // by value to all the children (who would otherwise re-validate it repeatedly).
230            self.metadata = self.metadata.with_full_validation()?;
231
232            let field_id_buffer = slice_from_slice(
233                self.value,
234                self.header.field_ids_start_byte() as _..self.first_field_offset_byte as _,
235            )?;
236
237            let mut field_ids_iter =
238                map_bytes_to_offsets(field_id_buffer, self.header.field_id_size);
239
240            // Validate all field ids exist in the metadata dictionary and the corresponding field names are lexicographically sorted
241            if self.metadata.is_sorted() {
242                // Since the metadata dictionary has unique and sorted field names, we can also guarantee this object's field names
243                // are lexicographically sorted by their field id ordering
244                let dictionary_size = self.metadata.len();
245
246                if let Some(mut current_id) = field_ids_iter.next() {
247                    for next_id in field_ids_iter {
248                        if current_id >= dictionary_size {
249                            return Err(ArrowError::InvalidArgumentError(
250                                "field id is not valid".to_string(),
251                            ));
252                        }
253
254                        if next_id <= current_id {
255                            return Err(ArrowError::InvalidArgumentError(
256                                "field names not sorted".to_string(),
257                            ));
258                        }
259                        current_id = next_id;
260                    }
261
262                    if current_id >= dictionary_size {
263                        return Err(ArrowError::InvalidArgumentError(
264                            "field id is not valid".to_string(),
265                        ));
266                    }
267                }
268            } else {
269                // The metadata dictionary can't guarantee uniqueness or sortedness, so we have to parse out the corresponding field names
270                // to check lexicographical order
271                //
272                // Since we are probing the metadata dictionary by field id, this also verifies field ids are in-bounds
273                let mut current_field_name = match field_ids_iter.next() {
274                    Some(field_id) => Some(self.metadata.get(field_id)?),
275                    None => None,
276                };
277
278                for field_id in field_ids_iter {
279                    let next_field_name = self.metadata.get(field_id)?;
280
281                    // Equal names are rejected as well: field names must be unique within an
282                    // object. The sorted branch above enforces this via strictly ordered ids.
283                    if let Some(current_name) = current_field_name
284                        && next_field_name <= current_name
285                    {
286                        return Err(ArrowError::InvalidArgumentError(
287                            "field names not sorted".to_string(),
288                        ));
289                    }
290                    current_field_name = Some(next_field_name);
291                }
292            }
293
294            // Validate whether values are valid variant objects
295            let field_offset_buffer = slice_from_slice(
296                self.value,
297                self.first_field_offset_byte as _..self.first_value_byte as _,
298            )?;
299            let num_offsets = field_offset_buffer.len() / self.header.field_offset_size() as usize;
300
301            let value_buffer = slice_from_slice(self.value, self.first_value_byte as _..)?;
302
303            map_bytes_to_offsets(field_offset_buffer, self.header.field_offset_size)
304                .take(num_offsets.saturating_sub(1))
305                .try_for_each(|offset| {
306                    let value_bytes = slice_from_slice(value_buffer, offset..)?;
307                    Variant::try_new_with_metadata_at_depth(
308                        self.metadata.clone(),
309                        value_bytes,
310                        depth + 1,
311                    )?;
312
313                    Ok::<_, ArrowError>(())
314                })?;
315
316            self.validated = true;
317        }
318        Ok(self)
319    }
320
321    /// Returns the number of key-value pairs in this object
322    pub fn len(&self) -> usize {
323        self.num_elements as _
324    }
325
326    /// Returns true if the object contains no key-value pairs
327    pub fn is_empty(&self) -> bool {
328        self.len() == 0
329    }
330
331    /// Get a field's value by index in `0..self.len()`
332    ///
333    /// # Panics
334    ///
335    /// If the index is out of bounds. Also if variant object is corrupted (e.g., invalid offsets or
336    /// field IDs). The latter can only happen when working with an unvalidated object produced by
337    /// [`Self::new`].
338    pub fn field(&self, i: usize) -> Option<Variant<'m, 'v>> {
339        (i < self.len()).then(|| {
340            self.try_field_with_shallow_validation(i)
341                .expect("Invalid object field value")
342        })
343    }
344
345    /// Fallible version of `field`. Returns field value by index, capturing validation errors
346    pub fn try_field(&self, i: usize) -> Result<Variant<'m, 'v>, ArrowError> {
347        self.try_field_with_shallow_validation(i)?
348            .with_full_validation()
349    }
350
351    // Attempts to retrieve the ith field value from the value region of the byte buffer; it
352    // performs only basic (constant-cost) validation.
353    fn try_field_with_shallow_validation(&self, i: usize) -> Result<Variant<'m, 'v>, ArrowError> {
354        let value_bytes = slice_from_slice(self.value, self.first_value_byte as _..)?;
355        let value_bytes = slice_from_slice(value_bytes, self.get_offset(i)? as _..)?;
356        Variant::try_new_with_metadata_and_shallow_validation(self.metadata.clone(), value_bytes)
357    }
358
359    // Attempts to retrieve the ith offset from the field offset region of the byte buffer.
360    fn get_offset(&self, i: usize) -> Result<u32, ArrowError> {
361        let byte_range = self.first_field_offset_byte as _..self.first_value_byte as _;
362        let field_offsets = slice_from_slice(self.value, byte_range)?;
363        self.header.field_offset_size.unpack_u32(field_offsets, i)
364    }
365
366    /// Get a field's name by index in `0..self.len()`
367    ///
368    /// # Panics
369    /// If the variant object is corrupted (e.g., invalid offsets or field IDs).
370    /// This should never happen since the constructor validates all data upfront.
371    pub fn field_name(&self, i: usize) -> Option<&'m str> {
372        (i < self.len()).then(|| {
373            self.try_field_name(i)
374                .expect("Invalid variant object field name")
375        })
376    }
377
378    /// Fallible version of `field_name`. Returns field name by index, capturing validation errors
379    fn try_field_name(&self, i: usize) -> Result<&'m str, ArrowError> {
380        let byte_range = self.header.field_ids_start_byte() as _..self.first_field_offset_byte as _;
381        let field_id_bytes = slice_from_slice(self.value, byte_range)?;
382        let field_id = self.header.field_id_size.unpack_u32(field_id_bytes, i)?;
383        self.metadata.get(field_id as _)
384    }
385
386    /// Returns an iterator of (name, value) pairs over the fields of this object.
387    ///
388    /// # Panics
389    ///
390    /// Panics if this object is invalid. Use [`Self::iter_try`] for a fallible version.
391    pub fn iter(&self) -> impl Iterator<Item = (&'m str, Variant<'m, 'v>)> + '_ {
392        self.iter_try_with_shallow_validation()
393            .map(|result| result.expect("Invalid variant object field value"))
394    }
395
396    /// Fallible iteration over the fields of this object.
397    pub fn iter_try(
398        &self,
399    ) -> impl Iterator<Item = Result<(&'m str, Variant<'m, 'v>), ArrowError>> + '_ {
400        self.iter_try_with_shallow_validation().map(|result| {
401            let (name, value) = result?;
402            Ok((name, value.with_full_validation()?))
403        })
404    }
405
406    // Fallible iteration over the fields of this object that performs only shallow (constant-cost)
407    // validation of field values.
408    fn iter_try_with_shallow_validation(
409        &self,
410    ) -> impl Iterator<Item = Result<(&'m str, Variant<'m, 'v>), ArrowError>> + '_ {
411        (0..self.len()).map(|i| {
412            let field = self.try_field_with_shallow_validation(i)?;
413            Ok((self.try_field_name(i)?, field))
414        })
415    }
416
417    /// Returns the value of the field with the specified name, if any.
418    ///
419    /// Returns `Some(Variant)` if the field exists, or `None` if the field does not exist.
420    pub fn get(&self, name: &str) -> Option<Variant<'m, 'v>> {
421        // Binary search through the field IDs of this object to find the requested field name.
422        //
423        // NOTE: This does not require a sorted metadata dictionary, because the variant spec
424        // requires object field ids to be lexically sorted by their corresponding string values,
425        // and probing the dictionary for a field id is always O(1) work.
426        let cmp = |i| Some(self.field_name(i)?.cmp(name));
427        let i = try_binary_search_range_by(0..self.len(), cmp)?.ok()?;
428        self.field(i)
429    }
430}
431
432// Custom implementation of PartialEq for variant objects
433//
434// According to the spec, field values are not required to be in the same order as the field IDs,
435// to enable flexibility when constructing Variant values
436//
437// Instead of comparing the raw bytes of 2 variant objects, this implementation recursively
438// checks whether the field values are equal -- regardless of their order
439impl PartialEq for VariantObject<'_, '_> {
440    fn eq(&self, other: &Self) -> bool {
441        if self.num_elements != other.num_elements {
442            return false;
443        }
444
445        // IFF two objects are valid and logically equal, they will have the same
446        // field names in the same order, because the spec requires the object
447        // fields to be sorted lexicographically.
448        self.iter()
449            .zip(other.iter())
450            .all(|((name_a, value_a), (name_b, value_b))| name_a == name_b && value_a == value_b)
451    }
452}
453
454#[cfg(test)]
455mod tests {
456    use crate::VariantBuilder;
457
458    use super::*;
459
460    #[test]
461    fn test_variant_object_simple() {
462        // Create metadata with field names: "age", "name", "active" (sorted)
463        // Header: version=1, sorted=1, offset_size=1 (offset_size_minus_one=0)
464        // So header byte = 00_0_1_0001 = 0x11
465        let metadata_bytes = vec![
466            0b0001_0001,
467            3, // dictionary size
468            0, // "active"
469            6, // "age"
470            9, // "name"
471            13,
472            b'a',
473            b'c',
474            b't',
475            b'i',
476            b'v',
477            b'e',
478            b'a',
479            b'g',
480            b'e',
481            b'n',
482            b'a',
483            b'm',
484            b'e',
485        ];
486        let metadata = VariantMetadata::try_new(&metadata_bytes).unwrap();
487
488        // Create object value data for: {"active": true, "age": 42, "name": "hello"}
489        // Field IDs in sorted order: [0, 1, 2] (active, age, name)
490        // Header: basic_type=2, field_offset_size_minus_one=0, field_id_size_minus_one=0, is_large=0
491        // value_header = 0000_00_00 = 0x00
492        // So header byte = (0x00 << 2) | 2 = 0x02
493        let object_value = vec![
494            0x02, // header: basic_type=2, value_header=0x00
495            3,    // num_elements = 3
496            // Field IDs (1 byte each): active=0, age=1, name=2
497            0, 1, 2,
498            // Field offsets (1 byte each): 4 offsets total
499            0, // offset to first value (boolean true)
500            1, // offset to second value (int8)
501            3, // offset to third value (short string)
502            9, // end offset
503            // Values:
504            0x04, // boolean true: primitive_header=1, basic_type=0 -> (1 << 2) | 0 = 0x04
505            0x0C,
506            42, // int8: primitive_header=3, basic_type=0 -> (3 << 2) | 0 = 0x0C, then value 42
507            0x15, b'h', b'e', b'l', b'l',
508            b'o', // short string: length=5, basic_type=1 -> (5 << 2) | 1 = 0x15
509        ];
510
511        let variant_obj = VariantObject::try_new(metadata, &object_value).unwrap();
512
513        // Test basic properties
514        assert_eq!(variant_obj.len(), 3);
515        assert!(!variant_obj.is_empty());
516
517        // Test field access
518        let active_field = variant_obj.get("active");
519        assert!(active_field.is_some());
520        assert_eq!(active_field.unwrap().as_boolean(), Some(true));
521
522        let age_field = variant_obj.get("age");
523        assert!(age_field.is_some());
524        assert_eq!(age_field.unwrap().as_int8(), Some(42));
525
526        let name_field = variant_obj.get("name");
527        assert!(name_field.is_some());
528        assert_eq!(name_field.unwrap().as_string(), Some("hello"));
529
530        // Test non-existent field
531        let missing_field = variant_obj.get("missing");
532        assert!(missing_field.is_none());
533
534        let missing_field_name = variant_obj.field_name(3);
535        assert!(missing_field_name.is_none());
536
537        let missing_field_name = variant_obj.field_name(300);
538        assert!(missing_field_name.is_none());
539
540        let missing_field_value = variant_obj.field(3);
541        assert!(missing_field_value.is_none());
542
543        let missing_field_value = variant_obj.field(300);
544        assert!(missing_field_value.is_none());
545
546        // Test fields iterator
547        let fields: Vec<_> = variant_obj.iter().collect();
548        assert_eq!(fields.len(), 3);
549
550        // Fields should be in sorted order: active, age, name
551        assert_eq!(fields[0].0, "active");
552        assert_eq!(fields[0].1.as_boolean(), Some(true));
553
554        assert_eq!(fields[1].0, "age");
555        assert_eq!(fields[1].1.as_int8(), Some(42));
556
557        assert_eq!(fields[2].0, "name");
558        assert_eq!(fields[2].1.as_string(), Some("hello"));
559
560        // Test field access by index
561        // Fields should be in sorted order: active, age, name
562        assert_eq!(variant_obj.field_name(0), Some("active"));
563        assert_eq!(variant_obj.field(0).unwrap().as_boolean(), Some(true));
564
565        assert_eq!(variant_obj.field_name(1), Some("age"));
566        assert_eq!(variant_obj.field(1).unwrap().as_int8(), Some(42));
567
568        assert_eq!(variant_obj.field_name(2), Some("name"));
569        assert_eq!(variant_obj.field(2).unwrap().as_string(), Some("hello"));
570    }
571
572    #[test]
573    fn test_variant_object_empty_fields() {
574        let mut builder = VariantBuilder::new();
575        builder.new_object().with_field("", 42).finish();
576        let (metadata, value) = builder.finish();
577
578        // Resulting object is valid and has a single empty field
579        let variant = Variant::try_new(&metadata, &value).unwrap();
580        let variant_obj = variant.as_object().unwrap();
581        assert_eq!(variant_obj.len(), 1);
582        assert_eq!(variant_obj.get(""), Some(Variant::from(42)));
583    }
584
585    #[test]
586    fn test_variant_object_empty() {
587        // Create metadata with no fields
588        let metadata_bytes = vec![
589            0x11, // header: version=1, sorted=0, offset_size_minus_one=0
590            0,    // dictionary_size = 0
591            0,    // offset[0] = 0 (end of dictionary)
592        ];
593        let metadata = VariantMetadata::try_new(&metadata_bytes).unwrap();
594
595        // Create empty object value data: {}
596        let object_value = vec![
597            0x02, // header: basic_type=2, value_header=0x00
598            0,    // num_elements = 0
599            0,    // single offset pointing to end
600                  // No field IDs, no values
601        ];
602
603        let variant_obj = VariantObject::try_new(metadata, &object_value).unwrap();
604
605        // Test basic properties
606        assert_eq!(variant_obj.len(), 0);
607        assert!(variant_obj.is_empty());
608
609        // Test field access on empty object
610        let missing_field = variant_obj.get("anything");
611        assert!(missing_field.is_none());
612
613        // Test fields iterator on empty object
614        let fields: Vec<_> = variant_obj.iter().collect();
615        assert_eq!(fields.len(), 0);
616    }
617
618    #[test]
619    fn test_variant_object_invalid_metadata_end_offset() {
620        // Create metadata with field names: "age", "name" (sorted)
621        let metadata_bytes = vec![
622            0b0001_0001, // header: version=1, sorted=1, offset_size_minus_one=0
623            2,           // dictionary size
624            0,           // "age"
625            3,           // "name"
626            8,           // Invalid end offset (should be 7)
627            b'a',
628            b'g',
629            b'e',
630            b'n',
631            b'a',
632            b'm',
633            b'e',
634        ];
635        let err = VariantMetadata::try_new(&metadata_bytes);
636        let err = err.unwrap_err();
637        assert!(matches!(
638            err,
639            ArrowError::InvalidArgumentError(ref msg) if msg.contains("Tried to extract byte(s) ..13 from 12-byte buffer")
640        ));
641    }
642
643    #[test]
644    fn test_variant_object_invalid_end_offset() {
645        // Create metadata with field names: "age", "name" (sorted)
646        let metadata_bytes = vec![
647            0b0001_0001, // header: version=1, sorted=1, offset_size_minus_one=0
648            2,           // dictionary size
649            0,           // "age"
650            3,           // "name"
651            7,
652            b'a',
653            b'g',
654            b'e',
655            b'n',
656            b'a',
657            b'm',
658            b'e',
659        ];
660        let metadata = VariantMetadata::try_new(&metadata_bytes).unwrap();
661
662        // Create object value data for: {"age": 42, "name": "hello"}
663        // Field IDs in sorted order: [0, 1] (age, name)
664        // Header: basic_type=2, field_offset_size_minus_one=0, field_id_size_minus_one=0, is_large=0
665        // value_header = 0000_00_00 = 0x00
666        let object_value = vec![
667            0x02, // header: basic_type=2, value_header=0x00
668            2,    // num_elements = 2
669            // Field IDs (1 byte each): age=0, name=1
670            0, 1,
671            // Field offsets (1 byte each): 3 offsets total
672            0, // offset to first value (int8)
673            2, // offset to second value (short string)
674            9, // invalid end offset (correct would be 8)
675            // Values:
676            0x0C,
677            42, // int8: primitive_header=3, basic_type=0 -> (3 << 2) | 0 = 0x0C, then value 42
678            0x15, b'h', b'e', b'l', b'l',
679            b'o', // short string: length=5, basic_type=1 -> (5 << 2) | 1 = 0x15
680        ];
681
682        let err = VariantObject::try_new(metadata, &object_value);
683        let err = err.unwrap_err();
684        assert!(matches!(
685            err,
686            ArrowError::InvalidArgumentError(ref msg) if msg.contains("Tried to extract byte(s) ..16 from 15-byte buffer")
687        ));
688    }
689
690    fn test_variant_object_with_count(count: i32, expected_field_id_size: OffsetSizeBytes) {
691        let field_names: Vec<_> = (0..count).map(|val| val.to_string()).collect();
692        let mut builder =
693            VariantBuilder::new().with_field_names(field_names.iter().map(|s| s.as_str()));
694
695        let mut obj = builder.new_object();
696
697        for i in 0..count {
698            obj.insert(&field_names[i as usize], i);
699        }
700
701        obj.finish();
702        let (metadata, value) = builder.finish();
703        let variant = Variant::new(&metadata, &value);
704
705        if let Variant::Object(obj) = variant {
706            assert_eq!(obj.len(), count as usize);
707
708            assert_eq!(obj.get(&field_names[0]).unwrap(), Variant::Int32(0));
709            assert_eq!(
710                obj.get(&field_names[(count - 1) as usize]).unwrap(),
711                Variant::Int32(count - 1)
712            );
713            assert_eq!(
714                obj.header.field_id_size, expected_field_id_size,
715                "Expected {}-byte field IDs, got {}-byte field IDs",
716                expected_field_id_size as usize, obj.header.field_id_size as usize
717            );
718        } else {
719            panic!("Expected object variant");
720        }
721    }
722
723    #[test]
724    fn test_variant_object_257_elements() {
725        test_variant_object_with_count((1 << 8) + 1, OffsetSizeBytes::Two); // 2^8 + 1, expected 2-byte field IDs
726    }
727
728    #[test]
729    fn test_variant_object_65537_elements() {
730        test_variant_object_with_count((1 << 16) + 1, OffsetSizeBytes::Three);
731        // 2^16 + 1, expected 3-byte field IDs
732    }
733
734    /* Can't run this test now as it takes 45x longer than other tests
735    #[test]
736    fn test_variant_object_16777217_elements() {
737        test_variant_object_with_count((1 << 24) + 1, OffsetSizeBytes::Four);
738        // 2^24 + 1, expected 4-byte field IDs
739    }
740     */
741
742    #[test]
743    fn test_variant_object_small_sizes_255_elements() {
744        test_variant_object_with_count(255, OffsetSizeBytes::One);
745    }
746
747    fn test_variant_object_with_large_data(
748        data_size_per_field: usize,
749        expected_field_offset_size: OffsetSizeBytes,
750    ) {
751        let num_fields = 20;
752        let mut builder = VariantBuilder::new();
753        let mut obj = builder.new_object();
754
755        let str_val = "a".repeat(data_size_per_field);
756
757        for val in 0..num_fields {
758            let key = format!("id_{val}");
759            obj.insert(&key, str_val.as_str());
760        }
761
762        obj.finish();
763        let (metadata, value) = builder.finish();
764        let variant = Variant::new(&metadata, &value);
765
766        if let Variant::Object(obj) = variant {
767            assert_eq!(obj.len(), num_fields);
768            assert_eq!(
769                obj.header.field_offset_size, expected_field_offset_size,
770                "Expected {}-byte field offsets, got {}-byte field offsets",
771                expected_field_offset_size as usize, obj.header.field_offset_size as usize
772            );
773        } else {
774            panic!("Expected object variant");
775        }
776    }
777
778    #[test]
779    fn test_variant_object_child_data_0_byte_offsets_minus_one() {
780        test_variant_object_with_large_data(10, OffsetSizeBytes::One);
781    }
782
783    #[test]
784    fn test_variant_object_256_bytes_child_data_3_byte_offsets() {
785        test_variant_object_with_large_data(256 + 1, OffsetSizeBytes::Two); // 2^8 - 2^16 elements
786    }
787
788    #[test]
789    fn test_variant_object_16777216_bytes_child_data_4_byte_offsets() {
790        test_variant_object_with_large_data(65536 + 1, OffsetSizeBytes::Three); // 2^16 - 2^24 elements
791    }
792
793    #[test]
794    fn test_variant_object_65535_bytes_child_data_2_byte_offsets() {
795        test_variant_object_with_large_data(16777216 + 1, OffsetSizeBytes::Four);
796        // 2^24
797    }
798
799    #[test]
800    fn test_objects_with_same_fields_are_equal() {
801        let mut b = VariantBuilder::new();
802        let mut o = b.new_object();
803
804        o.insert("b", ());
805        o.insert("c", ());
806        o.insert("a", ());
807
808        o.finish();
809
810        let (m, v) = b.finish();
811
812        let v1 = Variant::try_new(&m, &v).unwrap();
813        let v2 = Variant::try_new(&m, &v).unwrap();
814
815        assert_eq!(v1, v2);
816    }
817
818    #[test]
819    fn test_same_objects_with_different_builder_are_equal() {
820        let mut b = VariantBuilder::new();
821        let mut o = b.new_object();
822
823        o.insert("a", ());
824        o.insert("b", false);
825
826        o.finish();
827        let (m, v) = b.finish();
828
829        let v1 = Variant::try_new(&m, &v).unwrap();
830
831        let mut b = VariantBuilder::new();
832        let mut o = b.new_object();
833
834        o.insert("a", ());
835        o.insert("b", false);
836
837        o.finish();
838        let (m, v) = b.finish();
839
840        let v2 = Variant::try_new(&m, &v).unwrap();
841
842        assert_eq!(v1, v2);
843    }
844
845    #[test]
846    fn test_objects_with_different_values_are_not_equal() {
847        let mut b = VariantBuilder::new();
848        let mut o = b.new_object();
849
850        o.insert("a", ());
851        o.insert("b", 4.3);
852
853        o.finish();
854
855        let (m, v) = b.finish();
856
857        let v1 = Variant::try_new(&m, &v).unwrap();
858
859        // second object, same field name but different values
860        let mut b = VariantBuilder::new();
861        let mut o = b.new_object();
862
863        o.insert("a", ());
864        let mut inner_o = o.new_object("b");
865        inner_o.insert("a", 3.3);
866        inner_o.finish();
867        o.finish();
868
869        let (m, v) = b.finish();
870
871        let v2 = Variant::try_new(&m, &v).unwrap();
872
873        let m1 = v1.metadata();
874        let m2 = v2.metadata();
875
876        // metadata would be equal since they contain the same keys
877        assert_eq!(m1, m2);
878
879        // but the objects are not equal
880        assert_ne!(v1, v2);
881    }
882
883    #[test]
884    fn test_objects_with_different_field_names_are_not_equal() {
885        let mut b = VariantBuilder::new();
886        let mut o = b.new_object();
887
888        o.insert("a", ());
889        o.insert("b", 4.3);
890
891        o.finish();
892
893        let (m, v) = b.finish();
894
895        let v1 = Variant::try_new(&m, &v).unwrap();
896
897        // second object, same field name but different values
898        let mut b = VariantBuilder::new();
899        let mut o = b.new_object();
900
901        o.insert("aardvark", ());
902        o.insert("barracuda", 3.3);
903
904        o.finish();
905
906        let (m, v) = b.finish();
907        let v2 = Variant::try_new(&m, &v).unwrap();
908
909        assert_ne!(v1, v2);
910    }
911
912    #[test]
913    fn test_objects_with_different_insertion_order_are_equal() {
914        let mut b = VariantBuilder::new();
915        let mut o = b.new_object();
916
917        o.insert("b", false);
918        o.insert("a", ());
919
920        o.finish();
921
922        let (m, v) = b.finish();
923
924        let v1 = Variant::try_new(&m, &v).unwrap();
925        assert!(!v1.metadata().is_sorted());
926
927        // create another object pre-filled with field names, b and a
928        // but insert the fields in the order of a, b
929        let mut b = VariantBuilder::new().with_field_names(["b", "a"]);
930        let mut o = b.new_object();
931
932        o.insert("a", ());
933        o.insert("b", false);
934
935        o.finish();
936
937        let (m, v) = b.finish();
938
939        let v2 = Variant::try_new(&m, &v).unwrap();
940
941        // v2 should also have a unsorted dictionary
942        assert!(!v2.metadata().is_sorted());
943
944        assert_eq!(v1, v2);
945    }
946
947    #[test]
948    fn test_objects_with_differing_metadata_are_equal() {
949        let mut b = VariantBuilder::new();
950        let mut o = b.new_object();
951
952        o.insert("a", ());
953        o.insert("b", 4.3);
954
955        o.finish();
956
957        let (meta1, value1) = b.finish();
958
959        let v1 = Variant::try_new(&meta1, &value1).unwrap();
960        // v1 is sorted
961        assert!(v1.metadata().is_sorted());
962
963        // create a second object with different insertion order
964        let mut b = VariantBuilder::new().with_field_names(["d", "c", "b", "a"]);
965        let mut o = b.new_object();
966
967        o.insert("b", 4.3);
968        o.insert("a", ());
969
970        o.finish();
971
972        let (meta2, value2) = b.finish();
973
974        let v2 = Variant::try_new(&meta2, &value2).unwrap();
975        // v2 is not sorted
976        assert!(!v2.metadata().is_sorted());
977
978        // object metadata are not the same
979        assert_ne!(v1.metadata(), v2.metadata());
980
981        // objects are still logically equal
982        assert_eq!(v1, v2);
983    }
984
985    #[test]
986    fn test_compare_object_with_unsorted_dictionary_vs_sorted_dictionary() {
987        // create a sorted object
988        let mut b = VariantBuilder::new();
989        let mut o = b.new_object();
990
991        o.insert("a", false);
992        o.insert("b", false);
993
994        o.finish();
995
996        let (m, v) = b.finish();
997
998        let v1 = Variant::try_new(&m, &v).unwrap();
999
1000        // Create metadata with an unsorted dictionary (field names are "a", "a", "b")
1001        // Since field names are not unique, it is considered not sorted.
1002        let metadata_bytes = vec![
1003            0b0000_0001,
1004            3, // dictionary size
1005            0, // "a"
1006            1, // "b"
1007            2, // "a"
1008            3,
1009            b'a',
1010            b'b',
1011            b'a',
1012        ];
1013        let m = VariantMetadata::try_new(&metadata_bytes).unwrap();
1014        assert!(!m.is_sorted());
1015
1016        let v2 = Variant::new_with_metadata(m, &v);
1017        assert_eq!(v1, v2);
1018    }
1019
1020    #[test]
1021    fn test_object_rejects_duplicate_field_names() {
1022        // An unsorted dictionary may legally hold duplicate entries, but an object must not
1023        // reference the same field name twice.
1024        let metadata_bytes = vec![
1025            0b0000_0001,
1026            2, // dictionary size
1027            0, // "a"
1028            1, // "a"
1029            2,
1030            b'a',
1031            b'a',
1032        ];
1033        assert!(
1034            !VariantMetadata::try_new(&metadata_bytes)
1035                .unwrap()
1036                .is_sorted()
1037        );
1038
1039        let value_bytes = vec![
1040            0b0000_0010, // object header
1041            2,           // num_elements
1042            0,           // field id 0 -> "a"
1043            1,           // field id 1 -> "a"
1044            0,
1045            1,
1046            2,           // field offsets
1047            0b0000_1100, // true
1048            0b0000_1000, // false
1049        ];
1050        let err = Variant::try_new(&metadata_bytes, &value_bytes).unwrap_err();
1051        assert!(
1052            matches!(err, ArrowError::InvalidArgumentError(_)),
1053            "unexpected error: {err:?}"
1054        );
1055    }
1056
1057    /// return the value bytes for `depth` single-field objects nested around a null
1058    fn make_nested_objects(depth: usize) -> Vec<u8> {
1059        let mut value = vec![0u8]; // null primitive
1060        for _ in 0..depth {
1061            // header: object basic type, 1-byte field ids, 4-byte field offsets
1062            let mut outer = vec![0b0000_1110, 1, 0];
1063            outer.extend_from_slice(&0u32.to_le_bytes());
1064            outer.extend_from_slice(&(value.len() as u32).to_le_bytes());
1065            outer.append(&mut value);
1066            value = outer;
1067        }
1068        value
1069    }
1070
1071    #[test]
1072    fn test_variant_object_nesting_depth_limit() {
1073        let metadata = [0b0000_0001, 1, 0, 1, b'a']; // dictionary of one field name
1074
1075        let value = make_nested_objects(MAX_NESTING_DEPTH);
1076        Variant::try_new(&metadata, &value).unwrap();
1077
1078        // One level deeper would recurse past the limit -- previously a stack overflow
1079        let value = make_nested_objects(MAX_NESTING_DEPTH + 1);
1080        let err = Variant::try_new(&metadata, &value).unwrap_err();
1081        assert!(
1082            err.to_string().contains("nesting depth exceeds"),
1083            "unexpected error: {err}"
1084        );
1085    }
1086}