From 0e1a51367a4b00164d055f527ce0d08f78737bcb Mon Sep 17 00:00:00 2001 From: Ulf Hermann Date: Tue, 11 Jul 2023 11:16:43 +0200 Subject: 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 Reviewed-by: Sami Shalayel Reviewed-by: Qt CI Bot (cherry picked from commit f0b2fbcf47f00071a7f5f1a04258d451badcb81a) --- src/qml/jsruntime/qv4arraydata.cpp | 38 +++++++++++++++++++++++++++++++++----- 1 file changed, 33 insertions(+), 5 deletions(-) (limited to 'src/qml/jsruntime') 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 -void sortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan) +template +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(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(); -- cgit v1.2.3