QualityQuery.compareTo goes in a circle when numeric and non-numeric topic ids are mixed, so the TREC topic readers can throw

QualityQuery implements Comparable<QualityQuery>, and its compareTo (QualityQuery.java:68-81 on main 645d4fe14a20) returns n - nOther when both ids parse as int and otherwise compares the ids as Strings. When whole-number ids and other ids are mixed, the two orders disagree and form cycles: 2 < 100 as numbers, 100 < 1a and 1a < 2 as Strings. TrecTopicsReader.readQueries and Trec1MQReader.readQueries sort their result with Arrays.sort(qq) under // sort result array (by ID), and QueryDriver calls the former on its topics file. With 32 or more topics the JDK's TimSort can detect the cycle and throw IllegalArgumentException: Comparison method violates its general contract!: a 115-topic file (ids 1..111 plus 1a, 20a, 64a, 99a, each after its parent) throws on main and 10.6.0, with assertions on and off. Otherwise the result order depends on the file order. Digit-only ids beyond the int range (3000000015) also fall back to String order and trigger it with 35 topics. A side issue, n - nOther overflow (2147483647 vs -1), needs a negative id. The logic dates from LUCENE-836 (2007, first released in 2.3.0) and became an exception when JDK 7 made TimSort the default. A total order (Integer.compare for two int ids, int ids first, String order for the rest) fixes it.

QualityQuery.java:68-81:

/* for a nicer sort of input queries before running them.
 * Try first as ints, fall back to string if not int. */
@Override
public int compareTo(QualityQuery other) {
  try {
    // compare as ints when ids ints
    int n = Integer.parseInt(queryID);
    int nOther = Integer.parseInt(other.queryID);
    return n - nOther;
  } catch (NumberFormatException _) {
    // fall back to string comparison
    return queryID.compareTo(other.queryID);
  }
}

Both readers end with // sort result array (by ID) and Arrays.sort(qq) (TrecTopicsReader.java:106-108, Trec1MQReader.java:84-86); QueryDriver.main reads its topics file with TrecTopicsReader (QueryDriver.java:77-79). The readers take the id text as written (TrecTopicsReader.java:71-73, Trec1MQReader.java:70-71) and the public constructor accepts any String.

• 2 vs 100: both ints, 2 - 100 = -98, so 2 < 100.
• 100 vs 1a: 1a is not an int, so Strings: '0' (48) < 'a' (97), -49, so 100 < 1a.
• 1a vs 2: Strings, '1' < '2', -1, so 1a < 2.

So 2 < 100 < 1a < 2. The same can happen when an id that starts with a digit but is not an int (1a, 10.1, 31_1) meets int ids of different lengths (2 < 10 < 10.1, but "10.1" < "2"; not every such mix cycles: 2 < 10 < 3a is consistent), and when in-range ints meet digit-only ids too large for an int (9 < 10 as ints, but "10" < "3000000015" < "9" as Strings). Integer.parseInt accepts a sign, so signed ids can cycle even at one length (-99, -01, -0a). Letter-prefixed ids (q1, MB01) mixed with ints, and fixed-length ids without a sign, stay consistent (with ASCII digits): letters sort after digits, and equal-length digit strings sort like numbers (6,500 random fixed-length trials, 0 exceptions; exhaustive law checks over all two- and three-character ids of small alphabets, 0 violations).

Arrays.sort(Object[]) is the JDK's TimSort (unless -Djava.util.Arrays.useLegacyMergeSort=true), documented to throw IllegalArgumentException "if the natural ordering of the array elements is found to violate the Comparable contract". Below 32 elements it sorts by binary insertion and never merges; the exception comes only from its merge steps (ComparableTimSort.mergeLo / mergeHi) when a merge meets an impossible state. So fewer than 32 topics never throw, and larger files throw only for some orders (these counts are for JDK 25's TimSort; the broken contract does not depend on the runtime): 172 of 100,000 random natural-order files with 1 to 12 <n>a sub-topics threw in one seeded search; 889 and 1,055 of 200,000 with dotted (3.1) and underscore (31_1) sub-topics in an independent reproducer's search.

The sort returns some order that depends on the input: the three topics 2, 100, 1a come back unchanged for each of the three rotations of the file ([2, 100, 1a], [100, 1a, 2], [1a, 2, 100]). With the legacy merge sort the 115-topic file returns all 115 topics, starting [1, 1a, 2, 3, 4, ...], with 1a before 100 (positions 1 and 102) although compareTo(1a, 100) is 49.

n - nOther wraps for extreme ids: compareTo(2147483647, -1) and compareTo(-1, 2147483647) are both -2147483648, so each is "less than" the other. Two non-negative ints cannot overflow, so this needs a negative id.

• Who can hit it. Users of lucene/benchmark's search-quality package: the QueryDriver command-line tool ("Command-line tool for doing a TREC evaluation run") and code that calls TrecTopicsReader.readQueries or Trec1MQReader.readQueries, or sorts QualityQuery objects itself. The package docs invite other id sources: "To run on different formats of queries and judgements provide your own Judge and Quality queries".
• What it takes. A topics file in the readers' format (neither validates ids) whose ids mix plain numbers with ids that start with a digit and are not ints (sub-topics such as 12a, 3.1, 31_1), or with digit-only ids beyond 2147483647 (1..33 plus 3000000015 and 3000000016, each right after 15 and 16, 35 topics, throw through Trec1MQReader). Three topics are enough for an order that depends on the file; the exception needs 32 or more and an order the sort detects (JDK 25). Default settings, public API, single thread.
• Effect. A clean IllegalArgumentException from readQueries; QueryDriver stops before any query runs, and the submission file it already created is left empty (read, not run). When the sort returns, judgements are looked up by id (TrecJudge.java:91), so each query's results and metrics do not change; the order sets the run, log and submission order, which topics setMaxQueries(n) ("Useful at debugging") keeps, and the summation order of the averages, so they can differ by floating-point rounding (read, not run).
• Not hit. Search, indexing and every module other than lucene/benchmark; topic sets whose ids are all non-negative ints, all letter-prefixed, ints mixed only with letter-prefixed ids, or all of one length without a sign (ASCII digits).
• How likely. Rare. TREC topic sets are conventionally numbered with plain ints, and no public topic set mixing these id kinds is known; the example ids are synthetic. Hand-extended topic sets (sub-topics, merged collections with long ids) make it plausible.

The test builds new QualityQuery(id, Map.of()) for 2, 100 and 1a and fails only if the signs of compareTo(2, 100), compareTo(100, 1a) and compareTo(1a, 2) are equal and non-zero, which is a cycle. It does not fix which way the ids must sort, so any total order a fix picks passes.

The user-visible symptom, the readQueries exception on the 115-topic file, is left out of the repro on purpose: it follows from this cycle, depends on the input order and needs 32 or more topics. Its output is in the observed output below and in the steps above.

cp $REPRO/TestQualityQueryCompareTo.java $LUCENE/lucene/benchmark/src/test/org/apache/lucene/benchmark/quality/
cd $LUCENE && ./gradlew :lucene:benchmark:test --tests org.apache.lucene.benchmark.quality.TestQualityQueryCompareTo -Ptests.seed=DEADBEEF -Ptests.asserts=true
# also with -Ptests.asserts=false

# the minimal test, stock main 645d4fe14a20, gradle, -Ptests.asserts=false (true prints the same)
TestQualityQueryCompareTo > testCompareToIsTransitive FAILED
    java.lang.AssertionError: expected no cycle, got compareTo(2,100)=-1, (100,1a)=-1, (1a,2)=-1
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:8D60531F55597FD9]:0)
        at junit@4.13.2/org.junit.Assert.fail(Assert.java:89)
        at junit@4.13.2/org.junit.Assert.assertTrue(Assert.java:42)
        at junit@4.13.2/org.junit.Assert.assertFalse(Assert.java:65)
        at org.apache.lucene.benchmark.quality.TestQualityQueryCompareTo.testCompareToIsTransitive(TestQualityQueryCompareTo.java:32)
1 test completed, 1 failed
BUILD FAILED

# the same failure on the 10.6.0 release jars, -ea and -da; with the fix: BUILD SUCCESSFUL

# the user-visible symptom: TrecTopicsReader on ids 1..111 plus 1a, 20a, 64a, 99a (115 topics), stock main jars
java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.base/java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:870)
    at java.base/java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:487)
    at java.base/java.util.ComparableTimSort.mergeForceCollapse(ComparableTimSort.java:426)
    at java.base/java.util.ComparableTimSort.sort(ComparableTimSort.java:222)
    at java.base/java.util.Arrays.sort(Arrays.java:1038)
    at org.apache.lucene.benchmark.quality.trec.TrecTopicsReader.readQueries(TrecTopicsReader.java:108)
# with the fix: 115 topics, sorted, starting [1, 2, 3, 4, 5, 6, 7, 8]

• The JDK contract. Comparable requires signum(x.compareTo(y)) == -signum(y.compareTo(x)) and transitivity for all x, y, z; Arrays.sort documents the IllegalArgumentException for exactly that violation.
• The code's own intent. "for a nicer sort of input queries before running them. Try first as ints, fall back to string if not int" (QualityQuery.java:68-69): non-int ids were expected. Both readers say // sort result array (by ID); a cycle has no sorted order.
• The API. The public constructor takes any String id (QualityQuery.java:44); the class javadoc, getQueryID and the package docs put no limit on ids, and the readers keep the id text as written.
• Tests and history. Both TestQualityRun tests read trecTopics.txt (20 topics, ids 0..19, in order) with TrecTopicsReader: testTrecTopicsReader checks qqs[0], qqs[1] and qqs[19], and testTrecQuality's per-position checks (i % 8) assume numeric order. No test uses a non-int id or 32 topics. No commit, CHANGES or MIGRATE entry discusses the id order, and every later edit to compareTo was cosmetic. The code predates JDK 7, whose TimSort turned the inconsistency into an exception.
• Precedent. Lucene fixed broken compareTo methods as bugs before: LUCENE-5790 (2014), "Fix compareTo in MutableValueDouble and MutableValueBool".

The strongest case for "intended" (the intended-behaviour check and the cross-model intended-lens reviewer): the readers document numeric ids (<num> Number: nnn, qnum:qtext), and as long as every id is a non-negative number that fits in an int, compareTo is a total order (an exhaustive law check and a shuffled 5,000-topic file pass); sub-topic ids such as 1a are outside the format's numeric examples; letter-prefixed and fixed-length unsigned ids are consistent too; the sort is cosmetic, each query's metrics do not depend on it, the module is a developer tool, and the overflow needs a negative id.

Why it fails: (1) the format does not stop at the int range: digit-only ids beyond it are numbers in the documented format and still cycle (9 < 10 as ints, "10" < "3000000015" < "9" as Strings) and throw (35 topics); this needs no sub-topic ids; (2) the format lines are sketches, not preconditions: nothing validates ids, the shipped topics use Number: 0 to 19, and the package docs invite other formats; (3) the failure is not cosmetic: readQueries throws and QueryDriver stops; (4) a public Comparable must order every value its constructor accepts. All verifiers rate the intended argument weak; the intended-behaviour check judged the bug real, impact low.

Option A was built and run; B, C and D are alternatives with different orders, not built. Whatever is chosen, the minimal test stays the regression test: it passes for any total order.

A PR would also add a CHANGES.txt line under Bug Fixes.

One method in QualityQuery.java (+16/-7), the finder's fix unchanged. Every id is either an int or not; ints are ordered by Integer.compare (no overflow), the rest by String.compareTo, and every int comes before every non-int. Each part is a total order and the parts do not interleave, so the whole is one. It also removes the n - nOther overflow.

/* for a nicer sort of input queries before running them.
 * Numeric ids sort first, by value; other ids follow, as strings. This is a total order. */
@Override
public int compareTo(QualityQuery other) {
  Integer n = parseIntOrNull(queryID);
  Integer nOther = parseIntOrNull(other.queryID);
  if (n != null && nOther != null) {
    return Integer.compare(n, nOther);
  } else if (n != null) {
    return -1;
  } else if (nOther != null) {
    return 1;
  }
  return queryID.compareTo(other.queryID);
}

private static Integer parseIntOrNull(String id) {
  try {
    return Integer.parseInt(id);
  } catch (NumberFormatException _) {
    return null;
  }
}

Trade-offs

• Unchanged: all-int sets (the shipped ids 0..19 stay [0, 1, ..., 19]), all-non-int sets, and ints mixed with letter-prefixed ids ([2, 5, 30, MB01, q1, q10] before and after).
• Now deterministic: 2, 100, 1a sorts to [2, 100, 1a] for every input order.
• Changed: non-int ids that start with a character below '0' move from before the ints to after them ([#1, -x, 2, 5, 30] becomes [2, 5, 30, #1, -x]).
• Still text order: digit-only ids beyond the int range follow the ints and sort as Strings among themselves ([7, 33, 10000000000, 3000000015]); option B orders them by value.
• Ids that parse to the same int (007, 7) compare equal, as before; the stable sort keeps their file order.
• Cost: the stock code throws at most one NumberFormatException per comparison (it stops at the first parseInt that fails); the fix parses both ids, so it throws one for each non-int id, two when both are non-int. Parsing once in the constructor would avoid both (not built).

What the checks validated

• Gradle in a scratch worktree of main 645d4fe14a20 with the diff applied: the minimal test passes with -Ptests.asserts=true and false; --tests 'org.apache.lucene.benchmark.quality.*' passes (TestQualityQueryCompareTo, and TestQualityRun's testTrecQuality and testTrecTopicsReader); :lucene:benchmark:check passes (19 test classes, 91 tests, 0 failures; google-java-format, ecjLint, forbiddenApis).
• With the fixed class: the 115-topic file reads as 115 sorted topics; the three-topic files all come back [2, 100, 1a]; compareTo(2147483647, -1) is 1 and the reverse -1.
• Earlier, on main a9779ef3c193: an exhaustive law check over 14 ids finds 0 antisymmetry and 0 transitivity violations (109 transitivity and 4 antisymmetry violations without the fix); the finder's 115-topic test, an independent 6-test reproduction and the cross-model reviewers' tests pass; TestQualityRun stays green also with -Dtests.verbose=true (that run had three other hunt fixes applied too).

Treat ids made only of digits as numbers compared by value (for example BigInteger, or length after stripping leading zeros, then the digits), then the rest as Strings.

Trade-offs

Also orders 33 < 3000000015 < 10000000000. More code; signs and leading zeros must be decided and kept total.

For example 1, 1a, 2, 10, 10.1, 100.

Trade-offs

The nicest order for sub-topic ids, but the most code, and it must itself be shown to be a total order.

return queryID.compareTo(other.queryID);

Trade-offs

Smallest change and total, but it reorders every all-numeric topic set (0, 1, 10, 11, ..., 19, 2, ..., 9), changing the run and report order for every current user; TestQualityRun.testTrecTopicsReader expects qqs[19] to be topic 19, which would become topic 9, and testTrecQuality's per-position checks would no longer line up (read, not run).

Widens the numeric range.

Trade-offs

Keeps the 2 < 100 < 1a < 2 circle.

Method: semi-formal. The hunt unit compared Lucene's search-quality code with reference semantics. For QualityQuery.compareTo it checked antisymmetry and transitivity exhaustively over a 14-id alphabet on the real class (2,940 checks): 4 antisymmetry violations, all from the n - nOther overflow, and 109 transitivity violations, 6 of them without the int extremes (example: 9 < 10 < 5x but not 9 < 5x). With the fix: 0 and 0.

A seeded random search (seed 371) then generated 100,000 natural-order topic files (ids 1..N, N = 32..331, plus 1 to 12 <n>a sub-topics right after their parents) and ran the real TrecTopicsReader.readQueries on each: 172 threw. The smallest, 115 topics with 1a, 20a, 64a, 99a, became the finder's JUnit; the registry's minimal repro keeps only the three-id cycle.

Then: an independent reproducer wrote its own tests from the claim (dotted sub-topics, beyond-int ids, the overflow); cross-model reviews (OpenAI GPT-5.6, refute and intended lenses) wrote and ran their own tests; a devil's-advocate verifier argued "intended" and rejected it; an adjudication re-ran the tests and confirmed.