TSTLookup throws StackOverflowError on deep trees: a list added in sorted order cannot be stored or loaded, and one long suggestion breaks build()

TSTLookup keeps its suggestions in a ternary search tree, one character per node. Four methods walk that tree recursively, one Java stack frame per tree level: TSTAutocomplete.insert (behind add() and build()), TSTLookup.writeRecursively (store()), readRecursively (load()) and TernaryTreeNode.sizeInBytes (ramBytesUsed()). At each key position the lo/hi links form a plain binary search tree with no rebalancing, so add() in sorted order builds a chain about as deep as the number of distinct first characters (that sorted insertion leaves this tree highly unbalanced was noted by the TST's author, Ankul Garg, on SOLR-1316 in 2009, as a speed concern). Every character of a key also adds one level, so one long suggestion is deep even through build().

Adding the 20,992 CJK Unified Ideographs in code-point order gives a tree 20,993 levels deep: add(), get() and lookup() work, but store(), load() and ramBytesUsed() throw StackOverflowError on the JVM's default thread stack (2040 KiB on Linux aarch64). One 20,000-character suggestion makes build() itself overflow in a fresh JVM. Lookup.store and load document failure only as a false return or an IOException, and add() "always returns true" with no order or length limit. The same keys through build(), or add()ed in shuffled order, work. Every release from 3.3.0 to 10.6.0, and main, has the recursive code; 11 of those releases, Solr 3.1.0, the 10.6.0 release commit and main were run and fail. An iterative rewrite of the four walks, in the same byte format, fixes it.

1. The tree. A TernaryTreeNode holds one character (splitchar) and the links loKid, eqKid, hiKid (TernaryTreeNode.java:27-40). TSTLookup starts from a sentinel root whose splitchar is U+0000 (TSTLookup.java:43, :125, :277).
2. Insertion recurses once per level. TSTAutocomplete.insert (TSTAutocomplete.java:57-86) calls itself through loKid (:73) and hiKid (:83) without advancing the key position, and through eqKid once per character (:66, :76). add() calls it on the root with no balancing (TSTLookup.java:149-153).
3. Sorted add() builds a chain. Increasing characters each become the hiKid of the previous one: 20,992 one-character keys give a hiKid chain under the root, depth 20,993. Law T1 (the finder's): add() in increasing or decreasing order gives depth at least 1 + the number of distinct first characters, whatever the key length; checked against the real tree read back through store() for 81 values of n from 0 to 2,960 (every n up to 49, then steps of 97) and 300 random sorted and reverse-sorted dictionaries, 0 mismatches.
4. build() balances only the lo/hi links. It sorts the input (TSTLookup.java:117-142) and inserts it middle-first through balancedTree (TSTAutocomplete.java:40-46, itself only about log2(n) deep). Law T2 (proved, and checked on every non-empty set of up to 4 of 39 short keys): through build() the depth is at most the longest key length + floor(log2 n) + 1, and the bound is tight. Short keys are safe; each character of a long key adds one eqKid level.
5. The other walks recurse once per level too. writeRecursively (TSTLookup.java:242-265, calls at :257, :260, :263) for store() (:267-272); readRecursively (:218-239, calls at :229, :233, :237) for load() (:274-280); TernaryTreeNode.sizeInBytes (TernaryTreeNode.java:50-69, calls at :53, :56, :59) for ramBytesUsed() (TSTLookup.java:282-290). get() and lookup() use prefixCompletion (TSTAutocomplete.java:97-148), which already walks with an explicit ArrayDeque: they work even on a 41,002-level tree with a 256 KiB thread.
6. Side note: the add() javadoc (TSTLookup.java:145) reads "Adds a new node if <code>key</code> already exists, otherwise replaces its value", the inverse of what insert does (since d4aace10381, 2012).

Largest tree depth (store, load, ramBytesUsed) or key length (build) that survives; "sorted add" = how many of 41,000 one-character keys, added in sorted order, went in before the first add() threw (> 41,000 = all of them); a fresh JVM per trial, JDK 25.0.3, Linux aarch64, -da, full tiered JIT. "Cold" = no warm-up, "warm" = every entry point compiled first.

The thresholds move with the JIT state, and not monotonically: after a warm-up one check loaded 15,000 and 40,000 levels on 1 MiB while 20,992 still failed, and on 10.5.2 with -ea the 20,000-character build() survived the default stack while store(), load() and ramBytesUsed() of that tree still failed. With Lucene's local test flags (-XX:TieredStopAtLevel=1, C1 only) the sorted add() of 20,992 keys already overflows a 2 MiB thread. Only Linux aarch64 was run.

• Who is exposed. Users of TSTLookup (opt-in, not deprecated; FSTCompletionLookup's javadoc points to it).
• Trigger 1: sorted add() of a word list with thousands of distinct first characters, in practice a CJK-scale dictionary (for Latin-script words each per-position chain is bounded by the alphabet; a reading of the code, not run). add() has no in-tree caller, but it is public.
• Trigger 2: one long suggestion, through build() or add(). An independent check reached it through Lucene's own LuceneDictionary over an indexed StringField term of 8,000 bytes: TSTLookup.build threw StackOverflowError on a 1 MiB thread in 8 of 8 runs (main and 10.5.2); 12,000- and 32,000-byte terms failed too.
• What breaks. The lookup works in memory but cannot be stored or loaded, so it is lost on restart; a load() that fails this way also leaves the lookup half replaced (a separate bug, LFV-979).
• Scale. Thousands of levels: in a fresh JVM on a 1 MiB thread store()/load() fail from about 5,300 levels and build() from about 5,900 characters; on a 2040 KiB thread from about 10,800-12,500 levels and 12,400 characters. The JIT state moves these numbers.
• How likely. Rare: it needs a degenerate input shape, and the searches found no public report since 2011. The error is a loud StackOverflowError in the calling thread, with no index damage; but a store() that overflows has already written part of the tree (the count first, then each node before the walk goes below it), so the output it was writing to holds an incomplete copy (a reading of the code, not run).
• Workarounds. build() instead of sorted add() (short keys only), a cap on suggestion length, or running the steps that walk the tree on a thread with a larger stack: store(), load() and ramBytesUsed(), and for a long suggestion build()/add() too (the sorted add() itself also overflows under C1-only JIT flags).

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected store() of the 20,992 add()ed keys to return true, but it threw java.lang.StackOverflowError
       org.apache.lucene.search.suggest.tst.TestTSTLookupSortedAddStore.testStoreAfterSortedAdd(TestTSTLookupSortedAddStore.java:50)
     Caused by: java.lang.StackOverflowError
       java.base/java.nio.Buffer.<init>(Buffer.java:255)
       java.base/java.nio.ByteBuffer.<init>(ByteBuffer.java:323)
       java.base/java.nio.HeapByteBuffer.<init>(HeapByteBuffer.java:75)
       java.base/java.nio.ByteBuffer.allocate(ByteBuffer.java:398)
       org.apache.lucene.store.ByteBuffersDataOutput.appendBlock(ByteBuffersDataOutput.java:525)
       [...]

• Contract. TSTLookup.add: "This method always returns true", no order or length limit (TSTLookup.java:144-153). Lookup.store: "Persist the constructed lookup data to a directory. Optional operation. ... @return true if successful, false if unsuccessful or not supported. @throws IOException when fatal IO error occurs." Lookup.load: "Discard current lookup data and load it from a previously saved copy", with the same failure modes (Lookup.java:236-252).
• Lengths the module accepts. build() sorts through OfflineSorter, which rejects entries over 32,767 bytes with a clear IllegalArgumentException (OfflineSorter.java:550-551); with the 8-byte weight, build() accepts suggestions up to 32,759 UTF-8 bytes (run by the fact check: 32,759 bytes accepted, 32,760 rejected with "len must be <= 32767; got 32768"). The 20,000-character suggestion is ASCII, 20,000 bytes. WFSTCompletionLookup builds, stores and loads it on a 1 MiB thread.
• Order alone flips the result. The same 20,992 keys through build(), or add()ed in the shuffled order tested, complete every step; the limit is tree depth, not key count.
• Tests. Only TestPersistence and the @Ignored TestLookupBenchmark use TSTLookup, through build() with short keys; no test asserts or excludes deep trees.
• Precedent. LUCENE-5628, under Lucene 4.8.1 "Bug fixes" (core's automaton code, used when building suggesters): "Change getFiniteStrings to iterative not recursive implementation, so that building suggesters on a long suggestion doesn't risk overflowing the stack; previously it consumed one Java stack frame per character in the expanded suggestion. If you are building a suggester this is a nasty trap." More CHANGES entries that removed or bounded stack-exhausting recursion: GITHUB#16423, #11813, #11537, LUCENE-10181, LUCENE-7914, LUCENE-7956 (listed by the intended-lens reviewer, OpenAI GPT-5.6) and GITHUB#12286, "Toposort use iterator to avoid stackoverflow" (added by the finder).
• History. On SOLR-1316 (2009) the TST's author, Ankul Garg, wrote that adding strings "in sorted order in TST will make the tree highly unbalanced" and that balancedTree "takes care of that"; Andrzej Bialecki asked whether it could be rebalanced on the fly. They discussed speed; store()/load() (2011) and the recursive size method (2014) did not exist yet.

The strongest "works as designed" case: (a) the authors knew sorted insertion unbalances the tree and handled it only in build(); add() is a vestige (no longer in the Lookup API since LUCENE-3807, no in-tree caller, not counted by getCount()). (b) Maintainers declined iterative rewrites for very long input before: on LUCENE-5659 (#6721, Won't Fix) Robert Muir declined an iterative isFinite and called such use "abuse of the automaton pkg for what its not designed to do"; on LUCENE-6156 (#7218, Not A Problem) Michael McCandless wrote that making the code non-recursive "makes the code more complex". (c) Lookup is @lucene.experimental and Accountable @lucene.internal (a point from the refute-lens reviewer, OpenAI GPT-5.6).

The answer: nothing in (a) is documented, and the long-key leg needs no sorted input: build(), the path the authors made safe, overflows on one legal suggestion that WFSTCompletionLookup accepts. On (b), both refused code paths were later changed by bounding or removing the recursion (LUCENE-7914 and GITHUB#11813 for isFinite; GITHUB#11537 / PR #12462 for RegExp), and LUCENE-5628 was fixed as a bug. (c) weakens only the ramBytesUsed() leg. This shows the behavior is not documented as intended; it does not settle the design choice: a maintainer could still prefer a length limit, deprecation or no change over a rewrite.

Option A was applied in scratch worktrees of main 645d4fe14a20 and run through gradle (seed DEADBEEF) and the repro harness. Options B to E were not run.

Three files, +127/-82 lines:

• TSTAutocomplete.insert: a loop walks down (lo/hi without advancing the key position, eq advancing it) and remembers the parent and the link; at the first missing node it appends the rest of the key as a chain of eqKid nodes. Same signature, return value and tree.
• writeRecursively / readRecursively become writeTree / readTree: pre-order with an explicit ArrayDeque, kids pushed hi, eq, lo so they come off lo, eq, hi. The byte format is unchanged, and the split-char read/write lines keep their content, so LFV-699's fix (it changes exactly those lines) composes with this one; the lines move into the new loops with new indentation, so whichever patch lands second needs a trivial rebase.
• TernaryTreeNode.sizeInBytes: the same sum with an explicit stack.
• The add() javadoc: "Adds a new node if <code>key</code> does not exist yet, otherwise replaces its value."

diff --git a/lucene/suggest/src/java/org/apache/lucene/search/suggest/tst/TSTAutocomplete.java b/lucene/suggest/src/java/org/apache/lucene/search/suggest/tst/TSTAutocomplete.java
index 787d9b78230..ca821148c88 100644
--- a/lucene/suggest/src/java/org/apache/lucene/search/suggest/tst/TSTAutocomplete.java
+++ b/lucene/suggest/src/java/org/apache/lucene/search/suggest/tst/TSTAutocomplete.java
@@ -58,30 +58,53 @@ public class TSTAutocomplete {
     if (s == null || s.length() <= x) {
       return currentNode;
     }
-    if (currentNode == null) {
-      TernaryTreeNode newNode = new TernaryTreeNode();
-      newNode.splitchar = s.charAt(x);
-      currentNode = newNode;
-      if (x < s.length() - 1) {
-        currentNode.eqKid = insert(currentNode.eqKid, s, val, x + 1);
+    // Walk down iteratively: the tree can be deeper than the thread stack allows recursion
+    // (keys added in sorted order chain up the loKid/hiKid links; long keys chain up eqKid).
+    TernaryTreeNode parent = null;
+    int link = 0; // the link from parent to node: 0 = loKid, 1 = eqKid, 2 = hiKid
+    TernaryTreeNode node = currentNode;
+    while (node != null) {
+      char c = s.charAt(x);
+      if (node.splitchar > c) {
+        parent = node;
+        link = 0;
+        node = node.loKid;
+      } else if (node.splitchar < c) {
+        parent = node;
+        link = 2;
+        node = node.hiKid;
+      } else if (x < s.length() - 1) {
+        parent = node;
+        link = 1;
+        node = node.eqKid;
+        x++;
       } else {
-        currentNode.token = s.toString();
-        currentNode.val = val;
-        return currentNode;
-      }
-    } else if (currentNode.splitchar > s.charAt(x)) {
-      currentNode.loKid = insert(currentNode.loKid, s, val, x);
-    } else if (currentNode.splitchar == s.charAt(x)) {
-      if (x < s.length() - 1) {
-        currentNode.eqKid = insert(currentNode.eqKid, s, val, x + 1);
-      } else {
-        currentNode.token = s.toString();
-        currentNode.val = val;
+        node.token = s.toString();
+        node.val = val;
         return currentNode;
       }
+    }
+    // the rest of the key becomes a new chain of eqKid nodes
+    node = new TernaryTreeNode();
+    node.splitchar = s.charAt(x);
+    if (parent == null) {
+      currentNode = node;
+    } else if (link == 0) {
+      parent.loKid = node;
+    } else if (link == 1) {
+      parent.eqKid = node;
     } else {
-      currentNode.hiKid = insert(currentNode.hiKid, s, val, x);
+      parent.hiKid = node;
+    }
+    while (x < s.length() - 1) {
+      x++;
+      TernaryTreeNode next = new TernaryTreeNode();
+      next.splitchar = s.charAt(x);
+      node.eqKid = next;
+      node = next;
     }
+    node.token = s.toString();
+    node.val = val;
     return currentNode;
   }
 
diff --git 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
index 04a59768e58..6da272e3db9 100644
--- 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
@@ -17,6 +17,7 @@
 package org.apache.lucene.search.suggest.tst;
 
 import java.io.IOException;
+import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Comparator;
@@ -142,7 +143,7 @@ public class TSTLookup extends Lookup {
   }
 
   /**
-   * Adds a new node if <code>key</code> already exists, otherwise replaces its value.
+   * Adds a new node if <code>key</code> does not exist yet, otherwise replaces its value.
    *
    * <p>This method always returns true.
    */
@@ -214,60 +215,72 @@ public class TSTLookup extends Lookup {
   private static final byte HAS_TOKEN = 0x08;
   private static final byte HAS_VALUE = 0x10;
 
-  // pre-order traversal
-  private void readRecursively(DataInput in, TernaryTreeNode node) throws IOException {
-    node.splitchar = in.readString().charAt(0);
-    byte mask = in.readByte();
-    if ((mask & HAS_TOKEN) != 0) {
-      node.token = in.readString();
-    }
-    if ((mask & HAS_VALUE) != 0) {
-      node.val = in.readLong();
-    }
-    if ((mask & LO_KID) != 0) {
-      node.loKid = new TernaryTreeNode();
-      readRecursively(in, node.loKid);
-    }
-    if ((mask & EQ_KID) != 0) {
-      node.eqKid = new TernaryTreeNode();
-      readRecursively(in, node.eqKid);
-    }
-    if ((mask & HI_KID) != 0) {
-      node.hiKid = new TernaryTreeNode();
-      readRecursively(in, node.hiKid);
+  // Pre-order traversal with an explicit stack: the tree can be deeper than the thread stack
+  // allows recursion (keys added in sorted order, or one long key).
+  private void readTree(DataInput in, TernaryTreeNode root) throws IOException {
+    ArrayDeque<TernaryTreeNode> stack = new ArrayDeque<>();
+    stack.push(root);
+    while (!stack.isEmpty()) {
+      TernaryTreeNode node = stack.pop();
+      node.splitchar = in.readString().charAt(0);
+      byte mask = in.readByte();
+      if ((mask & HAS_TOKEN) != 0) {
+        node.token = in.readString();
+      }
+      if ((mask & HAS_VALUE) != 0) {
+        node.val = in.readLong();
+      }
+      // the kids follow in the order lo, eq, hi: push them in reverse
+      if ((mask & HI_KID) != 0) {
+        node.hiKid = new TernaryTreeNode();
+        stack.push(node.hiKid);
+      }
+      if ((mask & EQ_KID) != 0) {
+        node.eqKid = new TernaryTreeNode();
+        stack.push(node.eqKid);
+      }
+      if ((mask & LO_KID) != 0) {
+        node.loKid = new TernaryTreeNode();
+        stack.push(node.loKid);
+      }
     }
   }
 
-  // pre-order traversal
-  private void writeRecursively(DataOutput out, TernaryTreeNode node) throws IOException {
-    // write out the current node
-    out.writeString(new String(new char[] {node.splitchar}, 0, 1));
-    // prepare a mask of kids
-    byte mask = 0;
-    if (node.eqKid != null) mask |= EQ_KID;
-    if (node.loKid != null) mask |= LO_KID;
-    if (node.hiKid != null) mask |= HI_KID;
-    if (node.token != null) mask |= HAS_TOKEN;
-    if (node.val != null) mask |= HAS_VALUE;
-    out.writeByte(mask);
-    if (node.token != null) out.writeString(node.token);
-    if (node.val != null) out.writeLong(((Number) node.val).longValue());
-    // recurse and write kids
-    if (node.loKid != null) {
-      writeRecursively(out, node.loKid);
-    }
-    if (node.eqKid != null) {
-      writeRecursively(out, node.eqKid);
-    }
-    if (node.hiKid != null) {
-      writeRecursively(out, node.hiKid);
+  // Pre-order traversal with an explicit stack, in the order readTree expects.
+  private void writeTree(DataOutput out, TernaryTreeNode root) throws IOException {
+    ArrayDeque<TernaryTreeNode> stack = new ArrayDeque<>();
+    stack.push(root);
+    while (!stack.isEmpty()) {
+      TernaryTreeNode node = stack.pop();
+      // write out the current node
+      out.writeString(new String(new char[] {node.splitchar}, 0, 1));
+      // prepare a mask of kids
+      byte mask = 0;
+      if (node.eqKid != null) mask |= EQ_KID;
+      if (node.loKid != null) mask |= LO_KID;
+      if (node.hiKid != null) mask |= HI_KID;
+      if (node.token != null) mask |= HAS_TOKEN;
+      if (node.val != null) mask |= HAS_VALUE;
+      out.writeByte(mask);
+      if (node.token != null) out.writeString(node.token);
+      if (node.val != null) out.writeLong(((Number) node.val).longValue());
+      // write the kids in the order lo, eq, hi: push them in reverse
+      if (node.hiKid != null) {
+        stack.push(node.hiKid);
+      }
+      if (node.eqKid != null) {
+        stack.push(node.eqKid);
+      }
+      if (node.loKid != null) {
+        stack.push(node.loKid);
+      }
     }
   }
 
   @Override
   public synchronized boolean store(DataOutput output) throws IOException {
     output.writeVLong(count);
-    writeRecursively(output, root);
+    writeTree(output, root);
     return true;
   }
 
@@ -275,7 +288,7 @@ public class TSTLookup extends Lookup {
   public synchronized boolean load(DataInput input) throws IOException {
     count = input.readVLong();
     root = new TernaryTreeNode();
-    readRecursively(input, root);
+    readTree(input, root);
     return true;
   }
 
diff --git a/lucene/suggest/src/java/org/apache/lucene/search/suggest/tst/TernaryTreeNode.java b/lucene/suggest/src/java/org/apache/lucene/search/suggest/tst/TernaryTreeNode.java
index 6bbba74641b..95b1b9076fc 100644
--- a/lucene/suggest/src/java/org/apache/lucene/search/suggest/tst/TernaryTreeNode.java
+++ b/lucene/suggest/src/java/org/apache/lucene/search/suggest/tst/TernaryTreeNode.java
@@ -16,6 +16,7 @@
  */
 package org.apache.lucene.search.suggest.tst;
 
+import java.util.ArrayDeque;
 import org.apache.lucene.util.RamUsageEstimator;
 
 /** The class creates a TST node. */
@@ -47,24 +48,32 @@ public class TernaryTreeNode {
 
   Object val;
 
+  /** Returns the memory used by this node and the subtree below it. */
   long sizeInBytes() {
-    long mem = RamUsageEstimator.shallowSizeOf(this);
-    if (loKid != null) {
-      mem += loKid.sizeInBytes();
+    // explicit stack: the tree can be deeper than the thread stack allows recursion
+    long mem = 0;
+    ArrayDeque<TernaryTreeNode> stack = new ArrayDeque<>();
+    stack.push(this);
+    while (!stack.isEmpty()) {
+      TernaryTreeNode node = stack.pop();
+      mem += RamUsageEstimator.shallowSizeOf(node);
+      if (node.loKid != null) {
+        stack.push(node.loKid);
+      }
+      if (node.eqKid != null) {
+        stack.push(node.eqKid);
+      }
+      if (node.hiKid != null) {
+        stack.push(node.hiKid);
+      }
+      if (node.token != null) {
+        mem +=
+            RamUsageEstimator.shallowSizeOf(node.token)
+                + RamUsageEstimator.NUM_BYTES_ARRAY_HEADER
+                + Character.BYTES * (long) node.token.length();
+      }
+      mem += RamUsageEstimator.shallowSizeOf(node.val);
     }
-    if (eqKid != null) {
-      mem += eqKid.sizeInBytes();
-    }
-    if (hiKid != null) {
-      mem += hiKid.sizeInBytes();
-    }
-    if (token != null) {
-      mem +=
-          RamUsageEstimator.shallowSizeOf(token)
-              + RamUsageEstimator.NUM_BYTES_ARRAY_HEADER
-              + Character.BYTES * (long) token.length();
-    }
-    mem += RamUsageEstimator.shallowSizeOf(val);
     return mem;
   }
 }

Trade-offs

• The explicit stacks live on the heap: about one entry per pending sibling on the current path, small next to the tree.
• Nothing is rebalanced: sorted add() still builds a chain and visits about n²/2 nodes for n keys, as today; only stack use changes. No benchmark was run.
• A load() that fails part-way leaves slightly different garbage (kids are allocated before their bytes are read); either way the lookup is half replaced (LFV-979).

What the checks validated

• Stock: the repro fails with java.lang.StackOverflowError in add() under Lucene's default local test JVM flags (this step, 2026-10-30) and with ... in store() under the full JIT (TEST_JVM_ARGS=-XX:+UseParallelGC, an earlier run of this step).
• With option A applied (this step, 2026-10-30): the repro and TestPersistence, the only upstream test that runs TSTLookup, pass under the default flags with assertions on: :lucene:suggest:test (SUCCESS): 3 tests, 0 failures.
• With option A, an earlier run of this step on the same commit: all of :lucene:suggest:test with the repro added passes (32 classes, 237 tests, 7 skipped, 0 failures); the repro passes with the full JIT; :lucene:suggest:check -x test (format, ecjLint, forbiddenApis) passes with the test and the fix added (not run on stock code plus the test).
• Repro harness, patched classes shadowed: the repro passes with -ea and -da; the finder's 8-test JUnit passes 8 of 8 (6 of 8 fail stock), covering build() and add() of a 20,000-character key, load() of a stored deep tree and ramBytesUsed() on 1 MiB threads.
• Byte-level check (400 random dictionaries, 78,005 observations of store() bytes, bytes stored after load(), get, lookup, ramBytesUsed): the same SHA-256 on stock and patched code; a mutant whose readTree pushes lo before hi fails. It covers only trees the stock code can store.

Cap the key length in insert (or in build() and add()), with a clear exception, as OfflineSorter does for entries over 32,767 bytes.

Trade-offs

Smaller, but it covers only the long-key leg: the sorted-add depth comes from the number of distinct first characters, so it would also need a depth limit that rejects add() calls that work today, at a threshold that depends on the stack size.

Say in the add() javadoc that it does not rebalance and that keys added in sorted order build a tree that store() and load() may not handle; recommend build().

Trade-offs

No code change, but build() still overflows on one long legal suggestion.

Keep the lo/hi links of each key position balanced as add() inserts (rotations, or a periodic rebuild), so sorted adds no longer chain.

Trade-offs

Covers only the sorted-add leg: a long key is one eqKid level per character, which no rebalancing shortens, so build() of a long suggestion still needs option A or B. More invasive than A, and it changes the tree shape that sorted adds give today (a reading of the code, not run).

Deprecate it, and later remove it, in favour of the FST-based suggesters, as Michael McCandless suggested for the sibling Jaspell trie on LUCENE-5775 (#6837); Jaspell was removed in 9.0.0 (LUCENE-8638).

Trade-offs

No code fix for current users until they migrate, and FSTCompletionLookup's javadoc still points to TSTLookup.

• First signal. A planning probe added 5,000 two-character keys in sorted order: load() threw StackOverflowError on a 1 MiB thread (2026-10-28).
• Method: bounded-exhaustive differential model check. An independent iterative model of the ternary tree against the real tree read back through the public store() output: every add() sequence of up to 4 keys from 12 strings and every non-empty build() set of up to 4 of 39 keys, plus sequential and random scopes (774,462 checks, 0 mismatches; a lo/hi-swap mutant of the model was rejected). That established law T1 (sorted add(): depth at least 1 + distinct first characters) and law T2 (build(): depth at most key length + floor(log2 n) + 1).
• Then the finder measured the stack threshold of every entry point (fresh JVMs, 512 KiB to 2 MiB, cold and warm JIT), wrote a public-API JUnit (8 tests), and the repro was later minimized to one test.