search

akeranen / the-one

The Opportunistic Network Environment simulator
Other
208 stars 198 forks source link

Bugfix: compareByQueueMode() method causing IllegalArgumentException #31

Closed kenog closed 7 years ago

kenog commented 7 years ago

When using the PropherRouter, I experienced the following exception:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract! at java.util.TimSort.mergeLo(TimSort.java:777) at java.util.TimSort.mergeAt(TimSort.java:514) at java.util.TimSort.mergeCollapse(TimSort.java:441) at java.util.TimSort.sort(TimSort.java:245) at java.util.Arrays.sort(Arrays.java:1512) at java.util.ArrayList.sort(ArrayList.java:1454) at java.util.Collections.sort(Collections.java:175) at routing.ProphetRouter.tryOtherMessages(ProphetRouter.java:246) at routing.ProphetRouter.update(ProphetRouter.java:206) at core.DTNHost.update(DTNHost.java:346) at core.World.updateHosts(World.java:198) at core.World.update(World.java:167) at ui.DTNSimTextUI.runSim(DTNSimTextUI.java:29) at ui.DTNSimUI.start(DTNSimUI.java:77) at core.DTNSim.main(DTNSim.java:85)

I tracked it down to being caused by the method compareByQueueMode() of the MessageRouter class. It is called by some comparators used in the Prophet- and MaxProp-based routing protocols. The problem here is that in case the hashcodes of the two messages are equal, there is still a possibility, that the function does not return 0. In that case, the same result (-1 or 1) is returned, regardless of the order of the arguments, the method is called with. This behavior violates the contract for the compare method as defined in the Java documentation:

"The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y."

Therefore, the above shown exception is thrown. To mitigate this, I adapted the behavior to the behavior in the FIFO case of the method. Now the function is compliant to the requirements and does not throw an exception anymore.

akeranen commented 7 years ago

Good catch. And I think your proposed fix is good too. The downside of this fix is that it changes the ordering so implementations before this fix will have different order when using this mode, but I think that's fine. @tk721 can you perhaps double check that this is OK before we merge?

tk721 commented 7 years ago

Looks good to me. It would be nice if we had tests to have more confidence that fixes like this don't end up breaking something else.

julianofischer commented 7 years ago

Thank you, @kenog.