android-10.0.0_r2/s

// 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 {
  // 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.
  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);

    let elements: HeapObject = ReloadElements(sortState);
    const Load: LoadFn = GetLoadFn(sortState);

    const pending_runs: FixedArray =
        unsafe_cast<FixedArray>(sortState[kPendingRunsIdx]);
    let base_a: Smi = GetPendingRunBase(pending_runs, i);
    let length_a: Smi = GetPendingRunLength(pending_runs, i);
    let base_b: Smi = GetPendingRunBase(pending_runs, i + 1);
    let length_b: Smi = GetPendingRunLength(pending_runs, i + 1);
    assert(length_a > 0 && length_b > 0);
    assert(base_a + length_a == base_b);

    // 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;
      elements = ReloadElements(sortState);
      assert(k >= 0);

      base_a = base_a + k;
      length_a = length_a - k;
      if (length_a == 0) return kSuccess;
      assert(length_a > 0);

      // 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;
      elements = ReloadElements(sortState);
      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);
    }
  }

  macro LoadElementsOrTempArray(
      useTempArray: Boolean, sortState: FixedArray): HeapObject {
    return useTempArray == True ? GetTempArray(sortState) :
                                  ReloadElements(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);

    let last_ofs: Smi = 0;
    let offset: Smi = 1;

    try {
      const base_hint_element: Object = CallLoad(
          context, sortState, Load,
          LoadElementsOrTempArray(useTempArray, sortState), base + hint)
      otherwise Bailout;
      let order: Number =
          CallCompareFn(context, sortState, base_hint_element, key)
      otherwise Bailout;

      if (order < 0) {
        // a[base + hint] < key: gallop right, until
        // a[base + hint + last_ofs] < key <= a[base + hint + offset].

        // a[base + length - 1] is highest.
        let max_ofs: Smi = length - hint;
        while (offset < max_ofs) {
          const offset_element: Object = CallLoad(
              context, sortState, Load,
              LoadElementsOrTempArray(useTempArray, sortState),
              base + hint + offset)
          otherwise Bailout;
          order = CallCompareFn(context, sortState, offset_element, key)
          otherwise Bailout;

          // 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,
              LoadElementsOrTempArray(useTempArray, sortState),
              base + hint - offset)
          otherwise Bailout;
          order = CallCompareFn(context, sortState, offset_element, key)
          otherwise Bailout;

          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,
            LoadElementsOrTempArray(useTempArray, sortState), base + m)
        otherwise Bailout;
        order = CallCompareFn(context, sortState, base_m_element, key)
        otherwise Bailout;

        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);

    let last_ofs: Smi = 0;
    let offset: Smi = 1;

    try {
      const base_hint_element: Object = CallLoad(
          context, sortState, Load,
          LoadElementsOrTempArray(useTempArray, sortState), base + hint)
      otherwise Bailout;
      let order: Number =
          CallCompareFn(context, sortState, key, base_hint_element)
      otherwise Bailout;

      if (order < 0) {
        // key < a[base + hint]: gallop left, until
        // a[base + hint - offset] <= key < a[base + hint - last_ofs].

        // a[base + hint] is lowest.
        let max_ofs: Smi = hint + 1;
        while (offset < max_ofs) {
          const offset_element: Object = CallLoad(
              context, sortState, Load,
              LoadElementsOrTempArray(useTempArray, sortState),
              base + hint - offset)
          otherwise Bailout;
          order = CallCompareFn(context, sortState, key, offset_element)
          otherwise Bailout;

          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,
              LoadElementsOrTempArray(useTempArray, sortState),
              base + hint + offset)
          otherwise Bailout;
          order = CallCompareFn(context, sortState, key, offset_element)
          otherwise Bailout;

          // 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,
            LoadElementsOrTempArray(useTempArray, sortState), base + m)
        otherwise Bailout;
        order = CallCompareFn(context, sortState, key, base_m_element)
        otherwise Bailout;

        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;
          elements = ReloadElements(sortState);
          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;
          elements = ReloadElements(sortState);
          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;
          elements = ReloadElements(sortState);
          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;
          elements = ReloadElements(sortState);
          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);

    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[kBailoutStatusIdx] = kSuccess;

    // 3. Let len be ? ToLength(? Get(obj, "length")).
    const len: Number =
        ToLength_Inline(context, GetProperty(context, obj, 'length'));
    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(nofNonUndefined <= len);

    let map: Map = obj.map;
    sort_state[kInitialReceiverMapIdx] = map;
    sort_state[kInitialReceiverLengthIdx] = len;

    try {
      const a: JSArray = cast<JSArray>(obj) otherwise slow;
      const elementsKind: ElementsKind = map.elements_kind;
      if (!IsFastElementsKind(elementsKind)) goto slow;

      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 {
      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;
  }
}