changeset 51397:3a6d47df8239

8203864: Execution error in Java's Timsort Reviewed-by: martin, psandoz, forax
author dl
date Mon, 25 Jun 2018 09:59:16 -0700
parents 3c3ff151c75e
children 5637aca18f1d
files src/java.base/share/classes/java/util/ComparableTimSort.java src/java.base/share/classes/java/util/TimSort.java
diffstat 2 files changed, 20 insertions(+), 12 deletions(-) [+]
line wrap: on
line diff
--- a/src/java.base/share/classes/java/util/ComparableTimSort.java	Mon Jun 25 09:59:16 2018 -0700
+++ b/src/java.base/share/classes/java/util/ComparableTimSort.java	Mon Jun 25 09:59:16 2018 -0700
@@ -305,7 +305,7 @@
      * @param a the array in which a run is to be counted and possibly reversed
      * @param lo index of the first element in the run
      * @param hi index after the last element that may be contained in the run.
-              It is required that {@code lo < hi}.
+     *        It is required that {@code lo < hi}.
      * @return  the length of the run beginning at the specified position in
      *          the specified array
      */
@@ -394,19 +394,23 @@
      * This method is called each time a new run is pushed onto the stack,
      * so the invariants are guaranteed to hold for i < stackSize upon
      * entry to the method.
+     *
+     * Thanks to Stijn de Gouw, Jurriaan Rot, Frank S. de Boer,
+     * Richard Bubel and Reiner Hahnle, this is fixed with respect to
+     * the analysis in "On the Worst-Case Complexity of TimSort" by
+     * Nicolas Auger, Vincent Jug, Cyril Nicaud, and Carine Pivoteau.
      */
     private void mergeCollapse() {
         while (stackSize > 1) {
             int n = stackSize - 2;
-            if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
+            if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1] ||
+                n > 1 && runLen[n-2] <= runLen[n] + runLen[n-1]) {
                 if (runLen[n - 1] < runLen[n + 1])
                     n--;
-                mergeAt(n);
-            } else if (runLen[n] <= runLen[n + 1]) {
-                mergeAt(n);
-            } else {
+            } else if (n < 0 || runLen[n] > runLen[n + 1]) {
                 break; // Invariant is established
             }
+            mergeAt(n);
         }
     }
 
--- a/src/java.base/share/classes/java/util/TimSort.java	Mon Jun 25 09:59:16 2018 -0700
+++ b/src/java.base/share/classes/java/util/TimSort.java	Mon Jun 25 09:59:16 2018 -0700
@@ -339,7 +339,7 @@
      * @param a the array in which a run is to be counted and possibly reversed
      * @param lo index of the first element in the run
      * @param hi index after the last element that may be contained in the run.
-              It is required that {@code lo < hi}.
+     *        It is required that {@code lo < hi}.
      * @param c the comparator to used for the sort
      * @return  the length of the run beginning at the specified position in
      *          the specified array
@@ -429,19 +429,23 @@
      * This method is called each time a new run is pushed onto the stack,
      * so the invariants are guaranteed to hold for i < stackSize upon
      * entry to the method.
+     *
+     * Thanks to Stijn de Gouw, Jurriaan Rot, Frank S. de Boer,
+     * Richard Bubel and Reiner Hahnle, this is fixed with respect to
+     * the analysis in "On the Worst-Case Complexity of TimSort" by
+     * Nicolas Auger, Vincent Jug, Cyril Nicaud, and Carine Pivoteau.
      */
     private void mergeCollapse() {
         while (stackSize > 1) {
             int n = stackSize - 2;
-            if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
+            if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1] ||
+                n > 1 && runLen[n-2] <= runLen[n] + runLen[n-1]) {
                 if (runLen[n - 1] < runLen[n + 1])
                     n--;
-                mergeAt(n);
-            } else if (runLen[n] <= runLen[n + 1]) {
-                mergeAt(n);
-            } else {
+            } else if (n < 0 || runLen[n] > runLen[n + 1]) {
                 break; // Invariant is established
             }
+            mergeAt(n);
         }
     }