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