TSTLookup loses emoji and CJK Extension B suggestions after store() and load()

TSTLookup keeps its suggestions in a ternary search tree with one node per UTF-16 code unit (TSTAutocomplete.java:63), so a supplementary character such as the emoji 😀 (U+1F600) or the CJK Extension B character 𠮷 (U+20BB7) becomes two nodes, a high surrogate and a low surrogate. store() writes each node's split char as a one-char String with DataOutput.writeString (TSTLookup.java:244), which encodes UTF-8; a lone surrogate has no UTF-8 form and is written as EF BF BD, U+FFFD, and load() reads it back with readString().charAt(0) (:219). load() returns true, the count and the ASCII entries survive, but get() and every lookup whose prefix reaches such a character return nothing, BMP keys on the high side of such a node (fullwidth forms, halfwidth katakana) can be lost too, and a U+FFFD prefix can return keys it never matched. It is a regression from LUCENE-5404 (2014), which replaced the lossless writeChar/readChar: 4.6.1 round-trips, and every release from 4.7.0 to 10.5.2 and main does not. A layout-compatible fix keeps every existing file loadable; stores already written with such characters stay lossy until they are rebuilt (their tokens are stored whole, so a loader could also repair them; a probe showed this).

• TSTLookup: a prefix suggester in lucene/suggest. build() sorts the entries and inserts them into a ternary search tree; lookup(prefix, ...) walks the tree along the prefix and lists the entries below; get(key) returns a key's weight. Each node has a split char and three children: lower, equal (next char of the key) and higher.
• Surrogate pair: Java strings are UTF-16. A character above U+FFFF, such as 😀 U+1F600 (D83D DE00) or 𠮷 U+20BB7 (D842 DFB7), is stored as two chars, a high and a low surrogate. Neither half is a character on its own.
• Lookup.store / Lookup.load: "Persist the constructed lookup data" and "load it from a previously saved copy" (Lookup.java:236-252), for example to avoid rebuilding at startup.

1. TSTAutocomplete.insert makes one node per char: newNode.splitchar = s.charAt(x) (TSTAutocomplete.java:63). 𠮷野家 is four nodes: D842, DFB7, 91CE, 5BB6. The public TSTLookup.add(key, value) calls the same insert (TSTLookup.java:149-150).
2. TSTLookup.writeRecursively writes out.writeString(new String(new char[] {node.splitchar}, 0, 1)) (TSTLookup.java:244). writeString encodes UTF-8 (DataOutput.java:263-275, through new BytesRef(s), whose javadoc asks for text "with no unpaired surrogates", BytesRef.java:77, and UnicodeUtil.UTF16toUTF8), and UnicodeUtil writes EF BF BD (U+FFFD) for an "unpaired surrogate" (UnicodeUtil.java:231-235).
3. readRecursively reads in.readString().charAt(0) (TSTLookup.java:219): U+FFFD. Everything else (node layout, tokens, weights, the count) round-trips, so load() returns true.
4. The search compares the query's char with each node's split char (TSTAutocomplete.java:103-114). A query char D842 meets a node that now holds FFFD, goes to the lower child, and finds nothing.

 before store()                             after load()
  hi: D83D  first half of 😀                  hi: FFFD
      lo: 'a' p p l e -> apple/3                  lo: 'a' p p l e -> apple/3
      eq: DE00 ' smile' -> 😀 smile/4              eq: FFFD ' smile' -> 😀 smile/4
      hi: D842  first half of 𠮷                  hi: FFFD
          eq: DFB7 野 家 -> 𠮷野家/5                    eq: FFFD 野 家 -> 𠮷野家/5

 lookup("𠮷") after load():  D842 < FFFD -> lower child 'a' -> D842 > 'a' -> no higher child -> []
 lookup("�") after load():  FFFD = FFFD -> list everything below -> [😀 smile/4]

(The tree's top node is an empty root with split char U+0000; the dump starts at its higher child.)

Tokens are stored whole, so a prefix that ends before the first surrogate node still lists the key (the prefix a still finds a😀): the loss depends on the lookup path, not only on the key. ASCII keys and getCount() are unchanged.

• Who is exposed. TSTLookup is opt-in: an application picks it among the Lookup implementations. It is not deprecated and has no experimental tag of its own (class javadoc TSTLookup.java:36-42), though its base class Lookup is @lucene.experimental (Lookup.java:38). Only lookups that are persisted with store() and reloaded with load() are hit, and only for text with characters above U+FFFF, whether built with build() or added with add().
• Silent. load() returns true, getCount() is right and ASCII entries work. Only lookups whose path reaches a surrogate node change: users who type such a character, and users who type some BMP prefixes beside such a node (the fullwidth Ａ, U+FFFD), get missing or wrong suggestions. It does not depend on randomness: the same with assertions on and off and with every seed tried.
• Lasting. The saved file holds U+FFFD in place of the surrogate split chars, and no Lucene version, fixed or not, reads them back. The tokens and weights are stored whole, though: a white-box probe re-derived the lost split chars from them and got every answer back. Without such a repair step, the lookup has to be rebuilt from its source.
• How much changes. In the finder's random sweep (100,000 dictionaries of 1-6 keys, with U+00E9, U+1F600 and U+FFFD among the possible keys; 341,084,860 lookups over 20 suggester configurations), the round trip changed 245,800 TSTLookup results, and 0 with the fix. An independent test: 13 of 24 code-point-boundary prefixes change.
• Siblings are fine. FSTCompletionLookup and WFSTCompletionLookup round-trip the same keys.
• Downstream (read, not run). In a 2020 Lucene/Solr source snapshot, Solr's suggester reloads a persisted lookup from a storeDir, and TSTLookupFactory creates a TSTLookup. The Lucene.NET port carries the same two lines.
• How likely. Rare: it needs a persisted TSTLookup, such characters in the dictionary, and a lookup through them; no report of it was found.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<5> but was:<null>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:120)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.search.suggest.tst.TestTSTLookupStoreLoadSupplementary.testStoreLoadKeepsSupplementaryKey(TestTSTLookupStoreLoadSupplementary.java:37)

• The contract. Lookup.store: "Persist the constructed lookup data ... @return true if successful"; Lookup.load: "Discard current lookup data and load it from a previously saved copy" (Lookup.java:236-252). TSTLookup implements both and returns true (TSTLookup.java:267-280).
• The upstream test. TestPersistence.testTSTPersistence runs runTest(TSTLookup.class, true) (TestPersistence.java:50-52): it stores, reloads into a new TSTLookup and asserts that every key returns 1 hit with its exact weight (:82-105), for 15 ASCII words (:31-48).
• Nothing limits it to the BMP. No javadoc restricts TSTLookup to BMP text; it sorts its input with a comparator whose comment explains where supplementary code points go (TSTLookup.java:73-115; a TODO at :71 asks whether the comparator is needed at all); before store() every repro's supplementary key is found.
• History. Before LUCENE-5404 the split char was written with DataOutputStream.writeChar and read with readChar (4.6.1, TSTLookup.java lines 154 and 179), lossless for any UTF-16 unit. LUCENE-5404 (2014) moved store/load to DataOutput/DataInput and replaced them with writeString/readString().charAt(0). Its discussion (19 comments) and its 4.7.0 CHANGES entry never mention characters. A probe round-trips on 4.6.1 and not on 4.7.0.

The strongest "intended" case (the devil's-advocate verifier; the reviews by another model family rated it weak): writeString is documented as UTF-8, and since LUCENE-510 (2008) "If any text ... has illegal UTF-16 surrogate characters, these characters are now silently replaced with the Unicode replacement character U+FFFD"; store/load is an "Optional operation" with no format header or version, and Lookup is @lucene.experimental; no upstream test stores non-ASCII keys in a TSTLookup; and LUCENE-5404 changed the format on purpose.

Why it fails: the caller's text is valid; TSTLookup itself splits it into lone surrogates and passes one to writeString as if it were a string, so DataOutput behaves as documented and TSTLookup's use of it is the defect; writeString builds a new BytesRef(s), whose javadoc asks for text "with no unpaired surrogates" (BytesRef.java:77). "Optional" lets an implementation return false; it does not allow returning true and loading a different lookup. An untested input is not an unsupported one, and the comparator anticipates it. The format change was deliberate; the character loss was a side effect nobody discussed. Verdict: a defect (adjudication: confirmed, high).

What a maintainer may still choose: the second cross-model fact check rated "intended" weak but "acceptable / won't fix" moderate. A maintainer could document the limit, deprecate TSTLookup, or prefer a format break with a header to a hand-written decoder in an unversioned format.

All options make the split char round-trip; they differ in what happens to files already on disk. Executed matrix (two dictionaries, each stored by each build with store(OutputStream) and loaded by each build): a stock file read by fix B answers exactly as on stock; an ASCII-only file is byte-identical under fix B; a fix B file read by stock answers as today. Under fix A, both stock files in the probe load with load() = true and every lookup empty, the ASCII-only one included, which works today; a fix A file makes stock and fix B throw StringIndexOutOfBoundsException. The 10.5.2 and 9.12.3 readers print exactly what main's stock reader prints for all six files (executed). A pre-9.0 reader misreads the weights of every file written by 9.0 or later, stock files included (9.0 made the Directory API little-endian, LUCENE-9047; executed with 8.8.1: apple/2 reads back as apple/144115188075855872), independent of this bug. Options A-C do not repair files written by 4.7.0 to main: their surrogate nodes already hold U+FFFD. The tokens are stored whole, though, so a loader could re-derive the split chars (option D; a probe did it, no patch). Add the new test with whichever option, and a CHANGES note that such stores must be rebuilt (unless the fix adds option D).

writeRecursively and readRecursively call two small helpers instead of writeString/readString().charAt(0). A surrogate is written as length 3 plus ED A0 80..ED BF BF (the same length as today's EF BF BD); that byte pattern never occurs in valid UTF-8 (after ED the next byte must be 80-9F), so the reader can tell it from every file written today. Every other char goes through writeString as before. +32/-2 in TSTLookup.java.

private static void writeSplitChar(DataOutput out, char c) throws IOException {
  if (Character.isSurrogate(c)) {
    out.writeVInt(3);
    out.writeByte((byte) (0xE0 | (c >> 12)));
    out.writeByte((byte) (0x80 | ((c >> 6) & 0x3F)));
    out.writeByte((byte) (0x80 | (c & 0x3F)));
  } else {
    out.writeString(String.valueOf(c));
  }
}

private static char readSplitChar(DataInput in) throws IOException {
  int length = in.readVInt();
  byte[] bytes = new byte[length];
  in.readBytes(bytes, 0, length);
  if (length == 3 && (bytes[0] & 0xFF) == 0xED && (bytes[1] & 0xE0) == 0xA0) {
    return (char) (0xD000 | ((bytes[1] & 0x3F) << 6) | (bytes[2] & 0x3F));
  }
  return new String(bytes, 0, length, StandardCharsets.UTF_8).charAt(0);
}

Trade-offs

• No break for today's readers: old files load as today (still lossy until rebuilt); new files without supplementary characters are byte-identical, and with them differ only in the surrogate nodes (11 of 154 bytes in the probe); main's stock reader and the 9.12.3 and 10.5.2 readers load a new file exactly as today (executed), because readString decodes with the JDK's UTF-8 decoder, which turns each ED A0 80..ED BF BF into a String that starts with U+FFFD (a single U+FFFD for all 2048 forms on OpenJDK 25.0.3, executed). Pre-9.0 readers cannot read any file written today (see above).
• 32 lines instead of 2, and a hand-written decoder for one byte pattern.
• The format stays unversioned; a maintainer may prefer to add a header at the same time (option C).
• Cost on load: one small byte[] per node, as readString allocates today.
• readSplitChar checks the first two bytes (ED, then A0-BF) but not that the third is 80-BF; every file store() writes satisfies that, but a reviewer may ask for the check. The new test covers two surrogate pairs; a production test may add boundary cases like the probe's.
• A maintainer may prefer option C, or option A with a header in a major release, to a hand-written decoder in an unversioned format (the second cross-model fact check's view).

What the checks validated

• Gradle, scratch worktree of a9779ef3c193, JDK 25: stock + the new test fails 2 of 2 with assertions on and off; with the fix, the new test and TestPersistence (4 tests) pass with assertions on and off; the whole lucene/suggest module, 32 suites, 238 tests (7 skipped), 0 failures with assertions on and off; :lucene:suggest:check -x test (ecjLint, forbiddenApis, checkGoogleJavaFormat) passes.
• Standalone runner: the new test 2 of 2 pass with -ea and -da.
• Compatibility matrix as described above (executed), including the 10.5.2, 9.12.3 and 8.8.1 readers.
• Every surrogate value: 1,031 keys covering D800-DFFF plus BMP keys at U+D7FF, U+E000, U+FFFD, U+FFFE, U+FFFF; 3,093 checks after a round trip: stock changes 3,078, fix B (-ea and -da) 0, fix A 0. The fix B bytes hold 2,048 03 ED A0..BF 80..BF forms and one 03 EF BF BD (the real U+FFFD key).

out.writeVInt(node.splitchar) / (char) in.readVInt(). +2/-2.

-    node.splitchar = in.readString().charAt(0);
+    node.splitchar = (char) in.readVInt();
...
-    out.writeString(new String(new char[] {node.splitchar}, 0, 1));
+    out.writeVInt(node.splitchar); // a lone surrogate must survive (writeString maps it to U+FFFD)

Trade-offs

Simplest, lossless, and ASCII nodes get 1 byte smaller (the ASCII file is 337 instead of 392 bytes). But every node's byte layout changes and nothing marks the format: a fixed reader misparses files written by 4.7.0 to main (both old files in the probe loaded with load() = true and every lookup empty, the ASCII-only one included), and an older reader threw StringIndexOutOfBoundsException on both new files (executed). Acceptable only with an explicit "rebuild your lookups" note in a major release, or together with option C.

What the checks validated

Gradle: the new test and TestPersistence pass with assertions on and off; the whole module, 238 tests, passes with assertions on; checkGoogleJavaFormat passes. Standalone: 2 of 2 pass with -ea and -da; the finder's and the independent reproducer's tests pass with it.

Write a header (for example with CodecUtil.writeHeader) and the split char with writeVInt or writeShort; read headerless files with today's decoding. Not built.

Trade-offs

Lets the format evolve later. Detecting "no header" is not free: today's files start with a VLong count, so the reader must tell the header's magic bytes apart from a count. The LUCENE-5404 discussion already noted the missing codec header.

Each node's split char equals token.charAt(depth) for any token stored at or below the node on its eq side, where depth is the number of eq edges from the root (TSTAutocomplete.insert advances the char index only on eq, TSTAutocomplete.java:57-86). A loader can re-derive every split char after readRecursively, keeping the tree shape. Combined with B or C, files written by 4.7.0 to main would answer correctly again. Executed only as a white-box probe on the stock files: for the supplementary file it changed the 4 surrogate nodes back and every answer then equals a fresh build; the ASCII file was unchanged.

Trade-offs

One more pass over the tree on load. Only a white-box probe exists: no patch, test or review.

Method: randomized differential translation validation on the stock main jars (the study's "semi-formal" tier). A hunt unit, "suggest lookups, cross-implementation differential", 2026-10-27.

• 20 configurations of seven Lookup classes (TSTLookup, FSTCompletionLookup, WFSTCompletionLookup, AnalyzingSuggester, FuzzySuggester, AnalyzingInfixSuggester, BlendedInfixSuggester; not every Lookup: FreeTextSuggester, for example, was not modelled) were run against an independent reference written from their javadoc, plus a store/load round trip that must reproduce every result list and getCount().
• Scope R1: 100,000 random dictionaries of 1-6 entries over {a,b,c}^1..3 plus keys with U+00E9, U+1F600 and U+FFFD; 341,084,860 lookups over 20 suggester configurations. The class "TST RT:changed" (a TSTLookup result that differs after the round trip) appeared 245,800 times on the stock jar and 0 times with the fix shadowed.
• The mechanism (writeString of a one-char String) had first been noticed while writing the model. The ASCII-only bounded-exhaustive scope (596,908 dictionaries) could not reach it.
• An AI finder then wrote the public-API JUnit, and independent AI tools reproduced, reviewed and judged it (see the checks).