This is an automated email from the ASF dual-hosted git repository.
sdf-jkl pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
The following commit(s) were added to refs/heads/main by this push:
new f9e02ba76a perf(variant): resolve borrowed field names without
searching the metadata dictionary (#10882)
f9e02ba76a is described below
commit f9e02ba76ad11e1380b559735ac912c602b604fb
Author: Adrian Garcia Badaracco <[email protected]>
AuthorDate: Thu Sep 10 07:28:44 2026 -0500
perf(variant): resolve borrowed field names without searching the metadata
dictionary (#10882)
# Which issue does this PR close?
- Closes #10881.
# Rationale for this change
`VariantMetadata::get_entry` resolves a field name to a field id by
searching the
dictionary, decoding and comparing dictionary strings as it goes (linear
for an
unsorted dictionary, logarithmic for a large sorted one).
Several paths copy fields out of a variant object and back into a
builder that
shares that object's metadata dictionary. `shred_variant` writes every
field the
shredding schema does not cover into the leftover `value` column, and
projection
paths do the same. In all of them the field name handed to the builder
came from
`VariantObject::iter`, which produced it by looking up a field id in
that very
dictionary. Searching for it by name is a round trip: the id was already
known,
and the search spends string comparisons recovering it.
`ReadOnlyMetadataBuilder` has a `known_field_names` cache intended to
absorb this
cost, but it cannot help here. `VariantValueArrayBuilder::builder_ext`
constructs
a fresh `ReadOnlyMetadataBuilder` per value, so in a per-row builder the
cache is
populated and dropped again on every row, never serving a lookup, and
each row
pays to hash names it will never see again.
In a CPU profile of the `shred_variant_unmatched_object_8k_rows`
benchmark added
here, `ReadOnlyMetadataBuilder::try_upsert_field_name` accounted for
about 57% of
`shred_variant`. After this change it accounts for about 20%, and
`get_entry` no
longer appears in the hot path.
# What changes are included in this PR?
- `VariantMetadata::borrowed_field_id` (crate-private). A field name
that is a
slice of the dictionary's own value region already encodes its field id:
it
belongs to the entry whose offset equals the name's distance from the
start of
that region. This finds the entry with a binary search over the offset
array,
comparing integers instead of decoding dictionary strings, and confirms
the hit
by comparing lengths rather than bytes.
A candidate is accepted only when it starts at the name's address and
has the
name's length, which makes the entry's bytes and the name's bytes the
same
bytes. Anything else, including a name that borrows from elsewhere, a
slice of
an entry, or metadata with arbitrary offsets, falls back to the existing
search. Addresses are only ever compared as integers, never
dereferenced.
This is attempted only for a **sorted** dictionary; see "Why sorted
only"
below.
- `VariantMetadata::get_entry` tries the above first, so all callers
benefit.
Cost for callers this cannot help: `get_entry` is public, and a name
looked up
against a sorted dictionary that does not borrow from it now runs the
address
range check before the existing search. That check short circuits on a
failed
comparison, so such a caller pays a few integer operations and nothing
else.
The one case that pays more is a name pointing into the value region
without
starting an entry, for example a substring of one: that costs a binary
search
over the offset array before falling back. Against an unsorted
dictionary the
added cost is a single boolean test. All three are bounded, but I would
rather
state them than have them found in review.
- `ReadOnlyMetadataBuilder::try_upsert_field_name` tries it before
consulting
`known_field_names`, so the paths described above do no hashing at all.
The
cache still serves field names that do not borrow from the dictionary,
and all
field names when the dictionary is unsorted.
- `shred_variant` reuses one scratch buffer to track which shredded
fields a row
supplied, instead of allocating a `HashSet` per row.
- Two new benchmarks in
`parquet-variant-compute/benches/variant_kernels.rs`
covering objects that the shredding schema matches partially and not at
all.
## Why sorted only
Thanks to @sdf-jkl for catching this; an earlier revision of this PR did
not
restrict the fast path, and was wrong.
[The spec][spec] requires dictionary entries to be unique only when
`sorted_strings` is set: "If the value is set to 0, readers may not make
any
assumptions about string order or uniqueness." So an unsorted dictionary
may
legally hold the same string at more than one field id, and this crate
already
relies on that — `with_full_validation` checks uniqueness only in the
sorted
branch, and `test_object_rejects_duplicate_field_names` covers exactly
such a
dictionary.
For such a dictionary, resolving a borrowed name by the id it came from
disagrees with resolving the same string by name. That is not a cosmetic
difference in which id gets picked, because `ObjectBuilder` detects
duplicate
fields by comparing field ids: two ids naming the same string defeat
`validate_unique_fields`, and with validation off they build an object
whose
field names are not unique, which `Variant::try_new` then rejects with
"field
names not sorted".
Restricting `borrowed_field_id` to sorted dictionaries removes that
entirely,
because validation rejects a sorted dictionary with duplicate entries,
so the id
a name was borrowed from is necessarily the id a search by name returns.
An
unsorted dictionary goes back to the `known_field_names` cache and the
existing
name search, exactly as before this PR.
The cost is that the fast path no longer applies to unsorted
dictionaries, where
`get_entry` can only search linearly. The benchmarks here build a sorted
dictionary (300 entries, `is_sorted() == true`), so the profile numbers
above are
unaffected by the restriction; recovering the unsorted case would need a
duplicate-free flag computed during validation, which I would rather
measure
separately than fold in here.
[spec]:
https://github.com/apache/parquet-format/blob/master/VariantEncoding.md#metadata-encoding-grammar
# Are these changes tested?
Yes. New unit tests cover sorted and unsorted dictionaries, agreement
between the
borrowed lookup, `get_entry`, and lookups by an owned (non-borrowed)
copy of the
same name, names borrowed from a different dictionary that must not be
resolved
against this one, a slice of an entry that shares its start offset
without being
equal to it, an unsorted dictionary holding the same string twice, and
empty
field names in both a sorted and an unsorted dictionary.
Two regression tests build objects through a `ReadOnlyMetadataBuilder`
over an
unsorted `["a", "a"]` dictionary: one asserts that
`validate_unique_fields`
rejects the second insert, and one asserts that a borrowed name and an
owned copy
of it collapse to a single field rather than producing a value that
fails
validation. Both fail if the sortedness restriction is removed.
The existing `parquet-variant`, `parquet-variant-compute`,
`parquet-variant-json`,
proptest fuzz, and `variant_interop` suites pass unchanged.
The two new benchmarks cover 8192 rows over a 300-entry dictionary with
15-field
objects. I am deliberately not posting timings yet. The machine
available to me is
heavily contended, and a paired interleaved probe there produced a 65%
spread
within a single invocation on identical work, so any speedup figure from
it would
be indistinguishable from noise. I will follow up with numbers from a
quiet
machine, measured with interleaved arms and with unaffected control
benchmarks
used to certify that the run is valid.
# Are there any user-facing changes?
No. There are no public API changes, and `get_entry` returns exactly
what it
returned before this PR for every input, including a dictionary that
holds the
same string at more than one field id.
---------
Co-authored-by: Claude Opus 5 <[email protected]>
Co-authored-by: Kosta Tarasov <[email protected]>
---
parquet-variant-compute/benches/variant_kernels.rs | 55 +++-
parquet-variant-compute/src/shred_variant.rs | 30 ++-
parquet-variant/src/builder/metadata.rs | 13 +
parquet-variant/src/builder/object.rs | 62 +++++
parquet-variant/src/variant/metadata.rs | 294 +++++++++++++++++++++
5 files changed, 444 insertions(+), 10 deletions(-)
diff --git a/parquet-variant-compute/benches/variant_kernels.rs
b/parquet-variant-compute/benches/variant_kernels.rs
index 7fec1ed786..e06c0e0b1e 100644
--- a/parquet-variant-compute/benches/variant_kernels.rs
+++ b/parquet-variant-compute/benches/variant_kernels.rs
@@ -21,7 +21,7 @@ use arrow_schema::{DataType, Field, FieldRef, Fields};
use criterion::{BatchSize, Criterion, criterion_group, criterion_main};
use parquet_variant::{EMPTY_VARIANT_METADATA_BYTES, Variant, VariantBuilder,
VariantPath};
use parquet_variant_compute::{
- GetOptions, VariantArray, VariantArrayBuilder, json_to_variant,
variant_get,
+ GetOptions, VariantArray, VariantArrayBuilder, json_to_variant,
shred_variant, variant_get,
};
use parquet_variant_json::append_json;
use rand::RngExt;
@@ -34,6 +34,7 @@ use std::sync::Arc;
const VARIANT_GET_UNSHREDDED_OBJECT_ROWS: usize = 262_144;
const VARIANT_ARRAY_BUILD_ROWS: usize = 262_144;
+const SHRED_VARIANT_OBJECT_ROWS: usize = 8_192;
fn variant_array_builder_build_bench(c: &mut Criterion) {
c.bench_function("variant_array_builder_build_262k_small_values", |b| {
@@ -201,11 +202,63 @@ pub fn variant_get_unshredded_object_path_bench(c: &mut
Criterion) {
});
}
+/// Shreds objects whose fields only partially match the requested shredding
schema.
+///
+/// Every field that is *not* covered by the schema is copied into the
leftover `value` column,
+/// which requires the builder to resolve that field's name back to its id in
the row's metadata
+/// dictionary. The source array's dictionary holds 300 field names, so the
cost of that name
+/// lookup is visible.
+pub fn shred_variant_partial_object_bench(c: &mut Criterion) {
+ let variant_array =
create_unshredded_object_variant_array(SHRED_VARIANT_OBJECT_ROWS);
+
+ // The source objects have 15 fields (`attr.000`, `attr.020`, ...
`attr.280`). Shred the first
+ // 5 of them, leaving the other 10 to be written to the leftover `value`
column.
+ let shredded_fields = (0..300)
+ .step_by(20)
+ .take(5)
+ .map(|index| {
+ Arc::new(Field::new(
+ format!("attr.{index:03}"),
+ DataType::Int32,
+ true,
+ ))
+ })
+ .collect::<Vec<FieldRef>>();
+ let as_type = DataType::Struct(Fields::from(shredded_fields));
+
+ c.bench_function("shred_variant_partial_object_8k_rows", |b| {
+ b.iter(|| std::hint::black_box(shred_variant(&variant_array,
&as_type).unwrap()))
+ });
+}
+
+/// Same as [`shred_variant_partial_object_bench`], but no field of the source
objects is covered
+/// by the shredding schema, so all 15 fields per row take the leftover
`value` column path.
+pub fn shred_variant_unmatched_object_bench(c: &mut Criterion) {
+ let variant_array =
create_unshredded_object_variant_array(SHRED_VARIANT_OBJECT_ROWS);
+
+ let shredded_fields = (0..5)
+ .map(|index| {
+ Arc::new(Field::new(
+ format!("missing.{index}"),
+ DataType::Int32,
+ true,
+ ))
+ })
+ .collect::<Vec<FieldRef>>();
+ let as_type = DataType::Struct(Fields::from(shredded_fields));
+
+ c.bench_function("shred_variant_unmatched_object_8k_rows", |b| {
+ b.iter(|| std::hint::black_box(shred_variant(&variant_array,
&as_type).unwrap()))
+ });
+}
+
criterion_group!(
benches,
variant_get_bench,
variant_get_shredded_utf8_bench,
variant_get_unshredded_object_path_bench,
+ shred_variant_partial_object_bench,
+ shred_variant_unmatched_object_bench,
variant_array_builder_build_bench,
benchmark_batch_json_string_to_variant
);
diff --git a/parquet-variant-compute/src/shred_variant.rs
b/parquet-variant-compute/src/shred_variant.rs
index 751d926d4a..6c4af06d51 100644
--- a/parquet-variant-compute/src/shred_variant.rs
+++ b/parquet-variant-compute/src/shred_variant.rs
@@ -359,6 +359,9 @@ pub(crate) struct
VariantToShreddedObjectVariantRowBuilder<'a> {
typed_value_nulls: NullBufferBuilder,
nulls: NullBufferBuilder,
null_value: NullValue,
+ /// Scratch space marking which of `typed_value_builders` the current row
supplied a value for,
+ /// indexed the same way as `typed_value_builders`. Reused across rows.
+ seen: Vec<bool>,
}
impl<'a> VariantToShreddedObjectVariantRowBuilder<'a> {
@@ -379,9 +382,11 @@ impl<'a> VariantToShreddedObjectVariantRowBuilder<'a> {
)?;
Ok((field.name().as_str(), builder))
});
+ let typed_value_builders: IndexMap<_, _> =
typed_value_builders.collect::<Result<_>>()?;
Ok(Self {
value_builder: VariantValueArrayBuilder::new(capacity),
- typed_value_builders: typed_value_builders.collect::<Result<_>>()?,
+ seen: vec![false; typed_value_builders.len()],
+ typed_value_builders,
typed_value_nulls: NullBufferBuilder::new(capacity),
nulls: NullBufferBuilder::new(capacity),
null_value,
@@ -411,15 +416,21 @@ impl<'a> VariantToShreddedObjectVariantRowBuilder<'a> {
};
// Route the object's fields by name as either shredded or unshredded
- let mut builder = self.value_builder.builder_ext(value.metadata());
+ let Self {
+ value_builder,
+ typed_value_builders,
+ seen,
+ ..
+ } = self;
+ seen.fill(false);
+ let mut builder = value_builder.builder_ext(value.metadata());
let mut object_builder = builder.try_new_object()?;
- let mut seen = std::collections::HashSet::new();
let mut partially_shredded = false;
for (field_name, value) in obj.iter() {
- match self.typed_value_builders.get_mut(field_name) {
- Some(typed_value_builder) => {
+ match typed_value_builders.get_full_mut(field_name) {
+ Some((index, _, typed_value_builder)) => {
typed_value_builder.append_value(value)?;
- seen.insert(field_name);
+ seen[index] = true;
}
None => {
object_builder.insert_bytes(field_name, value);
@@ -429,8 +440,8 @@ impl<'a> VariantToShreddedObjectVariantRowBuilder<'a> {
}
// Handle missing fields
- for (field_name, typed_value_builder) in &mut
self.typed_value_builders {
- if !seen.contains(field_name) {
+ for (index, (_, typed_value_builder)) in
typed_value_builders.iter_mut().enumerate() {
+ if !seen[index] {
typed_value_builder.append_null()?;
}
}
@@ -440,7 +451,8 @@ impl<'a> VariantToShreddedObjectVariantRowBuilder<'a> {
object_builder.finish();
} else {
drop(object_builder);
- self.value_builder.append_null();
+ drop(builder);
+ value_builder.append_null();
}
self.typed_value_nulls.append_non_null();
diff --git a/parquet-variant/src/builder/metadata.rs
b/parquet-variant/src/builder/metadata.rs
index 70b5d92167..8cde95e943 100644
--- a/parquet-variant/src/builder/metadata.rs
+++ b/parquet-variant/src/builder/metadata.rs
@@ -86,6 +86,8 @@ pub struct ReadOnlyMetadataBuilder<'m> {
metadata: &'m VariantMetadata<'m>,
// A cache that tracks field names this builder has already seen, because
finding the field id
// for a given field name is expensive -- O(n) for a large and unsorted
metadata dictionary.
+ // Field names borrowed from a sorted `metadata` bypass this cache; see
+ // `VariantMetadata::borrowed_field_id`.
known_field_names: HashMap<&'m str, u32>,
}
@@ -101,6 +103,17 @@ impl<'m> ReadOnlyMetadataBuilder<'m> {
impl MetadataBuilder for ReadOnlyMetadataBuilder<'_> {
fn try_upsert_field_name(&mut self, field_name: &str) -> Result<u32,
ArrowError> {
+ // Callers that copy fields out of an object and back into the same
metadata dictionary
+ // (unshredding, shredding, and projection all do this) pass field
names that are slices of
+ // the dictionary itself. For a sorted dictionary those resolve
without hashing or any
+ // string comparison, which matters because this builder is often
created per row and so
+ // its `known_field_names` cache would otherwise be populated and
discarded without ever
+ // serving a lookup. An unsorted dictionary may hold duplicate
entries, so it keeps using
+ // the cache and the name-based search below.
+ if let Some(field_id) = self.metadata.borrowed_field_id(field_name) {
+ return Ok(field_id);
+ }
+
if let Some(field_id) = self.known_field_names.get(field_name) {
return Ok(*field_id);
}
diff --git a/parquet-variant/src/builder/object.rs
b/parquet-variant/src/builder/object.rs
index 0f6138d07d..907cc47d00 100644
--- a/parquet-variant/src/builder/object.rs
+++ b/parquet-variant/src/builder/object.rs
@@ -539,6 +539,68 @@ mod tests {
assert_eq!(obj.get("active"), Some(Variant::from(true)));
}
+ /// A dictionary that is not marked sorted may legally hold the same
string at more than one
+ /// field id. A field name must still resolve to a single id, or an object
builder sharing that
+ /// dictionary would emit two fields with the same name.
+ ///
+ /// Metadata dictionary `["a", "a"]`, unsorted:
+ const DUPLICATE_ENTRY_METADATA: &[u8] = &[
+ 0b0000_0001, // header: offset_size_minus_one=0, sorted=0, version=1
+ 2, // dictionary_size
+ 0x00,
+ 0x01,
+ 0x02,
+ b'a',
+ b'a',
+ ];
+
+ #[test]
+ fn
test_read_only_metadata_builder_duplicate_dictionary_entries_are_detected() {
+ let metadata =
VariantMetadata::try_new(DUPLICATE_ENTRY_METADATA).unwrap();
+ assert!(!metadata.is_sorted());
+
+ let mut metadata_builder = ReadOnlyMetadataBuilder::new(&metadata);
+ let mut value_builder = ValueBuilder::new();
+ let state = ParentState::variant(&mut value_builder, &mut
metadata_builder);
+ let mut obj = ObjectBuilder::new(state, true);
+
+ // Both dictionary entries name "a", so inserting both must be
reported as a duplicate
+ // field name rather than producing an object with two fields named
"a".
+ obj.insert(metadata.get(0).unwrap(), 1i8);
+ let err = obj
+ .try_insert(metadata.get(1).unwrap(), 2i8)
+ .expect_err("duplicate field name should be rejected");
+ assert!(
+ err.to_string().contains("Duplicate field name"),
+ "unexpected error: {err}"
+ );
+ }
+
+ #[test]
+ fn
test_read_only_metadata_builder_duplicate_dictionary_entries_build_valid_object()
{
+ let metadata =
VariantMetadata::try_new(DUPLICATE_ENTRY_METADATA).unwrap();
+
+ let mut metadata_builder = ReadOnlyMetadataBuilder::new(&metadata);
+ let mut value_builder = ValueBuilder::new();
+ {
+ let state = ParentState::variant(&mut value_builder, &mut
metadata_builder);
+ let mut obj = ObjectBuilder::new(state, false);
+
+ // A name borrowed from the dictionary and an owned copy of that
same name must resolve
+ // to the same field id, so that the last write wins instead of
both being emitted.
+ obj.insert(metadata.get(1).unwrap(), 1i8);
+ let owned = String::from("a");
+ obj.insert(owned.as_str(), 2i8);
+ obj.finish();
+ }
+
+ let value = value_builder.into_inner();
+ let variant = Variant::try_new(DUPLICATE_ENTRY_METADATA,
&value).unwrap();
+ let obj = variant.as_object().unwrap();
+ assert_eq!(obj.len(), 1);
+ assert_eq!(obj.get("a"), Some(Variant::Int8(2)));
+ }
+
// matthew
#[test]
fn test_append_object() {
diff --git a/parquet-variant/src/variant/metadata.rs
b/parquet-variant/src/variant/metadata.rs
index b6f80508ee..99de7b6447 100644
--- a/parquet-variant/src/variant/metadata.rs
+++ b/parquet-variant/src/variant/metadata.rs
@@ -391,6 +391,78 @@ impl<'m> VariantMetadata<'m> {
self.get(i).expect("Invalid metadata dictionary entry")
}
+ /// Attempts to resolve `field_name` to its field id under the assumption
that `field_name` is
+ /// itself a slice of this dictionary's value region, as is the case for
every field name
+ /// obtained from [`VariantObject::field_name`] or [`Self::get`] on the
same metadata instance.
+ /// Returns `None` when that assumption does not hold, so callers must be
prepared to fall back
+ /// to a name-based search such as [`Self::get_entry`].
+ ///
+ /// This is much cheaper than searching by name, because a borrowed field
name already encodes
+ /// its own field id: it belongs to the entry whose dictionary offset
equals its distance from
+ /// the start of the value region. Finding that entry is a binary search
over the
+ /// (non-decreasing) offset array, comparing integers rather than decoding
and comparing
+ /// dictionary strings at every step, and it needs no string comparison to
confirm the hit.
+ ///
+ /// # Correctness
+ ///
+ /// This is only attempted for a [sorted] dictionary. The spec requires
dictionary entries to
+ /// be unique only when `sorted_strings` is set, so an unsorted dictionary
may legally hold the
+ /// same string at more than one field id. Resolving a borrowed name by
the id it came from
+ /// would then disagree with a resolution by name, and callers rely on a
name mapping to a
+ /// single id: [`ObjectBuilder`] detects duplicate fields by comparing
field ids, so two ids
+ /// naming the same string would build an object whose field names are not
unique. Requiring
+ /// sortedness makes the two resolutions agree, because validation rejects
a sorted dictionary
+ /// with duplicate entries.
+ ///
+ /// A returned field id is also always verified, so this never reports an
id whose entry is not
+ /// `field_name` itself, even for [invalid] metadata whose offsets are
arbitrary. The candidate
+ /// entry is accepted only when it starts at `field_name`'s address and
has exactly
+ /// `field_name`'s length, which makes the entry's bytes and
`field_name`'s bytes the same
+ /// bytes. (Two live allocations cannot overlap, so an address inside our
own byte range
+ /// belongs to our own bytes. In the degenerate zero-length case the two
are both empty and
+ /// therefore still equal.)
+ ///
+ /// [`ObjectBuilder`]: crate::ObjectBuilder
+ /// [`VariantObject::field_name`]: crate::VariantObject::field_name
+ /// [invalid]: Self#Validation
+ /// [sorted]: Self::is_sorted
+ pub(crate) fn borrowed_field_id(&self, field_name: &str) -> Option<u32> {
+ // An unsorted dictionary may hold duplicate entries, which would make
the id a name was
+ // borrowed from differ from the id a search by name returns; see
"Correctness" above.
+ if !self.is_sorted() {
+ return None;
+ }
+
+ // Addresses are compared as integers and never dereferenced, so this
stays safe even when
+ // `field_name` borrows from an unrelated allocation.
+ let value_region_start = (self.bytes.as_ptr() as usize) +
self.first_value_byte as usize;
+ let value_region_end = (self.bytes.as_ptr() as usize) +
self.bytes.len();
+ let field_name_start = field_name.as_ptr() as usize;
+ if field_name_start < value_region_start || field_name_start >=
value_region_end {
+ return None;
+ }
+ let field_name_offset = u32::try_from(field_name_start -
value_region_start).ok()?;
+
+ // Hoist the offset array out of the search, so each step is just an
unaligned load.
+ let offset_byte_range = self.header.first_offset_byte() as
_..self.first_value_byte as _;
+ let offsets = slice_from_slice(self.bytes, offset_byte_range).ok()?;
+ let offset_size = self.header.offset_size;
+ let cmp = |i| {
+ Some(
+ offset_size
+ .unpack_u32(offsets, i)
+ .ok()?
+ .cmp(&field_name_offset),
+ )
+ };
+ let field_id = try_binary_search_range_by(0..self.len(), cmp)?.ok()?;
+
+ // Verify that this entry has exactly `field_name`'s bytes; see
"Correctness" above.
+ let entry_end = offset_size.unpack_u32(offsets, field_id + 1).ok()?;
+ let entry_len = entry_end.checked_sub(field_name_offset)?;
+ (entry_len as usize == field_name.len()).then_some(field_id as u32)
+ }
+
/// Attempts to retrieve a dictionary entry and its field id, returning
None if the requested field
/// name is not present. The search cost is logarithmic if
[`Self::is_sorted`] and linear
/// otherwise.
@@ -401,6 +473,12 @@ impl<'m> VariantMetadata<'m> {
///
/// [invalid]: Self#Validation
pub fn get_entry(&self, field_name: &str) -> Option<(u32, &'m str)> {
+ // A field name borrowed from this dictionary's (sorted) value region
resolves without
+ // any string comparisons.
+ if let Some(field_id) = self.borrowed_field_id(field_name) {
+ return Some((field_id, self.get_impl(field_id as _)));
+ }
+
let field_id = if self.is_sorted() && self.len() > 10 {
// Binary search is faster for a not-tiny sorted metadata
dictionary
let cmp = |i| Some(self.get_impl(i).cmp(field_name));
@@ -650,6 +728,222 @@ mod tests {
assert_eq!(&metadata[1], "");
}
+ /// Builds a metadata dictionary containing `field_names`, in the order
given.
+ fn metadata_bytes_for(field_names: &[&str]) -> Vec<u8> {
+ let mut builder =
VariantBuilder::new().with_field_names(field_names.iter().copied());
+ let mut object = builder.new_object();
+ for name in field_names {
+ object.insert(name, 1i32);
+ }
+ object.finish();
+ builder.finish().0
+ }
+
+ /// Every entry of `metadata` must resolve to its own field id through the
general name search
+ /// and through an owned (non-borrowed) copy of the name. The borrowed
fast path must agree
+ /// whenever it applies, which is only for a sorted dictionary.
+ fn assert_lookups_agree(metadata: &VariantMetadata<'_>) {
+ for i in 0..metadata.len() {
+ let borrowed = metadata.get(i).unwrap();
+ let owned = borrowed.to_string();
+
+ assert_eq!(
+ metadata.borrowed_field_id(borrowed),
+ metadata.is_sorted().then_some(i as u32),
+ "borrowed lookup of {borrowed:?} (field id {i})"
+ );
+ assert_eq!(
+ metadata.get_entry(borrowed),
+ Some((i as u32, borrowed)),
+ "get_entry of borrowed {borrowed:?} (field id {i})"
+ );
+ assert_eq!(
+ metadata.get_entry(owned.as_str()),
+ Some((i as u32, borrowed)),
+ "get_entry of owned {borrowed:?} (field id {i})"
+ );
+ // An owned copy does not borrow from the dictionary, so it cannot
take the fast path.
+ assert_eq!(metadata.borrowed_field_id(owned.as_str()), None);
+ }
+ }
+
+ /// Like [`assert_lookups_agree`], but tolerates the fast path declining
an entry, as it may
+ /// for a dictionary whose offset array does not increase strictly.
+ fn assert_lookups_agree_or_decline(metadata: &VariantMetadata<'_>) {
+ for i in 0..metadata.len() {
+ let borrowed = metadata.get(i).unwrap();
+ if let Some(field_id) = metadata.borrowed_field_id(borrowed) {
+ assert_eq!(field_id, i as u32, "borrowed lookup of
{borrowed:?}");
+ }
+ assert_eq!(
+ metadata.get_entry(borrowed),
+ Some((i as u32, borrowed)),
+ "get_entry of borrowed {borrowed:?} (field id {i})"
+ );
+ }
+ }
+
+ #[test]
+ fn test_borrowed_field_id_sorted_dictionary() {
+ // More than 10 entries, so `get_entry` uses its binary search path.
+ let names: Vec<String> = (0..64).map(|i|
format!("field_{i:03}")).collect();
+ let names: Vec<&str> = names.iter().map(String::as_str).collect();
+ let bytes = metadata_bytes_for(&names);
+ let metadata = VariantMetadata::try_new(&bytes).unwrap();
+
+ assert!(metadata.is_sorted());
+ assert_eq!(metadata.len(), 64);
+ assert_lookups_agree(&metadata);
+
+ assert_eq!(metadata.get_entry("field_999"), None);
+ assert_eq!(metadata.borrowed_field_id("field_999"), None);
+ }
+
+ #[test]
+ fn test_borrowed_field_id_unsorted_dictionary() {
+ let bytes = metadata_bytes_for(&["zebra", "apple", "mango", "kiwi"]);
+ let metadata = VariantMetadata::try_new(&bytes).unwrap();
+
+ assert!(!metadata.is_sorted());
+ assert_eq!(metadata.len(), 4);
+ // An unsorted dictionary may hold duplicate entries, so the fast path
never applies to it
+ // and every name falls back to the general search.
+ assert_lookups_agree(&metadata);
+ }
+
+ /// A dictionary that is not marked sorted may legally repeat a string,
and the two field ids
+ /// naming it must not become distinguishable by where the caller's name
was borrowed from:
+ /// `ObjectBuilder` detects duplicate fields by field id, so a name must
map to a single id.
+ #[test]
+ fn test_borrowed_field_id_unsorted_dictionary_with_duplicate_entries() {
+ let bytes = &[
+ 0b0000_0001, // header: offset_size_minus_one=0, sorted=0,
version=1
+ 2, // dictionary_size
+ 0x00,
+ 0x01,
+ 0x02,
+ b'a',
+ b'a',
+ ];
+ let metadata = VariantMetadata::try_new(bytes).unwrap();
+ assert!(!metadata.is_sorted());
+ assert_eq!(metadata.get(0).unwrap(), "a");
+ assert_eq!(metadata.get(1).unwrap(), "a");
+
+ // Whichever entry a name was borrowed from, it resolves to the first
entry naming it.
+ let owned = String::from("a");
+ for name in [metadata.get(0).unwrap(), metadata.get(1).unwrap(),
&owned] {
+ assert_eq!(metadata.borrowed_field_id(name), None);
+ assert_eq!(metadata.get_entry(name), Some((0, "a")));
+ }
+ }
+
+ #[test]
+ fn test_borrowed_field_id_ignores_names_from_another_dictionary() {
+ let this_bytes = metadata_bytes_for(&["alpha", "beta", "gamma"]);
+ let this = VariantMetadata::try_new(&this_bytes).unwrap();
+
+ // A different dictionary that shares some names, with different field
ids for them.
+ let other_bytes = metadata_bytes_for(&["delta", "gamma", "beta",
"alpha"]);
+ let other = VariantMetadata::try_new(&other_bytes).unwrap();
+
+ for i in 0..other.len() {
+ let name = other.get(i).unwrap();
+ // A copy that borrows from neither dictionary, to compare results
against.
+ let unborrowed_name: String = name.chars().collect();
+ // The name borrows from `other`, so `this` must not take the fast
path for it...
+ assert_eq!(this.borrowed_field_id(name), None);
+ // ...and the general search must still return `this`'s own field
id for that name.
+ assert_eq!(this.get_entry(name), this.get_entry(&unborrowed_name));
+ }
+
+ assert_eq!(this.get_entry(other.get(3).unwrap()), Some((0, "alpha")));
+ assert_eq!(this.get_entry(other.get(0).unwrap()), None);
+ }
+
+ #[test]
+ fn test_borrowed_field_id_rejects_substring_of_an_entry() {
+ // Dictionary ["x", "yy"], stored as the bytes "xyy". A slice of entry
1 that starts one
+ // byte into the value region shares its start offset with entry 1
without being equal to
+ // it, which the fast path must detect rather than reporting a bogus
field id. The
+ // dictionary is sorted, so the fast path applies to it.
+ let bytes = &[
+ 0b0001_0001, // header: offset_size_minus_one=0, ordered=1,
version=1
+ 2, // dictionary_size
+ 0x00,
+ 0x01,
+ 0x03,
+ b'x',
+ b'y',
+ b'y',
+ ];
+ let metadata = VariantMetadata::try_new(bytes).unwrap();
+ assert!(metadata.is_sorted());
+ assert_eq!(metadata.get(0).unwrap(), "x");
+ assert_eq!(metadata.get(1).unwrap(), "yy");
+ assert_eq!(
+ metadata.borrowed_field_id(metadata.get(1).unwrap()),
+ Some(1)
+ );
+
+ let prefix_of_entry_1 = &metadata.get(1).unwrap()[..1];
+ assert_eq!(prefix_of_entry_1, "y");
+ assert_eq!(metadata.borrowed_field_id(prefix_of_entry_1), None);
+ assert_eq!(metadata.get_entry(prefix_of_entry_1), None);
+
+ // A slice that starts inside an entry, at an offset no entry starts
at, is also rejected.
+ let suffix_of_entry_1 = &metadata.get(1).unwrap()[1..];
+ assert_eq!(metadata.borrowed_field_id(suffix_of_entry_1), None);
+ }
+
+ #[test]
+ fn test_borrowed_field_id_with_empty_field_name() {
+ let bytes = &[
+ 0b0000_0001, // header: offset_size_minus_one=0, ordered=0,
version=1
+ 2, // dictionary_size
+ 0x00,
+ 0x02,
+ 0x02, // an unsorted dict may hold an empty string anywhere
+ b'h',
+ b'i',
+ ];
+ let metadata = VariantMetadata::try_new(bytes).unwrap();
+ assert!(!metadata.is_sorted());
+ assert_eq!(metadata.get(0).unwrap(), "hi");
+ assert_eq!(metadata.get(1).unwrap(), "");
+
+ assert_eq!(
+ metadata.get_entry(metadata.get(0).unwrap()),
+ Some((0, "hi"))
+ );
+ assert_eq!(metadata.get_entry(metadata.get(1).unwrap()), Some((1,
"")));
+ assert_eq!(metadata.get_entry(""), Some((1, "")));
+ assert_eq!(metadata.borrowed_field_id(metadata.get(0).unwrap()), None);
+ }
+
+ #[test]
+ fn test_borrowed_field_id_with_leading_empty_field_name() {
+ // A sorted dictionary can only hold an empty string as its first
entry, where it shares a
+ // start offset with the entry after it. The fast path is free to
decline such an
+ // ambiguous offset, but must never report the wrong field id for it.
+ let bytes = &[
+ 0b0001_0001, // header: offset_size_minus_one=0, ordered=1,
version=1
+ 2, // dictionary_size
+ 0x00,
+ 0x00,
+ 0x02,
+ b'h',
+ b'i',
+ ];
+ let metadata = VariantMetadata::try_new(bytes).unwrap();
+ assert!(metadata.is_sorted());
+ assert_eq!(metadata.get(0).unwrap(), "");
+ assert_eq!(metadata.get(1).unwrap(), "hi");
+
+ assert_lookups_agree_or_decline(&metadata);
+ assert_eq!(metadata.get_entry(""), Some((0, "")));
+ }
+
#[test]
fn test_compare_sorted_dictionary_with_unsorted_dictionary() {
// create a sorted object
