FSTCompletion.lookup returns one shared, mutable list for empty results, so adding to it leaks into every other FSTCompletion in the JVM

FSTCompletion (module lucene/suggest, @lucene.experimental) is the FST autocomplete engine behind FSTCompletionLookup. Its lookup(key, num) returns one private static final ArrayList field, EMPTY_RESULT, whenever the key is empty or the instance was built with no entries (its automaton is then null). That list is the same object for every call on every instance (a static field exists once per loaded class, so in a typical application once per JVM), and it is mutable. So when a caller adds to the list it got for an empty key, for example a fallback suggestion, every other FSTCompletion, even one built from a different dictionary, returns that entry for empty keys from then on, with no error, until some code clears the list or the JVM restarts; an instance with no entries returns it for every key, and FSTCompletionLookup, which copies results, returns the polluted entries for empty keys too. Lucene's own code does not modify a result, so it takes application code that writes into a returned list. It has been there since FSTCompletion was created (SOLR-2888, first released in 3.6.0); since 10.0.0 every non-empty result is unmodifiable, so the empty one is the only list that silently accepts the change. The fix is one line: return List.of();.

1. One static list. FSTCompletion.java:77-81: private static final ArrayList<Completion> EMPTY_RESULT = new ArrayList<>();, with the comment "An empty result. Keep this an ArrayList to keep all the returned lists of single type (monomorphic calls)."
2. Returned as the result. lookup(CharSequence key, int num) (:197-210) starts with if (key.isEmpty() || automaton == null) { return EMPTY_RESULT; } (:198-200): the object itself, not a copy. The early return also skips num, so after several appends every empty lookup returns all of them (by reading, not executed).
3. No entries means a null automaton. FSTCompletionBuilder.build() (FSTCompletionBuilder.java:190-197) calls buildAutomaton, which returns null when no entry was added (:223), and the FSTCompletion constructor accepts it (FSTCompletion.java:113-122). Such an instance returns EMPTY_RESULT for every key.
4. Non-empty results are different. :206 and :208 return lookup(key)...limit(num).toList(), an unmodifiable list, a new one for each non-empty result (java.util.ImmutableCollections$ListN on JDK 25, executed). An unmatched non-empty prefix such as "q" takes this path too and gets an unmodifiable empty list (executed; on JDK 25 that is the JDK's own shared immutable empty list, which nobody can change). Among the paths inspected, only the early return hands out a list a caller can change.
5. The Lookup wrapper copies, then shows the pollution. FSTCompletionLookup.lookup (FSTCompletionLookup.java:262-281) calls completion.lookup(key, num) and copies each completion into a new ArrayList<LookupResult>, so Lookup users cannot cause the pollution, but after someone else did, their empty-key lookups return the added entries.
6. Who else uses it. In lucene/*/src/java only FSTCompletionBuilder and FSTCompletionLookup reference FSTCompletion; neither modifies a result.

Three instances, apple (from "apple"), zebra (from "zebra") and none (no entries), and zebraLookup = new FSTCompletionLookup(null, null, zebra, true). One caller runs apple.lookup("", 5).addAll(apple.lookup("a", 1)):

zebra.lookup("", 5) is the very list the caller changed (== is true). The zebra dictionary never contained "apple".

• Who is exposed. Direct users of the @lucene.experimental FSTCompletion whose code modifies a list that lookup returned for an empty key, or that an instance with no entries returned for any key. The natural pattern is "if the list is empty, add fallback (default, recent, per-user) suggestions".
• Version nuance. Since 10.0.0 (#12978) modifying a non-empty result throws UnsupportedOperationException, so only "modify when empty" code is silently hit. On 9.x and older every result was a mutable list the caller could change and only the empty one was shared, so any code that modified results was hit whenever a result was empty.
• Silent and lasting. No error; the change reaches every instance of the class (a class-wide static: one list per class loader, in a typical application the whole JVM) and stays until some code clears the list or the JVM restarts. If the application keeps appending, the shared list keeps growing (by reading, not executed). FSTCompletion may be used by several threads at once (FSTCompletion.java:380-381), so such appends to an unsynchronized ArrayList can also race with other threads reading it, for example a ConcurrentModificationException (by reading, not executed).
• Default vs opt-in. Lucene's own code does not modify a result (in lucene/*/src/java only FSTCompletionLookup calls lookup, and it copies); no setting, codec or scale is involved. It needs direct use of an experimental class plus application code that writes into a returned list. The Lookup entry point, FSTCompletionLookup, cannot trigger it, but returns the polluted entries for empty keys (executed).
• How likely. Rare: the pattern is ordinary Java, but no in-tree caller does it and nobody has reported it since 3.6.0 (2012).

This is the hunt's minimal repro with one change: the unused catch parameter is named _ instead of ignored, because Lucene's ecj lint rejects unused exception parameters; with it the test passes :lucene:suggest:check -x test. _ as a catch parameter needs Java 22 or later: fine on main (minimum Java 25); a source backport to 10.x (minimum Java 21) would need another form. The try/catch makes the test pass with either fix: an unmodifiable empty result throws on addAll, a fresh one absorbs it.

Executed: gradle on main e1faeba08bde with assertions on (seed 5EED1089) and off (5EED108A), both fail; the standalone runner on the 10.6.0 release jars with assertions on and off and on 9.12.3, all fail; the hunt's runs on main fail the same way. With the List.of() fix the test passes.

Use the same test as the regression test. It covers the empty-key trigger with an instance that has no entries as the victim; FSTCompletionLookup is shown only by the illustration probe. Its verdict does not depend on test order: on an unfixed tree it fails even if an earlier test already changed the shared list, and on a fixed tree nothing is shared. On an unfixed tree it does leave [apple/1] in the shared list, so later tests in the same JVM that look up an empty key (such as TestFSTCompletion.testEmptyInput) could fail too (by reading, not executed); the whole-suite gradle run was on the fixed tree only. To make it clean up after itself on an unfixed tree, clear apple.lookup("", 1) in a finally block that catches UnsupportedOperationException (not run).

cp $REPRO/TestFSTCompletionEmptyResult.java $LUCENE/lucene/suggest/src/test/org/apache/lucene/search/suggest/fst/
cd $LUCENE && ./gradlew :lucene:suggest:test --tests TestFSTCompletionEmptyResult -Ptests.seed=5EED1089 -Ptests.asserts=true
# also with -Ptests.asserts=false; nothing depends on the seed

TestFSTCompletionEmptyResult > testEmptyResultIsNotShared FAILED
    java.lang.AssertionError: expected:<[]> but was:<[apple/1]>
        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.fst.TestFSTCompletionEmptyResult.testEmptyResultIsNotShared(TestFSTCompletionEmptyResult.java:34)
1 test completed, 1 failed

# the same with -Ptests.asserts=false, and through the standalone runner on 10.6.0 (assertions on and off) and 9.12.3

• Contract. FSTCompletion.lookup (FSTCompletion.java:189-196): "@return Returns the suggestions, sorted by their approximated weight first (decreasing) and then alphabetically (UTF-8 codepoint order)." Lookup.lookup (Lookup.java:191): "@return a list of possible completions". Nothing says the list is shared, read-only or must not be modified, and CHANGES.txt, MIGRATE.md and the package docs say nothing either. The field is private, so a caller cannot know it got a shared object; java.util.List makes mutators optional, but this list supports them, so the defect is undocumented, surprising aliasing rather than a broken mutability promise.
• Test. TestFSTCompletion.testEmptyInput (TestFSTCompletion.java:238-241) asserts that an instance with no entries returns no suggestions for an empty key.
• Siblings. WFSTCompletionLookup (:163, :180) and AnalyzingSuggester (:679) return the unmodifiable Collections.emptyList() for empty lookup results.
• History. The predecessor FSTLookup, released in 3.3.0-3.6.2, returned an unmodifiable Collections.emptyList() (executed on 3.5.0 and 3.6.0). SOLR-2888 (92de7e88486, 2011) replaced it with the mutable ArrayList "to keep all the returned lists of single type (monomorphic calls)", a choice about the runtime class; none of its 21 JIRA comments, the commit message or the CHANGES entry mentions sharing. Since #12978 (10.0.0) non-empty results are ImmutableCollections$ListN, so the ArrayList is now the odd type out; List.of() has that same class (executed).
• Upstream precedent. #13055, #13087 and #13092 (2024) made other static final collections immutable. Those sweeps covered Set and Map constants, private ones included, but no List field, so this one was left as it was.

The strongest "intended / misuse" case (built by the devil's-advocate verifier; every reviewer rated it moderate but insufficient): the shared list was deliberate, a constant nobody was meant to modify; the class is @lucene.experimental, List mutators are optional, and no in-tree code modifies a result; since 10.0.0 non-empty results are unmodifiable, which suggests results are read-only; and maintainers called similar hardening cosmetic (#13092, dweiss: "These are cosmetic changes but they're worth backporting"; #13087, uschindler, on a public static Set constant: changing it "would be a downstream bug").

Why it fails: nothing documents a read-only rule, and unlike #13087's public constants this list is private and reaches the caller as its own result. From 3.6.0 to 9.12.3 every non-empty result was a fresh mutable list the caller owned, so modifying results worked; only the empty case aliased global state. #12978, which made non-empty results unmodifiable, had no description, no review comments and no CHANGES entry, so it is no documented contract. The change succeeds silently, crosses instances built from different data, and stays until some code clears the list. Net: not intended; a maintainer may well call the fix hardening, which is why it is Low.

One fix was built and validated in a scratch worktree of e1faeba08bde; the alternatives are listed with their trade-offs.

In FSTCompletion.lookup, return List.of() for an empty key or a null automaton and delete the field. The JDK's immutable empty list cannot leak between callers, and it has the same runtime class as the non-empty Stream.toList() results, so the field comment's "single type" aim is met again. On current JDKs List.of() returns one shared immutable empty list, so no allocation is added (an implementation detail, not an API guarantee). java.util.ArrayList stays imported for cacheRootArcs.

--- a/lucene/suggest/src/java/org/apache/lucene/search/suggest/fst/FSTCompletion.java
+++ b/lucene/suggest/src/java/org/apache/lucene/search/suggest/fst/FSTCompletion.java
@@ -74,12 +74,6 @@ public class FSTCompletion {
   /** Default number of buckets. */
   public static final int DEFAULT_BUCKETS = 10;
 
-  /**
-   * An empty result. Keep this an {@link ArrayList} to keep all the returned lists of single type
-   * (monomorphic calls).
-   */
-  private static final ArrayList<Completion> EMPTY_RESULT = new ArrayList<>();
-
   /** Finite state automaton encoding all the lookup terms. See class notes for details. */
   private final FST<Object> automaton;
 
@@ -196,7 +190,7 @@ public class FSTCompletion {
    */
   public List<Completion> lookup(CharSequence key, int num) {
     if (key.isEmpty() || automaton == null) {
-      return EMPTY_RESULT;
+      return List.of();
     }
 
     if (!higherWeightsFirst && rootArcs.length > 1) {

Trade-offs

A behaviour change for code that appends to an empty result: it now gets UnsupportedOperationException (executed with the illustration probe against the fixed classes), which is what it already gets for any non-empty result since 10.0.0.

What the checks validated

• stock: the test fails 1 of 1 with assertions on (seed 5EED1089) and off (5EED108A);
• fix A: the test plus TestFSTCompletion pass with assertions on (5EED108B) and off (5EED108C): 2 suites, 15 tests, 0 failures, 1 skipped (testRandom is @Nightly);
• the whole :lucene:suggest:test with assertions on (5EED108D): 32 suites, 237 tests, 7 skipped, 0 failures;
• :lucene:suggest:check -x test (checkGoogleJavaFormat, ecjLint, forbiddenApis) passes with the test in the tree;
• in the hunt, the repro, the 13 upstream TestFSTCompletion tests the standalone JUnit runner ran, and the independent reproducer's own test pass with the same fix.

Also removes the sharing, and keeps code that appends to an empty result working.

Trade-offs

One small allocation per empty lookup, and two result flavours on 10.x and later (mutable when empty, unmodifiable when not). Closer to the behaviour of a line where non-empty results are still mutable (9.x). Not validated.

Unmodifiable like A and what the sibling suggesters use.

Trade-offs

A third runtime class (Collections$EmptyList), against the field comment's stated aim. Not validated.

Method: non-formal (a cross-model idea, then executed probes and JUnit tests).

• Ideation, 2026-11-02: a concurrency idea from an independent reviewer of another model family (OpenAI GPT-5.6), "Concurrent FST lookup must not expose a globally mutable empty result", named FSTCompletion's static EMPTY_RESULT itself (FSTCompletion.java:77-81, :197-200) and proposed a two-thread test. A first probe turned that idea into a single-threaded cross-instance main() probe; on main (assertions on and off), 10.6.0, 9.12.3 and 9.1.0 it showed another instance returning the added entry, and a separate re-run agreed.
• A hunt unit, 2026-11-02: reduced it to one single-threaded public-API JUnit test, checked the history back to 3.6.0 and the runtime classes of the returned lists, and validated the List.of() fix.
• An independent reproducer, cross-model reviews, a devil's-advocate verifier, an adjudication and an audit then re-ran it (see the checks below).