ICUCollationKeyAnalyzer.normalize ignores the collator, so QueryParser range queries on ICU collation-key fields match the wrong documents

ICUCollationKeyAnalyzer (analysis-icu) indexes each whole value as its ICU collation key, so that a range over the field follows the language's sort order. It does not override Analyzer.attributeFactory(String), the factory that Analyzer.normalize uses to build its term, so normalize returns the plain UTF-8 bytes instead of the key the index holds. The classic QueryParser builds both bounds of every range with normalize, so [a TO c] becomes a byte range from [61] to [63] over a field whose term for b is [2d 1 5 1 5 0]: 0 hits instead of 1. Other ranges miss documents inside the collated range and return documents outside it (731 of 1,280 parsed ranges wrong in a bounded differential). Default IndexWriterConfig and QueryParser, one document, no error. The java.text twin CollationKeyAnalyzer has the one-method override and is correct. Introduced by LUCENE-7355 (6.2.0; default path from 7.0.0), a regression of a scenario LUCENE-4176 had fixed in 2012; still in 10.6.0 and on main.

1. Indexing. ICUCollationKeyAnalyzer.createComponents builds new KeywordTokenizer(factory, KeywordTokenizer.DEFAULT_BUFFER_SIZE), one token for the whole value (ICUCollationKeyAnalyzer.java:64-69). factory is an ICUCollationAttributeFactory (:53, :60-62) whose term attribute writes the collator's raw key as the term bytes (ICUCollatedTermAttributeImpl.java:46-54).
2. Normalization. Analyzer.normalize (public final, Analyzer.java:213) applies the normalization char filters, then builds a one-term StringTokenStream with attributeFactory(fieldName) (:233-236) and reads its bytes (:237).
3. The missing override. The default attributeFactory(String) returns TokenStream.DEFAULT_TOKEN_ATTRIBUTE_FACTORY (:293-295). ICUCollationKeyAnalyzer is final and has only a constructor and createComponents (ICUCollationKeyAnalyzer.java:52-70), so normalize returns UTF-8.
4. The parser. QueryParserBase.newRangeQuery sets start = getAnalyzer().normalize(field, part1) and end = getAnalyzer().normalize(field, part2) (QueryParserBase.java:550, :556) and returns a TermRangeQuery over them (:559-560); an open end stays null.
5. Result. TermRangeQuery compares unsigned bytes, so UTF-8 bounds against ICU keys select an arbitrary slice of the key space.

Stock: the range [61]..[63] does not contain [2d 1 5 1 5 0]. With the fix the bounds are the keys of a and c, and b's key lies between them. A term query b on the same field and parser matches, because it goes through tokenStream, which produces the key.

CollationKeyAnalyzer (java.text) builds the same KeywordTokenizer with its own factory and also overrides attributeFactory(String) to return it (CollationKeyAnalyzer.java:70-73), as does the test framework's MockBytesAnalyzer (MockBytesAnalyzer.java:36-39).

• Trigger. A field analyzed with ICUCollationKeyAnalyzer and a range parsed by the classic QueryParser; every bound other than * goes through normalize. Direct callers of Analyzer.normalize on this analyzer get UTF-8 too. Since 7.0.0 no parser setting avoids it (setAnalyzeRangeTerms was removed).
• Effect. Silent wrong results, both directions: in a bounded differential (every ordered pair of 16 words, including supplementary and 3-byte letters, times 5 ICU strengths, against the collator's own order) 731 of 1,280 parsed ranges were wrong, missing 3,814 documents and adding 750, and all 80 normalize checks differed from the indexed term. At primary strength [a TO b] misses a, ab, b, B and ä and returns Greek Β and β, whose keys fall between the bytes of a and b. With the fix: 0 and 0.
• The module's advertised use case. The analysis-icu overview lists "Efficient range queries over fields that contain terms in languages that use non-Unicode character orderings" (overview.html:97-100).
• Not affected: the java.text CollationKeyAnalyzer; TermRangeQuery built by hand from collation-key bytes (what the ICU tests do); ICUCollationDocValuesField; a downstream server's ICU collation field type that builds its bounds through tokenStream.
• Not claimed: prefix, wildcard and fuzzy terms over opaque keys, the flexible StandardQueryParser and SimpleQueryParser, to keep the report to one clear contract. This bug reaches them too: on stock, the flexible parser's [b TO d] returns 0 hits with the ICU analyzer and 3 with the java.text twin, and the fix makes it 3; the ICU prefix, fuzzy and SimpleQueryParser results also differ from the twin on stock and match it with the fix. The flexible parser also has a limitation of its own that hits both collation analyzers: it turns each normalized bound back into a string with utf8ToString() (TermRangeQueryNodeProcessor.java:136-139), so key bytes that are not valid UTF-8 do not survive.
• Likelihood: plausible. Deterministic for every parsed range on such a field, but a niche feature; many applications build key ranges by hand, and nobody has reported it since 7.0.0 (2017).

Single thread. The seed also randomises the test framework's environment, such as the directory, codec, locale and time zone (the DEADBEEF run drew locale mr and time zone Africa/Niamey); the outcome was the same in every recorded run, with assertions on and off, through gradle and the standalone runner. The analysis-icu module has no test dependency on the query parser today, so the run adds moduleTestImplementation project(':lucene:queryparser') to the dependencies block of lucene/analysis/icu/build.gradle.

The hunt's earlier 5-document form (a..e, [b TO d], expected 3, got 0) fails the same way on main and on the 10.6.0, 10.5.2, 9.12.3 and 9.1.0 release jars; it is supplementary and not needed to file.

Regression test: this same test, with the build.gradle line; it passes with the recommended fix.

cp $REPRO/TestICUCollationKeyAnalyzerRange.java $LUCENE/lucene/analysis/icu/src/test/org/apache/lucene/analysis/icu/
# add to the dependencies block of $LUCENE/lucene/analysis/icu/build.gradle:
#   moduleTestImplementation project(':lucene:queryparser')
cd $LUCENE && ./gradlew :lucene:analysis:icu:test --tests TestICUCollationKeyAnalyzerRange -Ptests.seed=DEADBEEF
# assertions off: add -Ptests.asserts=false (same failure)

# main 645d4fe14a20, gradle, -Ptests.seed=DEADBEEF (the same with -Ptests.asserts=false)
TestICUCollationKeyAnalyzerRange > testQueryParserRange FAILED
    java.lang.AssertionError: expected:<1> but was:<0>
        ...
        at org.apache.lucene.analysis.icu.TestICUCollationKeyAnalyzerRange.testQueryParserRange(TestICUCollationKeyAnalyzerRange.java:45)
:lucene:analysis:icu:test (FAILURE): 1 test, 1  failure

# standalone runner: main 645d4fe14a20 -ea / -da: fail 1/1, the same message
# the bytes (a main() probe): indexed term of "b" = [2d 1 5 1 5 0]; range bounds normalize("a") = [61], normalize("c") = [63]
# with the fix: the bounds are [2b 1 5 1 5 0] and [2f 1 5 1 5 0]; the test passes; :lucene:analysis:icu:test (SUCCESS): 159 tests, 10 skipped

• The contracts. Analyzer.normalize: "Normalize a string down to the representation that it would have in the index. This is typically used by query parsers ..." (Analyzer.java:202-207). Analyzer.attributeFactory(String): "Return the AttributeFactory to be used for analysis and normalization on the given FieldName" (:288-292). The ICU analyzer uses its factory for analysis and the default one for normalization; its javadoc names no exception (ICUCollationKeyAnalyzer.java:24-50).
• The twin and the stand-in. CollationKeyAnalyzer overrides attributeFactory (CollationKeyAnalyzer.java:70-73); so does MockBytesAnalyzer (MockBytesAnalyzer.java:36-39), which TestQueryParser.testByteTerms ("// LUCENE-4176", TestQueryParser.java:974-985) uses as the stand-in for the ICU case, because the query parser module does not depend on ICU. No test asserts that the ICU analyzer's normalize returns UTF-8; the ICU tests build key bounds by hand (TestICUCollationKeyAnalyzer.java:43-50).
• History. The 4.0 MIGRATE note (LUCENE-2514): "To perform collated range queries, use a suitable collating analyzer: CollationKeyAnalyzer or ICUCollationKeyAnalyzer, and set qp.setAnalyzeRangeTerms(true)." LUCENE-4176 (#5248, 2012) was reported against ICUCollatedTermAttributeImpl with a parsed range returning 0 hits; Robert Muir fixed the parser to "just consume the bytes". LUCENE-7355 (#8409, 2016): Adrien Grand wrote that "some consumers need to get the binary representation of terms, which depends on the AttributeFactory (#5248)" and that normalize "uses the same AttributeFactory as the default analysis chain"; the commits added the hook, then without an argument, with overrides in CollationKeyAnalyzer and MockBytesAnalyzer, and touched no file under analysis/icu. LUCENE-7429 (#8482) added a fieldName parameter to the hook (attributeFactory() became attributeFactory(String)) and updated the same two classes. ICUCollationKeyAnalyzer has never had the override.
• Consistency. On the same field, parser and analyzer, a term query matches and a range query does not; the java.text twin gives the right answer for both.

The strongest case: on LUCENE-7429 (#8482, 2016) Uwe Schindler wrote that using the same attribute types for normalization "is sometimes broken for use-cases, where TokenStreams create binary tokens. But those would never be normalized, I think (!?)". The classic parser's package doc says "Untokenized fields are best added directly to queries, and not through the query parser" (package-info.java:86-90), and this analyzer uses a KeywordTokenizer. The ICU tests build key bounds by hand, the module overview's QueryParser range example is stale (it calls removed APIs), and ICUCollationDocValuesField offers another route.

Why it fails: the remark ends in "(!?)"; Adrien Grand replied in the same thread with a possible counter-example (a non-default term attribute such as UTF-16 for CJK text), and the issue's commit kept and updated the override of the binary-token CollationKeyAnalyzer, which points to binary-token analyzers being normalized on purpose, not excluded. The package-doc advice concerns program-generated values ("dates, keywords"), not human text that an analyzer converts. The javadocs make no exception, the MIGRATE note names this analyzer for parsed collated ranges, and LUCENE-4176 fixed exactly this scenario. Verdict: the evidence strongly indicates an omission, not a documented exclusion.

Option A was built and run; B and C are alternatives that were not built.

Add the method the java.text twin has (CollationKeyAnalyzer.java:70-73), plus its import. For the PR, add the test of the minimal repro and the one test-dependency line in lucene/analysis/icu/build.gradle.

import org.apache.lucene.util.AttributeFactory;

@Override
protected AttributeFactory attributeFactory(String fieldName) {
  return factory;
}

Trade-offs

• No index change: the index already holds keys. What changes is the normalize result visible through the API, from UTF-8 to the key the index holds, for direct callers and every parser that uses it.
• Parsed prefix, wildcard and fuzzy terms on such a field then also see key bytes, as they already do with the java.text twin; those query types have no clear meaning over collation keys either way (not claimed).
• The flexible StandardQueryParser's ranges on such a field change too: [b TO d] goes from 0 to 3 hits in the side-parser run, matching the java.text twin.
• A consistency repair: normalize then agrees with the indexed term. It does not imply that hand-built TermRangeQuery bounds or ICUCollationDocValuesField are wrong; both stay as they are.
• The regression test adds a test-only dependency of analysis-icu on the query parser; without it, the same one-document check can assert normalize() against the indexed term.

What the checks validated

• Scratch worktree of 645d4fe14a20, JDK 25, gradle: the minimal test fails on stock and passes with the fix, assertions on and off.
• The whole lucene/analysis/icu module with the fix and the test: 159 tests in 17 suites, 10 skipped, 0 failures, assertions on and off (the upstream TestICUCollationKeyAnalyzer and TestICUCollationDocValuesField included).
• :lucene:analysis:icu:check -x test (format, ecjLint, forbiddenApis) passes once the test's long assertEquals line is wrapped as google-java-format asks (./gradlew tidy); the wrapped test passes.
• Standalone runner: the minimal test and the hunt's 5-document test pass with the fix, assertions on and off; the bounded differential finds 0 of 1,280 ranges and 0 of 80 normalize checks wrong.
• Not run: the lucene/queryparser module's own tests with the fix, the full Lucene suite, nightly tests.

Make Analyzer.normalize take the factory from the analyzer's own tokenizer, so no analyzer can miss the override.

Trade-offs

A broad core change that reverses a design decision: an earlier LUCENE-7355 patch did borrow the factory from the analysis chain, and Adrien Grand switched to the explicit method because that "makes us close the token stream before it has been consumed, which some analysis chains might not like"; on LUCENE-7429 Uwe Schindler also disliked creating a TokenStream just to get its attribute source.

Say in the javadoc that ranges on this analyzer must be built by hand from collation keys.

Trade-offs

Contradicts the normalize and attributeFactory javadocs, the 4.0 MIGRATE note and the java.text twin.

Method: bounded-exhaustive metamorphic testing on the stock main jars, by two hunt units at about the same time (2026-10-26).

• Relation N1: Analyzer.normalize(f, w) equals the single token that indexing produces for w, over about 20,000 short words (every word of 1-2 characters over a 110-character alphabet plus random longer ones) and 99 analyzer configurations; relation N2: the query parsers actually reach normalize. ICUCollationKeyAnalyzer failed N1.
• A differential of the java.text and ICU collation analyzers against the collator's own order (10 locales x 4 strengths, every string of up to 3 characters over a per-locale alphabet): only the ICU classic-parser range oracle disagreed, in 10,079 of 16,000 checks (0 of 16,000 for the java.text twin).
• An adjudication unit reduced it to one JUnit test, ran a new bounded differential (16 words x 5 strengths: 1,280 ranges, 80 normalize checks) on stock and with the fix, and swept the releases from 6.1.0 to main.