QV4::ArrayData: Fix offset calculation for sort()

We cannot just sort the raw values. We have to take the offset into
account. If the array wraps around the end of the allocation, we have to
move it around to be contiguous.

Fixes: QTBUG-58718
Change-Id: I1866b3f271d97352e250d687955af3fc54340334
Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
Reviewed-by: Sami Shalayel <sami.shalayel@qt.io>
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
(cherry picked from commit f0b2fbcf47f00071a7f5f1a04258d451badcb81a)

2 files changed, 110 insertions, 5 deletions

diff --git a/src/qml/jsruntime/qv4arraydata.cpp b/src/qml/jsruntime/qv4arraydata.cpp
index b4f7a630e1..9b6b380c5d 100644
--- a/src/qml/jsruntime/qv4arraydata.cpp
+++ b/src/qml/jsruntime/qv4arraydata.cpp
@@ -670,8 +670,8 @@ 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)
+template <typename RandomAccessIterator, typename LessThan>
+void sortHelper(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)
 {
 top:
     int span = int(end - start);
@@ -716,7 +716,7 @@ top:
         ++low;
 
     qSwap(*end, *low);
-    sortHelper(start, low, t, lessThan);
+    sortHelper(start, low, lessThan);
 
     start = low + 1;
     ++end;
@@ -816,8 +816,36 @@ void ArrayData::sort(ExecutionEngine *engine, Object *thisObject, const Value &c
 
     ArrayElementLessThan lessThan(engine, static_cast<const FunctionObject &>(comparefn));
 
-    Value *begin = thisObject->arrayData()->values.values;
-    sortHelper(begin, begin + len, *begin, lessThan);
+    const auto thisArrayData = thisObject->arrayData();
+    uint startIndex = thisArrayData->mappedIndex(0);
+    uint endIndex = thisArrayData->mappedIndex(len - 1) + 1;
+    if (startIndex < endIndex) {
+        // Values are contiguous. Sort right away.
+        sortHelper(
+                thisArrayData->values.values + startIndex,
+                thisArrayData->values.values + endIndex,
+                lessThan);
+    } else {
+        // Values wrap around the end of the allocation. Close the gap to form a contiguous array.
+        // We're going to sort anyway. So we don't need to care about order.
+
+        // ArrayElementLessThan sorts empty and undefined to the end of the array anyway, but we
+        // probably shouldn't rely on the unused slots to be actually undefined or empty.
+
+        const uint gap = startIndex - endIndex;
+        const uint allocEnd = thisArrayData->values.alloc - 1;
+        for (uint i = 0; i < gap; ++i) {
+            const uint from = allocEnd - i;
+            const uint to = endIndex + i;
+            if (from < startIndex)
+                break;
+
+            std::swap(thisArrayData->values.values[from], thisArrayData->values.values[to]);
+        }
+
+        thisArrayData->offset = 0;
+        sortHelper(thisArrayData->values.values, thisArrayData->values.values + len, 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 f1c34e6142..8e7958c3ef 100644
--- a/tests/auto/qml/qjsengine/tst_qjsengine.cpp
+++ b/tests/auto/qml/qjsengine/tst_qjsengine.cpp
@@ -105,6 +105,8 @@ private slots:
     void collectGarbageNestedWrappersTwoEngines();
     void gcWithNestedDataStructure();
     void stacktrace();
+    void unshiftAndSort();
+    void unshiftAndPushAndSort();
     void numberParsing_data();
     void numberParsing();
     void automaticSemicolonInsertion();
@@ -1982,6 +1984,81 @@ void tst_QJSEngine::stacktrace()
     }
 }
 
+void tst_QJSEngine::unshiftAndSort()
+{
+    QJSEngine engine;
+    QJSValue func = engine.evaluate(R"""(
+    (function (objectArr, currIdx) {
+        objectArr.unshift({"sortIndex": currIdx});
+        objectArr.sort(function(a, b) {
+            if (a.sortIndex > b.sortIndex)
+                return 1;
+            if (a.sortIndex < b.sortIndex)
+                return -1;
+            return 0;
+        });
+        return objectArr;
+    })
+    )""");
+    QVERIFY(func.isCallable());
+    QJSValue objectArr = engine.newArray();
+
+    for (int i = 0; i < 5; ++i) {
+        objectArr = func.call({objectArr, i});
+        QVERIFY2(!objectArr.isError(), qPrintable(objectArr.toString()));
+        const int length = objectArr.property("length").toInt();
+
+        // It did add one element
+        QCOMPARE(length, i + 1);
+
+        for (int x = 0; x < length; ++x) {
+            // We didn't sort cruft into the array.
+            QVERIFY(!objectArr.property(x).isUndefined());
+
+            // The array is actually sorted.
+            QCOMPARE(objectArr.property(x).property("sortIndex").toInt(), x);
+        }
+    }
+}
+
+void tst_QJSEngine::unshiftAndPushAndSort()
+{
+    QJSEngine engine;
+    QJSValue func = engine.evaluate(R"""(
+    (function (objectArr, currIdx) {
+        objectArr.unshift({"sortIndex": currIdx});
+        objectArr.push({"sortIndex": currIdx + 1});
+        objectArr.sort(function(a, b) {
+            if (a.sortIndex > b.sortIndex)
+                return 1;
+            if (a.sortIndex < b.sortIndex)
+                return -1;
+            return 0;
+        });
+        return objectArr;
+    })
+    )""");
+    QVERIFY(func.isCallable());
+    QJSValue objectArr = engine.newArray();
+
+    for (int i = 0; i < 20; i += 2) {
+        objectArr = func.call({objectArr, i});
+        QVERIFY2(!objectArr.isError(), qPrintable(objectArr.toString()));
+        const int length = objectArr.property("length").toInt();
+
+        // It did add 2 elements
+        QCOMPARE(length, i + 2);
+
+        for (int x = 0; x < length; ++x) {
+            // We didn't sort cruft into the array.
+            QVERIFY(!objectArr.property(x).isUndefined());
+
+            // The array is actually sorted.
+            QCOMPARE(objectArr.property(x).property("sortIndex").toInt(), x);
+        }
+    }
+}
+
 void tst_QJSEngine::numberParsing_data()
 {
     QTest::addColumn<QString>("string");