From 59203c63bb777a3bacec32fb8830fba33540e809 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 12 Jun 2024 07:35:29 +0200 Subject: Adding upstream version 127.0. Signed-off-by: Daniel Baumann --- js/src/builtin/Array.cpp | 297 ++++------------------------------------------- 1 file changed, 21 insertions(+), 276 deletions(-) (limited to 'js/src/builtin/Array.cpp') diff --git a/js/src/builtin/Array.cpp b/js/src/builtin/Array.cpp index 2ced07b6b9..868fae8bcf 100644 --- a/js/src/builtin/Array.cpp +++ b/js/src/builtin/Array.cpp @@ -51,6 +51,7 @@ # include "vm/TupleType.h" #endif +#include "builtin/Sorting-inl.h" #include "vm/ArgumentsObject-inl.h" #include "vm/ArrayObject-inl.h" #include "vm/GeckoProfiler-inl.h" @@ -439,7 +440,7 @@ bool js::GetElements(JSContext* cx, HandleObject aobj, uint32_t length, if (aobj->is()) { Handle typedArray = aobj.as(); if (typedArray->length().valueOr(0) == length) { - return TypedArrayObject::getElements(cx, typedArray, vp); + return TypedArrayObject::getElements(cx, typedArray, length, vp); } } @@ -2180,44 +2181,16 @@ static bool ArraySortWithoutComparator(JSContext* cx, Handle obj, return true; } -void ArraySortData::init(JSObject* obj, JSObject* comparator, ValueVector&& vec, - uint32_t length, uint32_t denseLen) { - MOZ_ASSERT(!vec.empty(), "must have items to sort"); - MOZ_ASSERT(denseLen <= length); - - obj_ = obj; - comparator_ = comparator; - - this->length = length; - this->denseLen = denseLen; - this->vec = std::move(vec); - - auto getComparatorKind = [](JSContext* cx, JSObject* comparator) { - if (!comparator->is()) { - return ComparatorKind::Unoptimized; - } - JSFunction* fun = &comparator->as(); - if (!fun->hasJitEntry() || fun->isClassConstructor()) { - return ComparatorKind::Unoptimized; - } - if (fun->realm() == cx->realm() && fun->nargs() <= ComparatorActualArgs) { - return ComparatorKind::JSSameRealmNoRectifier; - } - return ComparatorKind::JS; - }; - comparatorKind_ = getComparatorKind(cx(), comparator); -} - // This function handles sorting without a comparator function (or with a // trivial comparator function that we can pattern match) by calling // ArraySortWithoutComparator. // // If there's a non-trivial comparator function, it initializes the -// ArraySortData struct for ArraySortData::sortWithComparator. This function -// must be called next to perform the sorting. +// ArraySortData struct for ArraySortData::sortArrayWithComparator. This +// function must be called next to perform the sorting. // -// This is separate from ArraySortData::sortWithComparator because it lets the -// compiler generate better code for ArraySortData::sortWithComparator. +// This is separate from ArraySortData::sortArrayWithComparator because it lets +// the compiler generate better code for ArraySortData::sortArrayWithComparator. // // https://tc39.es/ecma262/#sec-array.prototype.sort // 23.1.3.30 Array.prototype.sort ( comparefn ) @@ -2280,7 +2253,7 @@ static MOZ_ALWAYS_INLINE bool ArraySortPrologue(JSContext* cx, uint32_t len = uint32_t(length); // Merge sort requires extra scratch space. - bool needsScratchSpace = len >= ArraySortData::InsertionSortLimit; + bool needsScratchSpace = len > ArraySortData::InsertionSortMaxLength; Rooted vec(cx); if (MOZ_UNLIKELY(!vec.reserve(needsScratchSpace ? (2 * len) : len))) { @@ -2323,13 +2296,13 @@ static MOZ_ALWAYS_INLINE bool ArraySortPrologue(JSContext* cx, } d->init(obj, &comparefn.toObject(), std::move(vec.get()), len, denseLen); - // Continue in ArraySortData::sortWithComparator. + // Continue in ArraySortData::sortArrayWithComparator. MOZ_ASSERT(!*done); return true; } -static ArraySortResult CallComparatorSlow(ArraySortData* d, const Value& x, - const Value& y) { +ArraySortResult js::CallComparatorSlow(ArraySortData* d, const Value& x, + const Value& y) { JSContext* cx = d->cx(); FixedInvokeArgs<2> callArgs(cx); callArgs[0].set(x); @@ -2343,230 +2316,15 @@ static ArraySortResult CallComparatorSlow(ArraySortData* d, const Value& x, return ArraySortResult::Done; } -static MOZ_ALWAYS_INLINE ArraySortResult -MaybeYieldToComparator(ArraySortData* d, const Value& x, const Value& y) { - // https://tc39.es/ecma262/#sec-comparearrayelements - // 23.1.3.30.2 CompareArrayElements ( x, y, comparefn ) - - // Steps 1-2. - if (x.isUndefined()) { - d->setComparatorReturnValue(Int32Value(y.isUndefined() ? 0 : 1)); - return ArraySortResult::Done; - } - - // Step 3. - if (y.isUndefined()) { - d->setComparatorReturnValue(Int32Value(-1)); - return ArraySortResult::Done; - } - - // Step 4. Yield to the JIT trampoline (or js::array_sort) if the comparator - // is a JS function we can call more efficiently from JIT code. - auto kind = d->comparatorKind(); - if (MOZ_LIKELY(kind != ArraySortData::ComparatorKind::Unoptimized)) { - d->setComparatorArgs(x, y); - return (kind == ArraySortData::ComparatorKind::JSSameRealmNoRectifier) - ? ArraySortResult::CallJSSameRealmNoRectifier - : ArraySortResult::CallJS; - } - return CallComparatorSlow(d, x, y); -} - -static MOZ_ALWAYS_INLINE bool RvalIsLessOrEqual(ArraySortData* data, - bool* lessOrEqual) { - // https://tc39.es/ecma262/#sec-comparearrayelements - // 23.1.3.30.2 CompareArrayElements ( x, y, comparefn ) - - // Fast path for int32 return values. - Value rval = data->comparatorReturnValue(); - if (MOZ_LIKELY(rval.isInt32())) { - *lessOrEqual = rval.toInt32() <= 0; - return true; - } - - // Step 4.a. - Rooted rvalRoot(data->cx(), rval); - double d; - if (MOZ_UNLIKELY(!ToNumber(data->cx(), rvalRoot, &d))) { - return false; - } - - // Step 4.b-c. - *lessOrEqual = std::isnan(d) ? true : (d <= 0); - return true; -} - -static void CopyValues(Value* out, const Value* list, uint32_t start, - uint32_t end) { - for (uint32_t i = start; i <= end; i++) { - out[i] = list[i]; - } -} - // static -ArraySortResult ArraySortData::sortWithComparator(ArraySortData* d) { - JSContext* cx = d->cx(); - auto& vec = d->vec; - - // This function is like a generator that is called repeatedly from the JIT - // trampoline or js::array_sort. Resume the sorting algorithm where we left - // off before calling the comparator. - switch (d->state) { - case State::Initial: - break; - case State::InsertionSortCall1: - goto insertion_sort_call1; - case State::InsertionSortCall2: - goto insertion_sort_call2; - case State::MergeSortCall1: - goto merge_sort_call1; - case State::MergeSortCall2: - goto merge_sort_call2; - } - - d->list = vec.begin(); - - // Use insertion sort for small arrays. - if (d->denseLen < InsertionSortLimit) { - for (d->i = 1; d->i < d->denseLen; d->i++) { - d->item = vec[d->i]; - d->j = d->i - 1; - do { - { - ArraySortResult res = MaybeYieldToComparator(d, vec[d->j], d->item); - if (res != ArraySortResult::Done) { - d->state = State::InsertionSortCall1; - return res; - } - } - insertion_sort_call1: - bool lessOrEqual; - if (!RvalIsLessOrEqual(d, &lessOrEqual)) { - return ArraySortResult::Failure; - } - if (lessOrEqual) { - break; - } - vec[d->j + 1] = vec[d->j]; - } while (d->j-- > 0); - vec[d->j + 1] = d->item; - } - } else { - static constexpr size_t InitialWindowSize = 4; - - // Use insertion sort for initial ranges. - for (d->start = 0; d->start < d->denseLen - 1; - d->start += InitialWindowSize) { - d->end = - std::min(d->start + InitialWindowSize - 1, d->denseLen - 1); - for (d->i = d->start + 1; d->i <= d->end; d->i++) { - d->item = vec[d->i]; - d->j = d->i - 1; - do { - { - ArraySortResult res = MaybeYieldToComparator(d, vec[d->j], d->item); - if (res != ArraySortResult::Done) { - d->state = State::InsertionSortCall2; - return res; - } - } - insertion_sort_call2: - bool lessOrEqual; - if (!RvalIsLessOrEqual(d, &lessOrEqual)) { - return ArraySortResult::Failure; - } - if (lessOrEqual) { - break; - } - vec[d->j + 1] = vec[d->j]; - } while (d->j-- > d->start); - vec[d->j + 1] = d->item; - } - } - - // Merge sort. Set d->out to scratch space initially. - d->out = vec.begin() + d->denseLen; - for (d->windowSize = InitialWindowSize; d->windowSize < d->denseLen; - d->windowSize *= 2) { - for (d->start = 0; d->start < d->denseLen; - d->start += 2 * d->windowSize) { - // The midpoint between the two subarrays. - d->mid = d->start + d->windowSize - 1; - - // To keep from going over the edge. - d->end = std::min(d->start + 2 * d->windowSize - 1, - d->denseLen - 1); - - // Merge comparator-sorted slices list[start..<=mid] and - // list[mid+1..<=end], storing the merged sequence in out[start..<=end]. - - // Skip lopsided runs to avoid doing useless work. - if (d->mid >= d->end) { - CopyValues(d->out, d->list, d->start, d->end); - continue; - } - - // Skip calling the comparator if the sub-list is already sorted. - { - ArraySortResult res = - MaybeYieldToComparator(d, d->list[d->mid], d->list[d->mid + 1]); - if (res != ArraySortResult::Done) { - d->state = State::MergeSortCall1; - return res; - } - } - merge_sort_call1: - bool lessOrEqual; - if (!RvalIsLessOrEqual(d, &lessOrEqual)) { - return ArraySortResult::Failure; - } - if (lessOrEqual) { - CopyValues(d->out, d->list, d->start, d->end); - continue; - } - - d->i = d->start; - d->j = d->mid + 1; - d->k = d->start; - - while (d->i <= d->mid && d->j <= d->end) { - { - ArraySortResult res = - MaybeYieldToComparator(d, d->list[d->i], d->list[d->j]); - if (res != ArraySortResult::Done) { - d->state = State::MergeSortCall2; - return res; - } - } - merge_sort_call2: - bool lessOrEqual; - if (!RvalIsLessOrEqual(d, &lessOrEqual)) { - return ArraySortResult::Failure; - } - d->out[d->k++] = lessOrEqual ? d->list[d->i++] : d->list[d->j++]; - } - - // Empty out any remaining elements. Use local variables to let the - // compiler generate more efficient code. - Value* out = d->out; - Value* list = d->list; - uint32_t k = d->k; - uint32_t mid = d->mid; - uint32_t end = d->end; - for (uint32_t i = d->i; i <= mid; i++) { - out[k++] = list[i]; - } - for (uint32_t j = d->j; j <= end; j++) { - out[k++] = list[j]; - } - } - - // Swap both lists. - std::swap(d->list, d->out); - } +ArraySortResult ArraySortData::sortArrayWithComparator(ArraySortData* d) { + ArraySortResult result = sortWithComparatorShared(d); + if (result != ArraySortResult::Done) { + return result; } // Copy elements to the array. + JSContext* cx = d->cx(); Rooted obj(cx, d->obj_); if (!SetArrayElements(cx, obj, 0, d->denseLen, d->list)) { return ArraySortResult::Failure; @@ -2600,9 +2358,9 @@ bool js::array_sort(JSContext* cx, unsigned argc, Value* vp) { Rooted data(cx, cx); - // On all return paths other than ArraySortWithComparatorLoop returning Done, - // we call freeMallocData to not fail debug assertions. This matches the JIT - // trampoline where we can't rely on C++ destructors. + // On all return paths other than ArraySortData::sortArrayWithComparator + // returning Done, we call freeMallocData to not fail debug assertions. This + // matches the JIT trampoline where we can't rely on C++ destructors. auto freeData = mozilla::MakeScopeExit([&]() { data.get().freeMallocData(); }); @@ -2620,7 +2378,8 @@ bool js::array_sort(JSContext* cx, unsigned argc, Value* vp) { Rooted rval(cx); while (true) { - ArraySortResult res = ArraySortData::sortWithComparator(data.address()); + ArraySortResult res = + ArraySortData::sortArrayWithComparator(data.address()); switch (res) { case ArraySortResult::Failure: return false; @@ -2666,21 +2425,7 @@ ArraySortResult js::ArraySortFromJit(JSContext* cx, return ArraySortResult::Done; } - return ArraySortData::sortWithComparator(data); -} - -ArraySortData::ArraySortData(JSContext* cx) : cx_(cx) { -#ifdef DEBUG - cx_->liveArraySortDataInstances++; -#endif -} - -void ArraySortData::freeMallocData() { - vec.clearAndFree(); -#ifdef DEBUG - MOZ_ASSERT(cx_->liveArraySortDataInstances > 0); - cx_->liveArraySortDataInstances--; -#endif + return ArraySortData::sortArrayWithComparator(data); } void ArraySortData::trace(JSTracer* trc) { -- cgit v1.2.3