[C++][Java] Cross language incompatability when working with maps

[le-michael]

Summary

Java and C++ have different string compare logic resulting in incompatible binaries when sending between services that are built in different languages.

Investigation

According to the internals documentation, the canonical comparison approach should be using strcmp as the comparison algorithm for strings.
https://flatbuffers.dev/internals/

The C++ implementation follows this logic according to its code generator

flatbuffers/src/idl_gen_cpp.cpp

Lines 2608 to 2610 in 81edeb1

	code_ += " int KeyCompareWithValue(const char *_{{FIELD_NAME}}) const {";
	code_ += " return strcmp({{FIELD_NAME}}()->c_str(), _{{FIELD_NAME}});";
	code_ += " }";

The Java implementation does not follow this and implements their own algorithm

flatbuffers/java/src/main/java/com/google/flatbuffers/Table.java

Lines 279 to 296 in 81edeb1

	/**
	* Compare string from the buffer with the 'String' object.
	*
	* @param offset_1 An 'int' index of the first string into the bb.
	* @param key Second string as a byte array.
	* @param bb A {@code ByteBuffer} to get the first string.
	*/
	protected static int compareStrings(int offset_1, byte[] key, ByteBuffer bb) {
	offset_1 += bb.getInt(offset_1);
	int len_1 = bb.getInt(offset_1);
	int len_2 = key.length;
	int startPos_1 = offset_1 + Constants.SIZEOF_INT;
	int len = Math.min(len_1, len_2);
	for (int i = 0; i < len; i++) {
	if (bb.get(i + startPos_1) != key[i]) return bb.get(i + startPos_1) - key[i];
	}
	return len_1 - len_2;
	}

As a result the binaries generated from one language will be incompatible with another.

Reproduction

Summary

Because C++ compares strings using unsigned bytes (where 97 < 195), it sorts the map keys as ["a", "é"]. However, Java's Table.compareStrings() implementation uses signed bytes (where -61 < 97), meaning it expects the binary's keys to be sorted as ["é", "a"].

Schema:

table Entry {
      key: string (key);
      value: int;
}

table Map {
      entries: [Entry];
}

root_type Map;

Data Encoded:

We are encoding a vector of Entry tables containing two elements:

{"key": "a", "value": 1}
{"key": "é", "value": 2}

C++ Binary

000000 0c 00 00 00 00 00 06 00 08 00 04 00 06 00 00 00  >................<
000010 04 00 00 00 02 00 00 00 08 00 00 00 20 00 00 00  >............ ...<
000020 ec ff ff ff 08 00 00 00 01 00 00 00 01 00 00 00  >................<
000030 61 00 00 00 08 00 0c 00 04 00 08 00 08 00 00 00  >a...............<
000040 08 00 00 00 02 00 00 00 02 00 00 00 c3 a9 00 00  >................<
000050

Java Binary

000000 0c 00 00 00 00 00 06 00 08 00 04 00 06 00 00 00  >................<
000010 04 00 00 00 02 00 00 00 1c 00 00 00 04 00 00 00  >................<
000020 f4 ff ff ff 1c 00 00 00 01 00 00 00 08 00 0c 00  >................<
000030 04 00 08 00 08 00 00 00 10 00 00 00 02 00 00 00  >................<
000040 01 00 00 00 61 00 00 00 02 00 00 00 c3 a9 00 00  >....a...........<
000050

[aardappel]

So far, we've always treated "whatever C++ does" as the gold standard for any differences, since it was the original implementation language, and it is probably most widely deployed. That entails Java is the one that would have to be fixed.

The problem is that presumably the Java binary search code has the same "bug" in it.

That in turn means that if we fix it, that any Java-only projects, which so far were consistent, may stop working when new code (using a new unsigned binary search) reads old data (ordered with old signed buffer construction).

So while projects that have C++ and Java interop would benefit from this being fixed, Java only projects would benefit from it not being fixed.

That said, noone has ever reported this bug, given that the map feature is a bit niche, and its use in Java is maybe even more niche, and its use with upper-bit-set characters is maybe further niche. Which would entail that maybe we can just fix it and it will be fine.

If we want to be super safe, we could introduce a flag that turns the fix on or off. TBD if it should be default on or off. But again it may be cleaner to just fix it, and add the flag if we ever get reports of data not reading correctly.

Also, whoever fixes this would be nice to do a quick check on other languages to see if these bytes are read signed or unsigned.

[le-michael]

One issue with the C++ implementation is that strcmp does not support strings with null-terminated bytes. For full interop compatibility we should consider fixing the C++ implementation to use memcmp which it already partially is when sorting vectors. IIUC this algorithim discrepancy means that the C++ map implementation does not work for clients only use C++ if it's encoding strings with bytes > 128.

For this fix i'm proposing we make

1. memcmp the canonical string compare algorithm for C++
2. Fix the lookup method in C++ to use memcmp since all binaries are already encoded with memcmp
3. Update the java impl to have a memcmp compatible comparator
4. Flag guard this with new sorting behaviour in java and other langauge with --memcmp-sort or --interop-compat-sort or something better
5. Update the documentation to mention memcmp is the canonical sort algorithm for future impls.

---

I generated an audit of all the current implementations for future reference.

• C++

  • Signed vs. Unsigned: Unsigned (strcmp and memcmp both evaluate memory as unsigned char per the C/C++ standard).
  • Aligns with strcmp algorithm: Mixed. Lookups using const char* strictly use strcmp (stops at null), as seen in idl_gen_cpp.cpp#L2608-L2610. However, sorting the vector uses flatbuffers::StringLessThan which is length-bounded, as seen in buffer.h#L93-L97.

• Java

  • Signed vs. Unsigned: Signed (Java's byte type is a signed 8-bit integer).
  • Aligns with strcmp algorithm: No. It performs a length-bounded comparison.
  • Implementation Link: Table.java#L286-L296

• C#

  • Signed vs. Unsigned: Unsigned (The Table.CompareStrings runtime method evaluates byte as an unsigned 8-bit integer).
  • Aligns with strcmp algorithm: No. It performs a length-bounded comparison.
  • Implementation Link: Table.cs#L200-L216

• Go

  • Signed vs. Unsigned: Unsigned (Go's byte is an alias for uint8).
  • Aligns with strcmp algorithm: No. It leverages bytes.Compare, which evaluates slices purely based on their lengths.
  • Implementation Link: idl_gen_go.cpp#L989

• Kotlin

  • Signed vs. Unsigned: Signed (Kotlin's Byte is a signed 8-bit integer).
  • Aligns with strcmp algorithm: No. It performs a length-bounded comparison.
  • Implementation Link: Flatbuffers.kt#L320-L331

• Swift

  • Signed vs. Unsigned: Signed (The runtime explicitly reads and casts bytes to Int8, a signed 8-bit integer).
  • Aligns with strcmp algorithm: No. It utilizes explicit length bounds for iteration.
  • Implementation Link: Table.swift#L250-L269

• Rust

  • Signed vs. Unsigned: Unsigned (Rust's str::cmp delegates to u8 unsigned slice comparisons).
  • Aligns with strcmp algorithm: No. Slice comparisons are strictly bounded by their length.
  • Implementation Link: idl_gen_rust.cpp#L2511-L2514

[aardappel]

does switching to memcmp only extend the set of strings which will work correctly, or does it also change behavior for previously serialized data?

If the former then I think I agree with the plan, if the latter, then I'd say C++ must be included in opt-in behavior change with an explicit switch. We simply have too much data in the wild to risk any of it silently not reading anymore.

[le-michael]

Yup it's the former, this change fixes the C++ lookup behaviour and extends the set of strings.

Encoding string compare:

flatbuffers/include/flatbuffers/buffer.h

Lines 91 to 97 in 81edeb1

	// Lexicographically compare two strings (possibly containing nulls), and
	// return true if the first is less than the second.
	static inline bool StringLessThan(const char* a_data, uoffset_t a_size,
	const char* b_data, uoffset_t b_size) {
	const auto cmp = memcmp(a_data, b_data, (std::min)(a_size, b_size));
	return cmp == 0 ? a_size < b_size : cmp < 0;
	}

Lookup by key string compare:

flatbuffers/src/idl_gen_cpp.cpp

Lines 2606 to 2609 in 81edeb1

	if (is_string) {
	// Compares key against a null-terminated char array.
	code_ += " int KeyCompareWithValue(const char *_{{FIELD_NAME}}) const {";
	code_ += " return strcmp({{FIELD_NAME}}()->c_str(), _{{FIELD_NAME}});";