summaryrefslogtreecommitdiff
path: root/deps/v8/third_party
diff options
context:
space:
mode:
authorMichaël Zasso <targos@protonmail.com>2018-12-04 08:20:37 +0100
committerMichaël Zasso <targos@protonmail.com>2018-12-06 15:23:33 +0100
commit9b4bf7de6c9a7c25f116c7a502384c20b5cfaea3 (patch)
tree2b0c843168dafb939d8df8a15b2aa72b76dee51d /deps/v8/third_party
parentb8fbe69db1292307adb2c2b2e0d5ef48c4ab2faf (diff)
downloadandroid-node-v8-9b4bf7de6c9a7c25f116c7a502384c20b5cfaea3.tar.gz
android-node-v8-9b4bf7de6c9a7c25f116c7a502384c20b5cfaea3.tar.bz2
android-node-v8-9b4bf7de6c9a7c25f116c7a502384c20b5cfaea3.zip
deps: update V8 to 7.1.302.28
PR-URL: https://github.com/nodejs/node/pull/23423 Reviewed-By: Colin Ihrig <cjihrig@gmail.com> Reviewed-By: Gus Caplan <me@gus.host> Reviewed-By: Myles Borins <myles.borins@gmail.com>
Diffstat (limited to 'deps/v8/third_party')
-rw-r--r--deps/v8/third_party/binutils/Linux_ia32/binutils.tar.bz2.sha12
-rw-r--r--deps/v8/third_party/binutils/Linux_x64/binutils.tar.bz2.sha12
-rw-r--r--deps/v8/third_party/googletest/src/googletest/include/gtest/gtest_prod.h3
-rw-r--r--deps/v8/third_party/v8/builtins/array-sort.tq1119
4 files changed, 559 insertions, 567 deletions
diff --git a/deps/v8/third_party/binutils/Linux_ia32/binutils.tar.bz2.sha1 b/deps/v8/third_party/binutils/Linux_ia32/binutils.tar.bz2.sha1
index 93942d8908..aaed4ddbad 100644
--- a/deps/v8/third_party/binutils/Linux_ia32/binutils.tar.bz2.sha1
+++ b/deps/v8/third_party/binutils/Linux_ia32/binutils.tar.bz2.sha1
@@ -1 +1 @@
-81fd042fef3e2ff2e807a8c1fb4ea621b665d6b3 \ No newline at end of file
+c956d54d404eb1d35b3a4d88b7bfd34f2f06f7af \ No newline at end of file
diff --git a/deps/v8/third_party/binutils/Linux_x64/binutils.tar.bz2.sha1 b/deps/v8/third_party/binutils/Linux_x64/binutils.tar.bz2.sha1
index 6bc9f8c8c1..dfa4fefbd5 100644
--- a/deps/v8/third_party/binutils/Linux_x64/binutils.tar.bz2.sha1
+++ b/deps/v8/third_party/binutils/Linux_x64/binutils.tar.bz2.sha1
@@ -1 +1 @@
-dbe488f8a5c2e11573a38e8b01e8c96bebed3365 \ No newline at end of file
+69bedb1192a03126687f75cb6cf1717758a1a59f \ No newline at end of file
diff --git a/deps/v8/third_party/googletest/src/googletest/include/gtest/gtest_prod.h b/deps/v8/third_party/googletest/src/googletest/include/gtest/gtest_prod.h
index 71377f87d4..e651671ebd 100644
--- a/deps/v8/third_party/googletest/src/googletest/include/gtest/gtest_prod.h
+++ b/deps/v8/third_party/googletest/src/googletest/include/gtest/gtest_prod.h
@@ -26,8 +26,7 @@
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-//
-// Author: wan@google.com (Zhanyong Wan)
+
//
// Google C++ Testing and Mocking Framework definitions useful in production code.
// GOOGLETEST_CM0003 DO NOT DELETE
diff --git a/deps/v8/third_party/v8/builtins/array-sort.tq b/deps/v8/third_party/v8/builtins/array-sort.tq
index 65d0b8348b..46848e3f49 100644
--- a/deps/v8/third_party/v8/builtins/array-sort.tq
+++ b/deps/v8/third_party/v8/builtins/array-sort.tq
@@ -124,7 +124,7 @@ module array {
// copied values from the prototype chain to the receiver if they were visible
// through a hole.
- builtin Load<ElementsAccessor : type>(
+ builtin Load<ElementsAccessor: type>(
context: Context, sortState: FixedArray, elements: HeapObject,
index: Smi): Object {
return GetProperty(context, elements, index);
@@ -133,14 +133,14 @@ module array {
Load<FastPackedSmiElements>(
context: Context, sortState: FixedArray, elements: HeapObject,
index: Smi): Object {
- const elems: FixedArray = unsafe_cast<FixedArray>(elements);
+ const elems: FixedArray = UnsafeCast<FixedArray>(elements);
return elems[index];
}
Load<FastSmiOrObjectElements>(
context: Context, sortState: FixedArray, elements: HeapObject,
index: Smi): Object {
- const elems: FixedArray = unsafe_cast<FixedArray>(elements);
+ const elems: FixedArray = UnsafeCast<FixedArray>(elements);
const result: Object = elems[index];
if (IsTheHole(result)) {
// The pre-processing step removed all holes by compacting all elements
@@ -155,7 +155,7 @@ module array {
context: Context, sortState: FixedArray, elements: HeapObject,
index: Smi): Object {
try {
- const elems: FixedDoubleArray = unsafe_cast<FixedDoubleArray>(elements);
+ const elems: FixedDoubleArray = UnsafeCast<FixedDoubleArray>(elements);
const value: float64 =
LoadDoubleWithHoleCheck(elems, index) otherwise Bailout;
return AllocateHeapNumberWithValue(value);
@@ -173,11 +173,11 @@ module array {
index: Smi): Object {
try {
const dictionary: NumberDictionary =
- unsafe_cast<NumberDictionary>(elements);
- const intptr_index: intptr = convert<intptr>(index);
+ UnsafeCast<NumberDictionary>(elements);
+ const intptrIndex: intptr = Convert<intptr>(index);
const value: Object =
- BasicLoadNumberDictionaryElement(dictionary, intptr_index)
- otherwise Bailout, Bailout;
+ BasicLoadNumberDictionaryElement(dictionary, intptrIndex)
+ otherwise Bailout, Bailout;
return value;
}
label Bailout {
@@ -189,11 +189,11 @@ module array {
context: Context, sortState: FixedArray, elements: HeapObject,
index: Smi): Object {
assert(IsFixedArray(elements));
- const elems: FixedArray = unsafe_cast<FixedArray>(elements);
+ const elems: FixedArray = UnsafeCast<FixedArray>(elements);
return elems[index];
}
- builtin Store<ElementsAccessor : type>(
+ builtin Store<ElementsAccessor: type>(
context: Context, sortState: FixedArray, elements: HeapObject, index: Smi,
value: Object): Smi {
SetProperty(context, elements, index, value);
@@ -203,7 +203,7 @@ module array {
Store<FastPackedSmiElements>(
context: Context, sortState: FixedArray, elements: HeapObject, index: Smi,
value: Object): Smi {
- const elems: FixedArray = unsafe_cast<FixedArray>(elements);
+ const elems: FixedArray = UnsafeCast<FixedArray>(elements);
StoreFixedArrayElementSmi(elems, index, value, SKIP_WRITE_BARRIER);
return kSuccess;
}
@@ -211,7 +211,7 @@ module array {
Store<FastSmiOrObjectElements>(
context: Context, sortState: FixedArray, elements: HeapObject, index: Smi,
value: Object): Smi {
- const elems: FixedArray = unsafe_cast<FixedArray>(elements);
+ const elems: FixedArray = UnsafeCast<FixedArray>(elements);
elems[index] = value;
return kSuccess;
}
@@ -219,10 +219,10 @@ module array {
Store<FastDoubleElements>(
context: Context, sortState: FixedArray, elements: HeapObject, index: Smi,
value: Object): Smi {
- const elems: FixedDoubleArray = unsafe_cast<FixedDoubleArray>(elements);
- const heap_val: HeapNumber = unsafe_cast<HeapNumber>(value);
+ const elems: FixedDoubleArray = UnsafeCast<FixedDoubleArray>(elements);
+ const heapVal: HeapNumber = UnsafeCast<HeapNumber>(value);
// Make sure we do not store signalling NaNs into double arrays.
- const val: float64 = Float64SilenceNaN(convert<float64>(heap_val));
+ const val: float64 = Float64SilenceNaN(Convert<float64>(heapVal));
StoreFixedDoubleArrayElementWithSmiIndex(elems, index, val);
return kSuccess;
}
@@ -230,12 +230,11 @@ module array {
Store<DictionaryElements>(
context: Context, sortState: FixedArray, elements: HeapObject, index: Smi,
value: Object): Smi {
- const dictionary: NumberDictionary =
- unsafe_cast<NumberDictionary>(elements);
- const intptr_index: intptr = convert<intptr>(index);
+ const dictionary: NumberDictionary = UnsafeCast<NumberDictionary>(elements);
+ const intptrIndex: intptr = Convert<intptr>(index);
try {
- BasicStoreNumberDictionaryElement(dictionary, intptr_index, value)
- otherwise Fail, Fail, ReadOnly;
+ BasicStoreNumberDictionaryElement(dictionary, intptrIndex, value)
+ otherwise Fail, Fail, ReadOnly;
return kSuccess;
}
label ReadOnly {
@@ -253,29 +252,29 @@ module array {
Store<TempArrayElements>(
context: Context, sortState: FixedArray, elements: HeapObject, index: Smi,
value: Object): Smi {
- const elems: FixedArray = unsafe_cast<FixedArray>(elements);
+ const elems: FixedArray = UnsafeCast<FixedArray>(elements);
elems[index] = value;
return kSuccess;
}
extern macro UnsafeCastObjectToCompareBuiltinFn(Object): CompareBuiltinFn;
- unsafe_cast<CompareBuiltinFn>(o: Object): CompareBuiltinFn {
+ UnsafeCast<CompareBuiltinFn>(o: Object): CompareBuiltinFn {
return UnsafeCastObjectToCompareBuiltinFn(o);
}
extern macro UnsafeCastObjectToLoadFn(Object): LoadFn;
- unsafe_cast<LoadFn>(o: Object): LoadFn {
+ UnsafeCast<LoadFn>(o: Object): LoadFn {
return UnsafeCastObjectToLoadFn(o);
}
extern macro UnsafeCastObjectToStoreFn(Object): StoreFn;
- unsafe_cast<StoreFn>(o: Object): StoreFn {
+ UnsafeCast<StoreFn>(o: Object): StoreFn {
return UnsafeCastObjectToStoreFn(o);
}
extern macro UnsafeCastObjectToCanUseSameAccessorFn(Object):
CanUseSameAccessorFn;
- unsafe_cast<CanUseSameAccessorFn>(o: Object): CanUseSameAccessorFn {
+ UnsafeCast<CanUseSameAccessorFn>(o: Object): CanUseSameAccessorFn {
return UnsafeCastObjectToCanUseSameAccessorFn(o);
}
@@ -284,8 +283,7 @@ module array {
assert(comparefn == Undefined);
if (TaggedIsSmi(x) && TaggedIsSmi(y)) {
- // TODO(szuend): Replace with a fast CallCFunction call.
- return SmiLexicographicCompare(context, x, y);
+ return SmiLexicographicCompare(UnsafeCast<Smi>(x), UnsafeCast<Smi>(y));
}
// 5. Let xString be ? ToString(x).
@@ -311,7 +309,7 @@ module array {
builtin SortCompareUserFn(
context: Context, comparefn: Object, x: Object, y: Object): Number {
assert(comparefn != Undefined);
- const cmpfn: Callable = unsafe_cast<Callable>(comparefn);
+ const cmpfn: Callable = UnsafeCast<Callable>(comparefn);
// a. Let v be ? ToNumber(? Call(comparefn, undefined, x, y)).
const v: Number =
@@ -324,16 +322,16 @@ module array {
return v;
}
- builtin CanUseSameAccessor<ElementsAccessor : type>(
+ builtin CanUseSameAccessor<ElementsAccessor: type>(
context: Context, receiver: JSReceiver, initialReceiverMap: Object,
initialReceiverLength: Number): Boolean {
assert(IsJSArray(receiver));
- let a: JSArray = unsafe_cast<JSArray>(receiver);
+ let a: JSArray = UnsafeCast<JSArray>(receiver);
if (a.map != initialReceiverMap) return False;
assert(TaggedIsSmi(initialReceiverLength));
- let originalLength: Smi = unsafe_cast<Smi>(initialReceiverLength);
+ let originalLength: Smi = UnsafeCast<Smi>(initialReceiverLength);
if (a.length_fast != originalLength) return False;
return True;
@@ -349,27 +347,27 @@ module array {
CanUseSameAccessor<DictionaryElements>(
context: Context, receiver: JSReceiver, initialReceiverMap: Object,
initialReceiverLength: Number): Boolean {
- let obj: JSReceiver = unsafe_cast<JSReceiver>(receiver);
+ let obj: JSReceiver = UnsafeCast<JSReceiver>(receiver);
return SelectBooleanConstant(obj.map == initialReceiverMap);
}
macro CallCompareFn(
context: Context, sortState: FixedArray, x: Object, y: Object): Number
- labels Bailout {
+ labels Bailout {
const userCmpFn: Object = sortState[kUserCmpFnIdx];
const sortCompare: CompareBuiltinFn =
- unsafe_cast<CompareBuiltinFn>(sortState[kSortComparePtrIdx]);
+ UnsafeCast<CompareBuiltinFn>(sortState[kSortComparePtrIdx]);
const result: Number = sortCompare(context, userCmpFn, x, y);
const receiver: JSReceiver = GetReceiver(sortState);
const initialReceiverMap: Object = sortState[kInitialReceiverMapIdx];
const initialReceiverLength: Number =
- unsafe_cast<Number>(sortState[kInitialReceiverLengthIdx]);
- const CanUseSameAccessor: CanUseSameAccessorFn =
+ UnsafeCast<Number>(sortState[kInitialReceiverLengthIdx]);
+ const canUseSameAccessorFn: CanUseSameAccessorFn =
GetCanUseSameAccessorFn(sortState);
- if (!CanUseSameAccessor(
+ if (!canUseSameAccessorFn(
context, receiver, initialReceiverMap, initialReceiverLength)) {
goto Bailout;
}
@@ -384,40 +382,40 @@ module array {
const receiver: JSReceiver = GetReceiver(sortState);
if (sortState[kAccessorIdx] == kGenericElementsAccessorId) return receiver;
- const object: JSObject = unsafe_cast<JSObject>(receiver);
+ const object: JSObject = UnsafeCast<JSObject>(receiver);
return object.elements;
}
macro GetLoadFn(sortState: FixedArray): LoadFn {
- return unsafe_cast<LoadFn>(sortState[kLoadFnIdx]);
+ return UnsafeCast<LoadFn>(sortState[kLoadFnIdx]);
}
macro GetStoreFn(sortState: FixedArray): StoreFn {
- return unsafe_cast<StoreFn>(sortState[kStoreFnIdx]);
+ return UnsafeCast<StoreFn>(sortState[kStoreFnIdx]);
}
macro GetCanUseSameAccessorFn(sortState: FixedArray): CanUseSameAccessorFn {
- return unsafe_cast<CanUseSameAccessorFn>(
+ return UnsafeCast<CanUseSameAccessorFn>(
sortState[kCanUseSameAccessorFnIdx]);
}
macro GetReceiver(sortState: FixedArray): JSReceiver {
- return unsafe_cast<JSReceiver>(sortState[kReceiverIdx]);
+ return UnsafeCast<JSReceiver>(sortState[kReceiverIdx]);
}
// Returns the temporary array without changing its size.
macro GetTempArray(sortState: FixedArray): FixedArray {
- return unsafe_cast<FixedArray>(sortState[kTempArrayIdx]);
+ return UnsafeCast<FixedArray>(sortState[kTempArrayIdx]);
}
// Re-loading the stack-size is done in a few places. The small macro allows
// for easier invariant checks at all use sites.
macro GetPendingRunsSize(sortState: FixedArray): Smi {
assert(TaggedIsSmi(sortState[kPendingRunsSizeIdx]));
- const stack_size: Smi = unsafe_cast<Smi>(sortState[kPendingRunsSizeIdx]);
+ const stackSize: Smi = UnsafeCast<Smi>(sortState[kPendingRunsSizeIdx]);
- assert(stack_size >= 0);
- return stack_size;
+ assert(stackSize >= 0);
+ return stackSize;
}
macro SetPendingRunsSize(sortState: FixedArray, value: Smi) {
@@ -425,7 +423,7 @@ module array {
}
macro GetPendingRunBase(pendingRuns: FixedArray, run: Smi): Smi {
- return unsafe_cast<Smi>(pendingRuns[run << 1]);
+ return UnsafeCast<Smi>(pendingRuns[run << 1]);
}
macro SetPendingRunBase(pendingRuns: FixedArray, run: Smi, value: Smi) {
@@ -433,7 +431,7 @@ module array {
}
macro GetPendingRunLength(pendingRuns: FixedArray, run: Smi): Smi {
- return unsafe_cast<Smi>(pendingRuns[(run << 1) + 1]);
+ return UnsafeCast<Smi>(pendingRuns[(run << 1) + 1]);
}
macro SetPendingRunLength(pendingRuns: FixedArray, run: Smi, value: Smi) {
@@ -443,38 +441,37 @@ module array {
macro PushRun(sortState: FixedArray, base: Smi, length: Smi) {
assert(GetPendingRunsSize(sortState) < kMaxMergePending);
- const stack_size: Smi = GetPendingRunsSize(sortState);
- const pending_runs: FixedArray =
- unsafe_cast<FixedArray>(sortState[kPendingRunsIdx]);
+ const stackSize: Smi = GetPendingRunsSize(sortState);
+ const pendingRuns: FixedArray =
+ UnsafeCast<FixedArray>(sortState[kPendingRunsIdx]);
- SetPendingRunBase(pending_runs, stack_size, base);
- SetPendingRunLength(pending_runs, stack_size, length);
+ SetPendingRunBase(pendingRuns, stackSize, base);
+ SetPendingRunLength(pendingRuns, stackSize, length);
- SetPendingRunsSize(sortState, stack_size + 1);
+ SetPendingRunsSize(sortState, stackSize + 1);
}
// Returns the temporary array and makes sure that it is big enough.
// TODO(szuend): Implement a better re-size strategy.
macro GetTempArray(sortState: FixedArray, requestedSize: Smi): FixedArray {
- const min_size: Smi = SmiMax(kSortStateTempSize, requestedSize);
+ const minSize: Smi = SmiMax(kSortStateTempSize, requestedSize);
- const current_size: Smi = unsafe_cast<Smi>(sortState[kTempArraySizeIdx]);
- if (current_size >= min_size) {
+ const currentSize: Smi = UnsafeCast<Smi>(sortState[kTempArraySizeIdx]);
+ if (currentSize >= minSize) {
return GetTempArray(sortState);
}
- const temp_array: FixedArray =
- AllocateZeroedFixedArray(convert<intptr>(min_size));
- FillFixedArrayWithSmiZero(temp_array, min_size);
+ const tempArray: FixedArray =
+ AllocateZeroedFixedArray(Convert<intptr>(minSize));
- sortState[kTempArraySizeIdx] = min_size;
- sortState[kTempArrayIdx] = temp_array;
- return temp_array;
+ sortState[kTempArraySizeIdx] = minSize;
+ sortState[kTempArrayIdx] = tempArray;
+ return tempArray;
}
// This macro jumps to the Bailout label iff kBailoutStatus is kFailure.
macro EnsureSuccess(sortState: FixedArray) labels Bailout {
- const status: Smi = unsafe_cast<Smi>(sortState[kBailoutStatusIdx]);
+ const status: Smi = UnsafeCast<Smi>(sortState[kBailoutStatusIdx]);
if (status == kFailure) goto Bailout;
}
@@ -489,17 +486,18 @@ module array {
// or the return value.
macro CallLoad(
- context: Context, sortState: FixedArray, Load: LoadFn,
- elements: HeapObject, index: Smi): Object labels Bailout {
- const result: Object = Load(context, sortState, elements, index);
+ context: Context, sortState: FixedArray, load: LoadFn,
+ elements: HeapObject, index: Smi): Object
+ labels Bailout {
+ const result: Object = load(context, sortState, elements, index);
EnsureSuccess(sortState) otherwise Bailout;
return result;
}
macro CallStore(
- context: Context, sortState: FixedArray, Store: StoreFn,
+ context: Context, sortState: FixedArray, store: StoreFn,
elements: HeapObject, index: Smi, value: Object) labels Bailout {
- Store(context, sortState, elements, index, value);
+ store(context, sortState, elements, index, value);
EnsureSuccess(sortState) otherwise Bailout;
}
@@ -521,21 +519,21 @@ module array {
}
macro CallGallopRight(
- context: Context, sortState: FixedArray, Load: LoadFn, key: Object,
+ context: Context, sortState: FixedArray, load: LoadFn, key: Object,
base: Smi, length: Smi, hint: Smi, useTempArray: Boolean): Smi
- labels Bailout {
+ labels Bailout {
const result: Smi = GallopRight(
- context, sortState, Load, key, base, length, hint, useTempArray);
+ context, sortState, load, key, base, length, hint, useTempArray);
EnsureSuccess(sortState) otherwise Bailout;
return result;
}
macro CallGallopLeft(
- context: Context, sortState: FixedArray, Load: LoadFn, key: Object,
+ context: Context, sortState: FixedArray, load: LoadFn, key: Object,
base: Smi, length: Smi, hint: Smi, useTempArray: Boolean): Smi
- labels Bailout {
+ labels Bailout {
const result: Smi = GallopLeft(
- context, sortState, Load, key, base, length, hint, useTempArray);
+ context, sortState, load, key, base, length, hint, useTempArray);
EnsureSuccess(sortState) otherwise Bailout;
return result;
}
@@ -551,15 +549,15 @@ module array {
context: Context, sortState: FixedArray): Smi {
const receiver: JSReceiver = GetReceiver(sortState);
- if (IsJSArray(receiver)) return unsafe_cast<JSArray>(receiver).length_fast;
+ if (IsJSArray(receiver)) return UnsafeCast<JSArray>(receiver).length_fast;
const len: Number =
- ToLength_Inline(context, GetProperty(context, receiver, 'length'));
- return unsafe_cast<Smi>(len);
+ ToLength_Inline(context, GetProperty(context, receiver, kLengthString));
+ return UnsafeCast<Smi>(len);
}
macro CopyToTempArray(
- context: Context, sortState: FixedArray, Load: LoadFn,
+ context: Context, sortState: FixedArray, load: LoadFn,
srcElements: HeapObject, srcPos: Smi, tempArray: FixedArray, dstPos: Smi,
length: Smi)
labels Bailout {
@@ -568,15 +566,15 @@ module array {
assert(srcPos <= GetReceiverLengthProperty(context, sortState) - length);
assert(dstPos <= tempArray.length - length);
- let src_idx: Smi = srcPos;
- let dst_idx: Smi = dstPos;
+ let srcIdx: Smi = srcPos;
+ let dstIdx: Smi = dstPos;
let to: Smi = srcPos + length;
- while (src_idx < to) {
+ while (srcIdx < to) {
let element: Object =
- CallLoad(context, sortState, Load, srcElements, src_idx++)
- otherwise Bailout;
- tempArray[dst_idx++] = element;
+ CallLoad(context, sortState, load, srcElements, srcIdx++)
+ otherwise Bailout;
+ tempArray[dstIdx++] = element;
}
}
@@ -588,17 +586,17 @@ module array {
assert(srcPos <= tempArray.length - length);
assert(dstPos <= GetReceiverLengthProperty(context, sortState) - length);
- let Store: StoreFn = GetStoreFn(sortState);
+ let store: StoreFn = GetStoreFn(sortState);
- let src_idx: Smi = srcPos;
- let dst_idx: Smi = dstPos;
+ let srcIdx: Smi = srcPos;
+ let dstIdx: Smi = dstPos;
let to: Smi = srcPos + length;
try {
- while (src_idx < to) {
+ while (srcIdx < to) {
CallStore(
- context, sortState, Store, dstElements, dst_idx++,
- tempArray[src_idx++])
- otherwise Bailout;
+ context, sortState, store, dstElements, dstIdx++,
+ tempArray[srcIdx++])
+ otherwise Bailout;
}
return kSuccess;
}
@@ -616,25 +614,25 @@ module array {
assert(dstPos <= GetReceiverLengthProperty(context, sortState) - length);
try {
- let Load: LoadFn = GetLoadFn(sortState);
- let Store: StoreFn = GetStoreFn(sortState);
+ let load: LoadFn = GetLoadFn(sortState);
+ let store: StoreFn = GetStoreFn(sortState);
if (srcPos < dstPos) {
- let src_idx: Smi = srcPos + length - 1;
- let dst_idx: Smi = dstPos + length - 1;
- while (src_idx >= srcPos) {
+ let srcIdx: Smi = srcPos + length - 1;
+ let dstIdx: Smi = dstPos + length - 1;
+ while (srcIdx >= srcPos) {
CopyElement(
- context, sortState, Load, Store, elements, src_idx--, dst_idx--)
- otherwise Bailout;
+ context, sortState, load, store, elements, srcIdx--, dstIdx--)
+ otherwise Bailout;
}
} else {
- let src_idx: Smi = srcPos;
- let dst_idx: Smi = dstPos;
+ let srcIdx: Smi = srcPos;
+ let dstIdx: Smi = dstPos;
let to: Smi = srcPos + length;
- while (src_idx < to) {
+ while (srcIdx < to) {
CopyElement(
- context, sortState, Load, Store, elements, src_idx++, dst_idx++)
- otherwise Bailout;
+ context, sortState, load, store, elements, srcIdx++, dstIdx++)
+ otherwise Bailout;
}
}
return kSuccess;
@@ -662,8 +660,8 @@ module array {
try {
let elements: HeapObject = ReloadElements(sortState);
- const Load: LoadFn = GetLoadFn(sortState);
- const Store: StoreFn = GetStoreFn(sortState);
+ const load: LoadFn = GetLoadFn(sortState);
+ const store: StoreFn = GetStoreFn(sortState);
let start: Smi = low == startArg ? (startArg + 1) : startArg;
@@ -673,8 +671,8 @@ module array {
let right: Smi = start;
const pivot: Object =
- CallLoad(context, sortState, Load, elements, right)
- otherwise Bailout;
+ CallLoad(context, sortState, load, elements, right)
+ otherwise Bailout;
// Invariants:
// pivot >= all in [low, left).
@@ -684,12 +682,12 @@ module array {
// Find pivot insertion point.
while (left < right) {
const mid: Smi = left + ((right - left) >>> 1);
- const mid_element: Object =
- CallLoad(context, sortState, Load, elements, mid)
- otherwise Bailout;
+ const midElement: Object =
+ CallLoad(context, sortState, load, elements, mid)
+ otherwise Bailout;
const order: Number =
- CallCompareFn(context, sortState, pivot, mid_element)
- otherwise Bailout;
+ CallCompareFn(context, sortState, pivot, midElement)
+ otherwise Bailout;
elements = ReloadElements(sortState);
if (order < 0) {
@@ -709,11 +707,11 @@ module array {
// sort is stable.
// Slide over to make room.
for (let p: Smi = start; p > left; --p) {
- CopyElement(context, sortState, Load, Store, elements, p - 1, p)
- otherwise Bailout;
+ CopyElement(context, sortState, load, store, elements, p - 1, p)
+ otherwise Bailout;
}
- CallStore(context, sortState, Store, elements, left, pivot)
- otherwise Bailout;
+ CallStore(context, sortState, store, elements, left, pivot)
+ otherwise Bailout;
}
return kSuccess;
}
@@ -741,152 +739,150 @@ module array {
// length is always an ascending sequence.
macro CountAndMakeRun(
context: Context, sortState: FixedArray, lowArg: Smi, high: Smi): Smi
- labels Bailout {
+ labels Bailout {
assert(lowArg < high);
let elements: HeapObject = ReloadElements(sortState);
- const Load: LoadFn = GetLoadFn(sortState);
- const Store: StoreFn = GetStoreFn(sortState);
+ const load: LoadFn = GetLoadFn(sortState);
+ const store: StoreFn = GetStoreFn(sortState);
let low: Smi = lowArg + 1;
if (low == high) return 1;
- let run_length: Smi = 2;
+ let runLength: Smi = 2;
- const element_low: Object =
- CallLoad(context, sortState, Load, elements, low) otherwise Bailout;
- const element_low_pred: Object =
- CallLoad(context, sortState, Load, elements, low - 1) otherwise Bailout;
+ const elementLow: Object =
+ CallLoad(context, sortState, load, elements, low) otherwise Bailout;
+ const elementLowPred: Object =
+ CallLoad(context, sortState, load, elements, low - 1) otherwise Bailout;
let order: Number =
- CallCompareFn(context, sortState, element_low, element_low_pred)
- otherwise Bailout;
+ CallCompareFn(context, sortState, elementLow, elementLowPred)
+ otherwise Bailout;
elements = ReloadElements(sortState);
// TODO(szuend): Replace with "order < 0" once Torque supports it.
// Currently the operator<(Number, Number) has return type
// 'never' and uses two labels to branch.
- const is_descending: bool = order < 0 ? true : false;
+ const isDescending: bool = order < 0 ? true : false;
- let previous_element: Object = element_low;
+ let previousElement: Object = elementLow;
for (let idx: Smi = low + 1; idx < high; ++idx) {
- const current_element: Object =
- CallLoad(context, sortState, Load, elements, idx) otherwise Bailout;
- order =
- CallCompareFn(context, sortState, current_element, previous_element)
- otherwise Bailout;
+ const currentElement: Object =
+ CallLoad(context, sortState, load, elements, idx) otherwise Bailout;
+ order = CallCompareFn(context, sortState, currentElement, previousElement)
+ otherwise Bailout;
elements = ReloadElements(sortState);
- if (is_descending) {
+ if (isDescending) {
if (order >= 0) break;
} else {
if (order < 0) break;
}
- previous_element = current_element;
- ++run_length;
+ previousElement = currentElement;
+ ++runLength;
}
- if (is_descending) {
+ if (isDescending) {
ReverseRange(
- context, sortState, Load, Store, elements, lowArg,
- lowArg + run_length)
- otherwise Bailout;
+ context, sortState, load, store, elements, lowArg, lowArg + runLength)
+ otherwise Bailout;
}
- return run_length;
+ return runLength;
}
macro ReverseRange(
- context: Context, sortState: FixedArray, Load: LoadFn, Store: StoreFn,
+ context: Context, sortState: FixedArray, load: LoadFn, store: StoreFn,
elements: HeapObject, from: Smi, to: Smi)
labels Bailout {
let low: Smi = from;
let high: Smi = to - 1;
while (low < high) {
- const element_low: Object =
- CallLoad(context, sortState, Load, elements, low) otherwise Bailout;
- const element_high: Object =
- CallLoad(context, sortState, Load, elements, high) otherwise Bailout;
- CallStore(context, sortState, Store, elements, low++, element_high)
- otherwise Bailout;
- CallStore(context, sortState, Store, elements, high--, element_low)
- otherwise Bailout;
+ const elementLow: Object =
+ CallLoad(context, sortState, load, elements, low) otherwise Bailout;
+ const elementHigh: Object =
+ CallLoad(context, sortState, load, elements, high) otherwise Bailout;
+ CallStore(context, sortState, store, elements, low++, elementHigh)
+ otherwise Bailout;
+ CallStore(context, sortState, store, elements, high--, elementLow)
+ otherwise Bailout;
}
}
// Merges the two runs at stack indices i and i + 1.
// Returns kFailure if we need to bailout, kSuccess otherwise.
builtin MergeAt(context: Context, sortState: FixedArray, i: Smi): Smi {
- const stack_size: Smi = GetPendingRunsSize(sortState);
+ const stackSize: Smi = GetPendingRunsSize(sortState);
// We are only allowed to either merge the two top-most runs, or leave
// the top most run alone and merge the two next runs.
- assert(stack_size >= 2);
+ assert(stackSize >= 2);
assert(i >= 0);
- assert(i == stack_size - 2 || i == stack_size - 3);
+ assert(i == stackSize - 2 || i == stackSize - 3);
let elements: HeapObject = ReloadElements(sortState);
- const Load: LoadFn = GetLoadFn(sortState);
-
- const pending_runs: FixedArray =
- unsafe_cast<FixedArray>(sortState[kPendingRunsIdx]);
- let base_a: Smi = GetPendingRunBase(pending_runs, i);
- let length_a: Smi = GetPendingRunLength(pending_runs, i);
- let base_b: Smi = GetPendingRunBase(pending_runs, i + 1);
- let length_b: Smi = GetPendingRunLength(pending_runs, i + 1);
- assert(length_a > 0 && length_b > 0);
- assert(base_a + length_a == base_b);
+ const load: LoadFn = GetLoadFn(sortState);
+
+ const pendingRuns: FixedArray =
+ UnsafeCast<FixedArray>(sortState[kPendingRunsIdx]);
+ let baseA: Smi = GetPendingRunBase(pendingRuns, i);
+ let lengthA: Smi = GetPendingRunLength(pendingRuns, i);
+ let baseB: Smi = GetPendingRunBase(pendingRuns, i + 1);
+ let lengthB: Smi = GetPendingRunLength(pendingRuns, i + 1);
+ assert(lengthA > 0 && lengthB > 0);
+ assert(baseA + lengthA == baseB);
// Record the length of the combined runs; if i is the 3rd-last run now,
// also slide over the last run (which isn't involved in this merge).
// The current run i + 1 goes away in any case.
- SetPendingRunLength(pending_runs, i, length_a + length_b);
- if (i == stack_size - 3) {
- const base: Smi = GetPendingRunBase(pending_runs, i + 2);
- const length: Smi = GetPendingRunLength(pending_runs, i + 2);
- SetPendingRunBase(pending_runs, i + 1, base);
- SetPendingRunLength(pending_runs, i + 1, length);
+ SetPendingRunLength(pendingRuns, i, lengthA + lengthB);
+ if (i == stackSize - 3) {
+ const base: Smi = GetPendingRunBase(pendingRuns, i + 2);
+ const length: Smi = GetPendingRunLength(pendingRuns, i + 2);
+ SetPendingRunBase(pendingRuns, i + 1, base);
+ SetPendingRunLength(pendingRuns, i + 1, length);
}
- SetPendingRunsSize(sortState, stack_size - 1);
+ SetPendingRunsSize(sortState, stackSize - 1);
try {
// Where does b start in a? Elements in a before that can be ignored,
// because they are already in place.
- const key_right: Object =
- CallLoad(context, sortState, Load, elements, base_b)
- otherwise Bailout;
+ const keyRight: Object =
+ CallLoad(context, sortState, load, elements, baseB)
+ otherwise Bailout;
const k: Smi = CallGallopRight(
- context, sortState, Load, key_right, base_a, length_a, 0, False)
- otherwise Bailout;
+ context, sortState, load, keyRight, baseA, lengthA, 0, False)
+ otherwise Bailout;
elements = ReloadElements(sortState);
assert(k >= 0);
- base_a = base_a + k;
- length_a = length_a - k;
- if (length_a == 0) return kSuccess;
- assert(length_a > 0);
+ baseA = baseA + k;
+ lengthA = lengthA - k;
+ if (lengthA == 0) return kSuccess;
+ assert(lengthA > 0);
// Where does a end in b? Elements in b after that can be ignored,
// because they are already in place.
- let key_left: Object =
- CallLoad(context, sortState, Load, elements, base_a + length_a - 1)
- otherwise Bailout;
- length_b = CallGallopLeft(
- context, sortState, Load, key_left, base_b, length_b, length_b - 1,
- False) otherwise Bailout;
+ let keyLeft: Object =
+ CallLoad(context, sortState, load, elements, baseA + lengthA - 1)
+ otherwise Bailout;
+ lengthB = CallGallopLeft(
+ context, sortState, load, keyLeft, baseB, lengthB, lengthB - 1, False)
+ otherwise Bailout;
elements = ReloadElements(sortState);
- assert(length_b >= 0);
- if (length_b == 0) return kSuccess;
+ assert(lengthB >= 0);
+ if (lengthB == 0) return kSuccess;
// Merge what remains of the runs, using a temp array with
- // min(length_a, length_b) elements.
- if (length_a <= length_b) {
- MergeLow(context, sortState, base_a, length_a, base_b, length_b)
- otherwise Bailout;
+ // min(lengthA, lengthB) elements.
+ if (lengthA <= lengthB) {
+ MergeLow(context, sortState, baseA, lengthA, baseB, lengthB)
+ otherwise Bailout;
} else {
- MergeHigh(context, sortState, base_a, length_a, base_b, length_b)
- otherwise Bailout;
+ MergeHigh(context, sortState, baseA, lengthA, baseB, lengthB)
+ otherwise Bailout;
}
return kSuccess;
}
@@ -919,111 +915,111 @@ module array {
// pretending that array[base - 1] is minus infinity and array[base + len]
// is plus infinity. In other words, key belongs at index base + k.
builtin GallopLeft(
- context: Context, sortState: FixedArray, Load: LoadFn, key: Object,
+ context: Context, sortState: FixedArray, load: LoadFn, key: Object,
base: Smi, length: Smi, hint: Smi, useTempArray: Boolean): Smi {
assert(length > 0 && base >= 0);
assert(0 <= hint && hint < length);
- let last_ofs: Smi = 0;
+ let lastOfs: Smi = 0;
let offset: Smi = 1;
try {
- const base_hint_element: Object = CallLoad(
- context, sortState, Load,
+ const baseHintElement: Object = CallLoad(
+ context, sortState, load,
LoadElementsOrTempArray(useTempArray, sortState), base + hint)
- otherwise Bailout;
+ otherwise Bailout;
let order: Number =
- CallCompareFn(context, sortState, base_hint_element, key)
- otherwise Bailout;
+ CallCompareFn(context, sortState, baseHintElement, key)
+ otherwise Bailout;
if (order < 0) {
// a[base + hint] < key: gallop right, until
- // a[base + hint + last_ofs] < key <= a[base + hint + offset].
+ // a[base + hint + lastOfs] < key <= a[base + hint + offset].
// a[base + length - 1] is highest.
- let max_ofs: Smi = length - hint;
- while (offset < max_ofs) {
- const offset_element: Object = CallLoad(
- context, sortState, Load,
+ let maxOfs: Smi = length - hint;
+ while (offset < maxOfs) {
+ const offsetElement: Object = CallLoad(
+ context, sortState, load,
LoadElementsOrTempArray(useTempArray, sortState),
base + hint + offset)
- otherwise Bailout;
- order = CallCompareFn(context, sortState, offset_element, key)
- otherwise Bailout;
+ otherwise Bailout;
+ order = CallCompareFn(context, sortState, offsetElement, key)
+ otherwise Bailout;
// a[base + hint + offset] >= key? Break.
if (order >= 0) break;
- last_ofs = offset;
+ lastOfs = offset;
offset = (offset << 1) + 1;
// Integer overflow.
- if (offset <= 0) offset = max_ofs;
+ if (offset <= 0) offset = maxOfs;
}
- if (offset > max_ofs) offset = max_ofs;
+ if (offset > maxOfs) offset = maxOfs;
// Translate back to positive offsets relative to base.
- last_ofs = last_ofs + hint;
+ lastOfs = lastOfs + hint;
offset = offset + hint;
} else {
// key <= a[base + hint]: gallop left, until
- // a[base + hint - offset] < key <= a[base + hint - last_ofs].
+ // a[base + hint - offset] < key <= a[base + hint - lastOfs].
assert(order >= 0);
// a[base + hint] is lowest.
- let max_ofs: Smi = hint + 1;
- while (offset < max_ofs) {
- const offset_element: Object = CallLoad(
- context, sortState, Load,
+ let maxOfs: Smi = hint + 1;
+ while (offset < maxOfs) {
+ const offsetElement: Object = CallLoad(
+ context, sortState, load,
LoadElementsOrTempArray(useTempArray, sortState),
base + hint - offset)
- otherwise Bailout;
- order = CallCompareFn(context, sortState, offset_element, key)
- otherwise Bailout;
+ otherwise Bailout;
+ order = CallCompareFn(context, sortState, offsetElement, key)
+ otherwise Bailout;
if (order < 0) break;
- last_ofs = offset;
+ lastOfs = offset;
offset = (offset << 1) + 1;
// Integer overflow.
- if (offset <= 0) offset = max_ofs;
+ if (offset <= 0) offset = maxOfs;
}
- if (offset > max_ofs) offset = max_ofs;
+ if (offset > maxOfs) offset = maxOfs;
// Translate back to positive offsets relative to base.
- const tmp: Smi = last_ofs;
- last_ofs = hint - offset;
+ const tmp: Smi = lastOfs;
+ lastOfs = hint - offset;
offset = hint - tmp;
}
- assert(-1 <= last_ofs && last_ofs < offset && offset <= length);
+ assert(-1 <= lastOfs && lastOfs < offset && offset <= length);
- // Now a[base+last_ofs] < key <= a[base+offset], so key belongs somewhere
- // to the right of last_ofs but no farther right than offset. Do a binary
+ // Now a[base+lastOfs] < key <= a[base+offset], so key belongs somewhere
+ // to the right of lastOfs but no farther right than offset. Do a binary
// search, with invariant:
- // a[base + last_ofs - 1] < key <= a[base + offset].
- last_ofs++;
- while (last_ofs < offset) {
- const m: Smi = last_ofs + ((offset - last_ofs) >>> 1);
+ // a[base + lastOfs - 1] < key <= a[base + offset].
+ lastOfs++;
+ while (lastOfs < offset) {
+ const m: Smi = lastOfs + ((offset - lastOfs) >>> 1);
- const base_m_element: Object = CallLoad(
- context, sortState, Load,
+ const baseMElement: Object = CallLoad(
+ context, sortState, load,
LoadElementsOrTempArray(useTempArray, sortState), base + m)
- otherwise Bailout;
- order = CallCompareFn(context, sortState, base_m_element, key)
- otherwise Bailout;
+ otherwise Bailout;
+ order = CallCompareFn(context, sortState, baseMElement, key)
+ otherwise Bailout;
if (order < 0) {
- last_ofs = m + 1; // a[base + m] < key.
+ lastOfs = m + 1; // a[base + m] < key.
} else {
offset = m; // key <= a[base + m].
}
}
// so a[base + offset - 1] < key <= a[base + offset].
- assert(last_ofs == offset);
+ assert(lastOfs == offset);
assert(0 <= offset && offset <= length);
return offset;
}
@@ -1042,109 +1038,109 @@ module array {
//
// or kFailure on error.
builtin GallopRight(
- context: Context, sortState: FixedArray, Load: LoadFn, key: Object,
+ context: Context, sortState: FixedArray, load: LoadFn, key: Object,
base: Smi, length: Smi, hint: Smi, useTempArray: Boolean): Smi {
assert(length > 0 && base >= 0);
assert(0 <= hint && hint < length);
- let last_ofs: Smi = 0;
+ let lastOfs: Smi = 0;
let offset: Smi = 1;
try {
- const base_hint_element: Object = CallLoad(
- context, sortState, Load,
+ const baseHintElement: Object = CallLoad(
+ context, sortState, load,
LoadElementsOrTempArray(useTempArray, sortState), base + hint)
- otherwise Bailout;
+ otherwise Bailout;
let order: Number =
- CallCompareFn(context, sortState, key, base_hint_element)
- otherwise Bailout;
+ CallCompareFn(context, sortState, key, baseHintElement)
+ otherwise Bailout;
if (order < 0) {
// key < a[base + hint]: gallop left, until
- // a[base + hint - offset] <= key < a[base + hint - last_ofs].
+ // a[base + hint - offset] <= key < a[base + hint - lastOfs].
// a[base + hint] is lowest.
- let max_ofs: Smi = hint + 1;
- while (offset < max_ofs) {
- const offset_element: Object = CallLoad(
- context, sortState, Load,
+ let maxOfs: Smi = hint + 1;
+ while (offset < maxOfs) {
+ const offsetElement: Object = CallLoad(
+ context, sortState, load,
LoadElementsOrTempArray(useTempArray, sortState),
base + hint - offset)
- otherwise Bailout;
- order = CallCompareFn(context, sortState, key, offset_element)
- otherwise Bailout;
+ otherwise Bailout;
+ order = CallCompareFn(context, sortState, key, offsetElement)
+ otherwise Bailout;
if (order >= 0) break;
- last_ofs = offset;
+ lastOfs = offset;
offset = (offset << 1) + 1;
// Integer overflow.
- if (offset <= 0) offset = max_ofs;
+ if (offset <= 0) offset = maxOfs;
}
- if (offset > max_ofs) offset = max_ofs;
+ if (offset > maxOfs) offset = maxOfs;
// Translate back to positive offsets relative to base.
- const tmp: Smi = last_ofs;
- last_ofs = hint - offset;
+ const tmp: Smi = lastOfs;
+ lastOfs = hint - offset;
offset = hint - tmp;
} else {
// a[base + hint] <= key: gallop right, until
- // a[base + hint + last_ofs] <= key < a[base + hint + offset].
+ // a[base + hint + lastOfs] <= key < a[base + hint + offset].
// a[base + length - 1] is highest.
- let max_ofs: Smi = length - hint;
- while (offset < max_ofs) {
- const offset_element: Object = CallLoad(
- context, sortState, Load,
+ let maxOfs: Smi = length - hint;
+ while (offset < maxOfs) {
+ const offsetElement: Object = CallLoad(
+ context, sortState, load,
LoadElementsOrTempArray(useTempArray, sortState),
base + hint + offset)
- otherwise Bailout;
- order = CallCompareFn(context, sortState, key, offset_element)
- otherwise Bailout;
+ otherwise Bailout;
+ order = CallCompareFn(context, sortState, key, offsetElement)
+ otherwise Bailout;
// a[base + hint + ofs] <= key.
if (order < 0) break;
- last_ofs = offset;
+ lastOfs = offset;
offset = (offset << 1) + 1;
// Integer overflow.
- if (offset <= 0) offset = max_ofs;
+ if (offset <= 0) offset = maxOfs;
}
- if (offset > max_ofs) offset = max_ofs;
+ if (offset > maxOfs) offset = maxOfs;
// Translate back to positive offests relative to base.
- last_ofs = last_ofs + hint;
+ lastOfs = lastOfs + hint;
offset = offset + hint;
}
- assert(-1 <= last_ofs && last_ofs < offset && offset <= length);
+ assert(-1 <= lastOfs && lastOfs < offset && offset <= length);
- // Now a[base + last_ofs] <= key < a[base + ofs], so key belongs
- // somewhere to the right of last_ofs but no farther right than ofs.
+ // Now a[base + lastOfs] <= key < a[base + ofs], so key belongs
+ // somewhere to the right of lastOfs but no farther right than ofs.
// Do a binary search, with invariant
- // a[base + last_ofs - 1] < key <= a[base + ofs].
- last_ofs++;
- while (last_ofs < offset) {
- const m: Smi = last_ofs + ((offset - last_ofs) >>> 1);
+ // a[base + lastOfs - 1] < key <= a[base + ofs].
+ lastOfs++;
+ while (lastOfs < offset) {
+ const m: Smi = lastOfs + ((offset - lastOfs) >>> 1);
- const base_m_element: Object = CallLoad(
- context, sortState, Load,
+ const baseMElement: Object = CallLoad(
+ context, sortState, load,
LoadElementsOrTempArray(useTempArray, sortState), base + m)
- otherwise Bailout;
- order = CallCompareFn(context, sortState, key, base_m_element)
- otherwise Bailout;
+ otherwise Bailout;
+ order = CallCompareFn(context, sortState, key, baseMElement)
+ otherwise Bailout;
if (order < 0) {
offset = m; // key < a[base + m].
} else {
- last_ofs = m + 1; // a[base + m] <= key.
+ lastOfs = m + 1; // a[base + m] <= key.
}
}
// so a[base + offset - 1] <= key < a[base + offset].
- assert(last_ofs == offset);
+ assert(lastOfs == offset);
assert(0 <= offset && offset <= length);
return offset;
}
@@ -1153,374 +1149,373 @@ module array {
}
}
- // Copies a single element inside the array/object (NOT the temp_array).
+ // Copies a single element inside the array/object (NOT the tempArray).
macro CopyElement(
- context: Context, sortState: FixedArray, Load: LoadFn, Store: StoreFn,
+ context: Context, sortState: FixedArray, load: LoadFn, store: StoreFn,
elements: HeapObject, from: Smi, to: Smi)
labels Bailout {
- const element: Object = CallLoad(context, sortState, Load, elements, from)
- otherwise Bailout;
- CallStore(context, sortState, Store, elements, to, element)
- otherwise Bailout;
- }
-
- // Merge the length_a elements starting at base_a with the length_b elements
- // starting at base_b in a stable way, in-place. length_a and length_b must
- // be > 0, and base_a + length_a == base_b. Must also have that
- // array[base_b] < array[base_a],
- // that array[base_a + length_a - 1] belongs at the end of the merge,
- // and should have length_a <= length_b.
+ const element: Object = CallLoad(context, sortState, load, elements, from)
+ otherwise Bailout;
+ CallStore(context, sortState, store, elements, to, element)
+ otherwise Bailout;
+ }
+
+ // Merge the lengthA elements starting at baseA with the lengthB elements
+ // starting at baseB in a stable way, in-place. lengthA and lengthB must
+ // be > 0, and baseA + lengthA == baseB. Must also have that
+ // array[baseB] < array[baseA],
+ // that array[baseA + lengthA - 1] belongs at the end of the merge,
+ // and should have lengthA <= lengthB.
macro MergeLow(
- context: Context, sortState: FixedArray, baseA: Smi, lengthA: Smi,
- baseB: Smi, lengthB: Smi)
+ context: Context, sortState: FixedArray, baseA: Smi, lengthAArg: Smi,
+ baseB: Smi, lengthBArg: Smi)
labels Bailout {
- assert(0 < lengthA && 0 < lengthB);
+ assert(0 < lengthAArg && 0 < lengthBArg);
assert(0 <= baseA && 0 < baseB);
- assert(baseA + lengthA == baseB);
+ assert(baseA + lengthAArg == baseB);
- let length_a: Smi = lengthA;
- let length_b: Smi = lengthB;
+ let lengthA: Smi = lengthAArg;
+ let lengthB: Smi = lengthBArg;
let elements: HeapObject = ReloadElements(sortState);
- const LoadF: LoadFn = GetLoadFn(sortState);
- const Store: StoreFn = GetStoreFn(sortState);
+ const load: LoadFn = GetLoadFn(sortState);
+ const store: StoreFn = GetStoreFn(sortState);
- const temp_array: FixedArray = GetTempArray(sortState, length_a);
+ const tempArray: FixedArray = GetTempArray(sortState, lengthA);
CopyToTempArray(
- context, sortState, LoadF, elements, baseA, temp_array, 0, length_a)
- otherwise Bailout;
+ context, sortState, load, elements, baseA, tempArray, 0, lengthA)
+ otherwise Bailout;
let dest: Smi = baseA;
- let cursor_temp: Smi = 0;
- let cursor_b: Smi = baseB;
+ let cursorTemp: Smi = 0;
+ let cursorB: Smi = baseB;
- CopyElement(context, sortState, LoadF, Store, elements, cursor_b++, dest++)
- otherwise Bailout;
+ CopyElement(context, sortState, load, store, elements, cursorB++, dest++)
+ otherwise Bailout;
try {
- if (--length_b == 0) goto Succeed;
- if (length_a == 1) goto CopyB;
+ if (--lengthB == 0) goto Succeed;
+ if (lengthA == 1) goto CopyB;
- let min_gallop: Smi = unsafe_cast<Smi>(sortState[kMinGallopIdx]);
+ let minGallop: Smi = UnsafeCast<Smi>(sortState[kMinGallopIdx]);
// TODO(szuend): Replace with something that does not have a runtime
// overhead as soon as its available in Torque.
while (Int32TrueConstant()) {
- let nof_wins_a: Smi = 0; // # of times A won in a row.
- let nof_wins_b: Smi = 0; // # of times B won in a row.
+ let nofWinsA: Smi = 0; // # of times A won in a row.
+ let nofWinsB: Smi = 0; // # of times B won in a row.
// Do the straightforward thing until (if ever) one run appears to
// win consistently.
// TODO(szuend): Replace with something that does not have a runtime
// overhead as soon as its available in Torque.
while (Int32TrueConstant()) {
- assert(length_a > 1 && length_b > 0);
-
- let element_b: Object =
- CallLoad(context, sortState, LoadF, elements, cursor_b)
- otherwise Bailout;
- let order: Number = CallCompareFn(
- context, sortState, element_b, temp_array[cursor_temp])
- otherwise Bailout;
+ assert(lengthA > 1 && lengthB > 0);
+
+ let elementB: Object =
+ CallLoad(context, sortState, load, elements, cursorB)
+ otherwise Bailout;
+ let order: Number =
+ CallCompareFn(context, sortState, elementB, tempArray[cursorTemp])
+ otherwise Bailout;
elements = ReloadElements(sortState);
if (order < 0) {
CopyElement(
- context, sortState, LoadF, Store, elements, cursor_b, dest)
- otherwise Bailout;
+ context, sortState, load, store, elements, cursorB, dest)
+ otherwise Bailout;
- ++cursor_b;
+ ++cursorB;
++dest;
- ++nof_wins_b;
- --length_b;
- nof_wins_a = 0;
+ ++nofWinsB;
+ --lengthB;
+ nofWinsA = 0;
- if (length_b == 0) goto Succeed;
- if (nof_wins_b >= min_gallop) break;
+ if (lengthB == 0) goto Succeed;
+ if (nofWinsB >= minGallop) break;
} else {
CallStore(
- context, sortState, Store, elements, dest,
- temp_array[cursor_temp])
- otherwise Bailout;
+ context, sortState, store, elements, dest,
+ tempArray[cursorTemp])
+ otherwise Bailout;
- ++cursor_temp;
+ ++cursorTemp;
++dest;
- ++nof_wins_a;
- --length_a;
- nof_wins_b = 0;
+ ++nofWinsA;
+ --lengthA;
+ nofWinsB = 0;
- if (length_a == 1) goto CopyB;
- if (nof_wins_a >= min_gallop) break;
+ if (lengthA == 1) goto CopyB;
+ if (nofWinsA >= minGallop) break;
}
}
// One run is winning so consistently that galloping may be a huge win.
// So try that, and continue galloping until (if ever) neither run
// appears to be winning consistently anymore.
- ++min_gallop;
- let first_iteration: bool = true;
- while (nof_wins_a >= kMinGallopWins || nof_wins_b >= kMinGallopWins ||
- first_iteration) {
- first_iteration = false;
- assert(length_a > 1 && length_b > 0);
-
- min_gallop = SmiMax(1, min_gallop - 1);
- sortState[kMinGallopIdx] = min_gallop;
-
- let key_right: Object =
- CallLoad(context, sortState, LoadF, elements, cursor_b)
- otherwise Bailout;
- nof_wins_a = CallGallopRight(
- context, sortState, Load<TempArrayElements>, key_right,
- cursor_temp, length_a, 0, True) otherwise Bailout;
+ ++minGallop;
+ let firstIteration: bool = true;
+ while (nofWinsA >= kMinGallopWins || nofWinsB >= kMinGallopWins ||
+ firstIteration) {
+ firstIteration = false;
+ assert(lengthA > 1 && lengthB > 0);
+
+ minGallop = SmiMax(1, minGallop - 1);
+ sortState[kMinGallopIdx] = minGallop;
+
+ let keyRight: Object =
+ CallLoad(context, sortState, load, elements, cursorB)
+ otherwise Bailout;
+ nofWinsA = CallGallopRight(
+ context, sortState, Load<TempArrayElements>, keyRight, cursorTemp,
+ lengthA, 0, True) otherwise Bailout;
elements = ReloadElements(sortState);
- assert(nof_wins_a >= 0);
+ assert(nofWinsA >= 0);
- if (nof_wins_a > 0) {
+ if (nofWinsA > 0) {
CallCopyFromTempArray(
- context, sortState, elements, dest, temp_array, cursor_temp,
- nof_wins_a) otherwise Bailout;
- dest = dest + nof_wins_a;
- cursor_temp = cursor_temp + nof_wins_a;
- length_a = length_a - nof_wins_a;
+ context, sortState, elements, dest, tempArray, cursorTemp,
+ nofWinsA) otherwise Bailout;
+ dest = dest + nofWinsA;
+ cursorTemp = cursorTemp + nofWinsA;
+ lengthA = lengthA - nofWinsA;
- if (length_a == 1) goto CopyB;
+ if (lengthA == 1) goto CopyB;
- // length_a == 0 is impossible now if the comparison function is
+ // lengthA == 0 is impossible now if the comparison function is
// consistent, but we can't assume that it is.
- if (length_a == 0) goto Succeed;
+ if (lengthA == 0) goto Succeed;
}
CopyElement(
- context, sortState, LoadF, Store, elements, cursor_b++, dest++)
- otherwise Bailout;
- if (--length_b == 0) goto Succeed;
-
- nof_wins_b = CallGallopLeft(
- context, sortState, LoadF, temp_array[cursor_temp], cursor_b,
- length_b, 0, False)
- otherwise Bailout;
+ context, sortState, load, store, elements, cursorB++, dest++)
+ otherwise Bailout;
+ if (--lengthB == 0) goto Succeed;
+
+ nofWinsB = CallGallopLeft(
+ context, sortState, load, tempArray[cursorTemp], cursorB, lengthB,
+ 0, False)
+ otherwise Bailout;
elements = ReloadElements(sortState);
- assert(nof_wins_b >= 0);
- if (nof_wins_b > 0) {
+ assert(nofWinsB >= 0);
+ if (nofWinsB > 0) {
CallCopyWithinSortArray(
- context, sortState, elements, cursor_b, dest, nof_wins_b)
- otherwise Bailout;
+ context, sortState, elements, cursorB, dest, nofWinsB)
+ otherwise Bailout;
- dest = dest + nof_wins_b;
- cursor_b = cursor_b + nof_wins_b;
- length_b = length_b - nof_wins_b;
+ dest = dest + nofWinsB;
+ cursorB = cursorB + nofWinsB;
+ lengthB = lengthB - nofWinsB;
- if (length_b == 0) goto Succeed;
+ if (lengthB == 0) goto Succeed;
}
CallStore(
- context, sortState, Store, elements, dest++,
- temp_array[cursor_temp++])
- otherwise Bailout;
- if (--length_a == 1) goto CopyB;
+ context, sortState, store, elements, dest++,
+ tempArray[cursorTemp++])
+ otherwise Bailout;
+ if (--lengthA == 1) goto CopyB;
}
- ++min_gallop; // Penalize it for leaving galloping mode
- sortState[kMinGallopIdx] = min_gallop;
+ ++minGallop; // Penalize it for leaving galloping mode
+ sortState[kMinGallopIdx] = minGallop;
}
}
label Succeed {
- if (length_a > 0) {
+ if (lengthA > 0) {
CallCopyFromTempArray(
- context, sortState, elements, dest, temp_array, cursor_temp,
- length_a) otherwise Bailout;
+ context, sortState, elements, dest, tempArray, cursorTemp, lengthA)
+ otherwise Bailout;
}
}
label CopyB {
- assert(length_a == 1 && length_b > 0);
+ assert(lengthA == 1 && lengthB > 0);
// The last element of run A belongs at the end of the merge.
CallCopyWithinSortArray(
- context, sortState, elements, cursor_b, dest, length_b)
- otherwise Bailout;
+ context, sortState, elements, cursorB, dest, lengthB)
+ otherwise Bailout;
CallStore(
- context, sortState, Store, elements, dest + length_b,
- temp_array[cursor_temp])
- otherwise Bailout;
+ context, sortState, store, elements, dest + lengthB,
+ tempArray[cursorTemp])
+ otherwise Bailout;
}
}
- // Merge the length_a elements starting at base_a with the length_b elements
- // starting at base_b in a stable way, in-place. length_a and length_b must
- // be > 0. Must also have that array[base_a + length_a - 1] belongs at the
- // end of the merge and should have length_a >= length_b.
+ // Merge the lengthA elements starting at baseA with the lengthB elements
+ // starting at baseB in a stable way, in-place. lengthA and lengthB must
+ // be > 0. Must also have that array[baseA + lengthA - 1] belongs at the
+ // end of the merge and should have lengthA >= lengthB.
macro MergeHigh(
- context: Context, sortState: FixedArray, baseA: Smi, lengthA: Smi,
- baseB: Smi, lengthB: Smi)
+ context: Context, sortState: FixedArray, baseA: Smi, lengthAArg: Smi,
+ baseB: Smi, lengthBArg: Smi)
labels Bailout {
- assert(0 < lengthA && 0 < lengthB);
+ assert(0 < lengthAArg && 0 < lengthBArg);
assert(0 <= baseA && 0 < baseB);
- assert(baseA + lengthA == baseB);
+ assert(baseA + lengthAArg == baseB);
- let length_a: Smi = lengthA;
- let length_b: Smi = lengthB;
+ let lengthA: Smi = lengthAArg;
+ let lengthB: Smi = lengthBArg;
let elements: HeapObject = ReloadElements(sortState);
- const LoadF: LoadFn = GetLoadFn(sortState);
- const Store: StoreFn = GetStoreFn(sortState);
+ const load: LoadFn = GetLoadFn(sortState);
+ const store: StoreFn = GetStoreFn(sortState);
- const temp_array: FixedArray = GetTempArray(sortState, length_b);
+ const tempArray: FixedArray = GetTempArray(sortState, lengthB);
CopyToTempArray(
- context, sortState, LoadF, elements, baseB, temp_array, 0, length_b)
- otherwise Bailout;
+ context, sortState, load, elements, baseB, tempArray, 0, lengthB)
+ otherwise Bailout;
// MergeHigh merges the two runs backwards.
- let dest: Smi = baseB + length_b - 1;
- let cursor_temp: Smi = length_b - 1;
- let cursor_a: Smi = baseA + length_a - 1;
+ let dest: Smi = baseB + lengthB - 1;
+ let cursorTemp: Smi = lengthB - 1;
+ let cursorA: Smi = baseA + lengthA - 1;
- CopyElement(context, sortState, LoadF, Store, elements, cursor_a--, dest--)
- otherwise Bailout;
+ CopyElement(context, sortState, load, store, elements, cursorA--, dest--)
+ otherwise Bailout;
try {
- if (--length_a == 0) goto Succeed;
- if (length_b == 1) goto CopyA;
+ if (--lengthA == 0) goto Succeed;
+ if (lengthB == 1) goto CopyA;
- let min_gallop: Smi = unsafe_cast<Smi>(sortState[kMinGallopIdx]);
+ let minGallop: Smi = UnsafeCast<Smi>(sortState[kMinGallopIdx]);
// TODO(szuend): Replace with something that does not have a runtime
// overhead as soon as its available in Torque.
while (Int32TrueConstant()) {
- let nof_wins_a: Smi = 0; // # of times A won in a row.
- let nof_wins_b: Smi = 0; // # of times B won in a row.
+ let nofWinsA: Smi = 0; // # of times A won in a row.
+ let nofWinsB: Smi = 0; // # of times B won in a row.
// Do the straightforward thing until (if ever) one run appears to
// win consistently.
// TODO(szuend): Replace with something that does not have a runtime
// overhead as soon as its available in Torque.
while (Int32TrueConstant()) {
- assert(length_a > 0 && length_b > 1);
-
- let element_a: Object =
- CallLoad(context, sortState, LoadF, elements, cursor_a)
- otherwise Bailout;
- let order: Number = CallCompareFn(
- context, sortState, temp_array[cursor_temp], element_a)
- otherwise Bailout;
+ assert(lengthA > 0 && lengthB > 1);
+
+ let elementA: Object =
+ CallLoad(context, sortState, load, elements, cursorA)
+ otherwise Bailout;
+ let order: Number =
+ CallCompareFn(context, sortState, tempArray[cursorTemp], elementA)
+ otherwise Bailout;
elements = ReloadElements(sortState);
if (order < 0) {
CopyElement(
- context, sortState, LoadF, Store, elements, cursor_a, dest)
- otherwise Bailout;
+ context, sortState, load, store, elements, cursorA, dest)
+ otherwise Bailout;
- --cursor_a;
+ --cursorA;
--dest;
- ++nof_wins_a;
- --length_a;
- nof_wins_b = 0;
+ ++nofWinsA;
+ --lengthA;
+ nofWinsB = 0;
- if (length_a == 0) goto Succeed;
- if (nof_wins_a >= min_gallop) break;
+ if (lengthA == 0) goto Succeed;
+ if (nofWinsA >= minGallop) break;
} else {
CallStore(
- context, sortState, Store, elements, dest,
- temp_array[cursor_temp])
- otherwise Bailout;
+ context, sortState, store, elements, dest,
+ tempArray[cursorTemp])
+ otherwise Bailout;
- --cursor_temp;
+ --cursorTemp;
--dest;
- ++nof_wins_b;
- --length_b;
- nof_wins_a = 0;
+ ++nofWinsB;
+ --lengthB;
+ nofWinsA = 0;
- if (length_b == 1) goto CopyA;
- if (nof_wins_b >= min_gallop) break;
+ if (lengthB == 1) goto CopyA;
+ if (nofWinsB >= minGallop) break;
}
}
// One run is winning so consistently that galloping may be a huge win.
// So try that, and continue galloping until (if ever) neither run
// appears to be winning consistently anymore.
- ++min_gallop;
- let first_iteration: bool = true;
- while (nof_wins_a >= kMinGallopWins || nof_wins_b >= kMinGallopWins ||
- first_iteration) {
- first_iteration = false;
+ ++minGallop;
+ let firstIteration: bool = true;
+ while (nofWinsA >= kMinGallopWins || nofWinsB >= kMinGallopWins ||
+ firstIteration) {
+ firstIteration = false;
- assert(length_a > 0 && length_b > 1);
+ assert(lengthA > 0 && lengthB > 1);
- min_gallop = SmiMax(1, min_gallop - 1);
- sortState[kMinGallopIdx] = min_gallop;
+ minGallop = SmiMax(1, minGallop - 1);
+ sortState[kMinGallopIdx] = minGallop;
let k: Smi = CallGallopRight(
- context, sortState, LoadF, temp_array[cursor_temp], baseA,
- length_a, length_a - 1, False)
- otherwise Bailout;
+ context, sortState, load, tempArray[cursorTemp], baseA, lengthA,
+ lengthA - 1, False)
+ otherwise Bailout;
elements = ReloadElements(sortState);
assert(k >= 0);
- nof_wins_a = length_a - k;
+ nofWinsA = lengthA - k;
- if (nof_wins_a > 0) {
- dest = dest - nof_wins_a;
- cursor_a = cursor_a - nof_wins_a;
+ if (nofWinsA > 0) {
+ dest = dest - nofWinsA;
+ cursorA = cursorA - nofWinsA;
CallCopyWithinSortArray(
- context, sortState, elements, cursor_a + 1, dest + 1,
- nof_wins_a)
- otherwise Bailout;
+ context, sortState, elements, cursorA + 1, dest + 1, nofWinsA)
+ otherwise Bailout;
- length_a = length_a - nof_wins_a;
- if (length_a == 0) goto Succeed;
+ lengthA = lengthA - nofWinsA;
+ if (lengthA == 0) goto Succeed;
}
CallStore(
- context, sortState, Store, elements, dest--,
- temp_array[cursor_temp--])
- otherwise Bailout;
- if (--length_b == 1) goto CopyA;
+ context, sortState, store, elements, dest--,
+ tempArray[cursorTemp--])
+ otherwise Bailout;
+ if (--lengthB == 1) goto CopyA;
let key: Object =
- CallLoad(context, sortState, LoadF, elements, cursor_a)
- otherwise Bailout;
+ CallLoad(context, sortState, load, elements, cursorA)
+ otherwise Bailout;
k = CallGallopLeft(
- context, sortState, Load<TempArrayElements>, key, 0, length_b,
- length_b - 1, True) otherwise Bailout;
+ context, sortState, Load<TempArrayElements>, key, 0, lengthB,
+ lengthB - 1, True) otherwise Bailout;
elements = ReloadElements(sortState);
assert(k >= 0);
- nof_wins_b = length_b - k;
+ nofWinsB = lengthB - k;
- if (nof_wins_b > 0) {
- dest = dest - nof_wins_b;
- cursor_temp = cursor_temp - nof_wins_b;
+ if (nofWinsB > 0) {
+ dest = dest - nofWinsB;
+ cursorTemp = cursorTemp - nofWinsB;
CallCopyFromTempArray(
- context, sortState, elements, dest + 1, temp_array,
- cursor_temp + 1, nof_wins_b) otherwise Bailout;
+ context, sortState, elements, dest + 1, tempArray,
+ cursorTemp + 1, nofWinsB) otherwise Bailout;
- length_b = length_b - nof_wins_b;
- if (length_b == 1) goto CopyA;
+ lengthB = lengthB - nofWinsB;
+ if (lengthB == 1) goto CopyA;
- // length_b == 0 is impossible now if the comparison function is
+ // lengthB == 0 is impossible now if the comparison function is
// consistent, but we can't assume that it is.
- if (length_b == 0) goto Succeed;
+ if (lengthB == 0) goto Succeed;
}
CopyElement(
- context, sortState, LoadF, Store, elements, cursor_a--, dest--)
- otherwise Bailout;
- if (--length_a == 0) goto Succeed;
+ context, sortState, load, store, elements, cursorA--, dest--)
+ otherwise Bailout;
+ if (--lengthA == 0) goto Succeed;
}
- ++min_gallop;
- sortState[kMinGallopIdx] = min_gallop;
+ ++minGallop;
+ sortState[kMinGallopIdx] = minGallop;
}
}
label Succeed {
- if (length_b > 0) {
- assert(length_a == 0);
+ if (lengthB > 0) {
+ assert(lengthA == 0);
CallCopyFromTempArray(
- context, sortState, elements, dest - (length_b - 1), temp_array, 0,
- length_b) otherwise Bailout;
+ context, sortState, elements, dest - (lengthB - 1), tempArray, 0,
+ lengthB) otherwise Bailout;
}
}
label CopyA {
- assert(length_b == 1 && length_a > 0);
+ assert(lengthB == 1 && lengthA > 0);
// The first element of run B belongs at the front of the merge.
- dest = dest - length_a;
- cursor_a = cursor_a - length_a;
+ dest = dest - lengthA;
+ cursorA = cursorA - lengthA;
CallCopyWithinSortArray(
- context, sortState, elements, cursor_a + 1, dest + 1, length_a)
- otherwise Bailout;
+ context, sortState, elements, cursorA + 1, dest + 1, lengthA)
+ otherwise Bailout;
CallStore(
- context, sortState, Store, elements, dest, temp_array[cursor_temp])
- otherwise Bailout;
+ context, sortState, store, elements, dest, tempArray[cursorTemp])
+ otherwise Bailout;
}
}
@@ -1543,20 +1538,20 @@ module array {
n = n >>> 1;
}
- const min_run_length: Smi = n + r;
- assert(nArg < 64 || (32 <= min_run_length && min_run_length <= 64));
- return min_run_length;
+ const minRunLength: Smi = n + r;
+ assert(nArg < 64 || (32 <= minRunLength && minRunLength <= 64));
+ return minRunLength;
}
// Returns true iff run_length(n - 2) > run_length(n - 1) + run_length(n).
macro RunInvariantEstablished(pendingRuns: FixedArray, n: Smi): bool {
if (n < 2) return true;
- const run_length_n: Smi = GetPendingRunLength(pendingRuns, n);
- const run_length_nm: Smi = GetPendingRunLength(pendingRuns, n - 1);
- const run_length_nmm: Smi = GetPendingRunLength(pendingRuns, n - 2);
+ const runLengthN: Smi = GetPendingRunLength(pendingRuns, n);
+ const runLengthNM: Smi = GetPendingRunLength(pendingRuns, n - 1);
+ const runLengthNMM: Smi = GetPendingRunLength(pendingRuns, n - 2);
- return run_length_nmm > run_length_nm + run_length_n;
+ return runLengthNMM > runLengthNM + runLengthN;
}
// Examines the stack of runs waiting to be merged, merging adjacent runs
@@ -1570,24 +1565,24 @@ module array {
// process. Determine if all these extra loads are ok.
macro MergeCollapse(context: Context, sortState: FixedArray)
labels Bailout {
- const pending_runs: FixedArray =
- unsafe_cast<FixedArray>(sortState[kPendingRunsIdx]);
+ const pendingRuns: FixedArray =
+ UnsafeCast<FixedArray>(sortState[kPendingRunsIdx]);
// Reload the stack size because MergeAt might change it.
while (GetPendingRunsSize(sortState) > 1) {
let n: Smi = GetPendingRunsSize(sortState) - 2;
- if (!RunInvariantEstablished(pending_runs, n + 1) ||
- !RunInvariantEstablished(pending_runs, n)) {
- if (GetPendingRunLength(pending_runs, n - 1) <
- GetPendingRunLength(pending_runs, n + 1)) {
+ if (!RunInvariantEstablished(pendingRuns, n + 1) ||
+ !RunInvariantEstablished(pendingRuns, n)) {
+ if (GetPendingRunLength(pendingRuns, n - 1) <
+ GetPendingRunLength(pendingRuns, n + 1)) {
--n;
}
CallMergeAt(context, sortState, n) otherwise Bailout;
} else if (
- GetPendingRunLength(pending_runs, n) <=
- GetPendingRunLength(pending_runs, n + 1)) {
+ GetPendingRunLength(pendingRuns, n) <=
+ GetPendingRunLength(pendingRuns, n + 1)) {
CallMergeAt(context, sortState, n) otherwise Bailout;
} else {
break;
@@ -1599,16 +1594,16 @@ module array {
// remains. This is used at the end of the mergesort.
macro MergeForceCollapse(context: Context, sortState: FixedArray)
labels Bailout {
- let pending_runs: FixedArray =
- unsafe_cast<FixedArray>(sortState[kPendingRunsIdx]);
+ let pendingRuns: FixedArray =
+ UnsafeCast<FixedArray>(sortState[kPendingRunsIdx]);
// Reload the stack size becuase MergeAt might change it.
while (GetPendingRunsSize(sortState) > 1) {
let n: Smi = GetPendingRunsSize(sortState) - 2;
if (n > 0 &&
- GetPendingRunLength(pending_runs, n - 1) <
- GetPendingRunLength(pending_runs, n + 1)) {
+ GetPendingRunLength(pendingRuns, n - 1) <
+ GetPendingRunLength(pendingRuns, n + 1)) {
--n;
}
CallMergeAt(context, sortState, n) otherwise Bailout;
@@ -1620,13 +1615,12 @@ module array {
sortState[kTempArraySizeIdx] = SmiConstant(0);
SetPendingRunsSize(sortState, 0);
- let pending_runs: FixedArray =
- AllocateZeroedFixedArray(convert<intptr>(kMaxMergePending));
- FillFixedArrayWithSmiZero(pending_runs, kMaxMergePending);
- sortState[kPendingRunsIdx] = pending_runs;
+ let pendingRuns: FixedArray =
+ AllocateZeroedFixedArray(Convert<intptr>(kMaxMergePending));
+ sortState[kPendingRunsIdx] = pendingRuns;
}
- macro InitializeSortStateAccessor<Accessor : type>(sortState: FixedArray) {
+ macro InitializeSortStateAccessor<Accessor: type>(sortState: FixedArray) {
sortState[kAccessorIdx] = kFastElementsAccessorId;
sortState[kLoadFnIdx] = Load<Accessor>;
sortState[kStoreFnIdx] = Store<Accessor>;
@@ -1651,44 +1645,44 @@ module array {
// March over the array once, left to right, finding natural runs,
// and extending short natural runs to minrun elements.
let low: Smi = 0;
- const min_run_length: Smi = ComputeMinRunLength(remaining);
+ const minRunLength: Smi = ComputeMinRunLength(remaining);
while (remaining != 0) {
- let current_run_length: Smi =
+ let currentRunLength: Smi =
CountAndMakeRun(context, sortState, low, low + remaining)
- otherwise Bailout;
+ otherwise Bailout;
- // If the run is short, extend it to min(min_run_length, remaining).
- if (current_run_length < min_run_length) {
- const forced_run_length: Smi = SmiMin(min_run_length, remaining);
+ // If the run is short, extend it to min(minRunLength, remaining).
+ if (currentRunLength < minRunLength) {
+ const forcedRunLength: Smi = SmiMin(minRunLength, remaining);
BinaryInsertionSort(
- context, sortState, low, low + current_run_length,
- low + forced_run_length);
+ context, sortState, low, low + currentRunLength,
+ low + forcedRunLength);
EnsureSuccess(sortState) otherwise Bailout;
- current_run_length = forced_run_length;
+ currentRunLength = forcedRunLength;
}
// Push run onto pending-runs stack, and maybe merge.
- PushRun(sortState, low, current_run_length);
+ PushRun(sortState, low, currentRunLength);
MergeCollapse(context, sortState) otherwise Bailout;
// Advance to find next run.
- low = low + current_run_length;
- remaining = remaining - current_run_length;
+ low = low + currentRunLength;
+ remaining = remaining - currentRunLength;
}
MergeForceCollapse(context, sortState) otherwise Bailout;
assert(GetPendingRunsSize(sortState) == 1);
assert(
GetPendingRunLength(
- unsafe_cast<FixedArray>(sortState[kPendingRunsIdx]), 0) == length);
+ UnsafeCast<FixedArray>(sortState[kPendingRunsIdx]), 0) == length);
}
builtin ArrayTimSort(
context: Context, sortState: FixedArray, length: Smi): Object {
try {
ArrayTimSortImpl(context, sortState, length)
- otherwise Slow;
+ otherwise Slow;
}
label Slow {
if (sortState[kAccessorIdx] == kGenericElementsAccessorId) {
@@ -1716,7 +1710,6 @@ module array {
// array and move the undefineds after that. Holes are removed.
// This happens for Array as well as non-Array objects.
extern runtime PrepareElementsForSort(Context, Object, Number): Smi;
- extern macro FillFixedArrayWithSmiZero(FixedArray, Smi);
// https://tc39.github.io/ecma262/#sec-array.prototype.sort
javascript builtin ArrayPrototypeSort(
@@ -1731,14 +1724,13 @@ module array {
// 2. Let obj be ? ToObject(this value).
const obj: JSReceiver = ToObject(context, receiver);
- const sort_state: FixedArray = AllocateZeroedFixedArray(kSortStateSize);
- FillFixedArrayWithSmiZero(sort_state, SmiTag(kSortStateSize));
+ const sortState: FixedArray = AllocateZeroedFixedArray(kSortStateSize);
- sort_state[kReceiverIdx] = obj;
- sort_state[kUserCmpFnIdx] = comparefnObj;
- sort_state[kSortComparePtrIdx] =
+ sortState[kReceiverIdx] = obj;
+ sortState[kUserCmpFnIdx] = comparefnObj;
+ sortState[kSortComparePtrIdx] =
comparefnObj != Undefined ? SortCompareUserFn : SortCompareDefault;
- sort_state[kBailoutStatusIdx] = kSuccess;
+ sortState[kBailoutStatusIdx] = kSuccess;
// 3. Let len be ? ToLength(? Get(obj, "length")).
const len: Number =
@@ -1751,33 +1743,34 @@ module array {
assert(nofNonUndefined <= len);
let map: Map = obj.map;
- sort_state[kInitialReceiverMapIdx] = map;
- sort_state[kInitialReceiverLengthIdx] = len;
+ sortState[kInitialReceiverMapIdx] = map;
+ sortState[kInitialReceiverLengthIdx] = len;
try {
- const a: JSArray = cast<JSArray>(obj) otherwise slow;
+ const a: JSArray = Cast<JSArray>(obj) otherwise Slow;
const elementsKind: ElementsKind = map.elements_kind;
- if (!IsFastElementsKind(elementsKind)) goto slow;
+ if (!IsFastElementsKind(elementsKind)) goto Slow;
if (IsDoubleElementsKind(elementsKind)) {
- InitializeSortStateAccessor<FastDoubleElements>(sort_state);
+ InitializeSortStateAccessor<FastDoubleElements>(sortState);
} else if (elementsKind == PACKED_SMI_ELEMENTS) {
- InitializeSortStateAccessor<FastPackedSmiElements>(sort_state);
+ InitializeSortStateAccessor<FastPackedSmiElements>(sortState);
} else {
- InitializeSortStateAccessor<FastSmiOrObjectElements>(sort_state);
+ InitializeSortStateAccessor<FastSmiOrObjectElements>(sortState);
}
- ArrayTimSort(context, sort_state, nofNonUndefined);
+ ArrayTimSort(context, sortState, nofNonUndefined);
}
- label slow {
+ label Slow {
if (map.elements_kind == DICTIONARY_ELEMENTS && IsExtensibleMap(map) &&
!IsCustomElementsReceiverInstanceType(map.instance_type)) {
- InitializeSortStateAccessor<DictionaryElements>(sort_state);
+ InitializeSortStateAccessor<DictionaryElements>(sortState);
} else {
- InitializeSortStateAccessor<GenericElementsAccessor>(sort_state);
+ InitializeSortStateAccessor<GenericElementsAccessor>(sortState);
}
- ArrayTimSort(context, sort_state, nofNonUndefined);
+ ArrayTimSort(context, sortState, nofNonUndefined);
}
return receiver;
}
}
+