Adding upstream version 127.0.upstream/127.0

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 21 insertions, 276 deletions

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<TypedArrayObject>()) {
     Handle<TypedArrayObject*> typedArray = aobj.as<TypedArrayObject>();
     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<JSObject*> 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<JSFunction>()) {
-      return ComparatorKind::Unoptimized;
-    }
-    JSFunction* fun = &comparator->as<JSFunction>();
-    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<ArraySortData::ValueVector> 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<Value> 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<uint32_t>(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<uint32_t>(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<ArraySortKind::Array>(d);
+  if (result != ArraySortResult::Done) {
+    return result;
   }
 
   // Copy elements to the array.
+  JSContext* cx = d->cx();
   Rooted<JSObject*> 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<ArraySortData> 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<Value> 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) {