You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@datasketches.apache.org by "cestercian (via GitHub)" <gi...@apache.org> on 2026/08/25 08:09:11 UTC
[PR] fix: reject invalid REQ compactor states on deserialize (datasketches-rust)
cestercian opened a new pull request, #221:
URL: https://github.com/apache/datasketches-rust/pull/221
Fixes #218
## Summary
REQ deserialization accepted compactor states that a valid sketch cannot produce. Those images later panicked in `ReqSketch::merge` or returned a `rank()` outside `[0.0, 1.0]`. Deserialize now rejects those states with `ErrorKind::InvalidData`.
## Changes Made
- `Compactor::deserialize` rejects `num_sections` values that the REQ doubling schedule cannot produce, including `num_sections = 0`. Malformed wire fields now return `ErrorKind::InvalidData` instead of `InvalidArgument`.
- `ReqSketch::deserialize` requires each compactor's `lg_weight` to equal its enclosing level index.
- `ReqSketch::deserialize` uses checked arithmetic for the retained weighted count and requires it to equal serialized `n`.
- Regression tests in `datasketches/tests/serde_tests/req.rs` cover the two malformed single-level images from the issue.
## Related Issue
https://github.com/apache/datasketches-rust/issues/218
## Testing Steps
1. `cargo x test` (from the repo root; run `cargo x prepare-testdata` first if serialization fixtures are missing)
2. `cargo x lint`
3. Confirm the new serde tests fail the two crafted images with `ErrorKind::InvalidData`:
- single-level image with `num_sections = 0`
- single-level image with level-0 `lg_weight = 63` and one item
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] fix: reject invalid REQ compactor states on deserialize (datasketches-rust)
Posted by "jeffoodchain (via GitHub)" <gi...@apache.org>.
jeffoodchain commented on code in PR #221:
URL: https://github.com/apache/datasketches-rust/pull/221#discussion_r3851623114
##########
datasketches/src/req/sketch.rs:
##########
Review Comment:
I think there are some `Error::invalid_argument` needed to change to `Error::deserial` in this function.
##########
datasketches/src/req/sketch.rs:
##########
@@ -716,6 +729,19 @@ impl<T: ReqValue> ReqSketch<T> {
// --- Internal ---
+ fn retained_weighted_count(compactors: &[Compactor<T>]) -> Result<u64, Error> {
Review Comment:
I think maybe no need to extract this as a function since it is only used once.
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] fix: reject invalid REQ compactor states on deserialize (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun merged PR #221:
URL: https://github.com/apache/datasketches-rust/pull/221
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] fix: reject invalid REQ compactor states on deserialize (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on PR #221:
URL: https://github.com/apache/datasketches-rust/pull/221#issuecomment-5412347968
@cestercian I found and fixed one additional malformed-state path after the previous review: two individually accepted high compactor states could OR to `u64::MAX` during merge and then overflow on compaction.
The updated validation requires each compactor's history to fit within the serialized stream length (`state * 2 * level_weight <= n`, using checked arithmetic). This follows because every level compaction consumes at least two items at that level's weight, and `a | b <= a + b` preserves the bound across merges. The tests include both a finite inconsistent state and the complementary-state merge reproducer.
I also ran a fresh defect-first review of the complete merge diff against the C++/Java section-growth logic and found no remaining actionable issues. Could you review the latest diff end to end and flag any concerns or alternatives?
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] fix: reject invalid REQ compactor states on deserialize (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on PR #221:
URL: https://github.com/apache/datasketches-rust/pull/221#issuecomment-5408952625
Here is a suggested prompt for the coding agent. The key is to reason from the complete deserialized-state contract instead of patching each counterexample independently:
> Read `CONTRIBUTING.md` in full. Review the complete REQ construction, update, merge, serialize, and deserialize paths, plus the pinned C++/Java compatibility fixtures and reference implementations. Do not modify code yet.
>
> First, enumerate every invariant that holds for a `ReqSketch` produced through safe Rust APIs and serialization. For every wire-controlled field, identify all downstream operations that rely on it and the concrete failure caused by violating it. Cover at least: header/RAW_ITEMS consistency; level count and `lg_weight`; the reachable relationship among `k`, `state`, `section_size_raw`, and `num_sections`; actual ordering whenever `is_sorted` is true; NaN/value assumptions; weighted retained count versus `n`; retained count versus nominal capacity; min/max consistency; and arithmetic/allocation bounds.
>
> Then implement one coherent validation boundary that rejects malformed images with `ErrorKind::InvalidData` before constructing a usable sketch. Avoid validation rules based only on global numeric ranges when fields are derived from other serialized state. Preserve every valid C++/Java fixture and Rust round trip.
>
> Add focused regression tests that start from canonical valid images and mutate exactly one invariant. Include boundary and neighboring cases, not only the reported examples. In particular cover false sorted claims, `k`/section-schedule mismatches, nonzero invalid section counts, weighted-count mismatch and overflow, and retained count at/above capacity. Ensure each test asserts the intended validation branch and error kind.
>
> Keep the implementation small: share algorithm constants instead of duplicating them, use a test helper for repeated `InvalidData` assertions, and do not add a changelog entry because REQ is still unreleased. Run `cargo x prepare-testdata`, `cargo x check`, `cargo x test`, and `cargo x lint`, and report the invariant table, implementation choices, compatibility evidence, and command results.
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] fix: reject invalid REQ compactor states on deserialize (datasketches-rust)
Posted by "cestercian (via GitHub)" <gi...@apache.org>.
cestercian commented on PR #221:
URL: https://github.com/apache/datasketches-rust/pull/221#issuecomment-5410361308
@tisonkun thanks for the invariant-table prompt. Earlier revisions were follow-ups against individual counterexamples (the issue images, then `MIN_K` / capacity). This round used your prompt as written: enumerate the deserialized-state contract first, then one `InvalidData` boundary, with tests that start from a canonical five-item image and mutate one field.
Implementation was Cursor cloud agents on this contributor fork. Verification was `cargo x prepare-testdata`, `cargo x check`, `cargo x test`, and `cargo x lint` (`serde_tests` 101 passed, including the C++/Java REQ fixtures). Java `section_size_raw` can land 2 ULPs off the C++/Rust doubling-schedule replay, so that check keeps the reachable `(k, state, num_sections)` relation and tolerates that float noise so the pinned TCK images still load.
Happy to adjust the validation or the 2-ULP tolerance if you want it stricter.
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org