src/builtins/array-reverse.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 LoadElement<ElementsAccessor : type, T : type>(
      elements: FixedArrayBase, index: Smi): T;

  LoadElement<FastPackedSmiElements, Smi>(
      elements: FixedArrayBase, index: Smi): Smi {
    const elems: FixedArray = unsafe_cast<FixedArray>(elements);
    return unsafe_cast<Smi>(elems[index]);
  }

  LoadElement<FastPackedObjectElements, Object>(
      elements: FixedArrayBase, index: Smi): Object {
    const elems: FixedArray = unsafe_cast<FixedArray>(elements);
    return elems[index];
  }

  LoadElement<FastPackedDoubleElements, float64>(
      elements: FixedArrayBase, index: Smi): float64 {
    try {
      const elems: FixedDoubleArray = unsafe_cast<FixedDoubleArray>(elements);
      return LoadDoubleWithHoleCheck(elems, index) otherwise Hole;
    }
    label Hole {
      // This macro is only used for PACKED_DOUBLE, loading the hole should
      // be impossible.
      unreachable;
    }
  }

  macro StoreElement<ElementsAccessor : type, T : type>(
      elements: FixedArrayBase, index: Smi, value: T);

  StoreElement<FastPackedSmiElements, Smi>(
      elements: FixedArrayBase, index: Smi, value: Smi) {
    const elems: FixedArray = unsafe_cast<FixedArray>(elements);
    StoreFixedArrayElementSmi(elems, index, value, SKIP_WRITE_BARRIER);
  }

  StoreElement<FastPackedObjectElements, Object>(
      elements: FixedArrayBase, index: Smi, value: Object) {
    const elems: FixedArray = unsafe_cast<FixedArray>(elements);
    elems[index] = value;
  }

  StoreElement<FastPackedDoubleElements, float64>(
      elements: FixedArrayBase, index: Smi, value: float64) {
    const elems: FixedDoubleArray = unsafe_cast<FixedDoubleArray>(elements);

    assert(value == Float64SilenceNaN(value));
    StoreFixedDoubleArrayElementWithSmiIndex(elems, index, value);
  }

  // Fast-path for all PACKED_* elements kinds. These do not need to check
  // whether a property is present, so we can simply swap them using fast
  // FixedArray loads/stores.
  macro FastPackedArrayReverse<Accessor : type, T : type>(
      elements: FixedArrayBase, length: Smi) {
    let lower: Smi = 0;
    let upper: Smi = length - 1;

    while (lower < upper) {
      const lower_value: T = LoadElement<Accessor, T>(elements, lower);
      const upper_value: T = LoadElement<Accessor, T>(elements, upper);
      StoreElement<Accessor, T>(elements, lower, upper_value);
      StoreElement<Accessor, T>(elements, upper, lower_value);
      ++lower;
      --upper;
    }
  }

  macro GenericArrayReverse(context: Context, receiver: Object): Object {
    // 1. Let O be ? ToObject(this value).
    const object: JSReceiver = ToObject_Inline(context, receiver);

    // 2. Let len be ? ToLength(? Get(O, "length")).
    const length: Number = GetLengthProperty(context, object);

    // 3. Let middle be floor(len / 2).
    // 4. Let lower be 0.
    // 5. Repeat, while lower != middle.
    //   a. Let upper be len - lower - 1.

    // Instead of calculating the middle value, we simply initialize upper
    // with len - 1 and decrement it after each iteration.
    let lower: Number = 0;
    let upper: Number = length - 1;

    while (lower < upper) {
      let lower_value: Object = Undefined;
      let upper_value: Object = Undefined;

      // b. Let upperP be ! ToString(upper).
      // c. Let lowerP be ! ToString(lower).
      // d. Let lowerExists be ? HasProperty(O, lowerP).
      const lower_exists: Boolean = HasProperty(context, object, lower);

      // e. If lowerExists is true, then.
      if (lower_exists == True) {
        // i. Let lowerValue be ? Get(O, lowerP).
        lower_value = GetProperty(context, object, lower);
      }

      // f. Let upperExists be ? HasProperty(O, upperP).
      const upper_exists: Boolean = HasProperty(context, object, upper);

      // g. If upperExists is true, then.
      if (upper_exists == True) {
        // i. Let upperValue be ? Get(O, upperP).
        upper_value = GetProperty(context, object, upper);
      }

      // h. If lowerExists is true and upperExists is true, then
      if (lower_exists == True && upper_exists == True) {
        // i. Perform ? Set(O, lowerP, upperValue, true).
        SetProperty(context, object, lower, upper_value);

        // ii. Perform ? Set(O, upperP, lowerValue, true).
        SetProperty(context, object, upper, lower_value);
      } else if (lower_exists == False && upper_exists == True) {
        // i. Perform ? Set(O, lowerP, upperValue, true).
        SetProperty(context, object, lower, upper_value);

        // ii. Perform ? DeletePropertyOrThrow(O, upperP).
        DeleteProperty(context, object, upper, kStrict);
      } else if (lower_exists == True && upper_exists == False) {
        // i. Perform ? DeletePropertyOrThrow(O, lowerP).
        DeleteProperty(context, object, lower, kStrict);

        // ii. Perform ? Set(O, upperP, lowerValue, true).
        SetProperty(context, object, upper, lower_value);
      }

      // l. Increase lower by 1.
      ++lower;
      --upper;
    }

    // 6. Return O.
    return object;
  }

  macro EnsureWriteableFastElements(array: JSArray) {
    const elements: FixedArrayBase = array.elements;
    if (elements.map != kCOWMap) return;

    // There are no COW *_DOUBLE_ELEMENTS arrays, so we are allowed to always
    // extract FixedArrays and don't have to worry about FixedDoubleArrays.
    assert(IsFastSmiOrTaggedElementsKind(array.map.elements_kind));

    const length: Smi = array.length_fast;
    array.elements = ExtractFixedArray(
        unsafe_cast<FixedArray>(elements), 0, length, length, kFixedArrays);
  }

  macro TryFastPackedArrayReverse(receiver: Object) labels Slow {
    const array: JSArray = cast<JSArray>(receiver) otherwise Slow;
    EnsureWriteableFastElements(array);
    assert(array.elements.map != kCOWMap);

    const kind: ElementsKind = array.map.elements_kind;
    if (kind == PACKED_SMI_ELEMENTS) {
      FastPackedArrayReverse<FastPackedSmiElements, Smi>(
          array.elements, array.length_fast);
    } else if (kind == PACKED_ELEMENTS) {
      FastPackedArrayReverse<FastPackedObjectElements, Object>(
          array.elements, array.length_fast);
    } else if (kind == PACKED_DOUBLE_ELEMENTS) {
      FastPackedArrayReverse<FastPackedDoubleElements, float64>(
          array.elements, array.length_fast);
    } else {
      goto Slow;
    }
  }

  // https://tc39.github.io/ecma262/#sec-array.prototype.reverse
  javascript builtin ArrayPrototypeReverse(
      context: Context, receiver: Object, ...arguments): Object {
    try {
      TryFastPackedArrayReverse(receiver) otherwise Baseline;
      return receiver;
    }
    label Baseline {
      return GenericArrayReverse(context, receiver);
    }
  }
}