tisonkun commented on PR #204: URL: https://github.com/apache/datasketches-rust/pull/204#issuecomment-5345104139
Glanced at the surface and commented above. Below is a review comment from Codex. I'll dive into implementation details later this week. And I think it's OK to merge a starting implementation and iterate later. But let's discuss existing items first to decide when to converge. [CODEX COMMENT STARTS] I found two correctness issues that I believe need to be fixed before this can be merged. 1. **`Compactor::merge` breaks the ordering invariant required by the wire format** In `datasketches/src/req/compactor.rs`, `Compactor::merge` appends the other compactor’s items and marks the result as unsorted. This is safe only while the sketch remains in memory, because `rank()` falls back to a linear scan. However, the REQ wire format stores a sorted flag only for level 0. Higher levels are implicitly required to be sorted, and `ReqSketch::deserialize` consequently marks every level above 0 as sorted. A merged sketch can therefore serialize unsorted higher-level items, which are then binary-searched as if they were sorted after deserialization. I reproduced this with two HRA sketches using `k = 12`, containing `1000..1072` and `0..72`. After merging the latter into the former and performing a serialize/deserialize round trip, the restored sketch returned different results from its sorted view for the same rank query. In one run: ```text restored.rank(0.0, Inclusive) = 0.097222... restored.sorted_view().rank(0.0, Inclusive) = 0.013888... ``` This also means a merged image produced by Rust may be interpreted incorrectly by Java or C++. Both reference implementations preserve ordering during compactor merge by sorting and performing an ordered merge. I suggest doing the same here, including validating that the two compactors have the same `lg_weight`. Please also add a regression test that: - builds two estimation-mode sketches with reversed/disjoint value ranges; - merges them; - serializes and deserializes the result; and - verifies that direct rank queries remain equal to sorted-view rank queries. 2. **Deserialization accepts impossible compactor states that later panic or violate public API contracts** The current validation checks `section_size_raw` and requires `lg_weight < 64`, but it does not validate several structural invariants controlled by the serialized input. Two concrete examples: - An image with `num_sections = 0` is accepted. Calling `merge()` on the resulting sketch then panics in `ensure_enough_sections()` when evaluating `num_sections - 1`. - A single-level image with `lg_weight = 63` and `n = 1` is accepted. Its inclusive rank query returns approximately `9.22e18`, despite `rank()` promising a result in `[0, 1]`. A malformed serialized image should not be able to create a sketch for which safe public operations panic or return impossible results. Before constructing the sketch, I suggest validating at least: - each compactor’s `lg_weight` equals its level index; - `num_sections`, `section_size_raw`, and `state` form a valid, non-zero compactor configuration; - the number of levels is representable by the `u64` weight model; - `sum(num_items * 2^level) == n`; - levels declared as sorted are actually sorted; and - extrema and retained values are consistent and contain no invalid NaN state. The relevant arithmetic should also use checked operations. Since these failures originate from malformed serialized input, they should return `ErrorKind::InvalidData`, not `InvalidArgument`. Once these two issues are addressed, the existing algorithm and cross-language compatibility coverage will be on much firmer ground. [CODEX COMMENT END] -- 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]
