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