This is an automated email from the ASF dual-hosted git repository.
Jefffrey 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 b36dc72685 Add `proptest` fuzzing to parquet-variant and implement
fixes for findings (#10352)
b36dc72685 is described below
commit b36dc726850245160485e0f04247e838cdb0ab87
Author: Peter L <[email protected]>
AuthorDate: Wed Aug 26 15:51:16 2026 +0930
Add `proptest` fuzzing to parquet-variant and implement fixes for findings
(#10352)
# Which issue does this PR close?
This PR is not tied to a single pre-existing issue; it fixes findings
1-6 in the table below,
all found while adding the `proptest` harness. The two remaining
findings are out of scope here
and are tracked as follow-up issues:
- #10359 - `shred_variant` panics on an object with duplicate field
names (finding 7)
- #10360 - `PartialEq` on unvalidated deeply-nested variants overflows
the stack (finding 8)
Here's a list of bugs found:
| # | Defect | Location | Effect | Status |
|---|--------|----------|--------|--------|
| 1 | Unsorted dictionary with an empty field name is rejected |
`metadata.rs:317` | Rejects **valid** data | Fixed |
| 2 | Unsorted dictionary offsets not checked for UTF-8 character
boundaries | `metadata.rs` (same branch) | Validated, then **panics** on
index/iter | Fixed |
| 3 | Duplicate field names in an object are accepted | `object.rs:270`
| Accepts **invalid** data | Fixed |
| 4 | `decode_date` overflows on large day counts | `decoder.rs:281` |
**Panics** inside `try_new` | Fixed |
| 5 | `decode_uuid` indexes raw on a truncated payload |
`decoder.rs:347` | **Panics** inside `try_new` | Fixed |
| 6 | Validation recurses without a depth limit | `list.rs:234`,
`object.rs` | **Process abort** | Fixed |
| 7 | `shred_variant` double-appends on duplicate field names |
`shred_variant.rs:418-429` | **Panics** in arrow-array | Open (#10359) |
| 8 | `PartialEq` recurses without bound on shallow variants |
`list.rs:313`, `object.rs` | **Process abort** | Open (#10360) |
# Rationale for this change
This PR was raised after some bugs caught in production caused some
failing jobs.
The original bug was empty field strings caused a weird `offsets not
monotonically increasing`, but with the assistance of an agent, we
expanded our search to use `proptest` to find some other similar cases.
# What changes are included in this PR?
Adds a new `proptest` harness for `parquet-variant` and fixes
# Are these changes tested?
Yes, most of these changes are driven by failing proptests and converted
into smaller unit tests.
# Are there any user-facing changes?
The only one that is probably worth mentioning, and maybe something we
allow to be configured, is a max depth recursion constant was added.
---------
Co-authored-by: Claude Opus 5 (1M context) <[email protected]>
---
Cargo.lock | 107 ++++++++++++---
parquet-variant/Cargo.toml | 1 +
parquet-variant/src/decoder.rs | 40 ++++--
parquet-variant/src/variant.rs | 36 ++++-
parquet-variant/src/variant/list.rs | 56 +++++++-
parquet-variant/src/variant/metadata.rs | 58 ++++++--
parquet-variant/src/variant/object.rs | 98 ++++++++++++-
parquet-variant/tests/proptest.rs | 234 ++++++++++++++++++++++++++++++++
8 files changed, 576 insertions(+), 54 deletions(-)
diff --git a/Cargo.lock b/Cargo.lock
index d2d412b239..0812500ec0 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -146,7 +146,7 @@ dependencies = [
"num-bigint 0.4.8",
"ouroboros",
"quad-rand",
- "rand",
+ "rand 0.10.2",
"regex-lite",
"serde",
"serde_bytes",
@@ -197,7 +197,7 @@ dependencies = [
"criterion",
"half",
"memmap2",
- "rand",
+ "rand 0.10.2",
"serde",
]
@@ -232,7 +232,7 @@ dependencies = [
"num-complex",
"num-integer",
"num-traits",
- "rand",
+ "rand 0.10.2",
]
[[package]]
@@ -259,7 +259,7 @@ dependencies = [
"md5",
"object_store",
"once_cell",
- "rand",
+ "rand 0.10.2",
"serde",
"serde_json",
"sha2",
@@ -280,7 +280,7 @@ dependencies = [
"half",
"num-bigint 0.5.1",
"num-traits",
- "rand",
+ "rand 0.10.2",
]
[[package]]
@@ -302,7 +302,7 @@ dependencies = [
"insta",
"lexical-core",
"num-traits",
- "rand",
+ "rand 0.10.2",
"ryu",
]
@@ -459,7 +459,7 @@ dependencies = [
"lexical-core",
"memchr",
"num-traits",
- "rand",
+ "rand 0.10.2",
"ryu",
"serde",
"serde_core",
@@ -479,7 +479,7 @@ dependencies = [
"arrow-schema",
"arrow-select",
"half",
- "rand",
+ "rand 0.10.2",
]
[[package]]
@@ -504,7 +504,7 @@ dependencies = [
"arrow-schema",
"arrow-select",
"half",
- "rand",
+ "rand 0.10.2",
]
[[package]]
@@ -531,7 +531,7 @@ dependencies = [
"arrow-data",
"arrow-schema",
"num-traits",
- "rand",
+ "rand 0.10.2",
]
[[package]]
@@ -847,7 +847,7 @@ checksum =
"d524456ba66e72eb8b115ff89e01e497f8e6d11d78b70b1aa13c0fbd97540a81"
dependencies = [
"cfg-if",
"cpufeatures",
- "rand_core",
+ "rand_core 0.10.1",
]
[[package]]
@@ -1478,7 +1478,7 @@ dependencies = [
"js-sys",
"libc",
"r-efi 6.0.0",
- "rand_core",
+ "rand_core 0.10.1",
"wasm-bindgen",
]
@@ -2315,7 +2315,7 @@ dependencies = [
"parking_lot",
"percent-encoding",
"quick-xml",
- "rand",
+ "rand 0.10.2",
"reqwest",
"rustls-pki-types",
"serde",
@@ -2446,7 +2446,7 @@ dependencies = [
"parquet-geospatial",
"parquet-variant",
"parquet-variant-compute",
- "rand",
+ "rand 0.10.2",
"ring",
"seq-macro",
"serde",
@@ -2481,7 +2481,8 @@ dependencies = [
"criterion",
"half",
"indexmap",
- "rand",
+ "proptest",
+ "rand 0.10.2",
"simdutf8",
"uuid",
]
@@ -2499,7 +2500,7 @@ dependencies = [
"num-traits",
"parquet-variant",
"parquet-variant-json",
- "rand",
+ "rand 0.10.2",
"serde_json",
"uuid",
]
@@ -2630,6 +2631,15 @@ dependencies = [
"zerovec",
]
+[[package]]
+name = "ppv-lite86"
+version = "0.2.21"
+source = "registry+https://github.com/rust-lang/crates.io-index";
+checksum = "85eae3c4ed2f50dcfe72643da4befc30deadb458a9b590d720cde2f2b1e97da9"
+dependencies = [
+ "zerocopy",
+]
+
[[package]]
name = "predicates"
version = "3.1.4"
@@ -2698,6 +2708,21 @@ dependencies = [
"yansi",
]
+[[package]]
+name = "proptest"
+version = "1.11.0"
+source = "registry+https://github.com/rust-lang/crates.io-index";
+checksum = "4b45fcc2344c680f5025fe57779faef368840d0bd1f42f216291f0dc4ace4744"
+dependencies = [
+ "bitflags",
+ "num-traits",
+ "rand 0.9.5",
+ "rand_chacha",
+ "rand_xorshift",
+ "regex-syntax",
+ "unarray",
+]
+
[[package]]
name = "prost"
version = "0.14.4"
@@ -2852,7 +2877,7 @@ dependencies = [
"bytes",
"getrandom 0.4.3",
"lru-slab",
- "rand",
+ "rand 0.10.2",
"rand_pcg",
"ring",
"rustc-hash",
@@ -2900,6 +2925,16 @@ version = "6.0.0"
source = "registry+https://github.com/rust-lang/crates.io-index";
checksum = "f8dcc9c7d52a811697d2151c701e0d08956f92b0e24136cf4cf27b57a6a0d9bf"
+[[package]]
+name = "rand"
+version = "0.9.5"
+source = "registry+https://github.com/rust-lang/crates.io-index";
+checksum = "b9ef1d0d795eb7d84685bca4f72f3649f064e6641543d3a8c415898726a57b41"
+dependencies = [
+ "rand_chacha",
+ "rand_core 0.9.5",
+]
+
[[package]]
name = "rand"
version = "0.10.2"
@@ -2908,7 +2943,26 @@ checksum =
"c7f5fa3a058cd35567ef9bfa5e75732bee0f9e4c55fa90477bef2dfcdbc4be80"
dependencies = [
"chacha20",
"getrandom 0.4.3",
- "rand_core",
+ "rand_core 0.10.1",
+]
+
+[[package]]
+name = "rand_chacha"
+version = "0.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index";
+checksum = "d3022b5f1df60f26e1ffddd6c66e8aa15de382ae63b3a0c1bfc0e4d3e3f325cb"
+dependencies = [
+ "ppv-lite86",
+ "rand_core 0.9.5",
+]
+
+[[package]]
+name = "rand_core"
+version = "0.9.5"
+source = "registry+https://github.com/rust-lang/crates.io-index";
+checksum = "76afc826de14238e6e8c374ddcc1fa19e374fd8dd986b0d2af0d02377261d83c"
+dependencies = [
+ "getrandom 0.3.4",
]
[[package]]
@@ -2923,7 +2977,16 @@ version = "0.10.2"
source = "registry+https://github.com/rust-lang/crates.io-index";
checksum = "caa0f4137e1c0a72f4c651489402276c8e8e1cf081f3b0ba156d2cbeef09e86a"
dependencies = [
- "rand_core",
+ "rand_core 0.10.1",
+]
+
+[[package]]
+name = "rand_xorshift"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index";
+checksum = "513962919efc330f829edb2535844d1b912b0fbe2ca165d613e4e8788bb05a5a"
+dependencies = [
+ "rand_core 0.9.5",
]
[[package]]
@@ -3871,6 +3934,12 @@ version = "1.20.1"
source = "registry+https://github.com/rust-lang/crates.io-index";
checksum = "b6f5e870be6c3b371b77fe0ee0bafb859fa4964b4404c27de1d380043c4dda20"
+[[package]]
+name = "unarray"
+version = "0.1.4"
+source = "registry+https://github.com/rust-lang/crates.io-index";
+checksum = "eaea85b334db583fe3274d12b4cd1880032beab409c0d774be044d4480ab9a94"
+
[[package]]
name = "unicode-ident"
version = "1.0.24"
diff --git a/parquet-variant/Cargo.toml b/parquet-variant/Cargo.toml
index 645f5be486..df1aabd03e 100644
--- a/parquet-variant/Cargo.toml
+++ b/parquet-variant/Cargo.toml
@@ -45,6 +45,7 @@ name = "parquet_variant"
bench = false
[dev-dependencies]
+proptest = { version = "1.0", default-features = false, features = ["std"] }
criterion = { workspace = true, default-features = false }
rand = { version = "0.10", default-features = false, features = [
"std",
diff --git a/parquet-variant/src/decoder.rs b/parquet-variant/src/decoder.rs
index ce7c09a36c..dd226c5eec 100644
--- a/parquet-variant/src/decoder.rs
+++ b/parquet-variant/src/decoder.rs
@@ -278,8 +278,14 @@ pub(crate) fn decode_double(data: &[u8]) -> Result<f64,
ArrowError> {
/// Decodes a Date from the value section of a variant.
pub(crate) fn decode_date(data: &[u8]) -> Result<NaiveDate, ArrowError> {
let days_since_epoch = i32::from_le_bytes(array_from_slice(data, 0)?);
- let value = DateTime::UNIX_EPOCH +
Duration::days(i64::from(days_since_epoch));
- Ok(value.date_naive())
+ DateTime::UNIX_EPOCH
+ .checked_add_signed(Duration::days(i64::from(days_since_epoch)))
+ .map(|value| value.date_naive())
+ .ok_or_else(|| {
+ ArrowError::CastError(format!(
+ "Could not cast `{days_since_epoch}` days into a NaiveDate"
+ ))
+ })
}
/// Decodes a TimestampMicros from the value section of a variant.
@@ -338,8 +344,8 @@ pub(crate) fn decode_timestampntz_nanos(data: &[u8]) ->
Result<NaiveDateTime, Ar
/// Decodes a UUID from the value section of a variant.
pub(crate) fn decode_uuid(data: &[u8]) -> Result<Uuid, ArrowError> {
- Uuid::from_slice(&data[0..16])
- .map_err(|_| ArrowError::CastError(format!("Cant decode uuid from
{:?}", &data[0..16])))
+ let bytes: [u8; 16] = array_from_slice(data, 0)?;
+ Ok(Uuid::from_bytes(bytes))
}
/// Decodes a Binary from the value section of a variant.
@@ -467,6 +473,15 @@ mod tests {
NaiveDate::from_ymd_opt(2025, 4, 16).unwrap()
);
+ #[test]
+ fn test_date_out_of_range() {
+ // A day count that overflows chrono's supported date range must
error, not panic
+ for days in [i32::MAX, i32::MIN] {
+ let result = decode_date(&days.to_le_bytes());
+ assert!(matches!(result, Err(ArrowError::CastError(_))));
+ }
+ }
+
test_decoder_bounds!(
test_timestamp_micros,
[0xe0, 0x52, 0x97, 0xdd, 0xe7, 0x32, 0x06, 0x00],
@@ -531,18 +546,15 @@ mod tests {
);
}
- #[test]
- fn test_uuid() {
- let data = [
+ test_decoder_bounds!(
+ test_uuid,
+ [
0xf2, 0x4f, 0x9b, 0x64, 0x81, 0xfa, 0x49, 0xd1, 0xb7, 0x4e, 0x8c,
0x09, 0xa6, 0xe3,
0x1c, 0x56,
- ];
- let result = decode_uuid(&data).unwrap();
- assert_eq!(
- Uuid::parse_str("f24f9b64-81fa-49d1-b74e-8c09a6e31c56").unwrap(),
- result
- );
- }
+ ],
+ decode_uuid,
+ Uuid::parse_str("f24f9b64-81fa-49d1-b74e-8c09a6e31c56").unwrap()
+ );
mod time {
use super::*;
diff --git a/parquet-variant/src/variant.rs b/parquet-variant/src/variant.rs
index 7a9e326903..f8da6b1537 100644
--- a/parquet-variant/src/variant.rs
+++ b/parquet-variant/src/variant.rs
@@ -41,6 +41,19 @@ mod object;
const MAX_SHORT_STRING_BYTES: usize = 0x3F;
+/// The maximum number of nested objects and arrays a [`Variant`] may contain.
+///
+/// Full [validation] recurses into nested values, so unbounded nesting would
overflow the stack --
+/// an abort, not a catchable panic. Validation therefore rejects more deeply
nested values, which
+/// also bounds the recursion of infallible accesses such as [`Debug`] and
[`PartialEq`].
+///
+/// The variant [spec] does not specify a limit. This value matches the
default `serde_json`
+/// recursion limit, so any variant parsed from JSON already satisfies it.
+///
+/// [validation]: Variant#Validation
+/// [spec]:
https://github.com/apache/parquet-format/blob/master/VariantEncoding.md
+pub const MAX_NESTING_DEPTH: usize = 128;
+
/// A Variant [`ShortString`]
///
/// This implementation is a zero cost wrapper over `&str` that ensures
@@ -352,7 +365,17 @@ impl<'m, 'v> Variant<'m, 'v> {
metadata: VariantMetadata<'m>,
value: &'v [u8],
) -> Result<Self, ArrowError> {
- Self::try_new_with_metadata_and_shallow_validation(metadata,
value)?.with_full_validation()
+ Self::try_new_with_metadata_at_depth(metadata, value, 0)
+ }
+
+ // Same as [`Self::try_new_with_metadata`], tracking how deeply validation
has recursed.
+ pub(crate) fn try_new_with_metadata_at_depth(
+ metadata: VariantMetadata<'m>,
+ value: &'v [u8],
+ depth: usize,
+ ) -> Result<Self, ArrowError> {
+ Self::try_new_with_metadata_and_shallow_validation(metadata, value)?
+ .with_full_validation_at_depth(depth)
}
/// Similar to [`Self::try_new_with_metadata`], but [unvalidated].
@@ -455,13 +478,20 @@ impl<'m, 'v> Variant<'m, 'v> {
/// If [`Self::is_fully_validated`] is true, validation is a no-op.
Otherwise, the cost is `O(m + v)`
/// where `m` and `v` are the sizes of metadata and value buffers,
respectively.
///
+ /// Values nested more than [`MAX_NESTING_DEPTH`] deep are rejected.
+ ///
/// [objects]: VariantObject#Validation
/// [arrays]: VariantList#Validation
pub fn with_full_validation(self) -> Result<Self, ArrowError> {
+ self.with_full_validation_at_depth(0)
+ }
+
+ // Same as [`Self::with_full_validation`], tracking how deeply validation
has recursed.
+ pub(crate) fn with_full_validation_at_depth(self, depth: usize) ->
Result<Self, ArrowError> {
use Variant::*;
match self {
- List(list) => list.with_full_validation().map(List),
- Object(obj) => obj.with_full_validation().map(Object),
+ List(list) => list.with_full_validation_at_depth(depth).map(List),
+ Object(obj) =>
obj.with_full_validation_at_depth(depth).map(Object),
_ => Ok(self),
}
}
diff --git a/parquet-variant/src/variant/list.rs
b/parquet-variant/src/variant/list.rs
index b9d726565a..4066d5c10d 100644
--- a/parquet-variant/src/variant/list.rs
+++ b/parquet-variant/src/variant/list.rs
@@ -18,7 +18,7 @@ use crate::decoder::{OffsetSizeBytes, map_bytes_to_offsets};
use crate::utils::{
first_byte_from_slice, overflow_error, slice_from_slice,
slice_from_slice_at_offset,
};
-use crate::variant::{Variant, VariantMetadata};
+use crate::variant::{MAX_NESTING_DEPTH, Variant, VariantMetadata};
use arrow_schema::ArrowError;
@@ -216,9 +216,25 @@ impl<'m, 'v> VariantList<'m, 'v> {
/// Performs a full [validation] of this variant array and returns the
result.
///
+ /// Values nested more than [`MAX_NESTING_DEPTH`] deep are rejected.
+ ///
/// [validation]: Self#Validation
- pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
+ pub fn with_full_validation(self) -> Result<Self, ArrowError> {
+ self.with_full_validation_at_depth(0)
+ }
+
+ // Same as [`Self::with_full_validation`], tracking how deeply validation
has recursed.
+ pub(crate) fn with_full_validation_at_depth(
+ mut self,
+ depth: usize,
+ ) -> Result<Self, ArrowError> {
if !self.validated {
+ if depth >= MAX_NESTING_DEPTH {
+ return Err(ArrowError::InvalidArgumentError(format!(
+ "Variant nesting depth exceeds the maximum of
{MAX_NESTING_DEPTH}"
+ )));
+ }
+
// Validate the metadata dictionary first, if not already
validated, because we pass it
// by value to all the children (who would otherwise re-validate
it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
@@ -239,7 +255,11 @@ impl<'m, 'v> VariantList<'m, 'v> {
for next_offset in offset_iter {
let value_bytes = slice_from_slice(value_buffer,
current_offset..next_offset)?;
- Variant::try_new_with_metadata(self.metadata.clone(),
value_bytes)?;
+ Variant::try_new_with_metadata_at_depth(
+ self.metadata.clone(),
+ value_bytes,
+ depth + 1,
+ )?;
current_offset = next_offset;
}
@@ -744,6 +764,36 @@ mod tests {
assert_ne!(object.get("list1").unwrap(), object.get("list3").unwrap());
}
+ /// return the value bytes for `depth` single-element lists nested around
a null
+ fn make_nested_lists(depth: usize) -> Vec<u8> {
+ let mut value = vec![0u8]; // null primitive
+ for _ in 0..depth {
+ // header: array basic type, 4-byte offsets, then num_elements=1
and two offsets
+ let mut outer = vec![0x0F, 1];
+ outer.extend_from_slice(&0u32.to_le_bytes());
+ outer.extend_from_slice(&(value.len() as u32).to_le_bytes());
+ outer.append(&mut value);
+ value = outer;
+ }
+ value
+ }
+
+ #[test]
+ fn test_variant_list_nesting_depth_limit() {
+ let metadata = [0x01, 0, 0]; // empty dictionary
+
+ let value = make_nested_lists(MAX_NESTING_DEPTH);
+ Variant::try_new(&metadata, &value).unwrap();
+
+ // One level deeper would recurse past the limit -- previously a stack
overflow
+ let value = make_nested_lists(MAX_NESTING_DEPTH + 1);
+ let err = Variant::try_new(&metadata, &value).unwrap_err();
+ assert!(
+ err.to_string().contains("nesting depth exceeds"),
+ "unexpected error: {err}"
+ );
+ }
+
/// return metadata/value for a simple variant list with values in a range
fn make_listi32(range: Range<i32>) -> (Vec<u8>, Vec<u8>) {
let mut variant_builder = VariantBuilder::new();
diff --git a/parquet-variant/src/variant/metadata.rs
b/parquet-variant/src/variant/metadata.rs
index b48c50451b..bb571afbfa 100644
--- a/parquet-variant/src/variant/metadata.rs
+++ b/parquet-variant/src/variant/metadata.rs
@@ -115,7 +115,7 @@ impl VariantMetadataHeader {
/// - first offset is zero
/// - last offset is in-bounds
/// - all other offsets are in-bounds (*)
-/// - all offsets are monotonically increasing (*)
+/// - all offsets are non-decreasing (*)
/// - all values are valid utf-8 (*)
///
/// NOTE: [`Self::new`] only skips expensive (non-constant cost) validation
checks (marked by `(*)`
@@ -284,13 +284,13 @@ impl<'m> VariantMetadata<'m> {
string_from_slice(self.bytes, 0, self.first_value_byte as
_..self.bytes.len())?;
let mut offsets = map_bytes_to_offsets(offset_bytes,
self.header.offset_size);
+ let mut current_offset = offsets.next().unwrap_or(0);
if self.header.is_sorted {
// Validate the dictionary values are unique and
lexicographically sorted
//
// Since we use the offsets to access dictionary values, this
also validates
// offsets are in-bounds and monotonically increasing
- let mut current_offset = offsets.next().unwrap_or(0);
let mut prev_value: Option<&str> = None;
for next_offset in offsets {
let current_value =
value_buffer.get(current_offset..next_offset).ok_or_else(
@@ -313,15 +313,18 @@ impl<'m> VariantMetadata<'m> {
current_offset = next_offset;
}
} else {
- // Validate offsets are in-bounds and monotonically increasing
- //
- // Since shallow validation ensures the first and last offsets
are in bounds,
- // we can also verify all offsets are in-bounds by checking if
- // offsets are monotonically increasing
- if !offsets.is_sorted_by(|a, b| a < b) {
- return Err(ArrowError::InvalidArgumentError(
- "offsets not monotonically increasing".to_string(),
- ));
+ // Slicing each dictionary value validates that offsets are
in-bounds, non-decreasing,
+ // and land on UTF-8 character boundaries. Equal offsets are
legal: they encode an
+ // empty dictionary entry.
+ for next_offset in offsets {
+ value_buffer
+ .get(current_offset..next_offset)
+ .ok_or_else(|| {
+ ArrowError::InvalidArgumentError(format!(
+ "range {current_offset}..{next_offset} is
invalid or out of bounds"
+ ))
+ })?;
+ current_offset = next_offset;
}
}
@@ -619,6 +622,19 @@ mod tests {
matches!(err, ArrowError::InvalidArgumentError(_)),
"unexpected error: {err:?}"
);
+
+ let bytes = &[
+ 0b0000_0001, // header: offset_size_minus_one=0, ordered=0,
version=1
+ 2,
+ 0x00,
+ 0x02,
+ 0x02, // an unsorted dict may hold an empty string anywhere
+ b'h',
+ b'i',
+ ];
+ let metadata = VariantMetadata::try_new(bytes).unwrap();
+ assert_eq!(&metadata[0], "hi");
+ assert_eq!(&metadata[1], "");
}
#[test]
@@ -674,4 +690,24 @@ mod tests {
assert_eq!(m1, m2);
}
+
+ #[test]
+ fn test_empty_string_field_names() {
+ // Field names are added to the dictionary in insertion order, so this
dictionary is
+ // unsorted, and the empty field name makes its last two offsets equal.
+ let mut b = VariantBuilder::new().with_field_names(["b", "a", ""]);
+ let mut o = b.new_object();
+
+ o.insert("b", false);
+ o.insert("a", false);
+ o.insert("", false);
+
+ o.finish();
+
+ let (m, _) = b.finish();
+
+ let metadata = VariantMetadata::try_new(&m).unwrap();
+ assert!(!metadata.is_sorted());
+ assert_eq!(metadata.iter().collect::<Vec<_>>(), vec!["b", "a", ""]);
+ }
}
diff --git a/parquet-variant/src/variant/object.rs
b/parquet-variant/src/variant/object.rs
index 956eeea34c..221eb8f1b3 100644
--- a/parquet-variant/src/variant/object.rs
+++ b/parquet-variant/src/variant/object.rs
@@ -19,7 +19,7 @@ use crate::decoder::{OffsetSizeBytes, map_bytes_to_offsets};
use crate::utils::{
first_byte_from_slice, overflow_error, slice_from_slice,
try_binary_search_range_by,
};
-use crate::variant::{Variant, VariantMetadata};
+use crate::variant::{MAX_NESTING_DEPTH, Variant, VariantMetadata};
use arrow_schema::ArrowError;
@@ -101,6 +101,7 @@ impl VariantObjectHeader {
/// - field value array is in bounds
/// - all field ids are valid metadata dictionary entries (*)
/// - field ids are lexically ordered according by their corresponding string
values (*)
+/// - field names are unique; no field name appears more than once (*)
/// - all field offsets are in bounds (*)
/// - all field values are (recursively) _valid_ variant values (*)
/// - the associated variant metadata is [valid] (*)
@@ -218,9 +219,25 @@ impl<'m, 'v> VariantObject<'m, 'v> {
/// Performs a full [validation] of this variant object.
///
+ /// Values nested more than [`MAX_NESTING_DEPTH`] deep are rejected.
+ ///
/// [validation]: Self#Validation
- pub fn with_full_validation(mut self) -> Result<Self, ArrowError> {
+ pub fn with_full_validation(self) -> Result<Self, ArrowError> {
+ self.with_full_validation_at_depth(0)
+ }
+
+ // Same as [`Self::with_full_validation`], tracking how deeply validation
has recursed.
+ pub(crate) fn with_full_validation_at_depth(
+ mut self,
+ depth: usize,
+ ) -> Result<Self, ArrowError> {
if !self.validated {
+ if depth >= MAX_NESTING_DEPTH {
+ return Err(ArrowError::InvalidArgumentError(format!(
+ "Variant nesting depth exceeds the maximum of
{MAX_NESTING_DEPTH}"
+ )));
+ }
+
// Validate the metadata dictionary first, if not already
validated, because we pass it
// by value to all the children (who would otherwise re-validate
it repeatedly).
self.metadata = self.metadata.with_full_validation()?;
@@ -274,8 +291,10 @@ impl<'m, 'v> VariantObject<'m, 'v> {
for field_id in field_ids_iter {
let next_field_name = self.metadata.get(field_id)?;
+ // Equal names are rejected as well: field names must be
unique within an
+ // object. The sorted branch above enforces this via
strictly ordered ids.
if let Some(current_name) = current_field_name
- && next_field_name < current_name
+ && next_field_name <= current_name
{
return Err(ArrowError::InvalidArgumentError(
"field names not sorted".to_string(),
@@ -298,7 +317,11 @@ impl<'m, 'v> VariantObject<'m, 'v> {
.take(num_offsets.saturating_sub(1))
.try_for_each(|offset| {
let value_bytes = slice_from_slice(value_buffer,
offset..)?;
- Variant::try_new_with_metadata(self.metadata.clone(),
value_bytes)?;
+ Variant::try_new_with_metadata_at_depth(
+ self.metadata.clone(),
+ value_bytes,
+ depth + 1,
+ )?;
Ok::<_, ArrowError>(())
})?;
@@ -1006,4 +1029,71 @@ mod tests {
let v2 = Variant::new_with_metadata(m, &v);
assert_eq!(v1, v2);
}
+
+ #[test]
+ fn test_object_rejects_duplicate_field_names() {
+ // An unsorted dictionary may legally hold duplicate entries, but an
object must not
+ // reference the same field name twice.
+ let metadata_bytes = vec![
+ 0b0000_0001,
+ 2, // dictionary size
+ 0, // "a"
+ 1, // "a"
+ 2,
+ b'a',
+ b'a',
+ ];
+ assert!(
+ !VariantMetadata::try_new(&metadata_bytes)
+ .unwrap()
+ .is_sorted()
+ );
+
+ let value_bytes = vec![
+ 0b0000_0010, // object header
+ 2, // num_elements
+ 0, // field id 0 -> "a"
+ 1, // field id 1 -> "a"
+ 0,
+ 1,
+ 2, // field offsets
+ 0b0000_1100, // true
+ 0b0000_1000, // false
+ ];
+ let err = Variant::try_new(&metadata_bytes, &value_bytes).unwrap_err();
+ assert!(
+ matches!(err, ArrowError::InvalidArgumentError(_)),
+ "unexpected error: {err:?}"
+ );
+ }
+
+ /// return the value bytes for `depth` single-field objects nested around
a null
+ fn make_nested_objects(depth: usize) -> Vec<u8> {
+ let mut value = vec![0u8]; // null primitive
+ for _ in 0..depth {
+ // header: object basic type, 1-byte field ids, 4-byte field
offsets
+ let mut outer = vec![0b0000_1110, 1, 0];
+ outer.extend_from_slice(&0u32.to_le_bytes());
+ outer.extend_from_slice(&(value.len() as u32).to_le_bytes());
+ outer.append(&mut value);
+ value = outer;
+ }
+ value
+ }
+
+ #[test]
+ fn test_variant_object_nesting_depth_limit() {
+ let metadata = [0b0000_0001, 1, 0, 1, b'a']; // dictionary of one
field name
+
+ let value = make_nested_objects(MAX_NESTING_DEPTH);
+ Variant::try_new(&metadata, &value).unwrap();
+
+ // One level deeper would recurse past the limit -- previously a stack
overflow
+ let value = make_nested_objects(MAX_NESTING_DEPTH + 1);
+ let err = Variant::try_new(&metadata, &value).unwrap_err();
+ assert!(
+ err.to_string().contains("nesting depth exceeds"),
+ "unexpected error: {err}"
+ );
+ }
}
diff --git a/parquet-variant/tests/proptest.rs
b/parquet-variant/tests/proptest.rs
new file mode 100644
index 0000000000..8c7f7a968f
--- /dev/null
+++ b/parquet-variant/tests/proptest.rs
@@ -0,0 +1,234 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! Property tests for variant decoding and validation.
+//!
+//! Two families of invariant are checked here:
+//!
+//! 1. **Untrusted input.** [`Variant::try_new`] and
[`VariantMetadata::try_new`] are fallible APIs
+//! over bytes read from a file. They must return `Err` on malformed input
rather than panic, and
+//! anything they accept must then be panic-free to access, as
[`VariantMetadata`] documents.
+//! 2. **Writer/reader agreement.** Anything [`VariantBuilder`] emits must
validate and read back
+//! unchanged, whatever order the dictionary happens to be in.
+//!
+//! The generators deliberately produce degenerate shapes: empty field names,
multi-byte UTF-8, and
+//! interior NULs. This matters more than the properties themselves --
narrowing `arb_key` to
+//! `[a-z]+` makes these tests pass against code with known bugs.
+//!
+//! Objects are generated structurally rather than as random bytes: random
bytes are rejected by
+//! header and offset validation long before reaching the object logic, so
they never exercise it.
+
+use parquet_variant::{EMPTY_VARIANT_METADATA_BYTES, Variant, VariantBuilder,
VariantMetadata};
+use proptest::prelude::*;
+use std::collections::HashSet;
+
+/// Field names covering the shapes that distinguish correct validation from
incorrect: an empty
+/// name (encoded as two equal dictionary offsets), and multi-byte characters
(whose interior bytes
+/// are not valid split points).
+fn arb_key() -> impl Strategy<Value = String> {
+ prop_oneof![
+ Just(String::new()),
+ "[a-c]{1,3}",
+ Just("é".to_string()),
+ Just("€".to_string()),
+ Just("𝄞".to_string()),
+ Just("a\u{0}b".to_string()),
+ ]
+}
+
+/// Distinct field names, in generated order. `Vec::dedup` only drops
*consecutive* duplicates.
+fn arb_field_names(len: std::ops::Range<usize>) -> impl Strategy<Value =
Vec<String>> {
+ prop::collection::vec(arb_key(), len).prop_map(|mut names| {
+ let mut seen = HashSet::new();
+ names.retain(|n| seen.insert(n.clone()));
+ names
+ })
+}
+
+/// Builds an object from `names`, seeding the dictionary in
`dictionary_order` so that both the
+/// sorted and unsorted validation paths can be reached for the same logical
value.
+fn build_object(names: &[String], dictionary_order: &[&str]) -> (Vec<u8>,
Vec<u8>) {
+ let mut builder =
VariantBuilder::new().with_field_names(dictionary_order.iter().copied());
+ let mut obj = builder.new_object();
+ for (i, name) in names.iter().enumerate() {
+ obj.insert(name.as_str(), i as i32);
+ }
+ obj.finish();
+ builder.finish()
+}
+
+/// Forces every infallible accessor that a validated instance promises is
panic-free.
+fn traverse(variant: &Variant) {
+ match variant {
+ Variant::Object(o) => o.iter().for_each(|(_, child)| traverse(&child)),
+ Variant::List(l) => l.iter().for_each(|child| traverse(&child)),
+ other => {
+ let _ = format!("{other:?}");
+ }
+ }
+}
+
+proptest! {
+ // The byte-level properties below explore a large space in which the
interesting shapes are
+ // rare, so they need far more than proptest's default 256 cases: at the
default, neither the
+ // Date overflow nor the UTF-8 boundary bug this file was written to catch
is found.
+ #![proptest_config(ProptestConfig::with_cases(20_000))]
+
+ /// Whatever the builder writes, validation must accept.
+ #[test]
+ fn builder_output_validates(names in arb_field_names(0..6)) {
+ let order: Vec<&str> = names.iter().map(|s| s.as_str()).collect();
+ let (metadata, value) = build_object(&names, &order);
+ prop_assert!(
+ VariantMetadata::try_new(&metadata).is_ok(),
+ "builder emitted metadata that fails validation: {metadata:?}"
+ );
+ prop_assert!(Variant::try_new(&metadata, &value).is_ok());
+ }
+
+ /// Dictionary ordering is an encoding detail. The same logical object
must validate, and read
+ /// back, identically whether its dictionary happens to be sorted or not.
+ #[test]
+ fn dictionary_order_does_not_change_behavior(names in
arb_field_names(2..6)) {
+ prop_assume!(names.len() > 1);
+
+ let mut ascending: Vec<&str> = names.iter().map(|s|
s.as_str()).collect();
+ ascending.sort_unstable();
+ let descending: Vec<&str> = ascending.iter().rev().copied().collect();
+
+ let (m1, v1) = build_object(&names, &ascending);
+ let (m2, v2) = build_object(&names, &descending);
+
+ let sorted = Variant::try_new(&m1, &v1);
+ let unsorted = Variant::try_new(&m2, &v2);
+ prop_assert_eq!(
+ sorted.is_ok(),
+ unsorted.is_ok(),
+ "dictionary order changed validity for {:?}: {:?}",
+ names,
+ unsorted.err()
+ );
+
+ if let (Ok(a), Ok(b)) = (sorted, unsorted) {
+ let (a, b) = (a.as_object().unwrap(), b.as_object().unwrap());
+ for name in &names {
+ prop_assert_eq!(
+ format!("{:?}", a.get(name.as_str())),
+ format!("{:?}", b.get(name.as_str()))
+ );
+ }
+ }
+ }
+
+ /// Every inserted field reads back with the value it was given.
+ #[test]
+ fn object_fields_round_trip(names in arb_field_names(0..6)) {
+ let order: Vec<&str> = names.iter().map(|s| s.as_str()).collect();
+ let (metadata, value) = build_object(&names, &order);
+ let variant = Variant::try_new(&metadata, &value).unwrap();
+ let obj = variant.as_object().unwrap();
+ prop_assert_eq!(obj.len(), names.len());
+ for (i, name) in names.iter().enumerate() {
+ prop_assert_eq!(
+ format!("{:?}", obj.get(name.as_str())),
+ format!("{:?}", Some(Variant::from(i as i32)))
+ );
+ }
+ }
+
+ /// Every primitive type id, against arbitrary payloads of arbitrary
length.
+ #[test]
+ fn primitive_decoding_never_panics(
+ type_id in 0u8..=20,
+ payload in prop::collection::vec(any::<u8>(), 0..24),
+ ) {
+ let mut value = vec![type_id << 2];
+ value.extend_from_slice(&payload);
+ let _ = Variant::try_new(EMPTY_VARIANT_METADATA_BYTES,
&value).as_ref().map(traverse);
+ }
+
+ /// Arbitrary header byte and payload, covering short strings, objects and
lists.
+ #[test]
+ fn arbitrary_value_never_panics(value in
prop::collection::vec(any::<u8>(), 1..32)) {
+ let _ = Variant::try_new(EMPTY_VARIANT_METADATA_BYTES,
&value).as_ref().map(traverse);
+ }
+
+ /// Arbitrary metadata paired with arbitrary value, as both arrive from a
file.
+ #[test]
+ fn arbitrary_metadata_and_value_never_panic(
+ metadata in prop::collection::vec(any::<u8>(), 1..24),
+ value in prop::collection::vec(any::<u8>(), 1..24),
+ ) {
+ let _ = Variant::try_new(&metadata, &value).as_ref().map(traverse);
+ }
+
+ /// Validated metadata must be panic-free to index and iterate, and `get`
must not fail.
+ #[test]
+ fn validated_metadata_is_accessible(metadata in arb_metadata_bytes()) {
+ if let Ok(md) = VariantMetadata::try_new(&metadata) {
+ for i in 0..md.len() {
+ prop_assert!(md.get(i).is_ok(), "validated, but get({i})
failed");
+ let _ = &md[i];
+ }
+ let _: Vec<_> = md.iter().collect();
+ }
+ }
+
+ /// A well-formed object, then one byte perturbed. Reaches near-miss
states that random bytes
+ /// do not.
+ #[test]
+ fn perturbed_object_never_panics(
+ names in arb_field_names(1..5),
+ index in any::<prop::sample::Index>(),
+ byte in any::<u8>(),
+ ) {
+ let order: Vec<&str> = names.iter().map(|s| s.as_str()).collect();
+ let (metadata, mut value) = build_object(&names, &order);
+ let i = index.index(value.len());
+ value[i] = byte;
+ let _ = Variant::try_new(&metadata, &value).as_ref().map(traverse);
+ }
+}
+
+/// Metadata buffers shaped like the real thing -- a plausible header,
dictionary size, offsets and
+/// values -- since fully random bytes are rejected by the header check and
never reach the offset
+/// and UTF-8 validation this is meant to exercise.
+fn arb_metadata_bytes() -> impl Strategy<Value = Vec<u8>> {
+ (
+ prop::bool::ANY,
+ 0usize..6,
+ prop::collection::vec(0u8..8, 0..8),
+ prop::collection::vec(
+ prop_oneof![
+ Just(b"a".to_vec()),
+ Just("é".as_bytes().to_vec()),
+ Just("€".as_bytes().to_vec()),
+ Just(Vec::new()),
+ ],
+ 0..5,
+ ),
+ )
+ .prop_map(|(sorted, size, offsets, values)| {
+ let mut bytes = vec![0x01 | (u8::from(sorted) << 4)];
+ bytes.push(size as u8);
+ let mut offsets = offsets;
+ offsets.resize(size + 1, 0);
+ bytes.extend_from_slice(&offsets);
+ values.iter().for_each(|v| bytes.extend_from_slice(v));
+ bytes
+ })
+}
