JDK-8048887 : SortingFocusTraversalPolicy throws IllegalArgumentException from the sort method
  • Type: Bug
  • Component: client-libs
  • Sub-Component: javax.swing
  • Affected Version: 7,8,9
  • Priority: P3
  • Status: Resolved
  • Resolution: Fixed
  • OS: generic
  • CPU: generic
  • Submitted: 2014-07-01
  • Updated: 2016-02-15
  • Resolved: 2014-07-04
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availabitlity Release.

To download the current JDK release, click here.
JDK 7 JDK 8 JDK 9
7u72Resolved 8u40Resolved 9 b24Fixed
Related Reports
Duplicate :  
Relates :  
Relates :  
Relates :  
Relates :  
Description
SortingFocusTraversalPolicy uses ROW_TOLERANCE conception to alter a disposition of components in a focus cycle for the sake of visually more appropriate traversal order. This however breaks the transitivity rule, which in case of using the default tim-sort algo leads to an exception:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.util.TimSort.mergeHi(TimSort.java:895)
	at java.util.TimSort.mergeAt(TimSort.java:512)
	at java.util.TimSort.mergeForceCollapse(TimSort.java:453)
	at java.util.TimSort.sort(TimSort.java:250)
	at java.util.Arrays.sort(Arrays.java:1512)
	at java.util.ArrayList.sort(ArrayList.java:1466)
	at java.util.Collections.sort(Collections.java:175)
	at javax.swing.SortingFocusTraversalPolicy.enumerateAndSortCycle(SortingFocusTraversalPolicy.java:172)
	at javax.swing.SortingFocusTraversalPolicy.getFocusTraversalCycle(SortingFocusTraversalPolicy.java:143)
	at javax.swing.SortingFocusTraversalPolicy.getFirstComponent(SortingFocusTraversalPolicy.java:500)
	at javax.swing.LayoutFocusTraversalPolicy.getFirstComponent(LayoutFocusTraversalPolicy.java:167)
	at javax.swing.SortingFocusTraversalPolicy.getDefaultComponent(SortingFocusTraversalPolicy.java:590)
	at java.awt.FocusTraversalPolicy.getInitialComponent(FocusTraversalPolicy.java:169)
	at java.awt.DefaultKeyboardFocusManager.dispatchEvent(DefaultKeyboardFocusManager.java:420)
	at java.awt.Component.dispatchEventImpl(Component.java:4760)
	at java.awt.Container.dispatchEventImpl(Container.java:2302)
	at java.awt.Window.dispatchEventImpl(Window.java:2739)
	at java.awt.Component.dispatchEvent(Component.java:4711)
	at java.awt.EventQueue.dispatchEventImpl(EventQueue.java:751)
	at java.awt.EventQueue.access$500(EventQueue.java:97)
	at java.awt.EventQueue$3.run(EventQueue.java:702)
	at java.awt.EventQueue$3.run(EventQueue.java:696)
	at java.security.AccessController.doPrivileged(Native Method)
	at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDomain.java:75)
	at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDomain.java:86)
	at java.awt.EventQueue$4.run(EventQueue.java:724)
	at java.awt.EventQueue$4.run(EventQueue.java:722)
	at java.security.AccessController.doPrivileged(Native Method)
	at java.security.ProtectionDomain$1.doIntersectionPrivilege(ProtectionDomain.java:75)
	at java.awt.EventQueue.dispatchEvent(EventQueue.java:721)
	at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:190)
	at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:115)
	at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:104)
	at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:100)
	at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:92)
	at java.awt.EventDispatchThread.run(EventDispatchThread.java:81)

Run the following test case to reproduce it:

import java.awt.*;

import javax.swing.*;

public class TestLayoutBug extends JFrame
{
  private static TestLayoutBug dia;
  
  private static int[] Xs = new int[] {71, 23, 62, 4, 79, 39, 34, 9, 84, 58, 30, 34, 38, 15, 69, 10, 44, 95, 70, 54,
    44, 62, 77, 64, 70, 83, 31, 48, 96, 54, 40, 3, 60, 58, 3, 20, 94, 54, 26, 19, 48, 47, 12, 70, 86, 43, 71, 97, 19,
    69, 90, 22, 43, 76, 10, 60, 29, 49, 9, 9, 15, 73, 85, 80, 81, 35, 87, 43, 17, 57, 38, 44, 29, 86, 96, 15, 57, 26,
    27, 78, 26, 87, 43, 6, 4, 16, 57, 99, 32, 86, 96, 5, 50, 69, 12, 4, 36, 84, 71, 60, 22, 46, 11, 44, 87, 3, 23, 14,
    43, 25, 32, 44, 11, 18, 77, 2, 51, 87, 88, 53, 69, 37, 14, 10, 25, 73, 39, 33, 91, 51, 96, 9, 74, 66, 70, 42, 72,
    7, 82, 40, 91, 33, 83, 54, 33, 50, 83, 1, 81, 32, 66, 11, 75, 56, 53, 45, 1, 69, 46, 31, 79, 58, 12, 20, 92, 49,
    50, 90, 33, 8, 43, 93, 72, 78, 9, 56, 84, 60, 30, 39, 33, 88, 84, 56, 49, 47, 4, 90, 57, 6, 23, 96, 37, 88, 22, 79,
    35, 80, 45, 55};

  public TestLayoutBug()
  {
    JPanel panel = new JPanel(new GridBagLayout());
    GridBagConstraints gbc = new GridBagConstraints();
    for (int i=0; i < Xs.length; i++) {
      gbc.gridx = Xs[i];
      gbc.gridy = 100-gbc.gridx;
      panel.add(new MyComponent(), gbc);
    }
    getRootPane().getContentPane().add(panel);
    pack();
    setDefaultCloseOperation(EXIT_ON_CLOSE);
  }
  
  public static void main(String[] args) throws Exception
  {
    //System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
    SwingUtilities.invokeLater(new Runnable() {

      @Override
      public void run()
      {
        dia = new TestLayoutBug();
        dia.setVisible(true);
      }
    });
  }

  public static class MyComponent extends JPanel
  {
    private final static Dimension SIZE = new Dimension(1,1);
    
    public MyComponent()
    {
      setBackground(Color.BLACK);
      setOpaque(true);
    }

    @Override
    public Dimension getPreferredSize()
    {
      return SIZE;
    }
  }
}

Comments
The following fix calls the legacy merge-sort method via reflection: http://cr.openjdk.java.net/~ant/JDK-8048887/webrev.0/ I've tested it against performance in the following way. In a jframe I was adding up to 10.000 components a) at random location (with frame's null Layout) so that to completely untie traversal order from container order (hard case for the sort), and b) sequentially, so that to have the traversal order pre-sorted. Then I counted time spent in the sorting procedure. The results of the legacy merge-sort and the default tim-sort were pretty close. So, the fallback to the legacy sorting algo shouldn't hit performance for Swing. Just for the case of any unpredictable issue (and for the testing purpose), I left an ability to switch to the default tim-sort via setting the (undocumented) "swing.legacySortingFTPEnabled" property to false.
2014-07-01