23 April 2014

What to do when you get "Comparison method violates its general contract!"

Java 7 switched to a new sort algorithm - called ComparableTimSort. The old algorithm would silently ignore when you violate the Comparator/Comparable contract. The new one throws an exception "Comparison method violates its general contract!"

The contract is in the interface Comparable. The most common is to break the transitive contract. That is: If A < B and B < C, than A should be less than C. Stackoverflow.com has several posts on the issue.

I have made a small program that detects what elements that causes this issue. It only works for small lists but has helped me to debug compareTo()/compare() methods.

package se.lesc.blog;

import java.util.Comparator;

public class TransitivityTester {

    public static void transitivityTester(Object list[]) {
        transitivityTester(list, null);
    }
    
    /** Check that a lists compareTo() method is correct with respect to transitivity */    
    public static void transitivityTester(Object list[], Comparator<Object> comparator) {

        //Cache all possible comparison (for speed)
        byte[][] compareTable = new byte[list.length][];
        for (int x = 0; x < list.length; x++) {
            byte[] column = new byte[list.length];
            compareTable[x] = column;
            for (int y = 0; y < list.length; y++) {
                int result;
                if (comparator != null) {
                    result = comparator.compare(list[x], list[y]);    
                } else {
                    @SuppressWarnings("unchecked")
                    Comparable<Object> comparableX = (Comparable<Object>)list[x];
                    result = comparableX.compareTo(list[y]);
                }
                
                byte normalizedResult = normalize(result);
                column[y] = normalizedResult; 
            }
        }
        
        //Expensive O(n^3) iteration
        for (int a = 0; a < list.length; a++) {
            for (int b = 0; b < list.length; b++) {
                for (int c = 0; c < list.length; c++) {

                    if (compareTable[a][b] < 0 && compareTable[b][c] < 0) {
                        if (! (compareTable[a][c] < 0)) {
                            transitiveError("A < B && B < C but not A < C", a, b, c);
                        }
                    } else if (compareTable[a][b] > 0 && compareTable[b][c] > 0) {
                        if (! (compareTable[a][c] > 0)) {
                            transitiveError("A > B && B > C but not A > C", a, b, c);
                        }
                    } else if (compareTable[a][b] == 0 && compareTable[b][c] == 0) {
                        if (! (compareTable[a][c] == 0)) {
                            transitiveError("A == B && B == C but not A == C", a, b, c);
                        }
                    }
                }
            }
        }
    }
    
    private static void transitiveError(String transitiveRule, int a, int b, int c) {
        String errorMessage =
                        transitiveRule +
                        " (A = " + a + ", B= " + b + ", C = " + c + ") " + 
                        "Comparison method violates its general contract!";
        throw new IllegalArgumentException(errorMessage);
    }

    private static byte normalize(int result) {
        byte normalizedResult;
        if (result > 0) {
            normalizedResult = 1;
        } else if (result < 0) {
            normalizedResult = -1;
        } else {
            normalizedResult = 0;
        }
        return normalizedResult;
    }
}

Here is some test code for the above class:
package se.lesc.blog;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

import org.junit.Before;
import org.junit.Test;

public class TransitivityTesterTest {

    private List<Integer> list;

    @Before
    public void setUp() {
        list = new ArrayList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
    }

    @Test
    public void testNormalIntegerListShouldWork() {
        TransitivityTester.transitivityTester(list.toArray(new Integer[0]));        
    }
    
    @Test
    public void testCrazyOneIsAlwaysMoreComparator() {
        TransitivityTester.transitivityTester(list.toArray(new Integer[0]), new CrazyOneIsAlwaysMoreComparator());        
    }
    
    @Test
    public void testCrazyAllIsOneComparator() {
        TransitivityTester.transitivityTester(list.toArray(new Integer[0]), new CrazyAllIsOneComparator());        
    }
    
    public static class CrazyOneIsAlwaysMoreComparator implements Comparator<Object> {
        @Override
        public int compare(Object o1, Object o2) {
            Integer i1 = (Integer) o1;
            Integer i2 = (Integer) o2;
            if (i1.intValue() == 1) {
                return 1; 
            } else {
                return i1.compareTo(i2);
            }
        }
    }
    
    public static class CrazyAllIsOneComparator implements Comparator<Object> {
        @Override
        public int compare(Object o1, Object o2) {
            Integer i1 = (Integer) o1;
            Integer i2 = (Integer) o2;
            if (i1.intValue() == 1 || i2.intValue() == 1) {
                return 0; 
            } else {
                return i1.compareTo(i2);
            }
        }
    }
}

15 January 2014

More Btrace debugging

In the post http://blog.lesc.se/2009/06/btrace-debugging-tool-with-bugs.html I wrote about how it is possible to debug a running Java application. Here is some more magic.

Let say you have this simple program:

import javax.swing.JFrame;

public class SimpleApp {
  public static void main(String args[]) {
    JFrame frame = new JFrame("Simple application");
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.setSize(200, 100);
    frame.setVisible(true);
  }
}


And this Btrace script:
import com.sun.btrace.annotations.*;
import static com.sun.btrace.BTraceUtils.*;
import java.awt.EventQueue;
import java.awt.AWTEvent;
import java.awt.event.MouseEvent;
import java.lang.reflect.Field;

@BTrace
public class SimpleAppMouseTracer {
  @OnMethod(
     clazz="java.awt.EventQueue",
     method="dispatchEvent"
  )
  public static void onevent(@Self EventQueue queue, AWTEvent event) {
    if (event instanceof MouseEvent) {
      MouseEvent mouseEvent = (MouseEvent) event;
      Field idField = field("java.awt.AWTEvent", "id");
      Field xField = field("java.awt.event.MouseEvent", "x");
      Field yField = field("java.awt.event.MouseEvent", "y");
      if (getInt(idField, mouseEvent) == MouseEvent.MOUSE_CLICKED) {
        println(
          strcat("x = ", strcat(str(getInt(xField, mouseEvent)),
          strcat(", y = ", str(getInt(yField, mouseEvent))))));
      }
    }
  }
}


I have installed the Btrace into Java VisualVM (I downloaded and installed all the visualvm plugins from https://kenai.com/projects/btrace/downloads).

 


Each time I click with the mouse inside the Window I get a printout with the mouse coordinates.

The Btrace code is Java, but with many restrictions. That is why the String creation code gets a bit large; because build in Btrace functions must be used. The same goes for accessing variables inside the MouseEvent object.