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 e7d151e  refactor(req): use usize for in-memory counts and fix merge 
compaction (#354)
e7d151e is described below

commit e7d151e0925ca64410875194ae21fbfdcdb409c9
Author: tison <[email protected]>
AuthorDate: Thu Nov 12 22:16:11 2026 +0800

    refactor(req): use usize for in-memory counts and fix merge compaction 
(#354)
---
 CHANGELOG.md                               |  3 ++
 datasketches/src/req/compactor.rs          | 46 ++++++++++++++++--------------
 datasketches/src/req/mod.rs                |  4 +--
 datasketches/src/req/serialization.rs      |  7 +++--
 datasketches/src/req/sketch.rs             | 28 +++++++++---------
 tests-integration/tests/req_test/core.rs   |  2 +-
 tests-integration/tests/req_test/merge.rs  | 29 +++++++++++++++++++
 tests-integration/tests/serde_tests/req.rs | 24 +++++++++++++---
 8 files changed, 99 insertions(+), 44 deletions(-)

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 2c05111..b4839ae 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -11,6 +11,7 @@ All significant changes to this project will be documented in 
this file.
 * `CpcSketch::max_serialized_bytes` and `ReqSketch::serialized_size_bytes` are 
removed; serialize the sketch and inspect `len()` on the returned byte buffer 
when the encoded size is needed.
 * `ThetaJaccardSimilarity::compute` and `TupleJaccardSimilarity::compute` now 
return `datasketches::common::JaccardSimilarity` instead of 
`datasketches::thetacommon::JaccardSimilarity`, and `datasketches::thetacommon` 
is no longer part of the public API.
 * `FrequentItemsSketch::update_with_count` and 
`FrequentItemsSketch::update_with_count_ref` are renamed to 
`update_with_weight` and `update_with_weight_ref` to match weighted update 
naming across the crate.
+* `ReqSketch::num_retained` now returns `usize` instead of `u32`, matching 
`KllSketch`, `ThetaSketch`, and `TupleSketch`.
 
 ### New features
 
@@ -35,6 +36,8 @@ All significant changes to this project will be documented in 
this file.
 
 ### Bug fixes
 
+* `ReqSketch::merge` now cascades compaction across newly grown levels when a 
merged sketch overflows the top compactor's nominal capacity.
+* `ReqSketch::deserialize` now returns `InvalidData` for out-of-range or 
non-finite compactor `section_size_raw` values instead of overflowing 
section-size rounding.
 * `ThetaJaccardSimilarity` and `TupleJaccardSimilarity` now return 
`InvalidArgument` instead of `InvalidData` when a non-empty input sketch's seed 
hash does not match the configured seed.
 
 ## v0.6.0 (2026-10-29)
diff --git a/datasketches/src/req/compactor.rs 
b/datasketches/src/req/compactor.rs
index c6f6461..d2f8c92 100644
--- a/datasketches/src/req/compactor.rs
+++ b/datasketches/src/req/compactor.rs
@@ -19,6 +19,9 @@
 //!
 //! Each level compacts a selected range, retaining one item from each pair at 
twice the weight.
 
+use crate::codec::SketchBytes;
+use crate::codec::SketchSlice;
+use crate::codec::assert::insufficient_data;
 use crate::common::random::random_bit;
 use crate::error::Error;
 use crate::req::INITIAL_SECTIONS_PER_COMPACTOR;
@@ -38,7 +41,7 @@ pub struct Compactor<T> {
     /// Determines which sections are compacted and when their count doubles.
     state: u64,
     scratch_buffer: Vec<T>,
-    section_size: u32,
+    section_size: usize,
     num_sections: u8,
     lg_weight: u8,
     rank_accuracy: RankAccuracy,
@@ -57,7 +60,7 @@ where
         let section_size = nearest_even_section_size(section_size_raw);
         let num_sections = INITIAL_SECTIONS_PER_COMPACTOR;
 
-        let nominal: usize = (2 * section_size * num_sections as u32) as usize;
+        let nominal = 2 * section_size * usize::from(num_sections);
 
         Self {
             items: Vec::with_capacity(nominal),
@@ -76,13 +79,13 @@ where
     }
 
     /// Returns the number of items currently in this compactor.
-    pub fn num_items(&self) -> u32 {
-        self.items.len() as u32
+    pub fn num_items(&self) -> usize {
+        self.items.len()
     }
 
     /// Returns the nominal capacity of this compactor.
-    pub fn nominal_capacity(&self) -> u32 {
-        2 * self.section_size * self.num_sections as u32
+    pub fn nominal_capacity(&self) -> usize {
+        2 * self.section_size * usize::from(self.num_sections)
     }
 
     /// Returns whether the items are currently sorted.
@@ -253,7 +256,7 @@ where
         let section_size_raw = self.section_size_raw / 
std::f32::consts::SQRT_2;
         let section_size = nearest_even_section_size(section_size_raw);
 
-        if self.state >= threshold && section_size >= u32::from(MIN_K) {
+        if self.state >= threshold && section_size >= usize::from(MIN_K) {
             self.section_size_raw = section_size_raw;
             self.section_size = section_size;
             self.num_sections = num_sections;
@@ -264,9 +267,9 @@ where
 
     #[inline(always)]
     fn compute_compaction_range(&self, secs_to_compact: u8) -> (usize, usize) {
-        let nom_capacity = self.nominal_capacity() as usize;
-        let mut non_compact = nom_capacity / 2
-            + (self.num_sections - secs_to_compact) as usize * 
self.section_size as usize;
+        let nom_capacity = self.nominal_capacity();
+        let mut non_compact =
+            nom_capacity / 2 + usize::from(self.num_sections - 
secs_to_compact) * self.section_size;
 
         // Preserve an extra item when needed to make the compacted range even.
         if self.items.len() >= non_compact && ((self.items.len() - 
non_compact) & 1) == 1 {
@@ -283,16 +286,18 @@ where
     }
 
     /// Serialize this compactor (preamble + items) into the byte buffer.
-    pub fn serialize_into(&self, bytes: &mut crate::codec::SketchBytes)
+    pub fn serialize_into(&self, bytes: &mut SketchBytes)
     where
         T: ReqValue,
     {
+        let num_items =
+            u32::try_from(self.num_items()).expect("REQ compactor item count 
exceeds u32::MAX");
         bytes.write_u64_le(self.state);
         bytes.write_f32_le(self.section_size_raw);
         bytes.write_u8(self.lg_weight);
         bytes.write_u8(self.num_sections);
         bytes.write_u16_le(0); // padding
-        bytes.write_u32_le(self.num_items());
+        bytes.write_u32_le(num_items);
         for item in self.iter() {
             item.serialize_value(bytes);
         }
@@ -300,7 +305,7 @@ where
 
     /// Deserialize a compactor (preamble + items) from the byte cursor.
     pub fn deserialize(
-        cursor: &mut crate::codec::SketchSlice<'_>,
+        cursor: &mut SketchSlice<'_>,
         k: u16,
         expected_lg_weight: u8,
         rank_accuracy: RankAccuracy,
@@ -309,7 +314,6 @@ where
     where
         T: ReqValue,
     {
-        use crate::codec::assert::insufficient_data;
         let state = cursor
             .read_u64_le()
             .map_err(insufficient_data("compactor.state"))?;
@@ -325,9 +329,12 @@ where
         let _padding = cursor
             .read_u16_le()
             .map_err(insufficient_data("compactor.padding"))?;
-        let num_items = cursor
-            .read_u32_le()
-            .map_err(insufficient_data("compactor.num_items"))?;
+        let num_items = usize::try_from(
+            cursor
+                .read_u32_le()
+                .map_err(insufficient_data("compactor.num_items"))?,
+        )
+        .map_err(|_| Error::deserial("REQ compactor item count overflows 
usize"))?;
 
         validate_compactor_state(
             k,
@@ -342,7 +349,7 @@ where
         // a multi-gigabyte reservation before the per-item reads below fail. 
The buffer
         // holds at most `remaining` more items (each item is ≥ 1 byte), so 
cap the
         // pre-allocation there; `push` still grows the Vec as the validated 
data needs.
-        let capacity = (num_items as usize).min(cursor.remaining().len());
+        let capacity = num_items.min(cursor.remaining().len());
         let mut items = Vec::with_capacity(capacity);
         for _ in 0..num_items {
             items.push(T::deserialize_value(cursor)?);
@@ -476,9 +483,6 @@ mod tests {
 
     #[test]
     fn compactor_serialization_round_trip() {
-        use crate::codec::SketchBytes;
-        use crate::codec::SketchSlice;
-
         let mut c: Compactor<ReqFloat<f32>> = Compactor::new(0, 12, 
RankAccuracy::HighRank);
         for i in 0..30 {
             c.append(ReqFloat::<f32>::new(i as f32).unwrap());
diff --git a/datasketches/src/req/mod.rs b/datasketches/src/req/mod.rs
index 91bc2ba..ff0ed71 100644
--- a/datasketches/src/req/mod.rs
+++ b/datasketches/src/req/mod.rs
@@ -83,6 +83,6 @@ pub enum RankAccuracy {
 /// determine its capacity and compaction range; the count doubles as its 
state grows.
 const INITIAL_SECTIONS_PER_COMPACTOR: u8 = 3;
 
-fn nearest_even_section_size(value: f32) -> u32 {
-    ((value / 2.0).round() as u32) << 1
+fn nearest_even_section_size(value: f32) -> usize {
+    ((value / 2.0).round() as usize) << 1
 }
diff --git a/datasketches/src/req/serialization.rs 
b/datasketches/src/req/serialization.rs
index c4d1f23..bdc0cb4 100644
--- a/datasketches/src/req/serialization.rs
+++ b/datasketches/src/req/serialization.rs
@@ -72,9 +72,10 @@ pub fn validate_compactor_state(
             "REQ compactor lg_weight {lg_weight} does not match level 
{expected_lg_weight}"
         )));
     }
-    let section_size = nearest_even_section_size(section_size_raw);
-    if !section_size_raw.is_finite()
-        || !(u32::from(MIN_K)..=u32::from(k)).contains(&section_size)
+    let max_raw = f32::from(k) + 2.0;
+    if !(0.0..=max_raw).contains(&section_size_raw)
+        || !(usize::from(MIN_K)..=usize::from(k))
+            .contains(&nearest_even_section_size(section_size_raw))
         || !has_reachable_section_count(state, num_sections)
     {
         return Err(Error::deserial(format!(
diff --git a/datasketches/src/req/sketch.rs b/datasketches/src/req/sketch.rs
index abc240e..b9b4c09 100644
--- a/datasketches/src/req/sketch.rs
+++ b/datasketches/src/req/sketch.rs
@@ -54,8 +54,8 @@ pub struct ReqSketch<T> {
     k: u16,
     rank_accuracy: RankAccuracy,
     n: u64,
-    max_nom_size: u32,
-    num_retained: u32,
+    max_nom_size: usize,
+    num_retained: usize,
     compactors: Vec<Compactor<T>>,
     promotion_buf: Vec<T>,
     min_item: Option<T>,
@@ -136,7 +136,7 @@ where
     }
 
     /// Returns the number of items currently stored across all compactors.
-    pub fn num_retained(&self) -> u32 {
+    pub fn num_retained(&self) -> usize {
         self.num_retained
     }
 
@@ -324,7 +324,7 @@ where
     /// queries at ranks strictly between `0.0` and `1.0`, or repeated 
[`Self::pmf`]/[`Self::cdf`]
     /// queries.
     pub fn sorted_view(&self) -> SortedView<T> {
-        let mut weighted_items = Vec::with_capacity(self.num_retained as 
usize);
+        let mut weighted_items = Vec::with_capacity(self.num_retained);
         for compactor in &self.compactors {
             let weight = compactor.weight();
             for item in compactor.iter() {
@@ -738,7 +738,8 @@ where
         if num_levels == 1 {
             // Recover n / min / max from level 0 (these aren't in the 
preamble for exact mode).
             let level0 = &compactors[0];
-            n = level0.num_items() as u64;
+            n = u64::try_from(level0.num_items())
+                .map_err(|_| Error::deserial("REQ level 0 item count overflows 
u64"))?;
             let mut iter = level0.iter();
             if let Some(first) = iter.next() {
                 let mut mn = first.clone();
@@ -782,14 +783,13 @@ where
         let (retained_count, nominal_capacity, weighted_count) = compactors
             .iter()
             .try_fold(
-                (0u32, 0u32, 0u64),
+                (0usize, 0usize, 0u64),
                 |(retained, capacity, weighted), compactor| {
+                    let level_items = 
u64::try_from(compactor.num_items()).ok()?;
                     Some((
                         retained.checked_add(compactor.num_items())?,
                         capacity.checked_add(compactor.nominal_capacity())?,
-                        weighted.checked_add(
-                            (compactor.num_items() as 
u64).checked_mul(compactor.weight())?,
-                        )?,
+                        
weighted.checked_add(level_items.checked_mul(compactor.weight())?)?,
                     ))
                 },
             )
@@ -822,7 +822,7 @@ where
             max_nom_size: 0,
             num_retained: 0,
             compactors: vec![],
-            promotion_buf: Vec::with_capacity(k as usize),
+            promotion_buf: Vec::with_capacity(usize::from(k)),
             min_item: None,
             max_item: None,
         };
@@ -840,7 +840,8 @@ where
     }
 
     fn compress(&mut self) {
-        for h in 0..self.compactors.len() {
+        let mut h = 0;
+        while h < self.compactors.len() {
             if self.compactors[h].num_items() >= 
self.compactors[h].nominal_capacity() {
                 if h + 1 >= self.compactors.len() {
                     self.grow();
@@ -850,10 +851,11 @@ where
                     self.compactors[h + 1].sort();
                     self.compactors[h + 1].merge_sorted(&self.promotion_buf);
                 }
-                self.update_max_nom_size();
-                self.update_num_retained();
             }
+            h += 1;
         }
+        self.update_max_nom_size();
+        self.update_num_retained();
     }
 
     fn update_max_nom_size(&mut self) {
diff --git a/tests-integration/tests/req_test/core.rs 
b/tests-integration/tests/req_test/core.rs
index 1a3622e..876c8c8 100644
--- a/tests-integration/tests/req_test/core.rs
+++ b/tests-integration/tests/req_test/core.rs
@@ -184,7 +184,7 @@ fn estimation_mode_compresses_and_keeps_min_max() {
     assert!(!sketch.is_empty());
     assert!(sketch.is_estimation_mode());
     assert_eq!(sketch.n(), n);
-    assert_that!(sketch.num_retained(), lt(n as u32));
+    assert_that!(sketch.num_retained(), lt(n as usize));
     assert_eq!(sketch.min_item().copied(), Some(req_f64(0.0)));
     assert_eq!(sketch.max_item().copied(), Some(req_f64((n - 1) as f64)));
 
diff --git a/tests-integration/tests/req_test/merge.rs 
b/tests-integration/tests/req_test/merge.rs
index d24d6e7..8de74c8 100644
--- a/tests-integration/tests/req_test/merge.rs
+++ b/tests-integration/tests/req_test/merge.rs
@@ -23,6 +23,7 @@ use datasketches::req::ReqSketch;
 use googletest::assert_that;
 use googletest::prelude::anything;
 use googletest::prelude::err;
+use googletest::prelude::lt;
 use googletest::prelude::near;
 
 use super::ReqF64;
@@ -132,3 +133,31 @@ fn many_small_merges_preserve_count_bounds_and_median() {
         .expect("the sketch is non-empty");
     assert_that!(*median, near(4999.5, 500.0));
 }
+
+#[test]
+fn merge_larger_k_into_smaller_k_cascades_compaction_across_new_levels() {
+    let mut target: ReqSketch<ReqF64> = ReqSketch::new(4, 
RankAccuracy::HighRank).unwrap();
+    let mut source: ReqSketch<ReqF64> = ReqSketch::new(200, 
RankAccuracy::HighRank).unwrap();
+
+    // 500 items fit in level 0 of k=200 (nominal capacity 1200), so source 
has 1 level.
+    // Merging into k=4 (level nominal capacity 24) promotes 240 items into a 
newly grown
+    // level 1, which must cascade further compactions across newly grown 
upper levels.
+    for i in 0..500 {
+        source.update(req_f64(i as f64));
+    }
+    assert!(!source.is_estimation_mode());
+
+    target.merge(&source).expect("merge should succeed");
+
+    assert_eq!(target.n(), 500);
+    assert!(target.is_estimation_mode());
+    assert_that!(target.num_retained(), lt(120));
+    let weighted_sum: u64 = target.iter().map(|(_, weight)| weight).sum();
+    assert_eq!(weighted_sum, 500);
+    assert_eq!(target.min_item().copied(), Some(req_f64(0.0)));
+    assert_eq!(target.max_item().copied(), Some(req_f64(499.0)));
+
+    let round_trip = 
ReqSketch::<ReqF64>::deserialize(&target.serialize()).unwrap();
+    assert_eq!(round_trip.n(), target.n());
+    assert_eq!(round_trip.num_retained(), target.num_retained());
+}
diff --git a/tests-integration/tests/serde_tests/req.rs 
b/tests-integration/tests/serde_tests/req.rs
index 7c14763..fa1fc1d 100644
--- a/tests-integration/tests/serde_tests/req.rs
+++ b/tests-integration/tests/serde_tests/req.rs
@@ -335,11 +335,27 @@ fn deserialize_rejects_inconsistent_weighted_count() {
 
 #[test]
 fn deserialize_rejects_unreachable_section_configuration() {
-    let mut invalid_raw = exact_image(12, &[1.0, 2.0, 3.0, 4.0, 5.0]);
-    invalid_raw[EXACT_COMPACTOR_OFFSET + SECTION_SIZE_RAW_OFFSET
+    for raw in [
+        0.0f32,
+        -6.0,
+        f32::NAN,
+        f32::INFINITY,
+        f32::NEG_INFINITY,
+        f32::MAX,
+    ] {
+        let mut invalid_raw = exact_image(12, &[1.0, 2.0, 3.0, 4.0, 5.0]);
+        invalid_raw[EXACT_COMPACTOR_OFFSET + SECTION_SIZE_RAW_OFFSET
+            ..EXACT_COMPACTOR_OFFSET + SECTION_SIZE_RAW_OFFSET + 4]
+            .copy_from_slice(&raw.to_le_bytes());
+        assert_invalid_data(&invalid_raw);
+    }
+
+    // (4_294_967_808.0 / 2.0) = 0x8000_0100; shifting left in u32 would wrap 
to 512 == k.
+    let mut wrapping_raw = exact_image(512, &[1.0, 2.0, 3.0, 4.0, 5.0]);
+    wrapping_raw[EXACT_COMPACTOR_OFFSET + SECTION_SIZE_RAW_OFFSET
         ..EXACT_COMPACTOR_OFFSET + SECTION_SIZE_RAW_OFFSET + 4]
-        .copy_from_slice(&0.0f32.to_le_bytes());
-    assert_invalid_data(&invalid_raw);
+        .copy_from_slice(&4_294_967_808.0f32.to_le_bytes());
+    assert_invalid_data(&wrapping_raw);
 
     let mut invalid_sections = exact_image(12, &[1.0, 2.0, 3.0, 4.0, 5.0]);
     invalid_sections[EXACT_COMPACTOR_OFFSET + NUM_SECTIONS_OFFSET] = 6;


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to