BooleanPerceptronClassifier sorts its FST keys as Java Strings, so a fullwidth-letter term next to an emoji term loses its weight

BooleanPerceptronClassifier (the experimental lucene/classification module) keeps one weight per indexed term in an FST. It stages the weights in a ConcurrentSkipListMap<String, Double>, whose order is Java String order (UTF-16 code units), and adds the keys' UTF-8 bytes to a BYTE1 FSTCompiler in that order. FSTCompiler.add requires byte order and checks it only with an assert. The two orders disagree exactly when two terms first differ at a character where one is supplementary (most emoji, CJK Extension B, mathematical letters) and the other is in U+E000..U+FFFF (fullwidth and halfwidth forms, CJK compatibility ideographs, presentation forms and ligatures, private use, U+FFFD). Then the public constructor throws AssertionError with assertions on; with assertions off it silently builds an FST from out-of-order input whose affected weights read back as missing. Trained on "ｓａｌｅ ｓａｌｅ ｓａｌｅ" -> true and "🎉" -> false with the default bias 2, assignClass("ｓａｌｅ") returns (false, 0.632) instead of (true, 0.393). In larger term sets one such document, labelled or not, made every tested probe text classify false or made training throw ArrayIndexOutOfBoundsException. Every release checked from 5.0.0 to 10.5.2, and main, is affected. An index vocabulary of only ASCII, or of emoji next to ordinary CJK, kana or Hangul, cannot trigger it. Keying the map by the terms' bytes (BytesRef) fixes it; the repro and the whole classification test suite pass with that change.

• BooleanPerceptronClassifier (lucene/classification, @lucene.experimental): a perceptron that assigns true or false to a text. Its javadoc: the weights "are calculated using TermsEnum#totalTermFreq ... and then a corresponding FST is used for class assignment" (BooleanPerceptronClassifier.java:50-56). assignClass(text) sums the FST weights of the text's tokens and answers output >= bias, with score 1 - exp(-|bias - output| / bias) (:222-240). The default bias is the average total term frequency (:99-105).
• FST and FSTCompiler: Lucene's compact sorted map from byte strings to outputs. FSTCompiler.add must receive each key "sorted after the previous one according to IntsRef#compareTo" (FSTCompiler.java:840-847), which for a BYTE1 FST of UTF-8 terms is unsigned byte order. The order is checked only by an assert (:854-855).
• UTF-16 vs UTF-8 order: Java's String.compareTo compares UTF-16 code units. A supplementary character is a surrogate pair D800-DBFF DC00-DFFF, which sorts below E000-FFFF. In UTF-8 a supplementary character starts with byte F0-F4 and a character in U+E000..U+FFFF with EE-EF, so byte order puts them the other way round. Below U+D800 the two orders agree.

1. The constructor reads every term of the text field over the whole reader from a TermsEnum (:90, :119-123), which yields them in UTF-8 byte order.
2. It decodes each with utf8ToString() into SortedMap<String, Double> weights = new ConcurrentSkipListMap<>() (:117, "TODO : remove this map as soon as we have a writable FST"), which re-sorts them in UTF-16 order.
3. updateFST iterates the map, re-encodes each key with copyChars and calls fstCompiler.add on a BYTE1 compiler in map order (:208-220), after the initial fill (:124) and after misclassified training documents (:203-205).
4. With assertions on, FSTCompiler.add throws AssertionError: inputs are added out of order from the public constructor. With assertions off, the FST is built anyway. In the two-document case the root keeps its two arcs as a plain list in the order F0, EF; a list lookup gives up at the first label larger than the one it seeks (FST.java:1093-1107), so "ｓａｌｅ" (EF ...) reads back as missing. With "ｓａｌｅ" labelled true, training misclassifies its document and updateWeights writes 0 for it (:200); with the labels swapped, both training documents already get their labelled class, no update happens, and only the score of "ｓａｌｅ" is wrong.
5. In larger term sets, nodes stored with fixed-length arcs take their label range from the first and last label (FSTCompiler.java:540) and their presence bits from label differences (:798, checked only by asserts at :797 and :808-810), so a node can be read misaligned: every weight in it unreadable, or ArrayIndexOutOfBoundsException. This explanation was checked for one root shape (14 of 14 cases); deeper nodes and other layouts were not mapped.
6. A Z3 model of both orders (strings of up to 2 Unicode scalars) confirms they disagree exactly when, at the first differing character, one is supplementary and the other in U+E000..U+FFFF (6 of 6 checks as expected).

One document can switch the model off (assertions off). A dense ASCII training set of 8 labelled documents plus one unlabelled document "😀 ａ": all 8 probe texts classify false with output 0 ("apple bonus cash" is true, output 6, when that document is "一 丁" instead). The same when the document is deleted before training and not yet merged away, because the FST keys come from the term dictionary. Over 12 random 300-document corpora plus one such document: 6 throw ArrayIndexOutOfBoundsException during training (where a message is recorded: Index -1 out of bounds for length 32768), and in the other 6 every probe text gets output 0. With the fix none of this happens. These corpora are synthetic (300 labelled documents from a 400-word vocabulary of ASCII letters and digits, plus one fixed unlabelled trigger document): they show that the damage depends on the layout of the whole term set, not how often it happens in natural-language indexes.

• Who is exposed. Applications that train BooleanPerceptronClassifier (opt-in lucene/classification module, @lucene.experimental). Nothing in Lucene constructs the class outside its tests, and no major downstream product is known to use it (Solr's classification update processor offers only k-NN and naive Bayes).
• Default vs opt-in. Inside the module no non-default setting is needed: the public constructor with batchSize 1 and the default bias, a whitespace analyzer, two documents. The stock StandardAnalyzer keeps the trigger characters (an independent check ran it with halfwidth katakana "ｾｰﾙ" and fullwidth "ｓａｌｅ" next to "🎉"). Width folding removes only some trigger forms: CJKWidthFilter folds fullwidth ASCII (U+FF01..U+FF5E) and halfwidth katakana (U+FF65..U+FF9F) only; NFKC also folds ligatures such as U+FB01, compatibility ideographs such as U+F900 and halfwidth Hangul, but leaves private-use characters and U+FFFD unchanged. Neither was run as a classifier test, and other analyzers were not tested.
• What text hits it. Informal or mixed-script text: an emoji word next to a word starting with a fullwidth Latin letter or halfwidth katakana (common in Japanese text), a CJK compatibility ideograph, a ligature from PDF extraction (such as U+FB01 "fi") or U+FFFD. An ASCII-only vocabulary never triggers it, and neither does emoji next to ordinary CJK ideographs, kana or Hangul (all below U+D800). Once a trigger pair is in the index, though, ASCII texts can lose their weights too.
• Who triggers it. Any document in the reader: labelled or not, and a deleted one until a merge drops its terms. The training query and the class-field clause do not restrict the FST's terms; they select the documents used for updates and, as scoring clauses, may also reorder them (the separate LFV-684). Text passed to assignClass cannot trigger it.
• Silent in production. With assertions off there is no error: weights are lost, in some term sets all of them. With assertions on (how Lucene's own tests run), the public constructor throws an internal AssertionError.
• Deterministic. Every training run on such an index is affected, again on every retraining while the terms stay in the index.
• How likely. Plausible but quiet: nobody has reported it since 5.0.0 (2015), which fits a small user base.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: inputs are added out of order lastInput=[f0 9d 90 80] vs input=[ef a4 80]
       org.apache.lucene.util.fst.FSTCompiler.add(FSTCompiler.java:855)
       org.apache.lucene.classification.BooleanPerceptronClassifier.updateFST(BooleanPerceptronClassifier.java:216)
       org.apache.lucene.classification.BooleanPerceptronClassifier.<init>(BooleanPerceptronClassifier.java:124)
       org.apache.lucene.classification.TestBooleanPerceptronUtf8Order.testHighBmpAndSupplementaryTerms(TestBooleanPerceptronUtf8Order.java:53)

• The callee's contract. FSTCompiler.add: "The provided input must be sorted after the previous one according to IntsRef#compareTo" (FSTCompiler.java:840-847). The caller that breaks it is the classifier's own private updateFST, fed from its own private map; the user passes an ordinary index.
• Lucene documents this exact pitfall. util/fst/package-info.java:38-40: keys "must be provided to Builder in Unicode code point (UTF8 or UTF32) sorted order. Note that sorting by Java's String.compareTo, which is UTF16 sorted order, is not correct and can lead to exceptions while building the FST". The warning came from #10095 / LUCENE-9053 (2019), where a user's own code hit the same assertion.
• Lucene's own practice. SynonymMap.Builder.compareCodePoints: "Compares by Unicode code point, which matches the UTF-8 byte order the FST requires" (SynonymMap.java:196-197, used at :261), with TestSynonymMap.testSupplementaryCharsSortAfterHighBMP for exactly this boundary (#16834).
• The class's own documentation describes the weights and the FST lookup (BooleanPerceptronClassifier.java:50-56). No javadoc, package doc, CHANGES or MIGRATE entry limits the text to ASCII or to characters below U+D800.
• Why the tests never caught it. Every perceptron test uses ASCII text: a fixed English sample and TestUtil.randomSimpleString (a..z) (ClassificationTestBase.java:146, :254-267).
• History. The String-ordered map is in the class's first commit (2013, TreeMap<String,Double>); the LUCENE-4818 discussion never mentions character order or Unicode.

The strongest "works as designed" case (a refute-lens review by another model family rated it moderate; the independent reproducer, an intended-lens review and the devil's advocate rated it weak or rejected it): the class is @lucene.experimental and promises no accuracy; FSTCompiler puts the sorted-input duty on its caller; all upstream perceptron tests are ASCII; the map is a self-described temporary hack ("TODO : remove this map ..."); and "renaming tokens must not change the class", the first oracle used, is not a documented contract.

Why it fails: experimental status allows API changes, not a constructor that throws an internal assertion or drops weights it was given for ordinary indexed Unicode. The caller that owns the precondition is this class. The repro's expected values follow from the documented weighting and the code's own formulas, not from renaming, and the controls show the same corpus gives them when the two orders agree. ASCII-only tests are a coverage gap, not a statement of intent. Eleven years without a report fits a small user base, not a design choice; width folding is an analyzer option the class never asks for, and it does not fold every trigger; LUCENE-9053 was resolved Invalid because the out-of-order caller there was the user's own code, while here it is Lucene's own class. Verdict: a defect (adjudication: confirmed, high; every executed check: real).

Two fixes were run, the recommended one through gradle. A one-line alternative orders the existing String map by UTF-8 bytes. Separately, FSTCompiler.add could check its input order for real instead of only with an assert; that is a core-wide change with its own cost question. Workaround until a fix ships: fold width in the text field's analyzer. CJKWidthFilter folds only fullwidth ASCII (U+FF01..U+FF5E) and halfwidth katakana (U+FF65..U+FF9F); NFKC also folds ligatures (U+FB01), compatibility ideographs (U+F900) and halfwidth Hangul. Private-use characters and U+FFFD stay under both, so neither removes every trigger (not run as a classifier test).

The map becomes SortedMap<BytesRef, Double>, filled with BytesRef.deepCopyOf(term) in the constructor and in updateWeights; updateFST adds Util.toIntsRef(entry.getKey(), scratchInts) directly; BytesRefBuilder, utf8ToString() and copyChars go. +8/-12 in BooleanPerceptronClassifier.java.

    // TODO : remove this map as soon as we have a writable FST
    // keyed by the terms' UTF-8 bytes: BytesRef order is the input order FSTCompiler requires
    SortedMap<BytesRef, Double> weights = new ConcurrentSkipListMap<>();
    ...
      weights.put(BytesRef.deepCopyOf(textTerm), (double) termsEnum.totalTermFreq());
    ...
    for (Map.Entry<BytesRef, Double> entry : weights.entrySet()) {
      fstCompiler.add(Util.toIntsRef(entry.getKey(), scratchInts), entry.getValue().longValue());
    }

Trade-offs

• BytesRef.compareTo is unsigned byte order, which is the order of the BYTE1 labels, so the order is right by construction; no allocation per comparison.
• Unchanged behaviour on text that is not affected today (ASCII, or every character below U+D800): the orders agree there and the keys are the same bytes.
• Cost: a BytesRef deep copy wherever the code builds a String today: once per dictionary term in the constructor, and once per term of each misclassified training document in updateWeights; not benchmarked.
• It edits the same updateWeights lines as the fix for the sibling batchSize bug (LFV-680); the two are compatible in intent, but neither diff applies on top of the other, so combining them needs a small manual merge (not run).

What the checks validated

• Scratch worktree of main a9779ef3c193 with the diff applied, gradle: the new test passes 4 of 4, and the whole :lucene:classification:test passes with assertions on and off (13 suites, 47 tests including the new 4, 0 failures, 1 @Monster test skipped).
• :lucene:classification:check -x test passes (checkGoogleJavaFormat, ecjLintMain, ecjLintTest and forbiddenApisMain ran; forbiddenApisTest was up to date from the stock run, where it ran and passed on the same test sources).
• Standalone runner with the fixed class shadowed: this doc's test (on and off), the independent reproducer's test (4 of 4, on and off) and the follow-up probe (unlabelled and deleted documents: trigger equals control; 12 random corpora: 0 throw, 0 changed) pass.

The finder's change: new ConcurrentSkipListMap<>((a, b) -> new BytesRef(a).compareTo(new BytesRef(b))). +3/-1.

    SortedMap<String, Double> weights =
        new ConcurrentSkipListMap<>((a, b) -> new BytesRef(a).compareTo(new BytesRef(b)));

Trade-offs

Smallest diff. It encodes both Strings into new byte arrays on every comparison (about V log V encodings to fill a map of V terms); cost not measured.

What the checks validated

This doc's test with the class shadowed: 4 of 4 pass, on and off. Earlier: every verifier's test and the 42 upstream classification tests pass with it.

Compare by code point, as SynonymMap.Builder.compareCodePoints does; code point order equals UTF-8 byte order.

Trade-offs

No allocation, but that helper is package-private in analysis-common, which lucene/classification's main code does not depend on (only its tests do), so its 16 lines would be copied. Not run.

Replace the assert with a check that throws, so this silent corruption, and any other caller's, becomes an exception.

Trade-offs

Core-wide; changes a hot path for every FST build, and Lucene asks that robustness changes not slow hot paths. Cost not measured; other FSTCompiler callers were not audited for this pattern. Not a fix for this class on its own. Not run.

Method: non-formal (the hunt's tier for finds made by reading code; a model characterised the trigger afterwards). A hunt unit (classification), 2026-10-26, stock main jars.

• The unit's primary method was transcribing the classifiers' score pipelines into an SMT model. While reading BooleanPerceptronClassifier for it, the finder noticed the String-keyed sorted map feeding a BYTE1 FSTCompiler.
• A Z3 QF_BV model of UTF-16 versus UTF-8 lexicographic order over strings of up to 2 Unicode scalars then characterised the trigger: a satisfiable witness that the orders differ, two unsatisfiable implications showing they differ exactly when, at the first differing scalar, one is supplementary and the other in U+E000..U+FFFF, and three vacuity probes (6 of 6 as expected).
• A public-API JUnit test reproduced it on the stock jars of main, 10.5.2 and 9.12.3, and the finder's fix made it pass along with the upstream classification tests.