The TSTLookup suggester throws StringIndexOutOfBoundsException on an empty key instead of returning null or a list

TSTLookup, the ternary-search-tree implementation of Lucene's Lookup suggester API, throws java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0 when it is asked about an empty key. Both public entry points fail: get(""), whose javadoc promises null for a key that does not exist, and lookup("", onlyMorePopular, num) for both onlyMorePopular values. Every TSTLookup is affected (built, restored with load(), never built, or built from an empty dictionary), with assertions on and off; non-empty keys work normally. The cause is one missing length check in TSTAutocomplete.prefixCompletion: its loop always runs, because the tree's root node always exists, and its first statement reads s.charAt(0). The code dates from SOLR-1316 (2010); all 14 Lucene releases run from 3.3.0 to 10.6.0, and main, fail, and every release tag checked has the same loop. Returning the empty list before the loop when there is no character to read fixes it; the suggest module's tests pass with that change.

TSTLookup.get(key)                    TSTLookup.java:157   autocomplete.prefixCompletion(root, key, 0)
TSTLookup.lookup(key, ctx, omp, num)  TSTLookup.java:188   autocomplete.prefixCompletion(root, key, 0)
   root is never null: TSTLookup.java:43 (field), :125 (build), :277 (load): new TernaryTreeNode()

TSTAutocomplete.prefixCompletion(TernaryTreeNode root, CharSequence s, int x)      TSTAutocomplete.java:97
  :99    TernaryTreeNode p = root;
  :102   while (p != null) {
  :103     if (s.charAt(x) < p.splitchar) {          <- s = "", x = 0: StringIndexOutOfBoundsException
  :105     } else if (s.charAt(x) == p.splitchar) {
  :106       if (x == s.length() - 1) { break; }     <- the only length check, after charAt

• The root is created as an empty node, so its character is the default '\u0000' (TernaryTreeNode.java:27-28). For keys that do not start with '\u0000' it is only the starting point and the entries hang below it; a key that starts with '\u0000' matches the root's character. Because the root is never null, the loop body runs at least once for every dictionary, including an empty or never-built one.
• A non-empty key is safe: x only grows while x < s.length() - 1, so charAt(x) stays in range. Only the empty key has no character 0.
• The empty key can never be stored: insert returns before it creates a node when s.length() <= x (TSTAutocomplete.java:58-59), and both build (through balancedTree, TSTAutocomplete.java:43) and add go through it (load restores whatever the stream holds; a stream that store wrote from such a tree holds no empty key). So get("") should be null.
• Nothing else checks the key: lookup checks only contexts, get nothing. TSTAutocomplete's constructor is package-private, so TSTLookup is the only public way in.

The recorded runs cover lookup("", false, 5), lookup("", true, 5), get("") and an empty StringBuilder key, and lookups built with TSTLookup(Directory, String), restored with load(), never built (new TSTLookup()) and built from an empty dictionary, with assertions on and off. Not every combination of form and state was run; in every state the root exists, so every form reaches the same unchecked charAt at TSTAutocomplete.java:103. Non-empty keys on the same lookup answer normally, before and after the failing calls.

• Who is exposed. Applications that use TSTLookup and pass it an empty key: typically an as-you-type box that forwards its text after the user clears it, or a get(""). TSTLookup is one of several Lookup implementations an application chooses explicitly; Lucene has no default suggester. FSTCompletionLookup's javadoc points users to it for fine-grained weights.
• What happens. An unchecked exception from an API that declares only IOException; if the caller does not catch it, that request fails. Nothing else: after 3,000 failing calls on a 20,000-entry dictionary, the stored bytes and 66 sampled non-empty answers (8 prefixes with both onlyMorePopular values, and 50 get calls) were unchanged, and a 4-thread run had 0 mismatches. Each failing call took about 8-9 microseconds (single runs on one host: an order of magnitude, not a benchmark).
• Scale. None: deterministic, every dictionary, on the first loop step.
• Versions. Lucene 3.3.0 (2011) to 10.6.0, and main: all 14 releases run in that range fail, and all 131 release tags of the history clone that contain the code have the same loop. Not every release was run; the clone has no 8.x tags after 8.8.1, so the later 8.x releases before 8.11.4 are covered by neither check. All runs used OpenJDK 25.
• How likely. Plausible, not common: it needs an application that forwards an empty key without a check. No public report was found in the searches below, although the code dates from 2010.
• Workaround. Check key.length() == 0 before calling lookup or get.

Create the directory lucene/suggest/src/test/org/apache/lucene/search/suggest/tst/ (it does not exist upstream), copy the file into it and run the command. The test body is deterministic, though it runs under Lucene's randomized test framework; pass -Ptests.asserts explicitly, because by default the build picks it from the seed. With the file added, :lucene:suggest:check -x test passes.

new TSTLookup() is the no-arg constructor ("Creates a new TSTLookup with an empty Ternary Search Tree."); a lookup built with TSTLookup(Directory, String) fails the same way, and so does lookup("", false, 5), at the same line. The test is the suggested regression test as it stands.

./gradlew :lucene:suggest:test --tests "org.apache.lucene.search.suggest.tst.TestTSTLookupEmptyKey" -Ptests.seed=DEADBEEF -Ptests.asserts=true

# gradle, main 645d4fe14a20, seed DEADBEEF, -Ptests.asserts=true (the same with false)
TestTSTLookupEmptyKey > testGetEmptyKeyReturnsNull FAILED
    java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:AAA38CA45D33748D]:0)
        ... (9 JDK-internal frames: Preconditions, String.checkIndex, StringLatin1.charAt)
        at java.base/java.lang.String.charAt(String.java:1624)
        at org.apache.lucene.search.suggest.tst.TSTAutocomplete.prefixCompletion(TSTAutocomplete.java:103)
        at org.apache.lucene.search.suggest.tst.TSTLookup.get(TSTLookup.java:157)
        at org.apache.lucene.search.suggest.tst.TestTSTLookupEmptyKey.testGetEmptyKeyReturnsNull(TestTSTLookupEmptyKey.java:25)
1 test completed, 1 failed

# with the recommended fix, assertions on and off:
:lucene:suggest:test (SUCCESS): 1 test
BUILD SUCCESSFUL

• get contradicts its own javadoc. "Returns the value for the specified key, or null if the key does not exist." (TSTLookup.java:155). The empty key cannot exist in a tree made by build or add (or restored from what store wrote), because insert drops it (TSTAutocomplete.java:58-59).
• lookup has no precondition. Lookup.lookup takes "lookup key. Depending on the implementation this may be a prefix, misspelling, or even infix", returns "a list of possible completions" and declares only IOException (Lookup.java:185-194, :209-211).
• Public API, though experimental. The package is exported by the suggest module and neither class is deprecated or tagged internal, but TSTLookup's base class Lookup is marked @lucene.experimental (Lookup.java:38); TSTAutocomplete has no such base class. That allows API changes between releases and is a point for low priority; it does not document an index exception.
• No test covers it. Upstream, TSTLookup appears only in TestPersistence (full keys) and the ignored TestLookupBenchmark, which looks up non-empty prefixes: the first 2-4, 6-9 or 100-200 characters of each dictionary key, or the whole key when shorter; none of its dictionary keys is empty.
• Siblings handle the empty key explicitly. FSTCompletion.lookup returns an empty result for key.isEmpty() (FSTCompletion.java:198, :221); AnalyzingSuggester lists among its limitations "Lookups with the empty string return no results instead of all results" (AnalyzingSuggester.java:95); LUCENE-8287 (2018) made empty regex completion queries return no results.
• History. The loop is unchanged since SOLR-1316 (2010). Its first caller, Solr's spellcheck-based Suggester, passed the text of each query token, which is normally non-empty, and it has no empty-token check, so the case was probably never considered. No commit, CHANGES or MIGRATE entry mentions it.

The strongest case for "intended": the empty-key result is deliberately not uniform across the module. For lookup("", false, 5) (the only form run on them), WFSTCompletionLookup returns every entry, FSTCompletionLookup, AnalyzingSuggester, FuzzySuggester, AnalyzingInfixSuggester and BlendedInfixSuggester return [], and FreeTextSuggester throws IllegalArgumentException on purpose, which TestFreeTextSuggester.testEmptyString asserts. So an exception for "" is accepted in this module, Lookup is marked experimental, and a caller can guard trivially.

Why it does not change the verdict: FreeTextSuggester's exception is a deliberate check with a message ("no tokens produced by analyzer, or the only tokens were empty strings", FreeTextSuggester.java:476-479); TSTLookup's is an incidental charAt range check that nothing documents, and get("") breaks a promise in its own javadoc. The argument bears on which answer to return ([], every entry, or a documented exception), not on whether an index exception is intended. Later cross-model reviews of this doc's brief (rounds 1 and 2) each rated the case for "intended" moderate and still judged the bug real, with low priority.

Option A answers "no completions", like most sibling suggesters and like get's javadoc. If maintainers prefer every entry (option C) or a documented exception (option D), the repro's expectation changes accordingly. No CHANGES entry is drafted.

In TSTAutocomplete.prefixCompletion, before while (p != null), return the (empty) result list when x >= s.length(). One check covers both entry points, lookup and get; non-empty keys never reach it.

     TernaryTreeNode p = root;
     ArrayList<TernaryTreeNode> suggest = new ArrayList<>();
+    if (x >= s.length()) {
+      // empty (remaining) key: the loop below reads s.charAt(x)
+      return suggest;
+    }
 
     while (p != null) {
       if (s.charAt(x) < p.splitchar) {

Trade-offs

It settles the answer as "no completions". The guard sits in the shared helper, so a later caller is covered too. A null key still throws NullPointerException, now from s.length() in the guard instead of s.charAt(x) (read, not run); neither lookup nor get documents null keys.

What the checks validated

• Gradle in a scratch worktree of main 645d4fe14a20, seed DEADBEEF, assertions on and off: the repro alone fails stock and passes with the fix.
• The repro with TestPersistence, the only non-ignored upstream test that builds a TSTLookup (the ignored TestLookupBenchmark builds one too): stock 1 failure (the repro), with the fix 3 of 3 pass, each way. Repeated in a fresh worktree, with the module run: same results.
• All of :lucene:suggest:test with the fix, assertions on: 32 classes (31 upstream), 237 tests, 7 skipped, 0 failures.
• :lucene:suggest:check -x test (google-java-format, ecjLint, forbiddenApis) passes with the fix and the repro added.
• Earlier, in the repro harness: with the fix, an independent 8-test JUnit passes 8 of 8 on main ea57360912ed (same file), and a probe on 645d4fe14a20 shows lookup("", false, 5) and lookup("", true, 5) returning [], get("") returning null and lookup("ca", false, 5) unchanged.

Return a new empty list from lookup (its res list is declared only after the prefixCompletion call) and null from get when key.length() == 0, before they call prefixCompletion.

Trade-offs

Same visible behaviour as A, but two guards instead of one, and prefixCompletion keeps its hidden precondition.

What WFSTCompletionLookup does ([cat/5, car/3, dog/2] on the example dictionary): every key starts with the empty prefix.

Trade-offs

For "", prefixCompletion would walk the whole tree and collect a reference to every entry's node before lookup trims the result to num (with onlyMorePopular true, lookup also creates a LookupResult per match); no entries or strings are copied, and a very short prefix that matches most entries costs the same today. It also differs from five sibling suggesters and from AnalyzingSuggester's documented choice. get("") must still return null.

Like FreeTextSuggester: a check with a clear message, documented in the javadoc.

Trade-offs

Better than an index exception, but callers still need their own guard, and get's javadoc, which promises null, would have to change.

• Method (semi-formal): bounded-exhaustive translation validation of two suggesters against an exact reference, on the real main jars: WFSTCompletionLookup (exactFirst on and off, onlyMorePopular false) and TSTLookup (onlyMorePopular true); FSTCompletionLookup was not in the model. Dictionaries: every sequence of 1 to 3 (string, weight) entries, duplicates allowed, with strings from "", a, b, aa, ab, ba, bb and weights 0, 1, 2 and Integer.MAX_VALUE (28 + 28^2 + 28^3 = 22,764 dictionaries; the empty dictionary is not in this scope, the independent JUnit and the probes cover it). Keys: every key of length at most 3 over a and b, including "" (15 keys); num 1 to 6: 6,146,280 checks.
• Signal. One exception class, StringIndexOutOfBoundsException, in 136,584 checks: every dictionary and every num for the empty key. The only other TSTLookup class was a duplicate-input weight difference (19,512 checks; no documented rule; not this bug). WFSTCompletionLookup had 0 mismatches.
• The class was reduced by hand to a public-API JUnit, and the repro was later minimized to the one test above.