JSArray.cpp 48.6 KB
Newer Older
darin's avatar
darin committed
1 2
/*
 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3
 *  Copyright (C) 2003, 2007, 2008, 2009 Apple Inc. All rights reserved.
darin's avatar
darin committed
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
 *  Copyright (C) 2003 Peter Kelly (pmk@post.com)
 *  Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
 *
 *  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
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 *
 */

#include "config.h"
darin@apple.com's avatar
darin@apple.com committed
24
#include "JSArray.h"
darin's avatar
darin committed
25

darin@apple.com's avatar
darin@apple.com committed
26
#include "ArrayPrototype.h"
27
#include "CachedCall.h"
28
#include "Error.h"
29
#include "Executable.h"
darin's avatar
darin committed
30
#include "PropertyNameArray.h"
ap@webkit.org's avatar
ap@webkit.org committed
31
#include <wtf/AVLTree.h>
32
#include <wtf/Assertions.h>
33
#include <wtf/OwnPtr.h>
34
#include <Operations.h>
darin's avatar
darin committed
35

36
using namespace std;
ap@webkit.org's avatar
ap@webkit.org committed
37
using namespace WTF;
bdash's avatar
bdash committed
38

39
namespace JSC {
darin's avatar
darin committed
40

ggaren@apple.com's avatar
ggaren@apple.com committed
41 42
ASSERT_CLASS_FITS_IN_CELL(JSArray);

barraclough@apple.com's avatar
barraclough@apple.com committed
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
// Overview of JSArray
//
// Properties of JSArray objects may be stored in one of three locations:
//   * The regular JSObject property map.
//   * A storage vector.
//   * A sparse map of array entries.
//
// Properties with non-numeric identifiers, with identifiers that are not representable
// as an unsigned integer, or where the value is greater than  MAX_ARRAY_INDEX
// (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit
// integer) are not considered array indices and will be stored in the JSObject property map.
//
// All properties with a numeric identifer, representable as an unsigned integer i,
// where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the
// storage vector or the sparse map.  An array index i will be handled in the following
// fashion:
//
//   * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector.
//   * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either
//     be stored in the storage vector or in the sparse array, depending on the density of
//     data that would be stored in the vector (a vector being used where at least
//     (1 / minDensityMultiplier) of the entries would be populated).
//   * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored
//     in the sparse array.

// The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
// function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
ggaren@apple.com's avatar
ggaren@apple.com committed
70 71 72
// size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(JSValue)) +
// (vectorLength * sizeof(JSValue)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
#define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue))
barraclough@apple.com's avatar
barraclough@apple.com committed
73 74 75 76 77

// These values have to be macros to be used in max() and min() without introducing
// a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
#define MIN_SPARSE_ARRAY_INDEX 10000U
#define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
78
// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
barraclough@apple.com's avatar
barraclough@apple.com committed
79
#define MAX_ARRAY_INDEX 0xFFFFFFFEU
darin's avatar
darin committed
80

81 82 83 84 85 86 87 88
// The value BASE_VECTOR_LEN is the maximum number of vector elements we'll allocate
// for an array that was created with a sepcified length (e.g. a = new Array(123))
#define BASE_VECTOR_LEN 4U
    
// The upper bound to the size we'll grow a zero length array when the first element
// is added.
#define FIRST_VECTOR_GROW 4U

darin's avatar
darin committed
89
// Our policy for when to use a vector and when to use a sparse map.
barraclough@apple.com's avatar
barraclough@apple.com committed
90 91
// For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
// When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
darin's avatar
darin committed
92 93 94
// as long as it is 1/8 full. If more sparse than that, we use a map.
static const unsigned minDensityMultiplier = 8;

95
const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0, CREATE_METHOD_TABLE(JSArray)};
darin's avatar
darin committed
96

97 98 99 100 101
// We keep track of the size of the last array after it was grown.  We use this
// as a simple heuristic for as the value to grow the next array from size 0.
// This value is capped by the constant FIRST_VECTOR_GROW defined above.
static unsigned lastArraySize = 0;

darin's avatar
darin committed
102 103
static inline size_t storageSize(unsigned vectorLength)
{
barraclough@apple.com's avatar
barraclough@apple.com committed
104 105 106 107
    ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);

    // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
    // - as asserted above - the following calculation cannot overflow.
ggaren@apple.com's avatar
ggaren@apple.com committed
108
    size_t size = (sizeof(ArrayStorage) - sizeof(JSValue)) + (vectorLength * sizeof(JSValue));
barraclough@apple.com's avatar
barraclough@apple.com committed
109 110
    // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
    // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
ggaren@apple.com's avatar
ggaren@apple.com committed
111
    ASSERT(((size - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValue))));
barraclough@apple.com's avatar
barraclough@apple.com committed
112 113

    return size;
darin's avatar
darin committed
114 115 116 117 118 119 120
}

static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
{
    return length / minDensityMultiplier <= numValues;
}

121 122
#if !CHECK_ARRAY_CONSISTENCY

darin@apple.com's avatar
darin@apple.com committed
123
inline void JSArray::checkConsistency(ConsistencyCheckType)
124 125 126 127 128
{
}

#endif

129
JSArray::JSArray(VPtrStealingHackType)
130
    : JSNonFinalObject(VPtrStealingHack)
131 132 133
{
}

134 135
JSArray::JSArray(JSGlobalData& globalData, Structure* structure)
    : JSNonFinalObject(globalData, structure)
weinig@apple.com's avatar
weinig@apple.com committed
136
{
137 138 139 140 141
}

void JSArray::finishCreation(JSGlobalData& globalData)
{
    Base::finishCreation(globalData);
142 143
    ASSERT(inherits(&s_info));

weinig@apple.com's avatar
weinig@apple.com committed
144 145
    unsigned initialCapacity = 0;

146 147
    m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
    m_storage->m_allocBase = m_storage;
148
    m_indexBias = 0;
149
    m_vectorLength = initialCapacity;
weinig@apple.com's avatar
weinig@apple.com committed
150 151

    checkConsistency();
152 153

    Heap::heap(this)->reportExtraMemoryCost(storageSize(0));
weinig@apple.com's avatar
weinig@apple.com committed
154 155
}

156
void JSArray::finishCreation(JSGlobalData& globalData, unsigned initialLength, ArrayCreationMode creationMode)
darin's avatar
darin committed
157
{
158
    Base::finishCreation(globalData);
159 160
    ASSERT(inherits(&s_info));

161 162 163 164
    unsigned initialCapacity;
    if (creationMode == CreateCompact)
        initialCapacity = initialLength;
    else
165 166
        initialCapacity = min(BASE_VECTOR_LEN, MIN_SPARSE_ARRAY_INDEX);
    
167 168 169
    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
    m_storage->m_allocBase = m_storage;
    m_storage->m_length = initialLength;
170
    m_indexBias = 0;
171
    m_vectorLength = initialCapacity;
172 173 174
    m_storage->m_sparseValueMap = 0;
    m_storage->subclassData = 0;
    m_storage->reportedMapCapacity = 0;
darin's avatar
darin committed
175

176 177
    if (creationMode == CreateCompact) {
#if CHECK_ARRAY_CONSISTENCY
178
        m_storage->m_inCompactInitialization = !!initialCapacity;
179
#endif
180 181
        m_storage->m_length = 0;
        m_storage->m_numValuesInVector = initialCapacity;
182 183
    } else {
#if CHECK_ARRAY_CONSISTENCY
184
        storage->m_inCompactInitialization = false;
185
#endif
186 187
        m_storage->m_length = initialLength;
        m_storage->m_numValuesInVector = 0;
188
        WriteBarrier<Unknown>* vector = m_storage->m_vector;
189
        for (size_t i = 0; i < initialCapacity; ++i)
190
            vector[i].clear();
191
    }
192

193
    checkConsistency();
194
    
195
    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity));
darin's avatar
darin committed
196 197
}

198
void JSArray::finishCreation(JSGlobalData& globalData, const ArgList& list)
darin's avatar
darin committed
199
{
200
    Base::finishCreation(globalData);
201 202
    ASSERT(inherits(&s_info));

203
    unsigned initialCapacity = list.size();
204 205 206 207 208 209 210 211 212 213
    unsigned initialStorage;
    
    // If the ArgList is empty, allocate space for 3 entries.  This value empirically
    // works well for benchmarks.
    if (!initialCapacity)
        initialStorage = 3;
    else
        initialStorage = initialCapacity;
    
    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialStorage)));
214
    m_storage->m_allocBase = m_storage;
215
    m_indexBias = 0;
216
    m_storage->m_length = initialCapacity;
217
    m_vectorLength = initialStorage;
218 219 220 221
    m_storage->m_numValuesInVector = initialCapacity;
    m_storage->m_sparseValueMap = 0;
    m_storage->subclassData = 0;
    m_storage->reportedMapCapacity = 0;
222
#if CHECK_ARRAY_CONSISTENCY
223
    m_storage->m_inCompactInitialization = false;
224
#endif
darin's avatar
darin committed
225

ggaren's avatar
ggaren committed
226
    size_t i = 0;
227
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
ggaren@apple.com's avatar
ggaren@apple.com committed
228 229
    for (; i < list.size(); ++i)
        vector[i].set(globalData, this, list.at(i));
230
    for (; i < initialStorage; i++)
231
        vector[i].clear();
darin's avatar
darin committed
232

233
    checkConsistency();
234

235
    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialStorage));
darin's avatar
darin committed
236 237
}

238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277
void JSArray::finishCreation(JSGlobalData& globalData, const JSValue* values, size_t length)
{
    Base::finishCreation(globalData);
    ASSERT(inherits(&s_info));

    unsigned initialCapacity = length;
    unsigned initialStorage;
    
    // If the ArgList is empty, allocate space for 3 entries.  This value empirically
    // works well for benchmarks.
    if (!initialCapacity)
        initialStorage = 3;
    else
        initialStorage = initialCapacity;
    
    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialStorage)));
    m_storage->m_allocBase = m_storage;
    m_indexBias = 0;
    m_storage->m_length = initialCapacity;
    m_vectorLength = initialStorage;
    m_storage->m_numValuesInVector = initialCapacity;
    m_storage->m_sparseValueMap = 0;
    m_storage->subclassData = 0;
    m_storage->reportedMapCapacity = 0;
#if CHECK_ARRAY_CONSISTENCY
    m_storage->m_inCompactInitialization = false;
#endif

    size_t i = 0;
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
    for ( ; i != length; ++i)
        vector[i].set(globalData, this, values[i]);
    for (; i < initialStorage; i++)
        vector[i].clear();

    checkConsistency();

    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialStorage));
}

darin@apple.com's avatar
darin@apple.com committed
278
JSArray::~JSArray()
darin's avatar
darin committed
279
{
ap@apple.com's avatar
ap@apple.com committed
280
    ASSERT(vptr() == JSGlobalData::jsArrayVPtr);
281 282
    checkConsistency(DestructorConsistencyCheck);

283 284
    delete m_storage->m_sparseValueMap;
    fastFree(m_storage->m_allocBase);
darin's avatar
darin committed
285 286
}

287
bool JSArray::getOwnPropertySlotByIndex(JSCell* cell, ExecState* exec, unsigned i, PropertySlot& slot)
288
{
289
    JSArray* thisObject = jsCast<JSArray*>(cell);
290
    ArrayStorage* storage = thisObject->m_storage;
291
    
ggaren@apple.com's avatar
ggaren@apple.com committed
292
    if (i >= storage->m_length) {
barraclough@apple.com's avatar
barraclough@apple.com committed
293
        if (i > MAX_ARRAY_INDEX)
294
            return thisObject->methodTable()->getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
295 296 297
        return false;
    }

298
    if (i < thisObject->m_vectorLength) {
299 300 301
        JSValue value = storage->m_vector[i].get();
        if (value) {
            slot.setValue(value);
darin's avatar
darin committed
302 303 304
            return true;
        }
    } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
305
        if (i >= MIN_SPARSE_ARRAY_INDEX) {
darin@apple.com's avatar
darin@apple.com committed
306 307
            SparseArrayValueMap::iterator it = map->find(i);
            if (it != map->end()) {
308
                slot.setValue(it->second.get());
darin@apple.com's avatar
darin@apple.com committed
309 310
                return true;
            }
darin's avatar
darin committed
311 312 313
        }
    }

314
    return JSObject::getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
315 316
}

317 318
bool JSArray::getOwnPropertySlot(JSCell* cell, ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
{
319
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
320
    if (propertyName == exec->propertyNames().length) {
321
        slot.setValue(jsNumber(thisObject->length()));
darin's avatar
darin committed
322 323 324 325
        return true;
    }

    bool isArrayIndex;
326
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
327
    if (isArrayIndex)
328
        return JSArray::getOwnPropertySlotByIndex(thisObject, exec, i, slot);
darin's avatar
darin committed
329

330
    return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
darin's avatar
darin committed
331 332
}

333
bool JSArray::getOwnPropertyDescriptor(JSObject* object, ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
334
{
335
    JSArray* thisObject = jsCast<JSArray*>(object);
336
    if (propertyName == exec->propertyNames().length) {
337
        descriptor.setDescriptor(jsNumber(thisObject->length()), DontDelete | DontEnum);
338 339
        return true;
    }
340

341
    ArrayStorage* storage = thisObject->m_storage;
342 343
    
    bool isArrayIndex;
344
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
345
    if (isArrayIndex) {
346
        if (i >= storage->m_length)
347
            return false;
348
        if (i < thisObject->m_vectorLength) {
349
            WriteBarrier<Unknown>& value = storage->m_vector[i];
350
            if (value) {
351
                descriptor.setDescriptor(value.get(), 0);
352 353
                return true;
            }
354
        } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
355 356 357
            if (i >= MIN_SPARSE_ARRAY_INDEX) {
                SparseArrayValueMap::iterator it = map->find(i);
                if (it != map->end()) {
358
                    descriptor.setDescriptor(it->second.get(), 0);
359 360 361 362 363
                    return true;
                }
            }
        }
    }
364
    return JSObject::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor);
365 366
}

367 368 369
// ECMA 15.4.5.1
void JSArray::put(JSCell* cell, ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
{
370
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
371
    bool isArrayIndex;
372
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
373
    if (isArrayIndex) {
374
        putByIndex(thisObject, exec, i, value);
darin's avatar
darin committed
375 376 377 378
        return;
    }

    if (propertyName == exec->propertyNames().length) {
weinig@apple.com's avatar
weinig@apple.com committed
379 380
        unsigned newLength = value.toUInt32(exec);
        if (value.toNumber(exec) != static_cast<double>(newLength)) {
381
            throwError(exec, createRangeError(exec, "Invalid array length"));
darin's avatar
darin committed
382 383
            return;
        }
384
        thisObject->setLength(newLength);
darin's avatar
darin committed
385 386 387
        return;
    }

388
    JSObject::put(thisObject, exec, propertyName, value, slot);
darin's avatar
darin committed
389 390
}

391
void JSArray::putByIndex(JSCell* cell, ExecState* exec, unsigned i, JSValue value)
392
{
393
    JSArray* thisObject = jsCast<JSArray*>(cell);
394 395 396
    thisObject->checkConsistency();

    ArrayStorage* storage = thisObject->m_storage;
397 398

    unsigned length = storage->m_length;
barraclough@apple.com's avatar
barraclough@apple.com committed
399
    if (i >= length && i <= MAX_ARRAY_INDEX) {
darin's avatar
darin committed
400
        length = i + 1;
401
        storage->m_length = length;
darin's avatar
darin committed
402 403
    }

404
    if (i < thisObject->m_vectorLength) {
405
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
406
        if (valueSlot) {
407 408
            valueSlot.set(exec->globalData(), thisObject, value);
            thisObject->checkConsistency();
409 410
            return;
        }
411
        valueSlot.set(exec->globalData(), thisObject, value);
412
        ++storage->m_numValuesInVector;
413
        thisObject->checkConsistency();
darin's avatar
darin committed
414 415 416
        return;
    }

417
    thisObject->putSlowCase(exec, i, value);
418 419
}

ggaren@apple.com's avatar
ggaren@apple.com committed
420
NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
421
{
422
    ArrayStorage* storage = m_storage;
423
    
darin's avatar
darin committed
424
    SparseArrayValueMap* map = storage->m_sparseValueMap;
ap@webkit.org's avatar
ap@webkit.org committed
425

barraclough@apple.com's avatar
barraclough@apple.com committed
426 427
    if (i >= MIN_SPARSE_ARRAY_INDEX) {
        if (i > MAX_ARRAY_INDEX) {
weinig@apple.com's avatar
weinig@apple.com committed
428
            PutPropertySlot slot;
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
429
            methodTable()->put(this, exec, Identifier::from(exec, i), value, slot);
430 431 432
            return;
        }

ap@webkit.org's avatar
ap@webkit.org committed
433
        // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
434
        // (which will only be compacted as we reach indices that are less than MIN_SPARSE_ARRAY_INDEX) - but this makes the check much faster.
barraclough@apple.com's avatar
barraclough@apple.com committed
435
        if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
ap@webkit.org's avatar
ap@webkit.org committed
436 437 438 439
            if (!map) {
                map = new SparseArrayValueMap;
                storage->m_sparseValueMap = map;
            }
440

441 442 443 444
            WriteBarrier<Unknown> temp;
            pair<SparseArrayValueMap::iterator, bool> result = map->add(i, temp);
            result.first->second.set(exec->globalData(), this, value);
            if (!result.second) // pre-existing entry
445 446 447 448 449 450 451
                return;

            size_t capacity = map->capacity();
            if (capacity != storage->reportedMapCapacity) {
                Heap::heap(this)->reportExtraMemoryCost((capacity - storage->reportedMapCapacity) * (sizeof(unsigned) + sizeof(JSValue)));
                storage->reportedMapCapacity = capacity;
            }
darin's avatar
darin committed
452 453 454 455
            return;
        }
    }

ap@webkit.org's avatar
ap@webkit.org committed
456 457 458
    // We have decided that we'll put the new item into the vector.
    // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
    if (!map || map->isEmpty()) {
barraclough@apple.com's avatar
barraclough@apple.com committed
459
        if (increaseVectorLength(i + 1)) {
460
            storage = m_storage;
461
            storage->m_vector[i].set(exec->globalData(), this, value);
462
            ++storage->m_numValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
463 464 465
            checkConsistency();
        } else
            throwOutOfMemoryError(exec);
darin's avatar
darin committed
466 467 468
        return;
    }

ap@webkit.org's avatar
ap@webkit.org committed
469 470
    // Decide how many values it would be best to move from the map.
    unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
471
    unsigned newVectorLength = getNewVectorLength(i + 1);
472
    for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
darin's avatar
darin committed
473
        newNumValuesInVector += map->contains(j);
barraclough@apple.com's avatar
barraclough@apple.com committed
474
    if (i >= MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
475
        newNumValuesInVector -= map->contains(i);
darin's avatar
darin committed
476
    if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
477
        unsigned needLength = max(i + 1, storage->m_length);
darin's avatar
darin committed
478
        unsigned proposedNewNumValuesInVector = newNumValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
479
        // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
480
        while ((newVectorLength < needLength) && (newVectorLength < MAX_STORAGE_VECTOR_LENGTH)) {
481
            unsigned proposedNewVectorLength = getNewVectorLength(newVectorLength + 1);
barraclough@apple.com's avatar
barraclough@apple.com committed
482
            for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
darin's avatar
darin committed
483 484 485 486 487 488 489 490
                proposedNewNumValuesInVector += map->contains(j);
            if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
                break;
            newVectorLength = proposedNewVectorLength;
            newNumValuesInVector = proposedNewNumValuesInVector;
        }
    }

491
    void* baseStorage = storage->m_allocBase;
492 493
    
    if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) {
barraclough@apple.com's avatar
barraclough@apple.com committed
494 495 496
        throwOutOfMemoryError(exec);
        return;
    }
darin's avatar
darin committed
497

498
    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
499 500
    m_storage->m_allocBase = baseStorage;
    storage = m_storage;
501
    
502
    unsigned vectorLength = m_vectorLength;
503
    WriteBarrier<Unknown>* vector = storage->m_vector;
504

darin's avatar
darin committed
505 506
    if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
        for (unsigned j = vectorLength; j < newVectorLength; ++j)
507
            vector[j].clear();
barraclough@apple.com's avatar
barraclough@apple.com committed
508
        if (i > MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
509
            map->remove(i);
darin's avatar
darin committed
510
    } else {
barraclough@apple.com's avatar
barraclough@apple.com committed
511
        for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
512 513
            vector[j].clear();
        JSGlobalData& globalData = exec->globalData();
barraclough@apple.com's avatar
barraclough@apple.com committed
514
        for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
515
            vector[j].set(globalData, this, map->take(j).get());
darin's avatar
darin committed
516 517
    }

518
    ASSERT(i < newVectorLength);
darin's avatar
darin committed
519

520
    m_vectorLength = newVectorLength;
darin's avatar
darin committed
521
    storage->m_numValuesInVector = newNumValuesInVector;
ap@webkit.org's avatar
ap@webkit.org committed
522

523
    storage->m_vector[i].set(exec->globalData(), this, value);
524 525

    checkConsistency();
526 527

    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
darin's avatar
darin committed
528 529
}

530 531
bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, const Identifier& propertyName)
{
532
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
533
    bool isArrayIndex;
534
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
535
    if (isArrayIndex)
536
        return thisObject->methodTable()->deletePropertyByIndex(thisObject, exec, i);
darin's avatar
darin committed
537 538 539 540

    if (propertyName == exec->propertyNames().length)
        return false;

541
    return JSObject::deleteProperty(thisObject, exec, propertyName);
darin's avatar
darin committed
542 543
}

544
bool JSArray::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
545
{
546
    JSArray* thisObject = jsCast<JSArray*>(cell);
547 548 549
    thisObject->checkConsistency();

    ArrayStorage* storage = thisObject->m_storage;
550
    
551
    if (i < thisObject->m_vectorLength) {
552
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
553
        if (!valueSlot) {
554
            thisObject->checkConsistency();
555 556
            return false;
        }
557
        valueSlot.clear();
558
        --storage->m_numValuesInVector;
559
        thisObject->checkConsistency();
560
        return true;
darin's avatar
darin committed
561 562 563
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
564
        if (i >= MIN_SPARSE_ARRAY_INDEX) {
darin@apple.com's avatar
darin@apple.com committed
565 566 567
            SparseArrayValueMap::iterator it = map->find(i);
            if (it != map->end()) {
                map->remove(it);
568
                thisObject->checkConsistency();
darin@apple.com's avatar
darin@apple.com committed
569 570
                return true;
            }
darin's avatar
darin committed
571 572 573
        }
    }

574
    thisObject->checkConsistency();
575

barraclough@apple.com's avatar
barraclough@apple.com committed
576
    if (i > MAX_ARRAY_INDEX)
577
        return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, i));
darin's avatar
darin committed
578 579 580 581

    return false;
}

582
void JSArray::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
darin's avatar
darin committed
583
{
584
    JSArray* thisObject = jsCast<JSArray*>(object);
darin's avatar
darin committed
585
    // FIXME: Filling PropertyNameArray with an identifier for every integer
586 587
    // is incredibly inefficient for large arrays. We need a different approach,
    // which almost certainly means a different structure for PropertyNameArray.
darin's avatar
darin committed
588

589
    ArrayStorage* storage = thisObject->m_storage;
590
    
591
    unsigned usedVectorLength = min(storage->m_length, thisObject->m_vectorLength);
darin's avatar
darin committed
592
    for (unsigned i = 0; i < usedVectorLength; ++i) {
593
        if (storage->m_vector[i])
ap@webkit.org's avatar
ap@webkit.org committed
594
            propertyNames.add(Identifier::from(exec, i));
darin's avatar
darin committed
595 596 597 598 599
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
        SparseArrayValueMap::iterator end = map->end();
        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
ap@webkit.org's avatar
ap@webkit.org committed
600
            propertyNames.add(Identifier::from(exec, it->first));
darin's avatar
darin committed
601
    }
602

603 604 605
    if (mode == IncludeDontEnumProperties)
        propertyNames.add(exec->propertyNames().length);

606
    JSObject::getOwnPropertyNames(thisObject, exec, propertyNames, mode);
darin's avatar
darin committed
607 608
}

609 610 611 612 613
ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
{
    ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);

    unsigned increasedLength;
614
    unsigned maxInitLength = min(m_storage->m_length, 100000U);
615

616 617
    if (desiredLength < maxInitLength)
        increasedLength = maxInitLength;
618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635
    else if (!m_vectorLength)
        increasedLength = max(desiredLength, lastArraySize);
    else {
        // Mathematically equivalent to:
        //   increasedLength = (newLength * 3 + 1) / 2;
        // or:
        //   increasedLength = (unsigned)ceil(newLength * 1.5));
        // This form is not prone to internal overflow.
        increasedLength = desiredLength + (desiredLength >> 1) + (desiredLength & 1);
    }

    ASSERT(increasedLength >= desiredLength);

    lastArraySize = min(increasedLength, FIRST_VECTOR_GROW);

    return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
}

darin@apple.com's avatar
darin@apple.com committed
636
bool JSArray::increaseVectorLength(unsigned newLength)
darin's avatar
darin committed
637
{
ap@webkit.org's avatar
ap@webkit.org committed
638 639 640
    // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
    // to the vector. Callers have to account for that, because they can do it more efficiently.

641
    ArrayStorage* storage = m_storage;
darin's avatar
darin committed
642

643
    unsigned vectorLength = m_vectorLength;
darin's avatar
darin committed
644
    ASSERT(newLength > vectorLength);
barraclough@apple.com's avatar
barraclough@apple.com committed
645
    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
646
    unsigned newVectorLength = getNewVectorLength(newLength);
647
    void* baseStorage = storage->m_allocBase;
darin's avatar
darin committed
648

649
    if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage))
ap@webkit.org's avatar
ap@webkit.org committed
650
        return false;
651

652
    storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
653
    m_storage->m_allocBase = baseStorage;
654

655
    WriteBarrier<Unknown>* vector = storage->m_vector;
656
    for (unsigned i = vectorLength; i < newVectorLength; ++i)
657
        vector[i].clear();
ap@webkit.org's avatar
ap@webkit.org committed
658

659
    m_vectorLength = newVectorLength;
660 661
    
    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
darin's avatar
darin committed
662

663 664
    return true;
}
darin's avatar
darin committed
665

666 667 668 669 670
bool JSArray::increaseVectorPrefixLength(unsigned newLength)
{
    // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
    // to the vector. Callers have to account for that, because they can do it more efficiently.
    
671
    ArrayStorage* storage = m_storage;
672 673 674 675 676
    
    unsigned vectorLength = m_vectorLength;
    ASSERT(newLength > vectorLength);
    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
    unsigned newVectorLength = getNewVectorLength(newLength);
677 678

    void* newBaseStorage = fastMalloc(storageSize(newVectorLength + m_indexBias));
679 680 681 682 683
    if (!newBaseStorage)
        return false;
    
    m_indexBias += newVectorLength - newLength;
    
684
    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(newBaseStorage) + m_indexBias * sizeof(JSValue));
685

686 687
    memcpy(m_storage, storage, storageSize(0));
    memcpy(&m_storage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], vectorLength * sizeof(JSValue));
688
    
689
    m_storage->m_allocBase = newBaseStorage;
690 691
    m_vectorLength = newLength;
    
692
    fastFree(storage->m_allocBase);
693 694 695 696
    ASSERT(newLength > vectorLength);
    unsigned delta = newLength - vectorLength;
    for (unsigned i = 0; i < delta; i++)
        m_storage->m_vector[i].clear();
697
    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
698
    
ap@webkit.org's avatar
ap@webkit.org committed
699
    return true;
darin's avatar
darin committed
700
}
701
    
darin's avatar
darin committed
702

darin@apple.com's avatar
darin@apple.com committed
703
void JSArray::setLength(unsigned newLength)
darin's avatar
darin committed
704
{
705 706
    ArrayStorage* storage = m_storage;
    
707
#if CHECK_ARRAY_CONSISTENCY
708
    if (!storage->m_inCompactInitialization)
709 710
        checkConsistency();
    else
711
        storage->m_inCompactInitialization = false;
712
#endif
713

714
    unsigned length = storage->m_length;
darin's avatar
darin committed
715 716

    if (newLength < length) {
717
        unsigned usedVectorLength = min(length, m_vectorLength);
darin's avatar
darin committed
718
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
719
            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
720
            bool hadValue = valueSlot;
721
            valueSlot.clear();
darin's avatar
darin committed
722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737
            storage->m_numValuesInVector -= hadValue;
        }

        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
            SparseArrayValueMap copy = *map;
            SparseArrayValueMap::iterator end = copy.end();
            for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
                if (it->first >= newLength)
                    map->remove(it->first);
            }
            if (map->isEmpty()) {
                delete map;
                storage->m_sparseValueMap = 0;
            }
        }
    }
aroben@apple.com's avatar
aroben@apple.com committed
738

739
    storage->m_length = newLength;
740 741

    checkConsistency();
darin's avatar
darin committed
742 743
}

ggaren@apple.com's avatar
ggaren@apple.com committed
744
JSValue JSArray::pop()
745 746 747
{
    checkConsistency();

748
    ArrayStorage* storage = m_storage;
749 750
    
    unsigned length = storage->m_length;
751 752 753 754 755
    if (!length)
        return jsUndefined();

    --length;

ggaren@apple.com's avatar
ggaren@apple.com committed
756
    JSValue result;
757

758
    if (length < m_vectorLength) {
759
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[length];
760
        if (valueSlot) {
761
            --storage->m_numValuesInVector;
762 763
            result = valueSlot.get();
            valueSlot.clear();
764
        } else
765 766 767
            result = jsUndefined();
    } else {
        result = jsUndefined();
768
        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
769 770
            SparseArrayValueMap::iterator it = map->find(length);
            if (it != map->end()) {
771
                result = it->second.get();
772 773 774
                map->remove(it);
                if (map->isEmpty()) {
                    delete map;
775
                    storage->m_sparseValueMap = 0;
776 777 778 779 780
                }
            }
        }
    }

781
    storage->m_length = length;