TSTLookup.build throws away its suggestions before it reads the new input

TSTLookup.build() replaces its ternary search tree with a new, empty one before it reads the input. The SortedInputIterator it creates next reads every entry and sorts them, and only after that does build() reset the entry count and fill the tree that lookups already see. So a lookup made while a rebuild reads its input finds nothing (upstream's own rebuild harness, which the tests of five other suggesters run and which orders the two threads with semaphores, fails on TSTLookup), and a rebuild that throws while the SortedInputIterator constructor reads or sorts the input (an IOException from the input, a temp-directory failure, an entry of 32,760 bytes or more, whose sort record with its 8-byte weight exceeds 32767 bytes) leaves a lookup with no suggestions whose getCount() still reports the previous build; store() and load() carry that pair into a new instance. After a rebuild whose input throws an IOException, FSTCompletionLookup, WFSTCompletionLookup and AnalyzingSuggester keep their previous suggestions: they already built their new FST aside and assigned it at the end of build() before 9.2.0, and LUCENE-10292 (9.2.0, Bug Fixes) made their count do the same; it did not touch TSTLookup. A later successful build repairs the state. Lookup documents neither failure atomicity nor concurrent build()/lookup(), so this is a low-priority consistency bug; building into local variables and assigning them at the end fixes both halves.

1. build() first does root = new TernaryTreeNode(); (TSTLookup.java:125). root is the field every lookup reads (:43, not volatile; lookup() calls autocomplete.prefixCompletion(root, key, 0), :188), so from here on lookups see an empty tree.
2. Then new SortedInputIterator(tempDir, tempFileNamePrefix, iterator, ...) (:128-129). Its constructor ends with this.reader = sort(); (SortedInputIterator.java:80), which writes every entry of the input to a temp file and sorts it (:175-195). Anything thrown here leaves build(): an IOException from the input (BytesRefIterator.next() is declared throws IOException), a temp-directory failure, or IllegalArgumentException("len must be <= 32767 ...") when the record, the entry plus its 8-byte weight (SortedInputIterator.java:216, :239-240), is longer than 32767 bytes, so for an entry of 32,760 bytes or more (OfflineSorter.java:550-551).
3. Only then count = 0; (:130) and count++ per sorted entry (:139). The failed-rebuild state below comes from a throw in the constructor of step 2, before this reset (every executed fault is of that kind); a throw later, while the loop (:135-140) reads the sorted entries back, would leave the empty tree with a partial count instead (by reading the code; not run).
4. Last, autocomplete.balancedTree(..., root) (:141) fills the root that lookups already see.
5. store() writes count and then the tree (:268-272); load() reads both back (:274-280). Both are synchronized; build() and lookup() are not, so this orders nothing between a rebuild and lookups.

• During a rebuild (the repro): built from bar/10, rebuilt from bar/10 + baz/5 by upstream's SuggestRebuildTestUtil, lookup("ba") returns 0 suggestions instead of 1 while the rebuild sits in its first next(); assertions on and off, also on the 10.5.2 and 10.6.0 jars. The repro stops at that check; a separate semaphore-controlled probe with the same data shows 2 suggestions ([bar/10, baz/5], getCount() 2) after the rebuild returns.
• After a failed rebuild (a probe): same data, the input throws IOException on its 2nd next(). TSTLookup: lookup("ba") = [], getCount() = 1; the same after store() + load() into a new instance; [bar, baz], 2 after a later good build. FSTCompletionLookup, WFSTCompletionLookup, AnalyzingSuggester: [bar], 1 (the same after a temp-file failure; an entry of 32,760 bytes does not fail the FST and WFST builds at all). With the fix, TSTLookup keeps [bar], 1.

WFSTCompletionLookup, FSTCompletionLookup and AnalyzingSuggester build their new FST aside and assign it at the end of build(); they already did so before 9.2.0. LUCENE-10292 changed only their count to work the same way: a local newCount, assigned after the FST, in a volatile field (WFSTCompletionLookup: long newCount = 0; :107; fst = ...; count = newCount; :129-130; private volatile long count :73; FSTCompletionLookup :103, :213, :245; AnalyzingSuggester :167, :410, :589-590).

• Who is exposed. Applications that use TSTLookup (the application picks it; nothing in Lucene selects it by default) and rebuild the same instance in place: lookups served while build() runs, or the instance kept after a build() that threw.
• What happens. During the rebuild every lookup returns nothing until the input has been read, sorted and copied, a window that covers the whole read of the dictionary (by reading the code; not timed). After a failed rebuild the lookup answers from an empty tree while getCount() still reports the last successful build's number of entries; store() persists that pair, so loading the stored file later keeps it. No exception beyond the one the failing input already threw.
• Transient. The next successful build(), or a load() of a good file, repairs it.
• How likely. Rare: it needs an in-place rebuild of a live instance, or a rebuild that fails and an application that keeps serving the instance. Nobody has reported either half since 2010 and 2014.
• Scale. Independent of dictionary size (the probe uses 1 and 2 entries). The failed-rebuild half is single-threaded and deterministic; the during-rebuild repro is deterministic because the harness orders the two threads with semaphores. For callers that do not synchronize, root and count are plain fields, so the Java memory model does not say when another thread sees the empty tree.

Copy the file to lucene/suggest/src/test/org/apache/lucene/search/suggest/tst/ (a new directory) and run the command. The harness, Input and InputArrayIterator are already in that test source set. The harness builds from [bar/10] and checks 1 result; then it rebuilds from [bar/10, baz/5] in one background thread whose input blocks in every next() until the main thread has re-run the check; after the rebuild it checks 2 results. Concurrency is the claimed behaviour of this half; the thread is the harness's own. The semaphores also order the two threads' memory accesses, so the test shows what a lookup sees while the rebuild reads its input; it does not show that unsynchronized concurrent calls are safe, with or without the fix. Pass -Ptests.asserts explicitly, because by default the build picks it from the seed. The failed-rebuild half (an IOException while the input is read) is described with its executed numbers in the explanation above and is not a second repro. The test is the suggested regression test as it stands.

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

# gradle, main 645d4fe14a20, seed DEADBEEF, -Ptests.asserts=true (the same with false)
TestTSTLookupDuringRebuild > testLookupsDuringReBuild FAILED
    java.lang.AssertionError: expected:<1> but was:<0>
        at org.apache.lucene.search.suggest.tst.TestTSTLookupDuringRebuild.lambda$testLookupsDuringReBuild$0(TestTSTLookupDuringRebuild.java:34)
        at org.apache.lucene.search.suggest.SuggestRebuildTestUtil.testLookupsDuringReBuild(SuggestRebuildTestUtil.java:84)
        at org.apache.lucene.search.suggest.tst.TestTSTLookupDuringRebuild.testLookupsDuringReBuild(TestTSTLookupDuringRebuild.java:31)
1 test completed, 1 failed

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

• Upstream tests this property. SuggestRebuildTestUtil is "Reusable Logic for confirming that Lookup impls can return suggestions during a 'rebuild'" (SuggestRebuildTestUtil.java:29). testLookupsDuringReBuild runs in TestWFSTCompletion, TestFSTCompletion, TestAnalyzingSuggester, TestFreeTextSuggester and TestAnalyzingInfixSuggester. TSTLookup has no test class: it appears only in TestPersistence and the @Ignored TestLookupBenchmark.
• Analogous problems in the infix and FST-based suggesters were fixed as bugs. CHANGES.txt, 9.2.0, Bug Fixes: "LUCENE-10292: Suggest: Fix AnalyzingInfixSuggester / BlendedInfixSuggester to correctly return existing lookup() results during concurrent build(). Fix other FST based suggesters so that getCount() returned results consistent with lookup() during concurrent build()." gh#11328 is labelled type:bug.
• TSTLookup was missed, not excluded. Chris Hostetter, the fix's author, wrote on gh#11328 (2022-04-07): "I refactored the test code so that it could be applied to all other Lookup impls (that have a build() method) and found that while none of the other impls had the same problem of .lookup() failing to return suggestions during a (re)build"; the comment goes on to say that a few FST-based ones had an inconsistent getCount(). None of the issue's 20 comments mentions TST. The issue description (Chris Hostetter, 2021-12-06) states the expectation: "With all other Lookup implementations I've examined, it is possible to call lookup() regardless of whether another thread is concurrently calling build()" and "Typically this is works because the build() method uses temporary datastructures until it's "build logic" is complete, at which point it atomically replaces the datastructures used by the lookup() method." (verbatim, typos included).
• The count's contract. getCount(): "Get the number of entries the lookup was built with" (Lookup.java:172; the field comment at TSTLookup.java:46 says the same). After a failed rebuild TSTLookup answers from 0 entries and reports the previous build's count.
• No recorded decision. The reset at :125 is from the class's first version (SOLR-1316, 2010); count = 0 after the sort is from LUCENE-5404 (2014), whose review discussed the count's type and persistence, not failures.
• Not a documented contract. Lookup promises nothing about the state after build() throws or about lookups during build() (see below). The case rests on upstream's own test, on what the siblings do and on the getCount() wording.

The strongest case: Lookup is @lucene.experimental and documents neither what build() leaves behind when it throws nor concurrent build()/lookup(). On gh#11328 Dawid Weiss asked "how did you arrive at the conclusion that Lookup.build can be called concurrently? I don't think this is mentioned anywhere in Lookup documentation" (2022-04-27), said the test "tests the behavior that isn't guaranteed or documented by the Lookup class" and that "Concurrency concerns should be handled by the code that uses Lookups" (2022-04-29); Chris Hostetter agreed "there's nothing in the docs that implies/guarantees anything about what getCount will return during a build" (2022-04-28). TSTLookup.add() changes the tree without touching count, root and count are plain fields (so even the fix gives a concurrent reader no visibility guarantee), an empty lookup is a valid state on its own, and the CHANGES entry names AnalyzingInfixSuggester / BlendedInfixSuggester and "other FST based suggesters", which TSTLookup is not.

Why it fails: that shows the behaviour is unspecified, not intended. Dawid Weiss also wrote "I don't want you to revert the changes you made", and the harness and its five call sites are still on main. The failed-rebuild half needs no concurrency: one thread, a legal IOException, and the instance then serves nothing while its count still reports the last successful build, which none of the three siblings above does in the probe. Verdict: a low-priority consistency bug; "improvement" would be a fair label. It is not a thread-safety violation, it rests on no strict count invariant, and not every sibling is failure-atomic (FreeTextSuggester resets totTokens before it reads its input).

Options A and B were applied in one scratch worktree of main 645d4fe14a20 (stock first, then each patch) and run through gradle with assertions on and off; the worktree was removed afterwards. C and D were not run.

TernaryTreeNode newRoot and long newCount replace the early root = ... and count = 0; after balancedTree(..., newRoot) the method assigns root = newRoot; count = newCount;. +6/-4 lines in TSTLookup.build(), the way the siblings publish their new FST and, since LUCENE-10292, their count. It fixes both halves: lookups keep the previous tree while the rebuild reads its input, and a rebuild that throws leaves the previous tree and count in place. root and count stay two separate plain writes: the fix removes the long empty window, but it is not atomic and gives a concurrent reader no visibility guarantee (trade-offs below).

--- a/lucene/suggest/src/java/org/apache/lucene/search/suggest/tst/TSTLookup.java
+++ b/lucene/suggest/src/java/org/apache/lucene/search/suggest/tst/TSTLookup.java
@@ -122,12 +122,12 @@
     if (iterator.hasContexts()) {
       throw new IllegalArgumentException("this suggester doesn't support contexts");
     }
-    root = new TernaryTreeNode();
+    TernaryTreeNode newRoot = new TernaryTreeNode();
 
     // make sure it's sorted and the comparator uses UTF16 sort order
     iterator =
         new SortedInputIterator(tempDir, tempFileNamePrefix, iterator, utf8SortedAsUTF16SortOrder);
-    count = 0;
+    long newCount = 0;
     ArrayList<String> tokens = new ArrayList<>();
     ArrayList<Number> vals = new ArrayList<>();
     BytesRef spare;
@@ -136,9 +136,11 @@
       charsSpare.copyUTF8Bytes(spare);
       tokens.add(charsSpare.toString());
       vals.add(iterator.weight());
-      count++;
+      newCount++;
     }
-    autocomplete.balancedTree(tokens.toArray(), vals.toArray(), 0, tokens.size() - 1, root);
+    autocomplete.balancedTree(tokens.toArray(), vals.toArray(), 0, tokens.size() - 1, newRoot);
+    root = newRoot;
+    count = newCount;
   }
 
   /**

Trade-offs

• root and count are still set by two separate writes, as in the siblings, so a lookup at that very moment can see one without the other. With A neither field is volatile (the siblings' count is), so nothing guarantees when another thread sees the new tree; option B makes count volatile, which lookup() does not read, so B does not publish root safely either. A removes the long empty window, not every race.
• The previous tree stays reachable until the new one is complete, so peak heap during a rebuild holds the old tree, the token and weight lists and the new tree, as the siblings keep their old FST (by reading the code). The current order lets the old tree be collected before the read, which lowers that peak; that may be why build() clears it first, though no source comment or commit message gives a reason. The fix trades memory for consistency.
• A rebuild from an empty input still ends with an empty tree and count = 0, as before.

What the checks validated

• Gradle in a scratch worktree of main 645d4fe14a20, seed DEADBEEF, assertions on and off: the repro fails stock (expected:<1> but was:<0>) and passes with the fix.
• The repro, the hunt's 2-test failed-rebuild JUnit (added for this check only; not part of the repro) and the upstream TestPersistence, TestWFSTCompletion and TestFSTCompletion: 5 classes, 26 tests; stock 3 failures, with the fix 0, each way.
• All of :lucene:suggest:test with the fix, assertions on: 33 classes (the 31 upstream ones plus the repro and the hunt's 2-test JUnit), 239 tests, 7 skipped, 0 failures.
• :lucene:suggest:check -x test (google-java-format, ecjLint, forbiddenApis) passes with the fix and the repro added.
• Re-checked in a fresh scratch worktree of 645d4fe14a20 (seed DEADBEEF): the repro fails stock and passes with the fix, together with TestPersistence, assertions on and off.
• Through the repro harness: with the fix shadowed, the failed-rebuild probe keeps [bar], getCount() = 1 after the failed rebuild and after store() + load(). Earlier, the fault-injection harness, run with the fix and assertions off, found no mixed states (the temp-file mismatches of a separate candidate remain), and the finder's, the independent reproduction's and the intended-behaviour check's checks pass with it.

Mirrors the siblings exactly: WFSTCompletionLookup, FSTCompletionLookup and AnalyzingSuggester declare count volatile and assign it after the structure. Making root volatile too would be the same idea for the tree (not run).

Trade-offs

Gives getCount() cross-thread visibility (not root, which lookups read and which stays plain), but it is a step towards promising concurrent use, the API question Dawid Weiss raised on gh#11328; it does not answer it.

What the checks validated

Gradle, same worktree and seed, assertions on and off: the repro and the same 5 classes (26 tests) pass, and :lucene:suggest:check -x test passes. The whole module was not run for B.

Say on Lookup.build() or TSTLookup that the lookup may return nothing while build() runs and may be empty if build() throws, and that callers should build a new instance and swap it in.

Trade-offs

The smallest change, in line with Dawid Weiss's view and the open LUCENE-4492 (#5558, immutable suggesters), but TSTLookup stays the one suggester that behaves this way, and the stale getCount() after a failed rebuild stays.

Build a new TSTLookup and replace the reference only after build() returns.

Trade-offs

Avoids both halves today; every application has to know to do it.

• Method (semi-formal): bounded-exhaustive fault-injection translation validation on the stock jar, in a hunt unit on suggester rebuild failure atomicity. The harness builds each Lookup twice (every input of up to 2 entries for the first build and up to 3 for the second, from a fixed entry set), injects every fault that can fail the second build (an IOException or RuntimeException from the InputIterator, createTempOutput and openInput failures, an entry whose sort record exceeds 32767 bytes) and requires the state after the failure (lookups and getCount()) to equal the previous build or an empty lookup.
• Result for TSTLookup. 4,323 checks per assertion mode, 2,409 failed second builds, 1,890 mixed states (empty tree, previous count) across all five fault kinds; 0 in the recorded run with the fix (assertions off), where only the temp-file mismatches of a separate candidate remain. The plan had named the early tree reset as a lead; the harness showed the count disagreement that makes it a mixed state rather than an empty lookup.
• Reduction. The finder reduced it to a public-API JUnit (a FileDictionary whose stream throws after its first line, and a latch-ordered lookup during a rebuild). The repro was later minimized to one test that runs upstream's own rebuild harness on TSTLookup.