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