1/*
2 * Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3 * Copyright (C) 2003-2018 Apple Inc. All rights reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18 *
19 */
20
21#pragma once
22
23#include "ArgList.h"
24#include "ArrayConventions.h"
25#include "ButterflyInlines.h"
26#include "JSCellInlines.h"
27#include "JSObject.h"
28
29namespace JSC {
30
31class JSArray;
32class LLIntOffsetsExtractor;
33
34extern const ASCIILiteral LengthExceededTheMaximumArrayLengthError;
35
36class JSArray : public JSNonFinalObject {
37 friend class LLIntOffsetsExtractor;
38 friend class Walker;
39 friend class JIT;
40
41public:
42 typedef JSNonFinalObject Base;
43 static const unsigned StructureFlags = Base::StructureFlags | OverridesGetOwnPropertySlot | OverridesGetPropertyNames;
44
45 static size_t allocationSize(Checked<size_t> inlineCapacity)
46 {
47 ASSERT_UNUSED(inlineCapacity, !inlineCapacity);
48 return sizeof(JSArray);
49 }
50
51protected:
52 explicit JSArray(VM& vm, Structure* structure, Butterfly* butterfly)
53 : JSNonFinalObject(vm, structure, butterfly)
54 {
55 }
56
57public:
58 static JSArray* tryCreate(VM&, Structure*, unsigned initialLength = 0);
59 static JSArray* tryCreate(VM&, Structure*, unsigned initialLength, unsigned vectorLengthHint);
60 static JSArray* create(VM&, Structure*, unsigned initialLength = 0);
61 static JSArray* createWithButterfly(VM&, GCDeferralContext*, Structure*, Butterfly*);
62
63 // tryCreateUninitializedRestricted is used for fast construction of arrays whose size and
64 // contents are known at time of creation. This is a restricted API for careful use only in
65 // performance critical code paths. If you don't have a good reason to use it, you probably
66 // shouldn't use it. Instead, you should go with
67 // - JSArray::tryCreate() or JSArray::create() instead of tryCreateUninitializedRestricted(), and
68 // - putDirectIndex() instead of initializeIndex().
69 //
70 // Clients of this interface must:
71 // - null-check the result (indicating out of memory, or otherwise unable to allocate vector).
72 // - call 'initializeIndex' for all properties in sequence, for 0 <= i < initialLength.
73 // - Provide a valid GCDefferalContext* if they might garbage collect when initializing properties,
74 // otherwise the caller can provide a null GCDefferalContext*.
75 // - Provide a local stack instance of ObjectInitializationScope at the call site.
76 //
77 JS_EXPORT_PRIVATE static JSArray* tryCreateUninitializedRestricted(ObjectInitializationScope&, GCDeferralContext*, Structure*, unsigned initialLength);
78 static JSArray* tryCreateUninitializedRestricted(ObjectInitializationScope& scope, Structure* structure, unsigned initialLength)
79 {
80 return tryCreateUninitializedRestricted(scope, nullptr, structure, initialLength);
81 }
82
83 static void eagerlyInitializeButterfly(ObjectInitializationScope&, JSArray*, unsigned initialLength);
84
85 JS_EXPORT_PRIVATE static bool defineOwnProperty(JSObject*, ExecState*, PropertyName, const PropertyDescriptor&, bool throwException);
86
87 JS_EXPORT_PRIVATE static bool getOwnPropertySlot(JSObject*, ExecState*, PropertyName, PropertySlot&);
88
89 DECLARE_EXPORT_INFO;
90
91 // OK if we know this is a JSArray, but not if it could be an object of a derived class; for RuntimeArray this always returns 0.
92 unsigned length() const { return getArrayLength(); }
93
94 // OK to use on new arrays, but not if it might be a RegExpMatchArray or RuntimeArray.
95 JS_EXPORT_PRIVATE bool setLength(ExecState*, unsigned, bool throwException = false);
96
97 void pushInline(ExecState*, JSValue);
98 JS_EXPORT_PRIVATE void push(ExecState*, JSValue);
99 JS_EXPORT_PRIVATE JSValue pop(ExecState*);
100
101 JSArray* fastSlice(ExecState&, unsigned startIndex, unsigned count);
102
103 bool canFastCopy(VM&, JSArray* otherArray);
104 bool canDoFastIndexedAccess(VM&);
105 // This function returns NonArray if the indexing types are not compatable for copying.
106 IndexingType mergeIndexingTypeForCopying(IndexingType other);
107 bool appendMemcpy(ExecState*, VM&, unsigned startIndex, JSArray* otherArray);
108
109 enum ShiftCountMode {
110 // This form of shift hints that we're doing queueing. With this assumption in hand,
111 // we convert to ArrayStorage, which has queue optimizations.
112 ShiftCountForShift,
113
114 // This form of shift hints that we're just doing care and feeding on an array that
115 // is probably typically used for ordinary accesses. With this assumption in hand,
116 // we try to preserve whatever indexing type it has already.
117 ShiftCountForSplice
118 };
119
120 bool shiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
121 {
122 VM& vm = exec->vm();
123 return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
124 }
125 bool shiftCountForSplice(ExecState* exec, unsigned& startIndex, unsigned count)
126 {
127 return shiftCountWithAnyIndexingType(exec, startIndex, count);
128 }
129 template<ShiftCountMode shiftCountMode>
130 bool shiftCount(ExecState* exec, unsigned& startIndex, unsigned count)
131 {
132 switch (shiftCountMode) {
133 case ShiftCountForShift:
134 return shiftCountForShift(exec, startIndex, count);
135 case ShiftCountForSplice:
136 return shiftCountForSplice(exec, startIndex, count);
137 default:
138 CRASH();
139 return false;
140 }
141 }
142
143 bool unshiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
144 {
145 return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
146 }
147 bool unshiftCountForSplice(ExecState* exec, unsigned startIndex, unsigned count)
148 {
149 return unshiftCountWithAnyIndexingType(exec, startIndex, count);
150 }
151 template<ShiftCountMode shiftCountMode>
152 bool unshiftCount(ExecState* exec, unsigned startIndex, unsigned count)
153 {
154 switch (shiftCountMode) {
155 case ShiftCountForShift:
156 return unshiftCountForShift(exec, startIndex, count);
157 case ShiftCountForSplice:
158 return unshiftCountForSplice(exec, startIndex, count);
159 default:
160 CRASH();
161 return false;
162 }
163 }
164
165 JS_EXPORT_PRIVATE void fillArgList(ExecState*, MarkedArgumentBuffer&);
166 JS_EXPORT_PRIVATE void copyToArguments(ExecState*, VirtualRegister firstElementDest, unsigned offset, unsigned length);
167
168 JS_EXPORT_PRIVATE bool isIteratorProtocolFastAndNonObservable();
169
170 static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype, IndexingType indexingType)
171 {
172 return Structure::create(vm, globalObject, prototype, TypeInfo(ArrayType, StructureFlags), info(), indexingType);
173 }
174
175protected:
176 void finishCreation(VM& vm)
177 {
178 Base::finishCreation(vm);
179 ASSERT(jsDynamicCast<JSArray*>(vm, this));
180 ASSERT_WITH_MESSAGE(type() == ArrayType || type() == DerivedArrayType, "Instance inheriting JSArray should have either ArrayType or DerivedArrayType");
181 }
182
183 static bool put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&);
184
185 static bool deleteProperty(JSCell*, ExecState*, PropertyName);
186 JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
187
188private:
189 bool isLengthWritable()
190 {
191 ArrayStorage* storage = arrayStorageOrNull();
192 if (!storage)
193 return true;
194 SparseArrayValueMap* map = storage->m_sparseMap.get();
195 return !map || !map->lengthIsReadOnly();
196 }
197
198 bool shiftCountWithAnyIndexingType(ExecState*, unsigned& startIndex, unsigned count);
199 JS_EXPORT_PRIVATE bool shiftCountWithArrayStorage(VM&, unsigned startIndex, unsigned count, ArrayStorage*);
200
201 bool unshiftCountWithAnyIndexingType(ExecState*, unsigned startIndex, unsigned count);
202 bool unshiftCountWithArrayStorage(ExecState*, unsigned startIndex, unsigned count, ArrayStorage*);
203 bool unshiftCountSlowCase(const AbstractLocker&, VM&, DeferGC&, bool, unsigned);
204
205 bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*);
206 void setLengthWritable(ExecState*, bool writable);
207};
208
209inline Butterfly* tryCreateArrayButterfly(VM& vm, JSObject* intendedOwner, unsigned initialLength)
210{
211 Butterfly* butterfly = Butterfly::tryCreate(
212 vm, intendedOwner, 0, 0, true, baseIndexingHeaderForArrayStorage(initialLength),
213 ArrayStorage::sizeFor(BASE_ARRAY_STORAGE_VECTOR_LEN));
214 if (!butterfly)
215 return nullptr;
216 ArrayStorage* storage = butterfly->arrayStorage();
217 storage->m_sparseMap.clear();
218 storage->m_indexBias = 0;
219 storage->m_numValuesInVector = 0;
220 return butterfly;
221}
222
223inline JSArray* JSArray::tryCreate(VM& vm, Structure* structure, unsigned initialLength, unsigned vectorLengthHint)
224{
225 ASSERT(vectorLengthHint >= initialLength);
226 unsigned outOfLineStorage = structure->outOfLineCapacity();
227
228 Butterfly* butterfly;
229 IndexingType indexingType = structure->indexingType();
230 if (LIKELY(!hasAnyArrayStorage(indexingType))) {
231 ASSERT(
232 hasUndecided(indexingType)
233 || hasInt32(indexingType)
234 || hasDouble(indexingType)
235 || hasContiguous(indexingType));
236
237 if (UNLIKELY(vectorLengthHint > MAX_STORAGE_VECTOR_LENGTH))
238 return nullptr;
239
240 unsigned vectorLength = Butterfly::optimalContiguousVectorLength(structure, vectorLengthHint);
241 void* temp = vm.jsValueGigacageAuxiliarySpace.allocateNonVirtual(
242 vm,
243 Butterfly::totalSize(0, outOfLineStorage, true, vectorLength * sizeof(EncodedJSValue)),
244 nullptr, AllocationFailureMode::ReturnNull);
245 if (!temp)
246 return nullptr;
247 butterfly = Butterfly::fromBase(temp, 0, outOfLineStorage);
248 butterfly->setVectorLength(vectorLength);
249 butterfly->setPublicLength(initialLength);
250 if (hasDouble(indexingType))
251 clearArray(butterfly->contiguousDouble().data(), vectorLength);
252 else
253 clearArray(butterfly->contiguous().data(), vectorLength);
254 } else {
255 ASSERT(
256 indexingType == ArrayWithSlowPutArrayStorage
257 || indexingType == ArrayWithArrayStorage);
258 butterfly = tryCreateArrayButterfly(vm, nullptr, initialLength);
259 if (!butterfly)
260 return nullptr;
261 for (unsigned i = 0; i < BASE_ARRAY_STORAGE_VECTOR_LEN; ++i)
262 butterfly->arrayStorage()->m_vector[i].clear();
263 }
264
265 return createWithButterfly(vm, nullptr, structure, butterfly);
266}
267
268inline JSArray* JSArray::tryCreate(VM& vm, Structure* structure, unsigned initialLength)
269{
270 return tryCreate(vm, structure, initialLength, initialLength);
271}
272
273inline JSArray* JSArray::create(VM& vm, Structure* structure, unsigned initialLength)
274{
275 JSArray* result = JSArray::tryCreate(vm, structure, initialLength);
276 RELEASE_ASSERT(result);
277
278 return result;
279}
280
281inline JSArray* JSArray::createWithButterfly(VM& vm, GCDeferralContext* deferralContext, Structure* structure, Butterfly* butterfly)
282{
283 JSArray* array = new (NotNull, allocateCell<JSArray>(vm.heap, deferralContext)) JSArray(vm, structure, butterfly);
284 array->finishCreation(vm);
285 return array;
286}
287
288JSArray* asArray(JSValue);
289
290inline JSArray* asArray(JSCell* cell)
291{
292 ASSERT(cell->inherits<JSArray>(*cell->vm()));
293 return jsCast<JSArray*>(cell);
294}
295
296inline JSArray* asArray(JSValue value)
297{
298 return asArray(value.asCell());
299}
300
301inline bool isJSArray(JSCell* cell)
302{
303 ASSERT((cell->classInfo(*cell->vm()) == JSArray::info()) == (cell->type() == ArrayType));
304 return cell->type() == ArrayType;
305}
306
307inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }
308
309JS_EXPORT_PRIVATE JSArray* constructArray(ExecState*, Structure*, const ArgList& values);
310JS_EXPORT_PRIVATE JSArray* constructArray(ExecState*, Structure*, const JSValue* values, unsigned length);
311JS_EXPORT_PRIVATE JSArray* constructArrayNegativeIndexed(ExecState*, Structure*, const JSValue* values, unsigned length);
312
313} // namespace JSC
314