Stempel: a second Optimizer2 or Optimizer pass over an already merge-reduced stemmer trie can silently lose words

The stempel table compiler Compile shrinks a stemmer trie with reduction passes named by letters (1 = Optimizer, 2 = Optimizer2, the two "merge" passes); the same reducers are public API (Trie.reduce(new Optimizer2())). One merge pass keeps the training words in every case tested. A second merge pass over a trie that a merge pass already reduced can silently corrupt it: Optimizer.optimize (inherited by Optimizer2) walks the rows from the last one down and remaps each child reference through an int[] remap whose slots are read before they are filled (Java zero-fills the new array), so a reference to a row it has not placed yet becomes 0. That is only right when every child row comes after its parent, which holds for a freshly built trie but not for the output of a merge pass. A one-word trie loses its only word; Compile -22 and -M22 lose all 9 training words of TestCompile's data; one more pass over the bundled Polish table changes 8,356 of 21,147 sampled stored keys. No error, with assertions on and off, in every release since 3.1.0. The default PolishAnalyzer and StempelPolishStemFilterFactory are not affected.

• Stemmer trie: stempel stores each training word with a patch command that turns it into its stem (aab -> aa is Da, delete one character). The trie is a list of rows; a row maps a character to a cell with a command and/or a reference to a child row. Polish tables are read backward, from the last character.
• Merge passes: Optimizer (1) and Optimizer2 (2) join rows that do not conflict (Optimizer2 only when the shared cells are identical) to shrink the table. Compile applies the reduction letters of its method string in turn: the bundled table used -0ME2.

1. Optimizer.optimize (Optimizer.java:79-110, inherited by Optimizer2) allocates int[] remap = new int[orows.size()] and never fills it (:83), so every slot is 0.
2. It walks the rows from the last one down (:85) and builds new Remap(orows.get(j), remap) (:86), which sets nc.ref = remap[nc.ref] for every child (Reduce.java:121), before row j itself gets its new index (:94, :100).
3. On a fresh trie that is right: Trie.add appends every new row (Trie.java:351-354), so children always come after their parent and are placed first.
4. A merge pass breaks that order: removeGaps renumbers rows in pre-order (Reduce.java:88-102), so a row merged with a deeper row, or shared by several parents, can sit at the same or a lower index than a parent. The bundled table has 31,837 such references.
5. In a second pass, such a reference reads remap[child] before the child is placed, gets 0, and points to whichever row was placed first. Row 0 is a real row, not a sentinel (removeGaps uses -1, Optimizer.java:106).

• TestCompile's testRules.txt (4 lines, 9 training words): -2 and -M2 stem all 9; -22 stems all 9 to null; -M22 returns all 9 unchanged. Compile's statistics after the second pass are identical to those after the first.
• Two-word trie {aa -> Da, ab -> Db}: after two Optimizer passes ab returns Da.
• 2,000 random small tries: about 930 lose a key after two Optimizer2 passes, about 800 after two Optimizer passes, none after one pass.
• Bundled table plus one more Optimizer2 pass: 8,356 of 21,147 sampled keys whose whole path is stored change their answer (0 with the fix).
• An 11-lemma Polish table (94 training forms): -0ME2 stems 93 correctly in every run; -0ME22 about two thirds and -0M22 almost none (67 and 0 in the finder's run, 63 to 74 and 0 to 3 in later runs; the counts depend on hash iteration order).

• Who is exposed. People who compile their own stempel tables with a method string that has two of the merge letters 1/2, or whose code calls Trie.reduce(new Optimizer2()) or reduce(new Optimizer()) on a table loaded with StempelStemmer.load that a merge pass built (such as the bundled one) or on any other trie that was already merge-reduced. Optimizer2's javadoc also says the class "allows the stemmer to be self-teaching", which reads like adding words to a table and reducing it again; nobody tested that flow.
• Not exposed. PolishAnalyzer and StempelPolishStemFilterFactory load the bundled stemmer_20000.tbl (its header names -0ME2, one merge pass) and never reduce it (PolishAnalyzer.java:61, 89, StempelPolishStemFilterFactory.java:50). A table that was never merge-reduced is not affected by one more pass: a -0M table reduced once with Optimizer2 changes 0 forms.
• What it takes. No scale: one word suffices. Not every twice-reduced trie loses a key (about 930 of 2,000 random tries do with Optimizer2), but every minimal case and every word table tested does. Exact counts vary with hash iteration order (since 9.11.0) and seeds; the failures always occur.
• Silent. No exception or warning; the table loads and stems, just wrongly. The same with -ea and -da.
• Likelihood: rare. The recipes found (the bundled -0ME2, a downstream port's -0ME2) use one merge pass, and the searches found no report since 3.1.0 (2011).

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => org.junit.ComparisonFailure: expected:<[Da]> but was:<[]>
       org.junit.Assert.assertEquals(Assert.java:117)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.analysis.stempel.TestOptimizer2SecondPass.testTwoOptimizer2PassesKeepTheOnlyWord(TestOptimizer2SecondPass.java:31)

• Contract. Optimizer2.java:60-63: "Information loss, resulting in the stemmer not being able to recognize words (as in Optimizer), is curtailed, allowing the stemmer to recognize words for which the original trie was built." Trie.reduce (Trie.java:361-369): "Remove empty rows from the given Trie and return the newly reduced Trie." Neither states a condition on the input. The module's overview.html (lines 175-177) says only: "Several optimization steps are applied in turn to reduce and optimize the initial trie", a chain of steps each run on the previous output, with no recipe and no limit.
• The API composes reducers. Trie.reduce, MultiTrie2.reduce, Optimizer and Optimizer2 are public in the exported org.egothor.stemmer package; a reducer returns an ordinary Trie. Compile applies every letter 1, 2, E, L, G in turn without rejecting repeats (Compile.java:145-171). The method string is case-sensitive and partly positional: a leading - selects a backward trie, then an optional 0 stores original forms and an optional M selects MultiTrie2 (Compile.java:88-100); of the rest, only the uppercase letters run a reduction and any other character is skipped (Compile.java:168-169); the "list ... in the package description" its javadoc cites (Compile.java:76-78) does not exist (package-info.java: "Egothor stemmer API.").
• Tests. TestStemmer.assertTrieContents asserts that each reduction keeps every inserted key, on fresh tries only; TestCompile's methods test, -test and Mtest contain no reduction letter. No upstream test composes two merge passes.
• History. The logic is the 2010 import (LUCENE-2298), never changed; no commit, issue or list thread calls repeated merge passes invalid.
• Optimizer vs Optimizer2. Optimizer2's javadoc says Optimizer loses information. But one Optimizer pass keeps every key of 2,000 random tries and two lose keys in about 800 of them; and with the finder's fix sketch shadowed (the same idea as fix A), the bounded checks' only remaining getLastOnPath violations are sequences with Lift(false) before an Optimizer pass (E1 in the length-2 run; E1, 2E1, E21, LE1 and others in the length-3 run): the documented loss. The same root cause affects both.

The intended-behaviour checker's strongest case (moderate; the cross-model reviews rated it weak): these are legacy offline compiler passes with an unstated "fresh trie only" precondition, since Optimizer, Gener and Lift all walk rows downward; every known recipe uses one merge pass; a second pass gains little; and maintainers treat the forked code as frozen (#8841: "I think we should avoid applying these kinds of modifications to forked code").

Why it fails: nothing documents that precondition; the bad input is produced by Lucene's own merge pass and shipped in its own table; on such input Gener's downward walk treats a row it has not visited yet as alive (Gener.java:84) and Lift on the loaded bundled table changes 0 stems, while Optimizer sends the reference to an unrelated row; and the unfilled slot is not a deliberate sentinel (Gener fills its array with 1, alive; removeGaps uses -1, not placed yet). The frozen-fork stance is a triage preference, not a statement of intent. Verdict: not intended, a defect.

Fix A was built and validated in a scratch worktree at a9779ef3c193; options B and C come from the adjudication and the audit and were not built.

Reduce.Remap records whether any reference got a negative (unassigned) value. Optimizer.optimize fills remap with -1; a row whose Remap has an unresolved reference is placed as it is, is never used as a merge target, and is remapped once every row has its new index. Every other row goes through the old merge code, except that deferred rows are never merge targets. Same idea as the finder's sketch, written more compactly.

--- a/lucene/analysis/stempel/src/java/org/egothor/stemmer/Optimizer.java
+++ b/lucene/analysis/stempel/src/java/org/egothor/stemmer/Optimizer.java
     int[] remap = new int[orows.size()];
+    Arrays.fill(remap, -1);
+    // Rows are placed from the last one down, so a reference to the same or a lower row is not
+    // resolved yet. A trie that is already reduced has such references: keep those rows unmerged
+    // and remap them once every row is placed.
+    BitSet deferred = new BitSet();
 
     for (int j = orows.size() - 1; j >= 0; j--) {
-      Row now = new Remap(orows.get(j), remap);
+      Remap now = new Remap(orows.get(j), remap);
+      if (now.unresolved) {
+        remap[j] = rows.size();
+        deferred.set(rows.size());
+        rows.add(orows.get(j));
+        continue;
+      }
       boolean merged = false;
 
       for (int i = 0; i < rows.size(); i++) {
+        if (deferred.get(i)) {
+          continue;
+        }
         Row q = merge(now, rows.get(i));
@@ after the loop
+    for (int i = deferred.nextSetBit(0); i >= 0; i = deferred.nextSetBit(i + 1)) {
+      rows.set(i, new Remap(rows.get(i), remap));
+    }
--- a/lucene/analysis/stempel/src/java/org/egothor/stemmer/Reduce.java
+++ b/lucene/analysis/stempel/src/java/org/egothor/stemmer/Reduce.java
   class Remap extends Row {
+    /** true if a reference points to a row that has no new index yet (remap value below 0) */
+    boolean unresolved;
@@ in the constructor
           nc.ref = remap[nc.ref];
+          unresolved |= nc.ref < 0;
(plus import java.util.BitSet; full patch: fix-a.diff)

Trade-offs

• A second pass now merges little: one more Optimizer2 pass over the bundled table keeps all 6,815 rows of its 8 sub-tries (stock goes from 6,815 to 6,577 rows, with a corrupted result). The fix makes a second pass safe, not useful.
• It touches Reduce.Remap, which removeGaps also uses (there unresolved is never read). Keeping Reduce untouched with a separate scan of each row's cells (the finder's sketch) passes the same tests, but every iteration of a row's cell map advances that map's iteration seed, so the extra scan changes the order in which later code visits the cells, and the output bytes change even for fresh tries: with the finder's sketch shadowed, all 13 identity-probe hashes differ from stock.
• Forked code (#8841): a maintainer may prefer B or C.

What the checks validated

• The repro class: 3 of 3 fail on stock (gradle, assertions on and off); with fix A the whole :lucene:analysis:stempel:test task passes: 6 classes, 22 tests, 0 failures (assertions on), 6 classes, 22 tests, 0 failures (assertions off).
• ecjLintMain, ecjLintTest, checkGoogleJavaFormat of the module with fix A and the repro class: pass (a first run flagged one line wrap in the test's javadoc; rewrapped).
• The independent reproducer's 10 tests and the finder's 4 pass with fix A; the bundled-table check reports changed=0 of 21,147 stored-path keys.
• Byte-identical output on stock and with fix A (SHA-256) for 5,000 random fresh tries after one Optimizer and after one Optimizer2 pass, and for Compile with 11 one-merge method strings, including the bundled -0ME2.
• The one-word trie: with fix A a second pass returns exactly the pass-1 trie.

Optimizer.optimize throws IllegalArgumentException when a row refers to the same or a lower row, and Compile rejects a second merge letter.

Trade-offs

Turns silent corruption into an error, but blocks re-reducing loaded tables, which fix A handles correctly in the tested cases. Not built.

State in the Optimizer/Optimizer2 javadoc that the input must be a trie built by add and not merge-reduced yet, and document Compile's method letters (the missing "package description" list).

Trade-offs

Cheapest, but Java callers stay exposed to silent corruption. Not built.

Method: bounded-exhaustive translation validation on the real jar (the hunt's "semi-formal" tier), unit "stempel trie and diff round trips", main a9779ef3c193, 2026-10-27.

• The harness built every set of at most 4 keys over {a,b} of length at most 3 with 3 commands, forward and backward, and applied every reduction sequence of length at most 2 over {1, 2, L, E, G} and of length 3 over {1, 2, L, E} on tries of at most 3 keys. The reference was the unreduced trie, itself checked against an independent longest-match reference (0 mismatches).
• Result (by getLastOnPath): every single pass kept the inserted keys; each sequence with two merge passes (11, 12, 21, 22, 2E2, ...) lost keys on some tries. With the finder's shadow fix of Optimizer.optimize (a one-file sketch of the same idea as fix A), all of those violations disappeared; only sequences with Lift(false) before an Optimizer pass (E1, 2E1, ...: Optimizer's documented loss) remained.
• An AI finder then wrote the public-API JUnit and traced the cause; independent AI tools reproduced and judged it (see the checks).