sdf-jkl commented on code in PR #11511:
URL: https://github.com/apache/arrow-rs/pull/11511#discussion_r4595936156


##########
parquet-variant/src/variant/view.rs:
##########
@@ -0,0 +1,546 @@
+// SPDX-License-Identifier: Apache-2.0
+// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for 
additional information regarding copyright ownership
+// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) 
under one or more contributor license agreements
+
+//! Views over encoded variant bytes that read only what they use.
+//!
+//! Building a view parses one header and nothing else. Each accessor reads 
and bounds-checks only
+//! the bytes it needs, so malformed input produces an error, never a panic. A 
view does not check
+//! UTF-8, sort order, or any offset it does not read. Field names are 
compared as bytes, which
+//! orders them exactly as `str` does.
+//!
+//! The views are the weakest state of a variant. The [`Variant`], 
[`VariantMetadata`],
+//! [`VariantObject`] and [`VariantList`] types are the stronger states:
+//!
+//! - [`ValueView::to_variant`], [`MetadataView::into_metadata`], 
[`ObjectView::into_object`] and
+//!   [`ListView::into_list`] check the first and last offsets, which bound 
the encoding. Those
+//!   checks are the ones that unvalidated instances of the public types 
guarantee.
+//! - The `with_full_validation` methods of the public types check everything 
else.
+//!
+//! A child value starts at its offset and extends to the end of its parent, 
because object field
+//! values need not be stored in field order. [`ValueView::bytes`] finds the 
exact encoding of a
+//! value when a caller needs it.
+
+use arrow_schema::ArrowError;
+
+pub use crate::decoder::VariantBasicType;
+
+use crate::decoder::{VariantPrimitiveType, get_basic_type};
+use crate::path::VariantPathElement;
+use crate::utils::{
+    array_from_slice, first_byte_from_slice, overflow_error, slice_from_slice,
+    slice_from_slice_at_offset, str_from_bytes, try_binary_search,
+};
+use crate::variant::list::VariantListHeader;
+use crate::variant::metadata::VariantMetadataHeader;
+use crate::variant::object::VariantObjectHeader;
+use crate::variant::{
+    EMPTY_VARIANT_METADATA, Variant, VariantList, VariantMetadata, 
VariantObject,
+};
+
+/// The size of the header byte of a metadata dictionary, object or list.
+const NUM_HEADER_BYTES: u32 = 1;
+
+#[inline]
+fn checked(value: Option<u32>, what: &str) -> Result<u32, ArrowError> {
+    value.ok_or_else(|| overflow_error(what))
+}
+
+fn index_error(kind: &str, index: usize, len: usize) -> ArrowError {
+    ArrowError::InvalidArgumentError(format!(
+        "{kind} index {index} is out of bounds for length {len}"
+    ))
+}
+
+/// A metadata dictionary of which only the header has been read.
+#[derive(Debug, Clone, Copy)]
+pub struct MetadataView<'m> {
+    pub(crate) bytes: &'m [u8],
+    pub(crate) header: VariantMetadataHeader,
+    pub(crate) dictionary_size: u32,
+    pub(crate) first_value_byte: u32,
+}
+
+impl<'m> MetadataView<'m> {
+    /// Reads the header and the dictionary size of the metadata dictionary in 
`bytes`.
+    #[inline]
+    pub fn try_new(bytes: &'m [u8]) -> Result<Self, ArrowError> {
+        let header = 
VariantMetadataHeader::try_new(first_byte_from_slice(bytes)?)?;
+        let dictionary_size =
+            header
+                .offset_size
+                .unpack_u32_at_offset(bytes, NUM_HEADER_BYTES as _, 0)?;
+
+        // There are dictionary_size + 1 offsets, and the string bytes 
immediately follow them.
+        let first_value_byte = checked(
+            dictionary_size
+                .checked_add(1)
+                .and_then(|n| n.checked_mul(header.offset_size()))
+                .and_then(|n| n.checked_add(header.first_offset_byte())),
+            "offset of variant metadata dictionary",
+        )?;
+
+        Ok(Self {
+            bytes,
+            header,
+            dictionary_size,
+            first_value_byte,
+        })
+    }
+
+    /// The number of entries in the dictionary.
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.dictionary_size as _
+    }
+
+    /// True if the dictionary has no entries.
+    #[inline]
+    pub fn is_empty(&self) -> bool {
+        self.dictionary_size == 0
+    }
+
+    /// True if the header declares the entries unique and sorted.
+    #[inline]
+    pub fn is_sorted(&self) -> bool {
+        self.header.is_sorted
+    }
+
+    /// The bytes of entry `id`, without UTF-8 validation.
+    #[inline]
+    pub fn entry(&self, id: usize) -> Result<&'m [u8], ArrowError> {
+        if id >= self.len() {
+            return Err(index_error("Metadata dictionary", id, self.len()));
+        }
+        self.read_entry(id)
+    }
+
+    /// The entry `id` as a string.
+    pub fn entry_str(&self, id: usize) -> Result<&'m str, ArrowError> {
+        str_from_bytes(self.entry(id)?)
+    }
+
+    /// The id of the entry equal to `name`, if any.
+    ///
+    /// The search is a binary search if the dictionary is sorted and has more 
than a few entries,
+    /// and a linear scan otherwise.
+    pub fn find(&self, name: &[u8]) -> Result<Option<u32>, ArrowError> {
+        if self.is_sorted() && self.len() > 10 {
+            let found = try_binary_search(self.len(), |id| 
Ok(self.read_entry(id)?.cmp(name)))?;
+            return Ok(found.map(|id| id as u32));
+        }
+        for id in 0..self.len() {
+            if self.read_entry(id)? == name {
+                return Ok(Some(id as u32));
+            }
+        }
+        Ok(None)
+    }
+
+    /// Checks the first and last offsets, and returns the bounded 
[`VariantMetadata`].
+    #[inline]
+    pub fn into_metadata(self) -> Result<VariantMetadata<'m>, ArrowError> {
+        VariantMetadata::try_from_view(self)
+    }
+
+    /// Entry `i` of the offset array, for `i` in `0..=self.len()`.
+    #[inline]
+    pub(crate) fn offset(&self, i: usize) -> Result<u32, ArrowError> {
+        self.header.offset_size.unpack_u32_at_offset(
+            self.bytes,
+            self.header.first_offset_byte() as _,
+            i,
+        )
+    }
+
+    // The bytes of entry `id`, for `id` in `0..self.len()`.
+    #[inline]
+    fn read_entry(&self, id: usize) -> Result<&'m [u8], ArrowError> {
+        let range = self.offset(id)? as usize..self.offset(id + 1)? as usize;
+        slice_from_slice_at_offset(self.bytes, self.first_value_byte as _, 
range)
+    }
+}
+
+/// A variant value of which only the header byte has been read.
+#[derive(Debug, Clone, Copy)]
+pub struct ValueView<'m, 'v> {
+    pub(crate) metadata: MetadataView<'m>,
+    pub(crate) value: &'v [u8],
+    header: u8,
+}
+
+impl<'m, 'v> ValueView<'m, 'v> {
+    /// Reads the header byte of the value that starts at the beginning of 
`value`.
+    ///
+    /// `value` may extend past the end of the value.
+    #[inline]
+    pub fn try_new(metadata: MetadataView<'m>, value: &'v [u8]) -> 
Result<Self, ArrowError> {
+        let header = first_byte_from_slice(value)?;
+        Ok(Self {
+            metadata,
+            value,
+            header,
+        })
+    }
+
+    /// The metadata dictionary of this value.
+    #[inline]
+    pub fn metadata(&self) -> MetadataView<'m> {
+        self.metadata
+    }
+
+    /// The basic type of this value.
+    #[inline]
+    pub fn basic_type(&self) -> VariantBasicType {
+        get_basic_type(self.header)
+    }
+
+    /// This value as an object, or `None` if it is not an object.
+    pub fn as_object(&self) -> Result<Option<ObjectView<'m, 'v>>, ArrowError> {
+        match self.basic_type() {
+            VariantBasicType::Object => ObjectView::try_new(self.metadata, 
self.value).map(Some),
+            _ => Ok(None),
+        }
+    }
+
+    /// This value as a list, or `None` if it is not a list.
+    pub fn as_list(&self) -> Result<Option<ListView<'m, 'v>>, ArrowError> {
+        match self.basic_type() {
+            VariantBasicType::Array => ListView::try_new(self.metadata, 
self.value).map(Some),
+            _ => Ok(None),
+        }
+    }
+
+    /// The value of field `name`, or `None` if this value is not an object or 
has no such field.
+    pub fn get_field(&self, name: &[u8]) -> Result<Option<Self>, ArrowError> {
+        match self.as_object()? {
+            Some(object) => object.get(name),
+            None => Ok(None),
+        }
+    }
+
+    /// Element `index`, or `None` if this value is not a list or has no such 
element.
+    pub fn get_index(&self, index: usize) -> Result<Option<Self>, ArrowError> {
+        match self.as_list()? {
+            Some(list) => list.get(index),
+            None => Ok(None),
+        }
+    }
+
+    /// Follows `path` from this value, or returns `None` if a step does not 
exist.
+    ///
+    /// A [`VariantPathElement::ListElement`] step does not exist, as in 
[`Variant::get_path`].
+    #[inline]
+    pub fn get_path(&self, path: &[VariantPathElement<'_>]) -> 
Result<Option<Self>, ArrowError> {
+        let mut current = *self;
+        for element in path {
+            let next = match element {
+                VariantPathElement::Field { name } => 
current.get_field(name.as_bytes())?,
+                VariantPathElement::Index { index } => 
current.get_index(*index)?,
+                VariantPathElement::ListElement => None,
+            };
+            match next {
+                Some(next) => current = next,
+                None => return Ok(None),
+            }
+        }
+        Ok(Some(current))
+    }
+
+    /// Decodes this value as an unvalidated [`Variant`].
+    ///
+    /// Only an object or a list reads the metadata dictionary, so only they 
check its bounds.
+    #[inline]
+    pub fn to_variant(&self) -> Result<Variant<'m, 'v>, ArrowError> {
+        let metadata = match self.basic_type() {
+            VariantBasicType::Object | VariantBasicType::Array => 
self.metadata.into_metadata()?,
+            VariantBasicType::Primitive | VariantBasicType::ShortString => 
EMPTY_VARIANT_METADATA,
+        };
+        Variant::try_new_with_metadata_and_shallow_validation(metadata, 
self.value)
+    }
+
+    /// The exact encoding of this value, without any bytes that follow it.
+    pub fn bytes(&self) -> Result<&'v [u8], ArrowError> {
+        let len = match self.basic_type() {
+            VariantBasicType::Primitive => primitive_len(self.header, 
self.value)?,
+            VariantBasicType::ShortString => 1 + (self.header >> 2) as usize,
+            VariantBasicType::Object => {
+                ObjectView::try_new(self.metadata, self.value)?.byte_len()?
+            }
+            VariantBasicType::Array => ListView::try_new(self.metadata, 
self.value)?.byte_len()?,
+        };
+        slice_from_slice(self.value, ..len)
+    }
+}
+
+/// The encoded size of the primitive value with header byte `header` at the 
start of `value`.
+fn primitive_len(header: u8, value: &[u8]) -> Result<usize, ArrowError> {
+    use VariantPrimitiveType::*;
+    let payload = match VariantPrimitiveType::try_from(header >> 2)? {
+        Null | BooleanTrue | BooleanFalse => 0,
+        Int8 => 1,
+        Int16 => 2,
+        Int32 | Date | Float => 4,
+        Decimal4 => 5,
+        Int64 | Double | TimestampMicros | TimestampNtzMicros | TimestampNanos
+        | TimestampNtzNanos | Time => 8,
+        Decimal8 => 9,
+        Uuid => 16,
+        Decimal16 => 17,
+        Binary | String => 4 + u32::from_le_bytes(array_from_slice(value, 1)?) 
as usize,
+    };
+    Ok(1 + payload)

Review Comment:
   🤖 💬 : Could both the length-prefix addition here and the header-byte 
addition below use checked arithmetic? On 32-bit targets, a length of 
`u32::MAX` overflows `4 + length`; `u32::MAX - 4` makes that addition succeed 
but overflows the subsequent `1 + payload`. With overflow checks this panics; 
without them the total wraps to a small length, so a truncated encoding can be 
accepted by `bytes()`.
   
   Minimal regression test (save as `parquet-variant/tests/pr11511_length.rs`):
   
   ```rust
   #[test]
   fn truncated_large_payload_is_rejected() {
       use parquet_variant::view::{MetadataView, ValueView};
       use parquet_variant::EMPTY_VARIANT_METADATA_BYTES;
   
       let metadata = 
MetadataView::try_new(EMPTY_VARIANT_METADATA_BYTES).unwrap();
       for header in [0x3c, 0x40] { // Binary and long String
           for length in [u32::MAX, u32::MAX - 4] {
               let mut bytes = vec![header];
               bytes.extend_from_slice(&length.to_le_bytes());
               let value = ValueView::try_new(metadata, &bytes).unwrap();
               assert!(value.bytes().is_err());
           }
       }
   }
   ```
   
   On a machine with an installed 32-bit Rust target and its linker/runtime:
   
   ```sh
   cargo test -p parquet-variant --test pr11511_length --target 
i686-unknown-linux-gnu
   cargo test -p parquet-variant --test pr11511_length --target 
i686-unknown-linux-gnu --release
   ```
   
   Expected: all four malformed encodings return `Err`. On 32-bit with default 
debug overflow checks, the first case should panic in the addition; with 
default release wrapping, it should return `Ok` with a four-byte slice, failing 
the assertion.
   
   This is an inspection finding: I compiled and ran this exact test on x86_64, 
where it passes, but have not run it on a 32-bit target. The arithmetic is 
unchanged when applying this PR to upstream `7a1e79d0c2`. Using `checked_add` 
for both additions would return an error before slicing.
   



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]

Reply via email to