constructArray() should always allocate the requested length.
[WebKit-https.git] / Source / JavaScriptCore / runtime / JSArray.h
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
29 namespace JSC {
30
31 class JSArray;
32 class LLIntOffsetsExtractor;
33
34 extern const ASCIILiteral LengthExceededTheMaximumArrayLengthError;
35
36 class JSArray : public JSNonFinalObject {
37     friend class LLIntOffsetsExtractor;
38     friend class Walker;
39     friend class JIT;
40
41 public:
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         
51 protected:
52     explicit JSArray(VM& vm, Structure* structure, Butterfly* butterfly)
53         : JSNonFinalObject(vm, structure, butterfly)
54     {
55     }
56
57 public:
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     // This function returns NonArray if the indexing types are not compatable for copying.
105     IndexingType mergeIndexingTypeForCopying(IndexingType other);
106     bool appendMemcpy(ExecState*, VM&, unsigned startIndex, JSArray* otherArray);
107
108     enum ShiftCountMode {
109         // This form of shift hints that we're doing queueing. With this assumption in hand,
110         // we convert to ArrayStorage, which has queue optimizations.
111         ShiftCountForShift,
112             
113         // This form of shift hints that we're just doing care and feeding on an array that
114         // is probably typically used for ordinary accesses. With this assumption in hand,
115         // we try to preserve whatever indexing type it has already.
116         ShiftCountForSplice
117     };
118
119     bool shiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
120     {
121         VM& vm = exec->vm();
122         return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
123     }
124     bool shiftCountForSplice(ExecState* exec, unsigned& startIndex, unsigned count)
125     {
126         return shiftCountWithAnyIndexingType(exec, startIndex, count);
127     }
128     template<ShiftCountMode shiftCountMode>
129     bool shiftCount(ExecState* exec, unsigned& startIndex, unsigned count)
130     {
131         switch (shiftCountMode) {
132         case ShiftCountForShift:
133             return shiftCountForShift(exec, startIndex, count);
134         case ShiftCountForSplice:
135             return shiftCountForSplice(exec, startIndex, count);
136         default:
137             CRASH();
138             return false;
139         }
140     }
141         
142     bool unshiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
143     {
144         return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
145     }
146     bool unshiftCountForSplice(ExecState* exec, unsigned startIndex, unsigned count)
147     {
148         return unshiftCountWithAnyIndexingType(exec, startIndex, count);
149     }
150     template<ShiftCountMode shiftCountMode>
151     bool unshiftCount(ExecState* exec, unsigned startIndex, unsigned count)
152     {
153         switch (shiftCountMode) {
154         case ShiftCountForShift:
155             return unshiftCountForShift(exec, startIndex, count);
156         case ShiftCountForSplice:
157             return unshiftCountForSplice(exec, startIndex, count);
158         default:
159             CRASH();
160             return false;
161         }
162     }
163
164     JS_EXPORT_PRIVATE void fillArgList(ExecState*, MarkedArgumentBuffer&);
165     JS_EXPORT_PRIVATE void copyToArguments(ExecState*, VirtualRegister firstElementDest, unsigned offset, unsigned length);
166
167     JS_EXPORT_PRIVATE bool isIteratorProtocolFastAndNonObservable();
168
169     static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype, IndexingType indexingType)
170     {
171         return Structure::create(vm, globalObject, prototype, TypeInfo(ArrayType, StructureFlags), info(), indexingType);
172     }
173         
174 protected:
175     void finishCreation(VM& vm)
176     {
177         Base::finishCreation(vm);
178         ASSERT(jsDynamicCast<JSArray*>(vm, this));
179         ASSERT_WITH_MESSAGE(type() == ArrayType || type() == DerivedArrayType, "Instance inheriting JSArray should have either ArrayType or DerivedArrayType");
180     }
181
182     static bool put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&);
183
184     static bool deleteProperty(JSCell*, ExecState*, PropertyName);
185     JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
186
187 private:
188     bool isLengthWritable()
189     {
190         ArrayStorage* storage = arrayStorageOrNull();
191         if (!storage)
192             return true;
193         SparseArrayValueMap* map = storage->m_sparseMap.get();
194         return !map || !map->lengthIsReadOnly();
195     }
196         
197     bool shiftCountWithAnyIndexingType(ExecState*, unsigned& startIndex, unsigned count);
198     JS_EXPORT_PRIVATE bool shiftCountWithArrayStorage(VM&, unsigned startIndex, unsigned count, ArrayStorage*);
199
200     bool unshiftCountWithAnyIndexingType(ExecState*, unsigned startIndex, unsigned count);
201     bool unshiftCountWithArrayStorage(ExecState*, unsigned startIndex, unsigned count, ArrayStorage*);
202     bool unshiftCountSlowCase(const AbstractLocker&, VM&, DeferGC&, bool, unsigned);
203
204     bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*);
205     void setLengthWritable(ExecState*, bool writable);
206 };
207
208 inline Butterfly* tryCreateArrayButterfly(VM& vm, JSObject* intendedOwner, unsigned initialLength)
209 {
210     Butterfly* butterfly = Butterfly::tryCreate(
211         vm, intendedOwner, 0, 0, true, baseIndexingHeaderForArrayStorage(initialLength),
212         ArrayStorage::sizeFor(BASE_ARRAY_STORAGE_VECTOR_LEN));
213     if (!butterfly)
214         return nullptr;
215     ArrayStorage* storage = butterfly->arrayStorage();
216     storage->m_sparseMap.clear();
217     storage->m_indexBias = 0;
218     storage->m_numValuesInVector = 0;
219     return butterfly;
220 }
221
222 inline JSArray* JSArray::tryCreate(VM& vm, Structure* structure, unsigned initialLength, unsigned vectorLengthHint)
223 {
224     ASSERT(vectorLengthHint >= initialLength);
225     unsigned outOfLineStorage = structure->outOfLineCapacity();
226
227     Butterfly* butterfly;
228     IndexingType indexingType = structure->indexingType();
229     if (LIKELY(!hasAnyArrayStorage(indexingType))) {
230         ASSERT(
231             hasUndecided(indexingType)
232             || hasInt32(indexingType)
233             || hasDouble(indexingType)
234             || hasContiguous(indexingType));
235
236         if (UNLIKELY(vectorLengthHint > MAX_STORAGE_VECTOR_LENGTH))
237             return nullptr;
238
239         unsigned vectorLength = Butterfly::optimalContiguousVectorLength(structure, vectorLengthHint);
240         void* temp = vm.jsValueGigacageAuxiliarySpace.allocateNonVirtual(
241             vm,
242             Butterfly::totalSize(0, outOfLineStorage, true, vectorLength * sizeof(EncodedJSValue)),
243             nullptr, AllocationFailureMode::ReturnNull);
244         if (!temp)
245             return nullptr;
246         butterfly = Butterfly::fromBase(temp, 0, outOfLineStorage);
247         butterfly->setVectorLength(vectorLength);
248         butterfly->setPublicLength(initialLength);
249         if (hasDouble(indexingType))
250             clearArray(butterfly->contiguousDouble().data(), vectorLength);
251         else
252             clearArray(butterfly->contiguous().data(), vectorLength);
253     } else {
254         ASSERT(
255             indexingType == ArrayWithSlowPutArrayStorage
256             || indexingType == ArrayWithArrayStorage);
257         butterfly = tryCreateArrayButterfly(vm, nullptr, initialLength);
258         if (!butterfly)
259             return nullptr;
260         for (unsigned i = 0; i < BASE_ARRAY_STORAGE_VECTOR_LEN; ++i)
261             butterfly->arrayStorage()->m_vector[i].clear();
262     }
263
264     return createWithButterfly(vm, nullptr, structure, butterfly);
265 }
266
267 inline JSArray* JSArray::tryCreate(VM& vm, Structure* structure, unsigned initialLength)
268 {
269     return tryCreate(vm, structure, initialLength, initialLength);
270 }
271
272 inline JSArray* JSArray::create(VM& vm, Structure* structure, unsigned initialLength)
273 {
274     JSArray* result = JSArray::tryCreate(vm, structure, initialLength);
275     RELEASE_ASSERT(result);
276
277     return result;
278 }
279
280 inline JSArray* JSArray::createWithButterfly(VM& vm, GCDeferralContext* deferralContext, Structure* structure, Butterfly* butterfly)
281 {
282     JSArray* array = new (NotNull, allocateCell<JSArray>(vm.heap, deferralContext)) JSArray(vm, structure, butterfly);
283     array->finishCreation(vm);
284     return array;
285 }
286
287 JSArray* asArray(JSValue);
288
289 inline JSArray* asArray(JSCell* cell)
290 {
291     ASSERT(cell->inherits<JSArray>(*cell->vm()));
292     return jsCast<JSArray*>(cell);
293 }
294
295 inline JSArray* asArray(JSValue value)
296 {
297     return asArray(value.asCell());
298 }
299
300 inline bool isJSArray(JSCell* cell)
301 {
302     ASSERT((cell->classInfo(*cell->vm()) == JSArray::info()) == (cell->type() == ArrayType));
303     return cell->type() == ArrayType;
304 }
305
306 inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }
307
308 JS_EXPORT_PRIVATE JSArray* constructArray(ExecState*, Structure*, const ArgList& values);
309 JS_EXPORT_PRIVATE JSArray* constructArray(ExecState*, Structure*, const JSValue* values, unsigned length);
310 JS_EXPORT_PRIVATE JSArray* constructArrayNegativeIndexed(ExecState*, Structure*, const JSValue* values, unsigned length);
311
312 } // namespace JSC