mbutrovich commented on code in PR #2866:
URL: https://github.com/apache/iceberg-rust/pull/2866#discussion_r3805671648
##########
crates/iceberg/src/delete_vector.rs:
##########
@@ -68,6 +77,148 @@ impl DeleteVector {
pub fn len(&self) -> u64 {
self.inner.len()
}
+
+ /// Parses a `deletion-vector-v1` Puffin blob into a `DeleteVector`.
+ ///
+ /// The layout, defined by the Iceberg Puffin spec and matching
Iceberg-Java's
+ /// `BitmapPositionDeleteIndex`, is:
+ ///
+ /// ```text
+ /// [length: u32 big-endian][magic: D1 D3 39 64][vector][crc: u32
big-endian]
+ /// ```
+ ///
+ /// `length` counts the magic and vector bytes (not itself or the CRC).
The CRC-32 is
+ /// computed over the magic and vector. `vector` is a roaring bitmap in
the portable 64-bit
+ /// format: a directory of 32-bit key / 32-bit roaring bitmap pairs,
ordered by unsigned
+ /// comparison of the keys, one bitmap per key.
+ ///
+ /// Cardinality is not checked here. The caller validates the decoded
length against the
+ /// delete file's `record_count`, where the manifest metadata is available.
+ ///
+ /// # Errors
+ ///
+ /// Returns [`ErrorKind::DataInvalid`] if the blob is shorter than the
minimum, the length
+ /// prefix or CRC does not match, the magic is wrong, the roaring
directory's keys are not
+ /// ordered by unsigned comparison, or the roaring payload fails to decode.
+ // Consumed by the scan delete loader once the deletion-vector read path
is wired up.
+ #[allow(dead_code)]
+ pub fn deserialize(blob: &[u8]) -> Result<Self> {
+ if blob.len() < DV_MIN_BLOB_BYTES {
+ return Err(Error::new(
+ ErrorKind::DataInvalid,
+ format!(
+ "deletion-vector-v1 blob is {} bytes, shorter than the
{DV_MIN_BLOB_BYTES}-byte minimum",
+ blob.len()
+ ),
+ ));
+ }
+
+ // The magic and vector, i.e. the bytes covered by both the length
prefix and the CRC.
+ let body = &blob[DV_LENGTH_PREFIX_BYTES..blob.len() - DV_CRC_BYTES];
+
+ let declared_len = (&blob[..DV_LENGTH_PREFIX_BYTES])
+ .try_get_u32()
+ .map_err(|e| {
+ Error::new(
+ ErrorKind::Unexpected,
+ "failed to read the deletion-vector-v1 length prefix",
+ )
+ .with_source(e)
+ })? as usize;
+ if declared_len != body.len() {
+ return Err(Error::new(
+ ErrorKind::DataInvalid,
+ format!(
+ "deletion-vector-v1 length prefix is {declared_len},
expected {}",
+ body.len()
+ ),
+ ));
+ }
+
+ // Verify the CRC before interpreting any bytes so a corrupt blob
yields a single clear
+ // error rather than an opaque roaring decode failure.
+ let stored_crc = (&blob[blob.len() - DV_CRC_BYTES..])
+ .try_get_u32()
+ .map_err(|e| {
+ Error::new(
+ ErrorKind::Unexpected,
+ "failed to read the deletion-vector-v1 CRC",
+ )
+ .with_source(e)
+ })?;
+ let computed_crc = crc32fast::hash(body);
+ if computed_crc != stored_crc {
+ return Err(Error::new(
+ ErrorKind::DataInvalid,
+ format!(
+ "deletion-vector-v1 CRC mismatch: computed
{computed_crc:#010x}, stored {stored_crc:#010x}"
+ ),
+ ));
+ }
+
+ let (magic, vector) = body.split_at(DV_MAGIC_BYTES);
+ if magic != DV_MAGIC {
+ return Err(Error::new(
+ ErrorKind::DataInvalid,
+ format!(
+ "deletion-vector-v1 magic mismatch: {magic:02x?}, expected
{DV_MAGIC:02x?}"
+ ),
+ ));
+ }
+
+ // The Puffin spec defines the roaring directory as the bitmaps
"ordered by unsigned
+ // comparison of the 32-bit keys", with one bitmap per key. Walk it
ourselves (rather than
+ // `RoaringTreemap::deserialize_from`, which stores keys in a
`BTreeMap` via a plain insert
+ // and would silently accept a stream with duplicate or out-of-order
keys, discarding the
+ // earlier bitmap on a duplicate) so a non-conformant blob is rejected
instead of decoded
+ // into a value that doesn't match what was actually written.
+ let mut reader = vector;
+ let bitmap_count = reader.try_get_u64_le().map_err(|e| {
Review Comment:
> Also can we move these validations into helper functions to improve
readability?
>
> The body of the current function is mainly different validations right now
and is a bit hard to follow
Done, split into `verify_length_prefix`, `verify_crc`, `verify_magic`, and
`decode_roaring_directory`. `deserialize` now just threads the blob through
them in order.
##########
crates/iceberg/src/delete_vector.rs:
##########
@@ -68,6 +77,148 @@ impl DeleteVector {
pub fn len(&self) -> u64 {
self.inner.len()
}
+
+ /// Parses a `deletion-vector-v1` Puffin blob into a `DeleteVector`.
+ ///
+ /// The layout, defined by the Iceberg Puffin spec and matching
Iceberg-Java's
+ /// `BitmapPositionDeleteIndex`, is:
+ ///
+ /// ```text
+ /// [length: u32 big-endian][magic: D1 D3 39 64][vector][crc: u32
big-endian]
+ /// ```
+ ///
+ /// `length` counts the magic and vector bytes (not itself or the CRC).
The CRC-32 is
+ /// computed over the magic and vector. `vector` is a roaring bitmap in
the portable 64-bit
+ /// format: a directory of 32-bit key / 32-bit roaring bitmap pairs,
ordered by unsigned
+ /// comparison of the keys, one bitmap per key.
+ ///
+ /// Cardinality is not checked here. The caller validates the decoded
length against the
+ /// delete file's `record_count`, where the manifest metadata is available.
+ ///
+ /// # Errors
+ ///
+ /// Returns [`ErrorKind::DataInvalid`] if the blob is shorter than the
minimum, the length
+ /// prefix or CRC does not match, the magic is wrong, the roaring
directory's keys are not
+ /// ordered by unsigned comparison, or the roaring payload fails to decode.
+ // Consumed by the scan delete loader once the deletion-vector read path
is wired up.
+ #[allow(dead_code)]
+ pub fn deserialize(blob: &[u8]) -> Result<Self> {
+ if blob.len() < DV_MIN_BLOB_BYTES {
+ return Err(Error::new(
+ ErrorKind::DataInvalid,
+ format!(
+ "deletion-vector-v1 blob is {} bytes, shorter than the
{DV_MIN_BLOB_BYTES}-byte minimum",
+ blob.len()
+ ),
+ ));
+ }
+
+ // The magic and vector, i.e. the bytes covered by both the length
prefix and the CRC.
+ let body = &blob[DV_LENGTH_PREFIX_BYTES..blob.len() - DV_CRC_BYTES];
+
+ let declared_len = (&blob[..DV_LENGTH_PREFIX_BYTES])
+ .try_get_u32()
+ .map_err(|e| {
+ Error::new(
+ ErrorKind::Unexpected,
+ "failed to read the deletion-vector-v1 length prefix",
+ )
+ .with_source(e)
+ })? as usize;
+ if declared_len != body.len() {
+ return Err(Error::new(
+ ErrorKind::DataInvalid,
+ format!(
+ "deletion-vector-v1 length prefix is {declared_len},
expected {}",
+ body.len()
+ ),
+ ));
+ }
+
+ // Verify the CRC before interpreting any bytes so a corrupt blob
yields a single clear
+ // error rather than an opaque roaring decode failure.
+ let stored_crc = (&blob[blob.len() - DV_CRC_BYTES..])
+ .try_get_u32()
+ .map_err(|e| {
+ Error::new(
+ ErrorKind::Unexpected,
+ "failed to read the deletion-vector-v1 CRC",
+ )
+ .with_source(e)
+ })?;
+ let computed_crc = crc32fast::hash(body);
+ if computed_crc != stored_crc {
+ return Err(Error::new(
+ ErrorKind::DataInvalid,
+ format!(
+ "deletion-vector-v1 CRC mismatch: computed
{computed_crc:#010x}, stored {stored_crc:#010x}"
+ ),
+ ));
+ }
+
+ let (magic, vector) = body.split_at(DV_MAGIC_BYTES);
+ if magic != DV_MAGIC {
+ return Err(Error::new(
+ ErrorKind::DataInvalid,
+ format!(
+ "deletion-vector-v1 magic mismatch: {magic:02x?}, expected
{DV_MAGIC:02x?}"
+ ),
+ ));
+ }
+
+ // The Puffin spec defines the roaring directory as the bitmaps
"ordered by unsigned
+ // comparison of the 32-bit keys", with one bitmap per key. Walk it
ourselves (rather than
+ // `RoaringTreemap::deserialize_from`, which stores keys in a
`BTreeMap` via a plain insert
+ // and would silently accept a stream with duplicate or out-of-order
keys, discarding the
+ // earlier bitmap on a duplicate) so a non-conformant blob is rejected
instead of decoded
+ // into a value that doesn't match what was actually written.
+ let mut reader = vector;
+ let bitmap_count = reader.try_get_u64_le().map_err(|e| {
Review Comment:
> [Roaring bitmap portable format
](https://github.com/RoaringBitmap/RoaringFormatSpec?tab=readme-ov-file#general-layout-1)states
that the range or bitmap_count actuallys falls in [0, 2^32 - 1], and we should
validate that.
>
> I think 2^32 - 1 is the number of possible keys. I'm not really sure why
they want to use 4 padding zero bytes here instead of just use 4 bytes to
represent bitmap_count. But not validating this will allow unexpected failure
Good catch, added. The roaring portable format spec restricts the bitmap
count to `[0, 2^32 - 1]` (stored as a u64 with the top 32 bits reserved as
padding), so I added a bound check before the per-key loop in
`decode_roaring_directory`.
I didn't add Java's additional `key <= Integer.MAX_VALUE - 1` bound on
individual keys: that's an artifact of `RoaringBitmap` using a signed 32-bit
int internally in Java, not a requirement in the Puffin spec or the Roaring
format spec. Our key is already a plain `u32`, so it's structurally confined to
`[0, 2^32-1]` with no extra check needed.
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
