Forcing TimSort IllegalArgumentException with Dates

Question

Using Java 8 u151

We have the following sort going on:

Collections.sort(srs, (sr1, sr2) -> sr1.getValidStartTime().compareTo(sr2.getValidEndTime()));

Where getValidStartTime and getValidEndTime are Date objects.

Obviously this code is wrong, in that our goal really was to just sort based on start time.

However, and unfortunately the data causing the issue was deleted from the database, we were getting the infamous IllegalArgumentException. This seems logical because between elements, we weren't using the same values for comparing (A.start is compared to B.end, but B.start is compared to C.end).

What I can't do is figure out a data set that causes this exception to be thrown again. Fixing the code to always compare start times is the correct approach, but in regards to testing before and after data sets, I haven't been able to show proof of the fix (even though everyone already agrees we're taking the change).

Tried looking into the mergeHi method of TimSort that threw this but I can't quite follow all the gallop and Array copy stuff going on. So while I can tell where the exception is throw, getting it to be reproducible has been met with failure.

And the Date objects are static between sorts. Once set in the database, they're immutable. The list itself was also not changing during sorts. So to me, and I could be wrong, this points to data and that we had some weird combination of start and end dates that violated the transitive clause, but every combo I've tried always comes out with a valid (if not slightly bizarre looking) sort.

Thanks!

Answer 1

It's fairly difficult to come up with data that will cause TimSort to throw the "Comparison method violates its general contract!" exception, when given a buggy Comparator. As Misha pointed out (+1) the input must be at least 32 elements long, and generating random data until you get one that causes the exception seems like a reasonable approach.

Having such input data might seem useful in showing that the bug is actually fixed. After all, it crashed with the old Comparator and presumably it doesn't crash with the fixed Comparator. It's one piece of evidence, but it doesn't actually show that the fixed Comparator is in fact fixed; it might not cause a problem with this input data, but it could just as well crash with some other input data.

The question is, how far do you want to go with this?

Rely on the Library

One approach is simply to use the Java 8 construct for creating a Comparator. You could rewrite the statement as follows:

Collections.sort(srs, Comparator.comparing(SR::getValidStartTime));

If you believe that the library's sort routine works, and that the Comparator.comparing routine works, then maybe you don't need to test this.

Test Comparator Contract Requirements

If you really want to test this Comparator (or perhaps you have a more complicated Comparator that you'd like to test), a different approach would be to write some unit tests for it based on the requirements listed in the Comparator.compare method specification:

• Antisymmetry: for all x and y, sgn(compare(x, y)) == -sgn(compare(y, x))

• Transitivity: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0

• Substitutability: compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z

You could write some unit tests that take a canned set of values and verifies that the given Comparator has these properties, for all combinations of inputs taken from the value set.

Verify Ordering of Sorted Result

Still another approach is to take some input data (either real, or randomly generated) and sort it using the Comparator. If it doesn't crash, verify that the resulting list is the order imposed by that Comparator. If the Comparator behaves inconsistently, it's possible or even likely that the result of sorting the items won't result in a list that is actually sorted according to that comparator. This is because the items to which the Comparator is applied during the sorting process are different from the items to which it's applied when you're comparing adjacent items. This isn't guaranteed to find errors, of course, but it's a potentially useful cross-check. Note that this doesn't test that the Comparator is semantically correct. It merely is a test of whether the Comparator behaves consistently.

Answer 2

The easiest way to do it is just keep generating random lists and trying to sort until it trips up the check. On jdk 1.8.0_111, the shortest list to cause the exception is 32 elements long. Here's the list of start/end timestamps that can be used to initialize Date values and will cause the exception:

{start=68208554877356084, end=3791095193142800835}
{start=248264922016936970, end=5326356389367348592}
{start=70847878331153962, end=1329864610265504554}
{start=299053597297857298, end=4543460986676142955}
{start=2075045414748723202, end=1193808915252175698}
{start=1888180037471781608, end=2492314749794483810}
{start=506596727265987351, end=2390472400080050280}
{start=4533260585328085001, end=2273691205607504663}
{start=5678209310012100575, end=959412777775545678}
{start=2732174389724934002, end=1780458709387750881}
{start=3098641550091084357, end=7078749384785410602}
{start=556524021068368297, end=8482788837298542192}
{start=98318333071465581, end=4156661237757928788}
{start=2084735587245502205, end=4379712643293008540}
{start=3165092267008534695, end=3427927233210778860}
{start=3109680552226050258, end=7303065366486904947}
{start=4928610946211198422, end=6426677832945805822}
{start=965369716172656147, end=6219167484686793206}
{start=805041445200191777, end=2942634988195806902}
{start=8045405997433808237, end=6001857015663585724}
{start=6633159983148701791, end=1448351075620872268}
{start=4539362557763873114, end=8432020244491782408}
{start=7435017849572867526, end=5951614001812150640}
{start=9205367993832979048, end=1341233048581746570}
{start=8478026453445310753, end=530855741009189818}
{start=4638397659065784972, end=2597599860193612976}
{start=3683809635722753669, end=8506390941316155399}
{start=5946468237919207244, end=3711093891423756040}
{start=6965128507257577261, end=8627460098134987362}
{start=7493578845247407113, end=8568660839840900159}
{start=7097494652946649557, end=8999069292652823540}
{start=9190087421488513073, end=20737341215892578}