This is an automated email from the ASF dual-hosted git repository.
wgtmac pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/parquet-java.git
The following commit(s) were added to refs/heads/master by this push:
new b98dd9bb4 GH-3735: Use unsigned UTF-8 byte order for Variant object
field keys (#3746)
b98dd9bb4 is described below
commit b98dd9bb4d49beb933912cfde2525fe507b77a88
Author: Peter Lee <[email protected]>
AuthorDate: Sun Sep 20 13:53:29 2026 +0800
GH-3735: Use unsigned UTF-8 byte order for Variant object field keys (#3746)
---
.../java/org/apache/parquet/variant/Variant.java | 53 ++++--
.../org/apache/parquet/variant/VariantBuilder.java | 2 +-
.../org/apache/parquet/variant/VariantUtil.java | 43 +++++
.../parquet/variant/TestVariantObjectBuilder.java | 191 +++++++++++++++++++++
4 files changed, 270 insertions(+), 19 deletions(-)
diff --git
a/parquet-variant/src/main/java/org/apache/parquet/variant/Variant.java
b/parquet-variant/src/main/java/org/apache/parquet/variant/Variant.java
index 3fdfc0060..d20e75eb0 100644
--- a/parquet-variant/src/main/java/org/apache/parquet/variant/Variant.java
+++ b/parquet-variant/src/main/java/org/apache/parquet/variant/Variant.java
@@ -273,24 +273,41 @@ public final class Variant {
}
}
} else {
- int low = 0;
- int high = info.numElements - 1;
- while (low <= high) {
- // Use unsigned right shift to compute the middle of `low` and `high`.
This is not only a
- // performance optimization, because it can properly handle the case
where `low + high`
- // overflows int.
- int mid = (low + high) >>> 1;
- int midId = VariantUtil.readUnsignedLittleEndian(value, idStart +
info.idSize * mid, info.idSize);
- String midKey = getMetadataKeyCached(midId);
- int cmp = midKey.compareTo(key);
- if (cmp < 0) {
- low = mid + 1;
- } else if (cmp > 0) {
- high = mid - 1;
- } else {
- int offset = VariantUtil.readUnsignedLittleEndian(
- value, offsetStart + info.offsetSize * mid, info.offsetSize);
- return childVariant(VariantUtil.slice(value, dataStart + offset));
+ // UTF-8 and UTF-16 order can only disagree at a code unit at or above
U+D800. A lookup key
+ // without one compares identically under either order, so a single
`String.compareTo`
+ // search navigates both spec-ordered and legacy UTF-16-ordered objects.
A key that has one
+ // searches in the spec's UTF-8 byte order first, then retries in the
UTF-16 order written
+ // by versions that sorted object fields with `String.compareTo`, so
those objects remain
+ // readable.
+ boolean needsUtf8 = false;
+ for (int i = 0; i < key.length(); ++i) {
+ if (key.charAt(i) >= Character.MIN_SURROGATE) {
+ needsUtf8 = true;
+ break;
+ }
+ }
+ int maxAttempts = needsUtf8 ? 2 : 1;
+ for (int attempt = 0; attempt < maxAttempts; ++attempt) {
+ int low = 0;
+ int high = info.numElements - 1;
+ while (low <= high) {
+ // Use unsigned right shift to compute the middle of `low` and
`high`. This is not only a
+ // performance optimization, because it can properly handle the case
where `low + high`
+ // overflows int.
+ int mid = (low + high) >>> 1;
+ int midId = VariantUtil.readUnsignedLittleEndian(value, idStart +
info.idSize * mid, info.idSize);
+ String midKey = getMetadataKeyCached(midId);
+ int cmp =
+ (needsUtf8 && attempt == 0) ? VariantUtil.compareKeys(midKey,
key) : midKey.compareTo(key);
+ if (cmp < 0) {
+ low = mid + 1;
+ } else if (cmp > 0) {
+ high = mid - 1;
+ } else {
+ int offset = VariantUtil.readUnsignedLittleEndian(
+ value, offsetStart + info.offsetSize * mid, info.offsetSize);
+ return childVariant(VariantUtil.slice(value, dataStart + offset));
+ }
}
}
}
diff --git
a/parquet-variant/src/main/java/org/apache/parquet/variant/VariantBuilder.java
b/parquet-variant/src/main/java/org/apache/parquet/variant/VariantBuilder.java
index c692d3119..61ee7782c 100644
---
a/parquet-variant/src/main/java/org/apache/parquet/variant/VariantBuilder.java
+++
b/parquet-variant/src/main/java/org/apache/parquet/variant/VariantBuilder.java
@@ -691,7 +691,7 @@ public class VariantBuilder {
@Override
public int compareTo(FieldEntry other) {
- return key.compareTo(other.key);
+ return VariantUtil.compareKeys(key, other.key);
}
}
diff --git
a/parquet-variant/src/main/java/org/apache/parquet/variant/VariantUtil.java
b/parquet-variant/src/main/java/org/apache/parquet/variant/VariantUtil.java
index ad7165fcf..97e497a17 100644
--- a/parquet-variant/src/main/java/org/apache/parquet/variant/VariantUtil.java
+++ b/parquet-variant/src/main/java/org/apache/parquet/variant/VariantUtil.java
@@ -301,6 +301,49 @@ class VariantUtil {
return result;
}
+ /**
+ * Compares two object field names by the unsigned lexicographic byte order
of their UTF-8
+ * encodings, as required by the Variant spec for object field ordering,
without encoding
+ * either name. UTF-8 byte order is exactly code point order, so this
compares the strings'
+ * code points via {@link #codePointOrderRank}.
+ *
+ * <p>This intentionally differs from {@link String#compareTo}, which
compares UTF-16 code
+ * units. The two orderings agree for all names in the Basic Multilingual
Plane but diverge for
+ * supplementary-plane characters (U+10000 and above): {@code
String#compareTo} orders a leading
+ * high surrogate (0xD800-0xDBFF) before code points in U+E000..U+FFFF,
whereas UTF-8 byte order
+ * (and the spec) orders them after. Using UTF-16 order here would produce
objects whose field
+ * ids are mis-sorted relative to the spec, breaking binary-search lookups
by any reader that
+ * follows the spec's UTF-8 byte ordering.
+ *
+ * <p>An unpaired surrogate has no UTF-8 encoding, and Java's encoder
substitutes {@code ?} for
+ * one, so a name containing one is ordered by the surrogate itself rather
than by the bytes
+ * that would be written for it.
+ */
+ static int compareKeys(String a, String b) {
+ int limit = Math.min(a.length(), b.length());
+ for (int i = 0; i < limit; ++i) {
+ char left = a.charAt(i);
+ char right = b.charAt(i);
+ if (left != right) {
+ return codePointOrderRank(left) - codePointOrderRank(right);
+ }
+ }
+ // All shared code units are equal, so the shorter name is a prefix of the
longer one.
+ return a.length() - b.length();
+ }
+
+ /**
+ * Maps a UTF-16 code unit to a value ordered like the code point it
encodes. A surrogate always
+ * encodes a supplementary code point (U+10000 and above), so U+D800..U+DFFF
must rank above
+ * every other code unit; U+E000..U+FFFF shift down to fill the gap they
leave behind.
+ */
+ private static int codePointOrderRank(char unit) {
+ if (unit < Character.MIN_SURROGATE) {
+ return unit;
+ }
+ return unit <= Character.MAX_SURROGATE ? unit + 0x2000 : unit - 0x800;
+ }
+
/**
* Fast little-endian unsigned read using bulk ByteBuffer operations.
* Requires the buffer to have {@link java.nio.ByteOrder#LITTLE_ENDIAN} byte
order.
diff --git
a/parquet-variant/src/test/java/org/apache/parquet/variant/TestVariantObjectBuilder.java
b/parquet-variant/src/test/java/org/apache/parquet/variant/TestVariantObjectBuilder.java
index d739fdba1..69539142c 100644
---
a/parquet-variant/src/test/java/org/apache/parquet/variant/TestVariantObjectBuilder.java
+++
b/parquet-variant/src/test/java/org/apache/parquet/variant/TestVariantObjectBuilder.java
@@ -23,6 +23,11 @@ import static
org.assertj.core.api.Assertions.assertThatThrownBy;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
+import java.nio.charset.StandardCharsets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.Random;
import java.util.UUID;
import org.junit.jupiter.api.Disabled;
import org.junit.jupiter.api.Test;
@@ -85,6 +90,192 @@ public class TestVariantObjectBuilder {
});
}
+ /**
+ * Object field keys must be ordered by the unsigned byte order of their
UTF-8 encoding, not by
+ * {@link String#compareTo} (UTF-16 code-unit order). The two orderings
disagree for
+ * supplementary-plane keys: U+FFFF encodes to UTF-8 {@code EF BF BF} and
U+10000 to
+ * {@code F0 90 80 80}, so U+FFFF must sort first; but in UTF-16 the leading
high surrogate
+ * 0xD800 of U+10000 sorts before 0xFFFF, which would wrongly put U+10000
first. See
+ * {@link VariantUtil#compareKeys}.
+ */
+ @Test
+ public void testObjectKeysSortedByUtf8ByteOrder() {
+ String bmpKey = "�"; // U+FFFF -> UTF-8 EF BF BF
+ String supplementaryKey = new String(Character.toChars(0x10000)); // UTF-8
F0 90 80 80
+
+ VariantBuilder b = new VariantBuilder();
+ VariantObjectBuilder o = b.startObject();
+ // Appended in the "wrong" order on purpose, to prove the builder sorts
rather than
+ // preserving insertion order.
+ o.appendKey(supplementaryKey);
+ o.appendLong(2);
+ o.appendKey(bmpKey);
+ o.appendLong(1);
+ b.endObject();
+
+ VariantTestUtil.testVariant(b.build(), v -> {
+ VariantTestUtil.checkType(v, VariantUtil.OBJECT, Variant.Type.OBJECT);
+ assertThat(v.numObjectElements()).isEqualTo(2);
+ // UTF-8 byte order: EF BF BF < F0 90 80 80, so the BMP key comes first.
+ assertThat(v.getFieldAtIndex(0).key).isEqualTo(bmpKey);
+ assertThat(v.getFieldAtIndex(1).key).isEqualTo(supplementaryKey);
+ assertThat(v.getFieldByKey(bmpKey).getLong()).isEqualTo(1);
+ assertThat(v.getFieldByKey(supplementaryKey).getLong()).isEqualTo(2);
+ });
+ }
+
+ /**
+ * A large object (>= BINARY_SEARCH_THRESHOLD) that mixes ASCII keys with
U+FFFF and a
+ * supplementary-plane key, exercising the reader's binary-search path in
+ * {@link Variant#getFieldByKey}. The binary search must use the same UTF-8
byte ordering as the
+ * builder's sort; with a UTF-16 comparator on the read side, the
supplementary key would be
+ * mis-navigated and not found.
+ */
+ @Test
+ public void testLargeObjectBinarySearchWithSupplementaryKey() {
+ String bmpKey = "�"; // UTF-8 EF BF BF
+ String supplementaryKey = new String(Character.toChars(0x10000)); // UTF-8
F0 90 80 80
+
+ VariantBuilder b = new VariantBuilder();
+ VariantObjectBuilder o = b.startObject();
+ for (int i = 0; i < 40; i++) { // well above BINARY_SEARCH_THRESHOLD (32)
+ o.appendKey(String.format("a%03d", i));
+ o.appendLong(i);
+ }
+ o.appendKey(bmpKey);
+ o.appendLong(998);
+ o.appendKey(supplementaryKey);
+ o.appendLong(999);
+ b.endObject();
+
+ VariantTestUtil.testVariant(b.build(), v -> {
+ assertThat(v.numObjectElements()).isEqualTo(42);
+ assertThat(v.getFieldByKey(bmpKey)).isNotNull();
+ assertThat(v.getFieldByKey(bmpKey).getLong()).isEqualTo(998);
+ assertThat(v.getFieldByKey(supplementaryKey)).isNotNull();
+ assertThat(v.getFieldByKey(supplementaryKey).getLong()).isEqualTo(999);
+ assertThat(v.getFieldByKey("a037").getLong()).isEqualTo(37);
+ });
+ }
+
+ /**
+ * Objects written before the ordering fix sorted field ids by {@link
String#compareTo} (UTF-16
+ * order). {@link Variant#getFieldByKey} must still find keys in such
objects: when a key
+ * contains a code unit at or above U+D800, the lookup retries the binary
search in UTF-16 order
+ * after the spec's UTF-8 order fails.
+ */
+ @Test
+ public void testLegacyUtf16OrderedObjectLookup() {
+ String bmpKey = "�"; // UTF-8 EF BF BF
+ String supplementaryKey = new String(Character.toChars(0x10000)); // UTF-8
F0 90 80 80
+
+ VariantBuilder b = new VariantBuilder();
+ VariantObjectBuilder o = b.startObject();
+ for (int i = 0; i < 40; i++) {
+ o.appendKey(String.format("a%03d", i));
+ o.appendLong(i);
+ }
+ o.appendKey(bmpKey);
+ o.appendLong(998);
+ o.appendKey(supplementaryKey);
+ o.appendLong(999);
+ b.endObject();
+ Variant canonical = b.build();
+
+ // Reproduce the layout written by older versions: swap the id and offset
entries of the last
+ // two fields, so the supplementary key precedes the BMP key (UTF-16
order).
+ ByteBuffer valueBuffer = canonical.getValueBuffer().duplicate();
+ byte[] legacyValue = new byte[valueBuffer.remaining()];
+ valueBuffer.get(legacyValue);
+ VariantUtil.ObjectInfo info =
+
VariantUtil.getObjectInfo(ByteBuffer.wrap(legacyValue).order(ByteOrder.LITTLE_ENDIAN));
+ swapLastTwoEntries(legacyValue, info.idStartOffset, info.idSize,
info.numElements);
+ swapLastTwoEntries(legacyValue, info.offsetStartOffset, info.offsetSize,
info.numElements);
+ Variant legacy = new Variant(ByteBuffer.wrap(legacyValue),
canonical.getMetadataBuffer());
+
+ assertThat(legacy.getFieldAtIndex(40).key).isEqualTo(supplementaryKey);
+ assertThat(legacy.getFieldAtIndex(41).key).isEqualTo(bmpKey);
+ // ASCII keys are found by the first (UTF-8 order) search.
+ assertThat(legacy.getFieldByKey("a037").getLong()).isEqualTo(37);
+ // Keys at or above U+D800 are found by the UTF-16 order retry.
+ assertThat(legacy.getFieldByKey(bmpKey).getLong()).isEqualTo(998);
+
assertThat(legacy.getFieldByKey(supplementaryKey).getLong()).isEqualTo(999);
+ // Absent keys stay absent after both attempts.
+ assertThat(legacy.getFieldByKey("missing")).isNull();
+ assertThat(legacy.getFieldByKey(new
String(Character.toChars(0x10001)))).isNull();
+ }
+
+ /**
+ * {@link VariantUtil#compareKeys} orders field names as their UTF-8
encodings compare as
+ * unsigned bytes, but reaches that order from the UTF-16 code units without
encoding either
+ * name. Check it against encoding both and comparing the bytes, over names
that cover every
+ * UTF-8 length, both sides of the surrogate range, and prefixes.
+ */
+ @Test
+ public void testCompareKeysMatchesUtf8ByteOrder() {
+ List<String> keys = new ArrayList<>(Arrays.asList(
+ "",
+ "a",
+ "ab",
+ "b",
+ "A",
+ "~",
+ "\u007f", // last 1-byte UTF-8
+ "\u0080", // first 2-byte UTF-8
+ "\u00e9",
+ "\u07ff", // last 2-byte UTF-8
+ "\u0800", // first 3-byte UTF-8
+ "\ud7ff", // last code unit below the surrogate range
+ "\ue000", // first code unit above the surrogate range
+ "\uffff", // EF BF BF
+ new String(Character.toChars(0x10000)), // F0 90 80 80, first 4-byte
UTF-8
+ new String(Character.toChars(0x10ffff)), // F4 8F BF BF, last code
point
+ "a\uffff",
+ "a" + new String(Character.toChars(0x10000)),
+ new String(Character.toChars(0x10000)) + "a"));
+ // Random names, to cover pairs the hand-picked ones miss.
+ Random random = new Random(2891);
+ for (int i = 0; i < 200; i++) {
+ StringBuilder key = new StringBuilder();
+ for (int c = 0; c < 1 + random.nextInt(3); c++) {
+ // Draw from ASCII, the BMP around the surrogate range, and the
supplementary planes.
+ switch (random.nextInt(3)) {
+ case 0:
+ key.append((char) ('a' + random.nextInt(3)));
+ break;
+ case 1:
+ // Valid code units either side of the surrogate range, which has
no UTF-8 encoding.
+ int offset = random.nextInt(6);
+ key.append((char) (offset < 3 ? 0xd7fd + offset : 0xe000 + offset
- 3));
+ break;
+ default:
+ key.appendCodePoint(0x10000 + random.nextInt(4));
+ }
+ }
+ keys.add(key.toString());
+ }
+
+ for (String left : keys) {
+ for (String right : keys) {
+ int expected = Arrays.compareUnsigned(
+ left.getBytes(StandardCharsets.UTF_8),
right.getBytes(StandardCharsets.UTF_8));
+ assertThat(Integer.signum(VariantUtil.compareKeys(left, right)))
+ .as("comparing %s against %s", left, right)
+ .isEqualTo(Integer.signum(expected));
+ }
+ }
+ }
+
+ private static void swapLastTwoEntries(byte[] bytes, int start, int width,
int numElements) {
+ int left = start + (numElements - 2) * width;
+ int right = left + width;
+ ByteBuffer buffer = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN);
+ int leftValue = VariantUtil.readUnsignedLittleEndian(buffer, left, width);
+ int rightValue = VariantUtil.readUnsignedLittleEndian(buffer, right,
width);
+ VariantUtil.writeLong(bytes, left, rightValue, width);
+ VariantUtil.writeLong(bytes, right, leftValue, width);
+ }
+
@Test
public void testMixedObjectBuilder() {
VariantBuilder b = new VariantBuilder();
