[Native, Wasm, stdlib] Fix bug in quickSort for primitive arrays
^KT-70005 Fixed
It took 7 years, 3 months, 13 days; 3 project managers; 2 developers;
2 language designers; 2 fixup commits; 1 code reviewer; 1 sedative pill
to fix this bug
Co-authored-by: Igor Yakovlev <igor.yakovlev@jetbrains.com>
Co-authored-by: marat.akhin <marat.akhin@jetbrains.com>
Co-authored-by: Mikhail Zarechenskiy <mikhail.zarechenskiy@jetbrains.com>
Jokes aside, the alternative fixes are:
private fun quickSort(
array: LongArray, left: Int, right: Int) {
+ if (left >= right) return
val index = partition(array, left, right)
if (left < index - 1)
quickSort(array, left, index - 1)
OR:
private fun quickSort(
array: LongArray, left: Int, right: Int) {
+ if (left >= right) return
val index = partition(array, left, right)
- if (left < index - 1)
- quickSort(array, left, index - 1)
- if (index < right)
- quickSort(array, index, right)
+ quickSort(array, left, index - 1)
+ quickSort(array, index, right)
}
The first fix is bad because `left >= right` will never be `true` inside
the recursion. (quickSort is recursively invoked only when
`left < index - 1`) So we are doing a redundant check on every level of
the recursion
The second fix doesn't have the redundant boolean check, but in the
worst case it will increase the recursion by one, which might be just
enough to cause stack overflow and break code that worked before. Not to
mention, that in the recursion tree every recursion will take one more
recursion call to complete.
diff --git a/kotlin-native/runtime/src/main/kotlin/generated/_ArraysNative.kt b/kotlin-native/runtime/src/main/kotlin/generated/_ArraysNative.kt
index 720249b..d93a002 100644
--- a/kotlin-native/runtime/src/main/kotlin/generated/_ArraysNative.kt
+++ b/kotlin-native/runtime/src/main/kotlin/generated/_ArraysNative.kt
@@ -2366,7 +2366,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun <T : Comparable<T>> Array<out T>.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1) sortArray(this, fromIndex, toIndex)
}
/**
@@ -2384,7 +2384,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun ByteArray.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1) sortArray(this, fromIndex, toIndex)
}
/**
@@ -2402,7 +2402,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun ShortArray.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1) sortArray(this, fromIndex, toIndex)
}
/**
@@ -2420,7 +2420,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun IntArray.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1) sortArray(this, fromIndex, toIndex)
}
/**
@@ -2438,7 +2438,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun LongArray.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1) sortArray(this, fromIndex, toIndex)
}
/**
@@ -2456,7 +2456,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun FloatArray.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1) sortArray(this, fromIndex, toIndex)
}
/**
@@ -2474,7 +2474,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun DoubleArray.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1) sortArray(this, fromIndex, toIndex)
}
/**
@@ -2492,7 +2492,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun CharArray.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1) sortArray(this, fromIndex, toIndex)
}
/**
diff --git a/libraries/stdlib/test/collections/ArraysTest.kt b/libraries/stdlib/test/collections/ArraysTest.kt
index 944583d..a76c0f5 100644
--- a/libraries/stdlib/test/collections/ArraysTest.kt
+++ b/libraries/stdlib/test/collections/ArraysTest.kt
@@ -1951,6 +1951,40 @@
assertEquals(Array(0, { "" }).asList(), emptyList<String>())
}
+ @Test fun mergeSortOutOfBounds() {
+ arrayOf<String>().sort()
+ arrayOf<String>().sort(0)
+ arrayOf<String>().sort(0, 0)
+
+ assertFailsWith<IndexOutOfBoundsException> { intArrayOf().sort(5, 5) }
+ assertFailsWith<IndexOutOfBoundsException> { intArrayOf().sort(0, 1) }
+ }
+
+ @Test fun quickSortOutOfBounds() {
+ // quickSort
+ byteArrayOf().sort(0)
+ shortArrayOf().sort(0)
+ longArrayOf().sort(0)
+ charArrayOf().sort(0)
+ floatArrayOf().sort(0)
+ doubleArrayOf().sort(0)
+ // booleanArrayOf().sort(0) // BooleanArray doesn't have sort extension function
+ ubyteArrayOf().sort(0)
+ ushortArrayOf().sort(0)
+ uintArrayOf().sort(0)
+ ulongArrayOf().sort(0)
+
+ intArrayOf().sort()
+ intArrayOf().sort(0)
+ intArrayOf().sort(0, 0)
+ assertFailsWith<IndexOutOfBoundsException> { intArrayOf().sort(5, 5) }
+ assertFailsWith<IndexOutOfBoundsException> { intArrayOf().sort(0, 1) }
+ }
+
+ @Test fun quickSortRange() {
+ intArrayOf().sort(fromIndex = 5, toIndex = 5)
+ }
+
@Test fun sort() {
val intArr = intArrayOf(5, 2, 1, 9, 80, Int.MIN_VALUE, Int.MAX_VALUE)
intArr.sort()
diff --git a/libraries/stdlib/wasm/src/generated/_ArraysWasm.kt b/libraries/stdlib/wasm/src/generated/_ArraysWasm.kt
index 135bb65..62f75c0 100644
--- a/libraries/stdlib/wasm/src/generated/_ArraysWasm.kt
+++ b/libraries/stdlib/wasm/src/generated/_ArraysWasm.kt
@@ -2437,7 +2437,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun ByteArray.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1 ) sortArray(this, fromIndex, toIndex)
}
/**
@@ -2455,7 +2455,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun ShortArray.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1) sortArray(this, fromIndex, toIndex)
}
/**
@@ -2473,7 +2473,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun IntArray.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1) sortArray(this, fromIndex, toIndex)
}
/**
@@ -2491,7 +2491,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun LongArray.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1) sortArray(this, fromIndex, toIndex)
}
/**
@@ -2509,7 +2509,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun FloatArray.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1) sortArray(this, fromIndex, toIndex)
}
/**
@@ -2527,7 +2527,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun DoubleArray.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1) sortArray(this, fromIndex, toIndex)
}
/**
@@ -2545,7 +2545,7 @@
@Suppress("ACTUAL_FUNCTION_WITH_DEFAULT_ARGUMENTS")
public actual fun CharArray.sort(fromIndex: Int = 0, toIndex: Int = size): Unit {
AbstractList.checkRangeIndexes(fromIndex, toIndex, size)
- sortArray(this, fromIndex, toIndex)
+ if (size > 1) sortArray(this, fromIndex, toIndex)
}
/**
