Fix crashes when calling Array.sort with imperfect sort functions

We can't use std::sort to implement Array.sort. The reason is that
std::sort expects a conformant compare function, and can do weird
things (esp. crash) when the sort function isn't conformant.

Falling back to qSort is not possible, as the method has been
deprecated. So add a copy of the qSort implementation here, and
use that one instead.

Fix the sortint test in tst_qqmlecmascript to have a consistent
sort function for strings, as the result of calling sort is
otherwise undefined according to the ecma standard.

Task-number: QTBUG-39072
Change-Id: I0602b3aa1ffa4de5006da58396f166805cf4a5e2
Reviewed-by: Robin Burchell <robin.burchell@viroteck.net>
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

1 files changed, 55 insertions, 1 deletions

diff --git a/src/qml/jsruntime/qv4arraydata.cpp b/src/qml/jsruntime/qv4arraydata.cpp
index 7d76a10ad6..9627848102 100644
--- a/src/qml/jsruntime/qv4arraydata.cpp
+++ b/src/qml/jsruntime/qv4arraydata.cpp
@@ -674,6 +674,60 @@ bool ArrayElementLessThan::operator()(Value v1, Value v2) const
     return p1s->toQString() < p2s->toQString();
 }
 
+template <typename RandomAccessIterator, typename T, typename LessThan>
+void sortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan)
+{
+top:
+    int span = int(end - start);
+    if (span < 2)
+        return;
+
+    --end;
+    RandomAccessIterator low = start, high = end - 1;
+    RandomAccessIterator pivot = start + span / 2;
+
+    if (lessThan(*end, *start))
+        qSwap(*end, *start);
+    if (span == 2)
+        return;
+
+    if (lessThan(*pivot, *start))
+        qSwap(*pivot, *start);
+    if (lessThan(*end, *pivot))
+        qSwap(*end, *pivot);
+    if (span == 3)
+        return;
+
+    qSwap(*pivot, *end);
+
+    while (low < high) {
+        while (low < high && lessThan(*low, *end))
+            ++low;
+
+        while (high > low && lessThan(*end, *high))
+            --high;
+
+        if (low < high) {
+            qSwap(*low, *high);
+            ++low;
+            --high;
+        } else {
+            break;
+        }
+    }
+
+    if (lessThan(*low, *end))
+        ++low;
+
+    qSwap(*end, *low);
+    sortHelper(start, low, t, lessThan);
+
+    start = low + 1;
+    ++end;
+    goto top;
+}
+
+
 void ArrayData::sort(ExecutionContext *context, ObjectRef thisObject, const ValueRef comparefn, uint len)
 {
     if (!len)
@@ -765,7 +819,7 @@ void ArrayData::sort(ExecutionContext *context, ObjectRef thisObject, const Valu
     ArrayElementLessThan lessThan(context, thisObject, comparefn);
 
     Value *begin = thisObject->arrayData->data;
-    std::sort(begin, begin + len, lessThan);
+    sortHelper(begin, begin + len, *begin, lessThan);
 
 #ifdef CHECK_SPARSE_ARRAYS
     thisObject->initSparseArray();