1/*
2 * Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3 * Copyright (C) 2003, 2007, 2008, 2009, 2012, 2015 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#ifndef JSArray_h
22#define JSArray_h
23
24#include "ArrayConventions.h"
25#include "ButterflyInlines.h"
26#include "JSObject.h"
27
28namespace JSC {
29
30class JSArray;
31class LLIntOffsetsExtractor;
32
33class JSArray : public JSNonFinalObject {
34 friend class LLIntOffsetsExtractor;
35 friend class Walker;
36 friend class JIT;
37
38public:
39 typedef JSNonFinalObject Base;
40 static const unsigned StructureFlags = Base::StructureFlags | OverridesGetOwnPropertySlot | OverridesGetPropertyNames;
41
42 static size_t allocationSize(size_t inlineCapacity)
43 {
44 ASSERT_UNUSED(inlineCapacity, !inlineCapacity);
45 return sizeof(JSArray);
46 }
47
48protected:
49 explicit JSArray(VM& vm, Structure* structure, Butterfly* butterfly)
50 : JSNonFinalObject(vm, structure, butterfly)
51 {
52 }
53
54public:
55 static JSArray* create(VM&, Structure*, unsigned initialLength = 0);
56 static JSArray* createWithButterfly(VM&, Structure*, Butterfly*);
57
58 // tryCreateUninitialized is used for fast construction of arrays whose size and
59 // contents are known at time of creation. Clients of this interface must:
60 // - null-check the result (indicating out of memory, or otherwise unable to allocate vector).
61 // - call 'initializeIndex' for all properties in sequence, for 0 <= i < initialLength.
62 static JSArray* tryCreateUninitialized(VM&, Structure*, unsigned initialLength);
63
64 JS_EXPORT_PRIVATE static bool defineOwnProperty(JSObject*, ExecState*, PropertyName, const PropertyDescriptor&, bool throwException);
65
66 JS_EXPORT_PRIVATE static bool getOwnPropertySlot(JSObject*, ExecState*, PropertyName, PropertySlot&);
67
68 DECLARE_EXPORT_INFO;
69
70 // 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.
71 unsigned length() const { return getArrayLength(); }
72
73 // OK to use on new arrays, but not if it might be a RegExpMatchArray or RuntimeArray.
74 JS_EXPORT_PRIVATE bool setLength(ExecState*, unsigned, bool throwException = false);
75
76 JS_EXPORT_PRIVATE void push(ExecState*, JSValue);
77 JS_EXPORT_PRIVATE JSValue pop(ExecState*);
78
79 JSArray* fastSlice(ExecState&, unsigned startIndex, unsigned count);
80
81 static IndexingType fastConcatType(VM& vm, JSArray& firstArray, JSArray& secondArray)
82 {
83 IndexingType type = firstArray.indexingType();
84 if (type != secondArray.indexingType())
85 return NonArray;
86 if (type != ArrayWithDouble && type != ArrayWithInt32 && type != ArrayWithContiguous)
87 return NonArray;
88 if (firstArray.structure(vm)->holesMustForwardToPrototype(vm)
89 || secondArray.structure(vm)->holesMustForwardToPrototype(vm))
90 return NonArray;
91 return type;
92 }
93 EncodedJSValue fastConcatWith(ExecState&, JSArray&);
94
95 enum ShiftCountMode {
96 // This form of shift hints that we're doing queueing. With this assumption in hand,
97 // we convert to ArrayStorage, which has queue optimizations.
98 ShiftCountForShift,
99
100 // This form of shift hints that we're just doing care and feeding on an array that
101 // is probably typically used for ordinary accesses. With this assumption in hand,
102 // we try to preserve whatever indexing type it has already.
103 ShiftCountForSplice
104 };
105
106 bool shiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
107 {
108 return shiftCountWithArrayStorage(exec->vm(), startIndex, count, ensureArrayStorage(exec->vm()));
109 }
110 bool shiftCountForSplice(ExecState* exec, unsigned& startIndex, unsigned count)
111 {
112 return shiftCountWithAnyIndexingType(exec, startIndex, count);
113 }
114 template<ShiftCountMode shiftCountMode>
115 bool shiftCount(ExecState* exec, unsigned& startIndex, unsigned count)
116 {
117 switch (shiftCountMode) {
118 case ShiftCountForShift:
119 return shiftCountForShift(exec, startIndex, count);
120 case ShiftCountForSplice:
121 return shiftCountForSplice(exec, startIndex, count);
122 default:
123 CRASH();
124 return false;
125 }
126 }
127
128 bool unshiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
129 {
130 return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
131 }
132 bool unshiftCountForSplice(ExecState* exec, unsigned startIndex, unsigned count)
133 {
134 return unshiftCountWithAnyIndexingType(exec, startIndex, count);
135 }
136 template<ShiftCountMode shiftCountMode>
137 bool unshiftCount(ExecState* exec, unsigned startIndex, unsigned count)
138 {
139 switch (shiftCountMode) {
140 case ShiftCountForShift:
141 return unshiftCountForShift(exec, startIndex, count);
142 case ShiftCountForSplice:
143 return unshiftCountForSplice(exec, startIndex, count);
144 default:
145 CRASH();
146 return false;
147 }
148 }
149
150 JS_EXPORT_PRIVATE void fillArgList(ExecState*, MarkedArgumentBuffer&);
151 JS_EXPORT_PRIVATE void copyToArguments(ExecState*, VirtualRegister firstElementDest, unsigned offset, unsigned length);
152
153 static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype, IndexingType indexingType)
154 {
155 return Structure::create(vm, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), info(), indexingType);
156 }
157
158protected:
159 static void put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&);
160
161 static bool deleteProperty(JSCell*, ExecState*, PropertyName);
162 JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
163
164private:
165 bool isLengthWritable()
166 {
167 ArrayStorage* storage = arrayStorageOrNull();
168 if (!storage)
169 return true;
170 SparseArrayValueMap* map = storage->m_sparseMap.get();
171 return !map || !map->lengthIsReadOnly();
172 }
173
174 bool shiftCountWithAnyIndexingType(ExecState*, unsigned& startIndex, unsigned count);
175 JS_EXPORT_PRIVATE bool shiftCountWithArrayStorage(VM&, unsigned startIndex, unsigned count, ArrayStorage*);
176
177 bool unshiftCountWithAnyIndexingType(ExecState*, unsigned startIndex, unsigned count);
178 bool unshiftCountWithArrayStorage(ExecState*, unsigned startIndex, unsigned count, ArrayStorage*);
179 bool unshiftCountSlowCase(VM&, bool, unsigned);
180
181 bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*);
182 void setLengthWritable(ExecState*, bool writable);
183};
184
185inline Butterfly* createContiguousArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned length, unsigned& vectorLength)
186{
187 IndexingHeader header;
188 vectorLength = std::max(length, BASE_VECTOR_LEN);
189 header.setVectorLength(vectorLength);
190 header.setPublicLength(length);
191 Butterfly* result = Butterfly::create(
192 vm, intendedOwner, 0, 0, true, header, vectorLength * sizeof(EncodedJSValue));
193 return result;
194}
195
196inline Butterfly* createArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned initialLength)
197{
198 Butterfly* butterfly = Butterfly::create(
199 vm, intendedOwner, 0, 0, true, baseIndexingHeaderForArray(initialLength),
200 ArrayStorage::sizeFor(BASE_VECTOR_LEN));
201 ArrayStorage* storage = butterfly->arrayStorage();
202 storage->m_indexBias = 0;
203 storage->m_sparseMap.clear();
204 storage->m_numValuesInVector = 0;
205 return butterfly;
206}
207
208Butterfly* createArrayButterflyInDictionaryIndexingMode(
209 VM&, JSCell* intendedOwner, unsigned initialLength);
210
211inline JSArray* JSArray::create(VM& vm, Structure* structure, unsigned initialLength)
212{
213 Butterfly* butterfly;
214 if (LIKELY(!hasAnyArrayStorage(structure->indexingType()))) {
215 ASSERT(
216 hasUndecided(structure->indexingType())
217 || hasInt32(structure->indexingType())
218 || hasDouble(structure->indexingType())
219 || hasContiguous(structure->indexingType()));
220 unsigned vectorLength;
221 butterfly = createContiguousArrayButterfly(vm, 0, initialLength, vectorLength);
222 ASSERT(initialLength < MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH);
223 if (hasDouble(structure->indexingType())) {
224 for (unsigned i = 0; i < vectorLength; ++i)
225 butterfly->contiguousDouble()[i] = PNaN;
226 }
227 } else {
228 ASSERT(
229 structure->indexingType() == ArrayWithSlowPutArrayStorage
230 || structure->indexingType() == ArrayWithArrayStorage);
231 butterfly = createArrayButterfly(vm, 0, initialLength);
232 }
233
234 return createWithButterfly(vm, structure, butterfly);
235}
236
237inline JSArray* JSArray::tryCreateUninitialized(VM& vm, Structure* structure, unsigned initialLength)
238{
239 unsigned vectorLength = std::max(BASE_VECTOR_LEN, initialLength);
240 if (vectorLength > MAX_STORAGE_VECTOR_LENGTH)
241 return 0;
242
243 unsigned outOfLineStorage = structure->outOfLineCapacity();
244
245 Butterfly* butterfly;
246 if (LIKELY(!hasAnyArrayStorage(structure->indexingType()))) {
247 ASSERT(
248 hasUndecided(structure->indexingType())
249 || hasInt32(structure->indexingType())
250 || hasDouble(structure->indexingType())
251 || hasContiguous(structure->indexingType()));
252
253 void* temp;
254 if (!vm.heap.tryAllocateStorage(0, Butterfly::totalSize(0, outOfLineStorage, true, vectorLength * sizeof(EncodedJSValue)), &temp))
255 return 0;
256 butterfly = Butterfly::fromBase(temp, 0, outOfLineStorage);
257 butterfly->setVectorLength(vectorLength);
258 butterfly->setPublicLength(initialLength);
259 if (hasDouble(structure->indexingType())) {
260 for (unsigned i = initialLength; i < vectorLength; ++i)
261 butterfly->contiguousDouble()[i] = PNaN;
262 }
263 } else {
264 void* temp;
265 if (!vm.heap.tryAllocateStorage(0, Butterfly::totalSize(0, outOfLineStorage, true, ArrayStorage::sizeFor(vectorLength)), &temp))
266 return 0;
267 butterfly = Butterfly::fromBase(temp, 0, outOfLineStorage);
268 *butterfly->indexingHeader() = indexingHeaderForArray(initialLength, vectorLength);
269 ArrayStorage* storage = butterfly->arrayStorage();
270 storage->m_indexBias = 0;
271 storage->m_sparseMap.clear();
272 storage->m_numValuesInVector = initialLength;
273 }
274
275 return createWithButterfly(vm, structure, butterfly);
276}
277
278inline JSArray* JSArray::createWithButterfly(VM& vm, Structure* structure, Butterfly* butterfly)
279{
280 JSArray* array = new (NotNull, allocateCell<JSArray>(vm.heap)) JSArray(vm, structure, butterfly);
281 array->finishCreation(vm);
282 return array;
283}
284
285JSArray* asArray(JSValue);
286
287inline JSArray* asArray(JSCell* cell)
288{
289 ASSERT(cell->inherits(JSArray::info()));
290 return jsCast<JSArray*>(cell);
291}
292
293inline JSArray* asArray(JSValue value)
294{
295 return asArray(value.asCell());
296}
297
298inline bool isJSArray(JSCell* cell) { return cell->classInfo() == JSArray::info(); }
299inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }
300
301inline JSArray* constructArray(ExecState* exec, Structure* arrayStructure, const ArgList& values)
302{
303 VM& vm = exec->vm();
304 unsigned length = values.size();
305 JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length);
306
307 // FIXME: we should probably throw an out of memory error here, but
308 // when making this change we should check that all clients of this
309 // function will correctly handle an exception being thrown from here.
310 RELEASE_ASSERT(array);
311
312 for (unsigned i = 0; i < length; ++i)
313 array->initializeIndex(vm, i, values.at(i));
314 return array;
315}
316
317inline JSArray* constructArray(ExecState* exec, Structure* arrayStructure, const JSValue* values, unsigned length)
318{
319 VM& vm = exec->vm();
320 JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length);
321
322 // FIXME: we should probably throw an out of memory error here, but
323 // when making this change we should check that all clients of this
324 // function will correctly handle an exception being thrown from here.
325 RELEASE_ASSERT(array);
326
327 for (unsigned i = 0; i < length; ++i)
328 array->initializeIndex(vm, i, values[i]);
329 return array;
330}
331
332inline JSArray* constructArrayNegativeIndexed(ExecState* exec, Structure* arrayStructure, const JSValue* values, unsigned length)
333{
334 VM& vm = exec->vm();
335 JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length);
336
337 // FIXME: we should probably throw an out of memory error here, but
338 // when making this change we should check that all clients of this
339 // function will correctly handle an exception being thrown from here.
340 RELEASE_ASSERT(array);
341
342 for (int i = 0; i < static_cast<int>(length); ++i)
343 array->initializeIndex(vm, i, values[-i]);
344 return array;
345}
346
347} // namespace JSC
348
349#endif // JSArray_h
350