Comparison method violates its general contract ошибка java

A variation of Gili’s answer to check if the comparator satisfies the requirements described in the compare method’s javadoc — with a focus on completeness and readability, e.g. by naming the variables the same as in the javadoc. Note that this is O(n^3), only use it when debugging, maybe just on a subset of your elements, in order to be fast enough to finish at all.

  public static <T> void verifyComparator(Comparator<T> comparator, Collection<T> elements) {
    for (T x : elements) {
      for (T y : elements) {
        for (T z : elements) {
          int x_y = comparator.compare(x, y);
          int y_x = comparator.compare(y, x);
          int y_z = comparator.compare(y, z);
          int x_z = comparator.compare(x, z);

          // javadoc: The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x))
          if (Math.signum(x_y) == -Math.signum(y_x)) { // ok
          } else {
            System.err.println("not holding: sgn(compare(x, y)) == -sgn(compare(y, x))" //
                + " | x_y: " + x_y + ", y_x: " + y_x + ",  x: " + x + ", y: " + y);
          }

          // javadoc: The implementor must also ensure that the relation is transitive:
          // ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.
          if (x_y > 0 && y_z > 0) {
            if (x_z > 0) { // ok
            } else {
              System.err.println("not holding: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0" //
                  + " | x_y: " + x_y + ", y_z: " + y_z + ",  x_z: " + x_z + ", x: " + x + ", y: " + y + ", z: " + z);
            }
          }

          // javadoc: Finally, the implementor must ensure that:
          // compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.
          if (x_y == 0) {
            if (Math.signum(x_z) == Math.signum(y_z)) { // ok
            } else {
              System.err.println("not holding: compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z" //
                  + " | x_y: " + x_y + ", x_z: " + x_z + ",  y_z: " + y_z + ", x: " + x + ", y: " + y + ", z: " + z);
            }
          }
        }
      }
    }
  }

1. Difference Between Comparator and Comparable Interfaces
2. Comparison Rules for Comparator and Comparable
3. Java Code Having the comparison method violates its general contract Error
4. Java Solutions Using the Comparator and Comparable Interfaces

Today, we will learn about the comparison rules used by the Comparator and Comparable interfaces, which will lead to possible causes of the comparison method violates its general contract error in Java. After that, we will understand two solutions using Comparator and Comparable interfaces.

Difference Between Comparator and Comparable Interfaces

These are two interfaces in Java core libraries. The Comparator is a function that compares two different objects and is independent of anything else.

It only looks for its two inputs, continues its process with them, and presents the results.

On the other hand, the Comparable is an interface that we mix with a data class. For instance, we have a class with some data; the Comparable interface will be used to compare this class’s first object with the same class’s second object.

It means the Comparable interface indicates that this instance can be compared with another instance of the same class. Remember, the Comparable defines the natural order for the class.

In other respects, it is also a comparison function just like the Comparator and has the same rules for the return value, transitive, reflexive, etc.

Comparison Rules for Comparator and Comparable

The comparison method violates its general contract means that the Comparator or Comparable (based on what we are using) has a bug and violates one of the consistency rules. What are the consistency rules?

Let’s learn them below.

We assume that we have written our Java program for integer-type values. So, our comparison function must adhere to the following rules.

• Given any two integers a and b, the Trichotomy Law must be satisfied, which means exactly one of the following relations must be true:

  • a is less than b (it returns -ve value if a < b)
  • a equals b (it returns 0 if a == b )
  • a is greater than b (it returns +ve value if a > b)

• It must satisfy the Transitivity, which means if a < b and b < c then, for any three numbers a, b, c, it implies a < c.

• The third rule is about Antisymmetry, where a < b implies ~b < a

• Substitutability is also a comparison rule that says, suppose, a == b and a < c; this implies b < c.

• The final comparison rule is Reflexivity, where a == a; also ~a < a.

If any of these rules are violated, we get the error saying the comparison method violates its general contract. Let’s learn it with the help of a code example below.

Java Code Having the comparison method violates its general contract Error

Example Code:

//import libraries
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
import static java.util.stream.Collectors.toCollection;

//Main
public class Main {
    public static void main(String[] args) {
        //generate random numbers
        List<Integer> list = new Random(209).ints(32L)
                             .boxed()
                             .collect(toCollection(ArrayList::new));
        //sort using lambda expression
        list.sort(logging((a,b) -> a-b));
   }//end main()

    //logging the comparisons
    static Comparator<Integer> logging(Comparator<Integer> c) {
       return (a, b) -> {
           int r = c.compare(a, b);
           System.err.printf("%,14d %,14d => %,14dn", a, b, r);
           return r;
       };
    }//end logging()
}//end class

In this code, we are generating a few random numbers by using the ints instance of the Random class, which is used to generate the stream of random numbers.

For this code, if we sort as list.sort((a, b) -> a - b); then, we will not be able to identify what the problem is and where it is happening. That’s why we are sorting it via logging, which will help us to identify it.

It gives us an error, but it also provides a lot of comparisons of numbers. We will not discuss all, but a few of them are enough to find the error.

OUTPUT:

As we can see, the program violates the consistency rule here, resulting in this error. In the next section, let’s have the solution using Comparator and Comparable.

Java Solutions Using the Comparator and Comparable Interfaces

Let’s use the Comparator interface with fewer random numbers.

Example Code:

//import libraries
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
import static java.util.stream.Collectors.toCollection;

//Main
public class Main {
    public static void main(String[] args) {
        //generate random numbers
        List<Integer> list = new Random(5).ints(32L)
                             .boxed()
                             .collect(toCollection(ArrayList::new));
        //sort using lambda expression
        list.sort(logging((a,b) -> a-b));
   }//end main()

    //logging the comparisons
    static Comparator<Integer> logging(Comparator<Integer> c) {
       return (a, b) -> {
           int r = c.compare(a, b);
           System.err.printf("%,14d %,14d => %,14dn", a, b, r);
           return r;
       };
    }//end logging()
}//end class

This code is executed successfully. We are not going through all the comparisons, but we will see a few of them to confirm.

Check the following screenshot.

OUTPUT:

Let’s learn about the error-free Java code using the Comparable interface for making comparisons. To use this interface, we have to make a class containing data.

Let’s do it below.

Example Code (Students.java class):

public class Student implements Comparable<Student> {
    private String firstName;
    private String lastName;

    public Student(String firstName, String lastName){
        this.firstName = firstName;
        this.lastName = lastName;

    }

    public String getFirstName() {
        return firstName;
    }

    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }

    public String getLastName() {
        return lastName;
    }

    public void setLastName(String lastName) {
        this.lastName = lastName;
    }

    public int compareTo(Student other) {
        /*
        compare the last names and save the result
        in `compareResult` variable
        */
        int compareResult = this.lastName.compareTo(other.lastName);

        /*
        If both last names match, then it would be true means 0. So,
        dive into the `if` condition and check if the count of their
        first name matches.
        if this.count == other.count return 0
        if this.count > other.count return 1
        if this.count < other.count return -1
        */

        if(compareResult == 0){
            if(this.firstName.chars().count() ==  other.firstName.chars().count()) {
                compareResult = 0;
                return compareResult;
            }
            else if(this.firstName.chars().count() > other.firstName.chars().count()){
               compareResult = 1;
                return compareResult;
            }
            else{
                compareResult =  -1;
                 return compareResult;
            }
        }
        else{
            return compareResult;
        }
    }
}

Example Code (Main.java class):

public class Main {

    public static void main(String[] args) {
        Student std1 = new Student ("Mehvish", "Ashiq");
        Student std2 = new Student ("Mehvish", "Ashiq");
        System.out.println("Result of Comparison 1: " + std1.compareTo(std2));

        Student std3 = new Student ("Aftab", "Ashiq");
        Student std4 = new Student ("Mehvish", "Ashiq");
        System.out.println("Result of Comparison 2: " + std3.compareTo(std4));

        Student std5 = new Student ("Mehr-un-nissa", "Ashiq");
        Student std6 = new Student ("Mehvish", "Ashiq");
        System.out.println("Result of Comparison 3: " + std5.compareTo(std6));
   }
}

OUTPUT:

Result of Comparison 1: 0
Result of Comparison 2: -1
Result of Comparison 3: 1

In this code, we compare the letter count of firstName if two objects’ lastName are the same.

As we can see, the results are consistent. If a==b, a<b, and a>b, it returns 0, -1, and 1, respectively.

Comparison method violates its general contract, error can be very painful to debug. I recently encountered this issue in one of the production servers and it was only sometimes the error was thrown. Here I would discuss some cases that can lead to such an error.

Stacktrace

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:1438)
	at java.util.Arrays$ArrayList.sort(Arrays.java:3895)
	at java.util.Collections.sort(Collections.java:175)

Possible Coding Mistakes

Example 1:

In the below example the last statement in compare, return 0 is never executed and  the compare method returns 1 even if the integers are equal.

  static void sort(Integer... ints){
	    List<Integer> list = Arrays.asList(ints);
		Collections.sort(list, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				if(o1 < o2){
					return -1;
				} else if (o1 <= o2){
					return 1;
				}
				return 0;
			}
		});
		System.out.println(list);
	  
  }

 Solution :

The solution to the above example is quite simple. Change the <= to <

Example 2:

In the below example two integers being equal is completely ignored.

  static void sort(Integer... ints){
	    List<Integer> list = Arrays.asList(ints);
		Collections.sort(list, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				if(o1 < o2){
					return -1;
				} else {
					return 1;
				}
			}
		});
		System.out.println(list);
	  
  }

Solution

The solution to this issue is also simple. Add the else block for the equals also.

Example 3:

We can also have a case when a comparison is being done and something is changed by another thread at the same time.  If we have a comparison on size of a list but that list is being updated at the same time by another thread.  This case is quite hard to debug as it may fail only in very rare cases. In the below example I am updating the list while running the comparison on the same time so it also throws the contract violation error.

  static void sort(){
	    final List<List<Integer>> list = new ArrayList<>();
	    for(int i= 0 ; i < 5000;i++){
	    	list.add(new ArrayList<>());
	    }
	    
	    Executors.newSingleThreadExecutor().execute(new Runnable() {
			@Override
			public void run() {
					for(int i= 0 ; i < 5000;i++){
				    	list.get(0).add(2);
				    	list.get(21).add(2);
				    	list.get(300).add(2);
				    }
				
			}
		});
		Collections.sort(list, new Comparator<List<Integer>>() {
			@Override
			public int compare(List<Integer> o1, List<Integer> o2) {
				return Integer.compare(o1.size(), o2.size());
			}
		});
		System.out.println(list);
	  
  }

Solution

The solution to this example is not no simple. You have to make sure that the list size is not changed while the comparison is being done. It anyways doesn’t make sense to do the sorting on size because the size is changing. So even if the comparison went through without any errors, the result would not be correct.

Complete Example

Here I have created a test array that throws the error.

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Test {

	public static void main(String[] args) {
		sort(2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3);

		sort(3, 2, 3, 2, 1, 31);
		
		sort(3, 2, 2, 2, 2, 3, 2, 3, 2, 2, 3, 2, 3, 3, 2, 2, 2, 2, 2, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
				1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
				1, 1, 1, 1, 1);
		sort(1, 1, 1, 1, 1, 2, 1, 1, 1);

		sort(1,3);

	}

	static void sort(Integer... ints) {
		List<Integer> list = Arrays.asList(ints);
		Collections.sort(list, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				if (o1 < o2) {
					return -1;
				} else {
					return 1;
				}
			}
		});
		System.out.println(list);

	}
}

Output :
In the output we see that the above method doesn’t throw the exception always.So for some cases it does pass

[2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
[1, 2, 2, 3, 3, 31]
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:1438)
	at java.util.Arrays$ArrayList.sort(Arrays.java:3895)
	at java.util.Collections.sort(Collections.java:175)

public class RecipientComparator implements Comparator<Recipient> {
    @Override
    public int compare(Recipient o1, Recipient o2) {
        if (o1.isDateLastContactNull() || o2.isDateLastContactNull()) {
            if (o1.isDateLastContactNull() && o2.isDateLastContactNull()) {
                return o1.getAddress().compareTo(o2.getAddress());
            } else if (o1.isDateLastContactNull()) {
                return -1;
            } else if (o2.isDateLastContactNull()) {
                return -1;
            }
        } else {
            if (o1.getDateLastContact().equals(o2.getDateLastContact())) {
                return o1.getAddress().compareTo(o2.getAddress());
            } else
                return o1.getDateLastContact().compareTo(o2.getDateLastContact());
        }
        return 0;
    }
}

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeHi(TimSort.java:899)
    at java.util.TimSort.mergeAt(TimSort.java:516)
    at java.util.TimSort.mergeCollapse(TimSort.java:439)
    at java.util.TimSort.sort(TimSort.java:245)
    at java.util.Arrays.sort(Arrays.java:1512)
    at java.util.ArrayList.sort(ArrayList.java:1462)
    at managers.RecipientManager.getAllRecipientFromAPI(RecipientManager.java:28)
    at com.company.Main.main(Main.java:18)

package recipientPackage;

import paramPackage.Param;

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Date;

public class Recipient {
    private String recipientID;
    private String address;
    private String status;
    private int contactCount;
    private Date dateLastContact;
    Param param;
    private String[] attributes = {"recipientID", "address", "status", "contactCount", "dateLastContact"};

    Recipient(String[] recipientBrut, boolean isComeFromMailing) {
        if (isComeFromMailing) {
            createRecipientMailing(recipientBrut);
        } else {
            createRecipientSurvey(recipientBrut);
        }
    }

    public void createRecipientMailing(String[] recipientBrut) {
        this.setRecipientID(recipientBrut[0].substring(recipientBrut[0].indexOf(':') + 1).replaceAll(""", ""));
        this.setAddress(recipientBrut[1].substring(recipientBrut[1].indexOf(':') + 1).replaceAll(""", ""));
        this.setStatus(recipientBrut[3].substring(recipientBrut[3].indexOf(':') + 1).replaceAll(""", ""));

        try {
            this.setDateLastContactForMailing(recipientBrut[5].substring(recipientBrut[5].indexOf(':') + 1).replaceAll(""", ""));
            this.setContactCount(Integer.parseInt(recipientBrut[4].substring(recipientBrut[4].indexOf(':') + 1).replaceAll(""", "")));
        } catch (IndexOutOfBoundsException e) {
            this.setDateLastContactForMailing(null);
        }catch (NumberFormatException e){
            e.printStackTrace();
        }
    }

    public void createRecipientSurvey(String[] recipientBrut) {
        setAddress(recipientBrut[0]);
        setStatus(recipientBrut[1]);
        setDateLastContactForSurvey(recipientBrut[2]);
        param.setParam_point_collecte(recipientBrut[5]);
        param.setParam_langue(recipientBrut[6]);
        param.setParam_semaine(recipientBrut[7]);
        param.setParam_periode(recipientBrut[8]);
        param.setParam_envoi(recipientBrut[9]);
        param.setParam_type_visiteur(recipientBrut[10]);
        param.setParam_saison(recipientBrut[11]);
    }

    private void setDateLastContactForMailing(String dateLastContact) {
        if (dateLastContact != null) {
            SimpleDateFormat formatter = new SimpleDateFormat("yyy-MM-dd'T'HH:mm:ss");
            try {
                this.dateLastContact = formatter.parse(dateLastContact);
            } catch (ParseException e) {
                e.printStackTrace();
            }
        } else
            this.dateLastContact = null;

    }

    private void setDateLastContactForSurvey(String dateLastContact) {
        if (!dateLastContact.equals("")) {
            SimpleDateFormat formatter = new SimpleDateFormat("dd/MM/yyyy HH:mm:ss");
            try {
                this.dateLastContact = formatter.parse(dateLastContact);
            } catch (ParseException ignored) {
            }
        } else
            this.dateLastContact = null;

    }
    public Boolean isDateLastContactNull() {
        return (dateLastContact == null);
    }

    public String getRecipientID() {
        return recipientID;
    }

    public void setRecipientID(String recipientID) {
        this.recipientID = recipientID;
    }

    public String getAddress() {
        return address;
    }

    public void setAddress(String address) {
        this.address = address;
    }

    public String getStatus() {
        return status;
    }

    public void setStatus(String status) {
        this.status = status;
    }

    public int getContactCount() {
        return contactCount;
    }

    public void setContactCount(int contactCount) {
        this.contactCount = contactCount;
    }

    public Date getDateLastContact() {
        return dateLastContact;
    }

    public void setDateLastContact(Date dateLastContact) {
        this.dateLastContact = dateLastContact;
    }

    public String[] getAttributes() {
        return attributes;
    }

    public void setAttributes(String[] attributes) {
        this.attributes = attributes;
    }
}

2 ответа

Лучший ответ

public static void main(String[] args){
    Recipient r1; // with isDateLastContactNull() == true;
    Recipient r2; // with isDateLastContactNull() == false;
    RecipientComparator rc = new RecipientComparator();

    System.out.println(rc.compare(r1, r2)); // -1
    System.out.println(rc.compare(r2, r1)); // -1
    // both print -1 which is not transitive.
}

if (o1.isDateLastContactNull() && o2.isDateLastContactNull()) {
    // if both null, return comparison of addresses
    return o1.getAddress().compareTo(o2.getAddress());
} else if (o1.isDateLastContactNull()) {
    // if first null, return -1
    return -1;
} else if (o2.isDateLastContactNull()) {
    // if second null, also return -1 ?
    return -1; // should probably be 1 instead
}

} else if (o1.isDateLastContactNull()) {
    return -1;
} else if (o2.isDateLastContactNull()) {
    return -1;
}

} else if (o1.isDateLastContactNull()) {
    return -1;
} else if (o2.isDateLastContactNull()) {
    return 1;
}

Exception information

java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.util.TimSort.mergeLo(TimSort.java:747)
	at java.util.TimSort.mergeAt(TimSort.java:483)
	at java.util.TimSort.mergeCollapse(TimSort.java:410)
	at java.util.TimSort.sort(TimSort.java:214)
	at java.util.TimSort.sort(TimSort.java:173)
	at java.util.Arrays.sort(Arrays.java:659)
	at java.util.Collections.sort(Collections.java:217)
	at com.sto.customerapp.yiqianshou.servlet.CourierInfoProcess.run(CourierInfoProcess.java:77)
	at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1145)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)
	at java.lang.Thread.run(Thread.java:745)

Cause Analysis

The algorithm of Array.sort has been modified in JDK1.7. Instead of using the previous MergeSort, the new TimeSort is used, which satisfies the following three characteristics:
1) Reflexivity: The comparison result of x, y is opposite to the comparison result of y, x.
2) Transitive: x>y, y>z, then x>z.
3) Symmetry: x=y, then the x,z comparison result is the same as the y,z comparison.

java.util.Arrays#sort(T[], java.util.Comparator<? super T>)

public static <T> void sort(T[] a, Comparator<? super T> c) {
	  if (LegacyMergeSort.userRequested)
	       legacyMergeSort(a, c);
	   else
	       TimSort.sort(a, c);
}

solution

• The ComparatorTool class, rewriting the Comparator’s compare method is considered comprehensive

public class ComparatorTool implements Comparator<CourierInfo> {
    SimpleDateFormat format = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");

    @Override
    public int compare(CourierInfo t1, CourierInfo t2) {
        if ((t1==null && t2==null) ||
                (StringUtils.isBlank(t1.getSignTime()) && StringUtils.isBlank(t2.getSignTime()))){
            return 0;
        }
        if(t1==null || StringUtils.isBlank(t1.getSignTime())){
            return 1;
        }
        if(t2==null || StringUtils.isBlank(t2.getSignTime())){
            return -1;
        }
        Date d1, d2;
        try {
            d1 = format.parse(t1.getSignTime());
            d2 = format.parse(t2.getSignTime());
        } catch (Throwable e) {
            // parsing error, no sorting
            return 0;
        }
        return d2.compareTo(d1);
    }

}

• Business method call

List<CourierInfo> courierInfoList = courierInfoConfig.getCourierInfoService().listCourierInfoList(courierInfoMap);
ComparatorTool c = new ComparatorTool();
// Sort by time
Collections.sort(courierInfoList, c);

Overview

Today, I want to share a bug fixing experience on
java.util.Comparator.
In our production environment, there is an error that happens frequently.
It happens so often that it is actually spamming the logs, so I decided to fix
it. After reading this article, you will understand:

• How to identify the problem?
• How to translate it mathematically?
• How to test the comparator?
• How to fix it?

Let’s begin 🙂

Identify Problem

In the stacktrace, there is an exception logged as follows:

Caused by: 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:439)
	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 com.nuxeo.connect.track.NuxeoConnectProfileImpl$1ProfileExtractorRunner.run(NuxeoConnectProfileImpl.java:165)

As mentioned in book “Effective Java, 2nd Edition”, Item 12: “… a compareTo
method must obey the same restrictions imposed by the equals contract:
reflexivity, symmetry, and transitivity.” Therefore, I need to check if they
are respected in the source code. Let’s have an example for transitivity. Let
A be the first object, B the second and C the third object. If A > B
and B > C, then A > C must be respected. Otherwise, the comparison method
violates its general contract.

In order to check that, I searched in the source code. Then I found the
comparator, written as a lambda. As you can see, the logic is very complex.
It’s almost impossible to find the cause in such situation. I tried to find a
counterexample to prove the incorrectness, but after one hour attempts with 5
different combinations, I still couldn’t find anything. So I gave up at the end.
I decided to try something else: divide the problem into sub-problems

Collections.sort(projects, (p1, p2) -> {
  try {
    Service s1 = p1.getAssociatedServiceByType(session, Service.BASE_TYPE);
    Service s2 = p2.getAssociatedServiceByType(session, Service.BASE_TYPE);
    if (s1 != null && s2 != null) {
      Calendar exp1 = s1.getEndDate();
      Calendar exp2 = s2.getEndDate();

      if (s1.isServiceValid() && s2.isServiceValid()) {
        // project with the first expiring subscription comes first
        return ObjectUtils.compare(exp1, exp2, true);
      } else {
        if (!s1.isServiceValid() && s2.isServiceValid()) {
          return 1;
        } else if (s1.isServiceValid() && !s2.isServiceValid()) {
          return -1;
        }
      }
    }
    // both projects are invalid or at least one has no BASE MAINTENANCE service associated
    Calendar d1 = (Calendar) p1.getDoc().getPropertyValue("dc:created");
    Calendar d2 = (Calendar) p2.getDoc().getPropertyValue("dc:created");
    // project with the last creation date comes first
    return ObjectUtils.compare(d2, d1, true);
  } catch (RuntimeException e) {
    logger.warn("Unable to compare projects, considering equal", e);
    return 0;
  }
})

Find Fields in Comparator

In the existing implementation, we didn’t respect transitivity. When there are
multiple fields to compare, we should compare the next field if and only if the
current field is equal in both object 1 and object 2. But first of all, let’s
find out the different fields as comparison order:

1. Service existence
2. Service validity
3. Service expiration date
4. Project creation date

In each field, there are different values to be filled. For service existence,
it can be existing or non-existent. For service validity, it can be either valid
or invalid. For service expiration date, it can be null, an earlier date, or a
later date. For project creation date, it can be null, an earlier date, or a
later date. So, there are actually 36 combinations:

2 * 2 * 3 * 3 = 36
|   |   |   |
|   |   |   |
|   |   |   +-- Project created date (0: null, 1: early, 2: late)
|   |   +------ Service expired date (0: null, 1: early, 2: late)
|   +---------- Service validity     (0: True, 1: False)
+-------------- Service existence    (0: null, 1: defined)

Reproduce Bug in Test

The next step is to reproduce the exception in unit test. In order to do that,
there are the following conditions:

1. Use something to represent the combination
2. Create a dataset having all the 36 combinations based on that representation
3. Randomly permutes the dataset
4. Sort the dataset to reproduce the bug

Preparation: replace lambda by static nested class. Replace lambda by static
nested class, it helps us the create test easily, without having the need to
prepare everything in the outer class.

// before
Collections.sort(projects, (p1, p2) -> { ... });

// after
projects.sort(new ProjectComparator(session));

Represent the combination.
For the 1st point, I thought about different solutions and finally chose array
as data structure. An integer array int[] with 4 items allows to store the
state of 4 fields. It can be initialized as:

int[] mode = { 0, 0, 0, 0 };

Thanks to this data structure, we can easily compute all the different
combinations, via a method for incrementation. It should look like the decimal
system, but here digits can only be in range of 0-1 or 0-2. Here’s how it is
used and how it is implemented:

int mode = { 0, 0, 0, 0 };
for (int i = 0; i < 36; i++) {
  // translate to Java
  ...
  mode = increment(mode);
}

private static int[] increment(int[] mode) {
  int[] newMode = Arrays.copyOf(mode, mode.length);
  boolean carry = false;
  newMode[0]++;
  if (newMode[0] > 1) {
    newMode[0] = 0;
    carry = true;
  }
  if (carry) {
    newMode[1]++;
    if (newMode[1] > 1) {
      newMode[1] = 0;
      carry = true;
    } else {
      carry = false;
    }
  }
  if (carry) {
    newMode[2]++;
    if (newMode[2] > 2) {
      newMode[2] = 0;
      carry = true;
    } else {
      carry = false;
    }
  }
  if (carry) {
    newMode[3]++;
  }
  return newMode;
}

Create dataset.
For the 2nd point, since we have mode, we can translate this mathematical
representation into actual Java state. As you can see, the comparator did a lot
of things. It uses a session object to perform a database lookup, and has a
underlying document model, retrieved via method Project#getDoc(). In order to
create the dataset, we need to mock these exchanges.

Here, I used Mockito as the mocking framework, because it is already a
dependency in our codebase, and it’s quite easy to understand.

// mock classes
Project project = mock(Project.class);
Service service = mock(Service.class);
DocumentModel document = mock(DocumentModel.class);

// stubbing before then actual execution
when(service.getEndDate()).thenReturn(/* TODO: fill state here */);
when(project.getDoc()).thenReturn(document);
...

So we saw how the implementation is done for each individual combination in
combinations.

List<Project> projects = new ArrayList();
int mode = { 0, 0, 0, 0 };
for (int i = 0; i < 36; i++) {
  // mock goes here:
  // math -> Java
  ...
  projects.add(p);
  mode = increment(mode);
}

Randomly permutes the dataset. Having a dataset is not enough. We still need
to permute the list to ensure each two items can be used by comparator and will
raise exception because some pairs violate the general contract. This can be
done using method
java.util.Collections#shuffle(List<?>).
Repeat the shuffle operation for 10,000 times to a high probability of
having the exception:

Comparator<Project> comparator = new ProjectComparator(session);
for (int i = 0; i < 10_000; i++) {
  Collections.shuffle(projects);
  projects.sort(comparator); // exception?
}

Sorting to raise exception. After “shuffle” operation, sort the projects
again. Exception should be thrown — and should be fixed once the implementation
is fixed.

Fix Comparator

Fixing the field comparison order as mentioned above, solves the problem:

1. Service existence
2. Service validity
3. Service expiration date
4. Project creation date

Here is the code:

static class ProjectComparator implements Comparator<Project> {

  private final CoreSession session;

  ProjectComparator (CoreSession session) {
    this.session = session;
  }

  /**
   * Comparing:
   * <ol>
   * <li>Service existence (nullability)</li>
   * <li>Service validity</li>
   * <li>Service expiration date</li>
   * <li>Project creation date</li>
   * </ol>
   */
  @Override
  public int compare(Project p1, Project p2) {
    try {
      Service s1 = p1.getAssociatedServiceByType(session, Service.BASE_TYPE);
      Service s2 = p2.getAssociatedServiceByType(session, Service.BASE_TYPE);
      boolean hasS1 = s1 != null;
      boolean hasS2 = s2 != null;

      if (hasS1 != hasS2) {
        return hasS1 ? -1 : 1;
      }
      if (!hasS1) { // stop here to avoid NPE
        return 0;
      }
      if (s1.isServiceValid() != s2.isServiceValid()) {
        return s1.isServiceValid() ? -1 : 1;
      }
      if (s1.isServiceValid() && s2.isServiceValid()) {
        // project with the first expiring subscription comes first
        Calendar exp1 = s1.getEndDate();
        Calendar exp2 = s2.getEndDate();
        return ObjectUtils.compare(exp1, exp2, true);
      }
      // both projects are invalid
      Calendar d1 = (Calendar) p1.getDoc().getPropertyValue("dc:created");
      Calendar d2 = (Calendar) p2.getDoc().getPropertyValue("dc:created");
      // project with the last creation date comes first
      return ObjectUtils.compare(d2, d1, true);
    } catch (RuntimeException e) {
      logger.warn("Unable to compare projects, considering equal", e);
      return 0;
    }
  }
}

The test passed. o(〃＾▽＾〃)o

Obviously, it’s not normal that the comparator contains so many logic here, and
should be refactored as the next step… But for now, at least the problem is
fixed.

Conclusion

Let’s do a recap of what have been discussed here. There was a problem about
sorting, due to incorrect implementation of a comparator. The problem was not
easy to be identified, and was finally identified by method of exhaustion —
listing all the combinations, shuffle then sort, and repeat 10,000 times. The
solution was to compare all fields properly, by comparing fields one after
another. Hope you enjoy this article, see you the next time!

References

• Mockito, “Mockito framework site”, Mockito, 2019.
  https://site.mockito.org/
• Oracle, “Comparator (Java Platform SE 8)”, Java Documentation, 2019.
  https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html
• Oracle, “Collections (Java Platform SE 8)”, Java Documentation, 2019.
  https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html
• Joshua Bloch, “Effective Java (Second Edition)”, Addison Wesley, 2015. [Book]