ZdravDim commented on code in PR #58455:
URL: https://github.com/apache/spark/pull/58455#discussion_r3948342490
##########
common/variant/src/main/java/org/apache/spark/types/variant/VariantBuilder.java:
##########
@@ -532,18 +541,308 @@ private void appendVariantImpl(byte[] value, byte[]
metadata, int pos) {
int offset = readUnsigned(value, offsetStart + offsetSize * i,
offsetSize);
int elementPos = dataStart + offset;
offsets.add(writePos - start);
- appendVariantImpl(value, metadata, elementPos);
+ appendVariantImpl(value, metadata, elementPos, needNormalization);
}
finishWritingArray(start, offsets);
return null;
});
break;
+ default:
+ if (needNormalization) {
+ appendCanonicalizedScalar(value, pos);
+ } else {
+ shallowAppendVariantImpl(value, pos);
+ }
+ break;
+ }
+ }
+
+ // Canonicalize and append a single scalar value: integers re-emitted at the
smallest int width,
+ // integer-valued decimals promoted to the integer encoding, decimal
trailing zeros stripped,
+ // -0.0 mapped to +0.0, and short strings short-encoded -- so e.g. `1.0`,
`1`, and a wide-encoded
+ // `1` all produce byte-equal output. The scalar normalization rules that
the read-side check
+ // (`isValueCanonical`) must mirror are factored into shared helpers so the
two cannot drift.
+ private void appendCanonicalizedScalar(byte[] value, int pos) {
+ switch (VariantUtil.getType(value, pos)) {
+ case LONG:
+ appendLong(VariantUtil.getLong(value, pos));
+ break;
+ case DECIMAL: {
+ BigDecimal bd = VariantUtil.getDecimal(value, pos);
+ if (decimalPromotesToLong(bd)) {
+ appendLong(bd.longValue());
+ } else {
+ // Fractional, or too large for a long: emit as a decimal (negative
scale coerced to 0).
+ appendDecimal(canonicalDecimalForm(bd));
+ }
+ break;
+ }
+ case FLOAT:
+ appendFloat(canonicalizeFloat(VariantUtil.getFloat(value, pos)));
+ break;
+ case DOUBLE:
+ appendDouble(canonicalizeDouble(VariantUtil.getDouble(value, pos)));
+ break;
+ case STRING:
+ appendString(VariantUtil.getString(value, pos));
+ break;
default:
shallowAppendVariantImpl(value, pos);
break;
}
}
+ // Return a canonical Variant.
+ // Two Variants are semantically equal iff their canonical forms are
byte-equal,
+ // so canonicalizing lets the byte-equality machinery (hash aggregate
bucketing,
+ // hash partitioning) group and compare Variants by value rather than by
+ // their incidental physical encoding.
+ //
+ // The metadata dictionary is rebuilt with its keys sorted by (the same order
+ // finishWritingObject already uses for object fields, so the two stay
+ // consistent) and unused entries stripped, with field ids remapped to the
sorted positions.
+ public static Variant canonicalize(Variant v) {
+ // Fast path: a top-level (pos == 0) input that is already canonical is
returned unchanged. A
+ // sub-variant (pos != 0) is a view into a parent's shared value/metadata,
so it always takes
+ // the slow path, which reads the element at v.pos and rebuilds a
standalone canonical Variant.
+ if (v.pos == 0 && isCanonical(v.value, v.metadata)) {
+ return v;
+ }
+ VariantBuilder builder = new VariantBuilder(/* allowDuplicateKeys */
false);
+ builder.buildCanonicalized(v.value, v.metadata, v.pos);
+ return builder.result();
+ }
+
+ private void buildCanonicalized(byte[] value, byte[] metadata, int pos) {
+ ArrayList<String> keys = new ArrayList<>();
+ collectAllObjectKeys(value, metadata, pos, keys);
+ keys.sort((a, b) -> compareKeys(encodeKey(a), encodeKey(b)));
+ keys = new ArrayList<>(new LinkedHashSet<>(keys));
+ for (String key : keys) {
+ addKey(key);
+ }
+ appendVariantImpl(value, metadata, pos, /* needNormalization */ true);
+ }
+
+ private void collectAllObjectKeys(
+ byte[] value, byte[] metadata, int pos, ArrayList<String> keys) {
+ checkIndex(pos, value.length);
+ int basicType = value[pos] & BASIC_TYPE_MASK;
+ switch (basicType) {
+ case OBJECT:
+ handleObject(value, pos, (size, idSize, offsetSize, idStart,
offsetStart, dataStart) -> {
+ for (int i = 0; i < size; ++i) {
+ int id = readUnsigned(value, idStart + idSize * i, idSize);
+ int offset = readUnsigned(value, offsetStart + offsetSize * i,
offsetSize);
+ int elementPos = dataStart + offset;
+ keys.add(getMetadataKey(metadata, id));
+ collectAllObjectKeys(value, metadata, elementPos, keys);
+ }
+ return null;
+ });
+ break;
+ case ARRAY:
+ handleArray(value, pos, (size, offsetSize, offsetStart, dataStart) -> {
+ for (int i = 0; i < size; ++i) {
+ int offset = readUnsigned(value, offsetStart + offsetSize * i,
offsetSize);
+ int elementPos = dataStart + offset;
+ collectAllObjectKeys(value, metadata, elementPos, keys);
+ }
+ return null;
+ });
+ break;
+ default:
+ break;
+ }
+ }
+
+ // Return true iff `(value, metadata)` is ALREADY in the exact byte form
that `buildCanonicalized`
+ // would produce -- i.e. calling `canonicalize` on it is a no-op. Intended
as a read-side fast
+ // path so already-canonical Variants skip the allocation-heavy rebuild
(dictionary sort +
+ // re-serialize).
+ //
+ // Checked here:
+ // - metadata dictionary: keys sorted + deduped, minimal offset width, no
unused keys;
+ // - objects/arrays: field ids ascending, offsets exact-cumulative,
id/offset widths minimal;
+ // - scalars:
+ // - minimal int width
+ // - decimal integer-promoted, trailing-zero-free, minimal width
+ // - float/double the exact bytes appendFloat/appendDouble emit
+ // - string short-encoded when it fits.
+ public static boolean isCanonical(byte[] value, byte[] metadata) {
+ checkIndex(0, metadata.length);
+ int metaOffsetSize = ((metadata[0] >> 6) & 0x3) + 1;
+ int numKeys = readUnsigned(metadata, 1, metaOffsetSize);
+ if (numKeys > 1) {
+ byte[] prevKey = encodeKey(getMetadataKey(metadata, 0));
+ for (int id = 1; id < numKeys; ++id) {
+ byte[] key = encodeKey(getMetadataKey(metadata, id));
+ if (compareKeys(prevKey, key) >= 0) {
+ return false;
+ }
+ prevKey = key;
+ }
+ }
+ int lastOffset = readUnsigned(metadata, 1 + (numKeys + 1) *
metaOffsetSize, metaOffsetSize);
+ long maxSize = Math.max(lastOffset, numKeys);
+ if ((metadata[0] & 0xFF) != (VERSION | ((minIntWidth(maxSize) - 1) << 6)))
{
+ return false;
+ }
+ boolean[] referenced = new boolean[numKeys];
+ if (!isValueCanonical(value, metadata, 0, referenced)) {
+ return false;
+ }
+ for (int id = 0; id < numKeys; ++id) {
+ if (!referenced[id]) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ // Value-traversal half of `isCanonical`. Returns false on the first
non-canonical node.
+ private static boolean isValueCanonical(
+ byte[] value, byte[] metadata, int pos, boolean[] referenced) {
+ switch (VariantUtil.getType(value, pos)) {
+ case OBJECT:
+ return handleObject(value, pos,
+ (size, idSize, offsetSize, idStart, offsetStart, dataStart) -> {
+ // Field ids strictly ascending: with a sorted dictionary, canon
emits fields in key
+ // order, and key order == id order. This also rejects duplicate
keys (equal ids).
+ int prevId = -1;
+ int dataSize = 0;
+ for (int i = 0; i < size; ++i) {
+ int id = readUnsigned(value, idStart + idSize * i, idSize);
+ if (id <= prevId || id >= referenced.length) {
+ return false;
+ }
+ prevId = id;
+ referenced[id] = true;
+ // Offsets must be the exact running data size (no gaps or
padding).
+ int offset = readUnsigned(value, offsetStart + offsetSize * i,
offsetSize);
+ if (offset != dataSize) {
+ return false;
+ }
+ int elementPos = dataStart + offset;
+ if (!isValueCanonical(value, metadata, elementPos, referenced)) {
+ return false;
+ }
+ dataSize += VariantUtil.valueSize(value, elementPos);
+ }
+ int lastOffset = readUnsigned(value, offsetStart + offsetSize *
size, offsetSize);
+ if (lastOffset != dataSize) {
+ return false;
+ }
+ int maxId = size == 0 ? 0 : prevId;
+ return idSize == minIntWidth(maxId) && offsetSize ==
minIntWidth(dataSize);
+ });
+ case ARRAY:
+ return handleArray(value, pos, (size, offsetSize, offsetStart,
dataStart) -> {
+ int dataSize = 0;
+ for (int i = 0; i < size; ++i) {
+ int offset = readUnsigned(value, offsetStart + offsetSize * i,
offsetSize);
+ if (offset != dataSize) {
+ return false;
+ }
+ int elementPos = dataStart + offset;
+ if (!isValueCanonical(value, metadata, elementPos, referenced)) {
+ return false;
+ }
+ dataSize += VariantUtil.valueSize(value, elementPos);
+ }
+ int lastOffset = readUnsigned(value, offsetStart + offsetSize *
size, offsetSize);
+ if (lastOffset != dataSize) {
+ return false;
+ }
+ return offsetSize == minIntWidth(dataSize);
+ });
+ case LONG:
+ // Must use the smallest int width `appendLong` would pick.
+ return VariantUtil.getTypeInfo(value, pos)
+ == canonicalLongTypeInfo(VariantUtil.getLong(value, pos));
+ case DECIMAL: {
+ BigDecimal onDisk = VariantUtil.getDecimalWithOriginalScale(value,
pos);
+ BigDecimal stripped = onDisk.stripTrailingZeros();
+ // A decimal that promotes to a long is stored as the wrong type ->
not canonical.
+ if (decimalPromotesToLong(stripped)) {
+ return false;
+ }
+ BigDecimal canonForm = canonicalDecimalForm(stripped);
+ return onDisk.scale() == canonForm.scale()
+ && VariantUtil.getTypeInfo(value, pos) ==
canonicalDecimalTypeInfo(canonForm);
+ }
+ case FLOAT: {
+ // Canonical iff the stored 4 bytes are exactly what `appendFloat`
would write.
+ int rawBits = (int) VariantUtil.readLong(value, pos + 1, 4);
+ float f = Float.intBitsToFloat(rawBits);
+ return rawBits == Float.floatToIntBits(canonicalizeFloat(f));
+ }
+ case DOUBLE: {
+ // Same as FLOAT, over 8 bytes.
+ long rawBits = VariantUtil.readLong(value, pos + 1, 8);
+ double d = Double.longBitsToDouble(rawBits);
+ return rawBits == Double.doubleToLongBits(canonicalizeDouble(d));
+ }
+ case STRING:
+ // A short string is always canonical (its length <=
MAX_SHORT_STR_SIZE by construction). A
+ // LONG_STR is canonical only when its length exceeds the short-string
cap.
+ if ((value[pos] & BASIC_TYPE_MASK) == SHORT_STR) {
+ return true;
+ }
+ return readUnsigned(value, pos + 1, U32_SIZE) > MAX_SHORT_STR_SIZE;
+ default:
+ return true;
+ }
+ }
+
+ // Smallest unsigned integer byte width that can hold `value`.
+ private static int minIntWidth(long value) {
Review Comment:
**minIntWidth(value)** is a silent duplicate of the existing
**getIntegerSize(value)**. Code for these two functions is pretty similar,
consider making **getIntegerSize(value)** do the assert and then call
**minIntWidth(value)**.
##########
common/variant/src/test/scala/org/apache/spark/types/variant/VariantCanonicalizeSuite.scala:
##########
@@ -0,0 +1,460 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.types.variant
+
+import java.util.Arrays
+
+import org.scalatest.funsuite.AnyFunSuite // scalastyle:ignore funsuite
+
+/**
+ * Direct unit tests for `VariantBuilder.canonicalize`.
+ *
+ * The canonical form is the contract that `canonicalize(a)` and
`canonicalize(b)` are byte-equal
+ * iff `a` and `b` are semantically equal. It currently covers structural
canonicalization
+ * (metadata dictionary key order, unused-key stripping, object field-id
remapping)
+ * and value normalization for integers, decimals, float/double, and strings
+ * (integer width, integer-promotion, trailing-zero strip, -0.0 -> +0.0,
canonical NaN, short-string
+ * encoding). The `isCanonical` read-side predicate is complete and checked
against `canonicalize`
+ * by a soundness oracle over a mixed corpus.
+ */
+class VariantCanonicalizeSuite extends AnyFunSuite { // scalastyle:ignore
funsuite
+
+ private def parse(json: String): Variant =
+ VariantBuilder.parseJson(
+ json,
+ /* allowDuplicateKeys = */ false)
+
+ private def canon(v: Variant): Variant = VariantBuilder.canonicalize(v)
+
+ private def bytesEqual(a: Variant, b: Variant): Boolean =
+ Arrays.equals(a.getValue, b.getValue) && Arrays.equals(a.getMetadata,
b.getMetadata)
+
+ private def isCanon(v: Variant): Boolean =
+ VariantBuilder.isCanonical(v.getValue, v.getMetadata)
+
+ private def buildDouble(d: Double): Variant = {
+ val b = new VariantBuilder(false)
+ b.appendDouble(d)
+ b.result()
+ }
+
+ private def buildFloat(f: Float): Variant = {
+ val b = new VariantBuilder(false)
+ b.appendFloat(f)
+ b.result()
+ }
+
+ test("object key order does not affect the canonical form") {
+ val a = canon(parse("""{"a":1,"b":2}"""))
+ val b = canon(parse("""{"b":2,"a":1}"""))
+ assert(bytesEqual(a, b), "objects equal up to key order must canonicalize
to equal bytes")
+ }
+
+ test("nested object key order does not affect the canonical form") {
+ val a = canon(parse("""{"outer":{"a":1,"b":2},"z":3}"""))
+ val b = canon(parse("""{"z":3,"outer":{"b":2,"a":1}}"""))
+ assert(bytesEqual(a, b), "nested object key order must be normalized
recursively")
+ }
+
+ test("canonical form is independent of the incoming metadata dictionary
order") {
+ val a = canon(parse("""{"m":{"a":1},"a":{"b":2}}"""))
+ val b = canon(parse("""{"a":{"b":2},"m":{"a":1}}"""))
+ assert(bytesEqual(a, b), "canonical metadata must not depend on incoming
dictionary order")
+ }
+
+ test("object key order inside array elements is normalized, array element
order is preserved") {
+ val a = canon(parse("""[{"a":1,"b":2},{"c":3}]"""))
+ val b = canon(parse("""[{"b":2,"a":1},{"c":3}]"""))
+ assert(bytesEqual(a, b), "object key order within array elements must be
normalized")
+
+ val c = canon(parse("""[1,2]"""))
+ val d = canon(parse("""[2,1]"""))
+ assert(!bytesEqual(c, d), "array element order is significant and must be
preserved")
+ }
+
+ test("canonicalize is idempotent") {
+ val inputs = Seq(
+ """{"b":2,"a":1}""",
+ """{"a":1,"b":2}""",
+ """{"outer":{"z":1,"a":2},"m":[1,2,3]}""",
+ "[1,2,3]",
+ "\"hello\"",
+ "true",
+ "null",
+ "1",
+ "{}",
+ "[]")
+ for (json <- inputs) {
+ val once = canon(parse(json))
+ val twice = canon(once)
+ assert(bytesEqual(once, twice), s"canonicalize must be idempotent for
input $json")
+ }
+ }
+
+ test("empty object and empty array canonicalize without error") {
+ assert(bytesEqual(canon(parse("{}")), canon(parse("{}"))))
+ assert(bytesEqual(canon(parse("[]")), canon(parse("[]"))))
+ }
+
+ // ----- Value normalization: DECIMAL -----
+
+ test("integer-valued decimal canonicalizes to the integer encoding") {
+ assert(!bytesEqual(parse("1.0"), parse("1")), "1.0 and 1 should differ
before canon")
+ assert(bytesEqual(canon(parse("1.0")), canon(parse("1"))), "1.0 must
canonicalize to 1")
+ assert(bytesEqual(canon(parse("1.000")), canon(parse("1"))), "1.000 must
canonicalize to 1")
+ }
+
+ test("decimal trailing zeros are stripped") {
+ assert(!bytesEqual(parse("1.50"), parse("1.5")), "1.50 and 1.5 should
differ before canon")
+ assert(bytesEqual(canon(parse("1.50")), canon(parse("1.5"))), "1.50 must
canonicalize to 1.5")
+ assert(bytesEqual(canon(parse("1.500")), canon(parse("1.5"))), "1.500 must
canonicalize to 1.5")
+ }
+
+ test("decimal normalization applies inside nested objects and arrays") {
+ assert(bytesEqual(canon(parse("""{"a":1.0}""")),
canon(parse("""{"a":1}"""))))
+ assert(bytesEqual(
+ canon(parse("""{"a":[1.0, 2.50]}""")),
+ canon(parse("""{"a":[1, 2.5]}"""))))
+ }
+
+ test("non-integer decimal is not promoted to an integer") {
+ assert(!bytesEqual(canon(parse("1.5")), canon(parse("1"))), "1.5 must not
collapse to 1")
+ assert(!bytesEqual(canon(parse("1.5")), canon(parse("2"))), "1.5 must not
collapse to 2")
+ }
+
+ test("integer decimal too large for a long is not promoted (stays a
decimal)") {
+ val big = "100000000000000000000"
+ assert(VariantUtil.getType(parse(big).getValue, 0) ==
VariantUtil.Type.DECIMAL,
+ "sanity: 10^20 should parse as a DECIMAL")
+ val canonBig = canon(parse(big))
+ assert(VariantUtil.getType(canonBig.getValue, 0) ==
VariantUtil.Type.DECIMAL,
+ "10^20 must remain a DECIMAL, not be wrapped into a long")
+ val actual = VariantUtil.getDecimal(canonBig.getValue, 0)
+ assert(actual.compareTo(new java.math.BigDecimal(big)) == 0, "10^20 value
must be preserved")
+ }
+
+ // ----- Value normalization: integer width -----
+
+ test("non-minimal integer width is reduced to the smallest") {
+ val int8Header =
+ ((VariantUtil.INT8 << VariantUtil.BASIC_TYPE_BITS) |
VariantUtil.PRIMITIVE).toByte
+ val int8One =
+ new Variant(Array[Byte](int8Header, 1, 0, 0, 0, 0, 0, 0, 0),
parse("1").getMetadata)
+ assert(!bytesEqual(int8One, parse("1")), "sanity: INT8(1) and INT1(1)
differ before canon")
+ assert(bytesEqual(canon(int8One), canon(parse("1"))), "INT8(1) must reduce
to INT1(1)")
+ }
+
+ // ----- Value normalization: float / double -----
+
+ test("negative zero canonicalizes to positive zero") {
+ assert(!bytesEqual(buildDouble(-0.0d), buildDouble(0.0d)), "sanity: -0.0d
and +0.0d differ")
+ assert(bytesEqual(canon(buildDouble(-0.0d)), canon(buildDouble(0.0d))),
"double -0.0 -> +0.0")
+ assert(!bytesEqual(buildFloat(-0.0f), buildFloat(0.0f)), "sanity: -0.0f
and +0.0f differ")
+ assert(bytesEqual(canon(buildFloat(-0.0f)), canon(buildFloat(0.0f))),
"float -0.0 -> +0.0")
+ }
+
+ test("non-canonical NaN canonicalizes to the canonical NaN") {
+ val doubleHeader =
+ ((VariantUtil.DOUBLE << VariantUtil.BASIC_TYPE_BITS) |
VariantUtil.PRIMITIVE).toByte
+ val bytes =
java.nio.ByteBuffer.allocate(9).order(java.nio.ByteOrder.LITTLE_ENDIAN)
+ .put(doubleHeader).putLong(0x7ff8000000000001L).array()
+ val nonCanonicalNaN = new Variant(bytes, parse("1").getMetadata)
+ assert(!bytesEqual(nonCanonicalNaN, buildDouble(Double.NaN)), "sanity: NaN
encodings differ")
+ assert(bytesEqual(canon(nonCanonicalNaN), canon(buildDouble(Double.NaN))),
+ "all NaN bit patterns must canonicalize to the same bytes")
+ }
+
+ // ----- Value normalization: string encoding -----
+
+ test("a short string stored as long_str is re-encoded as a short string") {
+ val longStrHeader =
+ ((VariantUtil.LONG_STR << VariantUtil.BASIC_TYPE_BITS) |
VariantUtil.PRIMITIVE).toByte
+ val text = "hi".getBytes(java.nio.charset.StandardCharsets.UTF_8)
+ val bytes = java.nio.ByteBuffer.allocate(1 + 4 + text.length)
+ .order(java.nio.ByteOrder.LITTLE_ENDIAN)
+ .put(longStrHeader).putInt(text.length).put(text).array()
+ val longEncoded = new Variant(bytes, parse("1").getMetadata)
+ assert(!bytesEqual(longEncoded, parse("\"hi\"")), "sanity: long_str and
short_str 'hi' differ")
+ assert(bytesEqual(canon(longEncoded), parse("\"hi\"")), "long_str 'hi' ->
short_str")
+ }
+
+ // ----- isCanonical: metadata dictionary -----
+
+ test("isCanonical accepts a sorted metadata dictionary and rejects an
unsorted one") {
+ assert(isCanon(parse("""{"a":1,"b":2}""")), "ascending dictionary is
canonical")
+ assert(!isCanon(parse("""{"b":2,"a":1}""")), "descending dictionary is not
canonical")
+ assert(!isCanon(parse("""{"z":1,"a":2,"m":3}""")), "unsorted dictionary is
not canonical")
+ assert(isCanon(canon(parse("""{"b":2,"a":1}"""))), "canon output has a
sorted dictionary")
+ }
+
+ test("isCanonical accepts an empty dictionary") {
+ assert(isCanon(parse("1")), "a scalar's empty dictionary is canonical")
+ assert(isCanon(parse("[1,2,3]")), "an array of scalars has an empty
dictionary")
+ }
+
+ test("isCanonical rejects a non-minimal metadata offset width") {
+ val emptyMeta = parse("1").getMetadata
+ val version = emptyMeta(0)
+ val header2 = (version | (1 << 6)).toByte // offset width = 2 bytes
+ val meta = java.nio.ByteBuffer.allocate(1 + 2 + 2 + 2 + 1)
+ .order(java.nio.ByteOrder.LITTLE_ENDIAN)
+ .put(header2)
+ .put(1.toByte).put(0.toByte) // numKeys = 1
+ .put(0.toByte).put(0.toByte) // offset[0] = 0
+ .put(1.toByte).put(0.toByte) // offset[1] = 1 (one key byte)
+ .put('a'.toByte) // key "a"
+ .array()
+ // isCanonical inspects only the metadata at this step, so any value bytes
suffice.
+ assert(!VariantBuilder.isCanonical(parse("1").getValue, meta),
+ "a 2-byte offset width where 1 byte fits is not canonical")
+ }
+
+ // ----- isCanonical: object / array structure -----
+
+ test("isCanonical rejects a dictionary with an unused key") {
+ val b = new VariantBuilder(false)
+ b.addKey("unused")
+ b.appendLong(1)
+ val withUnusedKey = b.result()
+ assert(!VariantBuilder.isCanonical(withUnusedKey.getValue,
withUnusedKey.getMetadata),
+ "a dictionary with an unreferenced key is not canonical")
+ }
+
+ test("isCanonical accepts already-canonical nested objects and arrays") {
+ assert(isCanon(parse("""{"a":{"b":1}}""")), "a canonical nested object is
accepted")
+ assert(isCanon(parse("""{"a":[1,2,3]}""")), "a canonical object-of-array
is accepted")
+ assert(isCanon(parse("[1,2]")), "a scalar array is accepted")
+ assert(isCanon(parse("{}")), "an empty object is accepted")
+ assert(isCanon(parse("[]")), "an empty array is accepted")
+ }
+
+ test("isCanonical accepts canonicalize's output for nested structures") {
+ val inputs = Seq(
+ """{"b":2,"a":1}""",
+ """{"z":{"b":1,"a":2},"m":3}""",
+ "[1,2,3]",
+ """{"a":[{"y":1,"x":2}],"b":{"d":4,"c":5}}""")
+ for (json <- inputs) {
+ assert(isCanon(canon(parse(json))), s"canon output must be structurally
canonical: $json")
+ }
+ }
+
+ test("isCanonical rejects a non-minimal array offset width") {
+ val elem = parse("1").getValue // INT1(1), a 2-byte canonical scalar,
reused as the element
+ val arrayHeader = ((0 << (VariantUtil.BASIC_TYPE_BITS + 2)) |
+ ((2 - 1) << VariantUtil.BASIC_TYPE_BITS) | VariantUtil.ARRAY).toByte //
2-byte offset width
+ val arr = java.nio.ByteBuffer.allocate(1 + 1 + 2 + 2 + elem.length)
+ .order(java.nio.ByteOrder.LITTLE_ENDIAN)
+ .put(arrayHeader)
+ .put(1.toByte) // size = 1
+ .put(0.toByte).put(0.toByte) // offset[0] = 0
+ .put(elem.length.toByte).put(0.toByte) // offset[1] = data size
+ .put(elem) // element: INT1(1)
+ .array()
+ val nonMinimalArray = new Variant(arr, parse("1").getMetadata)
+ assert(isCanon(parse("[1]")), "sanity: a minimal-width array is canonical")
+ assert(!VariantBuilder.isCanonical(nonMinimalArray.getValue,
nonMinimalArray.getMetadata),
+ "an array with a 2-byte offset width where 1 byte fits is not canonical")
+ }
+
+ // ----- isCanonical: scalar values -----
+
+ test("isCanonical rejects a non-minimally-encoded integer") {
+ val int8Header =
+ ((VariantUtil.INT8 << VariantUtil.BASIC_TYPE_BITS) |
VariantUtil.PRIMITIVE).toByte
+ val int8One =
+ new Variant(Array[Byte](int8Header, 1, 0, 0, 0, 0, 0, 0, 0),
parse("1").getMetadata)
+ assert(!VariantBuilder.isCanonical(int8One.getValue, int8One.getMetadata),
+ "INT8(1) is not minimal-width")
+ assert(isCanon(parse("1")), "INT1(1) is canonical")
+ }
+
+ test("isCanonical rejects integer-valued and trailing-zero decimals") {
+ assert(!isCanon(parse("1.0")), "1.0 canonicalizes to the integer 1")
+ assert(!isCanon(parse("1.50")), "1.50 has a trailing zero")
+ assert(isCanon(parse("1.5")), "1.5 is a minimal fractional decimal")
+ }
+
+ test("isCanonical rejects -0.0 and non-canonical NaN") {
+ assert(!isCanon(buildFloat(-0.0f)), "float -0.0 is not canonical")
+ assert(!isCanon(buildDouble(-0.0d)), "double -0.0 is not canonical")
+ assert(isCanon(buildFloat(0.0f)), "float +0.0 is canonical")
+ assert(isCanon(buildDouble(1.5d)), "an ordinary double is canonical")
+ assert(isCanon(buildDouble(Double.NaN)), "the canonical double NaN is
canonical")
+
+ // Hand-craft a double NaN whose mantissa differs from the canonical
0x7ff8000000000000.
+ val doubleHeader =
+ ((VariantUtil.DOUBLE << VariantUtil.BASIC_TYPE_BITS) |
VariantUtil.PRIMITIVE).toByte
+ val nanBytes =
java.nio.ByteBuffer.allocate(9).order(java.nio.ByteOrder.LITTLE_ENDIAN)
+ .put(doubleHeader).putLong(0x7ff8000000000001L).array()
+ val nonCanonicalNaN = new Variant(nanBytes, parse("1").getMetadata)
+ assert(!VariantBuilder.isCanonical(nonCanonicalNaN.getValue,
nonCanonicalNaN.getMetadata),
+ "a non-canonical NaN bit pattern is not canonical")
+ }
+
+ test("isCanonical rejects a short string stored as long_str") {
+ val longStrHeader =
+ ((VariantUtil.LONG_STR << VariantUtil.BASIC_TYPE_BITS) |
VariantUtil.PRIMITIVE).toByte
+ val text = "hi".getBytes(java.nio.charset.StandardCharsets.UTF_8)
+ val bytes = java.nio.ByteBuffer.allocate(1 + 4 + text.length)
+ .order(java.nio.ByteOrder.LITTLE_ENDIAN)
+ .put(longStrHeader).putInt(text.length).put(text).array()
+ val longEncoded = new Variant(bytes, parse("1").getMetadata)
+ assert(!VariantBuilder.isCanonical(longEncoded.getValue,
longEncoded.getMetadata),
+ "a short string stored as long_str is not canonical")
+ assert(isCanon(parse("\"hi\"")), "a short-encoded string is canonical")
+ // A genuinely long string (> MAX_SHORT_STR_SIZE bytes) is canonical as
long_str.
+ val bigString = "\"" + ("x" * 70) + "\""
+ assert(isCanon(parse(bigString)), "a >63-byte string is canonical as
long_str")
+ }
+
+ // ----- NaN and pass-through type coverage -----
+
+ test("canonicalize and isCanonical handle a non-canonical float NaN") {
+ val floatHeader =
+ ((VariantUtil.FLOAT << VariantUtil.BASIC_TYPE_BITS) |
VariantUtil.PRIMITIVE).toByte
+ val bytes = java.nio.ByteBuffer.allocate(1 +
4).order(java.nio.ByteOrder.LITTLE_ENDIAN)
+ .put(floatHeader).putInt(0x7fc00001).array()
+ val nonCanonicalNaN = new Variant(bytes, parse("1").getMetadata)
+ assert(!bytesEqual(nonCanonicalNaN, buildFloat(Float.NaN)), "sanity: NaN
encodings differ")
+ assert(!VariantBuilder.isCanonical(nonCanonicalNaN.getValue,
nonCanonicalNaN.getMetadata),
+ "a non-canonical float NaN is not canonical")
+ assert(bytesEqual(canon(nonCanonicalNaN), canon(buildFloat(Float.NaN))),
+ "all float NaN bit patterns canonicalize to the same bytes")
+ assert(isCanon(buildFloat(Float.NaN)), "the canonical float NaN is
canonical")
+ }
+
+ test("canonicalize passes through date, timestamp, binary, and uuid
unchanged") {
+ def build(f: VariantBuilder => Unit): Variant = {
+ val b = new VariantBuilder(false)
+ f(b)
+ b.result()
+ }
+ val samples = Seq(
+ build(_.appendDate(19000)),
+ build(_.appendTimestamp(1234567890123L)),
+ build(_.appendTimestampNtz(1234567890123L)),
+ build(_.appendBinary(Array[Byte](1, 2, 3, 4))),
+ build(_.appendUuid(new java.util.UUID(1L, 2L))))
+ for (v <- samples) {
+ assert(bytesEqual(v, canon(v)), "a pass-through scalar must be unchanged
by canonicalize")
Review Comment:
**assert(bytesEqual(v, canon(v)))** is a no-op here: these are
already-canonical top-level values, so canonicalize returns v via the
**isCanonical** fast path (**appendCanonicalizedScalar** never runs) and the
assert compares v to itself. The **isCanon(v)** assert is fine; To actually
cover this case, nest the value in a non-canonical structure so a rebuild is
forced.
--
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]
