directAddressingMaxOversizingFactor decides how fixed-length FST nodes are stored. A negative value is documented to mean binary search only; a very negative value overflows the size comparison and selects direct addressing instead.
- An FST node with many arcs (at least 5 near the root, or at least 10 anywhere) is stored with fixed-length arcs (unless
allowFixedLengthArcsis turned off), so a lookup can jump to the right arc instead of scanning them all. - Binary search keeps one slot per arc: 5 arcs of 4 bytes are 20 bytes. Direct addressing keeps one presence bit for every label between the lowest and the highest: for labels 0 to 1,048,576 that is 131,073 bytes, but a lookup only tests the label's bit and counts the set bits before it.
FSTCompiler.Builder#directAddressingMaxOversizingFactorsays how much bigger direct addressing may be than binary search (default 1). Its javadoc: a negative value (e.g. -1) disables direct addressing.
-Infinity the allowed oversize stops at -2,147,483,648, the int cost 131,079 + 2,147,483,648 wraps to -2,147,352,569, and a cost <= 0 picks direct addressing. Select the still to open it at full size. Generated with AI, checked against the code.- Build an FST with
FSTCompiler.Builder(BYTE4 labels,NoOutputs) and setdirectAddressingMaxOversizingFactor(Float.NEGATIVE_INFINITY), because the javadoc says a negative value disables direct addressing. Add the keys 0, 1, 2, 3 and 1,048,576 (2^20). - You expect a binary-search root node, 5 arcs of 4 bytes, and a 24-byte FST: exactly what the default factor,
-1or-1e8give. - Instead the root uses direct addressing, one presence bit for every label from 0 to 1,048,576, and the FST takes 131,085 bytes, the same as with
+Infinity. All 5 keys are still found. - Why:
allowedOversize = (int) (20 * -Infinity)stops at -2,147,483,648. ThenexpansionCost = 131,079 - allowedOversizeis too big for anintand wraps to -2,147,352,569, and a cost <= 0 means "use direct addressing".
Code that builds FSTs itself with FSTCompiler.Builder and turns direct addressing off with a large negative value: Float.NEGATIVE_INFINITY, or a finite value below the node's flip point (about -1.07e8 for 5 arcs, -4,270 for 100,000 sparse arcs). The default and -1 work; no in-tree production code sets the factor. Lookups stay correct; only size grows.
Mechanism, terms and numbers502 words
FSTCompiler.Builder#directAddressingMaxOversizingFactor(float) is documented with "Setting this factor to a negative value (e.g. -1) effectively disables direct addressing, only binary search nodes will be created." (FSTCompiler.java:321-322 at 5adff78bb168), and the setter stores any float. shouldExpandNodeWithDirectAddressing compares the two node sizes in int: allowedOversize = (int) (sizeForBinarySearch * factor) and expansionCost = sizeForDirectAddressing - allowedOversize, and picks direct addressing when expansionCost <= 0 (:631-647). For a very negative factor the cast stops at Integer.MIN_VALUE, the subtraction wraps to a negative value, and the node is written with direct addressing: for the repro the "off" setting gives the same root encoding and FST size as +Infinity. With five BYTE4 keys 0, 1, 2, 3 and 2^20 and Float.NEGATIVE_INFINITY, the FST takes 131,085 bytes instead of 24; every key is still found. Present since the factor was added in 8.4.0 (LUCENE-8920); no in-tree production code sets the factor, so only code that builds FSTs itself with a large negative value is hit.
- The node. The repro's root has 5 arcs with labels 0, 1, 2, 3 and 1,048,576: fixed-length (
FSTCompiler.java:601-606), not contiguous, soaddNodeasksshouldExpandNodeWithDirectAddressingwhich layout to use (:547-555). - The two sizes (
:623-627). Binary search:sizeForBinarySearch = 20. Direct addressing:getNumPresenceBytes(1,048,577) = 131,073presence bytes (FST.java:573-576) plus 6 bytes,sizeForDirectAddressing = 131,079(printed by an instrumented copy of the method). - Allowed oversize (
:631).20 * -Infinityis-Infinity, and Java's float-to-int cast saturates, soallowedOversize = -2,147,483,648(Integer.MIN_VALUE). - The wrap (
:632).131,079 - (-2,147,483,648) = 2,147,614,727exceedsInteger.MAX_VALUE(2,147,483,647), soexpansionCostis-2,147,352,569. - The choice (
:642-647).expansionCost <= 0selects direct addressing and adds 2,147,352,569 to the compiler's expansion credit (the probe readscredit=2147352569). The FST is 131,085 bytes, the same as with+Infinity.
Where it flips. For this node every factor down to -1.07367624e8 keeps binary search and every factor from -1.0736763e8 down selects direct addressing (bisected): that is where 131,079 - allowedOversize first exceeds Integer.MAX_VALUE. In general the wrap starts below about -(Integer.MAX_VALUE - sizeForDirectAddressing) / sizeForBinarySearch, so bigger nodes flip at smaller factors. Bisected on main: about -536,838 for a 1,000-arc BYTE4 root (4,005 bytes become 132,080) and about -4,270 for a sparse 100,000-arc root (500,006 bytes become 12,599,884); an independent BYTE2 test flips between -1.43e8 and -1.44e8. -Float.MAX_VALUE and -Infinity always flip. NaN casts to 0 and keeps binary search.
For ordinary negative factors the code is right. Without the wrap, expansionCost is at least sizeForDirectAddressing, and the credit branch needs sizeForDirectAddressing <= allowedOversize * 1.66, which a non-positive bound never allows (:642-645), so binary search wins, as documented. This assumes the node's sizes are themselves positive: for a label range within 7 of Integer.MAX_VALUE, getNumPresenceBytes overflows too (FST.java:573-576), whatever the factor. That separate overflow is not part of this bug (read, not run; not claimed).
Exposure and likelihood230 words
- Who is hit. Callers of the public
FSTCompiler.Builder(its enclosing classFSTCompileris@lucene.experimental,FSTCompiler.java:68) that passFloat.NEGATIVE_INFINITY,-Float.MAX_VALUE, or a finite value below the node's flip point: about -1.07e8 for the repro's 5-arc node, about -536,838 for a 1,000-arc node, about -4,270 for a sparse 100,000-arc node (bisected on main). The default (1) and the documented-1work. The only in-tree setter calls are tests (TestUtil.java:111passes-1f;TestFSTDirectAddressing.java:180,:329pass test parameters); no codec, suggester or analyzer sets the factor. - What happens. A silent change of encoding, not a wrong result: every key is found. Each affected node costs one presence bit per label between its lowest and highest label. BYTE1 labels span at most 256 values, so there it is a small layout change; sparse BYTE2 or BYTE4 labels (code points, numeric ids) make it large: 24 bytes to 131,085 bytes for a 2^20 span (the repro), 34 bytes to 33,554,447 bytes for a 2^28 span, 19 bytes to 7,513 bytes for a sparse BYTE2 node. A 40-key probe with eight such nodes ran out of a 512 MB heap.
- Narrow reach. It needs direct
FSTCompileruse and a factor far below the documented-1(how far depends on the node); GitHub code search found no caller passingNEGATIVE_INFINITY, and the recorded searches found no report since 8.4.0 (2019).
One JUnit test method on the public FST API: five one-label BYTE4 keys, factor Float.NEGATIVE_INFINITY, then it checks that the root node is a binary-search node. Deterministic, single-threaded, about 0.05 s; it fails with assertions on and off.
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.lucene.util.fst;
import org.apache.lucene.tests.util.LuceneTestCase;
import org.apache.lucene.util.IntsRef;
public class TestNegativeOversizingFactor extends LuceneTestCase {
public void testNegativeInfinityDisablesDirectAddressing() throws Exception {
NoOutputs outputs = NoOutputs.getSingleton();
FSTCompiler<Object> compiler =
new FSTCompiler.Builder<>(FST.INPUT_TYPE.BYTE4, outputs)
.directAddressingMaxOversizingFactor(Float.NEGATIVE_INFINITY)
.build();
for (int label : new int[] {0, 1, 2, 3, 1 << 20}) {
compiler.add(new IntsRef(new int[] {label}, 0, 1), outputs.getNoOutput());
}
FST<Object> fst = FST.fromFSTReader(compiler.compile(), compiler.getFSTReader());
FST.Arc<Object> root =
fst.readFirstTargetArc(
fst.getFirstArc(new FST.Arc<>()), new FST.Arc<>(), fst.getBytesReader());
// a negative factor disables direct addressing, so the root must be a binary-search node
assertEquals(
"FST size " + compiler.fstSizeInBytes(), FST.ARCS_FOR_BINARY_SEARCH, root.nodeFlags());
}
}
cp $REPRO/TestNegativeOversizingFactor.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/fst/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.fst.TestNegativeOversizingFactor -Ptests.seed=5EED0001
# and with -Ptests.asserts=false (assertions off): the same failure
- Expected
- The root node is a binary-search node (
nodeFlags()32) and the FST takes 24 bytes, as with-1. - Observed
AssertionError: FST size 131085 expected:<32> but was:<64>: a direct-addressing root node, with assertions on and off.
More files, environment, full output227 words
TestNegativeOversizingFactor (one method, extends LuceneTestCase, package org.apache.lucene.util.fst of the lucene/core tests). It uses only public API: FSTCompiler.Builder, FST.fromFSTReader, FST.readFirstTargetArc, FST.Arc#nodeFlags and FST.ARCS_FOR_BINARY_SEARCH. The failure message carries the FST size, so a failing run shows both the wrong layout (64 = direct addressing) and the size.
It is the hunt's minimal repro, formatted with the build's Java formatter and with a shorter comment. The test uses no randomness, so the seed does not matter. As the regression test, the same method fits into TestFSTDirectAddressing as is.
| lucene | main 5adff78bb168 (12.0.0-SNAPSHOT): fails; 10.6.0, 9.12.3: fail; 8.4.0 to 10.6.0: fail with the hunt's earlier variant of the test |
|---|---|
| jdk | OpenJDK 25.0.3 |
| os | Linux aarch64 (nothing platform-specific) |
cp $REPRO/TestNegativeOversizingFactor.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/fst/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.fst.TestNegativeOversizingFactor -Ptests.seed=5EED0001
# and with -Ptests.asserts=false (assertions off)
# -Ptests.asserts=false (the same with assertions on)
TestNegativeOversizingFactor > testNegativeInfinityDisablesDirectAddressing FAILED
java.lang.AssertionError: FST size 131085 expected:<32> but was:<64>
at org.apache.lucene.util.fst.TestNegativeOversizingFactor.testNegativeInfinityDisablesDirectAddressing(TestNegativeOversizingFactor.java:38)
# factor sweep on the same five keys (evidence, not the repro; assertions off)
default (no setter) flags=32 bytes=24 found=5/5 credit=0
factor=-1.0 flags=32 bytes=24 found=5/5 credit=0
factor=-1.0E8 flags=32 bytes=24 found=5/5 credit=0
factor=-1.0E9 flags=64 bytes=131085 found=5/5 credit=2147352569
factor=-3.4028235E38 flags=64 bytes=131085 found=5/5 credit=2147352569
factor=-Infinity flags=64 bytes=131085 found=5/5 credit=2147352569
factor=Infinity flags=64 bytes=131085 found=5/5 credit=2147352568
factor=NaN flags=32 bytes=24 found=5/5 credit=0
flip: factor -1.07367624E8 -> binary search, -1.0736763E8 -> direct addressing- The javadoc: "a negative value (e.g. -1) effectively disables direct addressing, only binary search nodes will be created"; the setter accepts any float.
- For every negative value that does not overflow, the code does exactly that; after the overflow, "off" behaves like
+Infinity. - The sentence and the
intarithmetic came in together (LUCENE-8920); neither its issue nor its PR discusses huge or non-finite factors.
The full argument164 words
- Contract. "Setting this factor to a negative value (e.g. -1) effectively disables direct addressing, only binary search nodes will be created." (
FSTCompiler.java:321-322).Float.NEGATIVE_INFINITYand-Float.MAX_VALUEare negative values,-1is introduced with "e.g.", and the setter stores any float with no check (:330-333). The sibling settersuffixRAMLimitMBrejectsmb < 0(:282-283) and documentsDouble.POSITIVE_INFINITYas a sentinel (:267), so an infinite value is a natural "for sure" choice in this Builder, whose javadoc asks callers to "Read parameter documentation carefully." (:239-240). - Code and javadoc agree until the overflow. For the repro's node the probe keeps binary search down to -1e8; after the wrap the root encoding and FST size equal those of
+Infinity, the opposite of the setting. - History. LUCENE-8920 (
068b6babac3, apache/lucene-solr#980 by bruno-roustant, 2019; issue #9963) added the setter, the sentence and the arithmetic at once. Nobody in the issue or the PR discusses very large or non-finite factors.
The devil's-advocate check215 words
The argument. The documented value is -1, the one in-tree caller that disables direct addressing passes -1f (TestUtil.java:111), and a comment on #10326 (LUCENE-9286) advises "set ... directAddressingMaxOversizingFactor(-1) - that should disable the direct addressing". "Effectively" may mean the disabling is a side effect meant for ordinary values, the API is @lucene.experimental, and "only binary search nodes" is already loose: contiguous nodes get the continuous encoding even with -1 (FSTCompiler.java:542-546).
Why it is weak as a reading of the javadoc. The sentence covers "a negative value" and gives -1 only as an example. Finite values fail too: -Float.MAX_VALUE, for this node any value below about -1.074e8, and for a sparse 100,000-arc node any value below about -4,270, so it is not about infinity. The result is not slightly off but the opposite of the setting. @lucene.experimental concerns API stability, not silently inverting a setting. Continuous nodes carry no presence bits, which is why the test uses a non-contiguous node.
What survives. The trigger is narrow, lookups stay correct and the recorded searches found no report since 2019, so a maintainer may reasonably answer "use -1" and treat a fix as hardening, or prefer to document what is supported (option C). The guard costs one comparison per fixed-length node.
Recommended A. Return binary search for a negative factor before the arithmetic (recommended)
In shouldExpandNodeWithDirectAddressing, return false (binary search) when the factor is negative, before the int arithmetic. That matches the javadoc for every negative value and changes nothing for negative factors that do not overflow today. The repro passes with assertions on and off, and the 38 FST tests pass.
int maxBytesPerArcWithoutLabel,
int labelRange) {
+ // A negative factor disables direct addressing (see the Builder javadoc). Return before the
+ // int arithmetic below, which overflows for very negative factors.
+ if (getDirectAddressingMaxOversizingFactor() < 0) {
+ return false;
+ }
// Anticipate precisely the size of the encodings.
int sizeForBinarySearch = numBytesPerArc * nodeIn.numArcs;All options and trade-offs3 options ยท 431 words
Option A is a five-line guard that keeps today's behaviour everywhere except the overflow. B and C are alternatives for maintainers who prefer to handle the value in the setter or the javadoc.
A. Return binary search for a negative factor before the arithmetic (recommended) (validated by the checks)
Check getDirectAddressingMaxOversizingFactor() < 0 at the top of shouldExpandNodeWithDirectAddressing and return false.
int maxBytesPerArcWithoutLabel,
int labelRange) {
+ // A negative factor disables direct addressing (see the Builder javadoc). Return before the
+ // int arithmetic below, which overflows for very negative factors.
+ if (getDirectAddressingMaxOversizingFactor() < 0) {
+ return false;
+ }
// Anticipate precisely the size of the encodings.
int sizeForBinarySearch = numBytesPerArc * nodeIn.numArcs;Trade-offs
One comparison per fixed-length node. On a node whose sizes are positive, every negative factor that does not wrap already gets binary search, so nothing else changes; the default, positive factors and NaN are untouched. On a node whose own size arithmetic overflows (label range within 7 of Integer.MAX_VALUE) it also sends negative factors to binary search, a case that is broken anyway (read, not run). It also covers a second route found by reading and not run (not claimed): with -1 the subtraction is sizeForDirectAddressing + sizeForBinarySearch, which wraps once the sum exceeds Integer.MAX_VALUE, for example on a fixed-length node of about 1.5 GB.
What the checks validated
- Gradle in scratch worktrees at
5adff78bb168, seed5EED0001: the repro fails without the guard (assertions on, and-Ptests.asserts=false) and passes with it (both). - With the guard:
:lucene:core:test --tests 'org.apache.lucene.util.fst.*'passes (9 classes, 38 tests, 5 skipped, 0 failures; includesTestFSTDirectAddressing,TestFSTs,TestUtil), and:lucene:core:checkGoogleJavaFormatpasses. - Independently, the same guard a few lines lower passes the hunt's tests, the cross-model reviewers' tests and upstream
TestFSTDirectAddressing(2 of 2).
Store -1 for any negative factor in Builder#directAddressingMaxOversizingFactor.
Trade-offs
Same effect for this bug, but getDirectAddressingMaxOversizingFactor() then returns -1 instead of the value passed, and the 1.5 GB route above stays.
What the checks validated
Not run.
Say "use -1" and that very negative or non-finite values are unsupported, or reject them in the setter.
Trade-offs
No fixed numeric bound is safe for every node: the flip point depends on the node's size (about -4,270 already for a sparse 100,000-arc node). Documentation alone keeps the silent inversion; rejecting only non-finite values misses finite ones such as -1e9, or -5000 on such a node.
What the checks validated
Not run (documentation only).
Downstream code that builds its own FSTs and passes a large negative factor to switch direct addressing off can get FSTs orders of magnitude larger than expected; no in-tree production code sets the factor.
A proof-obligation audit of the directAddressingMaxOversizingFactor contract: since the javadoc promises binary search for every negative value, shouldExpandNodeWithDirectAddressing must return false for all of them. The obligation holds while the int arithmetic does not overflow and fails once it does; a one-method JUnit test on the public API then witnessed it.
The method in full96 words
The audit took the Builder javadoc's promise as the obligation for shouldExpandNodeWithDirectAddressing over all float values of the factor and checked each step of the size comparison: the float product, the saturating cast and the int subtraction. The obligation fails exactly where the subtraction can wrap, which needs a very negative factor.
An executable one-test repro witnessed it on main with assertions on and off. An independent reproducer, two executed cross-model reviews (OpenAI GPT-5.6, refute and intended lenses), a devil's-advocate verifier and an adjudication then confirmed it, and a version sweep placed its start in 8.4.0.
No prior report found in apache/lucene issues, PRs and commits (incl. the JIRA archive), the mailing lists, downstream trackers or the web (searched 2026-11-03; GitHub re-checked the same day). Nearest: #9963 (LUCENE-8920), which introduced the factor, and #10326, a different memory problem.
Searches3 searches
Nearest items, none of them this bug: #9963 (LUCENE-8920) and apache/lucene-solr#980, which added the factor, the javadoc sentence and the arithmetic without discussing very large or non-finite factors; #10326 (LUCENE-9286), BitTables cloned by Arc.copyOf, which uses -1 and factors 0 to 1. Upstream main's newest commit to FSTCompiler.java is still 8cd74fed97b (#15133, unrelated); no open PR touches the file.
| Where | When | How | Found |
|---|---|---|---|
| GitHub issues, PRs and commits (apache/lucene incl. the migrated JIRA archive) | 2026-11-03; re-checked twice the same day | two scripted prior-report searches (51 queries each) plus about 25 manual searches, among them directAddressingMaxOversizingFactor, 'oversizing factor', 'direct addressing' negative / overflow / OutOfMemoryError, FSTCompiler NEGATIVE_INFINITY, allowedOversize, expansionCost; git log -S over the full history | no report; #9963 and #10326 are the nearest |
| Open PRs | 2026-11-03 | the changed files of all 409 open apache/lucene PRs | none touches FSTCompiler.java |
| Mailing lists, downstream trackers, code search, web | 2026-11-03 | dev@, java-user@, issues@ and commits@ through the scripted searches; Elasticsearch, OpenSearch and Solr searches; GitHub code search; 12 web queries | nothing about a very negative factor; no caller passes NEGATIVE_INFINITY |
Introduced with the factor itself by LUCENE-8920 (068b6babac3, 2019) and first released in 8.4.0. All 55 releases from 8.4.0 to 10.6.0 fail, and main. Not a regression and not fixed upstream.
Versions tested5 rows
068b6babac3 "LUCENE-8920: Reduce the memory used by direct addressing of arcs" (apache/lucene-solr#980 by bruno-roustant, 2019-11-13; issue #9963), on branch_8x 5dd9c4c04bc, added Builder#setDirectAddressingMaxOversizingFactor(float) with no range check, the javadoc sentence and the int arithmetic. Later commits changed only the form: 1812b367aba (LUCENE-9089, FSTCompiler.Builder), 2d6ad2fee6d (LUCENE-9570, reformat) and 04f38dd2885 (#12646, method moved from FST to FSTCompiler).
The release runs used the hunt's earlier one-test variant (label 2^28; API variants for 8.x and 9.0-9.9 keep the same steps and check). This doc's repro also fails on the 10.6.0 and 9.12.3 jars.
| Version or commit | Verdict | Result |
|---|---|---|
main 5adff78bb168 | affected | gradle: fails with assertions on and off; passes with the guard |
| 10.6.0, 9.12.3 | affected | this repro fails: FST size 131085 expected:<32> but was:<64> |
| 8.4.0 to 10.6.0 (55 releases) | affected | the earlier variant fails on every release: root flags 64, about 33.5 MB |
| 8.4.0 with factor -1 | control | binary search, as documented |
| 8.2.0, 8.3.1 | API absent | no oversizing factor yet |
A finder, an independent reproducer, two executed cross-model reviews (OpenAI GPT-5.6, real, high), a devil's-advocate verifier and an adjudication all rated it real; an audit kept it and a final repro check reproduced it. This doc's gradle runs reproduced it on main and validated the guard.
Checks and verdicts232 words
The cross-model reviews ran on main ea57360912ed, whose FSTCompiler.java is byte-identical to 5adff78bb168.
| Check | Verdict | What it found |
|---|---|---|
| finder | reproduced | The test fails on main (assertions on and off), 10.6.0 and 9.12.3; the guard passes. |
| independent reproducer | real | Own BYTE2 test (labels 1, 2, 3, 4, 60000) fails on main, 10.6.0, 10.5.2 and 9.12.3: 7,513 bytes instead of 19; flip between -1.43e8 and -1.44e8. |
| cross-model reviews, refute and intended lenses (OpenAI GPT-5.6, executed) | real (high) | Own tests fail for -Infinity and -Float.MAX_VALUE with a passing -1 control; the bytecode shows no negative-factor guard; with the guard their tests and TestFSTDirectAddressing pass; the "e.g. -1" reading rated weak. |
| devil's-advocate verifier | real, Low | Extreme negative factors give exactly the +Infinity encoding and size; contiguous nodes get the continuous encoding even with -1, so the test uses a non-contiguous node. |
| adjudication, separate re-runs, audit and final repro check | confirmed, Low | Re-runs fail on main (assertions on and off) and 10.6.0 and pass with the guard; one minimal deterministic test. |
| this doc | reproduced; guard validated | Gradle on scratch worktrees: the repro fails without the guard and passes with it; 38 FST tests pass; a factor sweep finds the flip at about -1.0737e8 for this node, and a scaling probe at about -536,838 for 1,000 arcs and -4,270 for 100,000 sparse arcs. |
The diagram as a still image, generated with AI and checked against the code. It is under 10 MB, the limit for a GitHub attachment.
- PNG 477 KB
Finding record, Lucene and upstream sources, repro files and diagram notes1,501 words
- Registry title
- FSTCompiler.Builder#directAddressingMaxOversizingFactor is documented so that any negative factor disables direct addressing, but a very negative one (Float.NEGATIVE_INFINITY, -Float.MAX_VALUE, or about -1e8 and below) saturates the int cost arithmetic in shouldExpandNodeWithDirectAddressing and turns direct addressing on, so five sparse BYTE4 keys give a 33.5 MB FST instead of 34 bytes (since 8.4.0)
- Area
- util / FST (FSTCompiler fixed-length node encoding: binary search vs direct addressing)
- Priority
- Low, rank 932: An extreme negative directAddressingMaxOversizingFactor on the experimental FSTCompiler.Builder turns direct addressing on instead of off, so sparse FSTs grow by orders of magnitude and can run out of heap, in every release since 8.4.0. Lookups stay correct, no Lucene component sets the factor and the documented -1 works, so only applications that choose a value such as Float.NEGATIVE_INFINITY hit it.
- Impact class
- minor
- Impact note
- Hits only applications that build FSTs themselves with the public, @lucene.experimental FSTCompiler.Builder and set directAddressingMaxOversizingFactor to an extreme negative value (no Lucene codec, suggester or analyzer sets the factor; the default, the documented -1 and every ordinary negative value work): their non-continuous fixed-length nodes are then written with direct addressing instead of binary search, lookups stay correct, and the FST grows with label sparsity (34 bytes to 33,554,447 bytes for one sparse BYTE4 node; 19 bytes to 7.5 KB for a sparse BYTE2 node; a 40-key BYTE4 probe ends in OutOfMemoryError under a 512 MB heap), in every release from 8.4.0 to 10.6.0 [exec].
- Summary
- You build an FST with FSTCompiler.Builder and set directAddressingMaxOversizingFactor(Float.NEGATIVE_INFINITY), because its javadoc says a negative value disables direct addressing and only binary-search nodes will be created. You expect the root node of five BYTE4 keys with labels 0, 1, 2, 3 and 2^28 to be a binary-search node and the FST to take 34 bytes, as it does with -1 or the default. Instead (int) (sizeForBinarySearch * factor) saturates to Integer.MIN_VALUE, the int subtraction for expansionCost wraps to a negative value, the node is written with direct addressing and the FST takes 33,554,447 bytes, almost all of them presence bits for the 2^28 label range; every key is still found.
- Introduced
- 068b6babac38 on main: LUCENE-8920 'Reduce the memory used by direct addressing of arcs' (apache/lucene-solr#980 by bruno-roustant, merged 2019-11-13; issue #9963), which added Builder#setDirectAddressingMaxOversizingFactor(float) with no range check, its javadoc sentence 'Setting this factor to a negative value (e.g. -1) effectively disables direct addressing, only binary search nodes will be created.' and the int arithmetic 'int allowedOversize = (int) (sizeForBinarySearch * factor); int expansionCost = sizeForDirectAddressing - allowedOversize; if (expansionCost <= 0 || ...) return true;' in FST.shouldExpandNodeWithDirectAddressing; branch_8x 5dd9c4c04bca (same change, 2019-11-14) -> 8.4.0. Later commits changed only the form: 1812b367aba (LUCENE-9089, Builder renamed FSTCompiler.Builder), 2d6ad2fee6d (LUCENE-9570, reformatting) and 04f38dd2885 (#12646, method moved from FST to FSTCompiler) [read: git log -S 'allowedOversize' / 'effectively disables direct addressing', git blame at 7cecf795236 (FSTCompiler.java byte-identical to 5adff78bb168)] [exec: 8.4.0 fails, 8.3.1 has no oversizing factor]. (2019-11-13 (author date of 068b6babac3; the branch_8x commit 5dd9c4c04bc was committed 2019-11-14))
- First affected version
- 8.4.0 [exec: the one-test repro, 8.x API variant, fails; the same variant with the documented factor -1 passes on 8.4.0]; 8.2.0 and 8.3.1 have no oversizing factor [exec: compile error, API absent]; 9.0.0 on the 9.x line [exec]
- Affected versions
- Every release from 8.4.0 to 10.6.0 (55 releases, released 10.6.0 = 4ae946e5a9b included) and main 5adff78bb168 (12.0.0-SNAPSHOT) [exec: all fail with root nodeFlags 64 instead of 32; 8.x and 9.0.0-9.9.2 through API variants of the same test that keep its steps and check, 9.10.0 and later with the test unchanged; main with -ea and -da]. Not affected: 8.2.0 and 8.3.1 (API absent) [exec]. Not fixed upstream: upstream main 1c2072f02843 (2026-11-02) has the same code; the newest commit to FSTCompiler.java is 8cd74fed97b (#15133, author date 2026-09-29, unrelated) [read, 2026-11-03]. Not new in 10.6. All runs with JDK 25.0.3 on Linux aarch64.
- Status
- documented (brief, checks and a per-finding doc exist)
- Verification
- Confirmed by AI-run checks: an independent repro, a cross-model review that agreed, an intended-behaviour check, a prior-report search and a skeptical audit; not yet triaged by a person.
- Found by
- semi-formal: proof-obligation audit
- Upstream and prior reports
- none found (2026-11-03, on top of the finder's run and the intended-behaviour check's and the adjudication's searches; rechecked the same day): two scripted prior-report searches (51 queries each over GitHub issues and PRs, commits, downstream repositories, the dev@, java-user@, issues@ and commits@ lists and the JIRA archive; 27 and 193 hits, none about this defect), about 25 manual GitHub searches on apache/lucene plus Elasticsearch, OpenSearch and Solr, GitHub code search (no caller passes NEGATIVE_INFINITY), the changed files of all 409 open apache/lucene PRs (none touches FSTCompiler.java), git log -S over the full history and general web search: no issue, PR, review comment, commit, list thread or downstream report describes a very negative factor turning direct addressing on, the saturating (int) cast of sizeForBinarySearch * factor or the wrapped expansionCost. Nearest items, not this bug: #9963 (LUCENE-8920) and apache/lucene-solr#980, which introduced the factor, the javadoc sentence and the int arithmetic in 2019 without discussing non-finite or very large negative factors; #10326 (LUCENE-9286, BitTables cloned by Arc.copyOf, a different root cause, which uses the documented -1 and factors 0..1). Same-day recheck: GitHub search for directAddressingMaxOversizingFactor, '"oversizing factor"', shouldExpandNodeWithDirectAddressing and '"direct addressing" negative' finds only #10326, #9963 and #12624 (FST writer refactoring, term overlap only); no apache/lucene issue or PR on FSTCompiler created since 2026-11-01 or on FST updated since 2026-11-02; none of the 28 open PRs updated since 2026-11-01 touches FSTCompiler.java; upstream main 1c2072f02843 still has the code.
- Lucene commit tested
- main
5adff78bb168(12.0.0-SNAPSHOT): gradle in two scratch worktrees for this doc (the repro fails with assertions on and off and passes with the guard; the 38org.apache.lucene.util.fsttests pass with it; the formatter check passes) and standalone JUnit runs; release jars 10.6.0 and 9.12.3 with this repro; the hunt's earlier variant of the test (label 2^28) on all 55 releases from 8.4.0 to 10.6.0. The cross-model reviews ran on mainea57360912ed, whoseFSTCompiler.javais byte-identical.
- Finding record
lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:318-333 (at 5adff78bb168) (Builder#directAddressingMaxOversizingFactor javadoc; :321-322 'Setting this factor to a negative value (e.g. -1) effectively disables direct addressing, only binary search nodes will be created.'; setter :330-333 stores any float, no validation)lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:265-287 (at 5adff78bb168) (suffixRAMLimitMB, for contrast: documents Double.POSITIVE_INFINITY as a sentinel at :267 and rejects mb < 0 at :282-283)lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:537-556 (at 5adff78bb168) (addNode: a continuous fixed-length node takes the continuous encoding; otherwise :547 shouldExpandNodeWithDirectAddressing chooses direct addressing over binary search)lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:617-650 (at 5adff78bb168) (shouldExpandNodeWithDirectAddressing: :631 int allowedOversize = (int) (sizeForBinarySearch * getDirectAddressingMaxOversizingFactor()); :632 int expansionCost = sizeForDirectAddressing - allowedOversize; :642 expansionCost <= 0 selects direct addressing)lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:68 (at 5adff78bb168) (@lucene.experimental on FSTCompiler)lucene/core/src/test/org/apache/lucene/util/fst/TestUtil.java:111 (at 5adff78bb168) and TestFSTDirectAddressing.java:180, :329 (the only in-tree setter calls: -1f, ordinary factors, a main() argument)
- The finding in 30 seconds
lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:318-333 (at 5adff78bb168) (Builder#directAddressingMaxOversizingFactor javadoc; :321-322 'Setting this factor to a negative value (e.g. -1) effectively disables direct addressing, only binary search nodes will be created.'; setter :330-333 stores any float, no check)lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:537-556 (at 5adff78bb168) (addNode: contiguous labels take the continuous encoding at :542-546; otherwise :547-555 shouldExpandNodeWithDirectAddressing picks direct addressing or binary search); :77-87 and :601-606 (fixed-length arcs: depth <= 3 and >= 5 arcs, or >= 10 arcs)lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:617-650 (at 5adff78bb168) (shouldExpandNodeWithDirectAddressing: sizes :623-627; :631 int allowedOversize = (int) (sizeForBinarySearch * getDirectAddressingMaxOversizingFactor()); :632 int expansionCost = sizeForDirectAddressing - allowedOversize; :642-647 expansionCost <= 0 selects direct addressing and adds -expansionCost to the credit)lucene/core/src/java/org/apache/lucene/util/fst/FST.java:573-576 (at 5adff78bb168) (getNumPresenceBytes = (labelRange + 7) >> 3); :88, :95, :101 (ARCS_FOR_BINARY_SEARCH = 32, ARCS_FOR_DIRECT_ADDRESSING = 64)
- Who is affected
lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:68 (at 5adff78bb168) (@lucene.experimental)lucene/core/src/test/org/apache/lucene/util/fst/TestUtil.java:111 (at 5adff78bb168) (-1f), TestFSTDirectAddressing.java:180, :329 (test parameters): the only in-tree setter calls
- Why it looks unintended
lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:318-333 (at 5adff78bb168) (Builder#directAddressingMaxOversizingFactor javadoc; :321-322 'Setting this factor to a negative value (e.g. -1) effectively disables direct addressing, only binary search nodes will be created.'; setter :330-333 stores any float, no check)lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:265-287 (at 5adff78bb168) (suffixRAMLimitMB: :267 documents Double.POSITIVE_INFINITY as a sentinel, :282-283 rejects mb < 0); :236-241 (Builder javadoc 'Read parameter documentation carefully.')lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:537-556 (at 5adff78bb168) (addNode: contiguous labels take the continuous encoding at :542-546; otherwise :547-555 shouldExpandNodeWithDirectAddressing picks direct addressing or binary search); :77-87 and :601-606 (fixed-length arcs: depth <= 3 and >= 5 arcs, or >= 10 arcs)
- Diagrams
lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:617-650 (at 5adff78bb168) (shouldExpandNodeWithDirectAddressing: sizes :623-627; :631 int allowedOversize = (int) (sizeForBinarySearch * getDirectAddressingMaxOversizingFactor()); :632 int expansionCost = sizeForDirectAddressing - allowedOversize; :642-647 expansionCost <= 0 selects direct addressing and adds -expansionCost to the credit)
- TestNegativeOversizingFactor.java (lucene/core, package org.apache.lucene.util.fst, 1 test):
repro/LFV-1204/TestNegativeOversizingFactor.java(41 lines)
The numbers are those a probe on main prints with assertions off, and the locals an instrumented copy of the method prints (FSTCompiler.java:623-647).
assets/LFV-1204/bug.png(477 KB)