src/builtins/array.tq

// 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.

module array {
  macro FastArraySplice(
      context: Context, args: Arguments, o: Object,
      originalLengthNumber: Number, actualStartNumber: Number, insertCount: Smi,
      actualDeleteCountNumber: Number): Object
  labels Bailout {
    let originalLength: Smi = cast<Smi>(originalLengthNumber) otherwise Bailout;
    let actualStart: Smi = cast<Smi>(actualStartNumber) otherwise Bailout;
    let actualDeleteCount: Smi =
        cast<Smi>(actualDeleteCountNumber) otherwise Bailout;
    let lengthDelta: Smi = insertCount - actualDeleteCount;
    let newLength: Smi = originalLength + lengthDelta;

    let a: JSArray = cast<JSArray>(o) otherwise Bailout;

    let map: Map = a.map;
    if (!IsPrototypeInitialArrayPrototype(context, map)) goto Bailout;
    if (IsNoElementsProtectorCellInvalid()) goto Bailout;
    if (IsArraySpeciesProtectorCellInvalid()) goto Bailout;

    // Fast path only works on fast elements kind and with writable length.
    let elementsKind: ElementsKind = EnsureArrayPushable(map) otherwise Bailout;
    if (!IsFastElementsKind(elementsKind)) goto Bailout;

    // For now, only support non-double fast elements
    if (!IsFastSmiOrTaggedElementsKind(elementsKind)) goto Bailout;

    if (IsFastSmiElementsKind(elementsKind)) {
      for (let e: Object of args [2: ]) {
        if (TaggedIsNotSmi(e)) goto Bailout;
      }
    }

    // Make sure that the length hasn't been changed by side-effect.
    let length: Smi = cast<Smi>(a.length) otherwise Bailout;
    if (originalLength != length) goto Bailout;

    let deletedResult: JSArray =
        ExtractFastJSArray(context, a, actualStart, actualDeleteCount);

    if (newLength == 0) {
      a.elements = kEmptyFixedArray;
      a.length = 0;
      return deletedResult;
    }

    let elements: FixedArray = cast<FixedArray>(a.elements) otherwise Bailout;
    let elementsMap: Map = elements.map;

    // If the source is a COW array or the spliced array is larger then the
    // source array, then allocate a new FixedArray to hold the result.
    let newElements: FixedArray = elements;
    if ((elementsMap == kCOWMap) || (lengthDelta > 0)) {
      newElements = ExtractFixedArray(
          elements, 0, actualStart, newLength, kAllFixedArrays);
      newElements.map = elementsMap;
      a.elements = newElements;
    }

    // Double check that the array is still in fast elements mode
    assert(IsFastSmiElementsKind(a.map.elements_kind));

    // Copy over inserted elements.
    let k: Smi = actualStart;
    if (insertCount > 0) {
      for (let e: Object of args [2: ]) {
        newElements[k++] = e;
      }
    }

    // Copy over elements after deleted elements.
    let count: Smi = length - actualStart - actualDeleteCount;
    while (count > 0) {
      let e: Object = elements[k - lengthDelta];
      newElements[k++] = e;
      count--;
    }

    // Fill rest of spliced FixedArray with the hole, but only if the
    // destination FixedArray is the original array's, since otherwise the array
    // is pre-filled with holes.
    if (elements == newElements) {
      let limit: Smi = elements.length;
      while (k < limit) {
        newElements[k++] = Hole;
      }
    }

    // Update the array's length after all the FixedArray shuffling is done.
    a.length = newLength;

    return deletedResult;
  }

  // https://tc39.github.io/ecma262/#sec-array.prototype.splice
  javascript builtin ArraySpliceTorque(
      context: Context, receiver: Object, ...arguments): Object {
    // 1. Let O be ? ToObject(this value).
    let o: Object = ToObject(context, receiver);

    // 2. Let len be ? ToLength(? Get(O, "length")).
    let len: Number =
        ToLength_Inline(context, GetProperty(context, o, 'length'));

    // 3. Let relativeStart be ? ToInteger(start).
    let start: Object = arguments[0];
    let relativeStart: Number = ToInteger_Inline(context, start);

    // 4. If relativeStart < 0, let actualStart be max((len + relativeStart),
    // 0);
    //    else let actualStart be min(relativeStart, len).
    let actualStart: Number = relativeStart < 0 ?
        max((len + relativeStart), 0) :
        min(relativeStart, len);

    let insertCount: Smi;
    let actualDeleteCount: Number;
    // 5. If the Number of actual arguments is 0, then
    if (arguments.length == 0) {
      // a. Let insertCount be 0.
      insertCount = 0;
      // b. Let actualDeleteCount be 0.
      actualDeleteCount = 0;
      // 6. Else if the Number of actual arguments is 1, then
    } else if (arguments.length == 1) {
      // a. Let insertCount be 0.
      insertCount = 0;
      // b. Let actualDeleteCount be len - actualStart.
      actualDeleteCount = len - actualStart;
      // 7. Else,
    } else {
      // a. Let insertCount be the Number of actual arguments minus 2.
      insertCount = convert<Smi>(arguments.length) - 2;
      // b. Let dc be ? ToInteger(deleteCount).
      let deleteCount: Object = arguments[1];
      let dc: Number = ToInteger_Inline(context, deleteCount);
      // c. Let actualDeleteCount be min(max(dc, 0), len - actualStart).
      actualDeleteCount = min(max(dc, 0), len - actualStart);
    }

    // 8. If len + insertCount - actualDeleteCount > 2^53-1, throw a
    //    Bailout exception.
    if (len + insertCount - actualDeleteCount > kMaxSafeInteger) {
      ThrowRangeError(context, kInvalidArrayLengthMessage);
    }

    try {
      return FastArraySplice(
          context, arguments, o, len, actualStart, insertCount,
          actualDeleteCount) otherwise Bailout;
    }
    label Bailout {}
    // If the fast case fails, just continue with the slow, correct,
    // spec-compliant case.

    // 9. Let A be ? ArraySpeciesCreate(O, actualDeleteCount).
    let a: Object = ArraySpeciesCreate(context, o, actualDeleteCount);

    // 10. Let k be 0.
    let k: Number = 0;

    // 11. Repeat, while k < actualDeleteCount
    while (k < actualDeleteCount) {
      // a. Let from be ! ToString(actualStart + k).
      let from: String = ToString_Inline(context, actualStart + k);

      // b. Let fromPresent be ? HasProperty(O, from).
      let fromPresent: Oddball =
          HasPropertyObject(o, from, context, kHasProperty);

      // c. If fromPresent is true, then
      if (fromPresent == True) {
        // i. Let fromValue be ? Get(O, from).
        let fromValue: Object = GetProperty(context, o, from);

        // ii. Perform ? CreateDataPropertyOrThrow(A, ! ToString(k), fromValue).
        CreateDataProperty(context, a, ToString_Inline(context, k), fromValue);
      }

      // d. Increment k by 1.
      k = k + 1;
    }

    // 12. Perform ? Set(A, "length", actualDeleteCount, true).
    SetProperty(context, a, 'length', actualDeleteCount, strict);

    // 13. Let items be a List whose elements are, in left-to-right order,
    //     the portion of the actual argument list starting with the third
    //     argument. The list is empty if fewer than three arguments were
    //     passed.
    // 14. Let itemCount be the Number of elements in items.
    let itemCount: Number = insertCount;

    // 15. If itemCount < actualDeleteCount, then
    if (itemCount < actualDeleteCount) {
      // a. Let k be actualStart.
      let k: Number = actualStart;

      // b. Repeat, while k < (len - actualDeleteCount)
      while (k < (len - actualDeleteCount)) {
        // i. Let from be ! ToString(k + actualDeleteCount).
        let from: String = ToString_Inline(context, k + actualDeleteCount);
        // ii. Let to be ! ToString(k + itemCount).
        let to: String = ToString_Inline(context, k + itemCount);

        // iii. Let fromPresent be ? HasProperty(O, from).
        let fromPresent: Oddball =
            HasPropertyObject(o, from, context, kHasProperty);

        // iv. If fromPresent is true, then
        if (fromPresent == True) {
          // 1. Let fromValue be ? Get(O, from).
          let fromValue: Object = GetProperty(context, o, from);

          // 2. Perform ? Set(O, to, fromValue, true).
          SetProperty(context, o, to, fromValue, strict);

          // v. Else fromPresent is false,
        } else {
          // 1. Perform ? DeletePropertyOrThrow(O, to).
          DeleteProperty(context, o, to, strict);
        }
        // vi. Increase k by 1.
        k = k + 1;
      }

      // c. Let k be len.
      k = len;
      // d. Repeat, while k > (len - actualDeleteCount + itemCount)
      while (k > (len - actualDeleteCount + itemCount)) {
        // i. Perform ? DeletePropertyOrThrow(O, ! ToString(k - 1)).
        DeleteProperty(context, o, ToString_Inline(context, k - 1), strict);

        // ii. Decrease k by 1.
        k = k - 1;
      }
      // 16. Else if itemCount > actualDeleteCount, then
    } else if (itemCount > actualDeleteCount) {
      // a. Let k be (len - actualDeleteCount).
      let k: Number = len - actualDeleteCount;

      // b. Repeat, while k > actualStart
      while (k > actualStart) {
        // i. Let from be ! ToString(k + actualDeleteCount - 1).
        let from: String = ToString_Inline(context, k + actualDeleteCount - 1);

        // ii. Let to be ! ToString(k + itemCount - 1).
        let to: String = ToString_Inline(context, k + itemCount - 1);

        // iii. Let fromPresent be ? HasProperty(O, from).
        let fromPresent: Oddball =
            HasPropertyObject(o, from, context, kHasProperty);

        // iv. If fromPresent is true, then
        if (fromPresent == True) {
          // 1. Let fromValue be ? Get(O, from).
          let fromValue: Object = GetProperty(context, o, from);

          // 2. Perform ? Set(O, to, fromValue, true).
          SetProperty(context, o, to, fromValue, strict);

          // v. Else fromPresent is false,
        } else {
          // 1. Perform ? DeletePropertyOrThrow(O, to).
          DeleteProperty(context, o, to, strict);
        }

        // vi. Decrease k by 1.
        k = k - 1;
      }
    }

    // 17. Let k be actualStart.
    k = actualStart;

    // 18. Repeat, while items is not empty
    //   a. Remove the first element from items and let E be the value of that
    //   element.
    if (arguments.length > 2) {
      for (let e: Object of arguments [2: ]) {
        // b. Perform ? Set(O, ! ToString(k), E, true).
        SetProperty(context, o, ToString_Inline(context, k), e, strict);

        // c. Increase k by 1.
        k = k + 1;
      }
    }

    // 19. Perform ? Set(O, "length", len - actualDeleteCount + itemCount,
    // true).
    SetProperty(
        context, o, 'length', len - actualDeleteCount + itemCount, strict);

    return a;
  }

  macro ArrayForEachTorqueContinuation(
      context: Context, o: Object, len: Number, callbackfn: Callable,
      thisArg: Object, initial_k: Number): Object {
    // 5. Let k be 0.
    // 6. Repeat, while k < len
    for (let k: Number = initial_k; k < len; k = k + 1) {
      // 6a. Let Pk be ! ToString(k).
      // k is guaranteed to be a positive integer, hence ToString is
      // side-effect free and HasProperty/GetProperty do the conversion inline.

      // 6b. Let kPresent be ? HasProperty(O, Pk).
      let kPresent: Oddball = HasPropertyObject(o, k, context, kHasProperty);

      // 6c. If kPresent is true, then
      if (kPresent == True) {
        // 6c. i. Let kValue be ? Get(O, Pk).
        let kValue: Object = GetProperty(context, o, k);

        // 6c. ii. Perform ? Call(callbackfn, T, <kValue, k, O>).
        Call(context, callbackfn, thisArg, kValue, k, o);
      }

      // 6d. Increase k by 1. (done by the loop).
    }
    return Undefined;
  }

  javascript builtin ArrayForEachLoopEagerDeoptContinuation(
      context: Context, receiver: Object, callback: Object, thisArg: Object,
      initialK: Object, length: Object): Object {
    return ArrayForEachLoopContinuation(
        context, receiver, callback, thisArg, Undefined, receiver, initialK,
        length, Undefined);
  }

  javascript builtin ArrayForEachLoopLazyDeoptContinuation(
      context: Context, receiver: Object, callback: Object, thisArg: Object,
      initialK: Object, length: Object, result: Object): Object {
    return ArrayForEachLoopContinuation(
        context, receiver, callback, thisArg, Undefined, receiver, initialK,
        length, Undefined);
  }

  builtin ArrayForEachLoopContinuation(
      context: Context, receiver: Object, callback: Object, thisArg: Object,
      array: Object, object: Object, initialK: Object, length: Object,
      to: Object): Object {
    try {
      let callbackfn: Callable = cast<Callable>(callback) otherwise Unexpected;
      let k: Number = cast<Number>(initialK) otherwise Unexpected;
      let number_length: Number = cast<Number>(length) otherwise Unexpected;

      return ArrayForEachTorqueContinuation(
          context, object, number_length, callbackfn, thisArg, k);
    }
    label Unexpected {
      unreachable;
    }
  }

  macro VisitAllElements<FixedArrayType : type>(
      context: Context, a: JSArray, len: Smi, callbackfn: Callable,
      thisArg: Object): void labels
  Bailout(Smi) {
    let k: Smi = 0;
    let map: Map = a.map;

    try {
      // Build a fast loop over the smi array.
      for (; k < len; k = k + 1) {
        // Ensure that the map didn't change.
        if (map != a.map) goto Slow;
        // Ensure that we haven't walked beyond a possibly updated length.
        if (k >= a.length) goto Slow;

        try {
          let value: Object =
              LoadElementNoHole<FixedArrayType>(a, k) otherwise FoundHole;
          Call(context, callbackfn, thisArg, value, k, a);
        }
        label FoundHole {
          // If we found the hole, we need to bail out if the initial
          // array prototype has had elements inserted. This is preferable
          // to walking the prototype chain looking for elements.

          if (IsNoElementsProtectorCellInvalid()) goto Bailout(k);
        }
      }
    }
    label Slow {
      goto Bailout(k);
    }
  }

  macro FastArrayForEach(
      context: Context, o: Object, len: Number, callbackfn: Callable,
      thisArg: Object): Object labels
  Bailout(Smi) {
    let k: Smi = 0;
    try {
      let smi_len: Smi = cast<Smi>(len) otherwise Slow;
      let a: JSArray = cast<JSArray>(o) otherwise Slow;
      let map: Map = a.map;

      if (!IsPrototypeInitialArrayPrototype(context, map)) goto Slow;
      let elementsKind: ElementsKind = map.elements_kind;
      if (!IsFastElementsKind(elementsKind)) goto Slow;

      if (IsElementsKindGreaterThan(elementsKind, HOLEY_ELEMENTS)) {
        VisitAllElements<FixedDoubleArray>(
            context, a, smi_len, callbackfn, thisArg)
        otherwise Bailout;
      } else {
        VisitAllElements<FixedArray>(context, a, smi_len, callbackfn, thisArg)
        otherwise Bailout;
      }
    }
    label Slow {
      goto Bailout(k);
    }
    return Undefined;
  }

  // https://tc39.github.io/ecma262/#sec-array.prototype.foreach
  javascript builtin ArrayForEach(
      context: Context, receiver: Object, ...arguments): Object {
    try {
      if (IsNullOrUndefined(receiver)) {
        goto NullOrUndefinedError;
      }

      // 1. Let O be ? ToObject(this value).
      let o: Object = ToObject(context, receiver);

      // 2. Let len be ? ToLength(? Get(O, "length")).
      let len: Number =
          ToLength_Inline(context, GetProperty(context, o, 'length'));

      // 3. If IsCallable(callbackfn) is false, throw a TypeError exception.
      if (arguments.length == 0) {
        goto TypeError;
      }
      let callbackfn: Callable =
          cast<Callable>(arguments[0]) otherwise TypeError;

      // 4. If thisArg is present, let T be thisArg; else let T be undefined.
      let thisArg: Object = arguments.length > 1 ? arguments[1] : Undefined;

      // Special cases.
      let k: Number = 0;
      try {
        return FastArrayForEach(context, o, len, callbackfn, thisArg)
        otherwise Bailout;
      }
      label Bailout(k_value: Smi) {
        k = k_value;
      }

      return ArrayForEachTorqueContinuation(
          context, o, len, callbackfn, thisArg, k);
    }
    label TypeError {
      ThrowTypeError(context, kCalledNonCallable, arguments[0]);
    }
    label NullOrUndefinedError {
      ThrowTypeError(
          context, kCalledOnNullOrUndefined, 'Array.prototype.forEach');
    }
  }
}