FSTCompletionLookup sorts weights as unsigned bytes, so negative weights get the highest buckets and are suggested before positive ones

FSTCompletionLookup turns weights into a few buckets (10 by default) and suggests higher buckets first. To find the buckets, build() sorts the entries by weight and cuts the sorted list into equal ranges, as its javadoc says. But it sorts each weight's four big-endian two's-complement bytes as unsigned bytes, where every negative int (first byte 0x80 or more) comes after every non-negative int. So the negative weights take the highest buckets: built from {apple: 10, apricot: -10}, lookup("ap", true, 2) returns [apricot/5, apple/0], with no error. encodeWeight accepts every int and InputIterator#weight() says "higher numbers mean better suggestions". Within each sign the order is right and the full set of matches is unchanged; only the sign boundary is inverted, which changes the top-k. The sign handling was dropped in 2012 (LUCENE-3807), before the class was first released, so every release from 3.6.0 to 10.6.0 (10.6.0 by reading) and main is affected. Flipping the sign bit of the sort key fixes it, with no format change.

• Weight: the number an InputIterator (or a Dictionary such as FileDictionary or DocumentDictionary) attaches to each suggestion; "higher numbers mean better suggestions" (InputIterator.java:35). A signed long; FSTCompletionLookup accepts any value in the int range (encodeWeight, FSTCompletionLookup.java:254-259).
• Bucket: FSTCompletionLookup keeps no exact weights. It sorts the entries by weight, cuts the sorted list into buckets equal ranges (10 by default) and stores each suggestion under its range number. lookup(key, true, num) returns the highest bucket first, and LookupResult.value is the bucket number, not the weight (:278).
• Unsigned byte order: the offline sorter compares byte strings as unsigned bytes (0x00 < ... < 0xFF). A negative int in two's complement starts with a byte of 0x80 or more, a non-negative one with 0x7F or less.

1. For each entry build() writes one line: the weight as 4 big-endian two's-complement bytes (output.writeInt(Integer.reverseBytes(encodedWeight)), FSTCompletionLookup.java:187-189, through the little-endian ByteArrayDataOutput.writeInt), then the suggestion bytes. 10 becomes 00 00 00 0A, -10 becomes FF FF FF F6.
2. OfflineSorter sorts the lines with its default comparator, BytesRef#compareTo, which is Arrays.compareUnsigned (:199; OfflineSorter.java:195, :202-206; BytesRef.java:161-162). The order is 0, 1, ..., Integer.MAX_VALUE, Integer.MIN_VALUE, ..., -1.
3. Buckets follow that order: bucket = line * buckets / inputLineCount (:226), equal weights share a bucket (:223-224). With 2 entries, line 0 (apple, 10) gets bucket 0 and line 1 (apricot, -10) bucket 5.
4. Higher buckets are "presented before suggestions placed in smaller buckets" (FSTCompletionBuilder.java:169-171; FSTCompletion.java:147), so lookup("ap", true, 2) returns [apricot/5, apple/0].

Within the negative weights, and within the non-negative weights, unsigned order equals numeric order, so those comparisons are right: {apple: 10, apricot: 5} and {apple: -1, apricot: -10} both give [apple/5, apricot/0]. A stale comment sits right above the loop (:174-175): "For now, assume they are non-negative. If negative floats are allowed some trickery needs to be done to find their byte order."

• Who is exposed. Users of FSTCompletionLookup (opt-in, @lucene.experimental, FSTCompletionLookup.java:71) whose weights mix negative and non-negative values. Every public weight source can deliver them: a custom InputIterator, FileDictionary (weights parsed as a signed long, FileDictionary.java:207-213), DocumentDictionary over a signed numeric field (executed) or DocumentValueSourceDictionary. The default constructor and the default 10 buckets suffice.
• What goes wrong. Negative-weight suggestions come before non-negative ones (with more entries than buckets, the entries at the sign boundary may instead share a bucket), so the top-k changes; an entry an application demotes with -1 is suggested first. The full set of matching suggestions is unchanged (0 mismatches in 168 full-set lookups over a 3,000-entry mixed-sign dictionary; the top 5 differed from an order-preserving control for 84 of 84 prefixes). One probe on 100,000 entries saw the same result counts and FST ramBytesUsed() as that control, with comparable single-run timings (not a benchmark). Nothing throws (executed on main with -ea and -da, and on 10.5.2).
• When it shows. In lookup(key, true, num) (higher weights first). With higherWeightsFirst = false the results are sorted by text when there is more than one bucket (FSTCompletion.java:202-206), though LookupResult.value and get() still report the inverted buckets (:278, :287-288). With the default exactMatchFirst, an exact match of the key is returned first whatever its bucket (FSTCompletion.java:235-280); no example here has one (by reading).
• It persists. The buckets are baked into the FST that store() writes (:293-300), so a stored lookup keeps the inverted order after load() until it is rebuilt on a fixed version (executed).
• Scale. Every mixed-sign build sorts the negative weights above the non-negative ones; it shows as an inversion whenever the bucket ranges separate them, which is always the case with at most buckets entries (the two-entry repro fails every time). With more entries a bucket is a range of lines: 19 entries with weights 0 to 18 plus one of weight -1 put the -1 entry in bucket 9 with weight 18 (above weights 0 to 17); 100 entries, one of weight 5 and 99 of weight -1, all land in bucket 0, so no inversion shows (executed on main). A 600-trial random property check (1 to 60 random weights per build) found at least one bucket inversion in 206 of 206 mixed-sign builds and in 0 of 394 single-sign builds; with the fix in 0.
• Likelihood. Rare by accident: common weight sources (term or document frequencies, popularity counts) are never negative, and WFSTCompletionLookup, AnalyzingSuggester and SuggestField reject negative weights. No user report was found since 3.6.0 (2012), though a silent mis-ranking may go unnoticed.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => org.junit.ComparisonFailure: results [apricot/5, apple/0] expected:<ap[ple]> but was:<ap[ricot]>
       org.junit.Assert.assertEquals(Assert.java:117)
       org.apache.lucene.search.suggest.fst.TestFSTCompletionLookupNegativeWeights.testNegativeWeightRankedBelowPositive(TestFSTCompletionLookupNegativeWeights.java:35)

• The contract. Class javadoc (FSTCompletionLookup.java:59-61): "The range of weights for bucketing/ discretization is determined by sorting the input by weight and then dividing into equal ranges." :63-65: the "overall distinction between \"classes\" of weights will be preserved regardless of the distribution of weights." InputIterator.java:35: "A term's weight, higher numbers mean better suggestions." No sign restriction anywhere in the javadoc, CHANGES or MIGRATE.
• The input is accepted. encodeWeight throws only outside Integer.MIN_VALUE..MAX_VALUE (:254-259). The LUCENE-3807 diff that introduced it wrote that explicit Integer.MIN_VALUE bound, while WFSTCompletionLookup.encodeWeight, changed in the same diff, kept its existing value < 0 || value > Integer.MAX_VALUE check (today WFSTCompletionLookup.java:262-267). No source records why the two bounds differ.
• Upstream tests. TestFSTCompletion#testLargeInputConstantWeights builds an FSTCompletionLookup from 5,000 entries of weight -1 (TestFSTCompletion.java:185, :192); TestPersistence asserts bucket values grow with the weight (TestPersistence.java:91-102), for weights 0..n. No test mixes signs.
• History. SOLR-2888 (92de7e88486, 2011) added the class with FloatMagic.toSortable, "a directly sortable unsigned integer" that sorted negatives below non-negatives. LUCENE-3807 (f303bcd4650, 2012; backport 71bd966a92e) switched weights to long, used (int) value and deleted FloatMagic. Its CHANGES entry says that weights became 64-bit signed integers (it also covers the disk-based sort and the move to CharSequence) and nothing about negative-weight order; its 38 comments never mention negative weights. The parents pass the FileDictionary probe, the two commits fail it, and each passes with the one-line sign-bit patch.
• Siblings that were checked. WFSTCompletionLookup, AnalyzingSuggester and SuggestField reject negative weights loudly; TSTLookup and AnalyzingInfixSuggester accept them and order them by numeric value (tst/TSTLookup.java:195-196, analyzing/AnalyzingInfixSuggester.java:166). Other suggesters were not checked for this.

The strongest works-as-designed case (intended-behaviour checker, adjudication, cross-model intended lens): the comment "For now, assume they are non-negative" (:174-175), sibling suggesters that reject negative weights, @lucene.experimental, and lossy bucketing.

It fails: the comment is internal, never enforced, and was stale from the day it was written (it came with SOLR-2888 in the same commit as FloatMagic, which did order negatives correctly, and it still talks about floats); encodeWeight explicitly admits negative ints (its lower bound is Integer.MIN_VALUE) while WFSTCompletionLookup rejects them; the module has no single convention; @lucene.experimental is about API stability, not wrong results; and the lossy-bucketing caveat is about merging nearby weights, while the same paragraph promises the classes are preserved. A reviewer may add that the class javadoc sends users who need "fine-grained control over which weights are assigned to which buckets" to FSTCompletion or TSTLookup (:67-68), which is about precision within the lossy scheme, not order, and that FSTCompletionBuilder.add requires a non-negative bucket (FSTCompletionBuilder.java:169-176), which constrains the bucket number build() computes from the line number, not the weight. Silently inverting accepted input is not a design; rejecting it would be, and a committer may reasonably prefer that to supporting negative weights. The cross-model refute lens said "not real" at low confidence only because it could not run the test; it agreed with the root cause and that the inputs are in contract.

One fix was applied in a scratch worktree at a9779ef3c193 and run through gradle (seed DEADBEEF); the alternatives were not run.

In FSTCompletionLookup.build, write Integer.reverseBytes(encodedWeight ^ Integer.MIN_VALUE) instead of Integer.reverseBytes(encodedWeight), and replace the stale "assume they are non-negative" comment. XOR with 0x80000000 maps Integer.MIN_VALUE..MAX_VALUE monotonically onto 0x00000000..0xFFFFFFFF: -10 becomes 7F FF FF F6, 10 becomes 80 00 00 0A. The value read back (:220) is only compared for equality (:223), and XOR is a bijection, so ties still share a bucket. FloatMagic applied the same sign-bit XOR to non-negative floats before 2012. Integer.MIN_VALUE is 0x80000000: the diagram writes the same constant in hex.

-    // Push floats up front before sequences to sort them. For now, assume they are non-negative.
-    // If negative floats are allowed some trickery needs to be done to find their byte order.
+    // Write each weight before its sequence, so that sorting the lines sorts them by weight.
 ...
         final int encodedWeight = encodeWeight(iterator.weight());
-        // write bytes for comparing in lexicographically order
-        output.writeInt(Integer.reverseBytes(encodedWeight));
+        // write big-endian bytes for comparing in lexicographic (unsigned) order; flipping the sign
+        // bit makes that order equal to the numeric order of the weights, negative ones included
+        output.writeInt(Integer.reverseBytes(encodedWeight ^ Integer.MIN_VALUE));

Trade-offs

• No index or file-format change: store() writes the entry count and the FST (:293-300); the key exists only in the temporary sort file.
• Lookups stored by affected versions keep their inverted buckets until they are rebuilt.
• Builds whose weights all have the same sign get the same buckets as today (unsigned order within one sign is unchanged; by reading).
• No cost: one XOR per entry at build time.

What the checks validated

• Stock main a9779ef3c193 (gradle, seed DEADBEEF): the repro fails 1 of 2 with assertions on and off ("got [apricot/5, apple/0]"); TestFSTCompletion and TestPersistence pass (16 tests, 1 @Nightly skipped).
• With the fix: the repro passes 2 of 2 with assertions on and with assertions off; TestFSTCompletion plus TestPersistence pass (16 tests, 0 failures); all of :lucene:suggest:test passes with the repro class added (32 classes, 238 tests, 0 failures, 7 skipped).
• ecjLintMain, ecjLintTest and checkGoogleJavaFormat pass for suggest; fix.diff and fix-with-test.diff apply cleanly to a clean tree.
• Through the classpath runner, the fix shadowed onto the main jars: 2 of 2 pass.
• Earlier, in the hunt (the same sign flip, shadowed onto the stock jars): the finder's JUnit, the reproducer's 6 tests, the 600-trial property check (0 violations), the security probe and TestFSTCompletion plus TestPersistence (15 of 15) pass; the same patch makes both introducing commits pass.
• Not run: other modules (outside lucene/suggest only CHANGES.txt names the class); no benchmark (one XOR per entry at build time).

Change encodeWeight's bound to value < 0 || value > Integer.MAX_VALUE, as in WFSTCompletionLookup and AnalyzingSuggester.

Trade-offs

• Loud instead of silent, and consistent with three sibling suggesters.
• A behaviour change for callers whose negative weights work today (all-negative or constant weights order correctly); one bad entry fails the whole build; needs a CHANGES/MIGRATE note.
• Breaks upstream TestFSTCompletion#testLargeInputConstantWeights, which builds from weight -1 (by reading).

A javadoc note only.

Trade-offs

Leaves the silent inversion in place for everyone who does not read it.

Method: end-to-end translation validation on the stock jar (semi-formal tier), in a hunt unit on how the suggesters preserve the InputIterator (term, weight) tuples.

• The harness built six suggesters (AnalyzingSuggester, FuzzySuggester, AnalyzingInfixSuggester, FSTCompletionLookup, WFSTCompletionLookup, TSTLookup) from 3,000 seeded random sources of 1-6 entries over 3 keys, passed through 5 InputIterator wrappers (90,000 builds and 292,350 lookups in all), and compared each result with a reference written from the javadoc (for FSTCompletionLookup: a key with a higher weight never gets a lower bucket). The FSTCompletionLookup sources drew weights from {Integer.MIN_VALUE, -5, -1, 0, 1, 5, Integer.MAX_VALUE}; the other suggesters used non-negative weight sets.
• For FSTCompletionLookup it reported 1,768 bucket-order inversions per wrapper, every one in a source that contains a negative weight, and 0 with the sign-bit fix shadowed onto the jar.
• The root cause was then located by reading build() and its history, and reduced to a two-test public-API JUnit. Found 2026-10-26 on main ea57360912ed; then checked by an independent reproducer, an intended-behaviour devil's advocate, reading-only reviews by a model from another family (OpenAI GPT-5.6), an adjudication, a history, prior-report and security follow-up, and a credibility audit.