src/builtins/object-groupby.tq

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

namespace collections {

extern macro CollectionsBuiltinsAssembler::AddValueToKeyedGroup(
    OrderedHashMap, Object, Object, String): OrderedHashMap;

extern macro CollectionsBuiltinsAssembler::NormalizeNumberKey(JSAny): JSAny;

}  // namespace collections

// https://tc39.es/proposal-array-grouping/#sec-group-by
transitioning macro CoerceGroupKey(
    implicit context: Context)(key: JSAny, coerceToProperty: Boolean): JSAny {
  // 6.g. If coercion is property, then
  if (coerceToProperty == True) {
    // i. Set key to Completion(ToPropertyKey(key)).
    return ToName(key);
  }
  // 6.h. Else,
  //    i. Assert: coercion is zero.
  //   ii. If key is -0𝔽, set key to +0𝔽.
  return collections::NormalizeNumberKey(key);
}

// https://tc39.es/proposal-array-grouping/#sec-group-by
transitioning builtin GroupByGeneric(
    implicit context: Context)(items: JSAny, initialGroups: OrderedHashMap,
    callbackfn: Callable, coerceToProperty: Boolean,
    methodName: String): OrderedHashMap {
  let groups = initialGroups;

  // 4. Let iteratorRecord be ? GetIterator(items, sync).
  const fastIteratorResultMap = GetIteratorResultMap();
  const iteratorRecord = iterator::GetIterator(items);

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

  // 6. Repeat,
  while (true) {
    // a. If k ≥ 2^53 - 1, then
    //   i. Let error be ThrowCompletion(a newly created TypeError object).
    //   ii. Return ? IteratorClose(iteratorRecord, error).
    //
    // The spec requires that we throw an exception if index reaches 2^53-1,
    // but an empty loop would take >100 days to do this many iterations. To
    // actually run for that long would require an iterator that never set
    // done to true and a target array which somehow never ran out of
    // memory, e.g. a proxy that discarded the values. Ignoring this case
    // just means we would call the callback with 2^53.
    dcheck(k < kMaxSafeInteger);

    // b. Let next be ? IteratorStep(iteratorRecord).
    let next: JSReceiver;
    try {
      next = iterator::IteratorStep(iteratorRecord, fastIteratorResultMap)
          otherwise NextIsFalse;
    }
    // c. If next is false, then
    label NextIsFalse {
      // i. Return groups.
      return groups;
    }

    // d. Let value be ? IteratorValue(next).
    const value = iterator::IteratorValue(next, fastIteratorResultMap);

    // e. Let key be Completion(Call(callbackfn, undefined, « value, 𝔽(k) »)).
    let key: JSAny;
    try {
      key = Call(context, callbackfn, Undefined, value, k);
      key = CoerceGroupKey(key, coerceToProperty);
    } catch (e, message) {
      // f. and g.ii.
      // IfAbruptCloseIterator(key, iteratorRecord).
      iterator::IteratorCloseOnException(iteratorRecord);
      ReThrowWithMessage(context, e, message);
    }

    // i. Perform AddValueToKeyedGroup(groups, key, value).
    groups = collections::AddValueToKeyedGroup(groups, key, value, methodName);

    // j. Set k to k + 1.
    k += 1;
  }

  unreachable;
}

// https://tc39.es/proposal-array-grouping/#sec-group-by
transitioning macro GroupByImpl(
    implicit context: Context)(items: JSAny, callback: JSAny,
    coerceToProperty: Boolean, methodName: constexpr string): OrderedHashMap {
  // 1. Perform ? RequireObjectCoercible(items).
  RequireObjectCoercible(items, methodName);

  // 2. If IsCallable(callbackfn) is false, throw a TypeError exception.
  const callbackfn = Cast<Callable>(callback)
      otherwise ThrowTypeError(MessageTemplate::kCalledNonCallable, callback);

  // 3. Let groups be a new empty List.
  let groups = AllocateOrderedHashMap();

  try {
    typeswitch (items) {
      case (array: FastJSArrayForReadWithNoCustomIteration): {
        // Per spec, the iterator and its next method are cached up front. This
        // means that we only need to check for no custom iteration once up
        // front. Even though the grouping callback has arbitrary side effects,
        // mutations to %ArrayIteratorPrototype% will not be reflected during
        // the iteration itself. Therefore we don't need a "no custom iteration"
        // witness.
        let fastArrayWitness = NewFastJSArrayForReadWitness(array);
        const stableArray = fastArrayWitness.stable;
        let k: Smi = 0;

        try {
          while (k < stableArray.length) {
            fastArrayWitness.Recheck() otherwise goto SlowArrayContinuation;
            let value: JSAny;
            try {
              value =
                  fastArrayWitness.LoadElementNoHole(k) otherwise IsUndefined;
            } label IsUndefined {
              value = Undefined;
            }
            const key = CoerceGroupKey(
                Call(context, callbackfn, Undefined, value, k),
                coerceToProperty);
            groups = collections::AddValueToKeyedGroup(
                groups, key, value, methodName);
            ++k;
          }
        } label SlowArrayContinuation deferred {
          // The grouping callback can mutate the array such that it is no
          // longer fast, but it is still a JSArray. Since the spec caches the
          // iterator up front, a fully generic fallback is not needed. Instead
          // we encode the array iterator logic here directly for the rest of
          // the loop.
          while (k < stableArray.length) {
            const value = GetProperty(stableArray, k);
            const key = CoerceGroupKey(
                Call(context, callbackfn, Undefined, value, k),
                coerceToProperty);
            groups = collections::AddValueToKeyedGroup(
                groups, key, value, methodName);
            ++k;
          }
        }

        return groups;
      }
      case (JSAny): {
        goto SlowGeneric;
      }
    }
  } label SlowGeneric {
    return GroupByGeneric(
        items, groups, callbackfn, coerceToProperty, methodName);
  }
}

@incrementUseCounter('v8::Isolate::kArrayGroup')
transitioning javascript builtin ObjectGroupBy(
    js-implicit context: NativeContext, receiver: JSAny)(items: JSAny,
    callback: JSAny): JSAny {
  // 1. Let groups be ? GroupBy(items, callbackfn, property).
  const groups: OrderedHashMap = GroupByImpl(
      items, callback, /* coerceToProperty */ True, 'Object.groupBy');

  let iter = collections::NewUnmodifiedOrderedHashMapIterator(groups);

  // 2. Let obj be OrdinaryObjectCreate(null).
  // 3. For each Record { [[Key]], [[Elements]] } g of groups, do
  //   a. Let elements be CreateArrayFromList(g.[[Elements]]).
  //   b. Perform ! CreateDataPropertyOrThrow(obj, g.[[Key]], elements).
  let properties: NameDictionary|SwissNameDictionary;

  @if(V8_ENABLE_SWISS_NAME_DICTIONARY) {
    properties =
        AllocateSwissNameDictionary(Convert<intptr>(iter.usedCapacity));
  }
  @ifnot(V8_ENABLE_SWISS_NAME_DICTIONARY) {
    properties = AllocateNameDictionary(Convert<intptr>(iter.usedCapacity));
  }
  const nullProtoMap = LoadSlowObjectWithNullPrototypeMap(context);
  const obj = AllocateJSObjectFromMap(nullProtoMap, properties);

  // TODO(v8:12499): Determine more specific elements map if worth it.
  try {
    const arrayMap = GetFastPackedElementsJSArrayMap();
    while (true) {
      const entry = iter.Next() otherwise Done;
      const elements = ArrayListElements(UnsafeCast<ArrayList>(entry.value));
      const array = NewJSArray(arrayMap, elements);
      CreateDataProperty(obj, entry.key, array);
    }
  } label Done {}

  // 4. Return obj.
  return obj;
}