ColdFusion: Comparison Method Violates Its General Contract
This week, a single instance of an error showed up in my ColdFusion logging: "Comparison method violates its general contract!". The stacktrace pointed to something in the Java layer called TimSort; which is what ColdFusion's Array.sort() method is using under the hood. This error may be thrown if the .sort() callback / operator doesn't adhere to the set of requirements defined by the Comparable interface.
The .sort() operation that was throwing the error has been in production for many months without any issue at all. And, after reproducing the error locally, I was able to mitigate the error by simply changing the initial sort of the input array. Which is all to say, non-compliance with the Comparable interface doesn't necessarily mean that any error will be thrown.
In my case, I was attempting to sort hotspots visually within a prototype screen. Essentially, I wanted the hotspots to be sorted vertically in the y axis; but with any grouping of hotspots in close proximity to be sorted in the x axis. In other words, I wanted the visual sorting of the hotspots to follow the natural path of the human eye.
My hotspot data looks like this, where each hotspot has a screenID and (x,y) coordinates:
<cfscript>
id = 0;
hotspots = [
[ "id": ++id, "screenID": 11095, "x": 91, "y": 73 ],
[ "id": ++id, "screenID": 11095, "x": 40, "y": 5299 ],
[ "id": ++id, "screenID": 11095, "x": 70, "y": 5548 ],
[ "id": ++id, "screenID": 11095, "x": 45, "y": 5545 ],
[ "id": ++id, "screenID": 11095, "x": 27, "y": 4413 ],
[ "id": ++id, "screenID": 11095, "x": 40, "y": 5403 ],
[ "id": ++id, "screenID": 11095, "x": 40, "y": 5325 ],
[ "id": ++id, "screenID": 11095, "x": 23, "y": 676 ],
[ "id": ++id, "screenID": 11095, "x": 34, "y": 3662 ],
[ "id": ++id, "screenID": 11095, "x": 26, "y": 5100 ],
[ "id": ++id, "screenID": 11095, "x": 40, "y": 5455 ],
// ... several hundred entries ...
];
</cfscript>
My initial .sort() callback contained the following logic—note that I'm using the sgn() function to ensure that my operator only ever returns -1, 0, or 1 for all comparisons.
<cfscript>
include "./data.cfm";
hotspots.sort(
( a, b ) => {
// Sort by screen.
if ( a.screenID != b.screenID ) {
return sgn( a.screenID - b.screenID );
}
// Sort by proximal horizontal space.
if ( abs( a.y - b.y ) < 30 ) {
return sgn( a.x - b.x );
}
// Sort by vertical space.
return sgn( a.y - b.y );
}
);
</cfscript>
When I run this code in Lucee CFML—with this specific set of sample data—I get the following error:
java.lang.IllegalArgumentException
lucee.runtime.exp.NativeException: Comparison method violates its general contract!
at java.base/java.util.TimSort.mergeLo(TimSort.java:781)
at java.base/java.util.TimSort.mergeAt(TimSort.java:518)
at java.base/java.util.TimSort.mergeCollapse(TimSort.java:448)
at java.base/java.util.TimSort.sort(TimSort.java:245)
at java.base/java.util.Arrays.sort(Arrays.java:1515)
at java.base/java.util.ArrayList.sort(ArrayList.java:1750)
at java.base/java.util.Collections$SynchronizedList.sort(Collections.java:2470)
at java.base/java.util.Collections.sort(Collections.java:179)
at lucee.runtime.type.wrap.ListAsArray.sortIt(ListAsArray.java:262)
at lucee.runtime.functions.arrays.ArraySort.call(ArraySort.java:92)
at lucee.runtime.functions.arrays.ArraySort.call(ArraySort.java:79)
at lucee.runtime.functions.arrays.ArraySort.invoke(ArraySort.java:98)
at lucee.runtime.interpreter.ref.func.BIFCall.getValue(BIFCall.java:134)
at lucee.runtime.type.util.MemberUtil.call(MemberUtil.java:117)
at lucee.runtime.type.util.ArraySupport.call(ArraySupport.java:322)
at lucee.runtime.util.VariableUtilImpl.callFunctionWithoutNamedValues(VariableUtilImpl.java:785)
at lucee.runtime.PageContextImpl.getFunction(PageContextImpl.java:1714)
at ope_sort180.test_cfm$cf$a.call(/ope-sort/test.cfm:25)
This error is fairly cryptic. But, from what I've read, it means that the underlying sorting algorithm has detected that the final sort of the given collection is not predictable. Meaning, it's possible that running the same sort on the same collection with a different initial state may result in a different outcome.
This is because the sort operation violates one of the following:
Comparing two different elements must result in either a
-1or a1outcome. If comparing two different elements results in a0, the sorting algorithm cannot determine with certain which element should be sorted first.The comparison of two different elements,
(a,b), must result in the inverse of comparing(b,a).The transitive property of three elements must hold true such that no contradictions can be found. Meaning, if comparing
(a,b)results in1, and comparing(b,c)results in1, then comparing(a,c)must also result in1.
To see how my sample data was failing these contracts, I tried to write a ColdFusion script that would assert each rule using a given operator():
<cfscript>
setting requesttimeout = 120;
include "./data.cfm";
// ------------------------------------------------------------------------------- //
// ------------------------------------------------------------------------------- //
// Given two objects that are NOT the same element (they don't have the same "id" in
// this case), they need to have a non-0 result. This way, the sorting algorithm
// always knows which order they get sorted into regardless of the order in which they
// were visited.
for ( a in hotspots ) {
for ( b in hotspots ) {
ab = operator( a, b );
if ( ( ab == 0 ) && ( a.id != b.id ) ) {
echo( "Two different elements have an indeterminate sort order." );
dump( a );
dump( b );
abort;
}
}
}
// Given two objects, the sorting algorithm needs to consistently calculate a result
// regardless of the order of comparator arguments.
for ( a in hotspots ) {
for ( b in hotspots ) {
ab = operator( a, b );
ba = operator( b, a );
if ( ab != -ba ) {
echo( "Two different elements have an unpredictable inversion." );
dump( a );
dump( b );
abort;
}
}
}
// Given three objects, the transitive property has to hold true. That is, if A is
// sorted after B and B is sorted after C, A must also be sorted after C.
for ( a in hotspots ) {
for ( b in hotspots ) {
for ( c in hotspots ) {
ab = operator( a, b );
bc = operator( b, c );
ac = operator( a, c );
if (
( ( ab > 0 ) && ( bc > 0 ) && ( ac <= 0 ) ) ||
( ( ab < 0 ) && ( bc < 0 ) && ( ac >= 0 ) )
) {
echo( "The transitive property doesn't hold." );
dump( a );
dump( b );
dump( c );
dump( "ab: #ab#" );
dump( "bc: #bc#" );
dump( "ac: #ac#" );
abort;
}
}
}
}
echo( "Validation complete (success)." );
</cfscript>
When I run this ColdFusion code using my initial comparison operator (see above), it immediately finds that two of the elements in the hotspots collection have an indeterminate sort:
Two different elements have an indeterminate sort order.
Once I was able to predictably violate the Comparable contract, I was able to start refactoring the operator logic. Part of what I had to do was fallback to using the id value of the element so that no two elements were ever considered the same (ie, resulted in 0):
<cfscript>
function operator( a, b ) {
// Sort by screen.
if ( a.screenID != b.screenID ) {
return sgn( a.screenID - b.screenID );
}
// Group hotspots into predictable vertical bands.
var aRow = ceiling( a.y / 30 );
var bRow = ceiling( b.y / 30 );
// Sort by distant vertical space.
if ( aRow != bRow ) {
return sgn( aRow - bRow );
}
// Sort by proximal horizontal space.
if ( a.x != b.x ) {
return sgn( a.x - b.x );
}
// Sort by proximal vertical space.
if ( a.y != b.y ) {
return sgn( a.y - b.y );
}
// When all else is equal, fallback to using the record ID.
return sgn( a.id - b.id );
}
</cfscript>
By ensuring that the comparison of any two elements always results in either -1 or 1, I was able to get the sort working without error:
Validation complete (success).
This is the hardest I've had to think about sorting an array in a long time. And it was absolutely fascinating! I couldn't understand why the sort was failing until I demonstrated the indeterminate sort.
Want to use code from this post? Check out the license.
Reader Comments
This is really funny because I just ran into this error and I've never seen it before. But thank you for digging into it because I thought it was due to me having a comparison that resulted in numbers bigger than 1,-1 not resulting in 0!
@Scott,
Team work makes the dream work! Glad to be timely 🙂
Post A Comment — ❤️ I'd Love To Hear From You! ❤️
Post a Comment →