The Comparator That Broke the Transitive Contract

I started at the one in a thousand, because that is where the symptom landed, and walked it backwards link by link until the failed stopped looking innocent.

Here is the shape of the comparator that violates transitivity, and the one property that makes it rare and total: the sort only fails when the data contains a cycle, so the comparator can pass every test and still break in production on the input that happens to form one.

This was Java's TimSort, and the mechanics are the same for any sort that checks its comparator's contract.

Why the comparator was cyclic

The comparator sorted by the three fields, and the three were the status and the priority and the date, and the comparison was the chained, and the chained was the if equal then next, and the next was the fallback, and the fallback was the inconsistent, because the status comparison used one ordering, and the priority used another, and the two disagreed, and the disagreed was the cycle.

The specific failure was the mixed ordering, and the mixed was the status ranked high to low and the priority ranked low to high, and the two were the opposite directions, and the opposite was the intransitive, because the comparison of two items depended on which field differed first, and the first was the data's arrangement, and the arrangement was the cycle, and the cycle was the contract's break.

The comparator looked correct, because each field's comparison was correct, and the correct fields were the assumption, and the assumption was the composition, and the composition was the wrong, because the composition of two orderings in opposite directions is not an ordering, and the not ordering is the cycle, and the cycle is the exception.

Why it only failed sometimes

The sort is the merge, and the merge is the comparisons, and the comparisons are the pairs, and the pairs are the data's, and the data's is the arrangement, and the arrangement is the cycle's presence, and the presence is the failure, and the failure is the rare, because the cycle requires the specific triple, and the triple is the unlikely, and the unlikely is the one in a thousand, and the thousand is the production.

The test data was the small, and the small was the no cycle, and the no cycle was the pass, and the pass was the confidence, and the confidence was the deploy, and the deploy was the production data, and the production data was the large, and the large was the cycle, and the cycle was the exception, and the exception was the incident, and the incident is the reason the comparator needs the property test rather than the example test.

The failure is the total, because the sort throws rather than returning a wrong order, and the throws is the report's absence, and the absence is the user's, and the user's is the incident, and the incident is the loud, and the loud is the better, because the wrong order would have been the silent, and the silent would have been the worse, and the worse is the reason the check exists.

The breakthrough

The breakthrough was the exception's message, and the message was the comparison method violates its general contract, and the contract was the transitivity, and the transitivity was the comparator, and the comparator was the three fields, and the three fields were the directions, and the directions were the opposite, and the opposite was the cycle, and the cycle was the fix's target.

The reproduction was the triple, and the triple was the three items, and the three items were the a and the b and the c, and the three were the cyclic comparison, and the cyclic was the proof, and the proof was the fix, and the fix was the consistent direction, and the consistent was the all ascending or the all descending, and the all was the ordering, and the ordering was the contract, and the contract was the sort's requirement.

This is the same family as the timezone-naive datetime that sorted backwards, and the shared property is the one worth fixing.

What I changed

Made every field's direction consistent. The comparisons all rank in the same direction, and the same is the ordering, and the ordering is the transitive, and the transitive is the contract, and the contract is the fix, and the fix is the sign, and the sign is the one character per field, and the character is the prevention.

Used the chained comparator builder. The comparing then comparing chain is the composed, and the composed is the consistent, and the consistent is the fix, and the fix is the library's, and the library's is the tested, and the tested is the safer than the hand written, because the builder composes the directions correctly by construction.

Added a property test for transitivity. The test generates random triples and asserts the contract, and the assert is the cycle's catch, and the catch is the prevention, and the prevention is the test, and the test is the fix, and the fix is the randomised, because the example tests miss the cycle and the property test finds it.

Defined a total order including the tiebreaker. The comparator ends with the unique identifier, and the identifier is the no ties, and the no ties is the total, and the total is the deterministic, and the deterministic is the fix, and the fix is the stability, and the stability is the same input's same output, and the same is the testability.

What I now do

A comparator must be transitive, so mixing field directions produces cycles on some inputs, and the sort throws when it finds one. Keep every field's direction consistent, use the chained comparator builder, add a property test that checks transitivity on random triples, and end with a unique tiebreaker.

The report failed on one dataset in a thousand because three records formed a comparison cycle, and the cycle existed because the status field ranked descending while the priority ranked ascending. That is the whole pattern, and it is the part worth remembering.

Published on debugly.dev by Rohit Bhadani | Founder of Krova Cloud