From 210475565969ca5381174016b47cd32ddc96eaed Mon Sep 17 00:00:00 2001
From: Lars Knoll <lars.knoll@digia.com>
Date: Thu, 12 Jun 2014 14:35:53 +0200
Subject: [PATCH] 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>
---
 src/qml/jsruntime/qv4arraydata.cpp                 | 56 +++++++++++++++++++++-
 tests/auto/qml/qjsengine/tst_qjsengine.cpp         | 19 ++++++++
 .../auto/qml/qqmlecmascript/data/sequenceSort.qml  |  2 +-
 3 files changed, 75 insertions(+), 2 deletions(-)

diff --git a/src/qml/jsruntime/qv4arraydata.cpp b/src/qml/jsruntime/qv4arraydata.cpp
index 7d76a10..9627848 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();
diff --git a/tests/auto/qml/qjsengine/tst_qjsengine.cpp b/tests/auto/qml/qjsengine/tst_qjsengine.cpp
index 51cd699..4b47e55 100644
--- a/tests/auto/qml/qjsengine/tst_qjsengine.cpp
+++ b/tests/auto/qml/qjsengine/tst_qjsengine.cpp
@@ -135,6 +135,7 @@ private slots:
     void reentrancy_objectCreation();
     void jsIncDecNonObjectProperty();
     void JSONparse();
+    void arraySort();
 
     void qRegExpInport_data();
     void qRegExpInport();
@@ -2729,6 +2730,24 @@ void tst_QJSEngine::JSONparse()
     QVERIFY(ret.isObject());
 }
 
+void tst_QJSEngine::arraySort()
+{
+    // tests that calling Array.sort with a bad sort function doesn't cause issues
+    // Using std::sort is e.g. not safe when used with a bad sort function and causes
+    // crashes
+    QJSEngine eng;
+    eng.evaluate("function crashMe() {"
+                 "    var data = [];"
+                 "    for (var i = 0; i < 50; i++) {"
+                 "        data[i] = 'whatever';"
+                 "    }"
+                 "    data.sort(function(a, b) {"
+                 "        return -1;"
+                 "    });"
+                 "}"
+                 "crashMe();");
+}
+
 static QRegExp minimal(QRegExp r) { r.setMinimal(true); return r; }
 
 void tst_QJSEngine::qRegExpInport_data()
diff --git a/tests/auto/qml/qqmlecmascript/data/sequenceSort.qml b/tests/auto/qml/qqmlecmascript/data/sequenceSort.qml
index 5e2892a..b130408 100644
--- a/tests/auto/qml/qqmlecmascript/data/sequenceSort.qml
+++ b/tests/auto/qml/qqmlecmascript/data/sequenceSort.qml
@@ -23,7 +23,7 @@ Item {
     }
 
     function compareStrings(a, b) {
-        return (a < b) ? 1 : -1;
+        return (a == b) ? 0 : ((a < b) ? 1 : -1);
     }
 
     function compareNumbers(a, b) {
-- 
2.7.4