// 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 {
  // Naming convention from elements.cc. We have a similar intent but implement
  // fastpaths using generics instead of using a class hierarchy for elements
  // kinds specific implementations.
  type Uint8Elements;
  type Int8Elements;
  type Uint16Elements;
  type Int16Elements;
  type Uint32Elements;
  type Int32Elements;
  type Float32Elements;
  type Float64Elements;
  type Uint8ClampedElements;
  type BigUint64Elements;
  type BigInt64Elements;

  struct TypedArrayElementsInfo {
    // Calculates the number of bytes required for specified number of elements.
    CalculateByteLength(lengthSmi: PositiveSmi): uintptr labels IfInvalid {
      const length = Convert<uintptr>(lengthSmi);
      const byteLength = length << this.sizeLog2;
      // If an overflow ocurred, the byte length exceeds
      // JSArrayBuffer::kMaxByteLength and is invalid.
      if (byteLength >>> this.sizeLog2 != length) goto IfInvalid;
      return byteLength;
    }

    // Calculates the maximum number of elements supported by a specified number
    // of bytes.
    CalculateLength(byteLength: uintptr): PositiveSmi labels IfInvalid {
      return Convert<PositiveSmi>(byteLength >>> this.sizeLog2)
          otherwise IfInvalid;
    }

    // Determines if `bytes` (byte offset or length) cannot be evenly divided by
    // element size.
    IsUnaligned(bytes: uintptr): bool {
      // Exploits the fact the element size is a power of 2. Determining whether
      // there is remainder (not aligned) can be achieved efficiently with bit
      // masking. Shift is safe as sizeLog2 can be 3 at most (see
      // ElementsKindToShiftSize).
      return (bytes & ((1 << this.sizeLog2) - 1)) != 0;
    }

    sizeLog2: uintptr;
    kind: ElementsKind;
  }
  extern runtime TypedArraySortFast(Context, Object): JSTypedArray;
  extern macro TypedArrayBuiltinsAssembler::ValidateTypedArray(
      Context, Object, constexpr string): JSTypedArray;

  extern macro TypedArrayBuiltinsAssembler::CallCMemcpy(
      RawPtr, RawPtr, uintptr): void;
  extern macro TypedArrayBuiltinsAssembler::CallCMemmove(
      RawPtr, RawPtr, uintptr): void;
  extern macro TypedArrayBuiltinsAssembler::CallCMemset(
      RawPtr, intptr, uintptr): void;
  extern macro TypedArrayBuiltinsAssembler::GetBuffer(
      implicit context: Context)(JSTypedArray): JSArrayBuffer;
  extern macro TypedArrayBuiltinsAssembler::GetTypedArrayElementsInfo(
      JSTypedArray): TypedArrayElementsInfo;
  extern macro TypedArrayBuiltinsAssembler::GetTypedArrayElementsInfo(Map):
      TypedArrayElementsInfo;
  extern macro TypedArrayBuiltinsAssembler::IsBigInt64ElementsKind(
      ElementsKind): bool;
  extern macro LoadFixedTypedArrayElementAsTagged(
      RawPtr, Smi, constexpr ElementsKind): Numeric;
  extern macro StoreJSTypedArrayElementFromTagged(
      Context, JSTypedArray, Smi, Object, constexpr ElementsKind);

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

  // AttachedJSTypedArray guards that the array's buffer is not detached.
  transient type AttachedJSTypedArray extends JSTypedArray;

  macro EnsureAttached(array: JSTypedArray): AttachedJSTypedArray
      labels Detached {
    if (IsDetachedBuffer(array.buffer)) goto Detached;
    return %RawDownCast<AttachedJSTypedArray>(array);
  }

  struct AttachedJSTypedArrayWitness {
    Get(): AttachedJSTypedArray {
      return this.unstable;
    }

    GetStable(): JSTypedArray {
      return this.stable;
    }

    Recheck() labels Detached {
      if (IsDetachedBuffer(this.stable.buffer)) goto Detached;
      this.unstable = %RawDownCast<AttachedJSTypedArray>(this.stable);
    }

    Load(implicit context: Context)(k: Smi): Object {
      const lf: LoadFn = this.loadfn;
      return lf(context, this.unstable, k);
    }

    stable: JSTypedArray;
    unstable: AttachedJSTypedArray;
    loadfn: LoadFn;
  }

  macro NewAttachedJSTypedArrayWitness(array: AttachedJSTypedArray):
      AttachedJSTypedArrayWitness {
    const kind = array.elements_kind;
    return AttachedJSTypedArrayWitness{
      stable: array,
      unstable: array,
      loadfn: GetLoadFnForElementsKind(kind)
    };
  }

  macro GetLoadFnForElementsKind(elementsKind: ElementsKind): LoadFn {
    if (IsElementsKindGreaterThan(elementsKind, UINT32_ELEMENTS)) {
      if (elementsKind == INT32_ELEMENTS) {
        return LoadFixedElement<Int32Elements>;
      } else if (elementsKind == FLOAT32_ELEMENTS) {
        return LoadFixedElement<Float32Elements>;
      } else if (elementsKind == FLOAT64_ELEMENTS) {
        return LoadFixedElement<Float64Elements>;
      } else if (elementsKind == UINT8_CLAMPED_ELEMENTS) {
        return LoadFixedElement<Uint8ClampedElements>;
      } else if (elementsKind == BIGUINT64_ELEMENTS) {
        return LoadFixedElement<BigUint64Elements>;
      } else if (elementsKind == BIGINT64_ELEMENTS) {
        return LoadFixedElement<BigInt64Elements>;
      } else {
        unreachable;
      }
    } else {
      if (elementsKind == UINT8_ELEMENTS) {
        return LoadFixedElement<Uint8Elements>;
      } else if (elementsKind == INT8_ELEMENTS) {
        return LoadFixedElement<Int8Elements>;
      } else if (elementsKind == UINT16_ELEMENTS) {
        return LoadFixedElement<Uint16Elements>;
      } else if (elementsKind == INT16_ELEMENTS) {
        return LoadFixedElement<Int16Elements>;
      } else if (elementsKind == UINT32_ELEMENTS) {
        return LoadFixedElement<Uint32Elements>;
      } else {
        unreachable;
      }
    }
  }

  macro KindForArrayType<T: type>(): constexpr ElementsKind;
  KindForArrayType<Uint8Elements>(): constexpr ElementsKind {
    return UINT8_ELEMENTS;
  }
  KindForArrayType<Int8Elements>(): constexpr ElementsKind {
    return INT8_ELEMENTS;
  }
  KindForArrayType<Uint16Elements>(): constexpr ElementsKind {
    return UINT16_ELEMENTS;
  }
  KindForArrayType<Int16Elements>(): constexpr ElementsKind {
    return INT16_ELEMENTS;
  }
  KindForArrayType<Uint32Elements>(): constexpr ElementsKind {
    return UINT32_ELEMENTS;
  }
  KindForArrayType<Int32Elements>(): constexpr ElementsKind {
    return INT32_ELEMENTS;
  }
  KindForArrayType<Float32Elements>(): constexpr ElementsKind {
    return FLOAT32_ELEMENTS;
  }
  KindForArrayType<Float64Elements>(): constexpr ElementsKind {
    return FLOAT64_ELEMENTS;
  }
  KindForArrayType<Uint8ClampedElements>(): constexpr ElementsKind {
    return UINT8_CLAMPED_ELEMENTS;
  }
  KindForArrayType<BigUint64Elements>(): constexpr ElementsKind {
    return BIGUINT64_ELEMENTS;
  }
  KindForArrayType<BigInt64Elements>(): constexpr ElementsKind {
    return BIGINT64_ELEMENTS;
  }

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

  builtin StoreFixedElement<T: type>(
      context: Context, typedArray: JSTypedArray, index: Smi,
      value: Object): Object {
    StoreJSTypedArrayElementFromTagged(
        context, typedArray, index, value, KindForArrayType<T>());
    return Undefined;
  }

  transitioning macro CallCompare(
      implicit context: Context, array: JSTypedArray,
      comparefn: Callable)(a: Object, b: Object): Number {
    // 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)) {
      ThrowTypeError(kDetachedOperation, '%TypedArray%.prototype.sort');
    }

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

    // d. return v.
    return v;
  }

  // Merges two sorted runs [from, middle) and [middle, to)
  // from "source" into "target".
  transitioning macro
  TypedArrayMerge(
      implicit context: Context, array: JSTypedArray, comparefn: Callable)(
      source: FixedArray, from: Smi, middle: Smi, to: Smi, target: FixedArray) {
    let left: Smi = from;
    let right: Smi = middle;

    for (let targetIndex: Smi = from; targetIndex < to; ++targetIndex) {
      if (left < middle && right >= to) {
        // If the left run has elements, but the right does not, we take
        // from the left.
        target.objects[targetIndex] = source.objects[left++];
      } else if (left < middle) {
        // If both have elements, we need to compare.
        const leftElement: Object = source.objects[left];
        const rightElement: Object = source.objects[right];
        if (CallCompare(leftElement, rightElement) <= 0) {
          target.objects[targetIndex] = leftElement;
          left++;
        } else {
          target.objects[targetIndex] = rightElement;
          right++;
        }
      } else {
        // No elements on the left, but the right does, so we take
        // from the right.
        assert(left == middle);
        target.objects[targetIndex] = source.objects[right++];
      }
    }
  }

  transitioning builtin
  TypedArrayMergeSort(
      implicit context: Context, array: JSTypedArray, comparefn: Callable)(
      source: FixedArray, from: Smi, to: Smi, target: FixedArray): Object {
    assert(to - from > 1);
    const middle: Smi = from + ((to - from) >> 1);

    // On the next recursion step source becomes target and vice versa.
    // This saves the copy of the relevant range from the original
    // array into a work array on each recursion step.
    if (middle - from > 1) TypedArrayMergeSort(target, from, middle, source);
    if (to - middle > 1) TypedArrayMergeSort(target, middle, to, source);

    TypedArrayMerge(source, from, middle, to, target);

    return Undefined;
  }

  // https://tc39.github.io/ecma262/#sec-%typedarray%.prototype.sort
  transitioning javascript builtin TypedArrayPrototypeSort(
      js-implicit 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(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]].
    // TODO(v8:4153): Support huge TypedArrays here.
    const len = Cast<Smi>(Convert<Number>(array.length)) otherwise unreachable;

    // Arrays of length 1 or less are considered sorted.
    if (len < 2) return array;

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

    const elementsKind: ElementsKind = array.elements_kind;

    if (IsElementsKindGreaterThan(elementsKind, UINT32_ELEMENTS)) {
      if (elementsKind == INT32_ELEMENTS) {
        loadfn = LoadFixedElement<Int32Elements>;
        storefn = StoreFixedElement<Int32Elements>;
      } else if (elementsKind == FLOAT32_ELEMENTS) {
        loadfn = LoadFixedElement<Float32Elements>;
        storefn = StoreFixedElement<Float32Elements>;
      } else if (elementsKind == FLOAT64_ELEMENTS) {
        loadfn = LoadFixedElement<Float64Elements>;
        storefn = StoreFixedElement<Float64Elements>;
      } else if (elementsKind == UINT8_CLAMPED_ELEMENTS) {
        loadfn = LoadFixedElement<Uint8ClampedElements>;
        storefn = StoreFixedElement<Uint8ClampedElements>;
      } else if (elementsKind == BIGUINT64_ELEMENTS) {
        loadfn = LoadFixedElement<BigUint64Elements>;
        storefn = StoreFixedElement<BigUint64Elements>;
      } else if (elementsKind == BIGINT64_ELEMENTS) {
        loadfn = LoadFixedElement<BigInt64Elements>;
        storefn = StoreFixedElement<BigInt64Elements>;
      } else {
        unreachable;
      }
    } else {
      if (elementsKind == UINT8_ELEMENTS) {
        loadfn = LoadFixedElement<Uint8Elements>;
        storefn = StoreFixedElement<Uint8Elements>;
      } else if (elementsKind == INT8_ELEMENTS) {
        loadfn = LoadFixedElement<Int8Elements>;
        storefn = StoreFixedElement<Int8Elements>;
      } else if (elementsKind == UINT16_ELEMENTS) {
        loadfn = LoadFixedElement<Uint16Elements>;
        storefn = StoreFixedElement<Uint16Elements>;
      } else if (elementsKind == INT16_ELEMENTS) {
        loadfn = LoadFixedElement<Int16Elements>;
        storefn = StoreFixedElement<Int16Elements>;
      } else if (elementsKind == UINT32_ELEMENTS) {
        loadfn = LoadFixedElement<Uint32Elements>;
        storefn = StoreFixedElement<Uint32Elements>;
      } else {
        unreachable;
      }
    }

    // Prepare the two work arrays. All numbers are converted to tagged
    // objects first, and merge sorted between the two FixedArrays.
    // The result is then written back into the JSTypedArray.
    const work1: FixedArray = AllocateZeroedFixedArray(Convert<intptr>(len));
    const work2: FixedArray = AllocateZeroedFixedArray(Convert<intptr>(len));

    for (let i: Smi = 0; i < len; ++i) {
      const element: Object = loadfn(context, array, i);
      work1.objects[i] = element;
      work2.objects[i] = element;
    }

    TypedArrayMergeSort(work2, 0, len, work1);

    // work1 contains the sorted numbers. Write them back.
    for (let i: Smi = 0; i < len; ++i)
      storefn(context, array, i, work1.objects[i]);

    return array;
  }
}