"Comparison method violates its general contract!" - TimSort and GridLayout

Question

I made a color palette with a jPanel and a JLabel array in it. At first it worked well, but then i put some other jLabels out of the JPanel and added them some events. Now I keep getting this error:

Exception in thread "AWT-EventQueue-0" 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 javax.swing.SortingFocusTraversalPolicy.enumerateAndSortCycle(SortingFocusTraversalPolicy.java:136)
at javax.swing.SortingFocusTraversalPolicy.getFocusTraversalCycle(SortingFocusTraversalPolicy.java:110)
at javax.swing.SortingFocusTraversalPolicy.getFirstComponent(SortingFocusTraversalPolicy.java:435)
at javax.swing.LayoutFocusTraversalPolicy.getFirstComponent(LayoutFocusTraversalPolicy.java:166)
at javax.swing.SortingFocusTraversalPolicy.getDefaultComponent(SortingFocusTraversalPolicy.java:515)
at java.awt.FocusTraversalPolicy.getInitialComponent(FocusTraversalPolicy.java:169)
at java.awt.DefaultKeyboardFocusManager.dispatchEvent(DefaultKeyboardFocusManager.java:380)
at java.awt.Component.dispatchEventImpl(Component.java:4731)
at java.awt.Container.dispatchEventImpl(Container.java:2287)
at java.awt.Window.dispatchEventImpl(Window.java:2719)
at java.awt.Component.dispatchEvent(Component.java:4687)
at java.awt.EventQueue.dispatchEventImpl(EventQueue.java:723)
at java.awt.EventQueue.access$200(EventQueue.java:103)
at java.awt.EventQueue$3.run(EventQueue.java:682)
at java.awt.EventQueue$3.run(EventQueue.java:680)
at java.security.AccessController.doPrivileged(Native Method)
at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDomain.java:76)
at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDomain.java:87)
at java.awt.EventQueue$4.run(EventQueue.java:696)
at java.awt.EventQueue$4.run(EventQueue.java:694)
at java.security.AccessController.doPrivileged(Native Method)
at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDomain.java:76)
at java.awt.EventQueue.dispatchEvent(EventQueue.java:693)
at java.awt.SequencedEvent.dispatch(SequencedEvent.java:116)
at java.awt.EventQueue.dispatchEventImpl(EventQueue.java:721)
at java.awt.EventQueue.access$200(EventQueue.java:103)
at java.awt.EventQueue$3.run(EventQueue.java:682)
at java.awt.EventQueue$3.run(EventQueue.java:680)
at java.security.AccessController.doPrivileged(Native Method)
at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDomain.java:76)
at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDomain.java:87)
at java.awt.EventQueue$4.run(EventQueue.java:696)
at java.awt.EventQueue$4.run(EventQueue.java:694)
at java.security.AccessController.doPrivileged(Native Method)
at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDomain.java:76)
at java.awt.EventQueue.dispatchEvent(EventQueue.java:693)
at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:244)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:163)
at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:151)
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:147)
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:139)
at java.awt.EventDispatchThread.run(EventDispatchThread.java:97)

I tried to remove everything i've done after first time i got this error, but still keep getting it. When i change the layout from GridLayout to anything else, then the error disappears, but the code becomes useless. So i need GridLayout. When i move everything in that JPanel to another JPanel, the error also goes away. But when i remove the first JPanel, error comes back.

By the way, the program works, but it's not pleasent to keep getting errors...

Edit: When i use less than 225 color, there's no error. I'm really curious about what's happening. Any explanation would be appreciated...

Finzer

See this: #7850039 – Ezechiel

Note that this is not a bug, but the removal of a loophole. The loophole was that the comparator used to sort arrays could contain an undetected logic error. With Java 7 a check has been added, and this check now output this error if the comparator has a wrong behavior. As this could create problems (though this resolves other), Java 7 includes a property to force the arrays to use the previous method (no comparator verification). Don't expect this message to disappear with newer releases of Java. Library developers must fix this in their code. – Tottering

Answer 1

It seems to me like you've hit a bug in the JDK since the error seems to come from Swing classes.

Options:

1. Define the property java.util.Arrays.useLegacyMergeSort as true. Either using in your code the line

   System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
   

   before any Swing code. As the first line in the main method should work.

   Or adding

   -Djava.util.Arrays.useLegacyMergeSort=true
   

   to your starting options (in the console, or in the project properties in an IDE, Ant script, etc.)

2. Upgrade your JDK and see if the problem goes away

3. Downgrade to Java 6

Fredelia

That is dependant in how are you running your application. Command line? Netbeans, Eclipse or some other IDE? – Fredelia

A general option would be to add System.setProperty("java.util.Arrays.useLegacyMergeSort", "true"); as the first line in your main method. – Fredelia

I am hitting this with 1.7.0_17-b02, which is the latest version as of this writing, so it seems that this bug hasn't been fixed yet. And setting the java.util.Arrays.useLegacyMergeSort system property to true indeed gets me around the problem. – Intellectualism

I hit this in a non-Swing application! Happened trying to establish a Topic connection to a JMS queue using the IBM MQ libraries – Subterfuge

@Finzer For eclipse you need to edit your run configuration which starts you application. Click on "Run -> Run configurations..." menu, selected your application execution configuration on the left hand side, select "Arguments" tab and add "-Djava.util.Arrays.useLegacyMergeSort=true" to "VM arguments" text box. – Albur

Answer 2

Report my findings:

-Djava.util.Arrays.useLegacyMergeSort=true

works

but

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

does not work.

It is due to the fact that in JDK Arrays.class

 static final class LegacyMergeSort {
    private static final boolean userRequested = ...

It is a static variable which is defined when jvm starts. Setting System property in the program will have no effect if the class has been loaded into jvm.

I have beeing monitoring the LegacyMergeSort.userRequested variable, and the findings confirmed with above statement.

Update: The program must set system properties before java.util.Arrays is loaded to classloader. Otherwise, once it is loaded, setting the properties is not going to be useful due to the reason mentioned above.

Make sure nothing else loaded Arrays.class:

By putting following code to your program to test:

    java.lang.reflect.Method m = ClassLoader.class.getDeclaredMethod("findLoadedClass", new Class[] { String.class });
    m.setAccessible(true);
    ClassLoader cl = ClassLoader.getSystemClassLoader();
    Object test1 = m.invoke(cl, "java.util.Arrays");
    System.out.println("test1 loaded? ->" + (test1 != null));

Sinclair

Answer 3

[Update] This solution unfortunately is not guaranteed to solve the problem in all cases. It is not enough to patch the default SortingFocusTraversalPolicy of the KeyboardFocusManager.

I recommend to read the answer by Robin Loxley below, including his Update. [/Update]

java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeHi(TimSort.java:868)

This problem is caused by a bug in javax.swing.LayoutComparator.

The following class installs a fixed version of javax.swing.LayoutComparator, which does not violate the contract of Comparator<Component>. This (or any other) fixed version of javax.swing.LayoutComparator should be submitted to Oracle by some Oracle contributor.

package ...;

import java.awt.Component;
import java.awt.ComponentOrientation;
import java.awt.FocusTraversalPolicy;
import java.awt.KeyboardFocusManager;
import java.awt.Window;
import java.lang.reflect.Field;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.ListIterator;

import javax.swing.JRootPane;
import javax.swing.SortingFocusTraversalPolicy;
import javax.swing.UIManager;

/**
 * Uses reflection to install a fixed version of {@link javax.swing.LayoutComparator} to solve the
 * LayoutFocusTraversalPolicy/TimSort problem.
 * 
 * <p>
 * <code>java.lang.IllegalArgumentException: Comparison method violates its general contract!</code>
 * <br/>
 * &nbsp;&nbsp;&nbsp;&nbsp;{@code     at java.util.TimSort.mergeHi(TimSort.java:868)}
 * </p>
 * <p>
 * Usage: call {@code Class.forName(LayoutFocusTraversalPolicyTimSortBugFixer.class.getName())}
 * before creating Swing components.
 * </p>
 * 
 * @author Burkhard Strauss
 * @since Feb 2015
 */
public class LayoutFocusTraversalPolicyTimSortBugFixer
{

   static
   {
      UIManager.getUI(new JRootPane()); // make Swing install the SortingFocusTraversalPolicy
      final KeyboardFocusManager keyboardFocusManager = KeyboardFocusManager
            .getCurrentKeyboardFocusManager();
      final FocusTraversalPolicy focusTraversalPolicy = keyboardFocusManager
            .getDefaultFocusTraversalPolicy();
      boolean fixed = false;
      if (focusTraversalPolicy instanceof SortingFocusTraversalPolicy)
      {
         try
         {
            final Field field = SortingFocusTraversalPolicy.class.getDeclaredField("comparator");
            final boolean accessible = field.isAccessible();
            try
            {
               field.setAccessible(true);
               field.set(focusTraversalPolicy, new LayoutComparator());
               fixed = true;
            }
            finally
            {
               field.setAccessible(accessible);
            }

         }
         catch (final Exception e)
         {
         }
      }
      if (!fixed)
      {
         Loggers.getLoggerFor(LayoutFocusTraversalPolicyTimSortBugFixer.class).warn("could not fix the bug");
      }
   }

   /**
    * Fixed version of {@link javax.swing.LayoutComparator}.
    * <p>
    * Search for 'bugfix' in the code.
    * </p>
    * 
    * @author Burkhard Strauss
    * @since Feb 2015
    */
   @SuppressWarnings("serial")
   private static class LayoutComparator implements Comparator<Component>, java.io.Serializable
   {

      private static final int ROW_TOLERANCE = 10;

      private boolean horizontal = true;
      private boolean leftToRight = true;

      @SuppressWarnings("unused")
      void setComponentOrientation(final ComponentOrientation orientation)
      {
         horizontal = orientation.isHorizontal();
         leftToRight = orientation.isLeftToRight();
      }

      @Override
      public int compare(Component a, Component b)
      {
         if (a == b)
         {
            return 0;
         }

         // Row/Column algorithm only applies to siblings. If 'a' and 'b'
         // aren't siblings, then we need to find their most inferior
         // ancestors which share a parent. Compute the ancestory lists for
         // each Component and then search from the Window down until the
         // hierarchy branches.
         if (a.getParent() != b.getParent())
         {
            final LinkedList<Component> aAncestory = new LinkedList<Component>();
            for (; a != null; a = a.getParent())
            {
               aAncestory.add(a);
               if (a instanceof Window)
               {
                  break;
               }
            }
            if (a == null)
            {
               // 'a' is not part of a Window hierarchy. Can't cope.
               throw new ClassCastException();
            }
            final LinkedList<Component> bAncestory = new LinkedList<Component>();
            for (; b != null; b = b.getParent())
            {
               bAncestory.add(b);
               if (b instanceof Window)
               {
                  break;
               }
            }
            if (b == null)
            {
               // 'b' is not part of a Window hierarchy. Can't cope.
               throw new ClassCastException();
            }
            for (ListIterator<Component> aIter = aAncestory.listIterator(aAncestory.size()), bIter = bAncestory
                  .listIterator(bAncestory.size());;)
            {
               if (aIter.hasPrevious())
               {
                  a = aIter.previous();
               }
               else
               {
                  // a is an ancestor of b
                  return -1;
               }
               if (bIter.hasPrevious())
               {
                  b = bIter.previous();
               }
               else
               {
                  // b is an ancestor of a
                  return 1;
               }
               if (a != b)
               {
                  break;
               }
            }
         }

         final int ax = a.getX(), ay = a.getY(), bx = b.getX(), by = b.getY();
         int zOrder = a.getParent().getComponentZOrder(a) - b.getParent().getComponentZOrder(b);
         {
            //
            // Here is the bugfix:
            // Don't return 0 if a != b. This would violate the contract of
            // Comparator<Component>.compare().
            //
            if (zOrder == 0)
            {
               zOrder = -1;
            }
         }
         if (horizontal)
         {
            if (leftToRight)
            {

               // LT - Western Europe (optional for Japanese, Chinese, Korean)

               if (Math.abs(ay - by) < ROW_TOLERANCE)
               {
                  return (ax < bx) ? -1 : ((ax > bx) ? 1 : zOrder);
               }
               else
               {
                  return (ay < by) ? -1 : 1;
               }
            }
            else
            { // !leftToRight

               // RT - Middle East (Arabic, Hebrew)

               if (Math.abs(ay - by) < ROW_TOLERANCE)
               {
                  return (ax > bx) ? -1 : ((ax < bx) ? 1 : zOrder);
               }
               else
               {
                  return (ay < by) ? -1 : 1;
               }
            }
         }
         else
         { // !horizontal
            if (leftToRight)
            {

               // TL - Mongolian

               if (Math.abs(ax - bx) < ROW_TOLERANCE)
               {
                  return (ay < by) ? -1 : ((ay > by) ? 1 : zOrder);
               }
               else
               {
                  return (ax < bx) ? -1 : 1;
               }
            }
            else
            { // !leftToRight

               // TR - Japanese, Chinese, Korean

               if (Math.abs(ax - bx) < ROW_TOLERANCE)
               {
                  return (ay < by) ? -1 : ((ay > by) ? 1 : zOrder);
               }
               else
               {
                  return (ax > bx) ? -1 : 1;
               }
            }
         }
      }
   }
}

Shaughnessy

Answer 4

I just ran into the same error and spent a good amount of time tracking it down. To help others who run into this error it is important to know how to test TimSort. The checks that violate the transitivity contract and throw this error are deep in the algorithm and require a test to meet certain criteria before this problem can be reproduced.

1. Create a list with 32 or more objects.
2. Within that list, there needs to two or more runs.
3. Each run must contain 3 or more objects.

Once you meet those two criteria you can begin testing for this failure.

A run is defined as a sub-set of the list where each item is already in the desired ordered state.

Loesch

Answer 5

It is not enough to patch LayoutComparator as suggerested above. This fix does not work in my case. The issue was fixed in JDK 8 (8u45 at least). SortingFocusTraversalPolicy to use legacy Merge Sort Method.

Rambow

Answer 6

There is nothing wrong with the JDK. I was facing the same issue since 2 days & finally got to know that bug was with my date-format. In my API response few dates were in "dd-MM-yyyy HH:mm" format while few of them were in "dd/MM/yyyy HH:mm" format.

Same issue while comparing integers, May be your List is having some null values.

Here is my code, which is working like a charm

Collections.sort(root_array, new Comparator<RootResponseItem>(){
                            public int compare(RootResponseItem o1, RootResponseItem o2){
                                Date date1 = new Date();
                                String dtStart = o1.getSectors().get(0).getDeparture().getDate() + " " + o1.getSectors().get(0).getDeparture().getTime();
                                dtStart = dtStart.replaceAll("-","/");
                                SimpleDateFormat format = new SimpleDateFormat("dd/MM/yyyy HH:mm");
                                try {
                                    date1 = format.parse(dtStart);
                                } catch (ParseException e) {
                                    e.printStackTrace();
                                }

                                Date date2 = new Date();
                                String dtStart2 = o2.getSectors().get(0).getDeparture().getDate() + " " + o2.getSectors().get(0).getDeparture().getTime();
                                dtStart2 = dtStart2.replaceAll("-","/");
                                SimpleDateFormat format2 = new SimpleDateFormat("dd/MM/yyyy HH:mm");
                                try {
                                    date2 = format2.parse(dtStart2);
                                } catch (ParseException e) {
                                    e.printStackTrace();
                                }

                                return date1.compareTo(date2);
                            }
                        });

Unjust