// 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. namespace array { type LoadJoinElementFn = builtin(Context, JSReceiver, uintptr) => JSAny; // Fast C call to write a fixed array (see Buffer.fixedArray) to a single // string. extern macro ArrayBuiltinsAssembler::CallJSArrayArrayJoinConcatToSequentialString( FixedArray, intptr, String, String): String; transitioning builtin LoadJoinElement<T : type extends ElementsKind>( context: Context, receiver: JSReceiver, k: uintptr): JSAny { return GetProperty(receiver, Convert<Number>(k)); } transitioning LoadJoinElement<array::DictionaryElements>( context: Context, receiver: JSReceiver, k: uintptr): JSAny { const array: JSArray = UnsafeCast<JSArray>(receiver); const dict: NumberDictionary = UnsafeCast<NumberDictionary>(array.elements); try { return BasicLoadNumberDictionaryElement(dict, Signed(k)) otherwise IfNoData, IfHole; } label IfNoData deferred { return GetProperty(receiver, Convert<Number>(k)); } label IfHole { return kEmptyString; } } LoadJoinElement<array::FastSmiOrObjectElements>( context: Context, receiver: JSReceiver, k: uintptr): JSAny { const array: JSArray = UnsafeCast<JSArray>(receiver); const fixedArray: FixedArray = UnsafeCast<FixedArray>(array.elements); const element: Object = fixedArray.objects[k]; return element == TheHole ? kEmptyString : UnsafeCast<JSAny>(element); } LoadJoinElement<array::FastDoubleElements>( context: Context, receiver: JSReceiver, k: uintptr): JSAny { const array: JSArray = UnsafeCast<JSArray>(receiver); const fixedDoubleArray: FixedDoubleArray = UnsafeCast<FixedDoubleArray>(array.elements); const element: float64 = fixedDoubleArray.floats[k].Value() otherwise return kEmptyString; return AllocateHeapNumberWithValue(element); } builtin LoadJoinTypedElement<T : type extends ElementsKind>( context: Context, receiver: JSReceiver, k: uintptr): JSAny { const typedArray: JSTypedArray = UnsafeCast<JSTypedArray>(receiver); assert(!IsDetachedBuffer(typedArray.buffer)); return typed_array::LoadFixedTypedArrayElementAsTagged( typedArray.data_ptr, k, typed_array::KindForArrayType<T>()); } transitioning builtin ConvertToLocaleString( context: Context, element: JSAny, locales: JSAny, options: JSAny): String { if (IsNullOrUndefined(element)) return kEmptyString; const prop: JSAny = GetProperty(element, 'toLocaleString'); try { const callable: Callable = Cast<Callable>(prop) otherwise TypeError; let result: JSAny; if (IsNullOrUndefined(locales)) { result = Call(context, callable, element); } else if (IsNullOrUndefined(options)) { result = Call(context, callable, element, locales); } else { result = Call(context, callable, element, locales, options); } return ToString_Inline(result); } label TypeError { ThrowTypeError(MessageTemplate::kCalledNonCallable, prop); } } // Verifies the current element JSArray accessor can still be safely used // (see LoadJoinElement<ElementsAccessor>). macro CannotUseSameArrayAccessor<T: type>(implicit context: Context)( loadFn: LoadJoinElementFn, receiver: JSReceiver, originalMap: Map, originalLen: Number): bool; CannotUseSameArrayAccessor<JSArray>(implicit context: Context)( loadFn: LoadJoinElementFn, receiver: JSReceiver, originalMap: Map, originalLen: Number): bool { if (loadFn == LoadJoinElement<array::GenericElementsAccessor>) return false; const array: JSArray = UnsafeCast<JSArray>(receiver); if (originalMap != array.map) return true; if (originalLen != array.length) return true; if (IsNoElementsProtectorCellInvalid()) return true; return false; } CannotUseSameArrayAccessor<JSTypedArray>(implicit context: Context)( _loadFn: LoadJoinElementFn, receiver: JSReceiver, _initialMap: Map, _initialLen: Number): bool { const typedArray: JSTypedArray = UnsafeCast<JSTypedArray>(receiver); return IsDetachedBuffer(typedArray.buffer); } // Calculates the running total length of the resulting string. If the // calculated length exceeds the maximum string length (see // String::kMaxLength), throws a range error. macro AddStringLength(implicit context: Context)( lenA: intptr, lenB: intptr): intptr { try { const length: intptr = TryIntPtrAdd(lenA, lenB) otherwise IfOverflow; if (length > kStringMaxLength) goto IfOverflow; return length; } label IfOverflow deferred { ThrowInvalidStringLength(context); } } // Stores an element to a fixed array and return the fixed array. If the fixed // array is not large enough, create and return a new, larger fixed array that // contains all previously elements and the new element. macro StoreAndGrowFixedArray<T: type>( fixedArray: FixedArray, index: intptr, element: T): FixedArray { const length: intptr = fixedArray.length_intptr; assert(index <= length); if (index < length) { fixedArray.objects[index] = element; return fixedArray; } else deferred { const newLength: intptr = CalculateNewElementsCapacity(length); assert(index < newLength); const newfixedArray: FixedArray = ExtractFixedArray(fixedArray, 0, length, newLength); newfixedArray.objects[index] = element; return newfixedArray; } } // Contains the information necessary to create a single, separator delimited, // flattened one or two byte string. // The buffer is maintained and updated by Buffer.constructor, Buffer.Add(), // Buffer.AddSeparators(). struct Buffer { macro Add(implicit context: Context)( str: String, nofSeparators: intptr, separatorLength: intptr) { // Add separators if necessary (at the beginning or more than one) const writeSeparators: bool = this.index == 0 | nofSeparators > 1; this.AddSeparators(nofSeparators, separatorLength, writeSeparators); this.totalStringLength = AddStringLength(this.totalStringLength, str.length_intptr); this.fixedArray = StoreAndGrowFixedArray(this.fixedArray, this.index++, str); this.isOneByte = IsOneByteStringInstanceType(str.instanceType) & this.isOneByte; } macro AddSeparators(implicit context: Context)( nofSeparators: intptr, separatorLength: intptr, write: bool) { if (nofSeparators == 0 || separatorLength == 0) return; const nofSeparatorsInt: intptr = nofSeparators; const sepsLen: intptr = separatorLength * nofSeparatorsInt; // Detect integer overflow // TODO(tebbi): Replace with overflow-checked multiplication. if (sepsLen / separatorLength != nofSeparatorsInt) deferred { ThrowInvalidStringLength(context); } this.totalStringLength = AddStringLength(this.totalStringLength, sepsLen); if (write) deferred { this.fixedArray = StoreAndGrowFixedArray( this.fixedArray, this.index++, Convert<Smi>(nofSeparatorsInt)); } } // Fixed array holding elements that are either: // 1) String result of `ToString(next)`. // 2) Smi representing the number of consecutive separators. // `BufferJoin()` will iterate and writes these entries to a flat string. // // To save space, reduce reads and writes, only separators at the beginning, // end, or more than one are written. // // No hole example // receiver: ['hello', 'world'] // fixedArray: ['hello', 'world'] // // Hole example // receiver: [<hole>, 'hello', <hole>, 'world', <hole>] // fixedArray: [1, 'hello', 2, 'world', 1] fixedArray: FixedArray; // Index to insert a new entry into `fixedArray`. index: intptr; // Running total of the resulting string length. totalStringLength: intptr; // `true` if the separator and all strings in the buffer are one-byte, // otherwise `false`. isOneByte: bool; } macro NewBuffer(len: uintptr, sep: String): Buffer { const cappedBufferSize: intptr = len > kMaxNewSpaceFixedArrayElements ? kMaxNewSpaceFixedArrayElements : Signed(len); assert(cappedBufferSize > 0); return Buffer{ fixedArray: AllocateZeroedFixedArray(cappedBufferSize), index: 0, totalStringLength: 0, isOneByte: IsOneByteStringInstanceType(sep.instanceType) }; } macro BufferJoin(implicit context: Context)( buffer: Buffer, sep: String): String { assert(IsValidPositiveSmi(buffer.totalStringLength)); if (buffer.totalStringLength == 0) return kEmptyString; // Fast path when there's only one buffer element. if (buffer.index == 1) { const fixedArray: FixedArray = buffer.fixedArray; typeswitch (fixedArray.objects[0]) { // When the element is a string, just return it and completely avoid // allocating another string. case (str: String): { return str; } // When the element is a smi, use StringRepeat to quickly build a memory // efficient separator repeated string. case (nofSeparators: Number): { return StringRepeat(context, sep, nofSeparators); } case (Object): { unreachable; } } } const length: uint32 = Convert<uint32>(Unsigned(buffer.totalStringLength)); const r: String = buffer.isOneByte ? AllocateSeqOneByteString(length) : AllocateSeqTwoByteString(length); return CallJSArrayArrayJoinConcatToSequentialString( buffer.fixedArray, buffer.index, sep, r); } transitioning macro ArrayJoinImpl<T: type>(implicit context: Context)( receiver: JSReceiver, sep: String, lengthNumber: Number, useToLocaleString: constexpr bool, locales: JSAny, options: JSAny, initialLoadFn: LoadJoinElementFn): String { const initialMap: Map = receiver.map; const len: uintptr = Convert<uintptr>(lengthNumber); const separatorLength: intptr = sep.length_intptr; let nofSeparators: intptr = 0; let loadFn: LoadJoinElementFn = initialLoadFn; let buffer: Buffer = NewBuffer(len, sep); // 6. Let k be 0. let k: uintptr = 0; // 7. Repeat, while k < len while (k < len) { if (CannotUseSameArrayAccessor<T>( loadFn, receiver, initialMap, lengthNumber)) deferred { loadFn = LoadJoinElement<array::GenericElementsAccessor>; } if (k > 0) { // a. If k > 0, let R be the string-concatenation of R and sep. nofSeparators = nofSeparators + 1; } // b. Let element be ? Get(O, ! ToString(k)). const element: JSAny = loadFn(context, receiver, k++); // c. If element is undefined or null, let next be the empty String; // otherwise, let next be ? ToString(element). let next: String; if constexpr (useToLocaleString) { next = ConvertToLocaleString(context, element, locales, options); if (next == kEmptyString) continue; } else { typeswitch (element) { case (str: String): { if (str == kEmptyString) continue; next = str; } case (num: Number): { next = NumberToString(num); } case (obj: JSAny): { if (IsNullOrUndefined(obj)) continue; next = string::ToString(context, obj); } } } // d. Set R to the string-concatenation of R and next. buffer.Add(next, nofSeparators, separatorLength); nofSeparators = 0; } // Add any separators at the end. buffer.AddSeparators(nofSeparators, separatorLength, true); // 8. Return R. return BufferJoin(buffer, sep); } transitioning macro ArrayJoin<T: type>(implicit context: Context)( useToLocaleString: constexpr bool, receiver: JSReceiver, sep: String, lenNumber: Number, locales: JSAny, options: JSAny): JSAny; transitioning ArrayJoin<JSArray>(implicit context: Context)( useToLocaleString: constexpr bool, receiver: JSReceiver, sep: String, lenNumber: Number, locales: JSAny, options: JSAny): JSAny { const map: Map = receiver.map; const kind: ElementsKind = map.elements_kind; let loadFn: LoadJoinElementFn; try { const array: JSArray = Cast<JSArray>(receiver) otherwise IfSlowPath; if (array.length != lenNumber) goto IfSlowPath; if (!IsPrototypeInitialArrayPrototype(map)) goto IfSlowPath; if (IsNoElementsProtectorCellInvalid()) goto IfSlowPath; if (IsElementsKindLessThanOrEqual(kind, ElementsKind::HOLEY_ELEMENTS)) { loadFn = LoadJoinElement<array::FastSmiOrObjectElements>; } else if (IsElementsKindLessThanOrEqual( kind, ElementsKind::HOLEY_DOUBLE_ELEMENTS)) { loadFn = LoadJoinElement<array::FastDoubleElements>; } else if (kind == ElementsKind::DICTIONARY_ELEMENTS) deferred { const dict: NumberDictionary = UnsafeCast<NumberDictionary>(array.elements); const nofElements: Smi = GetNumberDictionaryNumberOfElements(dict); if (nofElements == 0) { if (sep == kEmptyString) return kEmptyString; try { const nofSeparators: Smi = Cast<Smi>(lenNumber - 1) otherwise IfNotSmi; return StringRepeat(context, sep, nofSeparators); } label IfNotSmi { ThrowInvalidStringLength(context); } } else { loadFn = LoadJoinElement<array::DictionaryElements>; } } else { goto IfSlowPath; } } label IfSlowPath { loadFn = LoadJoinElement<array::GenericElementsAccessor>; } return ArrayJoinImpl<JSArray>( receiver, sep, lenNumber, useToLocaleString, locales, options, loadFn); } transitioning ArrayJoin<JSTypedArray>(implicit context: Context)( useToLocaleString: constexpr bool, receiver: JSReceiver, sep: String, lenNumber: Number, locales: JSAny, options: JSAny): JSAny { const map: Map = receiver.map; const kind: ElementsKind = map.elements_kind; let loadFn: LoadJoinElementFn; if (IsElementsKindGreaterThan(kind, ElementsKind::UINT32_ELEMENTS)) { if (kind == ElementsKind::INT32_ELEMENTS) { loadFn = LoadJoinTypedElement<typed_array::Int32Elements>; } else if (kind == ElementsKind::FLOAT32_ELEMENTS) { loadFn = LoadJoinTypedElement<typed_array::Float32Elements>; } else if (kind == ElementsKind::FLOAT64_ELEMENTS) { loadFn = LoadJoinTypedElement<typed_array::Float64Elements>; } else if (kind == ElementsKind::UINT8_CLAMPED_ELEMENTS) { loadFn = LoadJoinTypedElement<typed_array::Uint8ClampedElements>; } else if (kind == ElementsKind::BIGUINT64_ELEMENTS) { loadFn = LoadJoinTypedElement<typed_array::BigUint64Elements>; } else if (kind == ElementsKind::BIGINT64_ELEMENTS) { loadFn = LoadJoinTypedElement<typed_array::BigInt64Elements>; } else { unreachable; } } else { if (kind == ElementsKind::UINT8_ELEMENTS) { loadFn = LoadJoinTypedElement<typed_array::Uint8Elements>; } else if (kind == ElementsKind::INT8_ELEMENTS) { loadFn = LoadJoinTypedElement<typed_array::Int8Elements>; } else if (kind == ElementsKind::UINT16_ELEMENTS) { loadFn = LoadJoinTypedElement<typed_array::Uint16Elements>; } else if (kind == ElementsKind::INT16_ELEMENTS) { loadFn = LoadJoinTypedElement<typed_array::Int16Elements>; } else if (kind == ElementsKind::UINT32_ELEMENTS) { loadFn = LoadJoinTypedElement<typed_array::Uint32Elements>; } else { unreachable; } } return ArrayJoinImpl<JSTypedArray>( receiver, sep, lenNumber, useToLocaleString, locales, options, loadFn); } // The Join Stack detects cyclical calls to Array Join builtins // (Array.p.join(), Array.p.toString(), Array.p.toLocaleString()). This // FixedArray holds a stack of receivers to the current call. // CycleProtectedArrayJoin() is responsible for calling JoinStackPush and // JoinStackPop when visiting and leaving a receiver, respectively. const kMinJoinStackSize: constexpr int31 generates 'JSArray::kMinJoinStackSize'; macro LoadJoinStack(implicit context: Context)(): FixedArray labels IfUninitialized { typeswitch (*NativeContextSlot(ContextSlot::ARRAY_JOIN_STACK_INDEX)) { case (Undefined): { goto IfUninitialized; } case (stack: FixedArray): { return stack; } } } macro SetJoinStack(implicit context: Context)(stack: FixedArray): void { *NativeContextSlot(ContextSlot::ARRAY_JOIN_STACK_INDEX) = stack; } // Adds a receiver to the stack. The FixedArray will automatically grow to // accommodate the receiver. If the receiver already exists on the stack, // this indicates a cyclical call and False is returned. builtin JoinStackPush(implicit context: Context)( stack: FixedArray, receiver: JSReceiver): Boolean { const capacity: intptr = stack.length_intptr; for (let i: intptr = 0; i < capacity; i++) { const previouslyVisited: Object = stack.objects[i]; // Add `receiver` to the first open slot if (previouslyVisited == TheHole) { stack.objects[i] = receiver; return True; } // Detect cycles if (receiver == previouslyVisited) return False; } // If no open slots were found, grow the stack and add receiver to the end. const newStack: FixedArray = StoreAndGrowFixedArray(stack, capacity, receiver); SetJoinStack(newStack); return True; } // Fast path the common non-nested calls. If the receiver is not already on // the stack, add it to the stack and return true. Otherwise return false. macro JoinStackPushInline(implicit context: Context)(receiver: JSReceiver): bool { try { const stack: FixedArray = LoadJoinStack() otherwise IfUninitialized; if (stack.objects[0] == TheHole) { stack.objects[0] = receiver; } else if (JoinStackPush(stack, receiver) == False) deferred { return false; } } label IfUninitialized { const stack: FixedArray = AllocateFixedArrayWithHoles(kMinJoinStackSize, AllocationFlag::kNone); stack.objects[0] = receiver; SetJoinStack(stack); } return true; } // Removes a receiver from the stack. The FixedArray will automatically shrink // to Heap::kMinJoinStackSize once the stack becomes empty. builtin JoinStackPop(implicit context: Context)( stack: FixedArray, receiver: JSReceiver): JSAny { const len: intptr = stack.length_intptr; for (let i: intptr = 0; i < len; i++) { if (stack.objects[i] == receiver) { // Shrink the Join Stack if the stack will be empty and is larger than // the minimum size. if (i == 0 && len > kMinJoinStackSize) deferred { const newStack: FixedArray = AllocateFixedArrayWithHoles( kMinJoinStackSize, AllocationFlag::kNone); SetJoinStack(newStack); } else { stack.objects[i] = TheHole; } return Undefined; } } unreachable; } // Fast path the common non-nested calls. macro JoinStackPopInline(implicit context: Context)(receiver: JSReceiver) { const stack: FixedArray = LoadJoinStack() otherwise unreachable; const len: intptr = stack.length_intptr; // Builtin call was not nested (receiver is the first entry) and // did not contain other nested arrays that expanded the stack. if (stack.objects[0] == receiver && len == kMinJoinStackSize) { StoreFixedArrayElement(stack, 0, TheHole, SKIP_WRITE_BARRIER); } else deferred { JoinStackPop(stack, receiver); } } // Main entry point for all builtins using Array Join functionality. transitioning macro CycleProtectedArrayJoin<T: type>( implicit context: Context)( useToLocaleString: constexpr bool, o: JSReceiver, len: Number, sepObj: JSAny, locales: JSAny, options: JSAny): JSAny { // 3. If separator is undefined, let sep be the single-element String ",". // 4. Else, let sep be ? ToString(separator). const sep: String = sepObj == Undefined ? ',' : ToString_Inline(sepObj); // If the receiver is not empty and not already being joined, continue with // the normal join algorithm. if (len > 0 && JoinStackPushInline(o)) { try { const result: JSAny = ArrayJoin<T>(useToLocaleString, o, sep, len, locales, options); JoinStackPopInline(o); return result; } catch (e) deferred { JoinStackPopInline(o); ReThrow(context, e); } } else { return kEmptyString; } } // https://tc39.github.io/ecma262/#sec-array.prototype.join transitioning javascript builtin ArrayPrototypeJoin( js-implicit context: NativeContext, receiver: JSAny)(...arguments): JSAny { const separator: JSAny = arguments[0]; // 1. Let O be ? ToObject(this value). const o: JSReceiver = ToObject_Inline(context, receiver); // 2. Let len be ? ToLength(? Get(O, "length")). const len: Number = GetLengthProperty(o); // Only handle valid array lengths. Although the spec allows larger // values, this matches historical V8 behavior. if (len > kMaxArrayIndex + 1) ThrowTypeError(MessageTemplate::kInvalidArrayLength); return CycleProtectedArrayJoin<JSArray>( false, o, len, separator, Undefined, Undefined); } // https://tc39.github.io/ecma262/#sec-array.prototype.tolocalestring transitioning javascript builtin ArrayPrototypeToLocaleString( js-implicit context: NativeContext, receiver: JSAny)(...arguments): JSAny { const locales: JSAny = arguments[0]; const options: JSAny = arguments[1]; // 1. Let O be ? ToObject(this value). const o: JSReceiver = ToObject_Inline(context, receiver); // 2. Let len be ? ToLength(? Get(O, "length")). const len: Number = GetLengthProperty(o); // Only handle valid array lengths. Although the spec allows larger // values, this matches historical V8 behavior. if (len > kMaxArrayIndex + 1) ThrowTypeError(MessageTemplate::kInvalidArrayLength); return CycleProtectedArrayJoin<JSArray>(true, o, len, ',', locales, options); } // https://tc39.github.io/ecma262/#sec-array.prototype.tostring transitioning javascript builtin ArrayPrototypeToString( js-implicit context: NativeContext, receiver: JSAny)(...arguments): JSAny { // 1. Let array be ? ToObject(this value). const array: JSReceiver = ToObject_Inline(context, receiver); // 2. Let func be ? Get(array, "join"). const prop: JSAny = GetProperty(array, 'join'); try { // 3. If IsCallable(func) is false, let func be the intrinsic function // %ObjProto_toString%. const func: Callable = Cast<Callable>(prop) otherwise NotCallable; // 4. Return ? Call(func, array). return Call(context, func, array); } label NotCallable { return ObjectToString(context, array); } } // https://tc39.github.io/ecma262/#sec-%typedarray%.prototype.join transitioning javascript builtin TypedArrayPrototypeJoin( js-implicit context: NativeContext, receiver: JSAny)(...arguments): JSAny { const separator: JSAny = arguments[0]; // Spec: ValidateTypedArray is applied to the this value prior to evaluating // the algorithm. const typedArray: JSTypedArray = typed_array::ValidateTypedArray( context, receiver, '%TypedArray%.prototype.join'); const length = Convert<Number>(typedArray.length); return CycleProtectedArrayJoin<JSTypedArray>( false, typedArray, length, separator, Undefined, Undefined); } // https://tc39.github.io/ecma262/#sec-%typedarray%.prototype.tolocalestring transitioning javascript builtin TypedArrayPrototypeToLocaleString( js-implicit context: NativeContext, receiver: JSAny)(...arguments): JSAny { const locales: JSAny = arguments[0]; const options: JSAny = arguments[1]; // Spec: ValidateTypedArray is applied to the this value prior to evaluating // the algorithm. const typedArray: JSTypedArray = typed_array::ValidateTypedArray( context, receiver, '%TypedArray%.prototype.toLocaleString'); const length = Convert<Number>(typedArray.length); return CycleProtectedArrayJoin<JSTypedArray>( true, typedArray, length, ',', locales, options); } }