parquet_variant/variant/metadata.rs
1// Licensed to the Apache Software Foundation (ASF) under one
2// or more contributor license agreements. See the NOTICE file
3// distributed with this work for additional information
4// regarding copyright ownership. The ASF licenses this file
5// to you under the Apache License, Version 2.0 (the
6// "License"); you may not use this file except in compliance
7// with the License. You may obtain a copy of the License at
8//
9// http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing,
12// software distributed under the License is distributed on an
13// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14// KIND, either express or implied. See the License for the
15// specific language governing permissions and limitations
16// under the License.
17
18use crate::decoder::{OffsetSizeBytes, map_bytes_to_offsets};
19use crate::utils::{
20 first_byte_from_slice, overflow_error, slice_from_slice, slice_from_slice_at_offset,
21 string_from_slice, try_binary_search_range_by,
22};
23
24use arrow_schema::ArrowError;
25
26/// Header structure for [`VariantMetadata`]
27#[derive(Debug, Clone, Copy, PartialEq)]
28pub(crate) struct VariantMetadataHeader {
29 version: u8,
30 is_sorted: bool,
31 /// Note: This is `offset_size_minus_one` + 1
32 offset_size: OffsetSizeBytes,
33}
34
35// According to the spec this is currently always = 1, and so we store this const for validation
36// purposes and to make that visible.
37const CORRECT_VERSION_VALUE: u8 = 1;
38
39// The metadata header occupies one byte; use a named constant for readability
40const NUM_HEADER_BYTES: u32 = 1;
41
42impl VariantMetadataHeader {
43 // Hide the cast
44 const fn offset_size(&self) -> u32 {
45 self.offset_size as u32
46 }
47
48 // Avoid materializing this offset, since it's cheaply and safely computable
49 const fn first_offset_byte(&self) -> u32 {
50 NUM_HEADER_BYTES + self.offset_size()
51 }
52
53 /// Tries to construct the variant metadata header, which has the form
54 ///
55 /// ```text
56 /// 7 6 5 4 3 0
57 /// +-------+---+---+---------------+
58 /// header | | | | version |
59 /// +-------+---+---+---------------+
60 /// ^ ^
61 /// | +-- sorted_strings
62 /// +-- offset_size_minus_one
63 /// ```
64 ///
65 /// The version is a 4-bit value that must always contain the value 1.
66 /// - sorted_strings is a 1-bit value indicating whether dictionary strings are sorted and unique.
67 /// - offset_size_minus_one is a 2-bit value providing the number of bytes per dictionary size and offset field.
68 /// - The actual number of bytes, offset_size, is offset_size_minus_one + 1
69 pub(crate) fn try_new(header_byte: u8) -> Result<Self, ArrowError> {
70 let version = header_byte & 0x0F; // First four bits
71 if version != CORRECT_VERSION_VALUE {
72 let err_msg = format!(
73 "The version bytes in the header is not {CORRECT_VERSION_VALUE}, got {version:b}",
74 );
75 return Err(ArrowError::InvalidArgumentError(err_msg));
76 }
77 let is_sorted = (header_byte & 0x10) != 0; // Fifth bit
78 let offset_size_minus_one = header_byte >> 6; // Last two bits
79 Ok(Self {
80 version,
81 is_sorted,
82 offset_size: OffsetSizeBytes::try_new(offset_size_minus_one)?,
83 })
84 }
85}
86
87/// [`Variant`] Metadata
88///
89/// See the [Variant Spec] file for more information
90///
91/// # Validation
92///
93/// Every instance of variant metadata is either _valid_ or _invalid_. depending on whether the
94/// underlying bytes are a valid encoding of variant metadata (see below).
95///
96/// Instances produced by [`Self::try_new`] or [`Self::with_full_validation`] are fully _validated_. They always
97/// contain _valid_ data, and infallible accesses such as iteration and indexing are panic-free. The
98/// validation cost is linear in the number of underlying bytes.
99///
100/// Instances produced by [`Self::new`] are _unvalidated_ and so they may contain either _valid_ or
101/// _invalid_ data. Infallible accesses such as iteration and indexing will panic if the underlying
102/// bytes are _invalid_, and fallible alternatives such as [`Self::iter_try`] and [`Self::get`] are
103/// provided as panic-free alternatives. [`Self::with_full_validation`] can also be used to _validate_ an
104/// _unvalidated_ instance, if desired.
105///
106/// _Unvalidated_ instances can be constructed in constant time. This can be useful if the caller
107/// knows the underlying bytes were already validated previously, or if the caller intends to
108/// perform a small number of (fallible) accesses to a large dictionary.
109///
110/// A _validated_ variant [metadata instance guarantees that:
111///
112/// - header byte is valid
113/// - dictionary size is in bounds
114/// - offset array content is in-bounds
115/// - first offset is zero
116/// - last offset is in-bounds
117/// - all other offsets are in-bounds (*)
118/// - all offsets are non-decreasing (*)
119/// - all values are valid utf-8 (*)
120///
121/// NOTE: [`Self::new`] only skips expensive (non-constant cost) validation checks (marked by `(*)`
122/// in the list above); it panics any of the other checks fails.
123///
124/// # Safety
125///
126/// Even an _invalid_ variant metadata instance is still _safe_ to use in the Rust sense. Accessing
127/// it with infallible methods may cause panics but will never lead to undefined behavior.
128///
129/// [`Variant`]: crate::Variant
130/// [Variant Spec]: https://github.com/apache/parquet-format/blob/master/VariantEncoding.md#metadata-encoding
131#[derive(Debug, Clone, PartialEq)]
132pub struct VariantMetadata<'m> {
133 /// (Only) the bytes that make up this metadata instance.
134 pub(crate) bytes: &'m [u8],
135 header: VariantMetadataHeader,
136 dictionary_size: u32,
137 first_value_byte: u32,
138 validated: bool,
139}
140
141// We don't want this to grow because it increases the size of VariantList and VariantObject, which
142// could increase the size of Variant. All those size increases could hurt performance.
143#[cfg(target_pointer_width = "64")]
144const _: () = crate::utils::expect_size_of::<VariantMetadata>(32);
145
146#[cfg(target_pointer_width = "32")]
147const _: () = crate::utils::expect_size_of::<VariantMetadata>(20);
148
149/// The canonical byte slice corresponding to an empty metadata dictionary.
150///
151/// ```
152/// # use parquet_variant::{EMPTY_VARIANT_METADATA_BYTES, VariantMetadata, WritableMetadataBuilder};
153/// let mut metadata_builder = WritableMetadataBuilder::default();
154/// metadata_builder.finish();
155/// let metadata_bytes = metadata_builder.into_inner();
156/// assert_eq!(&metadata_bytes, EMPTY_VARIANT_METADATA_BYTES);
157/// ```
158pub const EMPTY_VARIANT_METADATA_BYTES: &[u8] = &[1, 0, 0];
159
160/// The empty metadata dictionary.
161///
162/// ```
163/// # use parquet_variant::{EMPTY_VARIANT_METADATA, VariantMetadata, WritableMetadataBuilder};
164/// let mut metadata_builder = WritableMetadataBuilder::default();
165/// metadata_builder.finish();
166/// let metadata_bytes = metadata_builder.into_inner();
167/// let empty_metadata = VariantMetadata::try_new(&metadata_bytes).unwrap();
168/// assert_eq!(empty_metadata, EMPTY_VARIANT_METADATA);
169/// ```
170pub const EMPTY_VARIANT_METADATA: VariantMetadata = VariantMetadata {
171 bytes: EMPTY_VARIANT_METADATA_BYTES,
172 header: VariantMetadataHeader {
173 version: CORRECT_VERSION_VALUE,
174 is_sorted: false,
175 offset_size: OffsetSizeBytes::One,
176 },
177 dictionary_size: 0,
178 first_value_byte: 3,
179 validated: true,
180};
181
182impl<'m> VariantMetadata<'m> {
183 /// Attempts to interpret `bytes` as a variant metadata instance, with full [validation] of all
184 /// dictionary entries.
185 ///
186 /// [validation]: Self#Validation
187 pub fn try_new(bytes: &'m [u8]) -> Result<Self, ArrowError> {
188 Self::try_new_with_shallow_validation(bytes)?.with_full_validation()
189 }
190
191 /// Interprets `bytes` as a variant metadata instance, without attempting to [validate] dictionary
192 /// entries. Panics if basic sanity checking fails, and subsequent infallible accesses such as
193 /// indexing and iteration could also panic if the underlying bytes are invalid.
194 ///
195 /// This constructor can be a useful lightweight alternative to [`Self::try_new`] if the bytes
196 /// were already validated previously by other means, or if the caller expects a small number of
197 /// accesses to a large dictionary (preferring to use a small number of fallible accesses as
198 /// needed, instead of paying expensive full validation up front).
199 ///
200 /// [validate]: Self#Validation
201 ///
202 /// # Panics
203 ///
204 /// Panics if basic sanity checking fails. Use [`Self::try_new`] for a fallible version.
205 pub fn new(bytes: &'m [u8]) -> Self {
206 Self::try_new_with_shallow_validation(bytes).expect("Invalid variant metadata")
207 }
208
209 // The actual constructor, which performs only basic (constant-const) validation.
210 pub(crate) fn try_new_with_shallow_validation(bytes: &'m [u8]) -> Result<Self, ArrowError> {
211 let header_byte = first_byte_from_slice(bytes)?;
212 let header = VariantMetadataHeader::try_new(header_byte)?;
213
214 // First element after header is dictionary size; the offset array immediately follows.
215 let dictionary_size =
216 header
217 .offset_size
218 .unpack_u32_at_offset(bytes, NUM_HEADER_BYTES as usize, 0)?;
219
220 // Calculate the starting offset of the dictionary string bytes.
221 //
222 // There are dict_size + 1 offsets, and the value bytes immediately follow
223 // = (dict_size + 1) * offset_size + header.first_offset_byte()
224 let first_value_byte = dictionary_size
225 .checked_add(1)
226 .and_then(|n| n.checked_mul(header.offset_size()))
227 .and_then(|n| n.checked_add(header.first_offset_byte()))
228 .ok_or_else(|| overflow_error("offset of variant metadata dictionary"))?;
229
230 let mut new_self = Self {
231 bytes,
232 header,
233 dictionary_size,
234 first_value_byte,
235 validated: false,
236 };
237
238 // Validate just the first and last offset, ignoring the other offsets and all value bytes.
239 let first_offset = new_self.get_offset(0)?;
240 if first_offset != 0 {
241 return Err(ArrowError::InvalidArgumentError(format!(
242 "First offset is not zero: {first_offset}"
243 )));
244 }
245
246 // Use the last offset to upper-bound the byte slice
247 let last_offset = new_self
248 .get_offset(dictionary_size as _)?
249 .checked_add(first_value_byte)
250 .ok_or_else(|| overflow_error("variant metadata size"))?;
251 new_self.bytes = slice_from_slice(bytes, ..last_offset as _)?;
252 Ok(new_self)
253 }
254
255 /// The number of metadata dictionary entries
256 pub fn len(&self) -> usize {
257 self.dictionary_size as _
258 }
259
260 /// True if this metadata dictionary contains no entries
261 pub fn is_empty(&self) -> bool {
262 self.len() == 0
263 }
264
265 /// True if this instance is fully [validated] for panic-free infallible accesses.
266 ///
267 /// [validated]: Self#Validation
268 pub fn is_fully_validated(&self) -> bool {
269 self.validated
270 }
271
272 /// Performs a full [validation] of this metadata dictionary and returns the result.
273 ///
274 /// [validation]: Self#Validation
275 pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
276 if !self.validated {
277 let offset_bytes = slice_from_slice(
278 self.bytes,
279 self.header.first_offset_byte() as _..self.first_value_byte as _,
280 )?;
281
282 // Verify the string values in the dictionary are UTF-8 encoded strings.
283 let value_buffer =
284 string_from_slice(self.bytes, 0, self.first_value_byte as _..self.bytes.len())?;
285
286 let mut offsets = map_bytes_to_offsets(offset_bytes, self.header.offset_size);
287 let mut current_offset = offsets.next().unwrap_or(0);
288
289 if self.header.is_sorted {
290 // Validate the dictionary values are unique and lexicographically sorted
291 //
292 // Since we use the offsets to access dictionary values, this also validates
293 // offsets are in-bounds and monotonically increasing
294 let mut prev_value: Option<&str> = None;
295 for next_offset in offsets {
296 let current_value = value_buffer.get(current_offset..next_offset).ok_or_else(
297 || {
298 ArrowError::InvalidArgumentError(format!(
299 "range {current_offset}..{next_offset} is invalid or out of bounds"
300 ))
301 },
302 )?;
303
304 if let Some(prev_val) = prev_value
305 && current_value <= prev_val
306 {
307 return Err(ArrowError::InvalidArgumentError(
308 "dictionary values are not unique and ordered".to_string(),
309 ));
310 }
311
312 prev_value = Some(current_value);
313 current_offset = next_offset;
314 }
315 } else {
316 // Slicing each dictionary value validates that offsets are in-bounds, non-decreasing,
317 // and land on UTF-8 character boundaries. Equal offsets are legal: they encode an
318 // empty dictionary entry.
319 for next_offset in offsets {
320 value_buffer
321 .get(current_offset..next_offset)
322 .ok_or_else(|| {
323 ArrowError::InvalidArgumentError(format!(
324 "range {current_offset}..{next_offset} is invalid or out of bounds"
325 ))
326 })?;
327 current_offset = next_offset;
328 }
329 }
330
331 self.validated = true;
332 }
333 Ok(self)
334 }
335
336 /// Whether the dictionary keys are sorted and unique
337 pub fn is_sorted(&self) -> bool {
338 self.header.is_sorted
339 }
340
341 /// The variant protocol version
342 pub const fn version(&self) -> u8 {
343 self.header.version
344 }
345
346 /// Gets an offset into the dictionary entry by index.
347 ///
348 /// This offset is an index into the dictionary, at the boundary between string `i-1` and string
349 /// `i`. See [`Self::get`] to retrieve a specific dictionary entry.
350 fn get_offset(&self, i: usize) -> Result<u32, ArrowError> {
351 let offset_byte_range = self.header.first_offset_byte() as _..self.first_value_byte as _;
352 let bytes = slice_from_slice(self.bytes, offset_byte_range)?;
353 self.header.offset_size.unpack_u32(bytes, i)
354 }
355
356 /// Returns the total size, in bytes, of the metadata.
357 ///
358 /// Note this value may be smaller than what was passed to [`Self::new`] or
359 /// [`Self::try_new`] if the input was larger than necessary to encode the
360 /// metadata dictionary.
361 pub fn size(&self) -> usize {
362 self.bytes.len()
363 }
364
365 /// Attempts to retrieve a dictionary entry by index, failing if out of bounds or if the
366 /// underlying bytes are [invalid].
367 ///
368 /// [invalid]: Self#Validation
369 pub fn get(&self, i: usize) -> Result<&'m str, ArrowError> {
370 let byte_range = self.get_offset(i)? as _..self.get_offset(i + 1)? as _;
371 if !self.validated {
372 return string_from_slice(self.bytes, self.first_value_byte as _, byte_range);
373 }
374
375 // Full validation already proved every dictionary entry is valid UTF-8, so validating
376 // again here would charge that cost once per field access instead of once per buffer.
377 let value_bytes =
378 slice_from_slice_at_offset(self.bytes, self.first_value_byte as _, byte_range)?;
379
380 debug_assert!(std::str::from_utf8(value_bytes).is_ok());
381
382 // SAFETY: `validated` is set only by `with_full_validation`, which proved that every
383 // dictionary entry, including this one, is valid UTF-8.
384 Ok(unsafe { str::from_utf8_unchecked(value_bytes) })
385 }
386
387 // Helper method used by our `impl Index` and also by `get_entry`. Panics if the underlying
388 // bytes are invalid. Needed because the `Index` trait forces the returned result to have the
389 // lifetime of `self` instead of the string's own (longer) lifetime `'m`.
390 fn get_impl(&self, i: usize) -> &'m str {
391 self.get(i).expect("Invalid metadata dictionary entry")
392 }
393
394 /// Attempts to retrieve a dictionary entry and its field id, returning None if the requested field
395 /// name is not present. The search cost is logarithmic if [`Self::is_sorted`] and linear
396 /// otherwise.
397 ///
398 /// # Panics
399 ///
400 /// Panics if the underlying bytes are [invalid].
401 ///
402 /// [invalid]: Self#Validation
403 pub fn get_entry(&self, field_name: &str) -> Option<(u32, &'m str)> {
404 let field_id = if self.is_sorted() && self.len() > 10 {
405 // Binary search is faster for a not-tiny sorted metadata dictionary
406 let cmp = |i| Some(self.get_impl(i).cmp(field_name));
407 try_binary_search_range_by(0..self.len(), cmp)?.ok()?
408 } else {
409 // Fall back to Linear search for tiny or unsorted dictionary
410 (0..self.len()).find(|i| self.get_impl(*i) == field_name)?
411 };
412 Some((field_id as u32, self.get_impl(field_id)))
413 }
414
415 /// Returns an iterator that attempts to visit all dictionary entries, producing `Err` if the
416 /// iterator encounters [invalid] data.
417 ///
418 /// [invalid]: Self#Validation
419 pub fn iter_try(&self) -> impl Iterator<Item = Result<&'m str, ArrowError>> + '_ {
420 (0..self.len()).map(|i| self.get(i))
421 }
422
423 /// Iterates over all dictionary entries. When working with [unvalidated] input, consider
424 /// [`Self::iter_try`] to avoid panics due to invalid data.
425 ///
426 /// [unvalidated]: Self#Validation
427 ///
428 /// # Panics
429 ///
430 /// Panics if the underlying bytes are invalid. Use [`Self::iter_try`] for a
431 /// fallible version.
432 pub fn iter(&self) -> impl Iterator<Item = &'m str> + '_ {
433 self.iter_try()
434 .map(|result| result.expect("Invalid metadata dictionary entry"))
435 }
436}
437
438/// Retrieves the ith dictionary entry, panicking if the index is out of bounds. Accessing
439/// [unvalidated] input could also panic if the underlying bytes are invalid.
440///
441/// [unvalidated]: Self#Validation
442impl std::ops::Index<usize> for VariantMetadata<'_> {
443 type Output = str;
444
445 fn index(&self, i: usize) -> &str {
446 self.get_impl(i)
447 }
448}
449
450#[cfg(test)]
451mod tests {
452
453 use crate::VariantBuilder;
454
455 use super::*;
456
457 /// `"cat"`, `"dog"` – valid metadata
458 #[test]
459 fn try_new_ok_inline() {
460 let bytes = &[
461 0b0000_0001, // header, offset_size_minus_one=0 and version=1
462 0x02, // dictionary_size (2 strings)
463 0x00,
464 0x03,
465 0x06,
466 b'c',
467 b'a',
468 b't',
469 b'd',
470 b'o',
471 b'g',
472 ];
473
474 let md = VariantMetadata::try_new(bytes).expect("should parse");
475 assert_eq!(md.len(), 2);
476 // Fields
477 assert_eq!(&md[0], "cat");
478 assert_eq!(&md[1], "dog");
479
480 // Offsets
481 assert_eq!(md.get_offset(0).unwrap(), 0x00);
482 assert_eq!(md.get_offset(1).unwrap(), 0x03);
483 assert_eq!(md.get_offset(2).unwrap(), 0x06);
484
485 let err = md.get_offset(3).unwrap_err();
486 assert!(
487 matches!(err, ArrowError::InvalidArgumentError(_)),
488 "unexpected error: {err:?}"
489 );
490
491 let fields: Vec<(usize, &str)> = md.iter().enumerate().collect();
492 assert_eq!(fields, vec![(0usize, "cat"), (1usize, "dog")]);
493 }
494
495 /// Too short buffer test (missing one required offset).
496 /// Should error with "metadata shorter than dictionary_size implies".
497 #[test]
498 fn try_new_missing_last_value() {
499 let bytes = &[
500 0b0000_0001, // header, offset_size_minus_one=0 and version=1
501 0x02, // dictionary_size = 2
502 0x00,
503 0x01,
504 0x02,
505 b'a',
506 b'b', // <-- we'll remove this
507 ];
508
509 let working_md = VariantMetadata::try_new(bytes).expect("should parse");
510 assert_eq!(working_md.len(), 2);
511 assert_eq!(&working_md[0], "a");
512 assert_eq!(&working_md[1], "b");
513
514 let truncated = &bytes[..bytes.len() - 1];
515
516 let err = VariantMetadata::try_new(truncated).unwrap_err();
517 assert!(
518 matches!(err, ArrowError::InvalidArgumentError(_)),
519 "unexpected error: {err:?}"
520 );
521 }
522
523 #[test]
524 fn try_new_fails_non_monotonic() {
525 // 'cat', 'dog', 'lamb'
526 let bytes = &[
527 0b0000_0001, // header, offset_size_minus_one=0 and version=1
528 0x03, // dictionary_size
529 0x00,
530 0x02,
531 0x01, // Doesn't increase monotonically
532 0x10,
533 b'c',
534 b'a',
535 b't',
536 b'd',
537 b'o',
538 b'g',
539 b'l',
540 b'a',
541 b'm',
542 b'b',
543 ];
544
545 let err = VariantMetadata::try_new(bytes).unwrap_err();
546 assert!(
547 matches!(err, ArrowError::InvalidArgumentError(_)),
548 "unexpected error: {err:?}"
549 );
550 }
551
552 #[test]
553 fn try_new_fails_non_monotonic2() {
554 // this test case checks whether offsets are monotonic in the full validation logic.
555
556 // 'cat', 'dog', 'lamb', "eel"
557 let bytes = &[
558 0b0000_0001, // header, offset_size_minus_one=0 and version=1
559 4, // dictionary_size
560 0x00,
561 0x02,
562 0x01, // Doesn't increase monotonically
563 0x10,
564 13,
565 b'c',
566 b'a',
567 b't',
568 b'd',
569 b'o',
570 b'g',
571 b'l',
572 b'a',
573 b'm',
574 b'b',
575 b'e',
576 b'e',
577 b'l',
578 ];
579
580 let err = VariantMetadata::try_new(bytes).unwrap_err();
581
582 assert!(
583 matches!(err, ArrowError::InvalidArgumentError(_)),
584 "unexpected error: {err:?}"
585 );
586 }
587
588 #[test]
589 fn try_new_truncated_offsets_inline() {
590 // Missing final offset
591 let bytes = &[0b0000_0001, 0x02, 0x00, 0x01];
592
593 let err = VariantMetadata::try_new(bytes).unwrap_err();
594 assert!(
595 matches!(err, ArrowError::InvalidArgumentError(_)),
596 "unexpected error: {err:?}"
597 );
598 }
599
600 #[test]
601 fn empty_string_is_valid() {
602 let bytes = &[
603 0b0001_0001, // header: offset_size_minus_one=0, ordered=1, version=1
604 1,
605 0x00,
606 0x00,
607 ];
608 let metadata = VariantMetadata::try_new(bytes).unwrap();
609 assert_eq!(&metadata[0], "");
610
611 let bytes = &[
612 0b0001_0001, // header: offset_size_minus_one=0, ordered=1, version=1
613 2,
614 0x00,
615 0x00,
616 0x02,
617 b'h',
618 b'i',
619 ];
620 let metadata = VariantMetadata::try_new(bytes).unwrap();
621 assert_eq!(&metadata[0], "");
622 assert_eq!(&metadata[1], "hi");
623
624 let bytes = &[
625 0b0001_0001, // header: offset_size_minus_one=0, ordered=1, version=1
626 2,
627 0x00,
628 0x02,
629 0x02, // empty string is allowed, but must be first in a sorted dict
630 b'h',
631 b'i',
632 ];
633 let err = VariantMetadata::try_new(bytes).unwrap_err();
634 assert!(
635 matches!(err, ArrowError::InvalidArgumentError(_)),
636 "unexpected error: {err:?}"
637 );
638
639 let bytes = &[
640 0b0000_0001, // header: offset_size_minus_one=0, ordered=0, version=1
641 2,
642 0x00,
643 0x02,
644 0x02, // an unsorted dict may hold an empty string anywhere
645 b'h',
646 b'i',
647 ];
648 let metadata = VariantMetadata::try_new(bytes).unwrap();
649 assert_eq!(&metadata[0], "hi");
650 assert_eq!(&metadata[1], "");
651 }
652
653 #[test]
654 fn test_compare_sorted_dictionary_with_unsorted_dictionary() {
655 // create a sorted object
656 let mut b = VariantBuilder::new();
657 let mut o = b.new_object();
658
659 o.insert("a", false);
660 o.insert("b", false);
661
662 o.finish();
663
664 let (m, _) = b.finish();
665
666 let m1 = VariantMetadata::new(&m);
667 assert!(m1.is_sorted());
668
669 // Create metadata with an unsorted dictionary (field names are "a", "a", "b")
670 // Since field names are not unique, it is considered not sorted.
671 let metadata_bytes = vec![
672 0b0000_0001,
673 3, // dictionary size
674 0, // "a"
675 1, // "a"
676 2, // "b"
677 3,
678 b'a',
679 b'a',
680 b'b',
681 ];
682 let m2 = VariantMetadata::try_new(&metadata_bytes).unwrap();
683 assert!(!m2.is_sorted());
684
685 assert_ne!(m1, m2);
686 }
687
688 #[test]
689 fn test_compare_sorted_dictionary_with_sorted_dictionary() {
690 // create a sorted object
691 let mut b = VariantBuilder::new();
692 let mut o = b.new_object();
693
694 o.insert("a", false);
695 o.insert("b", false);
696
697 o.finish();
698
699 let (m, _) = b.finish();
700
701 let m1 = VariantMetadata::new(&m);
702 let m2 = VariantMetadata::new(&m);
703
704 assert_eq!(m1, m2);
705 }
706
707 #[test]
708 fn test_empty_string_field_names() {
709 // Field names are added to the dictionary in insertion order, so this dictionary is
710 // unsorted, and the empty field name makes its last two offsets equal.
711 let mut b = VariantBuilder::new().with_field_names(["b", "a", ""]);
712 let mut o = b.new_object();
713
714 o.insert("b", false);
715 o.insert("a", false);
716 o.insert("", false);
717
718 o.finish();
719
720 let (m, _) = b.finish();
721
722 let metadata = VariantMetadata::try_new(&m).unwrap();
723 assert!(!metadata.is_sorted());
724 assert_eq!(metadata.iter().collect::<Vec<_>>(), vec!["b", "a", ""]);
725 }
726
727 /// Builds a metadata buffer directly, so that offsets which a builder would never emit can be
728 /// exercised. `values` is the raw dictionary value region.
729 fn raw_metadata(is_sorted: bool, offsets: &[u8], values: &[u8]) -> Vec<u8> {
730 let mut bytes = vec![0x01 | (u8::from(is_sorted) << 4)];
731 bytes.push(offsets.len() as u8 - 1); // dictionary_size
732 bytes.extend_from_slice(offsets);
733 bytes.extend_from_slice(values);
734 bytes
735 }
736
737 /// `get` skips UTF-8 revalidation once the metadata is fully validated, so full validation has
738 /// to reject offsets that split a multi-byte character. Otherwise a validated instance could
739 /// hand out a `&str` over a partial character.
740 #[test]
741 fn full_validation_rejects_offsets_splitting_a_character() {
742 // "é" is two bytes, so an offset of 1 lands inside it. The value region as a whole is
743 // still valid UTF-8, so only the per-entry check can catch this.
744 for is_sorted in [false, true] {
745 let bytes = raw_metadata(is_sorted, &[0, 1, 2], "é".as_bytes());
746
747 // Shallow validation looks only at the first and last offset, so it accepts.
748 let shallow = VariantMetadata::try_new_with_shallow_validation(&bytes).unwrap();
749 assert!(!shallow.is_fully_validated());
750 // ... and the fallible accessor reports the bad entry rather than panicking.
751 assert!(shallow.get(0).is_err());
752
753 // Full validation must reject the buffer outright.
754 assert!(
755 VariantMetadata::try_new(&bytes).is_err(),
756 "is_sorted={is_sorted}: full validation accepted offsets splitting a character"
757 );
758 }
759 }
760
761 /// Validated and unvalidated instances must agree on every entry, including multi-byte
762 /// characters and empty entries, since they take different code paths inside `get`.
763 #[test]
764 fn validated_and_unvalidated_get_agree() {
765 // Unsorted so that the dictionary order below is preserved verbatim.
766 let values = "aé€\u{10348}"; // 1, 2, 3 and 4 byte characters
767 let offsets: &[u8] = &[0, 1, 1, 3, 6, 10]; // note the repeated 1: an empty entry
768 let bytes = raw_metadata(false, offsets, values.as_bytes());
769
770 let validated = VariantMetadata::try_new(&bytes).unwrap();
771 assert!(validated.is_fully_validated());
772 let unvalidated = VariantMetadata::try_new_with_shallow_validation(&bytes).unwrap();
773 assert!(!unvalidated.is_fully_validated());
774
775 let expected = ["a", "", "é", "€", "\u{10348}"];
776 assert_eq!(validated.len(), expected.len());
777 for (i, want) in expected.iter().enumerate() {
778 assert_eq!(validated.get(i).unwrap(), *want, "validated get({i})");
779 assert_eq!(unvalidated.get(i).unwrap(), *want, "unvalidated get({i})");
780 }
781
782 // Out of bounds stays an error on both paths, rather than reading past the offset array.
783 assert!(validated.get(expected.len()).is_err());
784 assert!(unvalidated.get(expected.len()).is_err());
785 }
786
787 /// An unvalidated instance still reports invalid UTF-8 through the fallible accessor.
788 #[test]
789 fn unvalidated_get_still_reports_invalid_utf8() {
790 let bytes = raw_metadata(false, &[0, 1], &[0xFF]);
791 let unvalidated = VariantMetadata::try_new_with_shallow_validation(&bytes).unwrap();
792 assert!(unvalidated.get(0).is_err());
793 assert!(VariantMetadata::try_new(&bytes).is_err());
794 }
795}