Util.shortestPaths and FreeTextSuggester throw NoSuchElementException when asked for 0 results

Util.shortestPaths (core, @lucene.experimental) finds "the top N min cost completions to a final node" of an FST, with no stated range for N. Called with topN = 0, it throws java.util.NoSuchElementException instead of returning an empty result as soon as the start node offers one arc to the queue (every labelled arc; the end-of-string arc only with allowEmptyString). It builds a TopNSearcher whose queue may hold maxQueueDepth = topN = 0 paths (Util.java:467); while seeding the queue, addIfCompetitive treats queue.size() == maxQueueDepth as "full, compare with the worst entry", which is true for the empty queue, and queue.last() throws (Util.java:215-216). The rest of the search already handles 0, topN = -1 returns empty, and 4.0.0 returned empty. FreeTextSuggester.lookup(key, 0) has no check on num and reaches the same line, for a key that matches its model, with assertions on and off. With assertions off, so do WFSTCompletionLookup for a prefix that is not itself a key, AnalyzingSuggester without EXACT_FIRST, and AnalyzingSuggester / FuzzySuggester with their default EXACT_FIRST when the key is itself a suggestion. The throw came with LUCENE-4480 (2012) and is in every release executed from 4.1.0 to 10.6.0 and in main; all 121 release tags have the same unguarded check. A four-line early return for maxQueueDepth == 0 fixes every caller; it passes the core FST tests, the suggest module and core's static checks.

• FST: Lucene's finite state transducer, a compact map from keys (byte or char sequences) to outputs such as weights. Suggesters store their suggestions in one.
• Top-N search (Util.TopNSearcher, used by Util.shortestPaths): walks the FST from a start node and returns the N completions with the smallest total output. It keeps candidate paths in a sorted TreeSet of at most maxQueueDepth entries; shortestPaths passes N as both topN and maxQueueDepth.

1. Util.shortestPaths creates new TopNSearcher<>(fst, topN, topN, comparator) (Util.java:467), calls addStartPaths (:471), then search() (:472). It checks no argument.
2. addStartPaths calls addIfCompetitive(path) for each arc leaving the start node (:283-286; the end-of-string arc only if allowEmptyString). So one offered arc is enough: an FST whose only key is the empty string returns empty for topN = 0 with allowEmptyString = false, and throws with true (the study verifier's characterization test).
3. addIfCompetitive first asks whether the queue is full, if (queue.size() == maxQueueDepth) { (:215), and if so compares the new path with the worst queued one, FSTPath<T> bottom = queue.last(); (:216). That assumes a full queue has a last entry. With maxQueueDepth == 0 the empty queue is already "full" (0 == 0), and TreeSet.last() on an empty set throws NoSuchElementException.
4. Everything else already means "nothing" for 0: the non-full branch would add the path and drop it again at size maxQueueDepth + 1 (:247-249), after building it and asking the protected acceptPartialPath hook (:239-246); search() loops while (results.size() < topN) (:310) and reports isComplete = rejectCount + topN <= maxQueueDepth (:409), true for 0. It is never reached.
5. Negative values do not throw: the size is never -1, so the queue grows without pruning (it keeps every seed path), and search() returns empty because results.size() < -1 is false.
6. Suggesters reach the same line. FreeTextSuggester.lookup never checks num (FreeTextSuggester.java:426); for each model whose last tokens have a matching prefix in the FST (others are skipped, :526-561) it builds TopNSearcher(fst, num, num + seen.size(), ...) (:607-608) with seen empty for the first model; its addIfCompetitive override delegates to super (:613-617). WFSTCompletionLookup.lookup has only assert num > 0 (:156) and calls Util.shortestPaths(..., num, ...) (:198). AnalyzingSuggester has only assert num > 0 (:670); its main searcher gets topN = num - results.size() and depth num * maxAnalyzedPathsForOneInput, so depth 0 (:785-786), and is seeded with the prefix paths (:819-821). Without EXACT_FIRST that happens for any matching prefix. With the default EXACT_FIRST, a key that is not itself a suggestion returns early at :777 (results.size() == num, 0 == 0); a key that is itself a suggestion is added by the exact-first pass (:769-775), so results.size() is 1, the early return is skipped, and the searcher (topN = -1, depth 0) throws. FuzzySuggester extends AnalyzingSuggester.

One-key FST "a" -> 1: topN = 1 returns a = 1; topN = 0 throws at Util.java:216, called from addStartPaths (:285), with assertions on and off. Suggesters with num = 0 (keys car, cat, dog; the FreeText model built from "the cat sat", "the car", "a dog"):

• FreeTextSuggester.lookup("the", 0) throws, with assertions on and off; lookup("the", 1) returns 1 result.
• WFSTCompletionLookup.lookup("c", false, 0) throws with assertions off (with assertions on, assert num > 0 fires first).
• AnalyzingSuggester built without EXACT_FIRST, lookup("c", false, 0), throws with assertions off (the study fix author's probe on main 7cecf79523, and the fact check's probe on 645d4fe14a20).
• AnalyzingSuggester / FuzzySuggester with their default EXACT_FIRST, assertions off: lookup("cat", false, 0) (the key is itself a suggestion) throws at Util.java:216; lookup("c", false, 0) returns 0 results. With assertions on, assert num > 0 (:670) fires first.
• FSTCompletionLookup and TSTLookup return 0 results; the NRT TopSuggestDocsCollector rejects 0 with IllegalArgumentException("'num' must be > 0"). (The study's reach test asserts only that FreeText must not throw; the other rows are its printed outcomes, re-checked by the fact check's probe.)

• Who is hit. Code that passes an explicit 0: direct callers of Util.shortestPaths / Util.TopNSearcher (public, @lucene.experimental); applications that pass a caller-supplied count to FreeTextSuggester.lookup(key, num), for example a request asking for 0 suggestions for a key that matches the model; and, with assertions off as in production, WFSTCompletionLookup.lookup(prefix, false, 0) for a prefix that is not itself a key, AnalyzingSuggester built without EXACT_FIRST for a matching prefix, and AnalyzingSuggester / FuzzySuggester with their default options for a key that is itself a suggestion. Lookup.lookup documents num as the "maximum number of results to return", with no minimum.
• What happens. That one call fails at once with an internal NoSuchElementException from TreeSet.last(), not with an error about the count. Code that catches IllegalArgumentException for bad arguments does not catch it.
• What does not happen. No wrong results, no corruption, no hang, no meaningful resource use, no effect on the index or on other requests. Data and scale play no part: one start arc offered to the queue is enough.
• Default vs opt-in. Nothing calls these with 0 by default; it takes an explicit count of 0. Likelihood: rare. The behaviour also differs between suggesters: FSTCompletionLookup and TSTLookup return 0 results for num = 0, AnalyzingSuggester / FuzzySuggester with default options (assertions off) return 0 results for a key that is not itself a suggestion and throw for one that is, and the NRT suggester rejects 0.

TestShortestPathsTopNZero builds a one-key FST ("a" -> 1, PositiveIntOutputs, BYTE1) with FSTCompiler, then calls Util.shortestPaths(fst, fst.getFirstArc(new FST.Arc<>()), 0L, Comparator.naturalOrder(), 0, false) and asserts top.topN.size() == 0. A NoSuchElementException is rethrown as an AssertionError that states expected and actual, with the original as its cause. Public API only (it sits in org.apache.lucene.util.fst like TestFSTs, but uses nothing package-private); no randomness of its own, so the seed does not matter (two seeds gave the same result). It compiles on 9.10.0 and later: FST.fromFSTReader, FSTCompiler.getFSTReader and a compile() that returns the FST metadata came together in #12831, first released in 9.10.0.

As the regression test: this same test, for example as testShortestPathsTopNZero in TestFSTs. With fix A it passes ./gradlew :lucene:core:check -x test unchanged. If the maintainer picks option B (reject 0), its assertion becomes expectThrows(IllegalArgumentException.class, () -> Util.shortestPaths(...)).

cp TestShortestPathsTopNZero.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/fst/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.fst.TestShortestPathsTopNZero -Ptests.seed=DEADBEEF
# assertions off: add -Ptests.asserts=false (same result)

TestShortestPathsTopNZero > testTopNZeroReturnsEmptyResult FAILED
    java.lang.AssertionError: expected an empty result for topN=0, got java.util.NoSuchElementException
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:E5AE15C911A0C3BF]:0)
        at org.apache.lucene.util.fst.TestShortestPathsTopNZero.testTopNZeroReturnsEmptyResult(TestShortestPathsTopNZero.java:38)

        Caused by:
        java.util.NoSuchElementException
            at java.base/java.util.TreeMap.key(TreeMap.java:1638)
            at java.base/java.util.TreeMap.lastKey(TreeMap.java:310)
            at java.base/java.util.TreeSet.last(TreeSet.java:404)
            at org.apache.lucene.util.fst.Util$TopNSearcher.addIfCompetitive(Util.java:216)
            at org.apache.lucene.util.fst.Util$TopNSearcher.addStartPaths(Util.java:285)
            at org.apache.lucene.util.fst.Util$TopNSearcher.addStartPaths(Util.java:257)
            at org.apache.lucene.util.fst.Util.shortestPaths(Util.java:471)
            at org.apache.lucene.util.fst.TestShortestPathsTopNZero.testTopNZeroReturnsEmptyResult(TestShortestPathsTopNZero.java:34)

# gradle, main 645d4fe14a20, -Ptests.seed=DEADBEEF -Ptests.asserts=false; identical with assertions on

• Contract. shortestPaths: "Starting from node, find the top N min cost completions to a final node." (Util.java:455), with no range and no @throws. TopNSearcher: "@param topN the number of top scoring entries to retrieve", "@param maxQueueDepth the maximum size of the queue of possible top entries" (Util.java:185-186), no range. Lookup.lookup: "@param num maximum number of results to return" (Lookup.java:190, 206, 219); nothing there says 0 is invalid. The FST package docs show "N-shortest paths by weight" (package-info.java:82-95) with no range.
• The code already means "empty" for 0. search() returns an empty, complete result for topN = 0 (Util.java:310, :409); the throw happens before it. topN = -1 returns empty. AnalyzingSuggester itself builds a TopNSearcher(0, 0) whenever an EXACT_FIRST lookup finds no exact match (count * maxSurfaceFormsPerAnalyzedForm with count == 0, AnalyzingSuggester.java:731-735), so 0 is a depth Lucene uses; it just never seeds that searcher.
• History: by all appearances an accidental regression. Before LUCENE-4480 the searcher pruned only once a separate bottom field was set, which never happened for topN = 0: release 4.0.0 and the parent commit return an empty result. LUCENE-4480 ("handle insert into empty queue correctly", 2012-10-12), which fixed a different NoSuchElementException (queue exhaustion with topN = 4), replaced it with if (queue.size() == topN) { bottom = queue.last(); ..., which throws for 0. LUCENE-4481 gave today's queue.size() == maxQueueDepth. Neither issue (#5546, #5547) mentions 0.
• Tests never tried 0. TestFSTs draws topN from TestUtil.nextInt(random, 1, 10) (TestFSTs.java:1517, :1641), and its fixed shortest-path tests use 3 (:1341-1347, :1442-1448).

The strongest case for "not a bug" (the cross-model reviewer's and the verifiers'): some suggesters assert num > 0 (WFSTCompletionLookup.java:156, AnalyzingSuggester.java:670) and the NRT collector throws IllegalArgumentException for num <= 0 (TopSuggestDocsCollector.java:77-78), so the project's convention may be that 0 is not a valid count; Util is @lucene.experimental; and the call already fails loudly.

Why it fails: that convention is stated for none of shortestPaths, TopNSearcher, Lookup or FreeTextSuggester. An assert states an internal invariant, not an API precondition, and it is off in production, where WFSTCompletionLookup, AnalyzingSuggester and FuzzySuggester can then hit this exact throw. @lucene.experimental means the API may change, not that inputs are undefined. And even if 0 should be rejected, an internal NoSuchElementException from TreeSet.last() is not how Lucene rejects arguments: the facets module normalised topN <= 0 to IllegalArgumentException (#11503 / PR #751). Residual risk: a maintainer may prefer an IllegalArgumentException to an empty result; that is a choice of fix (option B), not "works as designed".

Fix A was validated through gradle in a scratch worktree of 645d4fe14a20. B and C are alternatives from the study's fix notes and the reviews; neither was run.

In Util.TopNSearcher.addIfCompetitive, inside the queue-full branch and before queue.last(), return when maxQueueDepth == 0. It leaves the queue as the non-full branch would (that branch adds the path and drops it again at once); it only skips building that path and asking the protected acceptPartialPath hook, which in the tree only NRTSuggester overrides (its collector rejects num <= 0).

--- a/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
@@ -213,6 +213,10 @@
       T output = fst.outputs.add(path.output, path.arc.output());
 
       if (queue.size() == maxQueueDepth) {
+        if (maxQueueDepth == 0) {
+          // Queue can't hold any path, so nothing competes
+          return;
+        }
         FSTPath<T> bottom = queue.last();
         int comp = pathComparator.compare(path, bottom);
         if (comp > 0) {

Trade-offs

• Fixes the wrong assumption where it lives, so every caller is covered: shortestPaths, the public TopNSearcher constructor, FreeTextSuggester (its override delegates to super), WFSTCompletionLookup, and AnalyzingSuggester / FuzzySuggester with and without EXACT_FIRST (no throw anywhere in the fact check's probe with the fix).
• Restores the 4.0.0 result (empty; 4.0.0 returned a MinResult[], with no isComplete) and matches what search() computes: topN = 0 gives an empty result with isComplete = true; topN >= 1 with depth 0 gives empty with isComplete = false ("queue too small"), both from the existing formula (Util.java:409). No change for depth 1 or more, or for negative depth.
• With assertions off, an exact-key lookup with 0 on AnalyzingSuggester / FuzzySuggester (default options) then returns its 1 exact match instead of throwing, as WFSTCompletionLookup already does: more results than num, from the exact-first step (option C).
• Cost: one comparison of a final int, only inside the already-full branch, which then walks the tree anyway.
• It silently accepts 0, which some may see as hiding a caller bug.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, seed DEADBEEF, 2026-11-01: without the fix the repro fails with assertions on and off; with it, it passes with assertions on and off.
• ./gradlew :lucene:core:test --tests 'org.apache.lucene.util.fst.*': 9 classes (including TestFSTs and the repro), 38 tests, 0 failures, 5 skipped (2 @Nightly, 3 @Ignore).
• ./gradlew :lucene:suggest:test (every other TopNSearcher caller lives there): 31 classes, 236 tests, 0 failures, 7 skipped.
• ./gradlew :lucene:core:check -x test with the fix and the repro as a new test file: passes (google-java-format, ecj lint, forbidden APIs; error-prone not enabled). The full Lucene test suite was not run.
• Earlier: with the fix shadowed into the stock jars the repro passes with assertions on and off; the cross-model reviewer's own tests and the TestFSTs tests it ran pass; FreeText, WFST (prefix) and Analyzing (no EXACT_FIRST) return 0 results. The fact check's probe with the fix: no throw on any core or suggester path; AnalyzingSuggester / FuzzySuggester default lookup("cat", false, 0) with assertions off returns 1 result; TestFSTs passes.

Check topN < 1 at the top of Util.shortestPaths and num < 1 in FreeTextSuggester.lookup, like TopSuggestDocsCollector does.

if (topN < 1) {
  throw new IllegalArgumentException("topN must be >= 1, got " + topN);
}

Trade-offs

• Explicit; matches the NRT suggester and the facets precedent (#11503).
• It must not go into the TopNSearcher constructor: AnalyzingSuggester builds TopNSearcher(0, 0) whenever an EXACT_FIRST lookup finds no exact match (AnalyzingSuggester.java:731-735), so a constructor check would break ordinary lookups.
• Without that, the public constructor and AnalyzingSuggester / FuzzySuggester (without EXACT_FIRST, or with it for an exact-key lookup; assertions off) still reach the throw, so B needs A as well, or guards in each caller.
• It turns shortestPaths(-1) from empty into an exception; WFSTCompletionLookup passes -1 today for num = 0 with an exact key.

What the checks validated

Not run.

Today Lookup.lookup(num = 0) asserts, throws IllegalArgumentException, returns empty, or hits this throw, depending on the class. One documented rule (reject or empty) would settle it.

Trade-offs

A policy question across many classes, separate from this bug; it also covers the older WFSTCompletionLookup quirk that returns 1 result for num = 0 on an exact key with assertions off, which fix A does not change, and the same 1-result answer that AnalyzingSuggester / FuzzySuggester give for an exact key with fix A.

• Method: code reading, the study's non-formal tier. In the 2026-10-22 study, the FST verification experiment wrote a brute-force oracle for Util.shortestPaths to compare with Lucene's top-N search. The oracle's bounded scope used topN >= 1, so it did not find this; reading TopNSearcher.addIfCompetitive while writing it showed that queue.size() == maxQueueDepth holds for an empty queue when the depth is 0.
• Verification: an independent verifier (FST) wrote its own core test (three-key FST) and a suggester reach test, reproduced the throw with assertions on and off, found the FreeTextSuggester and WFSTCompletionLookup paths, and called it a new, low-severity bug.
• Later: the test was reduced to one test method on a one-key FST (2026-10-29), re-verified on main 645d4fe14a20 (2026-11-01), reviewed by a reviewer from another model family that ran its own tests, and its history was bisected by execution.