JapaneseCompletionFilter builds every romaji spelling of a reading with no bound: 32 kana throw OutOfMemoryError

JapaneseCompletionFilter (kuromoji, used by JapaneseCompletionAnalyzer for Japanese auto-completion) adds the romanized spellings of each reading as extra tokens at the same position. Nine single kana have more than one spelling in romaji_map.txt: シ (si/shi), ジ (zi/ji), チ (ti/chi), ツ (tu/tsu), ヅ (du/zu), フ (hu/fu), ヲ (wo/o), ン (n/nn), and ヂ (di/zi/ji); so do 114 two- and three-kana keystrokes, such as シャ (sya/sha), チャ (tya/cha/cya) and ッファ (4 spellings). KatakanaRomanizer.romanize builds the full product of those choices, eagerly, with no limit and no de-duplication, and the filter queues every result before it returns the first token.

A reading with n such keystrokes therefore gets 2^n (or 3^n, or more) spellings, and the filter emits one token per spelling plus the surface token: 16 x ン gives 65,537 tokens at one position, 20 x ン gives 1,048,577, and 32 x ン (INDEX mode, the default) or 32 x し (QUERY mode) throw OutOfMemoryError with a 2 GB heap. For ン most are duplicates: 2^n spellings, n+1 distinct strings. Because the whole product is built inside one incrementToken() call, LimitTokenCountFilter after the filter cannot help; QueryBuilder's clause limit and AnalyzingSuggester's determinize limit act only after analysis, so they reject some smaller expansions but cannot prevent the OutOfMemoryError at 32 characters; and an IndexWriter that analyzes such a field closes on the Error and drops its uncommitted documents. 64 characters of ordinary hiragana fail in both modes. Present since the filter was added in 9.0.0; every release from 9.0.0 to 10.6.0 (10.6.0 by reading) and main are affected.

• Reading: the katakana pronunciation of a token (from the dictionary, or the kana surface itself). In QUERY mode, consecutive all-kana tokens are joined into one reading.
• Romanized tokens: JapaneseCompletionFilter keeps the surface token and adds one token per romaji spelling of the reading, all at the same position (position increment 0), so a prefix typed in romaji can match.
• Ambiguous kana: romaji_map.txt gives two spellings for シ si/shi (:29), ジ zi/ji (:38), チ ti/chi (:47), ツ tu/tsu (:48), ヅ du/zu (:56), フ hu/fu (:72), ヲ wo/o (:118), ン n/nn (:119), and three for ヂ di/zi/ji (:55). 114 two- and three-kana keystrokes also have 2-4 spellings, for example シャ sya/sha (:33), チャ tya/cha/cya (:51) and ッファ (4, :292).

1. JapaneseCompletionAnalyzer() is INDEX mode (JapaneseCompletionAnalyzer.java:37-39): CJKWidthCharFilter -> JapaneseTokenizer(userDict, true, true, NORMAL) -> JapaneseCompletionFilter -> LowerCaseFilter (:47-59). A katakana run such as ン x 32 is one token. The tokenizer gives this unknown word no reading, so the filter uses the kana surface, converted to katakana, as the reading (JapaneseCompletionFilter.java:125-128).
2. In QUERY mode, CompletionTokenGenerator.addToken appends every further all-kana token to the pending one, with no length limit (JapaneseCompletionFilter.java:194-202), so し x 32 or a whole hiragana sentence becomes one reading.
3. generateOutputs (:217-233) queues the surface token, calls KatakanaRomanizer.getInstance().romanize(reading) (:228) and queues one token per returned spelling (:229-232).
4. romanize (KatakanaRomanizer.java:103-169) matches keystrokes greedily (:112). For a keystroke with several spellings it builds candidates x pendingOutputs new strings (:138-156; the copy at :148-149), "To produce all possible keystroke patterns" (:143-144). No limit, no de-duplication, one List (:168). So count(x^n) = c(x)^n: 2^n, or 3^n for ヂ. For ン, n+nn and nn+n are the same string: ンン gives nn, nnn, nnn, nnnn.
5. All of this happens in the first incrementToken() (JapaneseCompletionFilter.java:99-116 -> mayIncrementToken :118-141 -> finish :212-215 -> generateOutputs), before any token leaves the filter. The OutOfMemoryError is thrown in the product loop, at KatakanaRomanizer.romanize:148 or :149, depending on the run.
6. At 32 two-spelling kana the list would need 2^32 entries, more than a Java array can hold, so a bigger heap only moves the threshold (at 2 GB, 23 x ン works, 24 fails), not the failure at 32.

• Who is hit. Applications that chose JapaneseCompletionAnalyzer or JapaneseCompletionFilter (opt-in; no default chain uses it; factory name japaneseCompletion) and analyze text they do not fully control: an auto-complete box (QUERY mode, which targets unconverted kana input) or suggestion entries and document fields (INDEX mode). Downstream servers expose the filter as kuromoji_completion.
• Trigger size. 24-32 ambiguous keystrokes with the default constructors: a run of ン, し or ヂ, or about 64 characters of ordinary hiragana. Natural inputs are already heavy before that: 9,216 romanized tokens for the 22-char onomatopoeia ジャンジャンバリバリチャンチャンシャンシャン, 16,385 tokens for a 32-char hiragana sentence.
• Effect: a JVM-wide OutOfMemoryError, not a per-request exception.
  • In 4 of 8 runs a concurrent thread doing ordinary searches also hit an OutOfMemoryError (in one run it killed that thread), and its worst request latency rose from 27-53 ms to 590-1,720 ms while the expansion ran.
  • A JVM started with -XX:+ExitOnOutOfMemoryError terminates (the control without the flag survives).
  • An IndexWriter treats the Error as tragic and closes (IndexWriter.java:1625-1641): uncommitted documents are lost; the last commit stays intact (CheckIndex clean, a new writer works).
• No downstream Lucene bound prevents it. LimitTokenCountFilter(10) after the filter: still OutOfMemoryError. QueryBuilder (default maxClauseCount 1024): TooManyClauses from 10 x し (1,025 terms) and for the 32-char sentence, OutOfMemoryError at 32 x し, because the clause check runs after analysis. AnalyzingSuggester (index analyzer in INDEX mode, query analyzer in QUERY mode): lookup of 12 or 16 x し and of the 22-char onomatopoeia throws TooComplexToDeterminizeException; 20 x し throws OutOfMemoryError in TokenStreamToAutomaton with a 1 GB heap, and with a 2 GB heap it ran for 10 minutes, until the probe's timeout, in AnalyzingSuggester.replaceSep (Operations.topoSortStates) without a result; 32 x し throws OutOfMemoryError with 2 GB. The determinize limit acts only on the smaller inputs.
• A small raw length cap is an effective application-level workaround, and it must be small: 12 x ヂ already gives 531,442 tokens, 20 x ン 1,048,577.
• Releases before 10.6.0 also drain the queue quadratically (INDEX ン x 20: about 51 s on 10.5.2 and 9.12.3 vs 0.5-0.9 s on main); #16416 (10.6.0, released 2026-10-29) fixed only that drain, not the count.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: tokens for ン x 8 expected:<10> but was:<257>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.apache.lucene.analysis.ja.TestJapaneseCompletionDuplicateRomaji.testRomanizedTokensAreDistinct(TestJapaneseCompletionDuplicateRomaji.java:41)

• What the code promises. romanize javadoc: "Translates a sequence of katakana to romaji. An input can produce multiple outputs because a keystroke can be mapped to multiple romajis." (KatakanaRomanizer.java:99-102). The comment at :143-144: "To produce all possible keystroke patterns, result outputs should be \"shin\", \"shinn\", \"sin\" and \"sinn\"." Several spellings are the design; nothing says the count may grow exponentially with input length.
• The documented limitations say nothing about length. The class javadoc (JapaneseCompletionFilter.java:36-58) lists circumflex/macron and missing width normalization; the analyzer normalizes width itself (JapaneseCompletionAnalyzer.java:57-59). No javadoc, CHANGES entry (CHANGES.txt:4632 LUCENE-10102, :596-597 #16416) or MIGRATE text mentions an input-length precondition or an output limit.
• Duplicates are not keystroke patterns. ン x 8 gives 256 romanized tokens, 9 distinct; ン x 16 gives 65,536, 17 distinct.
• Tests. TestKatakanaRomanizer and TestJapaneseCompletionFilter/Analyzer use readings with at most one ambiguous keystroke, so at most 2 spellings (ハシ -> hasi, hashi); their random-string tests use random Unicode, which practically never has long ambiguous runs, and @IgnoreRandomChains (LUCENE-10363, offsets, :59) keeps the filter out of the random-chains test.
• History. Feature issue #11140 (LUCENE-10102): "新橋 can be translated into eight romanized forms (in theory)". PR #297 (5 comments, 7 reviews, 8 inline comments) has nothing on size, memory or limits.
• No downstream bound prevents it. LimitTokenCountFilter, QueryBuilder's clause limit and AnalyzingSuggester's determinize limit all act after the product is built; the last two reject some smaller expansions but cannot prevent the out-of-memory at 32 characters.
• Precedent. LUCENE-3720 (#4794): a combinatorial OutOfMemoryError in BeiderMorseFilter, called "likely a real bug" and fixed under Bug Fixes.
• Framing for the issue. A robustness bug (eager, unbounded, duplicate-producing expansion), not wrong output: for シ/し and ヂ every spelling is a valid keystroke pattern.

The strongest case for "works as designed": the romanizer enumerates every keystroke pattern on purpose, and for シ/し and ヂ every one of the 2^n or 3^n outputs is distinct and valid, so any bound changes documented semantics. SECURITY.md (line 38) makes bounding untrusted analysis input the application's job. The intended consumer, AnalyzingSuggester, already rejects 12 x し, which suggests real inputs are short. Duplicate stacked tokens are legal in the TokenStream API.

Why it is still a defect: nothing documents or accepts memory exponential in a 20-32 character input; the filter has no parameter to bound it; Lucene's own limits cannot prevent the out-of-memory because the whole product exists before the first token; the ン duplicates are not patterns; 64 characters of ordinary hiragana fail; and SECURITY.md itself (line 46) calls out-of-scope issues like this "valid bug reports and hardening suggestions". The design argument does carry weight against a silent hard-coded cap: for シ/し and ヂ any bound drops valid spellings, so how to bound it (a cap, a configurable cap, failing fast, lazy generation plus a limit) is the maintainers' choice.

Which bound to choose is the maintainers' call: option A (a fixed cap) was built and validated in clean scratch trees; a configurable cap (D) or failing fast (E) are equally reasonable, and the design argument weighs against a silent, hard-coded cap. The finder's earlier sketch was validated at ea57360912ed; the other options are untested. Option A does not fix two separate registry bugs in the same code: LFV-341 (romanize ignores the offset of the input CharsRef, KatakanaRomanizer.java:165 and :173) and LFV-335 (the factory upper-cases the default mode). Workaround for users today: cap the raw length of text passed to the analyzer, small enough for the worst case (3^n for ヂ: 12 characters already give 531,442 tokens), or avoid QUERY mode on long all-kana input.

KatakanaRomanizer.java only (+22/-5 lines; the diff also adds 44 lines of tests). Each spelling is produced once (32 x ン: 33 outputs instead of 2^32). The cap is checked again at every keystroke: a keystroke with several spellings branches only if pendingOutputs.size() * candidates.size() is at most MAX_OUTPUTS (256); otherwise it contributes only its first spelling in romaji_map.txt (for example si for シ, n for ン, di for ヂ, sya for シャ). A capped keystroke does not grow the list, so a later keystroke with fewer spellings can still branch: シ x 7 gives 128 outputs, シ x 7 + ヂ also 128 (128 x 3 = 384), シ x 7 + ヂ + シ 256. Each decision depends only on the keystrokes before it, so for a prefix that ends on a keystroke boundary of the whole reading, the prefix's outputs stay prefixes of the whole reading's outputs, as on stock. Without that boundary the property fails on stock too, because of the greedy longest match: romanize(シ) gives si, shi, but romanize(シャ) gives sya, sha. Both modes call the same romanize, but they usually split text into different readings (32 x し: 30 positions in INDEX mode, one reading in QUERY mode). The diff adds two tests to TestKatakanaRomanizer.

/**
 * Maximum number of outputs of {@link #romanize}. ...
 */
static final int MAX_OUTPUTS = 256;
...
} else if (candidates.size() == 1
    || pendingOutputs.size() * candidates.size() > MAX_OUTPUTS) {
  // There are one or more pending output(s) and one matched keystroke, or combining all
  // matched keystrokes would exceed MAX_OUTPUTS.
  // Append the (first) matched keystroke to all pending outputs.
  ...
} else {
  ...
  List<CharsRefBuilder> outputs = new ArrayList<>();
  // different keystroke patterns can give the same output, e.g. "n" + "nn" and "nn" + "n"
  Set<CharsRef> seen = new HashSet<>();
  for (CharsRef cref : candidates) {
    for (CharsRefBuilder pdgOutput : pendingOutputs) {
      CharsRefBuilder buffer = new CharsRefBuilder();
      buffer.copyChars(pdgOutput.chars(), 0, pdgOutput.length());
      buffer.append(cref.chars, cref.offset, cref.length);
      if (seen.add(buffer.toCharsRef())) {
        outputs.add(buffer);
      }
    }
  }
  // update the pending outputs
  pendingOutputs = outputs;
}

Trade-offs

• Long readings lose spellings past the cap: in QUERY mode a 24-char sentence goes from 1,536 to 192, the 22-char onomatopoeia from 9,216 to 192 and the 32-char sentence from 16,384 to 256. A user who types a non-first spelling (for example the Hepburn shi) as trailing, not yet converted romaji after the cap no longer matches there (reasoned from the code, not measured).
• Short readings are unchanged: a reading keeps all its spellings when the product of its keystrokes' spelling counts is at most 256 (the 11- and 24-char test sentences keep 64 and 128 in QUERY mode). Thanks to the de-duplication, runs of up to 128 ン also keep all n+1; ン x 129 gives 129, not 130, because the bound counts pending outputs times spellings before de-duplicating.
• 256 is a judgement call: it keeps the default QueryBuilder query at 257 terms, under the 1024-clause limit (stock fails from 1,024 spellings on). Upstream may prefer another number or a constructor parameter (option D).
• Cost: one HashSet per branching keystroke; not benchmarked. SECURITY.md (line 46) asks that robustness changes not slow hot paths.
• A silent change to public API: KatakanaRomanizer, JapaneseCompletionFilter, JapaneseCompletionAnalyzer and the factory are public and not marked @lucene.experimental or @lucene.internal (unlike AnalyzingSuggester and TokenStreamToAutomaton), and the completion package is exported. A fixed cap changes their output for long readings without notice; this weighs for option D or E, and in any case for a CHANGES entry and a javadoc note.
• Test coverage: the new tests cover repeated シ and ン, ヂヂヂ and one mixed case (シ x 7 + ヂ (+ シ)); none covers a prefix that ends inside a keystroke such as シャ.

What the checks validated

• Revision 2 of the diff (2026-10-28, after review: the javadoc corrected and 2 assertions added; the code is the same as in revision 1). Clean scratch tree at a9779ef3c193, gradle, seed DEADBEEF, JDK 25 (tree removed afterwards): the diff applies cleanly; the minimal test, TestKatakanaRomanizer (with the 2 new tests), TestJapaneseCompletionFilter, TestJapaneseCompletionAnalyzer and TestJapaneseCompletionFilterFactory: 17 tests, 0 failures, with -Ptests.asserts=true and =false; the whole kuromoji module with the minimal test and the 5-test repro in place: 204 tests, 0 failures, 7 skipped; checkGoogleJavaFormat, ecjLintMain, ecjLintTest, forbiddenApisMain, forbiddenApisTest and renderJavadoc pass.
• Revision 1 (same code), the same way: stock fails the 5-test repro 5 of 5 and the minimal test 2 of 2; with the fix the 5-test repro and the 4 closest suites, 20 tests, 0 failures, assertions on and off; the module with the 5-test repro, 202 tests, 0 failures, 7 skipped; the minimal test 2 of 2; the same lint tasks (without renderJavadoc) pass.
• The fixed class on the stock jars (2 GB heap): the 5-test repro 5 of 5 pass with assertions on and off on main; the minimal test 2 of 2 on main (on and off) and on the 10.5.2 and 9.12.3 jars (off); the fixed TestKatakanaRomanizer 4 of 4 on main (on and off).
• Effect probe, stock vs fixed: QueryBuilder on 32 x し and on the 32-char sentence gives a SynonymQuery of 257 terms (stock: OutOfMemoryError, TooManyClauses); an AnalyzingSuggester built with the 22-char onomatopoeia finds it for prefixes of 6, 10, 16, 19 and 22 characters (stock: the 22-char lookup throws TooComplexToDeterminizeException); しん, しんぶ, とうきょう return the same suggestions as stock; the 64-char hiragana input no longer runs out of memory: 256 spellings at one position in QUERY mode, and 274 tokens at 5 positions, at most 256 spellings at one position, in INDEX mode.
• New tests: ンン gives exactly nn, nnn, nnnn; 32 x ン gives 33 distinct outputs; 32 x シ gives at most 256 distinct outputs including si x 32 and shi + si x 31; ヂヂヂ still gives all 27; シ x 7 + ヂ gives 128 and シ x 7 + ヂ + シ gives 256 (the cap is checked at every keystroke); every output of シ x 1, 7, 8, 9, 12 and 31 is a prefix of an output of シ x 32.

Use a set in the product loop and nothing else.

Trade-offs

Fixes the ン waste (2^n -> n+1) but not シ/し/ヂ, where every spelling is distinct: 32 x し would still need 2^32 outputs (count model). Not enough alone. Untested.

Breaks out of the product loop once 256 outputs exist, except for the first candidate.

Trade-offs

Branching at the boundary keystroke is partial and favours the first candidates; the all-or-nothing rule per keystroke of option A is easier to reason about.

What the checks validated

At ea57360912ed with the fixed class on the stock jars: the 5-test repro and the 11 upstream tests then present pass (16 run, 0 failed).

Option A with the cap as a parameter of JapaneseCompletionFilter, JapaneseCompletionAnalyzer and the factory (for example maxRomanizations, default around 256).

Trade-offs

An application that needs every spelling of long readings can raise it, and the limit is visible in the API; adds public API. Untested.

For example IllegalArgumentException when the count would exceed a limit.

Trade-offs

Exact semantics for accepted inputs, and nothing is dropped silently, but long inputs fail outright. At index time an exception from analysis rejects only that document and keeps the writer open (DocumentsWriterPerThread.java:392-398). Untested.

Enumerate the product one token at a time instead of building a list.

Trade-offs

Makes LimitTokenCountFilter effective and memory O(n), but without a limit the chain still emits 2^32 tokens (CPU instead of memory), and de-duplication gets harder. Combined with option D or E it is a sound design.

A javadoc warning plus "limit the input length", the interim step taken for LUCENE-3720.

Trade-offs

Leaves the trap, and the safe limit is small (12 x ヂ already gives 531,442 tokens).

Method: bounded-exhaustive translation validation (the hunt's semi-formal tier), a hunt unit on main ea57360912ed.

• The harness ran the real KatakanaRomanizer against an independent reference romanizer and an exact output-count formula on every katakana string of length up to 3, each with the suffixes '', 'k' and 'sy' (2,682,144 cases), on main and 10.5.2: 0 output mismatches, 0 count mismatches.
• The hypothesis came from reading romanize while writing the reference model; the harness's duplicate tally (549 inputs, for example ンン -> [nn, nnn, nnn, nnnn]) and an exact count model built from romaji_map.txt (count(x^n) = c(x)^n, tight at 3^n for ヂ and 2^n for the other 8 ambiguous kana) gave the growth.
• A public-API JUnit test then witnessed the OutOfMemoryError at 32 characters. No model checker, solver or prover found it; the exhaustive check bounds the input at 3 characters, so the growth itself comes from the count model and the executed tests.