JSArray.h 13 KB
Newer Older
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 6 7 8 9 10 11 12 13 14 15 16
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
mjs's avatar
mjs committed
17
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
18 19 20
 *
 */

darin@apple.com's avatar
darin@apple.com committed
21 22
#ifndef JSArray_h
#define JSArray_h
23

24
#include "ArrayConventions.h"
25
#include "ButterflyInlines.h"
26
#include "JSObject.h"
27

28
namespace JSC {
29

30 31
class JSArray;
class LLIntOffsetsExtractor;
32

33 34 35 36
class JSArray : public JSNonFinalObject {
    friend class LLIntOffsetsExtractor;
    friend class Walker;
    friend class JIT;
37

38 39
public:
    typedef JSNonFinalObject Base;
40

41 42 43 44 45 46
    static size_t allocationSize(size_t inlineCapacity)
    {
        ASSERT_UNUSED(inlineCapacity, !inlineCapacity);
        return sizeof(JSArray);
    }
        
47
protected:
48 49
    explicit JSArray(VM& vm, Structure* structure, Butterfly* butterfly)
        : JSNonFinalObject(vm, structure, butterfly)
50 51
    {
    }
52

53
public:
54
    static JSArray* create(VM&, Structure*, unsigned initialLength = 0);
55

56 57 58 59
    // tryCreateUninitialized is used for fast construction of arrays whose size and
    // contents are known at time of creation. Clients of this interface must:
    //   - null-check the result (indicating out of memory, or otherwise unable to allocate vector).
    //   - 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
    static bool getOwnPropertySlot(JSObject*, ExecState*, PropertyName, PropertySlot&);
65

66
    DECLARE_EXPORT_INFO;
67
        
68 69 70
    unsigned length() const { return getArrayLength(); }
    // OK to use on new arrays, but not if it might be a RegExpMatchArray.
    bool setLength(ExecState*, unsigned, bool throwException = false);
71

72 73 74
    void sort(ExecState*);
    void sort(ExecState*, JSValue compareFunction, CallType, const CallData&);
    void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&);
75

76 77
    void push(ExecState*, JSValue);
    JSValue pop(ExecState*);
78

79 80 81 82
    enum ShiftCountMode {
        // This form of shift hints that we're doing queueing. With this assumption in hand,
        // we convert to ArrayStorage, which has queue optimizations.
        ShiftCountForShift,
83
            
84 85 86 87
        // This form of shift hints that we're just doing care and feeding on an array that
        // is probably typically used for ordinary accesses. With this assumption in hand,
        // we try to preserve whatever indexing type it has already.
        ShiftCountForSplice
88
    };
89

90
    bool shiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
91
    {
92
        return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm()));
93
    }
94
    bool shiftCountForSplice(ExecState* exec, unsigned startIndex, unsigned count)
95
    {
96
        return shiftCountWithAnyIndexingType(exec, startIndex, count);
97
    }
98 99
    template<ShiftCountMode shiftCountMode>
    bool shiftCount(ExecState* exec, unsigned startIndex, unsigned count)
100
    {
101 102 103 104 105 106 107 108
        switch (shiftCountMode) {
        case ShiftCountForShift:
            return shiftCountForShift(exec, startIndex, count);
        case ShiftCountForSplice:
            return shiftCountForSplice(exec, startIndex, count);
        default:
            CRASH();
            return false;
109
        }
110
    }
111
        
112 113
    bool unshiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
    {
114
        return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130
    }
    bool unshiftCountForSplice(ExecState* exec, unsigned startIndex, unsigned count)
    {
        return unshiftCountWithAnyIndexingType(exec, startIndex, count);
    }
    template<ShiftCountMode shiftCountMode>
    bool unshiftCount(ExecState* exec, unsigned startIndex, unsigned count)
    {
        switch (shiftCountMode) {
        case ShiftCountForShift:
            return unshiftCountForShift(exec, startIndex, count);
        case ShiftCountForSplice:
            return unshiftCountForSplice(exec, startIndex, count);
        default:
            CRASH();
            return false;
131
        }
132 133
    }

134 135
    void fillArgList(ExecState*, MarkedArgumentBuffer&);
    void copyToArguments(ExecState*, CallFrame*, uint32_t length);
darin@apple.com's avatar
darin@apple.com committed
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 143 144
        
protected:
    static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesGetPropertyNames | JSObject::StructureFlags;
    static void put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&);
145

146 147 148 149 150
    static bool deleteProperty(JSCell*, ExecState*, PropertyName);
    JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);

private:
    bool isLengthWritable()
darin@apple.com's avatar
darin@apple.com committed
151
    {
152 153 154 155 156
        ArrayStorage* storage = arrayStorageOrNull();
        if (!storage)
            return true;
        SparseArrayValueMap* map = storage->m_sparseMap.get();
        return !map || !map->lengthIsReadOnly();
darin@apple.com's avatar
darin@apple.com committed
157
    }
158 159 160
        
    bool shiftCountWithAnyIndexingType(ExecState*, unsigned startIndex, unsigned count);
    bool shiftCountWithArrayStorage(unsigned startIndex, unsigned count, ArrayStorage*);
darin@apple.com's avatar
darin@apple.com committed
161

162 163
    bool unshiftCountWithAnyIndexingType(ExecState*, unsigned startIndex, unsigned count);
    bool unshiftCountWithArrayStorage(ExecState*, unsigned startIndex, unsigned count, ArrayStorage*);
164
    bool unshiftCountSlowCase(VM&, bool, unsigned);
165

166 167 168
    template<IndexingType indexingType>
    void sortNumericVector(ExecState*, JSValue compareFunction, CallType, const CallData&);
        
169 170
    template<IndexingType indexingType, typename StorageType>
    void sortCompactedVector(ExecState*, ContiguousData<StorageType>, unsigned relevantLength);
171 172 173
        
    template<IndexingType indexingType>
    void sortVector(ExecState*, JSValue compareFunction, CallType, const CallData&);
174

175 176 177 178 179 180 181
    bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*);
    void setLengthWritable(ExecState*, bool writable);
        
    template<IndexingType indexingType>
    void compactForSorting(unsigned& numDefined, unsigned& newRelevantLength);
};

182
inline Butterfly* createContiguousArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned length, unsigned& vectorLength)
183 184
{
    IndexingHeader header;
185 186
    vectorLength = std::max(length, BASE_VECTOR_LEN);
    header.setVectorLength(vectorLength);
187 188
    header.setPublicLength(length);
    Butterfly* result = Butterfly::create(
189
        vm, intendedOwner, 0, 0, true, header, vectorLength * sizeof(EncodedJSValue));
190 191 192
    return result;
}

193
inline Butterfly* createArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned initialLength)
194 195
{
    Butterfly* butterfly = Butterfly::create(
196 197
        vm, intendedOwner, 0, 0, true, baseIndexingHeaderForArray(initialLength),
        ArrayStorage::sizeFor(BASE_VECTOR_LEN));
198 199 200 201 202 203 204
    ArrayStorage* storage = butterfly->arrayStorage();
    storage->m_indexBias = 0;
    storage->m_sparseMap.clear();
    storage->m_numValuesInVector = 0;
    return butterfly;
}

205 206
Butterfly* createArrayButterflyInDictionaryIndexingMode(
    VM&, JSCell* intendedOwner, unsigned initialLength);
207

208
inline JSArray* JSArray::create(VM& vm, Structure* structure, unsigned initialLength)
209 210
{
    Butterfly* butterfly;
211 212 213 214 215 216 217
    if (LIKELY(!hasArrayStorage(structure->indexingType()))) {
        ASSERT(
            hasUndecided(structure->indexingType())
            || hasInt32(structure->indexingType())
            || hasDouble(structure->indexingType())
            || hasContiguous(structure->indexingType()));
        unsigned vectorLength;
218
        butterfly = createContiguousArrayButterfly(vm, 0, initialLength, vectorLength);
219
        ASSERT(initialLength < MIN_SPARSE_ARRAY_INDEX);
220 221 222 223
        if (hasDouble(structure->indexingType())) {
            for (unsigned i = 0; i < vectorLength; ++i)
                butterfly->contiguousDouble()[i] = QNaN;
        }
224 225 226
    } else {
        ASSERT(
            structure->indexingType() == ArrayWithSlowPutArrayStorage
227
            || structure->indexingType() == ArrayWithArrayStorage);
228
        butterfly = createArrayButterfly(vm, 0, initialLength);
229
    }
230 231
    JSArray* array = new (NotNull, allocateCell<JSArray>(vm.heap)) JSArray(vm, structure, butterfly);
    array->finishCreation(vm);
232 233 234
    return array;
}

235
inline JSArray* JSArray::tryCreateUninitialized(VM& vm, Structure* structure, unsigned initialLength)
236 237 238 239 240 241
{
    unsigned vectorLength = std::max(BASE_VECTOR_LEN, initialLength);
    if (vectorLength > MAX_STORAGE_VECTOR_LENGTH)
        return 0;
        
    Butterfly* butterfly;
242 243 244 245 246 247 248
    if (LIKELY(!hasArrayStorage(structure->indexingType()))) {
        ASSERT(
            hasUndecided(structure->indexingType())
            || hasInt32(structure->indexingType())
            || hasDouble(structure->indexingType())
            || hasContiguous(structure->indexingType()));

249
        void* temp;
250
        if (!vm.heap.tryAllocateStorage(0, Butterfly::totalSize(0, 0, true, vectorLength * sizeof(EncodedJSValue)), &temp))
251 252 253 254
            return 0;
        butterfly = Butterfly::fromBase(temp, 0, 0);
        butterfly->setVectorLength(vectorLength);
        butterfly->setPublicLength(initialLength);
255 256 257 258
        if (hasDouble(structure->indexingType())) {
            for (unsigned i = initialLength; i < vectorLength; ++i)
                butterfly->contiguousDouble()[i] = QNaN;
        }
259 260
    } else {
        void* temp;
261
        if (!vm.heap.tryAllocateStorage(0, Butterfly::totalSize(0, 0, true, ArrayStorage::sizeFor(vectorLength)), &temp))
262 263 264 265 266 267 268
            return 0;
        butterfly = Butterfly::fromBase(temp, 0, 0);
        *butterfly->indexingHeader() = indexingHeaderForArray(initialLength, vectorLength);
        ArrayStorage* storage = butterfly->arrayStorage();
        storage->m_indexBias = 0;
        storage->m_sparseMap.clear();
        storage->m_numValuesInVector = initialLength;
269
    }
270
        
271 272
    JSArray* array = new (NotNull, allocateCell<JSArray>(vm.heap)) JSArray(vm, structure, butterfly);
    array->finishCreation(vm);
273 274 275 276 277 278 279
    return array;
}

JSArray* asArray(JSValue);

inline JSArray* asArray(JSCell* cell)
{
280
    ASSERT(cell->inherits(JSArray::info()));
281 282 283 284 285 286 287 288
    return jsCast<JSArray*>(cell);
}

inline JSArray* asArray(JSValue value)
{
    return asArray(value.asCell());
}

289
inline bool isJSArray(JSCell* cell) { return cell->classInfo() == JSArray::info(); }
290 291 292 293
inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }

inline JSArray* constructArray(ExecState* exec, Structure* arrayStructure, const ArgList& values)
{
294
    VM& vm = exec->vm();
295
    unsigned length = values.size();
296
    JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length);
297 298 299 300

    // FIXME: we should probably throw an out of memory error here, but
    // when making this change we should check that all clients of this
    // 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 306 307 308 309
    return array;
}
    
inline JSArray* constructArray(ExecState* exec, Structure* arrayStructure, const JSValue* values, unsigned length)
{
310 311
    VM& vm = exec->vm();
    JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length);
312 313 314 315

    // FIXME: we should probably throw an out of memory error here, but
    // when making this change we should check that all clients of this
    // 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 321
    return array;
}
322

323 324 325 326 327 328 329 330 331 332 333 334 335 336 337
inline JSArray* constructArrayNegativeIndexed(ExecState* exec, Structure* arrayStructure, const JSValue* values, unsigned length)
{
    VM& vm = exec->vm();
    JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length);

    // FIXME: we should probably throw an out of memory error here, but
    // when making this change we should check that all clients of this
    // function will correctly handle an exception being thrown from here.
    RELEASE_ASSERT(array);

    for (int i = 0; i < static_cast<int>(length); ++i)
        array->initializeIndex(vm, i, values[-i]);
    return array;
}

338
} // namespace JSC
339

340
#endif // JSArray_h