72c40305576df17e9b43b57036ac039d34608359
[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 "JSObject.h"
27
28 namespace JSC {
29
30 class JSArray;
31 class LLIntOffsetsExtractor;
32
33 class JSArray : public JSNonFinalObject {
34     friend class LLIntOffsetsExtractor;
35     friend class Walker;
36     friend class JIT;
37
38 public:
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         
48 protected:
49     explicit JSArray(VM& vm, Structure* structure, Butterfly* butterfly)
50         : JSNonFinalObject(vm, structure, butterfly)
51     {
52     }
53
54 public:
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     enum ShiftCountMode {
82         // This form of shift hints that we're doing queueing. With this assumption in hand,
83         // we convert to ArrayStorage, which has queue optimizations.
84         ShiftCountForShift,
85             
86         // This form of shift hints that we're just doing care and feeding on an array that
87         // is probably typically used for ordinary accesses. With this assumption in hand,
88         // we try to preserve whatever indexing type it has already.
89         ShiftCountForSplice
90     };
91
92     bool shiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
93     {
94         return shiftCountWithArrayStorage(exec->vm(), startIndex, count, ensureArrayStorage(exec->vm()));
95     }
96     bool shiftCountForSplice(ExecState* exec, unsigned& startIndex, unsigned count)
97     {
98         return shiftCountWithAnyIndexingType(exec, startIndex, count);
99     }
100     template<ShiftCountMode shiftCountMode>
101     bool shiftCount(ExecState* exec, unsigned& startIndex, unsigned count)
102     {
103         switch (shiftCountMode) {
104         case ShiftCountForShift:
105             return shiftCountForShift(exec, startIndex, count);
106         case ShiftCountForSplice:
107             return shiftCountForSplice(exec, startIndex, count);
108         default:
109             CRASH();
110             return false;
111         }
112     }
113         
114     bool unshiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
115     {
116         return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
117     }
118     bool unshiftCountForSplice(ExecState* exec, unsigned startIndex, unsigned count)
119     {
120         return unshiftCountWithAnyIndexingType(exec, startIndex, count);
121     }
122     template<ShiftCountMode shiftCountMode>
123     bool unshiftCount(ExecState* exec, unsigned startIndex, unsigned count)
124     {
125         switch (shiftCountMode) {
126         case ShiftCountForShift:
127             return unshiftCountForShift(exec, startIndex, count);
128         case ShiftCountForSplice:
129             return unshiftCountForSplice(exec, startIndex, count);
130         default:
131             CRASH();
132             return false;
133         }
134     }
135
136     JS_EXPORT_PRIVATE void fillArgList(ExecState*, MarkedArgumentBuffer&);
137     JS_EXPORT_PRIVATE void copyToArguments(ExecState*, VirtualRegister firstElementDest, unsigned offset, unsigned length);
138
139     static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype, IndexingType indexingType)
140     {
141         return Structure::create(vm, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), info(), indexingType);
142     }
143         
144 protected:
145     static void put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&);
146
147     static bool deleteProperty(JSCell*, ExecState*, PropertyName);
148     JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
149
150 private:
151     bool isLengthWritable()
152     {
153         ArrayStorage* storage = arrayStorageOrNull();
154         if (!storage)
155             return true;
156         SparseArrayValueMap* map = storage->m_sparseMap.get();
157         return !map || !map->lengthIsReadOnly();
158     }
159         
160     bool shiftCountWithAnyIndexingType(ExecState*, unsigned& startIndex, unsigned count);
161     JS_EXPORT_PRIVATE bool shiftCountWithArrayStorage(VM&, unsigned startIndex, unsigned count, ArrayStorage*);
162
163     bool unshiftCountWithAnyIndexingType(ExecState*, unsigned startIndex, unsigned count);
164     bool unshiftCountWithArrayStorage(ExecState*, unsigned startIndex, unsigned count, ArrayStorage*);
165     bool unshiftCountSlowCase(VM&, bool, unsigned);
166
167     bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*);
168     void setLengthWritable(ExecState*, bool writable);
169 };
170
171 inline Butterfly* createContiguousArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned length, unsigned& vectorLength)
172 {
173     IndexingHeader header;
174     vectorLength = std::max(length, BASE_VECTOR_LEN);
175     header.setVectorLength(vectorLength);
176     header.setPublicLength(length);
177     Butterfly* result = Butterfly::create(
178         vm, intendedOwner, 0, 0, true, header, vectorLength * sizeof(EncodedJSValue));
179     return result;
180 }
181
182 inline Butterfly* createArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned initialLength)
183 {
184     Butterfly* butterfly = Butterfly::create(
185         vm, intendedOwner, 0, 0, true, baseIndexingHeaderForArray(initialLength),
186         ArrayStorage::sizeFor(BASE_VECTOR_LEN));
187     ArrayStorage* storage = butterfly->arrayStorage();
188     storage->m_indexBias = 0;
189     storage->m_sparseMap.clear();
190     storage->m_numValuesInVector = 0;
191     return butterfly;
192 }
193
194 Butterfly* createArrayButterflyInDictionaryIndexingMode(
195     VM&, JSCell* intendedOwner, unsigned initialLength);
196
197 inline JSArray* JSArray::create(VM& vm, Structure* structure, unsigned initialLength)
198 {
199     Butterfly* butterfly;
200     if (LIKELY(!hasAnyArrayStorage(structure->indexingType()))) {
201         ASSERT(
202             hasUndecided(structure->indexingType())
203             || hasInt32(structure->indexingType())
204             || hasDouble(structure->indexingType())
205             || hasContiguous(structure->indexingType()));
206         unsigned vectorLength;
207         butterfly = createContiguousArrayButterfly(vm, 0, initialLength, vectorLength);
208         ASSERT(initialLength < MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH);
209         if (hasDouble(structure->indexingType())) {
210             for (unsigned i = 0; i < vectorLength; ++i)
211                 butterfly->contiguousDouble()[i] = PNaN;
212         }
213     } else {
214         ASSERT(
215             structure->indexingType() == ArrayWithSlowPutArrayStorage
216             || structure->indexingType() == ArrayWithArrayStorage);
217         butterfly = createArrayButterfly(vm, 0, initialLength);
218     }
219
220     return createWithButterfly(vm, structure, butterfly);
221 }
222
223 inline JSArray* JSArray::tryCreateUninitialized(VM& vm, Structure* structure, unsigned initialLength)
224 {
225     unsigned vectorLength = std::max(BASE_VECTOR_LEN, initialLength);
226     if (vectorLength > MAX_STORAGE_VECTOR_LENGTH)
227         return 0;
228         
229     Butterfly* butterfly;
230     if (LIKELY(!hasAnyArrayStorage(structure->indexingType()))) {
231         ASSERT(
232             hasUndecided(structure->indexingType())
233             || hasInt32(structure->indexingType())
234             || hasDouble(structure->indexingType())
235             || hasContiguous(structure->indexingType()));
236
237         void* temp;
238         if (!vm.heap.tryAllocateStorage(0, Butterfly::totalSize(0, 0, true, vectorLength * sizeof(EncodedJSValue)), &temp))
239             return 0;
240         butterfly = Butterfly::fromBase(temp, 0, 0);
241         butterfly->setVectorLength(vectorLength);
242         butterfly->setPublicLength(initialLength);
243         if (hasDouble(structure->indexingType())) {
244             for (unsigned i = initialLength; i < vectorLength; ++i)
245                 butterfly->contiguousDouble()[i] = PNaN;
246         }
247     } else {
248         void* temp;
249         if (!vm.heap.tryAllocateStorage(0, Butterfly::totalSize(0, 0, true, ArrayStorage::sizeFor(vectorLength)), &temp))
250             return 0;
251         butterfly = Butterfly::fromBase(temp, 0, 0);
252         *butterfly->indexingHeader() = indexingHeaderForArray(initialLength, vectorLength);
253         ArrayStorage* storage = butterfly->arrayStorage();
254         storage->m_indexBias = 0;
255         storage->m_sparseMap.clear();
256         storage->m_numValuesInVector = initialLength;
257     }
258
259     return createWithButterfly(vm, structure, butterfly);
260 }
261
262 inline JSArray* JSArray::createWithButterfly(VM& vm, Structure* structure, Butterfly* butterfly)
263 {
264     JSArray* array = new (NotNull, allocateCell<JSArray>(vm.heap)) JSArray(vm, structure, butterfly);
265     array->finishCreation(vm);
266     return array;
267 }
268
269 JSArray* asArray(JSValue);
270
271 inline JSArray* asArray(JSCell* cell)
272 {
273     ASSERT(cell->inherits(JSArray::info()));
274     return jsCast<JSArray*>(cell);
275 }
276
277 inline JSArray* asArray(JSValue value)
278 {
279     return asArray(value.asCell());
280 }
281
282 inline bool isJSArray(JSCell* cell) { return cell->classInfo() == JSArray::info(); }
283 inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }
284
285 inline JSArray* constructArray(ExecState* exec, Structure* arrayStructure, const ArgList& values)
286 {
287     VM& vm = exec->vm();
288     unsigned length = values.size();
289     JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length);
290
291     // FIXME: we should probably throw an out of memory error here, but
292     // when making this change we should check that all clients of this
293     // function will correctly handle an exception being thrown from here.
294     RELEASE_ASSERT(array);
295
296     for (unsigned i = 0; i < length; ++i)
297         array->initializeIndex(vm, i, values.at(i));
298     return array;
299 }
300     
301 inline JSArray* constructArray(ExecState* exec, Structure* arrayStructure, const JSValue* values, unsigned length)
302 {
303     VM& vm = exec->vm();
304     JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length);
305
306     // FIXME: we should probably throw an out of memory error here, but
307     // when making this change we should check that all clients of this
308     // function will correctly handle an exception being thrown from here.
309     RELEASE_ASSERT(array);
310
311     for (unsigned i = 0; i < length; ++i)
312         array->initializeIndex(vm, i, values[i]);
313     return array;
314 }
315
316 inline JSArray* constructArrayNegativeIndexed(ExecState* exec, Structure* arrayStructure, const JSValue* values, unsigned length)
317 {
318     VM& vm = exec->vm();
319     JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length);
320
321     // FIXME: we should probably throw an out of memory error here, but
322     // when making this change we should check that all clients of this
323     // function will correctly handle an exception being thrown from here.
324     RELEASE_ASSERT(array);
325
326     for (int i = 0; i < static_cast<int>(length); ++i)
327         array->initializeIndex(vm, i, values[-i]);
328     return array;
329 }
330
331 } // namespace JSC
332
333 #endif // JSArray_h