| // 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 |
| |
| namespace array { |
| class SortState extends Struct { |
| Compare(implicit context: Context)(x: Object, y: Object): Number { |
| const sortCompare: CompareBuiltinFn = this.sortComparePtr; |
| return sortCompare(context, this.userCmpFn, x, y); |
| } |
| |
| CheckAccessor(implicit context: Context)() labels Bailout { |
| const canUseSameAccessorFn: CanUseSameAccessorFn = |
| this.canUseSameAccessorFn; |
| |
| if (!canUseSameAccessorFn( |
| context, this.receiver, this.initialReceiverMap, |
| this.initialReceiverLength)) { |
| goto Bailout; |
| } |
| } |
| |
| ResetToGenericAccessor() { |
| this.loadFn = Load<GenericElementsAccessor>; |
| this.storeFn = Store<GenericElementsAccessor>; |
| this.deleteFn = Delete<GenericElementsAccessor>; |
| } |
| |
| // The receiver of the Array.p.sort call. |
| receiver: JSReceiver; |
| |
| // 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. |
| initialReceiverMap: Map; |
| initialReceiverLength: Number; |
| |
| // If the user provided a comparison function, it is stored here. |
| userCmpFn: Undefined | Callable; |
| |
| // 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. |
| sortComparePtr: CompareBuiltinFn; |
| |
| // The following four function pointer represent a Accessor/Path. |
| // These are used to Load/Store/Delete elements and to check whether |
| // to bail to the baseline GenericElementsAccessor. |
| loadFn: LoadFn; |
| storeFn: StoreFn; |
| deleteFn: DeleteFn; |
| canUseSameAccessorFn: CanUseSameAccessorFn; |
| |
| // 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. |
| minGallop: Smi; |
| |
| // A stack of sortState.pendingRunsSize pending runs yet to be merged. |
| // Run #i starts at sortState.pendingRuns[2 * i] and extends for |
| // sortState.pendingRuns[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 |
| // |
| pendingRunsSize: Smi; |
| pendingRuns: FixedArray; |
| |
| // This is a copy of the original array/object that needs sorting. |
| // workArray is never exposed to user-code, and as such cannot change |
| // shape and won't be left-trimmed. |
| workArray: FixedArray; |
| |
| // Pointer to the temporary array. |
| tempArray: FixedArray; |
| |
| // The initialReceiverLength converted and clamped to Smi. |
| sortLength: Smi; |
| |
| // The number of undefined that need to be inserted after sorting |
| // when the elements are copied back from the workArray to the receiver. |
| numberOfUndefined: Smi; |
| } |
| |
| type FastSmiElements; |
| type FastObjectElements; |
| |
| // With the pre-processing step in Torque, the exact number of elements |
| // to sort is unknown at the time the sort state is created. |
| // The 'length' property is an upper bound (as per spec), |
| // while the actual size of the backing store is a good guess. |
| // After the pre-processing step, the workarray won't change in length. |
| macro CalculateWorkArrayLength( |
| receiver: JSReceiver, initialReceiverLength: Number): intptr { |
| // TODO(szuend): Implement full range sorting, not only up to MaxSmi. |
| // https://crbug.com/v8/7970. |
| let clampedReceiverLength: uintptr = |
| Convert<uintptr>(initialReceiverLength); |
| if (clampedReceiverLength > kSmiMaxValue) { |
| clampedReceiverLength = kSmiMaxValue; |
| } |
| |
| let workArrayLength: intptr = Convert<intptr>(clampedReceiverLength); |
| try { |
| const object = Cast<JSObject>(receiver) otherwise NoJsObject; |
| const elementsLength = Convert<intptr>(object.elements.length); |
| |
| // In some cases, elements are only on prototypes, but not on the receiver |
| // itself. Do nothing then, as {workArrayLength} got initialized with the |
| // {length} property. |
| if (elementsLength != 0) { |
| workArrayLength = IntPtrMin(workArrayLength, elementsLength); |
| } |
| } |
| label NoJsObject {} |
| |
| return workArrayLength; |
| } |
| |
| transitioning macro NewSortState(implicit context: Context)( |
| receiver: JSReceiver, comparefn: Undefined | Callable, |
| initialReceiverLength: Number): SortState { |
| const sortComparePtr = |
| comparefn != Undefined ? SortCompareUserFn : SortCompareDefault; |
| const map = receiver.map; |
| let loadFn: LoadFn; |
| let storeFn: StoreFn; |
| let deleteFn: DeleteFn; |
| let canUseSameAccessorFn: CanUseSameAccessorFn; |
| |
| try { |
| GotoIfForceSlowPath() otherwise Slow; |
| const a: FastJSArray = Cast<FastJSArray>(receiver) otherwise Slow; |
| |
| // Copy copy-on-write (COW) arrays. |
| array::EnsureWriteableFastElements(a); |
| |
| const elementsKind: ElementsKind = map.elements_kind; |
| if (IsDoubleElementsKind(elementsKind)) { |
| loadFn = Load<FastDoubleElements>; |
| storeFn = Store<FastDoubleElements>; |
| deleteFn = Delete<FastDoubleElements>; |
| canUseSameAccessorFn = CanUseSameAccessor<FastDoubleElements>; |
| } else if (IsFastSmiElementsKind(elementsKind)) { |
| loadFn = Load<FastSmiElements>; |
| storeFn = Store<FastSmiElements>; |
| deleteFn = Delete<FastSmiElements>; |
| canUseSameAccessorFn = CanUseSameAccessor<FastSmiElements>; |
| } else { |
| loadFn = Load<FastObjectElements>; |
| storeFn = Store<FastObjectElements>; |
| deleteFn = Delete<FastObjectElements>; |
| canUseSameAccessorFn = CanUseSameAccessor<FastObjectElements>; |
| } |
| } |
| label Slow { |
| loadFn = Load<GenericElementsAccessor>; |
| storeFn = Store<GenericElementsAccessor>; |
| deleteFn = Delete<GenericElementsAccessor>; |
| canUseSameAccessorFn = CanUseSameAccessor<GenericElementsAccessor>; |
| } |
| |
| const workArrayLength = |
| CalculateWorkArrayLength(receiver, initialReceiverLength); |
| |
| return new SortState{ |
| receiver, |
| initialReceiverMap: map, |
| initialReceiverLength, |
| userCmpFn: comparefn, |
| sortComparePtr, |
| loadFn, |
| storeFn, |
| deleteFn, |
| canUseSameAccessorFn, |
| minGallop: kMinGallopWins, |
| pendingRunsSize: 0, |
| pendingRuns: AllocateZeroedFixedArray(Convert<intptr>(kMaxMergePending)), |
| workArray: AllocateZeroedFixedArray(workArrayLength), |
| tempArray: kEmptyFixedArray, |
| sortLength: 0, |
| numberOfUndefined: 0 |
| }; |
| } |
| |
| 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, SortState, Smi) => Object; |
| type StoreFn = builtin(Context, SortState, Smi, Object) => Smi; |
| type DeleteFn = builtin(Context, SortState, Smi) => 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. |
| |
| transitioning builtin Load<ElementsAccessor: type>( |
| context: Context, sortState: SortState, index: Smi): Object { |
| const receiver = sortState.receiver; |
| if (!HasProperty_Inline(receiver, index)) return TheHole; |
| return GetProperty(receiver, index); |
| } |
| |
| Load<FastSmiElements>(context: Context, sortState: SortState, index: Smi): |
| Object { |
| const object = UnsafeCast<JSObject>(sortState.receiver); |
| const elements = UnsafeCast<FixedArray>(object.elements); |
| return elements.objects[index]; |
| } |
| |
| Load<FastObjectElements>(context: Context, sortState: SortState, index: Smi): |
| Object { |
| const object = UnsafeCast<JSObject>(sortState.receiver); |
| const elements = UnsafeCast<FixedArray>(object.elements); |
| return elements.objects[index]; |
| } |
| |
| Load<FastDoubleElements>(context: Context, sortState: SortState, index: Smi): |
| Object { |
| try { |
| const object = UnsafeCast<JSObject>(sortState.receiver); |
| const elements = UnsafeCast<FixedDoubleArray>(object.elements); |
| const value = LoadDoubleWithHoleCheck(elements, index) otherwise IfHole; |
| return AllocateHeapNumberWithValue(value); |
| } |
| label IfHole { |
| return TheHole; |
| } |
| } |
| |
| transitioning builtin Store<ElementsAccessor: type>( |
| context: Context, sortState: SortState, index: Smi, value: Object): Smi { |
| SetProperty(sortState.receiver, index, value); |
| return kSuccess; |
| } |
| |
| Store<FastSmiElements>( |
| context: Context, sortState: SortState, index: Smi, value: Object): Smi { |
| const object = UnsafeCast<JSObject>(sortState.receiver); |
| const elements = UnsafeCast<FixedArray>(object.elements); |
| const value = UnsafeCast<Smi>(value); |
| StoreFixedArrayElement(elements, index, value, SKIP_WRITE_BARRIER); |
| return kSuccess; |
| } |
| |
| Store<FastObjectElements>( |
| context: Context, sortState: SortState, index: Smi, value: Object): Smi { |
| const object = UnsafeCast<JSObject>(sortState.receiver); |
| const elements = UnsafeCast<FixedArray>(object.elements); |
| elements.objects[index] = value; |
| return kSuccess; |
| } |
| |
| Store<FastDoubleElements>( |
| context: Context, sortState: SortState, index: Smi, value: Object): Smi { |
| const object = UnsafeCast<JSObject>(sortState.receiver); |
| const elements = UnsafeCast<FixedDoubleArray>(object.elements); |
| const heapVal = UnsafeCast<HeapNumber>(value); |
| const val = Convert<float64>(heapVal); |
| StoreFixedDoubleArrayElementSmi(elements, index, val); |
| return kSuccess; |
| } |
| |
| transitioning builtin Delete<ElementsAccessor: type>( |
| context: Context, sortState: SortState, index: Smi): Smi { |
| const receiver = sortState.receiver; |
| if (!HasProperty_Inline(receiver, index)) return kSuccess; |
| DeleteProperty(receiver, index, kStrict); |
| return kSuccess; |
| } |
| |
| Delete<FastSmiElements>(context: Context, sortState: SortState, index: Smi): |
| Smi { |
| assert(IsHoleyFastElementsKind(sortState.receiver.map.elements_kind)); |
| |
| const object = UnsafeCast<JSObject>(sortState.receiver); |
| const elements = UnsafeCast<FixedArray>(object.elements); |
| elements.objects[index] = TheHole; |
| return kSuccess; |
| } |
| |
| Delete<FastObjectElements>( |
| context: Context, sortState: SortState, index: Smi): Smi { |
| assert(IsHoleyFastElementsKind(sortState.receiver.map.elements_kind)); |
| |
| const object = UnsafeCast<JSObject>(sortState.receiver); |
| const elements = UnsafeCast<FixedArray>(object.elements); |
| elements.objects[index] = TheHole; |
| return kSuccess; |
| } |
| |
| Delete<FastDoubleElements>( |
| context: Context, sortState: SortState, index: Smi): Smi { |
| assert(IsHoleyFastElementsKind(sortState.receiver.map.elements_kind)); |
| |
| const object = UnsafeCast<JSObject>(sortState.receiver); |
| const elements = UnsafeCast<FixedDoubleArray>(object.elements); |
| StoreFixedDoubleArrayHoleSmi(elements, index); |
| return kSuccess; |
| } |
| |
| transitioning builtin SortCompareDefault( |
| context: Context, comparefn: Object, x: Object, y: Object): Number { |
| assert(comparefn == Undefined); |
| |
| if (TaggedIsSmi(x) && TaggedIsSmi(y)) { |
| return SmiLexicographicCompare(UnsafeCast<Smi>(x), UnsafeCast<Smi>(y)); |
| } |
| |
| // 5. Let xString be ? ToString(x). |
| const xString = ToString_Inline(context, x); |
| |
| // 6. Let yString be ? ToString(y). |
| const yString = 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; |
| } |
| |
| transitioning builtin SortCompareUserFn( |
| context: Context, comparefn: Object, x: Object, y: Object): Number { |
| assert(comparefn != Undefined); |
| const cmpfn = UnsafeCast<Callable>(comparefn); |
| |
| // a. Let v be ? ToNumber(? Call(comparefn, undefined, x, y)). |
| const v = 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 { |
| if (receiver.map != initialReceiverMap) return False; |
| |
| assert(TaggedIsSmi(initialReceiverLength)); |
| const array = UnsafeCast<JSArray>(receiver); |
| const originalLength = UnsafeCast<Smi>(initialReceiverLength); |
| |
| return SelectBooleanConstant( |
| UnsafeCast<Smi>(array.length) == originalLength); |
| } |
| |
| CanUseSameAccessor<GenericElementsAccessor>( |
| _context: Context, _receiver: JSReceiver, _initialReceiverMap: Object, |
| _initialReceiverLength: Number): Boolean { |
| // Do nothing. We are already on the slow path. |
| return True; |
| } |
| |
| // 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(implicit context: Context)(sortState: SortState): |
| Smi { |
| const stackSize: Smi = sortState.pendingRunsSize; |
| assert(stackSize >= 0); |
| return stackSize; |
| } |
| |
| macro GetPendingRunBase(implicit context: |
| Context)(pendingRuns: FixedArray, run: Smi): Smi { |
| return UnsafeCast<Smi>(pendingRuns.objects[run << 1]); |
| } |
| |
| macro SetPendingRunBase(pendingRuns: FixedArray, run: Smi, value: Smi) { |
| pendingRuns.objects[run << 1] = value; |
| } |
| |
| macro GetPendingRunLength(implicit context: Context)( |
| pendingRuns: FixedArray, run: Smi): Smi { |
| return UnsafeCast<Smi>(pendingRuns.objects[(run << 1) + 1]); |
| } |
| |
| macro SetPendingRunLength(pendingRuns: FixedArray, run: Smi, value: Smi) { |
| pendingRuns.objects[(run << 1) + 1] = value; |
| } |
| |
| macro PushRun(implicit context: |
| Context)(sortState: SortState, base: Smi, length: Smi) { |
| assert(GetPendingRunsSize(sortState) < kMaxMergePending); |
| |
| const stackSize: Smi = GetPendingRunsSize(sortState); |
| const pendingRuns: FixedArray = sortState.pendingRuns; |
| |
| SetPendingRunBase(pendingRuns, stackSize, base); |
| SetPendingRunLength(pendingRuns, stackSize, length); |
| |
| sortState.pendingRunsSize = stackSize + 1; |
| } |
| |
| // Returns the temporary array and makes sure that it is big enough. |
| // TODO(szuend): Implement a better re-size strategy. |
| macro GetTempArray(implicit context: Context)( |
| sortState: SortState, requestedSize: Smi): FixedArray { |
| const minSize: Smi = SmiMax(kSortStateTempSize, requestedSize); |
| |
| const currentSize: Smi = sortState.tempArray.length; |
| if (currentSize >= minSize) { |
| return sortState.tempArray; |
| } |
| |
| const tempArray: FixedArray = |
| AllocateZeroedFixedArray(Convert<intptr>(minSize)); |
| |
| sortState.tempArray = tempArray; |
| return tempArray; |
| } |
| |
| transitioning builtin |
| Copy(implicit context: Context)( |
| source: FixedArray, srcPos: Smi, target: FixedArray, dstPos: Smi, |
| length: Smi): Object { |
| assert(srcPos >= 0); |
| assert(dstPos >= 0); |
| assert(srcPos <= source.length - length); |
| assert(dstPos <= target.length - length); |
| |
| // TODO(szuend): Investigate whether this builtin should be replaced |
| // by CopyElements/MoveElements for perfomance. |
| |
| // source and target might be the same array. To avoid overwriting |
| // values in the case of overlaping ranges, elements are copied from |
| // the back when srcPos < dstPos. |
| if (srcPos < dstPos) { |
| let srcIdx: Smi = srcPos + length - 1; |
| let dstIdx: Smi = dstPos + length - 1; |
| while (srcIdx >= srcPos) { |
| target.objects[dstIdx--] = source.objects[srcIdx--]; |
| } |
| } else { |
| let srcIdx: Smi = srcPos; |
| let dstIdx: Smi = dstPos; |
| const to: Smi = srcPos + length; |
| |
| while (srcIdx < to) { |
| target.objects[dstIdx++] = source.objects[srcIdx++]; |
| } |
| } |
| return kSuccess; |
| } |
| |
| // 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!. |
| macro BinaryInsertionSort(implicit context: Context, sortState: SortState)( |
| low: Smi, startArg: Smi, high: Smi) { |
| assert(low <= startArg && startArg <= high); |
| |
| const workArray = sortState.workArray; |
| |
| 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 = workArray.objects[right]; |
| |
| // 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 order = sortState.Compare(pivot, workArray.objects[mid]); |
| |
| 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) { |
| workArray.objects[p] = workArray.objects[p - 1]; |
| } |
| workArray.objects[left] = pivot; |
| } |
| } |
| |
| // 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(implicit context: Context, sortState: SortState)( |
| lowArg: Smi, high: Smi): Smi { |
| assert(lowArg < high); |
| |
| const workArray = sortState.workArray; |
| |
| const low: Smi = lowArg + 1; |
| if (low == high) return 1; |
| |
| let runLength: Smi = 2; |
| |
| const elementLow = workArray.objects[low]; |
| const elementLowPred = workArray.objects[low - 1]; |
| let order = sortState.Compare(elementLow, elementLowPred); |
| |
| // 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 isDescending: bool = order < 0 ? true : false; |
| |
| let previousElement: Object = elementLow; |
| for (let idx: Smi = low + 1; idx < high; ++idx) { |
| const currentElement = workArray.objects[idx]; |
| order = sortState.Compare(currentElement, previousElement); |
| |
| if (isDescending) { |
| if (order >= 0) break; |
| } else { |
| if (order < 0) break; |
| } |
| |
| previousElement = currentElement; |
| ++runLength; |
| } |
| |
| if (isDescending) { |
| ReverseRange(workArray, lowArg, lowArg + runLength); |
| } |
| |
| return runLength; |
| } |
| |
| macro ReverseRange(array: FixedArray, from: Smi, to: Smi) { |
| let low: Smi = from; |
| let high: Smi = to - 1; |
| |
| while (low < high) { |
| const elementLow = array.objects[low]; |
| const elementHigh = array.objects[high]; |
| array.objects[low++] = elementHigh; |
| array.objects[high--] = elementLow; |
| } |
| } |
| |
| // Merges the two runs at stack indices i and i + 1. |
| // Returns kFailure if we need to bailout, kSuccess otherwise. |
| transitioning builtin |
| MergeAt(implicit context: Context, sortState: SortState)(i: Smi): Smi { |
| 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(stackSize >= 2); |
| assert(i >= 0); |
| assert(i == stackSize - 2 || i == stackSize - 3); |
| |
| const workArray = sortState.workArray; |
| |
| const pendingRuns: FixedArray = sortState.pendingRuns; |
| let baseA: Smi = GetPendingRunBase(pendingRuns, i); |
| let lengthA: Smi = GetPendingRunLength(pendingRuns, i); |
| const 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(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); |
| } |
| sortState.pendingRunsSize = stackSize - 1; |
| |
| // Where does b start in a? Elements in a before that can be ignored, |
| // because they are already in place. |
| const keyRight = workArray.objects[baseB]; |
| const k: Smi = GallopRight(workArray, keyRight, baseA, lengthA, 0); |
| assert(k >= 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. |
| const keyLeft = workArray.objects[baseA + lengthA - 1]; |
| lengthB = GallopLeft(workArray, keyLeft, baseB, lengthB, lengthB - 1); |
| assert(lengthB >= 0); |
| if (lengthB == 0) return kSuccess; |
| |
| // Merge what remains of the runs, using a temp array with |
| // min(lengthA, lengthB) elements. |
| if (lengthA <= lengthB) { |
| MergeLow(baseA, lengthA, baseB, lengthB); |
| } else { |
| MergeHigh(baseA, lengthA, baseB, lengthB); |
| } |
| return kSuccess; |
| } |
| |
| // 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(implicit context: Context, sortState: SortState)( |
| array: FixedArray, key: Object, base: Smi, length: Smi, hint: Smi): Smi { |
| assert(length > 0 && base >= 0); |
| assert(0 <= hint && hint < length); |
| |
| let lastOfs: Smi = 0; |
| let offset: Smi = 1; |
| |
| const baseHintElement = array.objects[base + hint]; |
| let order = sortState.Compare(baseHintElement, key); |
| |
| if (order < 0) { |
| // a[base + hint] < key: gallop right, until |
| // a[base + hint + lastOfs] < key <= a[base + hint + offset]. |
| |
| // a[base + length - 1] is highest. |
| const maxOfs: Smi = length - hint; |
| while (offset < maxOfs) { |
| const offsetElement = array.objects[base + hint + offset]; |
| order = sortState.Compare(offsetElement, key); |
| |
| // a[base + hint + offset] >= key? Break. |
| if (order >= 0) break; |
| |
| lastOfs = offset; |
| offset = (offset << 1) + 1; |
| |
| // Integer overflow. |
| if (offset <= 0) offset = maxOfs; |
| } |
| |
| if (offset > maxOfs) offset = maxOfs; |
| |
| // Translate back to positive offsets relative to base. |
| lastOfs = lastOfs + hint; |
| offset = offset + hint; |
| } else { |
| // key <= a[base + hint]: gallop left, until |
| // a[base + hint - offset] < key <= a[base + hint - lastOfs]. |
| assert(order >= 0); |
| |
| // a[base + hint] is lowest. |
| const maxOfs: Smi = hint + 1; |
| while (offset < maxOfs) { |
| const offsetElement = array.objects[base + hint - offset]; |
| order = sortState.Compare(offsetElement, key); |
| |
| if (order < 0) break; |
| |
| lastOfs = offset; |
| offset = (offset << 1) + 1; |
| |
| // Integer overflow. |
| if (offset <= 0) offset = maxOfs; |
| } |
| |
| if (offset > maxOfs) offset = maxOfs; |
| |
| // Translate back to positive offsets relative to base. |
| const tmp: Smi = lastOfs; |
| lastOfs = hint - offset; |
| offset = hint - tmp; |
| } |
| |
| assert(-1 <= lastOfs && lastOfs < offset && offset <= length); |
| |
| // 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 + lastOfs - 1] < key <= a[base + offset]. |
| lastOfs++; |
| while (lastOfs < offset) { |
| const m: Smi = lastOfs + ((offset - lastOfs) >> 1); |
| |
| order = sortState.Compare(array.objects[base + m], key); |
| |
| if (order < 0) { |
| lastOfs = m + 1; // a[base + m] < key. |
| } else { |
| offset = m; // key <= a[base + m]. |
| } |
| } |
| // so a[base + offset - 1] < key <= a[base + offset]. |
| assert(lastOfs == offset); |
| assert(0 <= offset && offset <= length); |
| return offset; |
| } |
| |
| // 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(implicit context: Context, sortState: SortState)( |
| array: FixedArray, key: Object, base: Smi, length: Smi, hint: Smi): Smi { |
| assert(length > 0 && base >= 0); |
| assert(0 <= hint && hint < length); |
| |
| let lastOfs: Smi = 0; |
| let offset: Smi = 1; |
| |
| const baseHintElement = array.objects[base + hint]; |
| let order = sortState.Compare(key, baseHintElement); |
| |
| if (order < 0) { |
| // key < a[base + hint]: gallop left, until |
| // a[base + hint - offset] <= key < a[base + hint - lastOfs]. |
| |
| // a[base + hint] is lowest. |
| const maxOfs: Smi = hint + 1; |
| while (offset < maxOfs) { |
| const offsetElement = array.objects[base + hint - offset]; |
| order = sortState.Compare(key, offsetElement); |
| |
| if (order >= 0) break; |
| |
| lastOfs = offset; |
| offset = (offset << 1) + 1; |
| |
| // Integer overflow. |
| if (offset <= 0) offset = maxOfs; |
| } |
| |
| if (offset > maxOfs) offset = maxOfs; |
| |
| // Translate back to positive offsets relative to base. |
| const tmp: Smi = lastOfs; |
| lastOfs = hint - offset; |
| offset = hint - tmp; |
| } else { |
| // a[base + hint] <= key: gallop right, until |
| // a[base + hint + lastOfs] <= key < a[base + hint + offset]. |
| |
| // a[base + length - 1] is highest. |
| const maxOfs: Smi = length - hint; |
| while (offset < maxOfs) { |
| const offsetElement = array.objects[base + hint + offset]; |
| order = sortState.Compare(key, offsetElement); |
| |
| // a[base + hint + ofs] <= key. |
| if (order < 0) break; |
| |
| lastOfs = offset; |
| offset = (offset << 1) + 1; |
| |
| // Integer overflow. |
| if (offset <= 0) offset = maxOfs; |
| } |
| |
| if (offset > maxOfs) offset = maxOfs; |
| |
| // Translate back to positive offests relative to base. |
| lastOfs = lastOfs + hint; |
| offset = offset + hint; |
| } |
| assert(-1 <= lastOfs && lastOfs < offset && offset <= length); |
| |
| // 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 + lastOfs - 1] < key <= a[base + ofs]. |
| lastOfs++; |
| while (lastOfs < offset) { |
| const m: Smi = lastOfs + ((offset - lastOfs) >> 1); |
| |
| order = sortState.Compare(key, array.objects[base + m]); |
| |
| if (order < 0) { |
| offset = m; // key < a[base + m]. |
| } else { |
| lastOfs = m + 1; // a[base + m] <= key. |
| } |
| } |
| // so a[base + offset - 1] <= key < a[base + offset]. |
| assert(lastOfs == offset); |
| assert(0 <= offset && offset <= length); |
| return offset; |
| } |
| |
| // 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. |
| transitioning macro MergeLow(implicit context: Context, sortState: SortState)( |
| baseA: Smi, lengthAArg: Smi, baseB: Smi, lengthBArg: Smi) { |
| assert(0 < lengthAArg && 0 < lengthBArg); |
| assert(0 <= baseA && 0 < baseB); |
| assert(baseA + lengthAArg == baseB); |
| |
| let lengthA: Smi = lengthAArg; |
| let lengthB: Smi = lengthBArg; |
| |
| const workArray = sortState.workArray; |
| const tempArray: FixedArray = GetTempArray(sortState, lengthA); |
| Copy(workArray, baseA, tempArray, 0, lengthA); |
| |
| let dest: Smi = baseA; |
| let cursorTemp: Smi = 0; |
| let cursorB: Smi = baseB; |
| |
| workArray.objects[dest++] = workArray.objects[cursorB++]; |
| |
| try { |
| if (--lengthB == 0) goto Succeed; |
| if (lengthA == 1) goto CopyB; |
| |
| let minGallop: Smi = sortState.minGallop; |
| // TODO(szuend): Replace with something that does not have a runtime |
| // overhead as soon as its available in Torque. |
| while (Int32TrueConstant()) { |
| 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(lengthA > 1 && lengthB > 0); |
| |
| const order = sortState.Compare( |
| workArray.objects[cursorB], tempArray.objects[cursorTemp]); |
| |
| if (order < 0) { |
| workArray.objects[dest++] = workArray.objects[cursorB++]; |
| |
| ++nofWinsB; |
| --lengthB; |
| nofWinsA = 0; |
| |
| if (lengthB == 0) goto Succeed; |
| if (nofWinsB >= minGallop) break; |
| } else { |
| workArray.objects[dest++] = tempArray.objects[cursorTemp++]; |
| |
| ++nofWinsA; |
| --lengthA; |
| nofWinsB = 0; |
| |
| 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. |
| ++minGallop; |
| let firstIteration: bool = true; |
| while (nofWinsA >= kMinGallopWins || nofWinsB >= kMinGallopWins || |
| firstIteration) { |
| firstIteration = false; |
| assert(lengthA > 1 && lengthB > 0); |
| |
| minGallop = SmiMax(1, minGallop - 1); |
| sortState.minGallop = minGallop; |
| |
| nofWinsA = GallopRight( |
| tempArray, workArray.objects[cursorB], cursorTemp, lengthA, 0); |
| assert(nofWinsA >= 0); |
| |
| if (nofWinsA > 0) { |
| Copy(tempArray, cursorTemp, workArray, dest, nofWinsA); |
| dest = dest + nofWinsA; |
| cursorTemp = cursorTemp + nofWinsA; |
| lengthA = lengthA - nofWinsA; |
| |
| if (lengthA == 1) goto CopyB; |
| |
| // lengthA == 0 is impossible now if the comparison function is |
| // consistent, but we can't assume that it is. |
| if (lengthA == 0) goto Succeed; |
| } |
| workArray.objects[dest++] = workArray.objects[cursorB++]; |
| if (--lengthB == 0) goto Succeed; |
| |
| nofWinsB = GallopLeft( |
| workArray, tempArray.objects[cursorTemp], cursorB, lengthB, 0); |
| assert(nofWinsB >= 0); |
| if (nofWinsB > 0) { |
| Copy(workArray, cursorB, workArray, dest, nofWinsB); |
| |
| dest = dest + nofWinsB; |
| cursorB = cursorB + nofWinsB; |
| lengthB = lengthB - nofWinsB; |
| |
| if (lengthB == 0) goto Succeed; |
| } |
| workArray.objects[dest++] = tempArray.objects[cursorTemp++]; |
| if (--lengthA == 1) goto CopyB; |
| } |
| ++minGallop; // Penalize it for leaving galloping mode |
| sortState.minGallop = minGallop; |
| } |
| } |
| label Succeed { |
| if (lengthA > 0) { |
| Copy(tempArray, cursorTemp, workArray, dest, lengthA); |
| } |
| } |
| label CopyB { |
| assert(lengthA == 1 && lengthB > 0); |
| // The last element of run A belongs at the end of the merge. |
| Copy(workArray, cursorB, workArray, dest, lengthB); |
| workArray.objects[dest + lengthB] = tempArray.objects[cursorTemp]; |
| } |
| } |
| |
| // 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. |
| transitioning macro MergeHigh( |
| implicit context: Context, |
| sortState: |
| SortState)(baseA: Smi, lengthAArg: Smi, baseB: Smi, lengthBArg: Smi) { |
| assert(0 < lengthAArg && 0 < lengthBArg); |
| assert(0 <= baseA && 0 < baseB); |
| assert(baseA + lengthAArg == baseB); |
| |
| let lengthA: Smi = lengthAArg; |
| let lengthB: Smi = lengthBArg; |
| |
| const workArray = sortState.workArray; |
| const tempArray: FixedArray = GetTempArray(sortState, lengthB); |
| Copy(workArray, baseB, tempArray, 0, lengthB); |
| |
| // MergeHigh merges the two runs backwards. |
| let dest: Smi = baseB + lengthB - 1; |
| let cursorTemp: Smi = lengthB - 1; |
| let cursorA: Smi = baseA + lengthA - 1; |
| |
| workArray.objects[dest--] = workArray.objects[cursorA--]; |
| |
| try { |
| if (--lengthA == 0) goto Succeed; |
| if (lengthB == 1) goto CopyA; |
| |
| let minGallop: Smi = sortState.minGallop; |
| // TODO(szuend): Replace with something that does not have a runtime |
| // overhead as soon as its available in Torque. |
| while (Int32TrueConstant()) { |
| 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(lengthA > 0 && lengthB > 1); |
| |
| const order = sortState.Compare( |
| tempArray.objects[cursorTemp], workArray.objects[cursorA]); |
| |
| if (order < 0) { |
| workArray.objects[dest--] = workArray.objects[cursorA--]; |
| |
| ++nofWinsA; |
| --lengthA; |
| nofWinsB = 0; |
| |
| if (lengthA == 0) goto Succeed; |
| if (nofWinsA >= minGallop) break; |
| } else { |
| workArray.objects[dest--] = tempArray.objects[cursorTemp--]; |
| |
| ++nofWinsB; |
| --lengthB; |
| nofWinsA = 0; |
| |
| 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. |
| ++minGallop; |
| let firstIteration: bool = true; |
| while (nofWinsA >= kMinGallopWins || nofWinsB >= kMinGallopWins || |
| firstIteration) { |
| firstIteration = false; |
| |
| assert(lengthA > 0 && lengthB > 1); |
| |
| minGallop = SmiMax(1, minGallop - 1); |
| sortState.minGallop = minGallop; |
| |
| let k: Smi = GallopRight( |
| workArray, tempArray.objects[cursorTemp], baseA, lengthA, |
| lengthA - 1); |
| assert(k >= 0); |
| nofWinsA = lengthA - k; |
| |
| if (nofWinsA > 0) { |
| dest = dest - nofWinsA; |
| cursorA = cursorA - nofWinsA; |
| Copy(workArray, cursorA + 1, workArray, dest + 1, nofWinsA); |
| |
| lengthA = lengthA - nofWinsA; |
| if (lengthA == 0) goto Succeed; |
| } |
| workArray.objects[dest--] = tempArray.objects[cursorTemp--]; |
| if (--lengthB == 1) goto CopyA; |
| |
| k = GallopLeft( |
| tempArray, workArray.objects[cursorA], 0, lengthB, lengthB - 1); |
| assert(k >= 0); |
| nofWinsB = lengthB - k; |
| |
| if (nofWinsB > 0) { |
| dest = dest - nofWinsB; |
| cursorTemp = cursorTemp - nofWinsB; |
| Copy(tempArray, cursorTemp + 1, workArray, dest + 1, nofWinsB); |
| |
| lengthB = lengthB - nofWinsB; |
| if (lengthB == 1) goto CopyA; |
| |
| // lengthB == 0 is impossible now if the comparison function is |
| // consistent, but we can't assume that it is. |
| if (lengthB == 0) goto Succeed; |
| } |
| workArray.objects[dest--] = workArray.objects[cursorA--]; |
| if (--lengthA == 0) goto Succeed; |
| } |
| ++minGallop; |
| sortState.minGallop = minGallop; |
| } |
| } |
| label Succeed { |
| if (lengthB > 0) { |
| assert(lengthA == 0); |
| Copy(tempArray, 0, workArray, dest - (lengthB - 1), lengthB); |
| } |
| } |
| label CopyA { |
| assert(lengthB == 1 && lengthA > 0); |
| |
| // The first element of run B belongs at the front of the merge. |
| dest = dest - lengthA; |
| cursorA = cursorA - lengthA; |
| Copy(workArray, cursorA + 1, workArray, dest + 1, lengthA); |
| workArray.objects[dest] = tempArray.objects[cursorTemp]; |
| } |
| } |
| |
| // 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 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(implicit context: Context)( |
| pendingRuns: FixedArray, n: Smi): bool { |
| if (n < 2) return true; |
| |
| const runLengthN: Smi = GetPendingRunLength(pendingRuns, n); |
| const runLengthNM: Smi = GetPendingRunLength(pendingRuns, n - 1); |
| const runLengthNMM: Smi = GetPendingRunLength(pendingRuns, n - 2); |
| |
| return runLengthNMM > runLengthNM + runLengthN; |
| } |
| |
| // 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. |
| transitioning macro MergeCollapse(context: Context, sortState: SortState) { |
| const pendingRuns: FixedArray = sortState.pendingRuns; |
| |
| // Reload the stack size because MergeAt might change it. |
| while (GetPendingRunsSize(sortState) > 1) { |
| let n: Smi = GetPendingRunsSize(sortState) - 2; |
| |
| if (!RunInvariantEstablished(pendingRuns, n + 1) || |
| !RunInvariantEstablished(pendingRuns, n)) { |
| if (GetPendingRunLength(pendingRuns, n - 1) < |
| GetPendingRunLength(pendingRuns, n + 1)) { |
| --n; |
| } |
| |
| MergeAt(n); |
| } else if ( |
| GetPendingRunLength(pendingRuns, n) <= |
| GetPendingRunLength(pendingRuns, n + 1)) { |
| MergeAt(n); |
| } else { |
| break; |
| } |
| } |
| } |
| |
| // Regardless of invariants, merge all runs on the stack until only one |
| // remains. This is used at the end of the mergesort. |
| transitioning macro |
| MergeForceCollapse(context: Context, sortState: SortState) { |
| const pendingRuns: FixedArray = sortState.pendingRuns; |
| |
| // Reload the stack size becuase MergeAt might change it. |
| while (GetPendingRunsSize(sortState) > 1) { |
| let n: Smi = GetPendingRunsSize(sortState) - 2; |
| |
| if (n > 0 && |
| GetPendingRunLength(pendingRuns, n - 1) < |
| GetPendingRunLength(pendingRuns, n + 1)) { |
| --n; |
| } |
| MergeAt(n); |
| } |
| } |
| |
| transitioning macro |
| ArrayTimSortImpl(context: Context, sortState: SortState, length: Smi) { |
| 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 minRunLength: Smi = ComputeMinRunLength(remaining); |
| while (remaining != 0) { |
| let currentRunLength: Smi = CountAndMakeRun(low, low + remaining); |
| |
| // If the run is short, extend it to min(minRunLength, remaining). |
| if (currentRunLength < minRunLength) { |
| const forcedRunLength: Smi = SmiMin(minRunLength, remaining); |
| BinaryInsertionSort(low, low + currentRunLength, low + forcedRunLength); |
| currentRunLength = forcedRunLength; |
| } |
| |
| // Push run onto pending-runs stack, and maybe merge. |
| PushRun(sortState, low, currentRunLength); |
| |
| MergeCollapse(context, sortState); |
| |
| // Advance to find next run. |
| low = low + currentRunLength; |
| remaining = remaining - currentRunLength; |
| } |
| |
| MergeForceCollapse(context, sortState); |
| assert(GetPendingRunsSize(sortState) == 1); |
| assert(GetPendingRunLength(sortState.pendingRuns, 0) == length); |
| } |
| |
| transitioning macro |
| CompactReceiverElementsIntoWorkArray( |
| implicit context: Context, sortState: SortState)(): Smi { |
| let growableWorkArray = growable_fixed_array::GrowableFixedArray{ |
| array: sortState.workArray, |
| capacity: Convert<intptr>(sortState.workArray.length), |
| length: 0 |
| }; |
| |
| const loadFn = sortState.loadFn; |
| |
| // TODO(szuend): Implement full range sorting, not only up to MaxSmi. |
| // https://crbug.com/v8/7970. |
| const receiverLength: Number = sortState.initialReceiverLength; |
| assert(IsNumberNormalized(receiverLength)); |
| |
| const sortLength: Smi = TaggedIsSmi(receiverLength) ? |
| UnsafeCast<Smi>(receiverLength) : |
| Convert<PositiveSmi>(kSmiMax) otherwise unreachable; |
| |
| // Move all non-undefined elements into {sortState.workArray}, holes |
| // are ignored. |
| let numberOfUndefined: Smi = 0; |
| for (let i: Smi = 0; i < receiverLength; ++i) { |
| const element: Object = loadFn(context, sortState, i); |
| |
| if (element == TheHole) { |
| // Do nothing for holes. The result is that elements are |
| // compacted at the front of the work array. |
| } else if (element == Undefined) { |
| numberOfUndefined++; |
| } else { |
| growableWorkArray.Push(element); |
| } |
| } |
| |
| // Reset the workArray on the frameState, as it may have grown. |
| sortState.workArray = growableWorkArray.array; |
| sortState.sortLength = sortLength; |
| sortState.numberOfUndefined = numberOfUndefined; |
| |
| return Convert<Smi>(growableWorkArray.length); |
| } |
| |
| transitioning macro |
| CopyWorkArrayToReceiver(implicit context: Context, sortState: SortState)( |
| numberOfNonUndefined: Smi) { |
| const storeFn = sortState.storeFn; |
| const workArray = sortState.workArray; |
| |
| assert(numberOfNonUndefined <= workArray.length); |
| assert( |
| numberOfNonUndefined + sortState.numberOfUndefined <= |
| sortState.sortLength); |
| |
| // Writing the elements back is a 3 step process: |
| // 1. Copy the sorted elements from the workarray to the receiver. |
| // 2. Add {nOfUndefined} undefineds to the receiver. |
| // 3. Depending on the backing store either delete properties or |
| // set them to the TheHole up to {sortState.sortLength}. |
| let index: Smi = 0; |
| for (; index < numberOfNonUndefined; ++index) { |
| storeFn(context, sortState, index, workArray.objects[index]); |
| } |
| |
| const numberOfUndefinedEnd: Smi = |
| sortState.numberOfUndefined + numberOfNonUndefined; |
| for (; index < numberOfUndefinedEnd; ++index) { |
| storeFn(context, sortState, index, Undefined); |
| } |
| |
| const end: Smi = sortState.sortLength; |
| const deleteFn = sortState.deleteFn; |
| for (; index < end; ++index) { |
| deleteFn(context, sortState, index); |
| } |
| } |
| |
| transitioning builtin |
| ArrayTimSort(context: Context, sortState: SortState): Object { |
| const numberOfNonUndefined: Smi = CompactReceiverElementsIntoWorkArray(); |
| ArrayTimSortImpl(context, sortState, numberOfNonUndefined); |
| |
| try { |
| // The comparison function or toString might have changed the |
| // receiver, if that is the case, we switch to the slow path. |
| sortState.CheckAccessor() otherwise Slow; |
| } |
| label Slow deferred { |
| sortState.ResetToGenericAccessor(); |
| } |
| |
| CopyWorkArrayToReceiver(numberOfNonUndefined); |
| return kSuccess; |
| } |
| |
| // https://tc39.github.io/ecma262/#sec-array.prototype.sort |
| transitioning javascript builtin |
| ArrayPrototypeSort(js-implicit 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]; |
| const comparefn = Cast<(Undefined | Callable)>(comparefnObj) otherwise |
| ThrowTypeError(kBadSortComparisonFunction, comparefnObj); |
| |
| // 2. Let obj be ? ToObject(this value). |
| const obj: JSReceiver = ToObject(context, receiver); |
| |
| // 3. Let len be ? ToLength(? Get(obj, "length")). |
| const len: Number = GetLengthProperty(obj); |
| |
| if (len < 2) return receiver; |
| |
| const sortState: SortState = NewSortState(obj, comparefn, len); |
| ArrayTimSort(context, sortState); |
| |
| return receiver; |
| } |
| } |