WordBreakSpellChecker.suggestWordCombinations ignores maxEvaluations: the limit stops one left term, then every later one is evaluated

WordBreakSpellChecker.suggestWordCombinations suggests joining adjacent query words into one indexed word. setMaxEvaluations is documented as "The maximum number of word combinations to evaluate" (default 1000), and the method keeps one counter for the call, but it compares the counter with == maxEvaluations after each lookup and its break leaves only the inner loop. So the limit skips only the rest of the one left term at which the counter first equals it; every later left term is evaluated in full, and a limit of 0 or less never matches. With the terms ab, bc, bcd indexed, the query a b c d, maxChanges = 2 and maxEvaluations = 1, 4 of the 5 possible joins are looked up and 3 suggestions come back instead of at most 1. The code is unchanged since the class was added (LUCENE-3523, 2012), so every lucene-suggest release from 4.0.0-ALPHA to 10.6.0 and main are affected. #12077 fixed the same symptom in 9.5.0, but only in the word-break path. The work stays bounded by the query length times maxChanges; a small change (+5/-4 lines) that checks >= before each lookup and leaves both loops restores the cap and passes all lucene/suggest tests (237 run, 7 skipped, 0 failures).

WordBreakSpellChecker.suggestWordCombinations on main 645d4fe14a20:

int thisTimeEvaluations = 0;                                            // :168  one counter for the call
for (int i = 0; i < terms.length - 1; i++) {                            // :169  left term
  ...
  for (int j = i + 1; j < terms.length && j - i <= maxChanges; j++) {  // :186  right end of the join
    ...
    int combinedTermFreq = ir.docFreq(combinedTerm);                    // :204  one evaluation
    ...                                                                 // :206-226 offer a suggestion
    thisTimeEvaluations++;                                              // :228
    if (thisTimeEvaluations == maxEvaluations) {                        // :229  '==', not '>='
      break;                                                            // :230  leaves only the inner loop
    }
  }
}

• The counter is declared once, outside both loops, and never reset: it counts the whole call.
• It is checked after the lookup, with ==, and the unlabeled break leaves only the inner loop. After the first match the counter is past the limit and never equal to it again, so the outer loop carries on and every later left term is evaluated in full.
• Exactly the rest of the left term at which the counter first equals the limit is skipped. A limit of 0 or less never equals the counter after an increment, so nothing is skipped.
• The method is otherwise bounded: the inner loop stops after maxChanges right terms (:186), at a SEPARATOR_TERM (:187-189) and when the joined text passes maxCombineWordLength (default 20, :194-196), so a call makes at most about (terms - 1) x maxChanges lookups.
• The sibling path generateBreakUpSuggestions (word breaks) checks totalEvaluations >= maxEvaluations before each evaluation (:269-272; this check came with #12077 in 9.5.0), and also before recursing (:299) and after each recursion (:324-326), two checks that came with the breadth-first rewrite #12100 (9.12.0).

Index {ab, bc, bcd}, query a b c d, maxChanges = 2, maxEvaluations = 1, SUGGEST_ALWAYS:

Result: 4 lookups and 3 suggestions, [bc, ab, bcd]. A cap per call allows 1; a budget per left term would allow ab and bc (2). With the fix: 1 lookup, [ab].

• Who. Code that calls setMaxEvaluations with a value small enough to bind, directly or through a downstream component. Apache Solr's WordBreakSolrSpellChecker maps its maxEvaluations parameter onto setMaxEvaluations and calls suggestWordCombinations on every request it serves, even with combineWords=false; its sample config sets maxChanges = 10 (read from its source, not run).
• Default vs opt-in. With the default limit of 1,000 it shows only for queries with more than 1,000 joins: more than 1,001 words at the default maxChanges = 1, or roughly 100 short words at maxChanges = 10. With a smaller limit it shows on every query with more joins than the limit, deterministically.
• Effect. More combined-term lookups (term-dictionary seeks) than configured and possibly more suggestions, still capped by maxSuggestions; the skipped subset is irregular. No exception, no index change.
• Scale (a 702-term in-memory index, one host, medians of 5; the lookup counts are exact, the times indicative): defaults, 100,000 one-letter words: 99,999 lookups in 168 ms vs 1,000 in 2.6 ms fixed; maxChanges = 10: 999,945 lookups in 1.5 s vs 1,000 in 3.3 ms. The 100,000 per-word lookups that every mode except SUGGEST_ALWAYS does first take 129 ms.
• Size of the problem. Without the fix the combined-term lookups grow with the query length times maxChanges (at most (words - 1) x maxChanges); the fix caps them at maxEvaluations whatever the query length. Every mode except SUGGEST_ALWAYS also looks up each query word once (:155-161), so the whole call stays linear in the query length either way; the bug removes the fixed cap the caller asked for. Few deployments tune the setting, and nobody reported it in 14 years.

One test class, one method, single thread, nothing random: StringField, ByteBuffersDirectory and the default IndexWriterConfig. It asserts only the setter's contract: each evaluated combination yields at most one suggestion, so maxEvaluations = 1 allows at most one. Pass -Ptests.asserts explicitly, because Lucene's build otherwise picks it at random from the seed; the result is the same both ways.

Formatting: ./gradlew tidy (google-java-format) wraps the Arrays.toString(...) line. With that the test passes the module's format, ECJ and forbidden-apis checks.

Regression test: this same test, as its own class or as a method of TestWordBreakSpellChecker with its own directory (that class shares a different index).

Older releases: the test compiles on 10.0.0 and later (CombineSuggestion is a record there); on 9.x write s.suggestion.string.

cp $REPRO/TestWordBreakCombineMaxEvaluations.java $LUCENE/lucene/suggest/src/test/org/apache/lucene/search/spell/
cd $LUCENE && ./gradlew :lucene:suggest:test --tests org.apache.lucene.search.spell.TestWordBreakCombineMaxEvaluations -Ptests.seed=DEADBEEF -Ptests.asserts=true
# the same failure with -Ptests.asserts=false

# stock main 645d4fe14a20, gradle, -Ptests.seed=DEADBEEF -Ptests.asserts=true
TestWordBreakCombineMaxEvaluations > testMaxEvaluationsLimitsCombinations FAILED
    java.lang.AssertionError: expected at most 1 suggestion with maxEvaluations=1, got [bc, ab, bcd]
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:AAB441975C67B46F]:0)
        ...
        at org.apache.lucene.search.spell.TestWordBreakCombineMaxEvaluations.testMaxEvaluationsLimitsCombinations(TestWordBreakCombineMaxEvaluations.java:53)
1 test completed, 1 failed

# the same message with asserts off, and on releases 10.6.0 and 10.5.2

# lookup counts on the same input (a counting reader, assertions off; evidence, not the repro; log lines, labelled stock:/fix:)
stock: maxEvaluations=1    -> combinedLookups=4 suggestions=[bc, ab, bcd]
stock: maxEvaluations=1000 -> combinedLookups=5 suggestions=[bc, ab, bcd]
fix:   maxEvaluations=1    -> combinedLookups=1 suggestions=[ab]
fix:   maxEvaluations=1000 -> combinedLookups=5 suggestions=[bc, ab, bcd]

• The contract. setMaxEvaluations: "The maximum number of word combinations to evaluate. Default=1000. A higher value might improve result quality. A lower value might improve performance." (WordBreakSpellChecker.java:451-453); getMaxEvaluations: "Returns the maximum number of word combinations to evaluate." (:404-405). "Word combinations" names exactly what this method does.
• The method tries to apply it. It declares, increments and checks the counter itself (:168, :228-231). An == test with an inner-only break can fire at most once per call and has no coherent other meaning.
• Not a budget per left term. The counter is never reset. With maxChanges = 5 and maxEvaluations = 1 on six words, such a budget allows 5 lookups; the stock code makes 11.
• The project treats it as a bug. #12077 (hossman, 2023) reported the same symptom for generateBreakUpSuggestions(); 9007f746a39 fixed it with >= guards and changed only that method. CHANGES.txt:3869 (9.5.0): "GITHUB#12077: WordBreakSpellChecker now correctly respects maxEvaluations (hossman)".
• Tests. TestWordBreakSpellChecker.testMaxEvaluations and testSmallMaxEvaluations treat the limit as a hard bound for word breaks: "if maxEvaluations is respected, we can't possibly have more suggestions than that". No upstream test sets maxEvaluations for combinations.
• History. The == check and inner-only break are in the method's first version (LUCENE-3523, 2012) and were never changed; no comment, test, issue or list thread describes the current behaviour as wanted.

The strongest case for "intended": maxEvaluations is an effort knob meant for the exponential break-up recursion; the combine loop is bounded anyway by words x maxChanges; and the suggestWordCombinations javadoc does not mention the limit.

Why it fails: the method counts and checks the limit itself, the setter's text names word combinations, and a bound that grows with the query is not the fixed cap the setter offers (99,999 lookups instead of 1,000 with the defaults). Because the method javadoc is silent, the contract rests on the setter and the #12077 CHANGES line. What remains is an argument for low priority, not for intent.

One fix was validated through gradle in a scratch worktree of 645d4fe14a20; the smaller variant and a javadoc-only change are listed with their trade-offs.

WordBreakSpellChecker.suggestWordCombinations, +5/-4 lines: label the outer loop, test the counter before the docFreq lookup, and drop the == check after it.

int thisTimeEvaluations = 0;
outer:
for (int i = 0; i < terms.length - 1; i++) {
  ...
    if (thisTimeEvaluations >= maxEvaluations) {
      break outer;
    }
    thisTimeEvaluations++;
    Term combinedTerm = new Term(terms[0].field(), combinedTermText);
    int combinedTermFreq = ir.docFreq(combinedTerm);
    ...   // and remove: thisTimeEvaluations++; if (... == maxEvaluations) break;

Trade-offs

• At most maxEvaluations combined-term lookups per call, so at most that many suggestions. A limit of 0 or less makes no combined-term lookups, as the word-break path makes no evaluations then.
• Callers with a small limit get fewer combination suggestions than today, which is what the limit promises. Joins are tried left to right, so a tight limit favours those that start at earlier words; that is already true for the first left word today.
• Cost: one int compare per join.
• Open PR #16847 changes the int docFreq types in this method; the two touch nearby lines (a textual conflict only).

What the checks validated

• Scratch worktree of 645d4fe14a20, gradle --no-daemon, OpenJDK 25.0.3, seed DEADBEEF. Stock: the repro fails with assertions on and off.
• With the fix: the repro and TestWordBreakSpellChecker (5 tests) pass, and all :lucene:suggest:test passes (32 suites, 237 tests, 7 skipped, 0 failures) with assertions on and off. checkGoogleJavaFormat (after tidy of the test; the fix itself is clean), ecjLintMain, ecjLintTest, forbiddenApisMain and forbiddenApisTest pass. Other modules were not run.
• Earlier: the finder's, the independent reproduction's and the intended-behaviour check's tests and the history probe (1 / 3 / 1 / 0 where 1 / 3 / 1 / 0 are allowed) pass with the same change; upstream TestWordBreakSpellChecker 25 runs, 0 failures.

if (thisTimeEvaluations >= maxEvaluations) break outer; in place of the current check.

Trade-offs

Smaller diff and the same result for a limit of 1 or more, but a limit of 0 or less still makes one lookup before it stops, unlike the word-break path.

What the checks validated

Not run.

Javadoc change only.

Trade-offs

Contradicts the setter's text and the counter the method already keeps, and leaves combinations without a fixed cap. Not recommended.

What the checks validated

Not executed (documentation only).

Method: semi-formal (a bounded check on the stock jar against a stated property).

• The hunt unit for the spellchecker, dictionaries and word-break code first ran an exact-reference translation check of suggestWordCombinations with the limit unbounded, which could not see this defect.
• A separate bounded check then tested the setter's bound: a counting FilterLeafReader counted the combined-term docFreq lookups of suggestWordCombinations on a 5-word query for every maxEvaluations from 0 to 10 and maxChanges from 1 to 4. 30 of the 44 configurations exceeded the limit; with the fix shadowed in, none did.
• A public-API JUnit test reproduced it on main, 10.5.2, 9.12.3 and 9.1.0. Independent checkers then reproduced it with their own tests, built the strongest "intended" case and rejected it, an adjudication re-ran the tests, and a history probe ran it on every release.