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 292000d refactor: harden library usability before 0.5.0 (#253)
292000d is described below
commit 292000dd636be3074cb73700539910b30cee26b1
Author: tison <[email protected]>
AuthorDate: Mon Aug 31 20:08:33 2026 +0800
refactor: harden library usability before 0.5.0 (#253)
---
CHANGELOG.md | 3 ++-
datasketches/src/common/num_std_dev.rs | 6 ++---
datasketches/src/frequencies/serialization.rs | 11 +++++++--
datasketches/src/frequencies/sketch.rs | 2 --
datasketches/src/req/iter.rs | 8 +++----
datasketches/src/req/sketch.rs | 27 ++++++++++++++++------
datasketches/src/tdigest/sketch.rs | 18 +++++++++++++++
tests-integration/tests/req_test/bounds.rs | 24 ++++++++++---------
tests-integration/tests/req_test/property.rs | 5 ++--
tests-integration/tests/req_test/structure.rs | 6 ++---
tests-integration/tests/serde_tests/frequencies.rs | 10 ++++++++
tests-integration/tests/serde_tests/req.rs | 5 ++++
12 files changed, 90 insertions(+), 35 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 3f1f1bc..153a92f 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -25,7 +25,7 @@ All significant changes to this project will be documented in
this file.
### New features
* `TDigest` can now be serialized and deserialized directly without converting
through `TDigestMut` at the call site.
-* Add Relative Error Quantiles (REQ) sketches behind the `req` feature,
including configurable high- or low-rank accuracy, rank, quantile, PMF, and CDF
queries, merging, totally ordered custom item types, the `ReqFloat` adapter for
non-NaN floating-point values, and C++/Java-compatible serialization.
+* Add Relative Error Quantiles (REQ) sketches behind the `req` feature,
including configurable high- or low-rank accuracy, rank, quantile, PMF, and CDF
queries, typed rank confidence bounds, merging, totally ordered custom item
types, the `ReqFloat` adapter for non-NaN floating-point values, and
C++/Java-compatible serialization.
### Performance improvements
@@ -38,6 +38,7 @@ All significant changes to this project will be documented in
this file.
* T-Digest CDF and PMF queries now accept an empty split-point slice and
return the single all-values bin instead of panicking.
* Bloom filter deserialization now rejects malformed images with inconsistent
counts or payload lengths, while valid images with a dirty cached count are
restored correctly.
* `FrequentItemsSketch` now enforces the cross-language map-size limit of
`2^30` consistently. Oversized construction returns `InvalidArgument`, and
malformed or oversized serialized images return `InvalidData` instead of
panicking or attempting excessive allocation.
+* `FrequentItemsSketch<String>` now rejects an encoded string length that
exceeds the remaining input before allocating the string buffer.
* T-Digest compression now supports `k = u16::MAX` without overflowing.
* T-Digest rejects truncated serialized payloads before allocating, and
updating a deserialized digest no longer allows its buffered state to grow
without bound.
* Compact HLL4 images now restore all register values correctly.
diff --git a/datasketches/src/common/num_std_dev.rs
b/datasketches/src/common/num_std_dev.rs
index 2aa908f..99ef21f 100644
--- a/datasketches/src/common/num_std_dev.rs
+++ b/datasketches/src/common/num_std_dev.rs
@@ -31,9 +31,9 @@ static DELTA_OF_NUM_STD_DEVS: [f64; 4] = [
/// Number of standard deviations for confidence bounds.
///
/// This enum specifies the number of standard deviations to use when computing
-/// upper and lower bounds for cardinality estimates. Higher values provide
wider
-/// confidence intervals with greater certainty that the true cardinality falls
-/// within the bounds.
+/// upper and lower bounds for sketch estimates. Higher values provide wider
+/// confidence intervals with greater certainty that the true value falls
within
+/// the bounds.
#[repr(u8)]
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum NumStdDev {
diff --git a/datasketches/src/frequencies/serialization.rs
b/datasketches/src/frequencies/serialization.rs
index f1f8f0c..5ef3bf2 100644
--- a/datasketches/src/frequencies/serialization.rs
+++ b/datasketches/src/frequencies/serialization.rs
@@ -56,9 +56,16 @@ impl FrequentItemValue for String {
fn deserialize_value(cursor: &mut SketchSlice<'_>) -> Result<Self, Error> {
let len = cursor.read_u32_le().map_err(|_| {
Error::insufficient_data("failed to read string item
length".to_string())
- })?;
+ })? as usize;
+
+ let remaining = cursor.remaining().len();
+ if len > remaining {
+ return Err(Error::insufficient_data(format!(
+ "string item length ({len}) exceeds the remaining {remaining}
bytes"
+ )));
+ }
- let mut slice = vec![0; len as usize];
+ let mut slice = vec![0; len];
cursor.read_exact(&mut slice).map_err(|_| {
Error::insufficient_data("failed to read string item
bytes".to_string())
})?;
diff --git a/datasketches/src/frequencies/sketch.rs
b/datasketches/src/frequencies/sketch.rs
index 7a52045..f96bc90 100644
--- a/datasketches/src/frequencies/sketch.rs
+++ b/datasketches/src/frequencies/sketch.rs
@@ -365,7 +365,6 @@ impl<T: Eq + Hash> FrequentItemsSketch<T> {
if count == 0 {
return;
}
- assert!(count > 0, "count may not be negative");
self.stream_weight += count;
self.hash_map.adjust_or_put_value(item, count);
self.maybe_resize_or_purge();
@@ -418,7 +417,6 @@ impl<T: Eq + Hash> FrequentItemsSketch<T> {
if count == 0 {
return;
}
- assert!(count > 0, "count may not be negative");
self.stream_weight += count;
self.hash_map.adjust_or_put_value_ref(item, count);
self.maybe_resize_or_purge();
diff --git a/datasketches/src/req/iter.rs b/datasketches/src/req/iter.rs
index ba5c0f3..b36c2f4 100644
--- a/datasketches/src/req/iter.rs
+++ b/datasketches/src/req/iter.rs
@@ -24,7 +24,7 @@ use crate::req::compactor::Compactor;
/// Provides access to all items in the sketch along with their weights,
/// which depend on the level of the compactor they're stored in.
///
-/// Zero-allocation implementation that works directly with slices.
+/// Items are borrowed from the sketch, so iteration does not clone or
allocate.
pub struct ReqSketchIterator<'a, T> {
compactors: &'a [Compactor<T>],
current_level: usize,
@@ -64,14 +64,14 @@ impl<'a, T: Clone + Ord> ReqSketchIterator<'a, T> {
}
}
-impl<T: Clone + Ord> Iterator for ReqSketchIterator<'_, T> {
- type Item = (T, u64);
+impl<'a, T: Clone + Ord> Iterator for ReqSketchIterator<'a, T> {
+ type Item = (&'a T, u64);
fn next(&mut self) -> Option<Self::Item> {
loop {
if let Some(ref mut level_iter) = self.current_level_iter {
if let Some(item) = level_iter.next() {
- return Some((item.clone(), self.current_weight));
+ return Some((item, self.current_weight));
}
}
diff --git a/datasketches/src/req/sketch.rs b/datasketches/src/req/sketch.rs
index af93c6c..5826ce3 100644
--- a/datasketches/src/req/sketch.rs
+++ b/datasketches/src/req/sketch.rs
@@ -21,6 +21,7 @@ use crate::codec::SketchBytes;
use crate::codec::SketchSlice;
use crate::codec::assert::insufficient_data;
use crate::codec::family::Family;
+use crate::common::NumStdDev;
use crate::error::Error;
use crate::req::DEFAULT_K;
use crate::req::INITIAL_SECTIONS_PER_COMPACTOR;
@@ -351,25 +352,25 @@ where
Ok(())
}
- /// Returns the lower bound for the rank of a quantile at `num_std_dev`
confidence.
- pub fn rank_lower_bound(&self, rank: f64, num_std_dev: u8) -> f64 {
+ /// Returns the lower bound for the normalized `rank` at the requested
confidence level.
+ pub fn rank_lower_bound(&self, rank: f64, num_std_dev: NumStdDev) -> f64 {
self.compute_rank_lower_bound(
self.k,
self.compactors.len() as u8,
rank,
- num_std_dev,
+ num_std_dev.as_u8(),
self.n,
matches!(self.rank_accuracy, RankAccuracy::HighRank),
)
}
- /// Returns the upper bound for the rank of a quantile at `num_std_dev`
confidence.
- pub fn rank_upper_bound(&self, rank: f64, num_std_dev: u8) -> f64 {
+ /// Returns the upper bound for the normalized `rank` at the requested
confidence level.
+ pub fn rank_upper_bound(&self, rank: f64, num_std_dev: NumStdDev) -> f64 {
self.compute_rank_upper_bound(
self.k,
self.compactors.len() as u8,
rank,
- num_std_dev,
+ num_std_dev.as_u8(),
self.n,
matches!(self.rank_accuracy, RankAccuracy::HighRank),
)
@@ -689,9 +690,21 @@ where
}
}
- if n == 0 || min_item.is_none() || max_item.is_none() {
+ if n == 0 {
return Err(Error::deserial("non-empty REQ sketch contains no
items"));
}
+ let (Some(min), Some(max)) = (&min_item, &max_item) else {
+ return Err(Error::deserial("non-empty REQ sketch contains no
items"));
+ };
+ if compactors
+ .iter()
+ .flat_map(Compactor::iter)
+ .any(|item| item < min || item > max)
+ {
+ return Err(Error::deserial(
+ "REQ retained item falls outside the min/max range",
+ ));
+ }
let expected_raw_items = num_levels == 1 && n <= RAW_ITEMS_THRESHOLD;
if raw_items != expected_raw_items {
diff --git a/datasketches/src/tdigest/sketch.rs
b/datasketches/src/tdigest/sketch.rs
index b70ce51..f55c426 100644
--- a/datasketches/src/tdigest/sketch.rs
+++ b/datasketches/src/tdigest/sketch.rs
@@ -384,6 +384,11 @@ impl TDigestMut {
/// Returns the cumulative distribution approximation described by
[`TDigest::cdf`].
///
+ /// # Panics
+ ///
+ /// Panics if `split_points` is not unique, not monotonically increasing,
or contains `NaN`
+ /// values.
+ ///
/// # Examples
///
/// ```
@@ -408,6 +413,11 @@ impl TDigestMut {
/// Returns the probability mass approximation described by
[`TDigest::pmf`].
///
+ /// # Panics
+ ///
+ /// Panics if `split_points` is not unique, not monotonically increasing,
or contains `NaN`
+ /// values.
+ ///
/// # Examples
///
/// ```
@@ -432,6 +442,10 @@ impl TDigestMut {
/// Returns the normalized rank described by [`TDigest::rank`].
///
+ /// # Panics
+ ///
+ /// Panics if `value` is `NaN`.
+ ///
/// # Examples
///
/// ```
@@ -466,6 +480,10 @@ impl TDigestMut {
/// Returns the quantile described by [`TDigest::quantile`].
///
+ /// # Panics
+ ///
+ /// Panics if `rank` is outside `[0.0, 1.0]`.
+ ///
/// # Examples
///
/// ```
diff --git a/tests-integration/tests/req_test/bounds.rs
b/tests-integration/tests/req_test/bounds.rs
index b89b743..5caab94 100644
--- a/tests-integration/tests/req_test/bounds.rs
+++ b/tests-integration/tests/req_test/bounds.rs
@@ -17,6 +17,7 @@
//! Rank error bounds and sigma coverage for ReqSketch.
+use datasketches::common::NumStdDev;
use datasketches::error::Error;
use datasketches::req::RankAccuracy;
use datasketches::req::ReqSketch;
@@ -39,7 +40,8 @@ fn bounds_are_nested_and_in_unit_interval() {
}
for rank in [0.01, 0.05, 0.1, 0.25, 0.5, 0.75, 0.9, 0.95, 0.99, 0.999] {
- let bounds: Vec<(f64, f64)> = (1..=3u8)
+ let bounds: Vec<(f64, f64)> = [NumStdDev::One, NumStdDev::Two,
NumStdDev::Three]
+ .into_iter()
.map(|sigma| {
(
sketch.rank_lower_bound(rank, sigma),
@@ -76,8 +78,8 @@ fn theoretical_error_bounds_cover_uniform_quantiles() ->
Result<(), Error> {
] {
let true_quantile = req_f64(rank * (n - 1) as f64);
let estimated_rank = sketch.rank(&true_quantile,
SearchCriteria::Inclusive)?;
- let lower = sketch.rank_lower_bound(rank, 3);
- let upper = sketch.rank_upper_bound(rank, 3);
+ let lower = sketch.rank_lower_bound(rank, NumStdDev::Three);
+ let upper = sketch.rank_upper_bound(rank, NumStdDev::Three);
assert_that!(estimated_rank, all!(ge(lower), le(upper)), "rank:
{rank}");
}
@@ -95,10 +97,10 @@ fn hra_and_lra_bounds_are_tighter_at_their_target_end() ->
Result<(), Error> {
lra.update(req_f64(i as f64));
}
- let hra_error =
- (rank - hra.rank_lower_bound(rank,
2)).max(hra.rank_upper_bound(rank, 2) - rank);
- let lra_error =
- (rank - lra.rank_lower_bound(rank,
2)).max(lra.rank_upper_bound(rank, 2) - rank);
+ let hra_error = (rank - hra.rank_lower_bound(rank, NumStdDev::Two))
+ .max(hra.rank_upper_bound(rank, NumStdDev::Two) - rank);
+ let lra_error = (rank - lra.rank_lower_bound(rank, NumStdDev::Two))
+ .max(lra.rank_upper_bound(rank, NumStdDev::Two) - rank);
if rank >= 0.75 {
assert_that!(hra_error, le(lra_error));
@@ -121,8 +123,8 @@ fn exact_mode_bounds_are_tight() {
assert!(!sketch.is_estimation_mode());
for rank in [0.1, 0.25, 0.5, 0.75, 0.9] {
- let lower = sketch.rank_lower_bound(rank, 2);
- let upper = sketch.rank_upper_bound(rank, 2);
+ let lower = sketch.rank_lower_bound(rank, NumStdDev::Two);
+ let upper = sketch.rank_upper_bound(rank, NumStdDev::Two);
assert_that!((upper - lower) / 2.0, lt(0.05));
}
}
@@ -156,8 +158,8 @@ fn high_rank_accuracy_matches_tight_thresholds() {
}
for rank in [0.9, 0.99, 0.999] {
- let lower = sketch.rank_lower_bound(rank, 3);
- let upper = sketch.rank_upper_bound(rank, 3);
+ let lower = sketch.rank_lower_bound(rank, NumStdDev::Three);
+ let upper = sketch.rank_upper_bound(rank, NumStdDev::Three);
assert_that!(rank, all!(ge(lower), le(upper)));
}
}
diff --git a/tests-integration/tests/req_test/property.rs
b/tests-integration/tests/req_test/property.rs
index e993c4d..9df8c2c 100644
--- a/tests-integration/tests/req_test/property.rs
+++ b/tests-integration/tests/req_test/property.rs
@@ -17,6 +17,7 @@
//! Property-based ReqSketch tests.
+use datasketches::common::NumStdDev;
use datasketches::req::ReqSketch;
use datasketches::req::SearchCriteria;
use quickcheck::Gen;
@@ -56,8 +57,8 @@ fn prop_quantile_rank_consistency() {
// interval for the target rank (plus a small cushion for snapping
to a
// stored item). This scales with k and n, unlike a fixed slack,
so it
// actually constrains the result instead of always passing.
- let lower = sketch.rank_lower_bound(rank, 3) - 0.02;
- let upper = sketch.rank_upper_bound(rank, 3) + 0.02;
+ let lower = sketch.rank_lower_bound(rank, NumStdDev::Three) - 0.02;
+ let upper = sketch.rank_upper_bound(rank, NumStdDev::Three) + 0.02;
assert!(
(lower..=upper).contains(&recovered),
"rank {rank} -> quantile {quantile} -> recovered {recovered},
expected within [{lower:.4}, {upper:.4}]"
diff --git a/tests-integration/tests/req_test/structure.rs
b/tests-integration/tests/req_test/structure.rs
index e14cd79..8eff732 100644
--- a/tests-integration/tests/req_test/structure.rs
+++ b/tests-integration/tests/req_test/structure.rs
@@ -41,8 +41,8 @@ fn iterator_weights_sum_to_n_and_items_are_in_range() {
for (item, weight) in sketch.iter() {
assert_that!(weight, ge(1));
- assert_that!(item, ge(*sketch.min_item().expect("non-empty sketch")));
- assert_that!(item, le(*sketch.max_item().expect("non-empty sketch")));
+ assert_that!(*item, ge(*sketch.min_item().expect("non-empty sketch")));
+ assert_that!(*item, le(*sketch.max_item().expect("non-empty sketch")));
}
}
@@ -54,7 +54,7 @@ fn small_sketch_iterator_reports_unit_weights() {
sketch.update(req_f64(i as f64));
}
- let items: Vec<(ReqF64, u64)> = sketch.iter().collect();
+ let items: Vec<(&ReqF64, u64)> = sketch.iter().collect();
assert_eq!(items.len(), 10);
let weights: Vec<_> = items.iter().map(|&(_, weight)| weight).collect();
assert_that!(weights, each(eq(&1)));
diff --git a/tests-integration/tests/serde_tests/frequencies.rs
b/tests-integration/tests/serde_tests/frequencies.rs
index 6801b57..71bd62c 100644
--- a/tests-integration/tests/serde_tests/frequencies.rs
+++ b/tests-integration/tests/serde_tests/frequencies.rs
@@ -78,6 +78,16 @@ fn test_items_round_trip() {
assert_eq!(restored.maximum_error(), sketch.maximum_error());
}
+#[test]
+fn test_string_deserialize_rejects_length_larger_than_input() {
+ let bytes = 1024u32.to_le_bytes();
+ let mut cursor = SketchSlice::new(&bytes);
+
+ let error = String::deserialize_value(&mut cursor).unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::InvalidData);
+ assert_that!(error.message(), contains_substring("exceeds the remaining"));
+}
+
#[test]
fn test_non_clone_item_round_trip() {
let mut sketch =
FrequentItemsSketch::<NonCloneSerializableItem>::new(32).unwrap();
diff --git a/tests-integration/tests/serde_tests/req.rs
b/tests-integration/tests/serde_tests/req.rs
index 0138664..b097ed0 100644
--- a/tests-integration/tests/serde_tests/req.rs
+++ b/tests-integration/tests/serde_tests/req.rs
@@ -462,6 +462,11 @@ fn deserialize_rejects_invalid_extrema_and_raw_nan() {
reversed[20..24].copy_from_slice(&1.0f32.to_le_bytes());
assert_invalid_data(&reversed);
+ let mut extrema_exclude_retained_items = estimation_image(12, 1_000);
+
extrema_exclude_retained_items[16..20].copy_from_slice(&500.0f32.to_le_bytes());
+
extrema_exclude_retained_items[20..24].copy_from_slice(&500.0f32.to_le_bytes());
+ assert_invalid_data(&extrema_exclude_retained_items);
+
let mut raw_nan = vec![2u8, 1, 17, 8 | 16, 12, 0, 1, 1];
raw_nan.extend_from_slice(&f32::NAN.to_le_bytes());
assert_invalid_data(&raw_nan);
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
