tor-browser

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

Sorting.h (5641B)

      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_h
      8 #define builtin_Sorting_h
      9 
     10 #include "mozilla/Attributes.h"
     11 
     12 #include "js/GCVector.h"
     13 #include "vm/JSObject.h"
     14 
     15 // Code used by Array.prototype.sort and %TypedArray%.prototype.sort to sort
     16 // objects based on a user-defined comparator function.
     17 
     18 namespace js {
     19 
     20 // Note: we use uint32_t because the JIT code uses branch32.
     21 enum class ArraySortResult : uint32_t {
     22  Failure,
     23  Done,
     24  CallJS,
     25  CallJSSameRealmNoUnderflow
     26 };
     27 
     28 enum class ArraySortKind {
     29  Array,
     30  TypedArray,
     31 };
     32 
     33 // We use a JIT trampoline to optimize sorting with a comparator function. The
     34 // trampoline frame has an ArraySortData instance that contains all state used
     35 // by the sorting algorithm. The sorting algorithm is implemented as a C++
     36 // "generator" that can yield to the trampoline to perform a fast JIT => JIT
     37 // call to the comparator function. When the comparator function returns, the
     38 // trampoline calls back into C++ to resume the sorting algorithm.
     39 //
     40 // ArraySortData stores the JS Values in a js::Vector. To ensure we don't leak
     41 // its memory, we have debug assertions to check that for each C++ constructor
     42 // call we call |freeMallocData| exactly once. C++ code calls |freeMallocData|
     43 // when it's done sorting and the JIT exception handler calls it when unwinding
     44 // the trampoline frame.
     45 class alignas(8) ArraySortData {
     46 public:
     47  enum class ComparatorKind : uint8_t {
     48    Unoptimized,
     49    JS,
     50    JSSameRealmNoUnderflow,
     51  };
     52 
     53  // Insertion sort is used if the length is <= InsertionSortMaxLength.
     54  static constexpr size_t InsertionSortMaxLength = 8;
     55 
     56  static constexpr size_t ComparatorActualArgs = 2;
     57 
     58  using ValueVector = GCVector<Value, 8, SystemAllocPolicy>;
     59 
     60 protected:  // Silence Clang warning about unused private fields.
     61  // Data for the comparator call. These fields must match the JitFrameLayout
     62  // to let us perform efficient calls to the comparator from JIT code.
     63  // This is asserted in the JIT trampoline code.
     64  // callArgs[0] is also used to store the return value of the sort function and
     65  // the comparator.
     66  uintptr_t descriptor_;
     67  JSObject* comparator_ = nullptr;
     68  Value thisv;
     69  Value callArgs[ComparatorActualArgs];
     70 
     71 private:
     72  ValueVector vec;
     73  Value item;
     74  JSContext* cx_;
     75  JSObject* obj_ = nullptr;
     76 
     77  Value* list;
     78  Value* out;
     79 
     80  // The value of the .length property.
     81  uint32_t length;
     82 
     83  // The number of items to sort. Can be less than |length| if the object has
     84  // holes.
     85  uint32_t denseLen;
     86 
     87  uint32_t windowSize;
     88  uint32_t start;
     89  uint32_t mid;
     90  uint32_t end;
     91  uint32_t i, j, k;
     92 
     93  // The state value determines where we resume in sortWithComparator.
     94  enum class State : uint8_t {
     95    Initial,
     96    InsertionSortCall1,
     97    InsertionSortCall2,
     98    MergeSortCall1,
     99    MergeSortCall2
    100  };
    101  State state = State::Initial;
    102  ComparatorKind comparatorKind_;
    103 
    104  // Optional padding to ensure proper alignment of the comparator JIT frame.
    105 #if !defined(JS_64BIT) && !defined(DEBUG)
    106 protected:  // Silence Clang warning about unused private field.
    107  uint32_t padding[2];
    108 #endif
    109 
    110 private:
    111  // Merge sort requires extra scratch space in the vector. Insertion sort
    112  // should be used for short arrays that fit in the vector's inline storage, to
    113  // avoid extra malloc calls.
    114  static_assert(decltype(vec)::InlineLength <= InsertionSortMaxLength);
    115 
    116  template <ArraySortKind Kind>
    117  static MOZ_ALWAYS_INLINE ArraySortResult
    118  sortWithComparatorShared(ArraySortData* d);
    119 
    120 public:
    121  explicit inline ArraySortData(JSContext* cx);
    122 
    123  void MOZ_ALWAYS_INLINE init(JSObject* obj, JSObject* comparator,
    124                              ValueVector&& vec, uint32_t length,
    125                              uint32_t denseLen);
    126 
    127  JSContext* cx() const { return cx_; }
    128 
    129  JSObject* comparator() const {
    130    MOZ_ASSERT(comparator_);
    131    return comparator_;
    132  }
    133 
    134  Value returnValue() const { return callArgs[0]; }
    135  void setReturnValue(JSObject* obj) { callArgs[0].setObject(*obj); }
    136 
    137  Value comparatorArg(size_t index) {
    138    MOZ_ASSERT(index < ComparatorActualArgs);
    139    return callArgs[index];
    140  }
    141  Value comparatorThisValue() const { return thisv; }
    142  Value comparatorReturnValue() const { return callArgs[0]; }
    143  void setComparatorArgs(const Value& x, const Value& y) {
    144    callArgs[0] = x;
    145    callArgs[1] = y;
    146  }
    147  void setComparatorReturnValue(const Value& v) { callArgs[0] = v; }
    148 
    149  ComparatorKind comparatorKind() const { return comparatorKind_; }
    150 
    151  static ArraySortResult sortArrayWithComparator(ArraySortData* d);
    152  static ArraySortResult sortTypedArrayWithComparator(ArraySortData* d);
    153 
    154  inline void freeMallocData();
    155  void trace(JSTracer* trc);
    156 
    157  static constexpr int32_t offsetOfDescriptor() {
    158    return offsetof(ArraySortData, descriptor_);
    159  }
    160  static constexpr int32_t offsetOfComparator() {
    161    return offsetof(ArraySortData, comparator_);
    162  }
    163  static constexpr int32_t offsetOfComparatorReturnValue() {
    164    return offsetof(ArraySortData, callArgs[0]);
    165  }
    166  static constexpr int32_t offsetOfComparatorThis() {
    167    return offsetof(ArraySortData, thisv);
    168  }
    169  static constexpr int32_t offsetOfComparatorArgs() {
    170    return offsetof(ArraySortData, callArgs);
    171  }
    172 };
    173 
    174 ArraySortResult CallComparatorSlow(ArraySortData* d, const Value& x,
    175                                   const Value& y);
    176 
    177 }  // namespace js
    178 
    179 #endif /* builtin_Sorting_h */