tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

Sorting-inl.h (9476B)

      1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
      2 * vim: set ts=8 sts=2 et sw=2 tw=80:
      3 * This Source Code Form is subject to the terms of the Mozilla Public
      4 * License, v. 2.0. If a copy of the MPL was not distributed with this
      5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
      6 
      7 #ifndef builtin_Sorting_inl_h
      8 #define builtin_Sorting_inl_h
      9 
     10 #include "builtin/Sorting.h"
     11 
     12 #include "js/Conversions.h"
     13 #include "vm/JSContext.h"
     14 #include "vm/JSFunction.h"
     15 #include "vm/JSObject.h"
     16 
     17 namespace js {
     18 
     19 void ArraySortData::init(JSObject* obj, JSObject* comparator, ValueVector&& vec,
     20                         uint32_t length, uint32_t denseLen) {
     21  MOZ_ASSERT(!vec.empty(), "must have items to sort");
     22  MOZ_ASSERT(denseLen <= length);
     23 
     24  obj_ = obj;
     25  comparator_ = comparator;
     26 
     27  this->length = length;
     28  this->denseLen = denseLen;
     29  this->vec = std::move(vec);
     30 
     31  auto getComparatorKind = [](JSContext* cx, JSObject* comparator) {
     32    if (!comparator->is<JSFunction>()) {
     33      return ComparatorKind::Unoptimized;
     34    }
     35    JSFunction* fun = &comparator->as<JSFunction>();
     36    if (!fun->hasJitEntry() || fun->isClassConstructor()) {
     37      return ComparatorKind::Unoptimized;
     38    }
     39    if (fun->realm() == cx->realm() && fun->nargs() <= ComparatorActualArgs) {
     40      return ComparatorKind::JSSameRealmNoUnderflow;
     41    }
     42    return ComparatorKind::JS;
     43  };
     44  comparatorKind_ = getComparatorKind(cx(), comparator);
     45 }
     46 
     47 ArraySortData::ArraySortData(JSContext* cx) : cx_(cx) {
     48 #ifdef DEBUG
     49  cx_->liveArraySortDataInstances++;
     50 #endif
     51 }
     52 
     53 void ArraySortData::freeMallocData() {
     54  vec.clearAndFree();
     55 #ifdef DEBUG
     56  MOZ_ASSERT(cx_->liveArraySortDataInstances > 0);
     57  cx_->liveArraySortDataInstances--;
     58 #endif
     59 }
     60 
     61 template <ArraySortKind Kind>
     62 static MOZ_ALWAYS_INLINE ArraySortResult
     63 MaybeYieldToComparator(ArraySortData* d, const Value& x, const Value& y) {
     64  if constexpr (Kind == ArraySortKind::Array) {
     65    // https://tc39.es/ecma262/#sec-comparearrayelements
     66    // 23.1.3.30.2 CompareArrayElements ( x, y, comparefn )
     67 
     68    // Steps 1-2.
     69    if (x.isUndefined()) {
     70      d->setComparatorReturnValue(Int32Value(y.isUndefined() ? 0 : 1));
     71      return ArraySortResult::Done;
     72    }
     73 
     74    // Step 3.
     75    if (y.isUndefined()) {
     76      d->setComparatorReturnValue(Int32Value(-1));
     77      return ArraySortResult::Done;
     78    }
     79  } else {
     80    // https://tc39.es/ecma262/#sec-comparetypedarrayelements
     81    // 23.2.4.7 CompareTypedArrayElements ( x, y, comparefn )
     82 
     83    // Step 1.
     84    MOZ_ASSERT((x.isNumber() && y.isNumber()) ||
     85               (x.isBigInt() && y.isBigInt()));
     86  }
     87 
     88  // Yield to the JIT trampoline (or js::array_sort) if the comparator is a JS
     89  // function we can call more efficiently from JIT code.
     90  auto kind = d->comparatorKind();
     91  if (MOZ_LIKELY(kind != ArraySortData::ComparatorKind::Unoptimized)) {
     92    d->setComparatorArgs(x, y);
     93    return (kind == ArraySortData::ComparatorKind::JSSameRealmNoUnderflow)
     94               ? ArraySortResult::CallJSSameRealmNoUnderflow
     95               : ArraySortResult::CallJS;
     96  }
     97  return CallComparatorSlow(d, x, y);
     98 }
     99 
    100 static MOZ_ALWAYS_INLINE bool RvalIsLessOrEqual(ArraySortData* data,
    101                                                bool* lessOrEqual) {
    102  // https://tc39.es/ecma262/#sec-comparearrayelements
    103  // 23.1.3.30.2 CompareArrayElements ( x, y, comparefn )
    104  //
    105  // https://tc39.es/ecma262/#sec-comparetypedarrayelements
    106  // 23.2.4.7 CompareTypedArrayElements ( x, y, comparefn )
    107  //
    108  // Note: CompareTypedArrayElements step 2 is identical to CompareArrayElements
    109  // step 4.
    110 
    111  // Fast path for int32 return values.
    112  Value rval = data->comparatorReturnValue();
    113  if (MOZ_LIKELY(rval.isInt32())) {
    114    *lessOrEqual = rval.toInt32() <= 0;
    115    return true;
    116  }
    117 
    118  // Step 4.a.
    119  Rooted<Value> rvalRoot(data->cx(), rval);
    120  double d;
    121  if (MOZ_UNLIKELY(!ToNumber(data->cx(), rvalRoot, &d))) {
    122    return false;
    123  }
    124 
    125  // Step 4.b-c.
    126  *lessOrEqual = std::isnan(d) ? true : (d <= 0);
    127  return true;
    128 }
    129 
    130 static MOZ_ALWAYS_INLINE void CopyValues(Value* out, const Value* list,
    131                                         uint32_t start, uint32_t end) {
    132  for (uint32_t i = start; i <= end; i++) {
    133    out[i] = list[i];
    134  }
    135 }
    136 
    137 // static
    138 template <ArraySortKind Kind>
    139 ArraySortResult ArraySortData::sortWithComparatorShared(ArraySortData* d) {
    140  auto& vec = d->vec;
    141 
    142  // This function is like a generator that is called repeatedly from the JIT
    143  // trampoline or js::array_sort. Resume the sorting algorithm where we left
    144  // off before calling the comparator.
    145  switch (d->state) {
    146    case State::Initial:
    147      break;
    148    case State::InsertionSortCall1:
    149      goto insertion_sort_call1;
    150    case State::InsertionSortCall2:
    151      goto insertion_sort_call2;
    152    case State::MergeSortCall1:
    153      goto merge_sort_call1;
    154    case State::MergeSortCall2:
    155      goto merge_sort_call2;
    156  }
    157 
    158  d->list = vec.begin();
    159 
    160  // Use insertion sort for small arrays.
    161  if (d->denseLen <= InsertionSortMaxLength) {
    162    for (d->i = 1; d->i < d->denseLen; d->i++) {
    163      d->item = vec[d->i];
    164      d->j = d->i - 1;
    165      do {
    166        {
    167          ArraySortResult res =
    168              MaybeYieldToComparator<Kind>(d, vec[d->j], d->item);
    169          if (res != ArraySortResult::Done) {
    170            d->state = State::InsertionSortCall1;
    171            return res;
    172          }
    173        }
    174      insertion_sort_call1:
    175        bool lessOrEqual;
    176        if (!RvalIsLessOrEqual(d, &lessOrEqual)) {
    177          return ArraySortResult::Failure;
    178        }
    179        if (lessOrEqual) {
    180          break;
    181        }
    182        vec[d->j + 1] = vec[d->j];
    183      } while (d->j-- > 0);
    184      vec[d->j + 1] = d->item;
    185    }
    186  } else {
    187    static constexpr size_t InitialWindowSize = 4;
    188 
    189    // Use insertion sort for initial ranges.
    190    for (d->start = 0; d->start < d->denseLen - 1;
    191         d->start += InitialWindowSize) {
    192      d->end =
    193          std::min<uint32_t>(d->start + InitialWindowSize - 1, d->denseLen - 1);
    194      for (d->i = d->start + 1; d->i <= d->end; d->i++) {
    195        d->item = vec[d->i];
    196        d->j = d->i - 1;
    197        do {
    198          {
    199            ArraySortResult res =
    200                MaybeYieldToComparator<Kind>(d, vec[d->j], d->item);
    201            if (res != ArraySortResult::Done) {
    202              d->state = State::InsertionSortCall2;
    203              return res;
    204            }
    205          }
    206        insertion_sort_call2:
    207          bool lessOrEqual;
    208          if (!RvalIsLessOrEqual(d, &lessOrEqual)) {
    209            return ArraySortResult::Failure;
    210          }
    211          if (lessOrEqual) {
    212            break;
    213          }
    214          vec[d->j + 1] = vec[d->j];
    215        } while (d->j-- > d->start);
    216        vec[d->j + 1] = d->item;
    217      }
    218    }
    219 
    220    // Merge sort. Set d->out to scratch space initially.
    221    d->out = vec.begin() + d->denseLen;
    222    for (d->windowSize = InitialWindowSize; d->windowSize < d->denseLen;
    223         d->windowSize *= 2) {
    224      for (d->start = 0; d->start < d->denseLen;
    225           d->start += 2 * d->windowSize) {
    226        // The midpoint between the two subarrays.
    227        d->mid = d->start + d->windowSize - 1;
    228 
    229        // To keep from going over the edge.
    230        d->end = std::min<uint32_t>(d->start + 2 * d->windowSize - 1,
    231                                    d->denseLen - 1);
    232 
    233        // Merge comparator-sorted slices list[start..<=mid] and
    234        // list[mid+1..<=end], storing the merged sequence in out[start..<=end].
    235 
    236        // Skip lopsided runs to avoid doing useless work.
    237        if (d->mid >= d->end) {
    238          CopyValues(d->out, d->list, d->start, d->end);
    239          continue;
    240        }
    241 
    242        // Skip calling the comparator if the sub-list is already sorted.
    243        {
    244          ArraySortResult res = MaybeYieldToComparator<Kind>(
    245              d, d->list[d->mid], d->list[d->mid + 1]);
    246          if (res != ArraySortResult::Done) {
    247            d->state = State::MergeSortCall1;
    248            return res;
    249          }
    250        }
    251      merge_sort_call1:
    252        bool lessOrEqual;
    253        if (!RvalIsLessOrEqual(d, &lessOrEqual)) {
    254          return ArraySortResult::Failure;
    255        }
    256        if (lessOrEqual) {
    257          CopyValues(d->out, d->list, d->start, d->end);
    258          continue;
    259        }
    260 
    261        d->i = d->start;
    262        d->j = d->mid + 1;
    263        d->k = d->start;
    264 
    265        while (d->i <= d->mid && d->j <= d->end) {
    266          {
    267            ArraySortResult res =
    268                MaybeYieldToComparator<Kind>(d, d->list[d->i], d->list[d->j]);
    269            if (res != ArraySortResult::Done) {
    270              d->state = State::MergeSortCall2;
    271              return res;
    272            }
    273          }
    274        merge_sort_call2:
    275          bool lessOrEqual;
    276          if (!RvalIsLessOrEqual(d, &lessOrEqual)) {
    277            return ArraySortResult::Failure;
    278          }
    279          d->out[d->k++] = lessOrEqual ? d->list[d->i++] : d->list[d->j++];
    280        }
    281 
    282        // Empty out any remaining elements. Use local variables to let the
    283        // compiler generate more efficient code.
    284        Value* out = d->out;
    285        Value* list = d->list;
    286        uint32_t k = d->k;
    287        uint32_t mid = d->mid;
    288        uint32_t end = d->end;
    289        for (uint32_t i = d->i; i <= mid; i++) {
    290          out[k++] = list[i];
    291        }
    292        for (uint32_t j = d->j; j <= end; j++) {
    293          out[k++] = list[j];
    294        }
    295      }
    296 
    297      // Swap both lists.
    298      std::swap(d->list, d->out);
    299    }
    300  }
    301 
    302  return ArraySortResult::Done;
    303 }
    304 
    305 }  // namespace js
    306 
    307 #endif /* builtin_Sorting_inl_h */