blob: 7751e3a906b158834ecd44bc01ca54c11188d9a2 [file] [log] [blame]
// Copyright (c) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
// 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Python Software Foundation;
// All Rights Reserved
// This file implements a stable, adapative merge sort variant called TimSort.
//
// It was first implemented in python and this Torque implementation
// is based on the current version:
//
// https://github.com/python/cpython/blob/master/Objects/listobject.c
//
// Detailed analysis and a description of the algorithm can be found at:
//
// https://github.com/python/cpython/blob/master/Objects/listsort.txt
module array {
// Naming convention from elements.cc. We have a similar intent but implement
// fastpaths using generics instead of using a class hierarchy for elements
// kinds specific implementations.
// All accessors bail to the GenericElementsAccessor if assumptions checked
// by "CanUseSameAccessor<>" are violated:
// Generic <- FastPackedSmi
// <- FastSmiOrObject
// <- FastDouble
// <- Dictionary
//
// The only exception is TempArrayElements, since it does not describe the
// "elements" of the receiver, but instead is used as an "adaptor" so
// GallopLeft/GallopRight can be reused with the temporary array.
type GenericElementsAccessor;
type FastPackedSmiElements;
type FastSmiOrObjectElements;
type FastDoubleElements;
type DictionaryElements;
const kGenericElementsAccessorId: Smi = 0;
const kFastElementsAccessorId: Smi = 1;
// This is a special type, used to access the temporary array which is always
// PACKED_ELEMENTS. As a result, we do not need a sanity check for it,
// otherwise we might wrongly bail to the slow path.
type TempArrayElements;
// The following index constants describe the layout of the sortState.
// The sortState is currently implemented as a FixedArray of
// size kSortStateSize.
// The receiver of the Array.p.sort call.
const kReceiverIdx: constexpr int31 = 0;
// The initial map and length of the receiver. After calling into JS, these
// are reloaded and checked. If they changed we bail to the baseline
// GenericElementsAccessor.
const kInitialReceiverMapIdx: constexpr int31 = 1;
const kInitialReceiverLengthIdx: constexpr int31 = 2;
// If the user provided a comparison function, it is stored here.
const kUserCmpFnIdx: constexpr int31 = 3;
// Function pointer to the comparison function. This can either be a builtin
// that calls the user-provided comparison function or "SortDefault", which
// uses ToString and a lexicographical compare.
const kSortComparePtrIdx: constexpr int31 = 4;
// The following three function pointer represent a Accessor/Path.
// These are used to Load/Store elements and to check whether to bail to the
// baseline GenericElementsAccessor.
const kLoadFnIdx: constexpr int31 = 5;
const kStoreFnIdx: constexpr int31 = 6;
const kCanUseSameAccessorFnIdx: constexpr int31 = 7;
// If this field has the value kFailure, we need to bail to the baseline
// GenericElementsAccessor.
const kBailoutStatusIdx: constexpr int31 = 8;
// This controls when we get *into* galloping mode. It's initialized to
// kMinGallop. mergeLow and mergeHigh tend to nudge it higher for random data,
// and lower for highly structured data.
const kMinGallopIdx: constexpr int31 = 9;
// A stack of sortState[kPendingRunsSizeIdx] pending runs yet to be merged.
// Run #i starts at sortState[kPendingRunsIdx][2 * i] and extends for
// sortState[kPendingRunsIdx][2 * i + 1] elements:
//
// [..., base (i-1), length (i-1), base i, length i]
//
// It's always true (so long as the indices are in bounds) that
//
// base of run #i + length of run #i == base of run #i + 1
//
const kPendingRunsSizeIdx: constexpr int31 = 10;
const kPendingRunsIdx: constexpr int31 = 11;
// The current size of the temporary array.
const kTempArraySizeIdx: constexpr int31 = 12;
// Pointer to the temporary array.
const kTempArrayIdx: constexpr int31 = 13;
// Contains a Smi constant describing which accessors to use. This is used
// for reloading the right elements and for a sanity check.
const kAccessorIdx: constexpr int31 = 14;
const kSortStateSize: intptr = 15;
const kFailure: Smi = -1;
const kSuccess: Smi = 0;
// The maximum number of entries in a SortState's pending-runs stack.
// This is enough to sort arrays of size up to about
// 32 * phi ** kMaxMergePending
// where phi ~= 1.618. 85 is ridiculously large enough, good for an array with
// 2 ** 64 elements.
const kMaxMergePending: constexpr int31 = 85;
// When we get into galloping mode, we stay there until both runs win less
// often then kMinGallop consecutive times. See listsort.txt for more info.
const kMinGallopWins: constexpr int31 = 7;
// Default size of the temporary array. The temporary array is allocated when
// it is first requested, but it has always at least this size.
const kSortStateTempSize: Smi = 32;
type LoadFn = builtin(Context, FixedArray, HeapObject, Smi) => Object;
type StoreFn = builtin(Context, FixedArray, HeapObject, Smi, Object) => Smi;
type CanUseSameAccessorFn = builtin(Context, JSReceiver, Object, Number) =>
Boolean;
type CompareBuiltinFn = builtin(Context, Object, Object, Object) => Number;
// The following builtins implement Load/Store for all the Accessors.
// The most generic baseline version uses Get-/SetProperty. We do not need
// to worry about the prototype chain, because the pre-processing step has
// copied values from the prototype chain to the receiver if they were visible
// through a hole.
builtin Load<ElementsAccessor : type>(
context: Context, sortState: FixedArray, elements: HeapObject,
index: Smi): Object {
return GetProperty(context, elements, index);
}
Load<FastPackedSmiElements>(
context: Context, sortState: FixedArray, elements: HeapObject,
index: Smi): Object {
const elems: FixedArray = unsafe_cast<FixedArray>(elements);
return elems[index];
}
Load<FastSmiOrObjectElements>(
context: Context, sortState: FixedArray, elements: HeapObject,
index: Smi): Object {
const elems: FixedArray = unsafe_cast<FixedArray>(elements);
const result: Object = elems[index];
if (IsTheHole(result)) {
// The pre-processing step removed all holes by compacting all elements
// at the start of the array. Finding a hole means the cmp function or
// ToString changes the array.
return Failure(sortState);
}
return result;
}
Load<FastDoubleElements>(
context: Context, sortState: FixedArray, elements: HeapObject,
index: Smi): Object {
try {
const elems: FixedDoubleArray = unsafe_cast<FixedDoubleArray>(elements);
const value: float64 =
LoadDoubleWithHoleCheck(elems, index) otherwise Bailout;
return AllocateHeapNumberWithValue(value);
}
label Bailout {
// The pre-processing step removed all holes by compacting all elements
// at the start of the array. Finding a hole means the cmp function or
// ToString changes the array.
return Failure(sortState);
}
}
Load<DictionaryElements>(
context: Context, sortState: FixedArray, elements: HeapObject,
index: Smi): Object {
try {
const dictionary: NumberDictionary =
unsafe_cast<NumberDictionary>(elements);
const intptr_index: intptr = convert<intptr>(index);
const value: Object =
BasicLoadNumberDictionaryElement(dictionary, intptr_index)
otherwise Bailout, Bailout;
return value;
}
label Bailout {
return Failure(sortState);
}
}
Load<TempArrayElements>(
context: Context, sortState: FixedArray, elements: HeapObject,
index: Smi): Object {
assert(IsFixedArray(elements));
const elems: FixedArray = unsafe_cast<FixedArray>(elements);
return elems[index];
}
builtin Store<ElementsAccessor : type>(
context: Context, sortState: FixedArray, elements: HeapObject, index: Smi,
value: Object): Smi {
SetProperty(context, elements, index, value);
return kSuccess;
}
Store<FastPackedSmiElements>(
context: Context, sortState: FixedArray, elements: HeapObject, index: Smi,
value: Object): Smi {
const elems: FixedArray = unsafe_cast<FixedArray>(elements);
StoreFixedArrayElementSmi(elems, index, value, SKIP_WRITE_BARRIER);
return kSuccess;
}
Store<FastSmiOrObjectElements>(
context: Context, sortState: FixedArray, elements: HeapObject, index: Smi,
value: Object): Smi {
const elems: FixedArray = unsafe_cast<FixedArray>(elements);
elems[index] = value;
return kSuccess;
}
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);
// Make sure we do not store signalling NaNs into double arrays.
const val: float64 = Float64SilenceNaN(convert<float64>(heap_val));
StoreFixedDoubleArrayElementWithSmiIndex(elems, index, val);
return kSuccess;
}
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);
try {
BasicStoreNumberDictionaryElement(dictionary, intptr_index, value)
otherwise Fail, Fail, ReadOnly;
return kSuccess;
}
label ReadOnly {
// We cannot write to read-only data properties. Throw the same TypeError
// as SetProperty would.
const receiver: JSReceiver = GetReceiver(sortState);
ThrowTypeError(
context, kStrictReadOnlyProperty, index, Typeof(receiver), receiver);
}
label Fail {
return Failure(sortState);
}
}
Store<TempArrayElements>(
context: Context, sortState: FixedArray, elements: HeapObject, index: Smi,
value: Object): Smi {
const elems: FixedArray = unsafe_cast<FixedArray>(elements);
elems[index] = value;
return kSuccess;
}
extern macro UnsafeCastObjectToCompareBuiltinFn(Object): CompareBuiltinFn;
unsafe_cast<CompareBuiltinFn>(o: Object): CompareBuiltinFn {
return UnsafeCastObjectToCompareBuiltinFn(o);
}
extern macro UnsafeCastObjectToLoadFn(Object): LoadFn;
unsafe_cast<LoadFn>(o: Object): LoadFn {
return UnsafeCastObjectToLoadFn(o);
}
extern macro UnsafeCastObjectToStoreFn(Object): StoreFn;
unsafe_cast<StoreFn>(o: Object): StoreFn {
return UnsafeCastObjectToStoreFn(o);
}
extern macro UnsafeCastObjectToCanUseSameAccessorFn(Object):
CanUseSameAccessorFn;
unsafe_cast<CanUseSameAccessorFn>(o: Object): CanUseSameAccessorFn {
return UnsafeCastObjectToCanUseSameAccessorFn(o);
}
builtin SortCompareDefault(
context: Context, comparefn: Object, x: Object, y: Object): Number {
assert(comparefn == Undefined);
if (TaggedIsSmi(x) && TaggedIsSmi(y)) {
// TODO(szuend): Replace with a fast CallCFunction call.
return SmiLexicographicCompare(context, x, y);
}
// 5. Let xString be ? ToString(x).
const xString: String = ToString_Inline(context, x);
// 6. Let yString be ? ToString(y).
const yString: String = ToString_Inline(context, y);
// 7. Let xSmaller be the result of performing
// Abstract Relational Comparison xString < yString.
// 8. If xSmaller is true, return -1.
if (StringLessThan(context, xString, yString) == True) return -1;
// 9. Let ySmaller be the result of performing
// Abstract Relational Comparison yString < xString.
// 10. If ySmaller is true, return 1.
if (StringLessThan(context, yString, xString) == True) return 1;
// 11. Return +0.
return 0;
}
builtin SortCompareUserFn(
context: Context, comparefn: Object, x: Object, y: Object): Number {
assert(comparefn != Undefined);
const cmpfn: Callable = unsafe_cast<Callable>(comparefn);
// a. Let v be ? ToNumber(? Call(comparefn, undefined, x, y)).
const v: Number =
ToNumber_Inline(context, Call(context, cmpfn, Undefined, x, y));
// b. If v is NaN, return +0.
if (NumberIsNaN(v)) return 0;
// c. return v.
return v;
}
builtin CanUseSameAccessor<ElementsAccessor : type>(
context: Context, receiver: JSReceiver, initialReceiverMap: Object,
initialReceiverLength: Number): Boolean {
assert(IsJSArray(receiver));
let a: JSArray = unsafe_cast<JSArray>(receiver);
if (a.map != initialReceiverMap) return False;
assert(TaggedIsSmi(initialReceiverLength));
let originalLength: Smi = unsafe_cast<Smi>(initialReceiverLength);
if (a.length_fast != originalLength) return False;
return True;
}
CanUseSameAccessor<GenericElementsAccessor>(
context: Context, receiver: JSReceiver, initialReceiverMap: Object,
initialReceiverLength: Number): Boolean {
// Do nothing. We are already on the slow path.
return True;
}
CanUseSameAccessor<DictionaryElements>(
context: Context, receiver: JSReceiver, initialReceiverMap: Object,
initialReceiverLength: Number): Boolean {
let obj: JSReceiver = unsafe_cast<JSReceiver>(receiver);
return SelectBooleanConstant(obj.map == initialReceiverMap);
}
macro CallCompareFn(
context: Context, sortState: FixedArray, x: Object, y: Object): Number
labels Bailout {
const userCmpFn: Object = sortState[kUserCmpFnIdx];
const sortCompare: CompareBuiltinFn =
unsafe_cast<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 =
GetCanUseSameAccessorFn(sortState);
if (!CanUseSameAccessor(
context, receiver, initialReceiverMap, initialReceiverLength)) {
goto Bailout;
}
return result;
}
// Reloading elements after returning from JS is needed since left-trimming
// might have occurred. This means we cannot leave any pointer to the elements
// backing store on the stack (since it would point to the filler object).
// TODO(v8:7995): Remove reloading once left-trimming is removed.
macro ReloadElements(sortState: FixedArray): HeapObject {
const receiver: JSReceiver = GetReceiver(sortState);
if (sortState[kAccessorIdx] == kGenericElementsAccessorId) return receiver;
const object: JSObject = unsafe_cast<JSObject>(receiver);
return object.elements;
}
macro GetLoadFn(sortState: FixedArray): LoadFn {
return unsafe_cast<LoadFn>(sortState[kLoadFnIdx]);
}
macro GetStoreFn(sortState: FixedArray): StoreFn {
return unsafe_cast<StoreFn>(sortState[kStoreFnIdx]);
}
macro GetCanUseSameAccessorFn(sortState: FixedArray): CanUseSameAccessorFn {
return unsafe_cast<CanUseSameAccessorFn>(
sortState[kCanUseSameAccessorFnIdx]);
}
macro GetReceiver(sortState: FixedArray): JSReceiver {
return unsafe_cast<JSReceiver>(sortState[kReceiverIdx]);
}
// Returns the temporary array without changing its size.
macro GetTempArray(sortState: FixedArray): FixedArray {
return unsafe_cast<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]);
assert(stack_size >= 0);
return stack_size;
}
macro SetPendingRunsSize(sortState: FixedArray, value: Smi) {
sortState[kPendingRunsSizeIdx] = value;
}
macro GetPendingRunBase(pendingRuns: FixedArray, run: Smi): Smi {
return unsafe_cast<Smi>(pendingRuns[run << 1]);
}
macro SetPendingRunBase(pendingRuns: FixedArray, run: Smi, value: Smi) {
pendingRuns[run << 1] = value;
}
macro GetPendingRunLength(pendingRuns: FixedArray, run: Smi): Smi {
return unsafe_cast<Smi>(pendingRuns[(run << 1) + 1]);
}
macro SetPendingRunLength(pendingRuns: FixedArray, run: Smi, value: Smi) {
pendingRuns[(run << 1) + 1] = value;
}
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]);
SetPendingRunBase(pending_runs, stack_size, base);
SetPendingRunLength(pending_runs, stack_size, length);
SetPendingRunsSize(sortState, stack_size + 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 current_size: Smi = unsafe_cast<Smi>(sortState[kTempArraySizeIdx]);
if (current_size >= min_size) {
return GetTempArray(sortState);
}
const temp_array: FixedArray =
AllocateZeroedFixedArray(convert<intptr>(min_size));
FillFixedArrayWithSmiZero(temp_array, min_size);
sortState[kTempArraySizeIdx] = min_size;
sortState[kTempArrayIdx] = temp_array;
return temp_array;
}
// 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]);
if (status == kFailure) goto Bailout;
}
// Sets kBailoutStatus to kFailure and returns kFailure.
macro Failure(sortState: FixedArray): Smi {
sortState[kBailoutStatusIdx] = kFailure;
return kFailure;
}
// The following Call* macros wrap builtin calls, making call sites more
// readable since we can use labels and do not have to check kBailoutStatus
// 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);
EnsureSuccess(sortState) otherwise Bailout;
return result;
}
macro CallStore(
context: Context, sortState: FixedArray, Store: StoreFn,
elements: HeapObject, index: Smi, value: Object) labels Bailout {
Store(context, sortState, elements, index, value);
EnsureSuccess(sortState) otherwise Bailout;
}
macro CallCopyFromTempArray(
context: Context, sortState: FixedArray, dstElements: HeapObject,
dstPos: Smi, tempArray: FixedArray, srcPos: Smi, length: Smi)
labels Bailout {
CopyFromTempArray(
context, sortState, dstElements, dstPos, tempArray, srcPos, length);
EnsureSuccess(sortState) otherwise Bailout;
}
macro CallCopyWithinSortArray(
context: Context, sortState: FixedArray, elements: HeapObject,
srcPos: Smi, dstPos: Smi, length: Smi)
labels Bailout {
CopyWithinSortArray(context, sortState, elements, srcPos, dstPos, length);
EnsureSuccess(sortState) otherwise Bailout;
}
macro CallGallopRight(
context: Context, sortState: FixedArray, Load: LoadFn, key: Object,
base: Smi, length: Smi, hint: Smi, useTempArray: Boolean): Smi
labels Bailout {
const result: Smi = GallopRight(
context, sortState, Load, key, base, length, hint, useTempArray);
EnsureSuccess(sortState) otherwise Bailout;
return result;
}
macro CallGallopLeft(
context: Context, sortState: FixedArray, Load: LoadFn, key: Object,
base: Smi, length: Smi, hint: Smi, useTempArray: Boolean): Smi
labels Bailout {
const result: Smi = GallopLeft(
context, sortState, Load, key, base, length, hint, useTempArray);
EnsureSuccess(sortState) otherwise Bailout;
return result;
}
macro CallMergeAt(context: Context, sortState: FixedArray, i: Smi)
labels Bailout {
MergeAt(context, sortState, i);
EnsureSuccess(sortState) otherwise Bailout;
}
// Used for OOB asserts in Copy* builtins.
macro GetReceiverLengthProperty(
context: Context, sortState: FixedArray): Smi {
const receiver: JSReceiver = GetReceiver(sortState);
if (IsJSArray(receiver)) return unsafe_cast<JSArray>(receiver).length_fast;
const len: Number =
ToLength_Inline(context, GetProperty(context, receiver, 'length'));
return unsafe_cast<Smi>(len);
}
macro CopyToTempArray(
context: Context, sortState: FixedArray, Load: LoadFn,
srcElements: HeapObject, srcPos: Smi, tempArray: FixedArray, dstPos: Smi,
length: Smi)
labels Bailout {
assert(srcPos >= 0);
assert(dstPos >= 0);
assert(srcPos <= GetReceiverLengthProperty(context, sortState) - length);
assert(dstPos <= tempArray.length - length);
let src_idx: Smi = srcPos;
let dst_idx: Smi = dstPos;
let to: Smi = srcPos + length;
while (src_idx < to) {
let element: Object =
CallLoad(context, sortState, Load, srcElements, src_idx++)
otherwise Bailout;
tempArray[dst_idx++] = element;
}
}
builtin CopyFromTempArray(
context: Context, sortState: FixedArray, dstElements: HeapObject,
dstPos: Smi, tempArray: FixedArray, srcPos: Smi, length: Smi): Smi {
assert(srcPos >= 0);
assert(dstPos >= 0);
assert(srcPos <= tempArray.length - length);
assert(dstPos <= GetReceiverLengthProperty(context, sortState) - length);
let Store: StoreFn = GetStoreFn(sortState);
let src_idx: Smi = srcPos;
let dst_idx: Smi = dstPos;
let to: Smi = srcPos + length;
try {
while (src_idx < to) {
CallStore(
context, sortState, Store, dstElements, dst_idx++,
tempArray[src_idx++])
otherwise Bailout;
}
return kSuccess;
}
label Bailout {
return Failure(sortState);
}
}
builtin CopyWithinSortArray(
context: Context, sortState: FixedArray, elements: HeapObject,
srcPos: Smi, dstPos: Smi, length: Smi): Smi {
assert(srcPos >= 0);
assert(dstPos >= 0);
assert(srcPos <= GetReceiverLengthProperty(context, sortState) - length);
assert(dstPos <= GetReceiverLengthProperty(context, sortState) - length);
try {
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) {
CopyElement(
context, sortState, Load, Store, elements, src_idx--, dst_idx--)
otherwise Bailout;
}
} else {
let src_idx: Smi = srcPos;
let dst_idx: Smi = dstPos;
let to: Smi = srcPos + length;
while (src_idx < to) {
CopyElement(
context, sortState, Load, Store, elements, src_idx++, dst_idx++)
otherwise Bailout;
}
}
return kSuccess;
}
label Bailout {
return Failure(sortState);
}
}
// BinaryInsertionSort is the best method for sorting small arrays: it does
// few compares, but can do data movement quadratic in the number of elements.
// This is an advantage since comparisons are more expensive due to
// calling into JS.
//
// [low, high) is a contiguous range of a array, and is sorted via
// binary insertion. This sort is stable.
//
// On entry, must have low <= start <= high, and that [low, start) is already
// sorted. Pass start == low if you do not know!.
builtin BinaryInsertionSort(
context: Context, sortState: FixedArray, low: Smi, startArg: Smi,
high: Smi): Smi {
assert(low <= startArg && startArg <= high);
try {
let elements: HeapObject = ReloadElements(sortState);
const Load: LoadFn = GetLoadFn(sortState);
const Store: StoreFn = GetStoreFn(sortState);
let start: Smi = low == startArg ? (startArg + 1) : startArg;
for (; start < high; ++start) {
// Set left to where a[start] belongs.
let left: Smi = low;
let right: Smi = start;
const pivot: Object =
CallLoad(context, sortState, Load, elements, right)
otherwise Bailout;
// Invariants:
// pivot >= all in [low, left).
// pivot < all in [right, start).
assert(left < right);
// 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 order: Number =
CallCompareFn(context, sortState, pivot, mid_element)
otherwise Bailout;
elements = ReloadElements(sortState);
if (order < 0) {
right = mid;
} else {
left = mid + 1;
}
}
assert(left == right);
// The invariants still hold, so:
// pivot >= all in [low, left) and
// pivot < all in [left, start),
//
// so pivot belongs at left. Note that if there are elements equal to
// pivot, left points to the first slot after them -- that's why this
// 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;
}
CallStore(context, sortState, Store, elements, left, pivot)
otherwise Bailout;
}
return kSuccess;
}
label Bailout {
return Failure(sortState);
}
}
// Return the length of the run beginning at low, in the range [low, high),
// low < high is required on entry.
// "A run" is the longest ascending sequence, with
//
// a[low] <= a[low + 1] <= a[low + 2] <= ...
//
// or the longest descending sequence, with
//
// a[low] > a[low + 1] > a[low + 2] > ...
//
// For its intended use in stable mergesort, the strictness of the definition
// of "descending" is needed so that the range can safely be reversed
// without violating stability (strict ">" ensures there are no equal
// elements to get out of order).
//
// In addition, if the run is "descending", it is reversed, so the returned
// length is always an ascending sequence.
macro CountAndMakeRun(
context: Context, sortState: FixedArray, lowArg: Smi, high: Smi): Smi
labels Bailout {
assert(lowArg < high);
let elements: HeapObject = ReloadElements(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;
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;
let order: Number =
CallCompareFn(context, sortState, element_low, element_low_pred)
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;
let previous_element: Object = element_low;
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;
elements = ReloadElements(sortState);
if (is_descending) {
if (order >= 0) break;
} else {
if (order < 0) break;
}
previous_element = current_element;
++run_length;
}
if (is_descending) {
ReverseRange(
context, sortState, Load, Store, elements, lowArg,
lowArg + run_length)
otherwise Bailout;
}
return run_length;
}
macro ReverseRange(
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;
}
}
// 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);
// 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(i >= 0);
assert(i == stack_size - 2 || i == stack_size - 3);
const 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);
// 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);
}
SetPendingRunsSize(sortState, stack_size - 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 k: Smi = CallGallopRight(
context, sortState, Load, key_right, base_a, length_a, 0, False)
otherwise Bailout;
assert(k >= 0);
base_a = base_a + k;
length_a = length_a - k;
if (length_a == 0) return kSuccess;
assert(length_a > 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;
assert(length_b >= 0);
if (length_b == 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;
} else {
MergeHigh(context, sortState, base_a, length_a, base_b, length_b)
otherwise Bailout;
}
return kSuccess;
}
label Bailout {
return Failure(sortState);
}
}
// Locates the proper position of key in a sorted array; if the array contains
// an element equal to key, return the position immediately to the left of
// the leftmost equal element. (GallopRight does the same except returns the
// position to the right of the rightmost equal element (if any)).
//
// The array is sorted with "length" elements, starting at "base".
// "length" must be > 0.
//
// "hint" is an index at which to begin the search, 0 <= hint < n. The closer
// hint is to the final result, the faster this runs.
//
// The return value is the int offset in 0..length such that
//
// array[base + offset] < key <= array[base + offset + 1]
//
// 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,
base: Smi, length: Smi, hint: Smi, useTempArray: Boolean): Smi {
assert(length > 0 && base >= 0);
assert(0 <= hint && hint < length);
// We cannot leave a pointer to elements on the stack (see comment at
// ReloadElements). For this reason we pass a flag whether to reload
// and which array to use.
let elements: HeapObject = useTempArray == True ? GetTempArray(sortState) :
ReloadElements(sortState);
let last_ofs: Smi = 0;
let offset: Smi = 1;
try {
const base_hint_element: Object =
CallLoad(context, sortState, Load, elements, base + hint)
otherwise Bailout;
let order: Number =
CallCompareFn(context, sortState, base_hint_element, key)
otherwise Bailout;
if (useTempArray == False) {
elements = ReloadElements(sortState);
}
if (order < 0) {
// a[base + hint] < key: gallop right, until
// a[base + hint + last_ofs] < 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, elements, base + hint + offset)
otherwise Bailout;
order = CallCompareFn(context, sortState, offset_element, key)
otherwise Bailout;
if (useTempArray == False) {
elements = ReloadElements(sortState);
}
// a[base + hint + offset] >= key? Break.
if (order >= 0) break;
last_ofs = offset;
offset = (offset << 1) + 1;
// Integer overflow.
if (offset <= 0) offset = max_ofs;
}
if (offset > max_ofs) offset = max_ofs;
// Translate back to positive offsets relative to base.
last_ofs = last_ofs + hint;
offset = offset + hint;
} else {
// key <= a[base + hint]: gallop left, until
// a[base + hint - offset] < key <= a[base + hint - last_ofs].
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, elements, base + hint - offset)
otherwise Bailout;
order = CallCompareFn(context, sortState, offset_element, key)
otherwise Bailout;
if (useTempArray == False) {
elements = ReloadElements(sortState);
}
if (order < 0) break;
last_ofs = offset;
offset = (offset << 1) + 1;
// Integer overflow.
if (offset <= 0) offset = max_ofs;
}
if (offset > max_ofs) offset = max_ofs;
// Translate back to positive offsets relative to base.
const tmp: Smi = last_ofs;
last_ofs = hint - offset;
offset = hint - tmp;
}
assert(-1 <= last_ofs && last_ofs < 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
// 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);
const base_m_element: Object =
CallLoad(context, sortState, Load, elements, base + m)
otherwise Bailout;
order = CallCompareFn(context, sortState, base_m_element, key)
otherwise Bailout;
if (useTempArray == False) {
elements = ReloadElements(sortState);
}
if (order < 0) {
last_ofs = 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(0 <= offset && offset <= length);
return offset;
}
label Bailout {
return Failure(sortState);
}
}
// Exactly like GallopLeft, except that if key already exists in
// [base, base + length), finds the position immediately to the right of the
// rightmost equal value.
//
// The return value is the int offset in 0..length such that
//
// array[base + offset - 1] <= key < array[base + offset]
//
// or kFailure on error.
builtin GallopRight(
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);
// We cannot leave a pointer to elements on the stack (see comment at
// ReloadElements). For this reason we pass a flag whether to reload
// and which array to use.
let elements: HeapObject = useTempArray == True ? GetTempArray(sortState) :
ReloadElements(sortState);
let last_ofs: Smi = 0;
let offset: Smi = 1;
try {
const base_hint_element: Object =
CallLoad(context, sortState, Load, elements, base + hint)
otherwise Bailout;
let order: Number =
CallCompareFn(context, sortState, key, base_hint_element)
otherwise Bailout;
if (useTempArray == False) {
elements = ReloadElements(sortState);
}
if (order < 0) {
// key < a[base + hint]: gallop left, until
// a[base + hint - offset] <= key < a[base + hint - last_ofs].
// a[base + hint] is lowest.
let max_ofs: Smi = hint + 1;
while (offset < max_ofs) {
const offset_element: Object =
CallLoad(context, sortState, Load, elements, base + hint - offset)
otherwise Bailout;
order = CallCompareFn(context, sortState, key, offset_element)
otherwise Bailout;
if (useTempArray == False) {
elements = ReloadElements(sortState);
}
if (order >= 0) break;
last_ofs = offset;
offset = (offset << 1) + 1;
// Integer overflow.
if (offset <= 0) offset = max_ofs;
}
if (offset > max_ofs) offset = max_ofs;
// Translate back to positive offsets relative to base.
const tmp: Smi = last_ofs;
last_ofs = 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 + length - 1] is highest.
let max_ofs: Smi = length - hint;
while (offset < max_ofs) {
const offset_element: Object =
CallLoad(context, sortState, Load, elements, base + hint + offset)
otherwise Bailout;
order = CallCompareFn(context, sortState, key, offset_element)
otherwise Bailout;
if (useTempArray == False) {
elements = ReloadElements(sortState);
}
// a[base + hint + ofs] <= key.
if (order < 0) break;
last_ofs = offset;
offset = (offset << 1) + 1;
// Integer overflow.
if (offset <= 0) offset = max_ofs;
}
if (offset > max_ofs) offset = max_ofs;
// Translate back to positive offests relative to base.
last_ofs = last_ofs + hint;
offset = offset + hint;
}
assert(-1 <= last_ofs && last_ofs < 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.
// 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);
const base_m_element: Object =
CallLoad(context, sortState, Load, elements, base + m)
otherwise Bailout;
order = CallCompareFn(context, sortState, key, base_m_element)
otherwise Bailout;
if (useTempArray == False) {
elements = ReloadElements(sortState);
}
if (order < 0) {
offset = m; // key < a[base + m].
} else {
last_ofs = m + 1; // a[base + m] <= key.
}
}
// so a[base + offset - 1] <= key < a[base + offset].
assert(last_ofs == offset);
assert(0 <= offset && offset <= length);
return offset;
}
label Bailout {
return Failure(sortState);
}
}
// Copies a single element inside the array/object (NOT the temp_array).
macro CopyElement(
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.
macro MergeLow(
context: Context, sortState: FixedArray, baseA: Smi, lengthA: Smi,
baseB: Smi, lengthB: Smi)
labels Bailout {
assert(0 < lengthA && 0 < lengthB);
assert(0 <= baseA && 0 < baseB);
assert(baseA + lengthA == baseB);
let length_a: Smi = lengthA;
let length_b: Smi = lengthB;
let elements: HeapObject = ReloadElements(sortState);
const LoadF: LoadFn = GetLoadFn(sortState);
const Store: StoreFn = GetStoreFn(sortState);
const temp_array: FixedArray = GetTempArray(sortState, length_a);
CopyToTempArray(
context, sortState, LoadF, elements, baseA, temp_array, 0, length_a)
otherwise Bailout;
let dest: Smi = baseA;
let cursor_temp: Smi = 0;
let cursor_b: Smi = baseB;
CopyElement(context, sortState, LoadF, Store, elements, cursor_b++, dest++)
otherwise Bailout;
try {
if (--length_b == 0) goto Succeed;
if (length_a == 1) goto CopyB;
let min_gallop: Smi = unsafe_cast<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.
// 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;
elements = ReloadElements(sortState);
if (order < 0) {
CopyElement(
context, sortState, LoadF, Store, elements, cursor_b, dest)
otherwise Bailout;
++cursor_b;
++dest;
++nof_wins_b;
--length_b;
nof_wins_a = 0;
if (length_b == 0) goto Succeed;
if (nof_wins_b >= min_gallop) break;
} else {
CallStore(
context, sortState, Store, elements, dest,
temp_array[cursor_temp])
otherwise Bailout;
++cursor_temp;
++dest;
++nof_wins_a;
--length_a;
nof_wins_b = 0;
if (length_a == 1) goto CopyB;
if (nof_wins_a >= min_gallop) 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;
assert(nof_wins_a >= 0);
if (nof_wins_a > 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;
if (length_a == 1) goto CopyB;
// length_a == 0 is impossible now if the comparison function is
// consistent, but we can't assume that it is.
if (length_a == 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;
assert(nof_wins_b >= 0);
if (nof_wins_b > 0) {
CallCopyWithinSortArray(
context, sortState, elements, cursor_b, dest, nof_wins_b)
otherwise Bailout;
dest = dest + nof_wins_b;
cursor_b = cursor_b + nof_wins_b;
length_b = length_b - nof_wins_b;
if (length_b == 0) goto Succeed;
}
CallStore(
context, sortState, Store, elements, dest++,
temp_array[cursor_temp++])
otherwise Bailout;
if (--length_a == 1) goto CopyB;
}
++min_gallop; // Penalize it for leaving galloping mode
sortState[kMinGallopIdx] = min_gallop;
}
}
label Succeed {
if (length_a > 0) {
CallCopyFromTempArray(
context, sortState, elements, dest, temp_array, cursor_temp,
length_a) otherwise Bailout;
}
}
label CopyB {
assert(length_a == 1 && length_b > 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;
CallStore(
context, sortState, Store, elements, dest + length_b,
temp_array[cursor_temp])
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.
macro MergeHigh(
context: Context, sortState: FixedArray, baseA: Smi, lengthA: Smi,
baseB: Smi, lengthB: Smi)
labels Bailout {
assert(0 < lengthA && 0 < lengthB);
assert(0 <= baseA && 0 < baseB);
assert(baseA + lengthA == baseB);
let length_a: Smi = lengthA;
let length_b: Smi = lengthB;
let elements: HeapObject = ReloadElements(sortState);
const LoadF: LoadFn = GetLoadFn(sortState);
const Store: StoreFn = GetStoreFn(sortState);
const temp_array: FixedArray = GetTempArray(sortState, length_b);
CopyToTempArray(
context, sortState, LoadF, elements, baseB, temp_array, 0, length_b)
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;
CopyElement(context, sortState, LoadF, Store, elements, cursor_a--, dest--)
otherwise Bailout;
try {
if (--length_a == 0) goto Succeed;
if (length_b == 1) goto CopyA;
let min_gallop: Smi = unsafe_cast<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.
// 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;
elements = ReloadElements(sortState);
if (order < 0) {
CopyElement(
context, sortState, LoadF, Store, elements, cursor_a, dest)
otherwise Bailout;
--cursor_a;
--dest;
++nof_wins_a;
--length_a;
nof_wins_b = 0;
if (length_a == 0) goto Succeed;
if (nof_wins_a >= min_gallop) break;
} else {
CallStore(
context, sortState, Store, elements, dest,
temp_array[cursor_temp])
otherwise Bailout;
--cursor_temp;
--dest;
++nof_wins_b;
--length_b;
nof_wins_a = 0;
if (length_b == 1) goto CopyA;
if (nof_wins_b >= min_gallop) 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 > 0 && length_b > 1);
min_gallop = SmiMax(1, min_gallop - 1);
sortState[kMinGallopIdx] = min_gallop;
let k: Smi = CallGallopRight(
context, sortState, LoadF, temp_array[cursor_temp], baseA,
length_a, length_a - 1, False)
otherwise Bailout;
assert(k >= 0);
nof_wins_a = length_a - k;
if (nof_wins_a > 0) {
dest = dest - nof_wins_a;
cursor_a = cursor_a - nof_wins_a;
CallCopyWithinSortArray(
context, sortState, elements, cursor_a + 1, dest + 1,
nof_wins_a)
otherwise Bailout;
length_a = length_a - nof_wins_a;
if (length_a == 0) goto Succeed;
}
CallStore(
context, sortState, Store, elements, dest--,
temp_array[cursor_temp--])
otherwise Bailout;
if (--length_b == 1) goto CopyA;
let key: Object =
CallLoad(context, sortState, LoadF, elements, cursor_a)
otherwise Bailout;
k = CallGallopLeft(
context, sortState, Load<TempArrayElements>, key, 0, length_b,
length_b - 1, True) otherwise Bailout;
assert(k >= 0);
nof_wins_b = length_b - k;
if (nof_wins_b > 0) {
dest = dest - nof_wins_b;
cursor_temp = cursor_temp - nof_wins_b;
CallCopyFromTempArray(
context, sortState, elements, dest + 1, temp_array,
cursor_temp + 1, nof_wins_b) otherwise Bailout;
length_b = length_b - nof_wins_b;
if (length_b == 1) goto CopyA;
// length_b == 0 is impossible now if the comparison function is
// consistent, but we can't assume that it is.
if (length_b == 0) goto Succeed;
}
CopyElement(
context, sortState, LoadF, Store, elements, cursor_a--, dest--)
otherwise Bailout;
if (--length_a == 0) goto Succeed;
}
++min_gallop;
sortState[kMinGallopIdx] = min_gallop;
}
}
label Succeed {
if (length_b > 0) {
assert(length_a == 0);
CallCopyFromTempArray(
context, sortState, elements, dest - (length_b - 1), temp_array, 0,
length_b) otherwise Bailout;
}
}
label CopyA {
assert(length_b == 1 && length_a > 0);
// The first element of run B belongs at the front of the merge.
dest = dest - length_a;
cursor_a = cursor_a - length_a;
CallCopyWithinSortArray(
context, sortState, elements, cursor_a + 1, dest + 1, length_a)
otherwise Bailout;
CallStore(
context, sortState, Store, elements, dest, temp_array[cursor_temp])
otherwise Bailout;
}
}
// Compute a good value for the minimum run length; natural runs shorter than
// this are boosted artificially via binary insertion sort.
//
// If n < 64, return n (it's too small to bother with fancy stuff).
// Else if n is an exact power of 2, return 32.
// Else return an int k, 32 <= k <= 64, such that n/k is close to, but
// strictly less than, an exact power of 2.
//
// See listsort.txt for more info.
macro ComputeMinRunLength(nArg: Smi): Smi {
let n: Smi = nArg;
let r: Smi = 0; // Becomes 1 if any 1 bits are shifted off.
assert(n >= 0);
while (n >= 64) {
r = r | (n & 1);
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;
}
// 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);
return run_length_nmm > run_length_nm + run_length_n;
}
// Examines the stack of runs waiting to be merged, merging adjacent runs
// until the stack invariants are re-established:
//
// 1. run_length(i - 3) > run_length(i - 2) + run_length(i - 1)
// 2. run_length(i - 2) > run_length(i - 1)
//
// TODO(szuend): Remove unnecessary loads. This macro was refactored to
// improve readability, introducing unnecessary loads in the
// 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]);
// 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)) {
--n;
}
CallMergeAt(context, sortState, n) otherwise Bailout;
} else if (
GetPendingRunLength(pending_runs, n) <=
GetPendingRunLength(pending_runs, n + 1)) {
CallMergeAt(context, sortState, n) otherwise Bailout;
} else {
break;
}
}
}
// Regardless of invariants, merge all runs on the stack until only one
// 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]);
// 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)) {
--n;
}
CallMergeAt(context, sortState, n) otherwise Bailout;
}
}
macro InitializeSortState(sortState: FixedArray) {
sortState[kMinGallopIdx] = SmiConstant(kMinGallopWins);
sortState[kTempArraySizeIdx] = SmiConstant(0);
SetPendingRunsSize(sortState, 0);
let pending_runs: FixedArray =
AllocateZeroedFixedArray(convert<intptr>(kMaxMergePending));
FillFixedArrayWithSmiZero(pending_runs, kMaxMergePending);
sortState[kPendingRunsIdx] = pending_runs;
}
macro InitializeSortStateAccessor<Accessor : type>(sortState: FixedArray) {
sortState[kAccessorIdx] = kFastElementsAccessorId;
sortState[kLoadFnIdx] = Load<Accessor>;
sortState[kStoreFnIdx] = Store<Accessor>;
sortState[kCanUseSameAccessorFnIdx] = CanUseSameAccessor<Accessor>;
}
InitializeSortStateAccessor<GenericElementsAccessor>(sortState: FixedArray) {
sortState[kAccessorIdx] = kGenericElementsAccessorId;
sortState[kLoadFnIdx] = Load<GenericElementsAccessor>;
sortState[kStoreFnIdx] = Store<GenericElementsAccessor>;
sortState[kCanUseSameAccessorFnIdx] =
CanUseSameAccessor<GenericElementsAccessor>;
}
macro ArrayTimSortImpl(context: Context, sortState: FixedArray, length: Smi)
labels Bailout {
InitializeSortState(sortState);
if (length < 2) return;
let remaining: Smi = length;
// 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);
while (remaining != 0) {
let current_run_length: Smi =
CountAndMakeRun(context, sortState, low, low + remaining)
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);
BinaryInsertionSort(
context, sortState, low, low + current_run_length,
low + forced_run_length);
EnsureSuccess(sortState) otherwise Bailout;
current_run_length = forced_run_length;
}
// Push run onto pending-runs stack, and maybe merge.
PushRun(sortState, low, current_run_length);
MergeCollapse(context, sortState) otherwise Bailout;
// Advance to find next run.
low = low + current_run_length;
remaining = remaining - current_run_length;
}
MergeForceCollapse(context, sortState) otherwise Bailout;
assert(GetPendingRunsSize(sortState) == 1);
assert(
GetPendingRunLength(
unsafe_cast<FixedArray>(sortState[kPendingRunsIdx]), 0) == length);
}
builtin ArrayTimSort(
context: Context, sortState: FixedArray, length: Smi): Object {
try {
ArrayTimSortImpl(context, sortState, length)
otherwise Slow;
}
label Slow {
if (sortState[kAccessorIdx] == kGenericElementsAccessorId) {
// We were already on the slow path. This must not happen.
unreachable;
}
sortState[kBailoutStatusIdx] = kSuccess;
InitializeSortStateAccessor<GenericElementsAccessor>(sortState);
ArrayTimSort(context, sortState, length);
}
return kSuccess;
}
// For compatibility with JSC, we also sort elements inherited from
// the prototype chain on non-Array objects.
// We do this by copying them to this object and sorting only
// own elements. This is not very efficient, but sorting with
// inherited elements happens very, very rarely, if at all.
// The specification allows "implementation dependent" behavior
// if an element on the prototype chain has an element that
// might interact with sorting.
//
// We also move all non-undefined elements to the front of the
// 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(
context: Context, receiver: Object, ...arguments): Object {
// 1. If comparefn is not undefined and IsCallable(comparefn) is false,
// throw a TypeError exception.
const comparefnObj: Object = arguments[0];
if (comparefnObj != Undefined && !TaggedIsCallable(comparefnObj)) {
ThrowTypeError(context, kBadSortComparisonFunction, comparefnObj);
}
// 2. Let obj be ? ToObject(this value).
const obj: JSReceiver = ToObject(context, receiver);
let map: Map = obj.map;
const sort_state: FixedArray =
AllocateZeroedFixedArray(kSortStateSize);
FillFixedArrayWithSmiZero(sort_state, SmiTag(kSortStateSize));
sort_state[kReceiverIdx] = obj;
sort_state[kUserCmpFnIdx] = comparefnObj;
sort_state[kSortComparePtrIdx] =
comparefnObj != Undefined ? SortCompareUserFn : SortCompareDefault;
sort_state[kInitialReceiverMapIdx] = map;
sort_state[kBailoutStatusIdx] = kSuccess;
try {
const a: JSArray = cast<JSArray>(obj) otherwise slow;
const elementsKind: ElementsKind = map.elements_kind;
if (!IsFastElementsKind(elementsKind)) goto slow;
// 3. Let len be ? ToLength(? Get(obj, "length")).
const len: Smi = a.length_fast;
if (len < 2) return receiver;
// TODO(szuend): Investigate performance tradeoff of skipping this step
// for PACKED_* and handling Undefineds during sorting.
const nofNonUndefined: Smi = PrepareElementsForSort(context, obj, len);
assert(a.map == map);
sort_state[kInitialReceiverLengthIdx] = len;
if (IsDoubleElementsKind(elementsKind)) {
InitializeSortStateAccessor<FastDoubleElements>(sort_state);
} else if (elementsKind == PACKED_SMI_ELEMENTS) {
InitializeSortStateAccessor<FastPackedSmiElements>(sort_state);
} else {
InitializeSortStateAccessor<FastSmiOrObjectElements>(sort_state);
}
ArrayTimSort(context, sort_state, nofNonUndefined);
}
label slow {
// 3. Let len be ? ToLength(? Get(obj, "length")).
const len: Number =
ToLength_Inline(context, GetProperty(context, obj, 'length'));
if (len < 2) return receiver;
const nofNonUndefined: Smi = PrepareElementsForSort(context, obj, len);
sort_state[kInitialReceiverLengthIdx] = len;
// Reload the map, PrepareElementsForSort might have changed the
// elements kind.
map = obj.map;
if (map.elements_kind == DICTIONARY_ELEMENTS && IsExtensibleMap(map) &&
!IsCustomElementsReceiverInstanceType(map.instance_type)) {
InitializeSortStateAccessor<DictionaryElements>(sort_state);
} else {
InitializeSortStateAccessor<GenericElementsAccessor>(sort_state);
}
ArrayTimSort(context, sort_state, nofNonUndefined);
}
return receiver;
}
}