Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8177443

exception thrown from Arrays.sort comparator might lose elements

    Details

      Description

      FULL PRODUCT VERSION :
      java version "1.8.0_121"
      Java(TM) SE Runtime Environment (build 1.8.0_121-b13)
      Java HotSpot(TM) 64-Bit Server VM (build 25.121-b13, mixed mode)


      ADDITIONAL OS VERSION INFORMATION :
      Ubuntu 16.04 x64 - Linux james-ubuntu 4.4.0-66-generic #87-Ubuntu SMP Fri Mar 3 15:29:05 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux

      Microsoft Windows [Version 10.0.14393]


      A DESCRIPTION OF THE PROBLEM :
      After calling Collections.sort the collection may contain different elements. This occurs if the Comparator used throws an exception while TimSort is performing a merge (an example stack is output by the example code).

      This cause the merge to fail and results in elements in the collection being duplicated while others are lost. The length of the collection is correctly maintained.

      This was found while investigating a test failure in Jython. More details can be found on the ticket http://bugs.jython.org/issue2399

      REGRESSION. Last worked in version 7u80

      ADDITIONAL REGRESSION INFORMATION:
      java version "1.7.0_80"
      Java(TM) SE Runtime Environment (build 1.7.0_80-b15)
      Java HotSpot(TM) 64-Bit Server VM (build 24.80-b11, mixed mode)


      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      Run the example code provided

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      The example code should produce the following output:

      After sort distinct elements: 128

      ACTUAL -
      The example code produces the following output:

      After sort distinct elements: 126

      Indicating elements have been lost while others are duplicated.

      REPRODUCIBILITY :
      This bug can be reproduced always.

      ---------- BEGIN SOURCE ----------
      import java.util.ArrayList;
      import java.util.Collections;
      import java.util.Comparator;
      import java.util.HashSet;
      import java.util.List;

      public class TestSort {

          private static class Complains {
              public final int i;
              
              public Complains(int i) {
                  this.i = i;
              }

              @Override
              public String toString() {
                  return "Complains(" + i + ")";
              }
          }

          private static class ComplainsComparator implements Comparator<Complains> {
              @Override
              public int compare(Complains o1, Complains o2) {
                  // Values chosen to fail when TimSort is in the mergeLo function
                  if (o1.i == 30 && o2.i == 43) {
                      System.out.println("Throwing exception");
                      throw new RuntimeException();
                  }
                  return o1.i < o2.i ? -1 : 1;
              }
          }

          public static void main(String[] args) {
              List<Complains> complainsList= new ArrayList<>(128);

              int[] nums = new int[]{50, 84, 104, 51, 75, 15, 66, 43, 17, 70, 74, 60, 113, 91, 71, 56, 76, 24, 123, 30, 28, 69, 96, 58, 109, 36, 32, 57, 79, 46, 67, 99, 72, 93, 101, 63, 126, 48, 65, 10, 78, 12, 119, 115, 53, 11, 33, 87, 114, 118, 44, 3, 100, 19, 27, 122, 121, 39, 25, 22, 2, 54, 16, 52, 124, 61, 13, 88, 0, 47, 40, 116, 98, 81, 6, 102, 35, 31, 73, 105, 77, 5, 23, 20, 7, 117, 107, 106, 42, 1, 21, 29, 8, 82, 95, 111, 14, 26, 85, 108, 97, 45, 80, 38, 64, 41, 9, 59, 62, 127, 110, 125, 90, 92, 120, 34, 83, 4, 49, 103, 68, 94, 55, 112, 18, 37, 86, 89};

              for (int i : nums) {
                  complainsList.add(new Complains(i));
              }

              System.out.println("Before sort:" + complainsList);
              System.out.println("Before sort list size: " + complainsList.size());
              System.out.println("Before sort distinct elements: " + new HashSet<>(complainsList).size());

              try {
                  System.out.println("Do sort");
                  Collections.sort(complainsList, new ComplainsComparator());
              }
              catch (Exception e) {
                  e.printStackTrace();
              }

              System.out.println("After sort" + complainsList);
              System.out.println("After sort list size: " + complainsList.size());
              System.out.println("After sort distinct elements: " + new HashSet<>(complainsList).size());
          }
      }

      ---------- END SOURCE ----------

      CUSTOMER SUBMITTED WORKAROUND :
      You can disable TimSort by setting the system property -Djava.util.Arrays.useLegacyMergeSort=true

        Attachments

          Activity

            People

            • Assignee:
              smarks Stuart Marks
              Reporter:
              webbuggrp Webbug Group
            • Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

              • Created:
                Updated: