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 <[email protected]>
Reviewed-by: Sami Shalayel <[email protected]>
Reviewed-by: Qt CI Bot <[email protected]>
(cherry picked from commit f0b2fbcf47f00071a7f5f1a04258d451badcb81a)

1 files changed, 33 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();