1a1a40e2eb1d17dc523b87bbbf83871b049ce3cd
[WebKit-https.git] / Source / JavaScriptCore / runtime / JSArray.h
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2003-2017 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
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(Checked<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* tryCreate(VM&, Structure*, unsigned initialLength = 0);
57     static JSArray* tryCreate(VM&, Structure*, unsigned initialLength, unsigned vectorLengthHint);
58     static JSArray* create(VM&, Structure*, unsigned initialLength = 0);
59     static JSArray* createWithButterfly(VM&, GCDeferralContext*, Structure*, Butterfly*);
60
61     // tryCreateUninitializedRestricted is used for fast construction of arrays whose size and
62     // contents are known at time of creation. This is a restricted API for careful use only in
63     // performance critical code paths. If you don't have a good reason to use it, you probably
64     // shouldn't use it. Instead, you should go with
65     //   - JSArray::tryCreate() or JSArray::create() instead of tryCreateUninitializedRestricted(), and
66     //   - putDirectIndex() instead of initializeIndex().
67     //
68     // Clients of this interface must:
69     //   - null-check the result (indicating out of memory, or otherwise unable to allocate vector).
70     //   - call 'initializeIndex' for all properties in sequence, for 0 <= i < initialLength.
71     //   - Provide a valid GCDefferalContext* if they might garbage collect when initializing properties,
72     //     otherwise the caller can provide a null GCDefferalContext*.
73     //   - Provide a local stack instance of ObjectInitializationScope at the call site.
74     //
75     JS_EXPORT_PRIVATE static JSArray* tryCreateUninitializedRestricted(ObjectInitializationScope&, GCDeferralContext*, Structure*, unsigned initialLength);
76     static JSArray* tryCreateUninitializedRestricted(ObjectInitializationScope& scope, Structure* structure, unsigned initialLength)
77     {
78         return tryCreateUninitializedRestricted(scope, nullptr, structure, initialLength);
79     }
80
81     JS_EXPORT_PRIVATE static bool defineOwnProperty(JSObject*, ExecState*, PropertyName, const PropertyDescriptor&, bool throwException);
82
83     JS_EXPORT_PRIVATE static bool getOwnPropertySlot(JSObject*, ExecState*, PropertyName, PropertySlot&);
84
85     DECLARE_EXPORT_INFO;
86
87     // 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.
88     unsigned length() const { return getArrayLength(); }
89
90     // OK to use on new arrays, but not if it might be a RegExpMatchArray or RuntimeArray.
91     JS_EXPORT_PRIVATE bool setLength(ExecState*, unsigned, bool throwException = false);
92
93     JS_EXPORT_PRIVATE void push(ExecState*, JSValue);
94     JS_EXPORT_PRIVATE JSValue pop(ExecState*);
95
96     JSArray* fastSlice(ExecState&, unsigned startIndex, unsigned count);
97
98     bool canFastCopy(VM&, JSArray* otherArray);
99     // This function returns NonArray if the indexing types are not compatable for copying.
100     IndexingType mergeIndexingTypeForCopying(IndexingType other);
101     bool appendMemcpy(ExecState*, VM&, unsigned startIndex, JSArray* otherArray);
102
103     enum ShiftCountMode {
104         // This form of shift hints that we're doing queueing. With this assumption in hand,
105         // we convert to ArrayStorage, which has queue optimizations.
106         ShiftCountForShift,
107             
108         // This form of shift hints that we're just doing care and feeding on an array that
109         // is probably typically used for ordinary accesses. With this assumption in hand,
110         // we try to preserve whatever indexing type it has already.
111         ShiftCountForSplice
112     };
113
114     bool shiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
115     {
116         VM& vm = exec->vm();
117         return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
118     }
119     bool shiftCountForSplice(ExecState* exec, unsigned& startIndex, unsigned count)
120     {
121         return shiftCountWithAnyIndexingType(exec, startIndex, count);
122     }
123     template<ShiftCountMode shiftCountMode>
124     bool shiftCount(ExecState* exec, unsigned& startIndex, unsigned count)
125     {
126         switch (shiftCountMode) {
127         case ShiftCountForShift:
128             return shiftCountForShift(exec, startIndex, count);
129         case ShiftCountForSplice:
130             return shiftCountForSplice(exec, startIndex, count);
131         default:
132             CRASH();
133             return false;
134         }
135     }
136         
137     bool unshiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
138     {
139         return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
140     }
141     bool unshiftCountForSplice(ExecState* exec, unsigned startIndex, unsigned count)
142     {
143         return unshiftCountWithAnyIndexingType(exec, startIndex, count);
144     }
145     template<ShiftCountMode shiftCountMode>
146     bool unshiftCount(ExecState* exec, unsigned startIndex, unsigned count)
147     {
148         switch (shiftCountMode) {
149         case ShiftCountForShift:
150             return unshiftCountForShift(exec, startIndex, count);
151         case ShiftCountForSplice:
152             return unshiftCountForSplice(exec, startIndex, count);
153         default:
154             CRASH();
155             return false;
156         }
157     }
158
159     JS_EXPORT_PRIVATE void fillArgList(ExecState*, MarkedArgumentBuffer&);
160     JS_EXPORT_PRIVATE void copyToArguments(ExecState*, VirtualRegister firstElementDest, unsigned offset, unsigned length);
161
162     JS_EXPORT_PRIVATE bool isIteratorProtocolFastAndNonObservable();
163
164     static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype, IndexingType indexingType)
165     {
166         return Structure::create(vm, globalObject, prototype, TypeInfo(ArrayType, StructureFlags), info(), indexingType);
167     }
168         
169 protected:
170     void finishCreation(VM& vm)
171     {
172         Base::finishCreation(vm);
173         ASSERT_WITH_MESSAGE(type() == ArrayType || type() == DerivedArrayType, "Instance inheriting JSArray should have either ArrayType or DerivedArrayType");
174     }
175
176     static bool put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&);
177
178     static bool deleteProperty(JSCell*, ExecState*, PropertyName);
179     JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
180
181 private:
182     bool isLengthWritable()
183     {
184         ArrayStorage* storage = arrayStorageOrNull();
185         if (!storage)
186             return true;
187         SparseArrayValueMap* map = storage->m_sparseMap.get();
188         return !map || !map->lengthIsReadOnly();
189     }
190         
191     bool shiftCountWithAnyIndexingType(ExecState*, unsigned& startIndex, unsigned count);
192     JS_EXPORT_PRIVATE bool shiftCountWithArrayStorage(VM&, unsigned startIndex, unsigned count, ArrayStorage*);
193
194     bool unshiftCountWithAnyIndexingType(ExecState*, unsigned startIndex, unsigned count);
195     bool unshiftCountWithArrayStorage(ExecState*, unsigned startIndex, unsigned count, ArrayStorage*);
196     bool unshiftCountSlowCase(const AbstractLocker&, VM&, DeferGC&, bool, unsigned);
197
198     bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*);
199     void setLengthWritable(ExecState*, bool writable);
200 };
201
202 inline Butterfly* tryCreateArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned initialLength)
203 {
204     Butterfly* butterfly = Butterfly::tryCreate(
205         vm, intendedOwner, 0, 0, true, baseIndexingHeaderForArrayStorage(initialLength),
206         ArrayStorage::sizeFor(BASE_ARRAY_STORAGE_VECTOR_LEN));
207     if (!butterfly)
208         return nullptr;
209     ArrayStorage* storage = butterfly->arrayStorage();
210     storage->m_sparseMap.clear();
211     storage->m_indexBias = 0;
212     storage->m_numValuesInVector = 0;
213     return butterfly;
214 }
215
216 Butterfly* createArrayButterflyInDictionaryIndexingMode(
217     VM&, JSCell* intendedOwner, unsigned initialLength);
218
219 inline JSArray* JSArray::tryCreate(VM& vm, Structure* structure, unsigned initialLength, unsigned vectorLengthHint)
220 {
221     ASSERT(vectorLengthHint >= initialLength);
222     unsigned outOfLineStorage = structure->outOfLineCapacity();
223
224     Butterfly* butterfly;
225     IndexingType indexingType = structure->indexingType();
226     if (LIKELY(!hasAnyArrayStorage(indexingType))) {
227         ASSERT(
228             hasUndecided(indexingType)
229             || hasInt32(indexingType)
230             || hasDouble(indexingType)
231             || hasContiguous(indexingType));
232
233         if (UNLIKELY(vectorLengthHint > MAX_STORAGE_VECTOR_LENGTH))
234             return nullptr;
235
236         unsigned vectorLength = Butterfly::optimalContiguousVectorLength(structure, vectorLengthHint);
237         void* temp = vm.jsValueGigacageAuxiliarySpace.tryAllocate(nullptr, Butterfly::totalSize(0, outOfLineStorage, true, vectorLength * sizeof(EncodedJSValue)));
238         if (!temp)
239             return nullptr;
240         butterfly = Butterfly::fromBase(temp, 0, outOfLineStorage);
241         butterfly->setVectorLength(vectorLength);
242         butterfly->setPublicLength(initialLength);
243         if (hasDouble(indexingType))
244             clearArray(butterfly->contiguousDouble().data(), vectorLength);
245         else if (LIKELY(!hasUndecided(indexingType)))
246             clearArray(butterfly->contiguous().data(), vectorLength);
247     } else {
248         ASSERT(
249             indexingType == ArrayWithSlowPutArrayStorage
250             || indexingType == ArrayWithArrayStorage);
251         butterfly = tryCreateArrayButterfly(vm, nullptr, initialLength);
252         if (!butterfly)
253             return nullptr;
254         for (unsigned i = 0; i < BASE_ARRAY_STORAGE_VECTOR_LEN; ++i)
255             butterfly->arrayStorage()->m_vector[i].clear();
256     }
257
258     return createWithButterfly(vm, nullptr, structure, butterfly);
259 }
260
261 inline JSArray* JSArray::tryCreate(VM& vm, Structure* structure, unsigned initialLength)
262 {
263     return tryCreate(vm, structure, initialLength, initialLength);
264 }
265
266 inline JSArray* JSArray::create(VM& vm, Structure* structure, unsigned initialLength)
267 {
268     JSArray* result = JSArray::tryCreate(vm, structure, initialLength);
269     RELEASE_ASSERT(result);
270
271     return result;
272 }
273
274 inline JSArray* JSArray::createWithButterfly(VM& vm, GCDeferralContext* deferralContext, Structure* structure, Butterfly* butterfly)
275 {
276     JSArray* array = new (NotNull, allocateCell<JSArray>(vm.heap, deferralContext)) JSArray(vm, structure, butterfly);
277     array->finishCreation(vm);
278     return array;
279 }
280
281 JSArray* asArray(JSValue);
282
283 inline JSArray* asArray(JSCell* cell)
284 {
285     ASSERT(cell->inherits(*cell->vm(), JSArray::info()));
286     return jsCast<JSArray*>(cell);
287 }
288
289 inline JSArray* asArray(JSValue value)
290 {
291     return asArray(value.asCell());
292 }
293
294 inline bool isJSArray(JSCell* cell)
295 {
296     ASSERT((cell->classInfo(*cell->vm()) == JSArray::info()) == (cell->type() == ArrayType));
297     return cell->type() == ArrayType;
298 }
299
300 inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }
301
302 inline JSArray* constructArray(ExecState* exec, Structure* arrayStructure, const ArgList& values)
303 {
304     VM& vm = exec->vm();
305     unsigned length = values.size();
306     ObjectInitializationScope scope(vm);
307     JSArray* array = JSArray::tryCreateUninitializedRestricted(scope, arrayStructure, length);
308
309     // FIXME: we should probably throw an out of memory error here, but
310     // when making this change we should check that all clients of this
311     // function will correctly handle an exception being thrown from here.
312     // https://bugs.webkit.org/show_bug.cgi?id=169786
313     RELEASE_ASSERT(array);
314
315     for (unsigned i = 0; i < length; ++i)
316         array->initializeIndex(scope, i, values.at(i));
317     return array;
318 }
319     
320 inline JSArray* constructArray(ExecState* exec, Structure* arrayStructure, const JSValue* values, unsigned length)
321 {
322     VM& vm = exec->vm();
323     ObjectInitializationScope scope(vm);
324     JSArray* array = JSArray::tryCreateUninitializedRestricted(scope, arrayStructure, length);
325
326     // FIXME: we should probably throw an out of memory error here, but
327     // when making this change we should check that all clients of this
328     // function will correctly handle an exception being thrown from here.
329     // https://bugs.webkit.org/show_bug.cgi?id=169786
330     RELEASE_ASSERT(array);
331
332     for (unsigned i = 0; i < length; ++i)
333         array->initializeIndex(scope, i, values[i]);
334     return array;
335 }
336
337 inline JSArray* constructArrayNegativeIndexed(ExecState* exec, Structure* arrayStructure, const JSValue* values, unsigned length)
338 {
339     VM& vm = exec->vm();
340     ObjectInitializationScope scope(vm);
341     JSArray* array = JSArray::tryCreateUninitializedRestricted(scope, arrayStructure, length);
342
343     // FIXME: we should probably throw an out of memory error here, but
344     // when making this change we should check that all clients of this
345     // function will correctly handle an exception being thrown from here.
346     // https://bugs.webkit.org/show_bug.cgi?id=169786
347     RELEASE_ASSERT(array);
348
349     for (int i = 0; i < static_cast<int>(length); ++i)
350         array->initializeIndex(scope, i, values[-i]);
351     return array;
352 }
353
354 } // namespace JSC