voonhous commented on code in PR #19414:
URL: https://github.com/apache/hudi/pull/19414#discussion_r3681516088
##########
hudi-io/src/main/java/org/apache/hudi/common/util/StringUtils.java:
##########
@@ -137,23 +137,30 @@ public static byte[] getUTF8Bytes(String str) {
* <p>Neither argument may be {@code null}; like {@link
String#compareTo(String)}, a {@code null}
* argument throws {@link NullPointerException}.
*
- * <p>Assumes well-formed UTF-16 input: {@code String#getBytes(UTF_8)}
replaces unpaired surrogates
- * with {@code '?'}, so strings differing only in unpaired surrogates
compare equal.
+ * <p>This comparison does not materialize the UTF-8 byte arrays. It
compares UTF-16 code units
+ * directly and handles supplementary characters specially to preserve UTF-8
byte order.
*
- * <p>Note: encodes both strings to UTF-8 on every call; for very large
sorts consider
- * pre-encoding keys to byte arrays once and comparing those.
+ * <p>Ported from Google Firebase Firestore's {@code compareUtf8Strings}.
Review Comment:
This method is a verbatim port of Apache 2.0 code that is Copyright 2018
Google LLC, but there is no entry for it in `LICENSE`. Hudi's `LICENSE` lists
every other borrowed snippet, down to single methods (Spark, SystemML,
Cassandra's `BufferedRandomAccessFile`, commons-lang3's `Pair`), and an
unattributed port can hold up a release vote. Please add a stanza in the
existing style, something like:
```
This product includes code from the Google Firebase Android SDK
* org.apache.hudi.common.util.StringUtils#compareUtf8Bytes ported from
com.google.firebase.firestore.util.Util#compareUtf8Strings
* Copyright 2018 Google LLC
* Home page: https://github.com/firebase/firebase-android-sdk
* License: https://www.apache.org/licenses/LICENSE-2.0
```
##########
hudi-io/src/main/java/org/apache/hudi/common/util/StringUtils.java:
##########
@@ -137,23 +137,30 @@ public static byte[] getUTF8Bytes(String str) {
* <p>Neither argument may be {@code null}; like {@link
String#compareTo(String)}, a {@code null}
* argument throws {@link NullPointerException}.
*
- * <p>Assumes well-formed UTF-16 input: {@code String#getBytes(UTF_8)}
replaces unpaired surrogates
- * with {@code '?'}, so strings differing only in unpaired surrogates
compare equal.
+ * <p>This comparison does not materialize the UTF-8 byte arrays. It
compares UTF-16 code units
+ * directly and handles supplementary characters specially to preserve UTF-8
byte order.
*
- * <p>Note: encodes both strings to UTF-8 on every call; for very large
sorts consider
- * pre-encoding keys to byte arrays once and comparing those.
+ * <p>Ported from Google Firebase Firestore's {@code compareUtf8Strings}.
*/
public static int compareUtf8Bytes(String s1, String s2) {
Review Comment:
Not a problem with this PR, just flagging it while we are looking at this
comparator. The RFC-103 LSM merge still compares record keys in UTF-16 order
while the sorted runs it merges are written in UTF-8 order through
`SortedKeyBasedFileGroupRecordBuffer`: `LsmFileGroupRecordIterator.java:476`
uses `getRecordKey().compareTo(...)` and
`LsmFileGroupReaderBasedMergeHandle.java:67` sorts with
`Comparator.comparing(HoodieRecord::getRecordKey)`. That code (`6170ac90527`)
predates #18941, so the sweep there missed it. Mixed orders in a k-way merge
mean same-key records from two runs can fail to collide for keys where UTF-8
and UTF-16 order differ (any supplementary character vs U+E000..U+FFFF), which
silently drops updates. I think this deserves a follow-up issue to swap both
sites to `UTF8_LEXICOGRAPHIC_COMPARATOR` with a non-ASCII key merge test.
Nothing to change in this PR.
##########
hudi-io/src/main/java/org/apache/hudi/common/util/StringUtils.java:
##########
@@ -137,23 +137,30 @@ public static byte[] getUTF8Bytes(String str) {
* <p>Neither argument may be {@code null}; like {@link
String#compareTo(String)}, a {@code null}
* argument throws {@link NullPointerException}.
*
- * <p>Assumes well-formed UTF-16 input: {@code String#getBytes(UTF_8)}
replaces unpaired surrogates
- * with {@code '?'}, so strings differing only in unpaired surrogates
compare equal.
+ * <p>This comparison does not materialize the UTF-8 byte arrays. It
compares UTF-16 code units
+ * directly and handles supplementary characters specially to preserve UTF-8
byte order.
Review Comment:
#18941 added a javadoc caveat about unpaired surrogates at a reviewer's
request, and this rewrite drops it exactly when it becomes load bearing. The
old code agreed with the on-disk bytes by construction, since it called the
same `getBytes`. The new code sorts a lone surrogate after every BMP character,
while the UTF-8 encoder writes it as `?` (0x3F). So `compareUtf8Bytes("\uD800",
"z") > 0` even though the stored bytes say less, and `HFileWriterImpl.append`
has no ascending-key check, so a divergent key would be written silently.
Reachability is narrow (Spark, Avro and Flink all decode UTF-8, which can only
produce U+FFFD, never a lone surrogate), so documenting and pinning is enough:
```suggestion
* <p>This comparison does not materialize the UTF-8 byte arrays. It
compares UTF-16 code units
* directly and handles supplementary characters specially to preserve
UTF-8 byte order.
*
* <p>Assumes well-formed UTF-16 input. For strings containing unpaired
surrogates the result no
* longer matches {@code String#getBytes(UTF_8)} byte order: the encoder
replaces an unpaired
* surrogate with {@code '?'} while this method sorts it after every BMP
character. Production
* callers derive keys by decoding UTF-8, which cannot produce unpaired
surrogates.
```
Please also add a small test pinning the new behavior, for example
`compareUtf8Bytes("\uD800", "\uFFFD") > 0` and `compareUtf8Bytes("\uD800", "?")
> 0`. The new exhaustive sweep only generates valid code points, so it can
never hit this case.
##########
hudi-io/src/test/java/org/apache/hudi/common/util/TestStringUtils.java:
##########
@@ -323,6 +323,66 @@ public void
testCompareUtf8BytesEmptyPrefixAndIdenticalStrings() {
assertEquals(0, StringUtils.compareUtf8Bytes("abc", "abc"));
Review Comment:
Every equal pair in these tests is either interned literals or the same list
element in the sweep, so equality always short-circuits at the new `s1 == s2`
branch, and the full loop plus length tiebreak is never exercised for equal
content. I mutation tested this: breaking the final `Integer.compare` for equal
lengths is caught by zero assertions today. One extra line closes it:
```suggestion
assertEquals(0, StringUtils.compareUtf8Bytes("abc", "abc"));
assertEquals(0, StringUtils.compareUtf8Bytes(new String("abc"), new
String("abc")));
```
##########
hudi-io/src/test/java/org/apache/hudi/common/util/TestStringUtils.java:
##########
@@ -323,6 +323,66 @@ public void
testCompareUtf8BytesEmptyPrefixAndIdenticalStrings() {
assertEquals(0, StringUtils.compareUtf8Bytes("abc", "abc"));
}
+ @Test
+ public void testCompareUtf8BytesMatchesEncodedByteOrder() {
+ String[] alphabet = {
+ // One-byte UTF-8 characters, including the upper boundary.
+ "?",
+ "a",
+ String.valueOf((char) 0x007F),
+ // Two-byte UTF-8 lower and upper boundaries.
+ String.valueOf((char) 0x0080),
+ String.valueOf((char) 0x07FF),
+ // Three-byte UTF-8 boundaries around the surrogate range, plus U+FFFD.
+ String.valueOf((char) 0x0800),
+ String.valueOf((char) 0xD7FF),
+ String.valueOf((char) 0xE000),
+ String.valueOf((char) 0xFFFD),
+ // Four-byte UTF-8 supplementary characters, including two sharing a
high surrogate.
+ "😀", // U+1F600
+ new String(Character.toChars(0x20000)),
+ new String(Character.toChars(0x20001)),
+ new String(Character.toChars(0x10FFFF))
+ };
+
+ // Generate every sequence of one to three code points from the alphabet.
This covers cases
+ // where strings differ before, within, or after a supplementary character.
+ List<String> values = new ArrayList<>();
+ values.add("");
+ for (String first : alphabet) {
+ values.add(first);
+ for (String second : alphabet) {
+ values.add(first + second);
+ for (String third : alphabet) {
+ values.add(first + second + third);
+ }
+ }
+ }
+
+ // Compare only the sign because Comparator does not prescribe the
magnitude of its result.
+ for (String left : values) {
+ for (String right : values) {
+ assertEquals(
+ Integer.signum(compareEncodedUtf8Bytes(left, right)),
+ Integer.signum(StringUtils.compareUtf8Bytes(left, right)));
Review Comment:
Nit, feel free to ignore: when this 5.6M-pair loop fails it prints
`expected: <1> but was: <-1>` with no clue which pair failed, and most of these
operands are unprintable. A lazy message supplier only evaluates on failure:
```suggestion
assertEquals(
Integer.signum(compareEncodedUtf8Bytes(left, right)),
Integer.signum(StringUtils.compareUtf8Bytes(left, right)),
() -> "left=" + Arrays.toString(left.codePoints().toArray())
+ " right=" + Arrays.toString(right.codePoints().toArray()));
```
`java.util.Arrays` is already imported.
##########
hudi-io/src/main/java/org/apache/hudi/common/util/StringUtils.java:
##########
@@ -137,23 +137,30 @@ public static byte[] getUTF8Bytes(String str) {
* <p>Neither argument may be {@code null}; like {@link
String#compareTo(String)}, a {@code null}
* argument throws {@link NullPointerException}.
*
- * <p>Assumes well-formed UTF-16 input: {@code String#getBytes(UTF_8)}
replaces unpaired surrogates
- * with {@code '?'}, so strings differing only in unpaired surrogates
compare equal.
+ * <p>This comparison does not materialize the UTF-8 byte arrays. It
compares UTF-16 code units
+ * directly and handles supplementary characters specially to preserve UTF-8
byte order.
*
- * <p>Note: encodes both strings to UTF-8 on every call; for very large
sorts consider
- * pre-encoding keys to byte arrays once and comparing those.
+ * <p>Ported from Google Firebase Firestore's {@code compareUtf8Strings}.
*/
public static int compareUtf8Bytes(String s1, String s2) {
- byte[] b1 = getUTF8Bytes(s1);
- byte[] b2 = getUTF8Bytes(s2);
- int len = Math.min(b1.length, b2.length);
- for (int i = 0; i < len; i++) {
- int cmp = (b1[i] & 0xFF) - (b2[i] & 0xFF);
- if (cmp != 0) {
- return cmp;
+ // Source:
https://github.com/firebase/firebase-android-sdk/blame/f05e4bcb7f86f3b21833b1e0960d793b800d38d1/firebase-firestore/src/main/java/com/google/firebase/firestore/util/Util.java#L76-L132
Review Comment:
Nit, optional: `/blame/` opens the blame view, `/blob/` at the same pinned
sha is the usual permalink. The `// noinspection StringEquality` marker on the
next line is also an IntelliJ-only thing with no other instance in this repo; a
plain comment saying the identity check is intentional would read better.
```suggestion
// Source:
https://github.com/firebase/firebase-android-sdk/blob/f05e4bcb7f86f3b21833b1e0960d793b800d38d1/firebase-firestore/src/main/java/com/google/firebase/firestore/util/Util.java#L76-L132
```
##########
hudi-io/src/main/java/org/apache/hudi/common/util/StringUtils.java:
##########
@@ -137,23 +137,30 @@ public static byte[] getUTF8Bytes(String str) {
* <p>Neither argument may be {@code null}; like {@link
String#compareTo(String)}, a {@code null}
* argument throws {@link NullPointerException}.
*
- * <p>Assumes well-formed UTF-16 input: {@code String#getBytes(UTF_8)}
replaces unpaired surrogates
- * with {@code '?'}, so strings differing only in unpaired surrogates
compare equal.
+ * <p>This comparison does not materialize the UTF-8 byte arrays. It
compares UTF-16 code units
+ * directly and handles supplementary characters specially to preserve UTF-8
byte order.
*
- * <p>Note: encodes both strings to UTF-8 on every call; for very large
sorts consider
- * pre-encoding keys to byte arrays once and comparing those.
+ * <p>Ported from Google Firebase Firestore's {@code compareUtf8Strings}.
*/
public static int compareUtf8Bytes(String s1, String s2) {
- byte[] b1 = getUTF8Bytes(s1);
- byte[] b2 = getUTF8Bytes(s2);
- int len = Math.min(b1.length, b2.length);
- for (int i = 0; i < len; i++) {
- int cmp = (b1[i] & 0xFF) - (b2[i] & 0xFF);
- if (cmp != 0) {
- return cmp;
+ // Source:
https://github.com/firebase/firebase-android-sdk/blame/f05e4bcb7f86f3b21833b1e0960d793b800d38d1/firebase-firestore/src/main/java/com/google/firebase/firestore/util/Util.java#L76-L132
+ // noinspection StringEquality
+ if (s1 == s2) {
Review Comment:
This shortcut makes `compareUtf8Bytes(null, null)` return 0, while the
javadoc above still promises an NPE (the old code threw). A comparator that
treats two nulls as equal turns a fail-fast into a silent mis-sort at the
TreeSet call sites. Keeping fail-fast costs nothing:
```suggestion
if (s1 == s2 && s1 != null) {
```
Please also extend
`testUtf8LexicographicComparatorSerializableAndRejectsNull` with `assertThrows`
for `(null, null)` and `("a", null)` so the contract is pinned on both sides.
The existing test only covers `(null, "a")`, which passes either way.
##########
hudi-io/src/test/java/org/apache/hudi/common/util/TestStringUtils.java:
##########
@@ -323,6 +323,66 @@ public void
testCompareUtf8BytesEmptyPrefixAndIdenticalStrings() {
assertEquals(0, StringUtils.compareUtf8Bytes("abc", "abc"));
}
+ @Test
+ public void testCompareUtf8BytesMatchesEncodedByteOrder() {
+ String[] alphabet = {
+ // One-byte UTF-8 characters, including the upper boundary.
+ "?",
+ "a",
+ String.valueOf((char) 0x007F),
+ // Two-byte UTF-8 lower and upper boundaries.
+ String.valueOf((char) 0x0080),
+ String.valueOf((char) 0x07FF),
+ // Three-byte UTF-8 boundaries around the surrogate range, plus U+FFFD.
+ String.valueOf((char) 0x0800),
+ String.valueOf((char) 0xD7FF),
+ String.valueOf((char) 0xE000),
+ String.valueOf((char) 0xFFFD),
+ // Four-byte UTF-8 supplementary characters, including two sharing a
high surrogate.
+ "😀", // U+1F600
+ new String(Character.toChars(0x20000)),
+ new String(Character.toChars(0x20001)),
+ new String(Character.toChars(0x10FFFF))
+ };
+
+ // Generate every sequence of one to three code points from the alphabet.
This covers cases
+ // where strings differ before, within, or after a supplementary character.
+ List<String> values = new ArrayList<>();
+ values.add("");
+ for (String first : alphabet) {
+ values.add(first);
+ for (String second : alphabet) {
+ values.add(first + second);
+ for (String third : alphabet) {
+ values.add(first + second + third);
+ }
+ }
+ }
+
+ // Compare only the sign because Comparator does not prescribe the
magnitude of its result.
+ for (String left : values) {
+ for (String right : values) {
+ assertEquals(
+ Integer.signum(compareEncodedUtf8Bytes(left, right)),
+ Integer.signum(StringUtils.compareUtf8Bytes(left, right)));
+ }
+ }
+ }
+
+ private static int compareEncodedUtf8Bytes(String left, String right) {
Review Comment:
This helper is a byte-for-byte copy of the implementation the PR deletes, so
the oracle inherits any bug the old code had and cannot notice drift from the
comparator readers actually use. The real authority already lives in this
module: `new UTF8StringKey(left).compareTo(new UTF8StringKey(right))` goes
through `HFileByteUtils.compareKeys`, which is exactly what HFile seeks use.
Same assertion, but it pins agreement with the production comparator instead of
with the old StringUtils code. Please swap the helper over to that.
##########
hudi-io/src/test/java/org/apache/hudi/common/util/TestStringUtils.java:
##########
@@ -323,6 +323,66 @@ public void
testCompareUtf8BytesEmptyPrefixAndIdenticalStrings() {
assertEquals(0, StringUtils.compareUtf8Bytes("abc", "abc"));
}
+ @Test
+ public void testCompareUtf8BytesMatchesEncodedByteOrder() {
+ String[] alphabet = {
+ // One-byte UTF-8 characters, including the upper boundary.
+ "?",
+ "a",
+ String.valueOf((char) 0x007F),
+ // Two-byte UTF-8 lower and upper boundaries.
+ String.valueOf((char) 0x0080),
+ String.valueOf((char) 0x07FF),
+ // Three-byte UTF-8 boundaries around the surrogate range, plus U+FFFD.
+ String.valueOf((char) 0x0800),
+ String.valueOf((char) 0xD7FF),
+ String.valueOf((char) 0xE000),
+ String.valueOf((char) 0xFFFD),
+ // Four-byte UTF-8 supplementary characters, including two sharing a
high surrogate.
+ "😀", // U+1F600
+ new String(Character.toChars(0x20000)),
+ new String(Character.toChars(0x20001)),
+ new String(Character.toChars(0x10FFFF))
+ };
+
+ // Generate every sequence of one to three code points from the alphabet.
This covers cases
Review Comment:
Nit: the list also includes the empty string, so this is zero to three.
```suggestion
// Generate every sequence of zero to three code points from the
alphabet. This covers cases
```
--
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]
