DocumentSorter.compare bug

[chris9182]

this was written up with the help of Claude Opus 4.8, but i also manually verified both the bug and the bugfix in a local build.

DocumentSorter.compare returns -1 for null-vs-null → violates Comparator contract (orderBy throws / mis-sorts)

Version

• nitrite: 4.3.0 (same code on develop at time of writing) (also verified in 4.4)
• store: nitrite-mvstore-adapter 4.3.0
• JDK: tested on 17 and 25

Summary

DocumentSorter (used by find(FindOptions.orderBy(field, ...)) on the in-memory / blocking-sort path, i.e. when the sort field is not covered by an index) compares two null-keyed documents as -1 instead of 0. This breaks the Comparator contract (antisymmetry): compare(a, b) == compare(b, a) == -1. Consequences on a field that is null/absent in more than one document:

• Intermittent IllegalArgumentException: Comparison method violates its general contract! from TimSort, once the result set is ≥ 32 rows and the run layout trips TimSort's invariant check. (A deterministic reproducer is below.)
• Even when it does not throw, the resulting order is undefined, because the comparator is inconsistent.

Root cause

org.dizitart.no2.common.streams.DocumentSorter#compare:

if ((value1 == null || value1 instanceof DBNull) && value2 != null) {
    result = -1;
} else if (value1 != null && (value2 == null || value2 instanceof DBNull)) {
    result = 1;
} else if (value1 == null) {          // <-- reached only when BOTH are null
    result = -1;                      // <-- should be 0; returns -1
}

When both values are null/DBNull, the first two branches are false and the third returns -1, so no two null-keyed documents ever compare equal.

Deterministic reproduction (end-to-end, throws 5/5)

Nitrite db = Nitrite.builder()
    .loadModule(MVStoreModule.withConfig().build())   // in-memory
    .openOrCreate();
NitriteCollection c = db.getCollection("c");

Random r = new Random(65);           // fixed seed -> fixed layout
for (int i = 0; i < 35; i++) {
    Document d = Document.createDocument("idx", i);
    if (!r.nextBoolean()) d.put("value", r.nextDouble());  // ~14 of 35 left null
    c.insert(d);
}

// "value" is NOT indexed -> in-memory blocking sort
c.find(FindOptions.orderBy("value", SortOrder.Ascending)).toList();
// -> java.lang.IllegalArgumentException: Comparison method violates its general contract!

Isolated proof of the contract violation (no Nitrite, always throws)

The same null-handling as a standalone comparator; list.sort throws deterministically for new Random(65), n=35:

static int cmp(Double a, Double b) {          // mirrors DocumentSorter.compare
    if (a == null && b != null) return -1;
    else if (a != null && b == null) return 1;
    else if (a == null) return -1;            // both null -> -1  (the bug)
    else return Double.compare(a, b);
}
// build 35 elements, ~14 null, with new Random(65); list.sort(cmp) -> IllegalArgumentException

Expected

Two null keys compare equal; orderBy returns a stable, fully-ordered result (nulls grouped, first or last) and never throws.

Suggested fix

Return 0 when both sides are null/DBNull:

boolean n1 = value1 == null || value1 instanceof DBNull;
boolean n2 = value2 == null || value2 instanceof DBNull;
if (n1 && n2)      result = 0;
else if (n1)       result = -1;
else if (n2)       result = 1;
else { /* existing comparable comparison */ }

This restores a valid total order and matches the intended "nulls first" behavior.