This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new cf25bbe fix: align empty Theta and Tuple seed hash handling (#283)
cf25bbe is described below
commit cf25bbee6e2d2e771c1046763e06406502c800e3
Author: tison <[email protected]>
AuthorDate: Tue Sep 29 23:23:26 2026 +0800
fix: align empty Theta and Tuple seed hash handling (#283)
---
CHANGELOG.md | 1 +
.../src/thetafamily/theta/serialization.rs | 3 +
datasketches/src/thetafamily/theta/sketch.rs | 112 ++++++++++-----------
.../src/thetafamily/tuple/serialization.rs | 3 +
datasketches/src/thetafamily/tuple/sketch.rs | 36 ++++---
tests-integration/tests/serde_tests/theta.rs | 91 +++++++++++++++--
tests-integration/tests/serde_tests/tuple.rs | 48 +++++++++
7 files changed, 209 insertions(+), 85 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index e6614a7..5137769 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -29,6 +29,7 @@ All significant changes to this project will be documented in
this file.
### Bug fixes
+* Empty compact Theta and Tuple sketches now serialize with a zero seed hash,
matching the canonical cross-language encoding. Deserialization associates
empty sketches with the supplied seed, including legacy Theta v2 images with
zero or mismatched seed hashes.
* `CountMinSketch` updates now panic and merges return `InvalidArgument` if
the total absolute weight would exceed the counter type's maximum. Both leave
the sketch unchanged, including in release builds.
* `CountMinSketch::upper_bound` now clamps to the counter type's maximum
instead of overflowing.
* `CountMinSketch` deserialization now returns `InvalidData` if the total
absolute weight is negative or any counter's magnitude exceeds it.
diff --git a/datasketches/src/thetafamily/theta/serialization.rs
b/datasketches/src/thetafamily/theta/serialization.rs
index f9d6e2c..d10917f 100644
--- a/datasketches/src/thetafamily/theta/serialization.rs
+++ b/datasketches/src/thetafamily/theta/serialization.rs
@@ -20,6 +20,9 @@
pub const UNCOMPRESSED_SERIAL_VERSION: u8 = 3;
pub const COMPRESSED_SERIAL_VERSION: u8 = 4;
+/// Canonical empty compact image, independent of the configured seed.
+pub const EMPTY_SKETCH_BYTES: [u8; 8] = [1, 3, 3, 0, 0, 0x1e, 0, 0];
+
pub const V2_PREAMBLE_EMPTY: u8 = 1;
pub const V2_PREAMBLE_PRECISE: u8 = 2;
pub const V2_PREAMBLE_ESTIMATE: u8 = 3;
diff --git a/datasketches/src/thetafamily/theta/sketch.rs
b/datasketches/src/thetafamily/theta/sketch.rs
index c293a77..2c87383 100644
--- a/datasketches/src/thetafamily/theta/sketch.rs
+++ b/datasketches/src/thetafamily/theta/sketch.rs
@@ -495,7 +495,7 @@ impl CompactThetaSketch {
self.compact_state.is_ordered()
}
- /// Returns the 16-bit seed hash.
+ /// Returns the 16-bit fingerprint of the seed associated with this sketch.
pub fn seed_hash(&self) -> u16 {
self.compact_state.seed_hash()
}
@@ -537,7 +537,7 @@ impl CompactThetaSketch {
if self.is_estimation_mode() { 2 } else { 1 }
} else if self.is_estimation_mode() {
3
- } else if self.is_empty() || self.num_retained() == 1 {
+ } else if self.num_retained() == 1 {
1
} else {
2
@@ -546,8 +546,7 @@ impl CompactThetaSketch {
/// Serializes this sketch in compressed form if applicable.
///
- /// This uses `serVer = 4` when the sketch is ordered and suitable for
compression, and falls
- /// back to uncompressed `serVer = 3` otherwise.
+ /// Falls back to [`serialize`](Self::serialize) when compression is not
applicable.
pub fn serialize_compressed(&self) -> Vec<u8> {
if self.is_suitable_for_compression() {
self.serialize_v4()
@@ -562,8 +561,14 @@ impl CompactThetaSketch {
&& (self.num_retained() != 1 || self.is_estimation_mode())
}
- /// Serializes this sketch into the uncompressed compact theta format.
+ /// Serializes this sketch into the uncompressed compact Theta format.
+ ///
+ /// Empty sketches serialize with a zero seed hash.
pub fn serialize(&self) -> Vec<u8> {
+ if self.is_empty() {
+ return serialization::EMPTY_SKETCH_BYTES.to_vec();
+ }
+
let retained_hashes = self.retained_hashes();
let mut bytes = SketchBytes::with_capacity(64 + retained_hashes.len()
* 8);
@@ -576,9 +581,6 @@ impl CompactThetaSketch {
let mut flags = 0u8;
flags |= FLAGS_IS_READ_ONLY;
flags |= FLAGS_IS_COMPACT;
- if self.is_empty() {
- flags |= FLAGS_IS_EMPTY;
- }
if self.is_ordered() {
flags |= FLAGS_IS_ORDERED;
}
@@ -685,22 +687,24 @@ impl CompactThetaSketch {
bits.div_ceil(8) as u8
}
- /// Deserializes a compact theta sketch from bytes.
+ /// Deserializes a compact Theta sketch using the default seed.
///
/// # Errors
///
- /// Returns `InvalidData` if the image is malformed or its seed hash does
not match the default
- /// seed.
+ /// Returns `InvalidData` if the image is malformed or a non-empty image's
seed hash does not
+ /// match the default seed.
pub fn deserialize(bytes: &[u8]) -> Result<Self, Error> {
Self::deserialize_with_seed(bytes, DEFAULT_UPDATE_SEED)
}
- /// Deserializes a compact theta sketch from bytes using the provided
expected seed.
+ /// Deserializes a compact Theta sketch using `seed`.
+ ///
+ /// Empty sketches use the hash of `seed` regardless of the stored seed
hash.
///
/// # Errors
///
- /// Returns `InvalidData` if the image is malformed, its seed hash does
not match `seed`, or
- /// `seed` itself computes to the reserved zero seed hash.
+ /// Returns `InvalidData` if the image is malformed, a non-empty image's
seed hash does not
+ /// match `seed`, or `seed` itself computes to the reserved zero seed hash.
pub fn deserialize_with_seed(bytes: &[u8], seed: u64) -> Result<Self,
Error> {
let expected_seed_hash = compute_seed_hash(seed,
ErrorKind::InvalidData)?;
let mut cursor = SketchSlice::new(bytes);
@@ -809,36 +813,9 @@ impl CompactThetaSketch {
let seed_hash = cursor
.read_u16_le()
.map_err(insufficient_data("seed_hash"))?;
- check_seed_hash(
- expected_seed_hash,
- seed_hash,
- "deserialized CompactThetaSketch v2",
- ErrorKind::InvalidData,
- )?;
-
- match pre_longs {
- V2_PREAMBLE_EMPTY =>
Ok(Self::from_compact_state(CompactSketchState::empty(
- seed_hash,
- ))),
- V2_PREAMBLE_PRECISE => {
- let num_entries = cursor
- .read_u32_le()
- .map_err(insufficient_data("num_entries"))?
- as usize;
- cursor
- .read_u32_le()
- .map_err(insufficient_data("<unused_u32>"))?;
- let entries = Self::read_entries(&mut cursor, num_entries,
MAX_THETA)?;
- if num_entries == 0 {
- return
Ok(Self::from_compact_state(CompactSketchState::empty(
- seed_hash,
- )));
- }
- Ok(Self::from_compact_state(CompactSketchState::non_empty(
- entries, MAX_THETA, seed_hash, true,
- )))
- }
- V2_PREAMBLE_ESTIMATE => {
+ let (num_entries, theta) = match pre_longs {
+ V2_PREAMBLE_EMPTY => (0, MAX_THETA),
+ V2_PREAMBLE_PRECISE | V2_PREAMBLE_ESTIMATE => {
let num_entries = cursor
.read_u32_le()
.map_err(insufficient_data("num_entries"))?
@@ -846,23 +823,36 @@ impl CompactThetaSketch {
cursor
.read_u32_le()
.map_err(insufficient_data("<unused_u32>"))?;
- let theta = Self::deserialize_theta(
- cursor
- .read_u64_le()
- .map_err(insufficient_data("theta_long"))?,
- )?;
- let entries = Self::read_entries(&mut cursor, num_entries,
theta)?;
- if num_entries == 0 && theta == MAX_THETA {
- return
Ok(Self::from_compact_state(CompactSketchState::empty(
- seed_hash,
- )));
- }
- Ok(Self::from_compact_state(CompactSketchState::non_empty(
- entries, theta, seed_hash, true,
- )))
+ let theta = if pre_longs == V2_PREAMBLE_ESTIMATE {
+ Self::deserialize_theta(
+ cursor
+ .read_u64_le()
+ .map_err(insufficient_data("theta_long"))?,
+ )?
+ } else {
+ MAX_THETA
+ };
+ (num_entries, theta)
}
- _ => Err(Error::invalid_preamble_longs(&[1, 2, 3], pre_longs)),
+ _ => return Err(Error::invalid_preamble_longs(&[1, 2, 3],
pre_longs)),
+ };
+
+ if num_entries == 0 && theta == MAX_THETA {
+ return Ok(Self::from_compact_state(CompactSketchState::empty(
+ expected_seed_hash,
+ )));
}
+
+ check_seed_hash(
+ expected_seed_hash,
+ seed_hash,
+ "deserialized CompactThetaSketch v2",
+ ErrorKind::InvalidData,
+ )?;
+ let entries = Self::read_entries(&mut cursor, num_entries, theta)?;
+ Ok(Self::from_compact_state(CompactSketchState::non_empty(
+ entries, theta, seed_hash, true,
+ )))
}
fn deserialize_v3(
@@ -881,7 +871,7 @@ impl CompactThetaSketch {
let empty = (flags & FLAGS_IS_EMPTY) != 0;
if empty {
return Ok(Self::from_compact_state(CompactSketchState::empty(
- seed_hash,
+ expected_seed_hash,
)));
}
@@ -1021,7 +1011,7 @@ impl CompactThetaSketch {
let ordered = (flags & FLAGS_IS_ORDERED) != 0;
let compact_state = if empty {
- CompactSketchState::empty(seed_hash)
+ CompactSketchState::empty(expected_seed_hash)
} else {
CompactSketchState::non_empty(entries, theta, seed_hash, ordered)
};
diff --git a/datasketches/src/thetafamily/tuple/serialization.rs
b/datasketches/src/thetafamily/tuple/serialization.rs
index 1f4cfee..d44a104 100644
--- a/datasketches/src/thetafamily/tuple/serialization.rs
+++ b/datasketches/src/thetafamily/tuple/serialization.rs
@@ -40,6 +40,9 @@ pub const SKETCH_TYPE: u8 = 1;
/// Legacy sketch-type byte still accepted on read.
pub const SKETCH_TYPE_LEGACY: u8 = 5;
+/// Canonical empty compact image, independent of the configured seed and
summary type.
+pub const EMPTY_SKETCH_BYTES: [u8; 8] = [1, 3, 9, 1, 0, 0x1e, 0, 0];
+
/// Trait for values that can be stored as Tuple sketch summaries.
///
/// Implement this trait for a summary type to make it (de)serializable by
diff --git a/datasketches/src/thetafamily/tuple/sketch.rs
b/datasketches/src/thetafamily/tuple/sketch.rs
index 2d6b93f..509ef16 100644
--- a/datasketches/src/thetafamily/tuple/sketch.rs
+++ b/datasketches/src/thetafamily/tuple/sketch.rs
@@ -53,6 +53,7 @@ use crate::tuple::hash_table::TupleEntry;
use crate::tuple::hash_table::TupleHashTable;
use crate::tuple::policy::SummaryPolicy;
use crate::tuple::policy::SummaryUpdatePolicy;
+use crate::tuple::serialization::EMPTY_SKETCH_BYTES;
use crate::tuple::serialization::SERIAL_VERSION;
use crate::tuple::serialization::SERIAL_VERSION_LEGACY;
use crate::tuple::serialization::SKETCH_TYPE;
@@ -503,7 +504,7 @@ impl<S> CompactTupleSketch<S> {
self.compact_state.is_ordered()
}
- /// Returns the 16-bit seed hash.
+ /// Returns the 16-bit fingerprint of the seed associated with this sketch.
pub fn seed_hash(&self) -> u16 {
self.compact_state.seed_hash()
}
@@ -549,7 +550,7 @@ impl<S> CompactTupleSketch<S> {
fn preamble_longs(&self) -> u8 {
if self.is_estimation_mode() {
3
- } else if self.is_empty() || self.num_retained() == 1 {
+ } else if self.num_retained() == 1 {
1
} else {
2
@@ -558,9 +559,10 @@ impl<S> CompactTupleSketch<S> {
/// Serializes this sketch into the compact Tuple binary format.
///
- /// Each summary is encoded by its [`TupleSummaryValue`] implementation.
The layout matches the
- /// Java/C++ Tuple sketches, so the output can be read by those
implementations given a
- /// compatible summary encoding.
+ /// Uses [`TupleSummaryValue`] to encode summaries. Reading the output in
Java or C++ requires
+ /// a compatible summary encoding.
+ ///
+ /// Empty sketches serialize with a zero seed hash.
///
/// # Examples
///
@@ -578,6 +580,10 @@ impl<S> CompactTupleSketch<S> {
where
S: TupleSummaryValue,
{
+ if self.is_empty() {
+ return EMPTY_SKETCH_BYTES.to_vec();
+ }
+
let retained_entries = self.retained_entries();
let pre_longs = self.preamble_longs();
let entries_size: usize = retained_entries
@@ -593,9 +599,6 @@ impl<S> CompactTupleSketch<S> {
bytes.write_u8(0); // unused
let mut flags = FLAGS_IS_READ_ONLY | FLAGS_IS_COMPACT;
- if self.is_empty() {
- flags |= FLAGS_IS_EMPTY;
- }
if self.is_ordered() {
flags |= FLAGS_IS_ORDERED;
}
@@ -621,8 +624,9 @@ impl<S> CompactTupleSketch<S> {
///
/// # Errors
///
- /// Returns `InvalidData` if the image is malformed, its seed hash does
not match the default
- /// seed, or a summary cannot be decoded by `S`.
+ /// Returns `InvalidData` if the image is malformed or a non-empty image's
seed hash does not
+ /// match the default seed. Also propagates errors from
+ /// [`TupleSummaryValue::deserialize_value`].
pub fn deserialize(bytes: &[u8]) -> Result<Self, Error>
where
S: TupleSummaryValue,
@@ -630,13 +634,15 @@ impl<S> CompactTupleSketch<S> {
Self::deserialize_with_seed(bytes, DEFAULT_UPDATE_SEED)
}
- /// Deserializes a compact Tuple sketch using the provided expected `seed`.
+ /// Deserializes a compact Tuple sketch using `seed`.
+ ///
+ /// Empty sketches use the hash of `seed` regardless of the stored seed
hash.
///
/// # Errors
///
- /// Returns `InvalidData` if the bytes are truncated, the family/serial
version/sketch type are
- /// unexpected, the seed hash does not match, the supplied seed computes
to the reserved zero
- /// seed hash, or an entry is corrupted.
+ /// Returns `InvalidData` if the image is malformed, a non-empty image's
seed hash does not
+ /// match `seed`, or `seed` itself computes to the reserved zero seed
hash. Also propagates
+ /// errors from [`TupleSummaryValue::deserialize_value`].
pub fn deserialize_with_seed(bytes: &[u8], seed: u64) -> Result<Self,
Error>
where
S: TupleSummaryValue,
@@ -680,7 +686,7 @@ impl<S> CompactTupleSketch<S> {
if empty {
return Ok(Self::from_compact_state(CompactSketchState::empty(
- seed_hash,
+ expected_seed_hash,
)));
}
diff --git a/tests-integration/tests/serde_tests/theta.rs
b/tests-integration/tests/serde_tests/theta.rs
index 0850f73..b51fc2d 100644
--- a/tests-integration/tests/serde_tests/theta.rs
+++ b/tests-integration/tests/serde_tests/theta.rs
@@ -159,6 +159,62 @@ fn test_go_compatibility() {
test_sketch_file(path, 0, false);
}
+#[test]
+fn empty_sketch_serialization() {
+ let expected = fs::read(serialization_test_data(
+ "cpp_generated_files",
+ "theta_n0_cpp.sk",
+ ))
+ .unwrap();
+ let sketch = ThetaSketchBuilder::default()
+ .seed(123)
+ .sampling_probability(0.5)
+ .build()
+ .unwrap()
+ .compact(false);
+ assert_eq!(sketch.serialize(), expected);
+ assert_eq!(sketch.serialize_compressed(), expected);
+
+ let other_seed_hash =
ThetaSketchBuilder::default().build().unwrap().seed_hash();
+ // v3 and v4 empty inputs; v4 includes a one-byte entry count of zero.
+ for mut bytes in [expected, vec![1, 4, 3, 0, 1, 0x1e, 0, 0, 0]] {
+ for stored_seed_hash in [0, other_seed_hash] {
+ bytes[6..8].copy_from_slice(&stored_seed_hash.to_le_bytes());
+ let restored = CompactThetaSketch::deserialize_with_seed(&bytes,
123).unwrap();
+ assert!(restored.is_empty());
+ assert_eq!(restored.seed_hash(), sketch.seed_hash());
+ }
+ }
+}
+
+#[test]
+fn non_empty_images_without_entries_preserve_seed_hash() {
+ let mut sketch = ThetaSketchBuilder::default()
+ .seed(123)
+ .sampling_probability(1e-12)
+ .build()
+ .unwrap();
+ sketch.update("apple");
+ let compact = sketch.compact(true);
+ assert!(!compact.is_empty());
+ assert_eq!(compact.num_retained(), 0);
+
+ // v2 and v3 share the count/theta layout for sampled sketches.
+ for version in [2, 3] {
+ let mut bytes = compact.serialize();
+ bytes[1] = version;
+ let restored = CompactThetaSketch::deserialize_with_seed(&bytes,
123).unwrap();
+ assert!(!restored.is_empty());
+ assert_eq!(restored.theta64(), compact.theta64());
+ let err = CompactThetaSketch::deserialize(&bytes).unwrap_err();
+ assert_eq!(err.kind(), ErrorKind::InvalidData);
+
+ bytes[6..8].fill(0);
+ let err = CompactThetaSketch::deserialize_with_seed(&bytes,
123).unwrap_err();
+ assert_eq!(err.kind(), ErrorKind::InvalidData);
+ }
+}
+
#[test]
fn malformed_input_is_rejected() {
let mut sketch = ThetaSketchBuilder::default().lg_k(5).build().unwrap();
@@ -235,13 +291,30 @@ fn test_v2_exact_non_empty_compatibility() {
}
#[test]
-fn test_v2_exact_zero_entries_remains_empty() {
- let sketch =
CompactThetaSketch::deserialize(&serialize_v2_exact(&[])).unwrap();
-
- assert!(sketch.is_empty());
- assert!(!sketch.is_estimation_mode());
- assert_eq!(sketch.num_retained(), 0);
- assert_eq!(sketch.estimate(), 0.0);
- assert_eq!(sketch.lower_bound(NumStdDev::One), 0.0);
- assert_eq!(sketch.upper_bound(NumStdDev::One), 0.0);
+fn test_v2_java_empty_layouts() {
+ let expected_seed_hash = ThetaSketchBuilder::default()
+ .seed(123)
+ .build()
+ .unwrap()
+ .seed_hash();
+ let other_seed_hash =
ThetaSketchBuilder::default().build().unwrap().seed_hash();
+
+ // Port of Java 8.0.0 ForwardCompatibilityTest's
checkSerVer2_{1,2,3}PreLong[s]_Empty:
+ //
https://github.com/apache/datasketches-java/blob/8.0.0/src/test/java/org/apache/datasketches/theta/ForwardCompatibilityTest.java#L90-L137
+ for pre_longs in [1, 2, 3] {
+ let mut bytes = serialize_v2_exact(&[]);
+ bytes[0] = pre_longs;
+ bytes[5] = 0x0e; // Java's v2 empty flags.
+ bytes.resize(pre_longs as usize * 8, 0);
+ if pre_longs == 3 {
+ bytes[16..24].copy_from_slice(&(i64::MAX as u64).to_le_bytes());
+ }
+
+ for stored_seed_hash in [0, other_seed_hash] {
+ bytes[6..8].copy_from_slice(&stored_seed_hash.to_le_bytes());
+ let sketch = CompactThetaSketch::deserialize_with_seed(&bytes,
123).unwrap();
+ assert!(sketch.is_empty());
+ assert_eq!(sketch.seed_hash(), expected_seed_hash);
+ }
+ }
}
diff --git a/tests-integration/tests/serde_tests/tuple.rs
b/tests-integration/tests/serde_tests/tuple.rs
index fe4c7be..3a71e25 100644
--- a/tests-integration/tests/serde_tests/tuple.rs
+++ b/tests-integration/tests/serde_tests/tuple.rs
@@ -108,6 +108,54 @@ fn test_go_compatibility() {
}
}
+#[test]
+fn empty_sketch_serialization() {
+ let expected = fs::read(serialization_test_data(
+ "cpp_generated_files",
+ "tuple_int_n0_cpp.sk",
+ ))
+ .unwrap();
+ let sketch = TupleSketchBuilder::new(DefaultUpdatePolicy::<i32>::default())
+ .seed(123)
+ .sampling_probability(0.5)
+ .build()
+ .unwrap()
+ .compact(false);
+ assert_eq!(sketch.serialize(), expected);
+
+ let other_seed_hash =
TupleSketchBuilder::new(DefaultUpdatePolicy::<i32>::default())
+ .build()
+ .unwrap()
+ .seed_hash();
+ for stored_seed_hash in [0, other_seed_hash] {
+ let mut bytes = expected.clone();
+ bytes[6..8].copy_from_slice(&stored_seed_hash.to_le_bytes());
+ let restored =
CompactTupleSketch::<i32>::deserialize_with_seed(&bytes, 123).unwrap();
+ assert!(restored.is_empty());
+ assert_eq!(restored.seed_hash(), sketch.seed_hash());
+ }
+}
+
+#[test]
+fn non_empty_images_without_entries_preserve_seed_hash() {
+ let mut sketch =
TupleSketchBuilder::new(DefaultUpdatePolicy::<i32>::default())
+ .seed(123)
+ .sampling_probability(1e-12)
+ .build()
+ .unwrap();
+ sketch.update("apple", 1);
+ let compact = sketch.compact(true);
+ assert!(!compact.is_empty());
+ assert_eq!(compact.num_retained(), 0);
+
+ let bytes = compact.serialize();
+ let restored = CompactTupleSketch::<i32>::deserialize_with_seed(&bytes,
123).unwrap();
+ assert!(!restored.is_empty());
+ assert_eq!(restored.theta64(), compact.theta64());
+ let err = CompactTupleSketch::<i32>::deserialize(&bytes).unwrap_err();
+ assert_eq!(err.kind(), ErrorKind::InvalidData);
+}
+
#[test]
fn round_trip_preserves_summaries() {
let mut sketch =
TupleSketchBuilder::new(DefaultUpdatePolicy::<u64>::default())
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
