Skip to main content

parquet_variant/variant/
metadata.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    string_from_slice, try_binary_search_range_by,
9};
10
11use arrow_schema::ArrowError;
12
13/// Header structure for [`VariantMetadata`]
14#[derive(Debug, Clone, Copy, PartialEq)]
15pub(crate) struct VariantMetadataHeader {
16    version: u8,
17    is_sorted: bool,
18    /// Note: This is `offset_size_minus_one` + 1
19    offset_size: OffsetSizeBytes,
20}
21
22/// The version of the Variant specification implemented by this crate.
23///
24/// The spec currently defines only version 1. It appears in two places on
25/// disk: the 4-bit version field of every metadata header, and the
26/// `specification_version` of the Parquet `VARIANT` logical type annotation.
27/// Both must carry this value.
28pub const VARIANT_SPEC_VERSION: u8 = 1;
29
30// The metadata header occupies one byte; use a named constant for readability
31const NUM_HEADER_BYTES: u32 = 1;
32
33impl VariantMetadataHeader {
34    // Hide the cast
35    const fn offset_size(&self) -> u32 {
36        self.offset_size as u32
37    }
38
39    // Avoid materializing this offset, since it's cheaply and safely computable
40    const fn first_offset_byte(&self) -> u32 {
41        NUM_HEADER_BYTES + self.offset_size()
42    }
43
44    /// Tries to construct the variant metadata header, which has the form
45    ///
46    /// ```text
47    ///              7     6  5   4  3             0
48    ///             +-------+---+---+---------------+
49    /// header      |       |   |   |    version    |
50    ///             +-------+---+---+---------------+
51    ///                 ^         ^
52    ///                 |         +-- sorted_strings
53    ///                 +-- offset_size_minus_one
54    /// ```
55    ///
56    /// The version is a 4-bit value that must always contain the value 1.
57    /// - sorted_strings is a 1-bit value indicating whether dictionary strings are sorted and unique.
58    /// - offset_size_minus_one is a 2-bit value providing the number of bytes per dictionary size and offset field.
59    /// - The actual number of bytes, offset_size, is offset_size_minus_one + 1
60    pub(crate) fn try_new(header_byte: u8) -> Result<Self, ArrowError> {
61        let version = header_byte & 0x0F; // First four bits
62        if version != VARIANT_SPEC_VERSION {
63            let err_msg = format!(
64                "The version bytes in the header is not {VARIANT_SPEC_VERSION}, got {version:b}",
65            );
66            return Err(ArrowError::InvalidArgumentError(err_msg));
67        }
68        let is_sorted = (header_byte & 0x10) != 0; // Fifth bit
69        let offset_size_minus_one = header_byte >> 6; // Last two bits
70        Ok(Self {
71            version,
72            is_sorted,
73            offset_size: OffsetSizeBytes::try_new(offset_size_minus_one)?,
74        })
75    }
76}
77
78/// [`Variant`] Metadata
79///
80/// See the [Variant Spec] file for more information
81///
82/// # Validation
83///
84/// Every instance of variant metadata is either _valid_ or _invalid_. depending on whether the
85/// underlying bytes are a valid encoding of variant metadata (see below).
86///
87/// Instances produced by [`Self::try_new`] or [`Self::with_full_validation`] are fully _validated_. They always
88/// contain _valid_ data, and infallible accesses such as iteration and indexing are panic-free. The
89/// validation cost is linear in the number of underlying bytes.
90///
91/// Instances produced by [`Self::new`] are _unvalidated_ and so they may contain either _valid_ or
92/// _invalid_ data. Infallible accesses such as iteration and indexing will panic if the underlying
93/// bytes are _invalid_, and fallible alternatives such as [`Self::iter_try`] and [`Self::get`] are
94/// provided as panic-free alternatives. [`Self::with_full_validation`] can also be used to _validate_ an
95/// _unvalidated_ instance, if desired.
96///
97/// _Unvalidated_ instances can be constructed in constant time. This can be useful if the caller
98/// knows the underlying bytes were already validated previously, or if the caller intends to
99/// perform a small number of (fallible) accesses to a large dictionary.
100///
101/// A _validated_ variant [metadata instance guarantees that:
102///
103/// - header byte is valid
104/// - dictionary size is in bounds
105/// - offset array content is in-bounds
106/// - first offset is zero
107/// - last offset is in-bounds
108/// - all other offsets are in-bounds (*)
109/// - all offsets are non-decreasing (*)
110/// - all values are valid utf-8 (*)
111///
112/// NOTE: [`Self::new`] only skips expensive (non-constant cost) validation checks (marked by `(*)`
113/// in the list above); it panics any of the other checks fails.
114///
115/// # Safety
116///
117/// Even an _invalid_ variant metadata instance is still _safe_ to use in the Rust sense. Accessing
118/// it with infallible methods may cause panics but will never lead to undefined behavior.
119///
120/// [`Variant`]: crate::Variant
121/// [Variant Spec]: https://github.com/apache/parquet-format/blob/master/VariantEncoding.md#metadata-encoding
122#[derive(Debug, Clone, PartialEq)]
123pub struct VariantMetadata<'m> {
124    /// (Only) the bytes that make up this metadata instance.
125    pub(crate) bytes: &'m [u8],
126    header: VariantMetadataHeader,
127    dictionary_size: u32,
128    first_value_byte: u32,
129    validated: bool,
130}
131
132// We don't want this to grow because it increases the size of VariantList and VariantObject, which
133// could increase the size of Variant. All those size increases could hurt performance.
134#[cfg(target_pointer_width = "64")]
135const _: () = crate::utils::expect_size_of::<VariantMetadata>(32);
136
137#[cfg(target_pointer_width = "32")]
138const _: () = crate::utils::expect_size_of::<VariantMetadata>(20);
139
140/// The canonical byte slice corresponding to an empty metadata dictionary.
141///
142/// ```
143/// # use parquet_variant::{EMPTY_VARIANT_METADATA_BYTES, VariantMetadata, WritableMetadataBuilder};
144/// let mut metadata_builder = WritableMetadataBuilder::default();
145/// metadata_builder.finish();
146/// let metadata_bytes = metadata_builder.into_inner();
147/// assert_eq!(&metadata_bytes, EMPTY_VARIANT_METADATA_BYTES);
148/// ```
149pub const EMPTY_VARIANT_METADATA_BYTES: &[u8] = &[VARIANT_SPEC_VERSION, 0, 0];
150
151/// The empty metadata dictionary.
152///
153/// ```
154/// # use parquet_variant::{EMPTY_VARIANT_METADATA, VariantMetadata, WritableMetadataBuilder};
155/// let mut metadata_builder = WritableMetadataBuilder::default();
156/// metadata_builder.finish();
157/// let metadata_bytes = metadata_builder.into_inner();
158/// let empty_metadata = VariantMetadata::try_new(&metadata_bytes).unwrap();
159/// assert_eq!(empty_metadata, EMPTY_VARIANT_METADATA);
160/// ```
161pub const EMPTY_VARIANT_METADATA: VariantMetadata = VariantMetadata {
162    bytes: EMPTY_VARIANT_METADATA_BYTES,
163    header: VariantMetadataHeader {
164        version: VARIANT_SPEC_VERSION,
165        is_sorted: false,
166        offset_size: OffsetSizeBytes::One,
167    },
168    dictionary_size: 0,
169    first_value_byte: 3,
170    validated: true,
171};
172
173impl<'m> VariantMetadata<'m> {
174    /// Attempts to interpret `bytes` as a variant metadata instance, with full [validation] of all
175    /// dictionary entries.
176    ///
177    /// [validation]: Self#Validation
178    pub fn try_new(bytes: &'m [u8]) -> Result<Self, ArrowError> {
179        Self::try_new_with_shallow_validation(bytes)?.with_full_validation()
180    }
181
182    /// Interprets `bytes` as a variant metadata instance, without attempting to [validate] dictionary
183    /// entries. Panics if basic sanity checking fails, and subsequent infallible accesses such as
184    /// indexing and iteration could also panic if the underlying bytes are invalid.
185    ///
186    /// This constructor can be a useful lightweight alternative to [`Self::try_new`] if the bytes
187    /// were already validated previously by other means, or if the caller expects a small number of
188    /// accesses to a large dictionary (preferring to use a small number of fallible accesses as
189    /// needed, instead of paying expensive full validation up front).
190    ///
191    /// [validate]: Self#Validation
192    ///
193    /// # Panics
194    ///
195    /// Panics if basic sanity checking fails. Use [`Self::try_new`] for a fallible version.
196    pub fn new(bytes: &'m [u8]) -> Self {
197        Self::try_new_with_shallow_validation(bytes).expect("Invalid variant metadata")
198    }
199
200    // The actual constructor, which performs only basic (constant-const) validation.
201    pub(crate) fn try_new_with_shallow_validation(bytes: &'m [u8]) -> Result<Self, ArrowError> {
202        let header_byte = first_byte_from_slice(bytes)?;
203        let header = VariantMetadataHeader::try_new(header_byte)?;
204
205        // First element after header is dictionary size; the offset array immediately follows.
206        let dictionary_size =
207            header
208                .offset_size
209                .unpack_u32_at_offset(bytes, NUM_HEADER_BYTES as usize, 0)?;
210
211        // Calculate the starting offset of the dictionary string bytes.
212        //
213        // There are dict_size + 1 offsets, and the value bytes immediately follow
214        // = (dict_size + 1) * offset_size + header.first_offset_byte()
215        let first_value_byte = dictionary_size
216            .checked_add(1)
217            .and_then(|n| n.checked_mul(header.offset_size()))
218            .and_then(|n| n.checked_add(header.first_offset_byte()))
219            .ok_or_else(|| overflow_error("offset of variant metadata dictionary"))?;
220
221        let mut new_self = Self {
222            bytes,
223            header,
224            dictionary_size,
225            first_value_byte,
226            validated: false,
227        };
228
229        // Validate just the first and last offset, ignoring the other offsets and all value bytes.
230        let first_offset = new_self.get_offset(0)?;
231        if first_offset != 0 {
232            return Err(ArrowError::InvalidArgumentError(format!(
233                "First offset is not zero: {first_offset}"
234            )));
235        }
236
237        // Use the last offset to upper-bound the byte slice
238        let last_offset = new_self
239            .get_offset(dictionary_size as _)?
240            .checked_add(first_value_byte)
241            .ok_or_else(|| overflow_error("variant metadata size"))?;
242        new_self.bytes = slice_from_slice(bytes, ..last_offset as _)?;
243        Ok(new_self)
244    }
245
246    /// The number of metadata dictionary entries
247    pub fn len(&self) -> usize {
248        self.dictionary_size as _
249    }
250
251    /// True if this metadata dictionary contains no entries
252    pub fn is_empty(&self) -> bool {
253        self.len() == 0
254    }
255
256    /// True if this instance is fully [validated] for panic-free infallible accesses.
257    ///
258    /// [validated]: Self#Validation
259    pub fn is_fully_validated(&self) -> bool {
260        self.validated
261    }
262
263    /// Performs a full [validation] of this metadata dictionary and returns the result.
264    ///
265    /// [validation]: Self#Validation
266    pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
267        if !self.validated {
268            let offset_bytes = slice_from_slice(
269                self.bytes,
270                self.header.first_offset_byte() as _..self.first_value_byte as _,
271            )?;
272
273            // Verify the string values in the dictionary are UTF-8 encoded strings.
274            let value_buffer =
275                string_from_slice(self.bytes, 0, self.first_value_byte as _..self.bytes.len())?;
276
277            let mut offsets = map_bytes_to_offsets(offset_bytes, self.header.offset_size);
278            let mut current_offset = offsets.next().unwrap_or(0);
279
280            if self.header.is_sorted {
281                // Validate the dictionary values are unique and lexicographically sorted
282                //
283                // Since we use the offsets to access dictionary values, this also validates
284                // offsets are in-bounds and monotonically increasing
285                let mut prev_value: Option<&str> = None;
286                for next_offset in offsets {
287                    let current_value = value_buffer.get(current_offset..next_offset).ok_or_else(
288                        || {
289                            ArrowError::InvalidArgumentError(format!(
290                                "range {current_offset}..{next_offset} is invalid or out of bounds"
291                            ))
292                        },
293                    )?;
294
295                    if let Some(prev_val) = prev_value
296                        && current_value <= prev_val
297                    {
298                        return Err(ArrowError::InvalidArgumentError(
299                            "dictionary values are not unique and ordered".to_string(),
300                        ));
301                    }
302
303                    prev_value = Some(current_value);
304                    current_offset = next_offset;
305                }
306            } else {
307                // Slicing each dictionary value validates that offsets are in-bounds, non-decreasing,
308                // and land on UTF-8 character boundaries. Equal offsets are legal: they encode an
309                // empty dictionary entry.
310                for next_offset in offsets {
311                    value_buffer
312                        .get(current_offset..next_offset)
313                        .ok_or_else(|| {
314                            ArrowError::InvalidArgumentError(format!(
315                                "range {current_offset}..{next_offset} is invalid or out of bounds"
316                            ))
317                        })?;
318                    current_offset = next_offset;
319                }
320            }
321
322            self.validated = true;
323        }
324        Ok(self)
325    }
326
327    /// Whether the dictionary keys are sorted and unique
328    pub fn is_sorted(&self) -> bool {
329        self.header.is_sorted
330    }
331
332    /// The variant protocol version
333    pub const fn version(&self) -> u8 {
334        self.header.version
335    }
336
337    /// Gets an offset into the dictionary entry by index.
338    ///
339    /// This offset is an index into the dictionary, at the boundary between string `i-1` and string
340    /// `i`. See [`Self::get`] to retrieve a specific dictionary entry.
341    fn get_offset(&self, i: usize) -> Result<u32, ArrowError> {
342        let offset_byte_range = self.header.first_offset_byte() as _..self.first_value_byte as _;
343        let bytes = slice_from_slice(self.bytes, offset_byte_range)?;
344        self.header.offset_size.unpack_u32(bytes, i)
345    }
346
347    /// Returns the total size, in bytes, of the metadata.
348    ///
349    /// Note this value may be smaller than what was passed to [`Self::new`] or
350    /// [`Self::try_new`] if the input was larger than necessary to encode the
351    /// metadata dictionary.
352    pub fn size(&self) -> usize {
353        self.bytes.len()
354    }
355
356    /// Attempts to retrieve a dictionary entry by index, failing if out of bounds or if the
357    /// underlying bytes are [invalid].
358    ///
359    /// [invalid]: Self#Validation
360    pub fn get(&self, i: usize) -> Result<&'m str, ArrowError> {
361        let byte_range = self.get_offset(i)? as _..self.get_offset(i + 1)? as _;
362        if !self.validated {
363            return string_from_slice(self.bytes, self.first_value_byte as _, byte_range);
364        }
365
366        // Full validation already proved every dictionary entry is valid UTF-8, so validating
367        // again here would charge that cost once per field access instead of once per buffer.
368        let value_bytes =
369            slice_from_slice_at_offset(self.bytes, self.first_value_byte as _, byte_range)?;
370
371        debug_assert!(std::str::from_utf8(value_bytes).is_ok());
372
373        // SAFETY: `validated` is set only by `with_full_validation`, which proved that every
374        // dictionary entry, including this one, is valid UTF-8.
375        Ok(unsafe { str::from_utf8_unchecked(value_bytes) })
376    }
377
378    // Helper method used by our `impl Index` and also by `get_entry`. Panics if the underlying
379    // bytes are invalid. Needed because the `Index` trait forces the returned result to have the
380    // lifetime of `self` instead of the string's own (longer) lifetime `'m`.
381    fn get_impl(&self, i: usize) -> &'m str {
382        self.get(i).expect("Invalid metadata dictionary entry")
383    }
384
385    /// Attempts to resolve `field_name` to its field id under the assumption that `field_name` is
386    /// itself a slice of this dictionary's value region, as is the case for every field name
387    /// obtained from [`VariantObject::field_name`] or [`Self::get`] on the same metadata instance.
388    /// Returns `None` when that assumption does not hold, so callers must be prepared to fall back
389    /// to a name-based search such as [`Self::get_entry`].
390    ///
391    /// This is much cheaper than searching by name, because a borrowed field name already encodes
392    /// its own field id: it belongs to the entry whose dictionary offset equals its distance from
393    /// the start of the value region. Finding that entry is a binary search over the
394    /// (non-decreasing) offset array, comparing integers rather than decoding and comparing
395    /// dictionary strings at every step, and it needs no string comparison to confirm the hit.
396    ///
397    /// # Correctness
398    ///
399    /// This is only attempted for a [sorted] dictionary. The spec requires dictionary entries to
400    /// be unique only when `sorted_strings` is set, so an unsorted dictionary may legally hold the
401    /// same string at more than one field id. Resolving a borrowed name by the id it came from
402    /// would then disagree with a resolution by name, and callers rely on a name mapping to a
403    /// single id: [`ObjectBuilder`] detects duplicate fields by comparing field ids, so two ids
404    /// naming the same string would build an object whose field names are not unique. Requiring
405    /// sortedness makes the two resolutions agree, because validation rejects a sorted dictionary
406    /// with duplicate entries.
407    ///
408    /// A returned field id is also always verified, so this never reports an id whose entry is not
409    /// `field_name` itself, even for [invalid] metadata whose offsets are arbitrary. The candidate
410    /// entry is accepted only when it starts at `field_name`'s address and has exactly
411    /// `field_name`'s length, which makes the entry's bytes and `field_name`'s bytes the same
412    /// bytes. (Two live allocations cannot overlap, so an address inside our own byte range
413    /// belongs to our own bytes. In the degenerate zero-length case the two are both empty and
414    /// therefore still equal.)
415    ///
416    /// [`ObjectBuilder`]: crate::ObjectBuilder
417    /// [`VariantObject::field_name`]: crate::VariantObject::field_name
418    /// [invalid]: Self#Validation
419    /// [sorted]: Self::is_sorted
420    pub(crate) fn borrowed_field_id(&self, field_name: &str) -> Option<u32> {
421        // An unsorted dictionary may hold duplicate entries, which would make the id a name was
422        // borrowed from differ from the id a search by name returns; see "Correctness" above.
423        if !self.is_sorted() {
424            return None;
425        }
426
427        // Addresses are compared as integers and never dereferenced, so this stays safe even when
428        // `field_name` borrows from an unrelated allocation.
429        let value_region_start = (self.bytes.as_ptr() as usize) + self.first_value_byte as usize;
430        let value_region_end = (self.bytes.as_ptr() as usize) + self.bytes.len();
431        let field_name_start = field_name.as_ptr() as usize;
432        if field_name_start < value_region_start || field_name_start >= value_region_end {
433            return None;
434        }
435        let field_name_offset = u32::try_from(field_name_start - value_region_start).ok()?;
436
437        // Hoist the offset array out of the search, so each step is just an unaligned load.
438        let offset_byte_range = self.header.first_offset_byte() as _..self.first_value_byte as _;
439        let offsets = slice_from_slice(self.bytes, offset_byte_range).ok()?;
440        let offset_size = self.header.offset_size;
441        let cmp = |i| {
442            Some(
443                offset_size
444                    .unpack_u32(offsets, i)
445                    .ok()?
446                    .cmp(&field_name_offset),
447            )
448        };
449        let field_id = try_binary_search_range_by(0..self.len(), cmp)?.ok()?;
450
451        // Verify that this entry has exactly `field_name`'s bytes; see "Correctness" above.
452        let entry_end = offset_size.unpack_u32(offsets, field_id + 1).ok()?;
453        let entry_len = entry_end.checked_sub(field_name_offset)?;
454        (entry_len as usize == field_name.len()).then_some(field_id as u32)
455    }
456
457    /// Attempts to retrieve a dictionary entry and its field id, returning None if the requested field
458    /// name is not present. The search cost is logarithmic if [`Self::is_sorted`] and linear
459    /// otherwise.
460    ///
461    /// # Panics
462    ///
463    /// Panics if the underlying bytes are [invalid].
464    ///
465    /// [invalid]: Self#Validation
466    pub fn get_entry(&self, field_name: &str) -> Option<(u32, &'m str)> {
467        // A field name borrowed from this dictionary's (sorted) value region resolves without
468        // any string comparisons.
469        if let Some(field_id) = self.borrowed_field_id(field_name) {
470            return Some((field_id, self.get_impl(field_id as _)));
471        }
472
473        let field_id = if self.is_sorted() && self.len() > 10 {
474            // Binary search is faster for a not-tiny sorted metadata dictionary
475            let cmp = |i| Some(self.get_impl(i).cmp(field_name));
476            try_binary_search_range_by(0..self.len(), cmp)?.ok()?
477        } else {
478            // Fall back to Linear search for tiny or unsorted dictionary
479            (0..self.len()).find(|i| self.get_impl(*i) == field_name)?
480        };
481        Some((field_id as u32, self.get_impl(field_id)))
482    }
483
484    /// Returns an iterator that attempts to visit all dictionary entries, producing `Err` if the
485    /// iterator encounters [invalid] data.
486    ///
487    /// [invalid]: Self#Validation
488    pub fn iter_try(&self) -> impl Iterator<Item = Result<&'m str, ArrowError>> + '_ {
489        (0..self.len()).map(|i| self.get(i))
490    }
491
492    /// Iterates over all dictionary entries. When working with [unvalidated] input, consider
493    /// [`Self::iter_try`] to avoid panics due to invalid data.
494    ///
495    /// [unvalidated]: Self#Validation
496    ///
497    /// # Panics
498    ///
499    /// Panics if the underlying bytes are invalid. Use [`Self::iter_try`] for a
500    /// fallible version.
501    pub fn iter(&self) -> impl Iterator<Item = &'m str> + '_ {
502        self.iter_try()
503            .map(|result| result.expect("Invalid metadata dictionary entry"))
504    }
505}
506
507/// Retrieves the ith dictionary entry, panicking if the index is out of bounds. Accessing
508/// [unvalidated] input could also panic if the underlying bytes are invalid.
509///
510/// [unvalidated]: Self#Validation
511impl std::ops::Index<usize> for VariantMetadata<'_> {
512    type Output = str;
513
514    fn index(&self, i: usize) -> &str {
515        self.get_impl(i)
516    }
517}
518
519#[cfg(test)]
520mod tests {
521
522    use crate::VariantBuilder;
523
524    use super::*;
525
526    /// `"cat"`, `"dog"` – valid metadata
527    #[test]
528    fn try_new_ok_inline() {
529        let bytes = &[
530            0b0000_0001, // header, offset_size_minus_one=0 and version=1
531            0x02,        // dictionary_size (2 strings)
532            0x00,
533            0x03,
534            0x06,
535            b'c',
536            b'a',
537            b't',
538            b'd',
539            b'o',
540            b'g',
541        ];
542
543        let md = VariantMetadata::try_new(bytes).expect("should parse");
544        assert_eq!(md.len(), 2);
545        // Fields
546        assert_eq!(&md[0], "cat");
547        assert_eq!(&md[1], "dog");
548
549        // Offsets
550        assert_eq!(md.get_offset(0).unwrap(), 0x00);
551        assert_eq!(md.get_offset(1).unwrap(), 0x03);
552        assert_eq!(md.get_offset(2).unwrap(), 0x06);
553
554        let err = md.get_offset(3).unwrap_err();
555        assert!(
556            matches!(err, ArrowError::InvalidArgumentError(_)),
557            "unexpected error: {err:?}"
558        );
559
560        let fields: Vec<(usize, &str)> = md.iter().enumerate().collect();
561        assert_eq!(fields, vec![(0usize, "cat"), (1usize, "dog")]);
562    }
563
564    /// Too short buffer test (missing one required offset).
565    /// Should error with "metadata shorter than dictionary_size implies".
566    #[test]
567    fn try_new_missing_last_value() {
568        let bytes = &[
569            0b0000_0001, // header, offset_size_minus_one=0 and version=1
570            0x02,        // dictionary_size = 2
571            0x00,
572            0x01,
573            0x02,
574            b'a',
575            b'b', // <-- we'll remove this
576        ];
577
578        let working_md = VariantMetadata::try_new(bytes).expect("should parse");
579        assert_eq!(working_md.len(), 2);
580        assert_eq!(&working_md[0], "a");
581        assert_eq!(&working_md[1], "b");
582
583        let truncated = &bytes[..bytes.len() - 1];
584
585        let err = VariantMetadata::try_new(truncated).unwrap_err();
586        assert!(
587            matches!(err, ArrowError::InvalidArgumentError(_)),
588            "unexpected error: {err:?}"
589        );
590    }
591
592    #[test]
593    fn try_new_fails_non_monotonic() {
594        // 'cat', 'dog', 'lamb'
595        let bytes = &[
596            0b0000_0001, // header, offset_size_minus_one=0 and version=1
597            0x03,        // dictionary_size
598            0x00,
599            0x02,
600            0x01, // Doesn't increase monotonically
601            0x10,
602            b'c',
603            b'a',
604            b't',
605            b'd',
606            b'o',
607            b'g',
608            b'l',
609            b'a',
610            b'm',
611            b'b',
612        ];
613
614        let err = VariantMetadata::try_new(bytes).unwrap_err();
615        assert!(
616            matches!(err, ArrowError::InvalidArgumentError(_)),
617            "unexpected error: {err:?}"
618        );
619    }
620
621    #[test]
622    fn try_new_fails_non_monotonic2() {
623        // this test case checks whether offsets are monotonic in the full validation logic.
624
625        // 'cat', 'dog', 'lamb', "eel"
626        let bytes = &[
627            0b0000_0001, // header, offset_size_minus_one=0 and version=1
628            4,           // dictionary_size
629            0x00,
630            0x02,
631            0x01, // Doesn't increase monotonically
632            0x10,
633            13,
634            b'c',
635            b'a',
636            b't',
637            b'd',
638            b'o',
639            b'g',
640            b'l',
641            b'a',
642            b'm',
643            b'b',
644            b'e',
645            b'e',
646            b'l',
647        ];
648
649        let err = VariantMetadata::try_new(bytes).unwrap_err();
650
651        assert!(
652            matches!(err, ArrowError::InvalidArgumentError(_)),
653            "unexpected error: {err:?}"
654        );
655    }
656
657    #[test]
658    fn try_new_truncated_offsets_inline() {
659        // Missing final offset
660        let bytes = &[0b0000_0001, 0x02, 0x00, 0x01];
661
662        let err = VariantMetadata::try_new(bytes).unwrap_err();
663        assert!(
664            matches!(err, ArrowError::InvalidArgumentError(_)),
665            "unexpected error: {err:?}"
666        );
667    }
668
669    #[test]
670    fn empty_string_is_valid() {
671        let bytes = &[
672            0b0001_0001, // header: offset_size_minus_one=0, ordered=1, version=1
673            1,
674            0x00,
675            0x00,
676        ];
677        let metadata = VariantMetadata::try_new(bytes).unwrap();
678        assert_eq!(&metadata[0], "");
679
680        let bytes = &[
681            0b0001_0001, // header: offset_size_minus_one=0, ordered=1, version=1
682            2,
683            0x00,
684            0x00,
685            0x02,
686            b'h',
687            b'i',
688        ];
689        let metadata = VariantMetadata::try_new(bytes).unwrap();
690        assert_eq!(&metadata[0], "");
691        assert_eq!(&metadata[1], "hi");
692
693        let bytes = &[
694            0b0001_0001, // header: offset_size_minus_one=0, ordered=1, version=1
695            2,
696            0x00,
697            0x02,
698            0x02, // empty string is allowed, but must be first in a sorted dict
699            b'h',
700            b'i',
701        ];
702        let err = VariantMetadata::try_new(bytes).unwrap_err();
703        assert!(
704            matches!(err, ArrowError::InvalidArgumentError(_)),
705            "unexpected error: {err:?}"
706        );
707
708        let bytes = &[
709            0b0000_0001, // header: offset_size_minus_one=0, ordered=0, version=1
710            2,
711            0x00,
712            0x02,
713            0x02, // an unsorted dict may hold an empty string anywhere
714            b'h',
715            b'i',
716        ];
717        let metadata = VariantMetadata::try_new(bytes).unwrap();
718        assert_eq!(&metadata[0], "hi");
719        assert_eq!(&metadata[1], "");
720    }
721
722    /// Builds a metadata dictionary containing `field_names`, in the order given.
723    fn metadata_bytes_for(field_names: &[&str]) -> Vec<u8> {
724        let mut builder = VariantBuilder::new().with_field_names(field_names.iter().copied());
725        let mut object = builder.new_object();
726        for name in field_names {
727            object.insert(name, 1i32);
728        }
729        object.finish();
730        builder.finish().0
731    }
732
733    /// Every entry of `metadata` must resolve to its own field id through the general name search
734    /// and through an owned (non-borrowed) copy of the name. The borrowed fast path must agree
735    /// whenever it applies, which is only for a sorted dictionary.
736    fn assert_lookups_agree(metadata: &VariantMetadata<'_>) {
737        for i in 0..metadata.len() {
738            let borrowed = metadata.get(i).unwrap();
739            let owned = borrowed.to_string();
740
741            assert_eq!(
742                metadata.borrowed_field_id(borrowed),
743                metadata.is_sorted().then_some(i as u32),
744                "borrowed lookup of {borrowed:?} (field id {i})"
745            );
746            assert_eq!(
747                metadata.get_entry(borrowed),
748                Some((i as u32, borrowed)),
749                "get_entry of borrowed {borrowed:?} (field id {i})"
750            );
751            assert_eq!(
752                metadata.get_entry(owned.as_str()),
753                Some((i as u32, borrowed)),
754                "get_entry of owned {borrowed:?} (field id {i})"
755            );
756            // An owned copy does not borrow from the dictionary, so it cannot take the fast path.
757            assert_eq!(metadata.borrowed_field_id(owned.as_str()), None);
758        }
759    }
760
761    /// Like [`assert_lookups_agree`], but tolerates the fast path declining an entry, as it may
762    /// for a dictionary whose offset array does not increase strictly.
763    fn assert_lookups_agree_or_decline(metadata: &VariantMetadata<'_>) {
764        for i in 0..metadata.len() {
765            let borrowed = metadata.get(i).unwrap();
766            if let Some(field_id) = metadata.borrowed_field_id(borrowed) {
767                assert_eq!(field_id, i as u32, "borrowed lookup of {borrowed:?}");
768            }
769            assert_eq!(
770                metadata.get_entry(borrowed),
771                Some((i as u32, borrowed)),
772                "get_entry of borrowed {borrowed:?} (field id {i})"
773            );
774        }
775    }
776
777    #[test]
778    fn test_borrowed_field_id_sorted_dictionary() {
779        // More than 10 entries, so `get_entry` uses its binary search path.
780        let names: Vec<String> = (0..64).map(|i| format!("field_{i:03}")).collect();
781        let names: Vec<&str> = names.iter().map(String::as_str).collect();
782        let bytes = metadata_bytes_for(&names);
783        let metadata = VariantMetadata::try_new(&bytes).unwrap();
784
785        assert!(metadata.is_sorted());
786        assert_eq!(metadata.len(), 64);
787        assert_lookups_agree(&metadata);
788
789        assert_eq!(metadata.get_entry("field_999"), None);
790        assert_eq!(metadata.borrowed_field_id("field_999"), None);
791    }
792
793    #[test]
794    fn test_borrowed_field_id_unsorted_dictionary() {
795        let bytes = metadata_bytes_for(&["zebra", "apple", "mango", "kiwi"]);
796        let metadata = VariantMetadata::try_new(&bytes).unwrap();
797
798        assert!(!metadata.is_sorted());
799        assert_eq!(metadata.len(), 4);
800        // An unsorted dictionary may hold duplicate entries, so the fast path never applies to it
801        // and every name falls back to the general search.
802        assert_lookups_agree(&metadata);
803    }
804
805    /// A dictionary that is not marked sorted may legally repeat a string, and the two field ids
806    /// naming it must not become distinguishable by where the caller's name was borrowed from:
807    /// `ObjectBuilder` detects duplicate fields by field id, so a name must map to a single id.
808    #[test]
809    fn test_borrowed_field_id_unsorted_dictionary_with_duplicate_entries() {
810        let bytes = &[
811            0b0000_0001, // header: offset_size_minus_one=0, sorted=0, version=1
812            2,           // dictionary_size
813            0x00,
814            0x01,
815            0x02,
816            b'a',
817            b'a',
818        ];
819        let metadata = VariantMetadata::try_new(bytes).unwrap();
820        assert!(!metadata.is_sorted());
821        assert_eq!(metadata.get(0).unwrap(), "a");
822        assert_eq!(metadata.get(1).unwrap(), "a");
823
824        // Whichever entry a name was borrowed from, it resolves to the first entry naming it.
825        let owned = String::from("a");
826        for name in [metadata.get(0).unwrap(), metadata.get(1).unwrap(), &owned] {
827            assert_eq!(metadata.borrowed_field_id(name), None);
828            assert_eq!(metadata.get_entry(name), Some((0, "a")));
829        }
830    }
831
832    #[test]
833    fn test_borrowed_field_id_ignores_names_from_another_dictionary() {
834        let this_bytes = metadata_bytes_for(&["alpha", "beta", "gamma"]);
835        let this = VariantMetadata::try_new(&this_bytes).unwrap();
836
837        // A different dictionary that shares some names, with different field ids for them.
838        let other_bytes = metadata_bytes_for(&["delta", "gamma", "beta", "alpha"]);
839        let other = VariantMetadata::try_new(&other_bytes).unwrap();
840
841        for i in 0..other.len() {
842            let name = other.get(i).unwrap();
843            // A copy that borrows from neither dictionary, to compare results against.
844            let unborrowed_name: String = name.chars().collect();
845            // The name borrows from `other`, so `this` must not take the fast path for it...
846            assert_eq!(this.borrowed_field_id(name), None);
847            // ...and the general search must still return `this`'s own field id for that name.
848            assert_eq!(this.get_entry(name), this.get_entry(&unborrowed_name));
849        }
850
851        assert_eq!(this.get_entry(other.get(3).unwrap()), Some((0, "alpha")));
852        assert_eq!(this.get_entry(other.get(0).unwrap()), None);
853    }
854
855    #[test]
856    fn test_borrowed_field_id_rejects_substring_of_an_entry() {
857        // Dictionary ["x", "yy"], stored as the bytes "xyy". A slice of entry 1 that starts one
858        // byte into the value region shares its start offset with entry 1 without being equal to
859        // it, which the fast path must detect rather than reporting a bogus field id. The
860        // dictionary is sorted, so the fast path applies to it.
861        let bytes = &[
862            0b0001_0001, // header: offset_size_minus_one=0, ordered=1, version=1
863            2,           // dictionary_size
864            0x00,
865            0x01,
866            0x03,
867            b'x',
868            b'y',
869            b'y',
870        ];
871        let metadata = VariantMetadata::try_new(bytes).unwrap();
872        assert!(metadata.is_sorted());
873        assert_eq!(metadata.get(0).unwrap(), "x");
874        assert_eq!(metadata.get(1).unwrap(), "yy");
875        assert_eq!(
876            metadata.borrowed_field_id(metadata.get(1).unwrap()),
877            Some(1)
878        );
879
880        let prefix_of_entry_1 = &metadata.get(1).unwrap()[..1];
881        assert_eq!(prefix_of_entry_1, "y");
882        assert_eq!(metadata.borrowed_field_id(prefix_of_entry_1), None);
883        assert_eq!(metadata.get_entry(prefix_of_entry_1), None);
884
885        // A slice that starts inside an entry, at an offset no entry starts at, is also rejected.
886        let suffix_of_entry_1 = &metadata.get(1).unwrap()[1..];
887        assert_eq!(metadata.borrowed_field_id(suffix_of_entry_1), None);
888    }
889
890    #[test]
891    fn test_borrowed_field_id_with_empty_field_name() {
892        let bytes = &[
893            0b0000_0001, // header: offset_size_minus_one=0, ordered=0, version=1
894            2,           // dictionary_size
895            0x00,
896            0x02,
897            0x02, // an unsorted dict may hold an empty string anywhere
898            b'h',
899            b'i',
900        ];
901        let metadata = VariantMetadata::try_new(bytes).unwrap();
902        assert!(!metadata.is_sorted());
903        assert_eq!(metadata.get(0).unwrap(), "hi");
904        assert_eq!(metadata.get(1).unwrap(), "");
905
906        assert_eq!(
907            metadata.get_entry(metadata.get(0).unwrap()),
908            Some((0, "hi"))
909        );
910        assert_eq!(metadata.get_entry(metadata.get(1).unwrap()), Some((1, "")));
911        assert_eq!(metadata.get_entry(""), Some((1, "")));
912        assert_eq!(metadata.borrowed_field_id(metadata.get(0).unwrap()), None);
913    }
914
915    #[test]
916    fn test_borrowed_field_id_with_leading_empty_field_name() {
917        // A sorted dictionary can only hold an empty string as its first entry, where it shares a
918        // start offset with the entry after it. The fast path is free to decline such an
919        // ambiguous offset, but must never report the wrong field id for it.
920        let bytes = &[
921            0b0001_0001, // header: offset_size_minus_one=0, ordered=1, version=1
922            2,           // dictionary_size
923            0x00,
924            0x00,
925            0x02,
926            b'h',
927            b'i',
928        ];
929        let metadata = VariantMetadata::try_new(bytes).unwrap();
930        assert!(metadata.is_sorted());
931        assert_eq!(metadata.get(0).unwrap(), "");
932        assert_eq!(metadata.get(1).unwrap(), "hi");
933
934        assert_lookups_agree_or_decline(&metadata);
935        assert_eq!(metadata.get_entry(""), Some((0, "")));
936    }
937
938    #[test]
939    fn test_compare_sorted_dictionary_with_unsorted_dictionary() {
940        // create a sorted object
941        let mut b = VariantBuilder::new();
942        let mut o = b.new_object();
943
944        o.insert("a", false);
945        o.insert("b", false);
946
947        o.finish();
948
949        let (m, _) = b.finish();
950
951        let m1 = VariantMetadata::new(&m);
952        assert!(m1.is_sorted());
953
954        // Create metadata with an unsorted dictionary (field names are "a", "a", "b")
955        // Since field names are not unique, it is considered not sorted.
956        let metadata_bytes = vec![
957            0b0000_0001,
958            3, // dictionary size
959            0, // "a"
960            1, // "a"
961            2, // "b"
962            3,
963            b'a',
964            b'a',
965            b'b',
966        ];
967        let m2 = VariantMetadata::try_new(&metadata_bytes).unwrap();
968        assert!(!m2.is_sorted());
969
970        assert_ne!(m1, m2);
971    }
972
973    #[test]
974    fn test_compare_sorted_dictionary_with_sorted_dictionary() {
975        // create a sorted object
976        let mut b = VariantBuilder::new();
977        let mut o = b.new_object();
978
979        o.insert("a", false);
980        o.insert("b", false);
981
982        o.finish();
983
984        let (m, _) = b.finish();
985
986        let m1 = VariantMetadata::new(&m);
987        let m2 = VariantMetadata::new(&m);
988
989        assert_eq!(m1, m2);
990    }
991
992    #[test]
993    fn test_empty_string_field_names() {
994        // Field names are added to the dictionary in insertion order, so this dictionary is
995        // unsorted, and the empty field name makes its last two offsets equal.
996        let mut b = VariantBuilder::new().with_field_names(["b", "a", ""]);
997        let mut o = b.new_object();
998
999        o.insert("b", false);
1000        o.insert("a", false);
1001        o.insert("", false);
1002
1003        o.finish();
1004
1005        let (m, _) = b.finish();
1006
1007        let metadata = VariantMetadata::try_new(&m).unwrap();
1008        assert!(!metadata.is_sorted());
1009        assert_eq!(metadata.iter().collect::<Vec<_>>(), vec!["b", "a", ""]);
1010    }
1011
1012    /// Builds a metadata buffer directly, so that offsets which a builder would never emit can be
1013    /// exercised. `values` is the raw dictionary value region.
1014    fn raw_metadata(is_sorted: bool, offsets: &[u8], values: &[u8]) -> Vec<u8> {
1015        let mut bytes = vec![0x01 | (u8::from(is_sorted) << 4)];
1016        bytes.push(offsets.len() as u8 - 1); // dictionary_size
1017        bytes.extend_from_slice(offsets);
1018        bytes.extend_from_slice(values);
1019        bytes
1020    }
1021
1022    /// `get` skips UTF-8 revalidation once the metadata is fully validated, so full validation has
1023    /// to reject offsets that split a multi-byte character. Otherwise a validated instance could
1024    /// hand out a `&str` over a partial character.
1025    #[test]
1026    fn full_validation_rejects_offsets_splitting_a_character() {
1027        // "é" is two bytes, so an offset of 1 lands inside it. The value region as a whole is
1028        // still valid UTF-8, so only the per-entry check can catch this.
1029        for is_sorted in [false, true] {
1030            let bytes = raw_metadata(is_sorted, &[0, 1, 2], "é".as_bytes());
1031
1032            // Shallow validation looks only at the first and last offset, so it accepts.
1033            let shallow = VariantMetadata::try_new_with_shallow_validation(&bytes).unwrap();
1034            assert!(!shallow.is_fully_validated());
1035            // ... and the fallible accessor reports the bad entry rather than panicking.
1036            assert!(shallow.get(0).is_err());
1037
1038            // Full validation must reject the buffer outright.
1039            assert!(
1040                VariantMetadata::try_new(&bytes).is_err(),
1041                "is_sorted={is_sorted}: full validation accepted offsets splitting a character"
1042            );
1043        }
1044    }
1045
1046    /// Validated and unvalidated instances must agree on every entry, including multi-byte
1047    /// characters and empty entries, since they take different code paths inside `get`.
1048    #[test]
1049    fn validated_and_unvalidated_get_agree() {
1050        // Unsorted so that the dictionary order below is preserved verbatim.
1051        let values = "aé€\u{10348}"; // 1, 2, 3 and 4 byte characters
1052        let offsets: &[u8] = &[0, 1, 1, 3, 6, 10]; // note the repeated 1: an empty entry
1053        let bytes = raw_metadata(false, offsets, values.as_bytes());
1054
1055        let validated = VariantMetadata::try_new(&bytes).unwrap();
1056        assert!(validated.is_fully_validated());
1057        let unvalidated = VariantMetadata::try_new_with_shallow_validation(&bytes).unwrap();
1058        assert!(!unvalidated.is_fully_validated());
1059
1060        let expected = ["a", "", "é", "€", "\u{10348}"];
1061        assert_eq!(validated.len(), expected.len());
1062        for (i, want) in expected.iter().enumerate() {
1063            assert_eq!(validated.get(i).unwrap(), *want, "validated get({i})");
1064            assert_eq!(unvalidated.get(i).unwrap(), *want, "unvalidated get({i})");
1065        }
1066
1067        // Out of bounds stays an error on both paths, rather than reading past the offset array.
1068        assert!(validated.get(expected.len()).is_err());
1069        assert!(unvalidated.get(expected.len()).is_err());
1070    }
1071
1072    /// An unvalidated instance still reports invalid UTF-8 through the fallible accessor.
1073    #[test]
1074    fn unvalidated_get_still_reports_invalid_utf8() {
1075        let bytes = raw_metadata(false, &[0, 1], &[0xFF]);
1076        let unvalidated = VariantMetadata::try_new_with_shallow_validation(&bytes).unwrap();
1077        assert!(unvalidated.get(0).is_err());
1078        assert!(VariantMetadata::try_new(&bytes).is_err());
1079    }
1080}