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