third_party/v8/builtins/array-sort.tq

// 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 {
    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.bailoutStatus = kSuccess;
    }

    // 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 three function pointer represent a Accessor/Path.
    // These are used to Load/Store elements and to check whether to bail to the
    // baseline GenericElementsAccessor.
    loadFn: LoadFn;
    storeFn: StoreFn;
    canUseSameAccessorFn: CanUseSameAccessorFn;

    // If this field has the value kFailure, we need to bail to the baseline
    // GenericElementsAccessor.
    bailoutStatus: Smi;

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

  transitioning macro NewSortState(implicit context: Context)(
      receiver: JSReceiver, comparefn: Undefined | Callable,
      initialReceiverLength: Number, sortLength: Smi,
      forceGeneric: constexpr bool): SortState {
    const sortComparePtr =
        comparefn != Undefined ? SortCompareUserFn : SortCompareDefault;
    const map = receiver.map;
    let loadFn = Load<GenericElementsAccessor>;
    let storeFn = Store<GenericElementsAccessor>;
    let canUseSameAccessorFn = CanUseSameAccessor<GenericElementsAccessor>;

    try {
      if constexpr (!forceGeneric) {
        GotoIfForceSlowPath() otherwise Slow;
        let a: FastJSArray = Cast<FastJSArray>(receiver) otherwise Slow;

        const elementsKind: ElementsKind = map.elements_kind;
        if (IsDoubleElementsKind(elementsKind)) {
          loadFn = Load<FastDoubleElements>;
          storeFn = Store<FastDoubleElements>;
          canUseSameAccessorFn = CanUseSameAccessor<FastDoubleElements>;
        } else if (elementsKind == PACKED_SMI_ELEMENTS) {
          loadFn = Load<FastPackedSmiElements>;
          storeFn = Store<FastPackedSmiElements>;
          canUseSameAccessorFn = CanUseSameAccessor<FastPackedSmiElements>;
        } else {
          loadFn = Load<FastSmiOrObjectElements>;
          storeFn = Store<FastSmiOrObjectElements>;
          canUseSameAccessorFn = CanUseSameAccessor<FastSmiOrObjectElements>;
        }
      }
    }
    label Slow {
      if (map.elements_kind == DICTIONARY_ELEMENTS && IsExtensibleMap(map) &&
          !IsCustomElementsReceiverInstanceType(map.instance_type)) {
        loadFn = Load<DictionaryElements>;
        storeFn = Store<DictionaryElements>;
        canUseSameAccessorFn = CanUseSameAccessor<DictionaryElements>;
      }
    }

    return new SortState{
      receiver,
      initialReceiverMap: map,
      initialReceiverLength,
      userCmpFn: comparefn,
      sortComparePtr,
      loadFn,
      storeFn,
      canUseSameAccessorFn,
      bailoutStatus: kSuccess,
      minGallop: kMinGallopWins,
      pendingRunsSize: 0,
      pendingRuns: AllocateZeroedFixedArray(Convert<intptr>(kMaxMergePending)),
      workArray: AllocateZeroedFixedArray(Convert<intptr>(sortLength)),
      tempArray: kEmptyFixedArray
    };
  }

  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, SortState, Smi) => Object;
  type StoreFn = builtin(Context, SortState, 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.

  transitioning builtin Load<ElementsAccessor: type>(
      context: Context, sortState: SortState, index: Smi): Object {
    return GetProperty(sortState.receiver, index);
  }

  Load<FastPackedSmiElements>(
      context: Context, sortState: SortState, index: Smi): Object {
    const object = UnsafeCast<JSObject>(sortState.receiver);
    const elements = UnsafeCast<FixedArray>(object.elements);
    return elements.objects[index];
  }

  Load<FastSmiOrObjectElements>(
      context: Context, sortState: SortState, index: Smi): Object {
    const object = UnsafeCast<JSObject>(sortState.receiver);
    const elements = UnsafeCast<FixedArray>(object.elements);
    const result: Object = elements.objects[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: SortState, index: Smi):
      Object {
    try {
      const object = UnsafeCast<JSObject>(sortState.receiver);
      const elements = UnsafeCast<FixedDoubleArray>(object.elements);
      const value = LoadDoubleWithHoleCheck(elements, 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: SortState, index: Smi):
      Object {
    try {
      const object = UnsafeCast<JSObject>(sortState.receiver);
      const dictionary = UnsafeCast<NumberDictionary>(object.elements);
      const intptrIndex = Convert<intptr>(index);
      return BasicLoadNumberDictionaryElement(dictionary, intptrIndex)
          otherwise Bailout, Bailout;
    }
    label Bailout {
      return Failure(sortState);
    }
  }

  transitioning builtin Store<ElementsAccessor: type>(
      context: Context, sortState: SortState, index: Smi, value: Object): Smi {
    SetProperty(sortState.receiver, index, value);
    return kSuccess;
  }

  Store<FastPackedSmiElements>(
      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<FastSmiOrObjectElements>(
      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;
  }

  Store<DictionaryElements>(
      context: Context, sortState: SortState, index: Smi, value: Object): Smi {
    const object = UnsafeCast<JSObject>(sortState.receiver);
    const dictionary = UnsafeCast<NumberDictionary>(object.elements);
    const intptrIndex = Convert<intptr>(index);
    try {
      BasicStoreNumberDictionaryElement(dictionary, intptrIndex, 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 = sortState.receiver;
      ThrowTypeError(
          kStrictReadOnlyProperty, index, Typeof(receiver), receiver);
    }
    label Fail {
      return Failure(sortState);
    }
  }

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

  CanUseSameAccessor<DictionaryElements>(
      context: Context, receiver: JSReceiver, initialReceiverMap: Object,
      initialReceiverLength: Number): Boolean {
    return SelectBooleanConstant(receiver.map == initialReceiverMap);
  }

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

  // This macro jumps to the Bailout label iff kBailoutStatus is kFailure.
  macro EnsureSuccess(implicit context: Context)(sortState:
                                                     SortState) labels Bailout {
    if (sortState.bailoutStatus == kFailure) goto Bailout;
  }

  // Sets kBailoutStatus to kFailure and returns kFailure.
  macro Failure(sortState: SortState): Smi {
    sortState.bailoutStatus = 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(implicit context: Context, sortState: SortState)(
      load: LoadFn, index: Smi): Object
      labels Bailout {
    const result: Object = load(context, sortState, index);
    EnsureSuccess(sortState) otherwise Bailout;
    return result;
  }

  macro CallStore(implicit context: Context, sortState: SortState)(
      store: StoreFn, index: Smi, value: Object) labels Bailout {
    store(context, sortState, index, value);
    EnsureSuccess(sortState) otherwise Bailout;
  }

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

    let 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);
    let baseB: Smi = GetPendingRunBase(pendingRuns, i + 1);
    let lengthB: Smi = GetPendingRunLength(pendingRuns, i + 1);
    assert(lengthA > 0 && lengthB > 0);
    assert(baseA + lengthA == baseB);

    // Record the length of the combined runs; if i is the 3rd-last run now,
    // also slide over the last run (which isn't involved in this merge).
    // The current run i + 1 goes away in any case.
    SetPendingRunLength(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.
      let 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.
      let 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.
      let 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.
      let 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);

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

          let 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) {
    let 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
  CopyReceiverElementsToWorkArray(
      implicit context: Context, sortState: SortState)(length: Smi) {
    // TODO(szuend): Investigate if we can use COW arrays or a memcpy + range
    //               barrier to speed this step up.
    let loadFn = sortState.loadFn;
    const workArray = sortState.workArray;

    for (let i: Smi = 0; i < length; ++i) {
      try {
        workArray.objects[i] = CallLoad(loadFn, i) otherwise Bailout;
      }
      label Bailout deferred {
        sortState.ResetToGenericAccessor();
        loadFn = sortState.loadFn;
        workArray.objects[i] = CallLoad(loadFn, i) otherwise unreachable;
      }
    }
  }

  transitioning macro
  CopyWorkArrayToReceiver(implicit context: Context, sortState: SortState)(
      length: Smi) {
    // TODO(szuend): Build fast-path that simply installs the work array as the
    // new backing store where applicable.
    let storeFn = sortState.storeFn;
    const workArray = sortState.workArray;

    for (let i: Smi = 0; i < length; ++i) {
      try {
        CallStore(storeFn, i, workArray.objects[i]) otherwise Bailout;
      }
      label Bailout deferred {
        sortState.ResetToGenericAccessor();
        storeFn = sortState.storeFn;
        CallStore(storeFn, i, workArray.objects[i]) otherwise unreachable;
      }
    }
  }

  transitioning builtin
  ArrayTimSort(context: Context, sortState: SortState, length: Smi): Object {
    CopyReceiverElementsToWorkArray(length);
    ArrayTimSortImpl(context, sortState, length);

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

  // https://tc39.github.io/ecma262/#sec-array.prototype.sort
  transitioning 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];
    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;

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

    if (nofNonUndefined < 2) return receiver;

    const sortState: SortState =
        NewSortState(obj, comparefn, len, nofNonUndefined, false);
    ArrayTimSort(context, sortState, nofNonUndefined);

    return receiver;
  }
}