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