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}