// Copyright 2018 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include 'src/builtins/builtins-typed-array-gen.h'

namespace typed_array {
  extern runtime TypedArraySortFast(Context, Object): JSTypedArray;
  extern macro TypedArrayBuiltinsAssembler::ValidateTypedArray(
      Context, Object, constexpr string): JSTypedArray;

  extern macro LoadFixedTypedArrayElementAsTagged(
      RawPtr, Smi, constexpr ElementsKind, constexpr ParameterMode): Object;
  extern macro StoreFixedTypedArrayElementFromTagged(
      Context, FixedTypedArrayBase, Smi, Object, constexpr ElementsKind,
      constexpr ParameterMode);

  type LoadFn = builtin(Context, JSTypedArray, Smi) => Object;
  type StoreFn = builtin(Context, JSTypedArray, Smi, Object) => Object;

  // These UnsafeCast specializations are necessary becuase there is no
  // way to definitively test whether an Object is a Torque function
  // with a specific signature, and the default UnsafeCast implementation
  // would try to check this through an assert(Is<>), so the test
  // is bypassed in this specialization.
  UnsafeCast<LoadFn>(implicit context: Context)(o: Object): LoadFn {
    return %RawObjectCast<LoadFn>(o);
  }
  UnsafeCast<StoreFn>(implicit context: Context)(o: Object): StoreFn {
    return %RawObjectCast<StoreFn>(o);
  }

  macro KindForArrayType<T: type>(): constexpr ElementsKind;
  KindForArrayType<FixedUint8Array>(): constexpr ElementsKind {
    return UINT8_ELEMENTS;
  }
  KindForArrayType<FixedInt8Array>(): constexpr ElementsKind {
    return INT8_ELEMENTS;
  }
  KindForArrayType<FixedUint16Array>(): constexpr ElementsKind {
    return UINT16_ELEMENTS;
  }
  KindForArrayType<FixedInt16Array>(): constexpr ElementsKind {
    return INT16_ELEMENTS;
  }
  KindForArrayType<FixedUint32Array>(): constexpr ElementsKind {
    return UINT32_ELEMENTS;
  }
  KindForArrayType<FixedInt32Array>(): constexpr ElementsKind {
    return INT32_ELEMENTS;
  }
  KindForArrayType<FixedFloat32Array>(): constexpr ElementsKind {
    return FLOAT32_ELEMENTS;
  }
  KindForArrayType<FixedFloat64Array>(): constexpr ElementsKind {
    return FLOAT64_ELEMENTS;
  }
  KindForArrayType<FixedUint8ClampedArray>(): constexpr ElementsKind {
    return UINT8_CLAMPED_ELEMENTS;
  }
  KindForArrayType<FixedBigUint64Array>(): constexpr ElementsKind {
    return BIGUINT64_ELEMENTS;
  }
  KindForArrayType<FixedBigInt64Array>(): constexpr ElementsKind {
    return BIGINT64_ELEMENTS;
  }

  builtin LoadFixedElement<T: type>(
      context: Context, array: JSTypedArray, index: Smi): Object {
    return LoadFixedTypedArrayElementAsTagged(
        array.data_ptr, index, KindForArrayType<T>(), SMI_PARAMETERS);
  }

  builtin StoreFixedElement<T: type>(
      context: Context, array: JSTypedArray, index: Smi,
      value: Object): Object {
    const elements: FixedTypedArrayBase =
        UnsafeCast<FixedTypedArrayBase>(array.elements);
    StoreFixedTypedArrayElementFromTagged(
        context, elements, index, value, KindForArrayType<T>(), SMI_PARAMETERS);
    return Undefined;
  }

  transitioning macro CallCompareWithDetachedCheck(
      context: Context, array: JSTypedArray, comparefn: Callable, a: Object,
      b: Object): Number
      labels Detached {
    // a. Let v be ? ToNumber(? Call(comparefn, undefined, x, y)).
    const v: Number =
        ToNumber_Inline(context, Call(context, comparefn, Undefined, a, b));

    // b. If IsDetachedBuffer(buffer) is true, throw a TypeError exception.
    if (IsDetachedBuffer(array.buffer)) goto Detached;

    // c. If v is NaN, return +0.
    if (NumberIsNaN(v)) return 0;

    // d. return v.
    return v;
  }

  // InsertionSort is used for smaller arrays.
  transitioning macro TypedArrayInsertionSort(
      context: Context, array: JSTypedArray, fromArg: Smi, toArg: Smi,
      comparefn: Callable, load: LoadFn, store: StoreFn)
      labels Detached {
    let from: Smi = fromArg;
    let to: Smi = toArg;

    if (IsDetachedBuffer(array.buffer)) goto Detached;

    for (let i: Smi = from + 1; i < to; ++i) {
      const element: Object = load(context, array, i);
      let j: Smi = i - 1;
      for (; j >= from; --j) {
        const tmp: Object = load(context, array, j);
        const order: Number = CallCompareWithDetachedCheck(
            context, array, comparefn, tmp, element) otherwise Detached;
        if (order > 0) {
          store(context, array, j + 1, tmp);
        } else {
          break;
        }
      }
      store(context, array, j + 1, element);
    }
  }

  transitioning macro TypedArrayQuickSortImpl(
      context: Context, array: JSTypedArray, fromArg: Smi, toArg: Smi,
      comparefn: Callable, load: LoadFn, store: StoreFn)
      labels Detached {
    let from: Smi = fromArg;
    let to: Smi = toArg;

    while (to - from > 1) {
      if (to - from <= 10) {
        // TODO(szuend): Investigate InsertionSort removal.
        //               Currently it does not make any difference when the
        //               benchmarks are run locally.
        TypedArrayInsertionSort(
            context, array, from, to, comparefn, load, store)
            otherwise Detached;
        break;
      }

      // TODO(szuend): Check if a more involved thirdIndex calculation is
      //               worth it for very large arrays.
      const thirdIndex: Smi = from + ((to - from) >> 1);

      if (IsDetachedBuffer(array.buffer)) goto Detached;

      // Find a pivot as the median of first, last and middle element.
      let v0: Object = load(context, array, from);
      let v1: Object = load(context, array, to - 1);
      let v2: Object = load(context, array, thirdIndex);

      const c01: Number = CallCompareWithDetachedCheck(
          context, array, comparefn, v0, v1) otherwise Detached;
      if (c01 > 0) {
        // v1 < v0, so swap them.
        let tmp: Object = v0;
        v0 = v1;
        v1 = tmp;
      }
      // v0 <= v1.
      const c02: Number = CallCompareWithDetachedCheck(
          context, array, comparefn, v0, v2) otherwise Detached;
      if (c02 >= 0) {
        // v2 <= v0 <= v1.
        const tmp: Object = v0;
        v0 = v2;
        v2 = v1;
        v1 = tmp;
      } else {
        // v0 <= v1 && v0 < v2.
        const c12: Number = CallCompareWithDetachedCheck(
            context, array, comparefn, v1, v2) otherwise Detached;
        if (c12 > 0) {
          // v0 <= v2 < v1.
          const tmp: Object = v1;
          v1 = v2;
          v2 = tmp;
        }
      }

      // v0 <= v1 <= v2.
      store(context, array, from, v0);
      store(context, array, to - 1, v2);

      const pivot: Object = v1;
      let lowEnd: Smi = from + 1;   // Upper bound of elems lower than pivot.
      let highStart: Smi = to - 1;  // Lower bound of elems greater than pivot.

      let lowEndValue: Object = load(context, array, lowEnd);
      store(context, array, thirdIndex, lowEndValue);
      store(context, array, lowEnd, pivot);

      // From lowEnd to idx are elements equal to pivot.
      // From idx to highStart are elements that haven"t been compared yet.
      for (let idx: Smi = lowEnd + 1; idx < highStart; idx++) {
        let element: Object = load(context, array, idx);
        let order: Number = CallCompareWithDetachedCheck(
            context, array, comparefn, element, pivot) otherwise Detached;

        if (order < 0) {
          lowEndValue = load(context, array, lowEnd);
          store(context, array, idx, lowEndValue);
          store(context, array, lowEnd, element);
          lowEnd++;
        } else if (order > 0) {
          let breakFor: bool = false;

          while (order > 0) {
            highStart--;
            if (highStart == idx) {
              breakFor = true;
              break;
            }

            const topElement: Object = load(context, array, highStart);
            order = CallCompareWithDetachedCheck(
                context, array, comparefn, topElement, pivot)
                otherwise Detached;
          }

          if (breakFor) {
            break;
          }

          const highStartValue: Object = load(context, array, highStart);
          store(context, array, idx, highStartValue);
          store(context, array, highStart, element);

          if (order < 0) {
            element = load(context, array, idx);

            lowEndValue = load(context, array, lowEnd);
            store(context, array, idx, lowEndValue);
            store(context, array, lowEnd, element);
            lowEnd++;
          }
        }
      }

      if ((to - highStart) < (lowEnd - from)) {
        TypedArrayQuickSort(
            context, array, highStart, to, comparefn, load, store);
        to = lowEnd;
      } else {
        TypedArrayQuickSort(
            context, array, from, lowEnd, comparefn, load, store);
        from = highStart;
      }
    }
  }

  transitioning builtin TypedArrayQuickSort(
      context: Context, array: JSTypedArray, from: Smi, to: Smi,
      comparefn: Callable, load: LoadFn, store: StoreFn): JSTypedArray {
    try {
      TypedArrayQuickSortImpl(context, array, from, to, comparefn, load, store)
          otherwise Detached;
    }
    label Detached {
      ThrowTypeError(
          context, kDetachedOperation, '%TypedArray%.prototype.sort');
    }
    return array;
  }

  // https://tc39.github.io/ecma262/#sec-%typedarray%.prototype.sort
  transitioning javascript builtin TypedArrayPrototypeSort(
      context: Context, receiver: Object, ...arguments): JSTypedArray {
    // 1. If comparefn is not undefined and IsCallable(comparefn) is false,
    //    throw a TypeError exception.
    const comparefnObj: Object =
        arguments.length > 0 ? arguments[0] : Undefined;
    if (comparefnObj != Undefined && !TaggedIsCallable(comparefnObj)) {
      ThrowTypeError(context, kBadSortComparisonFunction, comparefnObj);
    }

    // 2. Let obj be the this value.
    const obj: Object = receiver;

    // 3. Let buffer be ? ValidateTypedArray(obj).
    //    ValidateTypedArray currently returns the array, not the ViewBuffer.
    const array: JSTypedArray =
        ValidateTypedArray(context, obj, '%TypedArray%.prototype.sort');

    // Default sorting is done in C++ using std::sort
    if (comparefnObj == Undefined) {
      return TypedArraySortFast(context, obj);
    }

    // 4. Let len be obj.[[ArrayLength]].
    const len: Smi = array.length;

    try {
      const comparefn: Callable =
          Cast<Callable>(comparefnObj) otherwise CastError;
      let loadfn: LoadFn;
      let storefn: StoreFn;

      let elementsKind: ElementsKind = array.elements_kind;

      if (IsElementsKindGreaterThan(elementsKind, UINT32_ELEMENTS)) {
        if (elementsKind == INT32_ELEMENTS) {
          loadfn = LoadFixedElement<FixedInt32Array>;
          storefn = StoreFixedElement<FixedInt32Array>;
        } else if (elementsKind == FLOAT32_ELEMENTS) {
          loadfn = LoadFixedElement<FixedFloat32Array>;
          storefn = StoreFixedElement<FixedFloat32Array>;
        } else if (elementsKind == FLOAT64_ELEMENTS) {
          loadfn = LoadFixedElement<FixedFloat64Array>;
          storefn = StoreFixedElement<FixedFloat64Array>;
        } else if (elementsKind == UINT8_CLAMPED_ELEMENTS) {
          loadfn = LoadFixedElement<FixedUint8ClampedArray>;
          storefn = StoreFixedElement<FixedUint8ClampedArray>;
        } else if (elementsKind == BIGUINT64_ELEMENTS) {
          loadfn = LoadFixedElement<FixedBigUint64Array>;
          storefn = StoreFixedElement<FixedBigUint64Array>;
        } else if (elementsKind == BIGINT64_ELEMENTS) {
          loadfn = LoadFixedElement<FixedBigInt64Array>;
          storefn = StoreFixedElement<FixedBigInt64Array>;
        } else {
          unreachable;
        }
      } else {
        if (elementsKind == UINT8_ELEMENTS) {
          loadfn = LoadFixedElement<FixedUint8Array>;
          storefn = StoreFixedElement<FixedUint8Array>;
        } else if (elementsKind == INT8_ELEMENTS) {
          loadfn = LoadFixedElement<FixedInt8Array>;
          storefn = StoreFixedElement<FixedInt8Array>;
        } else if (elementsKind == UINT16_ELEMENTS) {
          loadfn = LoadFixedElement<FixedUint16Array>;
          storefn = StoreFixedElement<FixedUint16Array>;
        } else if (elementsKind == INT16_ELEMENTS) {
          loadfn = LoadFixedElement<FixedInt16Array>;
          storefn = StoreFixedElement<FixedInt16Array>;
        } else if (elementsKind == UINT32_ELEMENTS) {
          loadfn = LoadFixedElement<FixedUint32Array>;
          storefn = StoreFixedElement<FixedUint32Array>;
        } else {
          unreachable;
        }
      }

      TypedArrayQuickSort(context, array, 0, len, comparefn, loadfn, storefn);
    }
    label CastError {
      unreachable;
    }
    return array;
  }
}