AnalyzingSuggester: num x analyzed forms overflows an int, so with synonyms a large num silently returns fewer suggestions

AnalyzingSuggester (and FuzzySuggester, which inherits lookup) finds the top num completions with a best-first search over its FST, Util.TopNSearcher, whose candidate queue is capped at maxQueueDepth. When the index-time analyzer turns one entry into several analyzed forms (synonyms or any token graph), a suggestion can be reached once per form, so the class sizes the queue as num * maxAnalyzedPathsForOneInput, the largest number of forms of any one entry: in Michael McCandless's words on LUCENE-4481 (#5547), "topN * M where M is the max number of analyzed forms we ever saw for any surface form". That product is a plain int (AnalyzingSuggester.java:786 on main 645d4fe14a20), and num is documented only as the "maximum number of results to return". With three entries and 3 forms on one of them, lookup("a", false, 1431655766) wraps the depth to 2 and silently returns 2 of the 3 matches; with the finder's 8 entries the same num returns 3 of 8 and skips three higher-weighted ones. A depth that wraps to 0 throws NoSuchElementException (num = 2^30 with 4 forms, or num = 65,536 with one 2^16-form entry), and a negative one keeps results right but fails the class's own assert completions.isComplete, typically at Integer.MAX_VALUE. The product is in every release from 4.1.0 to 10.6.0 and main. Multiplying in long and saturating at Integer.MAX_VALUE fixes it, validated with gradle on 645d4fe14a20.

1. Contract. Lookup.lookup(key, onlyMorePopular, num): "@param num maximum number of results to return" (Lookup.java:190). AnalyzingSuggester.lookup checks only assert num > 0 (AnalyzingSuggester.java:670). Both classes are @lucene.experimental (:98; FuzzySuggester.java:64); FuzzySuggester extends AnalyzingSuggester and does not override lookup (FuzzySuggester.java:66).
2. Graph analyzers are supported. "If SynonymFilter is used to map wifi and wireless network to hotspot then the partial text "wirele..." could suggest "wifi router"" (AnalyzingSuggester.java:78-79); "At index time, complex analyzers can safely be used" (FuzzySuggester.java:59-62). The 3- and 4-argument constructors pass maxGraphExpansions = -1, "no limit" (AnalyzingSuggester.java:170-195, :207-208; FuzzySuggester.java:98-127).
3. The path count. "Highest number of analyzed paths we saw for any single input surface form" (AnalyzingSuggester.java:153-157), set by build as Math.max(maxAnalyzedPathsForOneInput, finiteStrings.size()) (:484) and stored with the suggester (:607, :618).
4. The product, in int. new Util.TopNSearcher<>(fst, num - results.size(), num * maxAnalyzedPathsForOneInput, weightComparator) (:783-786). Java int arithmetic wraps modulo 2^32: 1,431,655,766 x 3 = 4,294,967,298 is 2; 1,073,741,824 x 4 = 2^32 is 0; 2,147,483,647 x 2 is -2.
5. Small positive depth. TopNSearcher keeps at most maxQueueDepth paths ("the maximum size of the queue of possible top entries", Util.java:186): once full, a new path that does not beat the worst is dropped, else it is added and the worst removed (Util.java:215-249). With room for 2, paths whose completions belong in the result are dropped and lookup returns what is left.
6. Depth 0. The first addIfCompetitive sees queue.size() == maxQueueDepth (0 == 0) and calls queue.last() on the empty TreeSet (Util.java:215-216): NoSuchElementException.
7. Negative depth. The queue size never equals it, so nothing is pruned and the results are right; but search() returns isComplete = rejectCount + topN <= maxQueueDepth (Util.java:409), false, and AnalyzingSuggester.java:823-824 asserts it. If the search rejects a duplicate path, rejectCount + topN overflows too and the check passes, so the assert fires typically, not always.

The short list keeps descending weight order; which items are missing, and how many, depends on the data and the FST layout. The arithmetic (a Z3 32-bit model and an exhaustive count over every positive int): with k = 2 the product is never a small non-negative number (only negative, so only the assertion); with k = 3 it is negative from num = 715,827,883 and equals 3 x num - 2^32 from 1,431,655,766 on, growing by 3 per step (205,032,704 at 1,500,000,000), so a short list needs num in a narrow window; with k = 4 exactly one num, 2^30, gives 0. The model also proved that num = Integer.MAX_VALUE makes isComplete false for every k from 2 to 2^20 when no path is rejected.

• Who is hit. Callers of AnalyzingSuggester.lookup or FuzzySuggester.lookup whose index-time analyzer gives some entry 2 or more analyzed forms, with a num above Integer.MAX_VALUE / k. One-form analyzers (k = 1) and ordinary counts are not affected. No large dictionary is needed: three entries are enough for the short list.
• Default or opt-in. Default constructor arguments (including maxGraphExpansions = -1, no limit); the graph analyzer is the application's choice, but a documented use of the class.
• What goes wrong. In production: at specific values, a silently incomplete list that can skip higher-weighted suggestions, or a NoSuchElementException from inside the FST search. With assertions on (tests): the class's own completeness assert, also at Integer.MAX_VALUE, the value Lucene's own TestFSTCompletion passes to mean "all results" on the separate FSTCompletion API (TestFSTCompletion.java:157, :165).
• Scale. Normally num must be in the hundreds of millions to billions. But k has no default limit: one 16-word entry with one synonym per word has 2^16 forms, and num = 65,536 then throws in production.
• Workaround. Pass a finite num no larger than Integer.MAX_VALUE / k (in practice no more than getCount(), which for a graph analyzer counts analyzed paths, not entries, the hunt's LFV-431: the repro's 3 entries give getCount() = 5, so it is still a safe upper bound on the results), or bound k with maxGraphExpansions.
• How likely: contrived for the short list (registry likelihood contrived, priority low): with 3 forms the wrapped depth is 3 x num - 2^32, so a list is short only for num within about (paths needed) / 3 of 1,431,655,766, and the natural Integer.MAX_VALUE is right in production. The NoSuchElementException leg is merely rare. No public report since 4.1.0 (2013).

TestAnalyzingSuggesterLargeNum (55 lines with the license header, one test method, package org.apache.lucene.search.suggest.analyzing like the upstream suggester tests; :lucene:suggest:check formats and lints it clean). It uses a ByteBuffersDirectory and a WhitespaceTokenizer (not MockTokenizer), so it is deterministic; LuceneTestCase still randomizes its environment (codec, locale, time zone).

Run with -Ptests.asserts=false to see the production result, [ad, ac]. With -Ptests.asserts=true, gradle's default, the class's own assert completions.isComplete (AnalyzingSuggester.java:824) fails before the test's assertEquals runs: the same wrapped depth, caught by Lucene itself.

The test keeps only the production-mode short list. With three entries the two returned are the top two by weight, so it does not show "skips higher-weighted ones" (the 8-entry table row does). The NoSuchElementException values, the 2^16-form trigger and the assertions-only Integer.MAX_VALUE case are left out on purpose: the same int product with the same fix. The same test is the suggested regression test; it passes with the fix.

cp $REPRO/TestAnalyzingSuggesterLargeNum.java $LUCENE/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/
cd $LUCENE && ./gradlew :lucene:suggest:test --tests org.apache.lucene.search.suggest.analyzing.TestAnalyzingSuggesterLargeNum -Ptests.seed=DEADBEEF -Ptests.asserts=false
# with -Ptests.asserts=true (gradle's default) the class's own assert completions.isComplete fails first

# gradle, main 645d4fe14a20, -Ptests.seed=DEADBEEF -Ptests.asserts=false
TestAnalyzingSuggesterLargeNum > testLargeNumReturnsAllMatches FAILED
    java.lang.AssertionError: expected:<[ad, ac, ab]> but was:<[ad, ac]>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:8DE7055CA230CA86]:0)
        at junit@4.13.2/org.junit.Assert.fail(Assert.java:89)
        at junit@4.13.2/org.junit.Assert.failNotEquals(Assert.java:835)
        at junit@4.13.2/org.junit.Assert.assertEquals(Assert.java:120)
        at junit@4.13.2/org.junit.Assert.assertEquals(Assert.java:146)
        at org.apache.lucene.search.suggest.analyzing.TestAnalyzingSuggesterLargeNum.testLargeNumReturnsAllMatches(TestAnalyzingSuggesterLargeNum.java:53)
:lucene:suggest:test (FAILURE): 1 test, 1  failure

# gradle, main 645d4fe14a20, -Ptests.seed=DEADBEEF -Ptests.asserts=true
TestAnalyzingSuggesterLargeNum > testLargeNumReturnsAllMatches FAILED
    java.lang.AssertionError
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:8DE7055CA230CA86]:0)
        at org.apache.lucene.search.suggest.analyzing.AnalyzingSuggester.lookup(AnalyzingSuggester.java:824)
        at org.apache.lucene.search.suggest.Lookup.lookup(Lookup.java:195)
        at org.apache.lucene.search.suggest.analyzing.TestAnalyzingSuggesterLargeNum.testLargeNumReturnsAllMatches(TestAnalyzingSuggesterLargeNum.java:51)
:lucene:suggest:test (FAILURE): 1 test, 1  failure

# standalone runner, seed DEADBEEF, main 645d4fe14a20: -da and -ea, 1 run, 1 failed, the same two outcomes

• Contract. num is a maximum (Lookup.java:190); nothing bounds it or says it is multiplied.
• An admissible bound, by design. On LUCENE-4481 (#5547) Michael McCandless found the earlier topN-sized queue unsound for token graphs and planned to "bound the queue using topN * M where M is the max number of analyzed forms we ever saw for any surface form". A wrapped product is no longer that bound. Util.java:465-466 states the rule for shortestPaths: "All paths are kept, so we can pass topN for maxQueueDepth and the pruning is admissible".
• The completeness assert is deliberate. On LUCENE-5519 (#6582) Robert Muir proposed returning a boolean saying whether the top-N is complete; Michael McCandless asked that callers "do the assert on that returned boolean; else, it means there's a serious bug (the search pruning is not admissible)" and suggested the name isComplete; Simon Willnauer implemented and committed it (803a9907d39, 4.8.0). That is the assert at AnalyzingSuggester.java:824 that fires here. LUCENE-5519 itself was opened to make depth enforcement optional for callers that accept an inexact top N (Simon Willnauer: "I am ok with a top N that is not 100% exact"; Robert Muir: "the current assert is bogus"). AnalyzingSuggester is not such a caller: the same commit gave it assert completions.isComplete (:755, :824), while NRTSuggester, which does accept an inexact bound, says "search admissibility is not guaranteed" and leaves the assert commented out (NRTSuggester.java:257-259).
• Precedent: a too-small depth was a bug. LUCENE-4533 (#5599, 2012), "if you pass dups (same surface form) to AnalyzingSuggester it can fail to return enough results": Michael McCandless's failing test "trips the assert in TopNSearcher that detects a too-small maxQueueDepth", and it was fixed.
• The neighbouring product is guarded. The document suggester computes topN * (long) maxAnalyzedPathsPerOutput and clamps it with Math.min (NRTSuggester.java:294, :301). Reviewing that code (LUCENE-6339, #7400), Michael McCandless asked whether it "could possibly overflow int? Maybe use long, and then cast back to int after the Math.min?"; the long multiplication now there came from Robert Muir's error-prone "narrow calculation" change (#11923).
• Tests. TestAnalyzingSuggester and TestFuzzySuggester use graph analyzers (for example testGraphDups) but only small num values; no test, javadoc or CHANGES entry accepts the wrap.

The strongest "works as designed" case (first raised by the refute-lens reviewer from another model family, OpenAI GPT-5.6, then argued in full by the devil's advocate): no autosuggest UI asks for a billion suggestions; both classes are @lucene.experimental; maxGraphExpansions exists to bound k; TopNSearcher deliberately supports bounded queues that may give an inexact top N (LUCENE-5519); and at Integer.MAX_VALUE production results are right, so only a test-time assert fires.

Why it fails: that bears on likelihood and priority, not on correctness. No doc bounds num; the depth is meant to be a sound bound and the class asserts that it is (the inexact mode is for callers such as NRTSuggester that say so, not for AnalyzingSuggester); with the default maxGraphExpansions one heavily expanded entry makes num = 65,536 throw; @lucene.experimental is about API stability. The adjudication (confirmed, high confidence, priority low), the independent reproducer, the intended-lens reviewer and the devil's advocate treat it as a real defect; the refute-lens review's "not real" (low) was procedural, as it could not run Java.

One fix was built and validated; two alternatives were considered and not built, and one caveat concerns TopNSearcher itself.

Below Integer.MAX_VALUE / k nothing changes. Above it the depth is Integer.MAX_VALUE, a queue the search never fills, so it prunes nothing: what a negative wrap already does in production today, and admissible. isComplete (rejectCount + topN <= Integer.MAX_VALUE) is then true. It mirrors the document suggester's queue size (NRTSuggester.java:294, :301: a long product clamped with Math.min), the shape Michael McCandless suggested for that product on LUCENE-6339 (#7400): "use long, and then cast back to int after the Math.min".

// AnalyzingSuggester.lookup, before the main TopNSearcher (line 783):
// Multiply in long and saturate: in int, num * maxAnalyzedPathsForOneInput wraps for a large
// num, and a wrapped queue depth makes the pruning inadmissible
int maxQueueDepth =
    (int) Math.min((long) num * maxAnalyzedPathsForOneInput, Integer.MAX_VALUE);
Util.TopNSearcher<Pair<Long, BytesRef>> searcher;
searcher =
    new Util.TopNSearcher<>(fst, num - results.size(), maxQueueDepth, weightComparator) {

Trade-offs

• No pruning above the threshold. For such a num the search keeps every candidate path, like an unbounded search; that is the cost of a correct answer for a huge num and the same as today's negative-wrap case. It does not make huge result counts cheap.
• The completeness sum. Util.java:409 adds rejectCount + topN in int too (a remark of the devil's advocate). With the saturated depth the flag comes out right; switching that sum to long as well would, with topN and the depth both at Integer.MAX_VALUE, report "incomplete" after one rejected duplicate although nothing was pruned (arithmetic, not executed). Changing TopNSearcher alone does not fix this bug, since the wrap happens in the caller; nor is the clamp the only possible fix.
• The exact-first searcher (AnalyzingSuggester.java:729-735) has a similar int product, count * maxSurfaceFormsPerAnalyzedForm, which needs about 8.4 million exact-match prefix paths to wrap; a patch could saturate it too.

What the checks validated

• Fresh scratch worktree of 645d4fe14a20, gradle, OpenJDK 25: the repro fails on the stock tree and passes with the fix, with assertions on and off.
• TestAnalyzingSuggester (23 tests) and TestFuzzySuggester (14) pass.
• The whole lucene/suggest module passes with assertions on (seed DEADBEEF) and off (seed 5EED1003): 32 suites, 237 tests, 7 skipped, 0 failures each time.
• :lucene:suggest:check -x test (checkGoogleJavaFormat, ecjLint, forbiddenApis) passes.
• The finder's 3-case test (3 forms at 1,431,655,766; 4 forms at 2^30; 2 forms at Integer.MAX_VALUE) passes 3 of 3 with assertions on and off.
• Earlier, by the hunt (main a9779ef3c193, same code): the same change passes the independent reproducer's 7 tests, the 2^16-form tests, the 4.1.0 port and 144 upstream suggest tests with all the hunt unit's fixes.
• Not run: nightly tests, a benchmark (one long multiplication per lookup).

Throw ArithmeticException instead of returning a short list.

Trade-offs

Honest, but it rejects a legal request (num is only a maximum) that the saturating fix answers correctly.

num = (int) Math.min(num, getCount()) before sizing the search: no more than count suggestions can come back (duplicate surface forms are removed by the searcher's seen set). count is at least the number of entries; for a graph analyzer it counts analyzed paths (AnalyzingSuggester.java:419, :590, the hunt's LFV-431), so it is still a safe upper bound on the results.

Trade-offs

Keeps the depth small for small dictionaries, but count * k can still overflow for a large dictionary with many forms, so it still needs the long product; best as an addition to the saturating fix.

Method: non-formal first signal, then a small formal model (a hunt unit for suggester num sizes, 2026-10-28, main a9779ef3c193).

• First signal. A differential probe ran the Lookup implementations at growing num on the stock main jars: AnalyzingSuggester with a 2-form synonym analyzer threw AssertionError at Integer.MAX_VALUE with assertions on, where num = 1000 returns 8; with assertions off it returned the right 8.
• Model. A Z3 32-bit bit-vector model of the queue-depth product found the production-mode witnesses the probe had not shown: the smallest num with a wrapped depth between 0 and topN is 1,431,655,766 for 3 forms (depth 2) and 2^30 for 4 forms (depth 0), and none exists for 2 forms; it proved that num = Integer.MAX_VALUE makes isComplete false for every k from 2 to 2^20 with no rejected path. An exhaustive count over every num followed.
• Execution. Each witness ran on the stock jars, then became a JUnit; a probe over 1-4 forms x 14 num values on both suggesters failed only where the model predicted. An independent verifier later found a moderate trigger: one entry with 2^16 forms and num = 65,536. The minimal-repro step reduced it all to one method.