JSArray.cpp 48.8 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
// 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:
//
60 61
//   * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector,
//     unless the array is in SparseMode in which case all properties go into the map.
barraclough@apple.com's avatar
barraclough@apple.com committed
62 63 64 65 66 67 68 69 70
//   * 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
71 72 73
// 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
74 75 76 77 78

// 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)
79
// 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
80
#define MAX_ARRAY_INDEX 0xFFFFFFFEU
darin's avatar
darin committed
81

82 83 84 85 86 87 88 89
// 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
90
// Our policy for when to use a vector and when to use a sparse map.
barraclough@apple.com's avatar
barraclough@apple.com committed
91 92
// 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
93 94 95
// as long as it is 1/8 full. If more sparse than that, we use a map.
static const unsigned minDensityMultiplier = 8;

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

98 99 100 101 102
// 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
103 104
static inline size_t storageSize(unsigned vectorLength)
{
barraclough@apple.com's avatar
barraclough@apple.com committed
105 106 107 108
    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
109
    size_t size = (sizeof(ArrayStorage) - sizeof(JSValue)) + (vectorLength * sizeof(JSValue));
barraclough@apple.com's avatar
barraclough@apple.com committed
110 111
    // 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
112
    ASSERT(((size - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValue))));
barraclough@apple.com's avatar
barraclough@apple.com committed
113 114

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

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

122 123
#if !CHECK_ARRAY_CONSISTENCY

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

#endif

130 131
JSArray::JSArray(JSGlobalData& globalData, Structure* structure)
    : JSNonFinalObject(globalData, structure)
weinig@apple.com's avatar
weinig@apple.com committed
132
{
133 134 135 136 137
}

void JSArray::finishCreation(JSGlobalData& globalData)
{
    Base::finishCreation(globalData);
138 139
    ASSERT(inherits(&s_info));

weinig@apple.com's avatar
weinig@apple.com committed
140 141
    unsigned initialCapacity = 0;

142 143
    m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
    m_storage->m_allocBase = m_storage;
144
    m_indexBias = 0;
145
    m_vectorLength = initialCapacity;
weinig@apple.com's avatar
weinig@apple.com committed
146 147

    checkConsistency();
148 149

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

152
void JSArray::finishCreation(JSGlobalData& globalData, unsigned initialLength, ArrayCreationMode creationMode)
darin's avatar
darin committed
153
{
154
    Base::finishCreation(globalData);
155 156
    ASSERT(inherits(&s_info));

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

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

188
    checkConsistency();
189
    
190
    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity));
darin's avatar
darin committed
191 192
}

193
void JSArray::finishCreation(JSGlobalData& globalData, const ArgList& list)
darin's avatar
darin committed
194
{
195
    Base::finishCreation(globalData);
196 197
    ASSERT(inherits(&s_info));

198
    unsigned initialCapacity = list.size();
199 200 201 202 203 204 205 206 207 208
    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)));
209
    m_storage->m_allocBase = m_storage;
210
    m_indexBias = 0;
211
    m_storage->m_length = initialCapacity;
212
    m_vectorLength = initialStorage;
213 214 215
    m_storage->m_numValuesInVector = initialCapacity;
    m_storage->m_sparseValueMap = 0;
    m_storage->subclassData = 0;
216
#if CHECK_ARRAY_CONSISTENCY
217
    m_storage->m_inCompactInitialization = false;
218
#endif
darin's avatar
darin committed
219

ggaren's avatar
ggaren committed
220
    size_t i = 0;
221
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
ggaren@apple.com's avatar
ggaren@apple.com committed
222 223
    for (; i < list.size(); ++i)
        vector[i].set(globalData, this, list.at(i));
224
    for (; i < initialStorage; i++)
225
        vector[i].clear();
darin's avatar
darin committed
226

227
    checkConsistency();
228

229
    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialStorage));
darin's avatar
darin committed
230 231
}

232 233 234 235 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
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;
#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
271
JSArray::~JSArray()
darin's avatar
darin committed
272
{
273
    ASSERT(jsCast<JSArray*>(this));
274 275
    checkConsistency(DestructorConsistencyCheck);

276 277
    delete m_storage->m_sparseValueMap;
    fastFree(m_storage->m_allocBase);
darin's avatar
darin committed
278 279
}

280 281 282 283 284
void JSArray::destroy(JSCell* cell)
{
    jsCast<JSArray*>(cell)->JSArray::~JSArray();
}

285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313
SparseArrayValueMap::iterator SparseArrayValueMap::find(unsigned i)
{
    if (i < MIN_SPARSE_ARRAY_INDEX && !sparseMode())
        return notFound();
    return m_map.find(i);
}

inline void SparseArrayValueMap::put(JSGlobalData& globalData, JSArray* array, unsigned i, JSValue value)
{
    SparseArrayEntry temp;
    pair<Map::iterator, bool> result = m_map.add(i, temp);
    result.first->second.set(globalData, array, value);
    if (!result.second) // pre-existing entry
        return;

    size_t capacity = m_map.capacity();
    if (capacity != m_reportedCapacity) {
        Heap::heap(array)->reportExtraMemoryCost((capacity - m_reportedCapacity) * (sizeof(unsigned) + sizeof(JSValue)));
        m_reportedCapacity = capacity;
    }
}

inline void SparseArrayValueMap::visitChildren(SlotVisitor& visitor)
{
    iterator end = m_map.end();
    for (iterator it = m_map.begin(); it != end; ++it)
        visitor.append(&it->second);
}

314
bool JSArray::getOwnPropertySlotByIndex(JSCell* cell, ExecState* exec, unsigned i, PropertySlot& slot)
315
{
316
    JSArray* thisObject = jsCast<JSArray*>(cell);
317
    ArrayStorage* storage = thisObject->m_storage;
318
    
ggaren@apple.com's avatar
ggaren@apple.com committed
319
    if (i >= storage->m_length) {
barraclough@apple.com's avatar
barraclough@apple.com committed
320
        if (i > MAX_ARRAY_INDEX)
321
            return thisObject->methodTable()->getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
322 323 324
        return false;
    }

325
    if (i < thisObject->m_vectorLength) {
326 327 328
        JSValue value = storage->m_vector[i].get();
        if (value) {
            slot.setValue(value);
darin's avatar
darin committed
329 330 331
            return true;
        }
    } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
332 333 334 335
        SparseArrayValueMap::iterator it = map->find(i);
        if (it != map->notFound()) {
            slot.setValue(it->second.get());
            return true;
darin's avatar
darin committed
336 337 338
        }
    }

339
    return JSObject::getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
340 341
}

342 343
bool JSArray::getOwnPropertySlot(JSCell* cell, ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
{
344
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
345
    if (propertyName == exec->propertyNames().length) {
346
        slot.setValue(jsNumber(thisObject->length()));
darin's avatar
darin committed
347 348 349 350
        return true;
    }

    bool isArrayIndex;
351
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
352
    if (isArrayIndex)
353
        return JSArray::getOwnPropertySlotByIndex(thisObject, exec, i, slot);
darin's avatar
darin committed
354

355
    return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
darin's avatar
darin committed
356 357
}

358
bool JSArray::getOwnPropertyDescriptor(JSObject* object, ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
359
{
360
    JSArray* thisObject = jsCast<JSArray*>(object);
361
    if (propertyName == exec->propertyNames().length) {
362
        descriptor.setDescriptor(jsNumber(thisObject->length()), DontDelete | DontEnum);
363 364
        return true;
    }
365

366
    ArrayStorage* storage = thisObject->m_storage;
367 368
    
    bool isArrayIndex;
369
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
370
    if (isArrayIndex) {
371
        if (i >= storage->m_length)
372
            return false;
373
        if (i < thisObject->m_vectorLength) {
374
            WriteBarrier<Unknown>& value = storage->m_vector[i];
375
            if (value) {
376
                descriptor.setDescriptor(value.get(), 0);
377 378
                return true;
            }
379
        } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
380 381 382 383
            SparseArrayValueMap::iterator it = map->find(i);
            if (it != map->notFound()) {
                descriptor.setDescriptor(it->second.get(), 0);
                return true;
384 385 386
            }
        }
    }
387
    return JSObject::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor);
388 389
}

390 391 392
// ECMA 15.4.5.1
void JSArray::put(JSCell* cell, ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
{
393
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
394
    bool isArrayIndex;
395
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
396
    if (isArrayIndex) {
397
        putByIndex(thisObject, exec, i, value);
darin's avatar
darin committed
398 399 400 401
        return;
    }

    if (propertyName == exec->propertyNames().length) {
weinig@apple.com's avatar
weinig@apple.com committed
402 403
        unsigned newLength = value.toUInt32(exec);
        if (value.toNumber(exec) != static_cast<double>(newLength)) {
404
            throwError(exec, createRangeError(exec, "Invalid array length"));
darin's avatar
darin committed
405 406
            return;
        }
407
        thisObject->setLength(newLength);
darin's avatar
darin committed
408 409 410
        return;
    }

411
    JSObject::put(thisObject, exec, propertyName, value, slot);
darin's avatar
darin committed
412 413
}

414
void JSArray::putByIndex(JSCell* cell, ExecState* exec, unsigned i, JSValue value)
415
{
416
    JSArray* thisObject = jsCast<JSArray*>(cell);
417 418 419
    thisObject->checkConsistency();

    ArrayStorage* storage = thisObject->m_storage;
420 421

    unsigned length = storage->m_length;
barraclough@apple.com's avatar
barraclough@apple.com committed
422
    if (i >= length && i <= MAX_ARRAY_INDEX) {
darin's avatar
darin committed
423
        length = i + 1;
424
        storage->m_length = length;
darin's avatar
darin committed
425 426
    }

427
    if (i < thisObject->m_vectorLength) {
428
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
429
        if (valueSlot) {
430 431
            valueSlot.set(exec->globalData(), thisObject, value);
            thisObject->checkConsistency();
432 433
            return;
        }
434
        valueSlot.set(exec->globalData(), thisObject, value);
435
        ++storage->m_numValuesInVector;
436
        thisObject->checkConsistency();
darin's avatar
darin committed
437 438 439
        return;
    }

440
    thisObject->putSlowCase(exec, i, value);
441 442
}

ggaren@apple.com's avatar
ggaren@apple.com committed
443
NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
444
{
445 446
    ASSERT(i >= m_vectorLength);

447
    ArrayStorage* storage = m_storage;
448
    
darin's avatar
darin committed
449
    SparseArrayValueMap* map = storage->m_sparseValueMap;
ap@webkit.org's avatar
ap@webkit.org committed
450

451 452 453
    if ((map && map->sparseMode())
        || ((i >= MIN_SPARSE_ARRAY_INDEX)
            && ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)))) {
454 455 456
        // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
        // (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
457
        if (i > MAX_ARRAY_INDEX) {
weinig@apple.com's avatar
weinig@apple.com committed
458
            PutPropertySlot slot;
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
459
            methodTable()->put(this, exec, Identifier::from(exec, i), value, slot);
460 461 462
            return;
        }

463 464 465
        if (!map) {
            map = new SparseArrayValueMap;
            storage->m_sparseValueMap = map;
darin's avatar
darin committed
466
        }
467 468 469

        map->put(exec->globalData(), this, i, value);
        return;
darin's avatar
darin committed
470 471
    }

ap@webkit.org's avatar
ap@webkit.org committed
472 473 474
    // 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
475
        if (increaseVectorLength(i + 1)) {
476
            storage = m_storage;
477
            storage->m_vector[i].set(exec->globalData(), this, value);
478
            ++storage->m_numValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
479 480 481
            checkConsistency();
        } else
            throwOutOfMemoryError(exec);
darin's avatar
darin committed
482 483 484
        return;
    }

ap@webkit.org's avatar
ap@webkit.org committed
485 486
    // Decide how many values it would be best to move from the map.
    unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
487
    unsigned newVectorLength = getNewVectorLength(i + 1);
488
    for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
darin's avatar
darin committed
489
        newNumValuesInVector += map->contains(j);
barraclough@apple.com's avatar
barraclough@apple.com committed
490
    if (i >= MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
491
        newNumValuesInVector -= map->contains(i);
darin's avatar
darin committed
492
    if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
493
        unsigned needLength = max(i + 1, storage->m_length);
darin's avatar
darin committed
494
        unsigned proposedNewNumValuesInVector = newNumValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
495
        // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
496
        while ((newVectorLength < needLength) && (newVectorLength < MAX_STORAGE_VECTOR_LENGTH)) {
497
            unsigned proposedNewVectorLength = getNewVectorLength(newVectorLength + 1);
barraclough@apple.com's avatar
barraclough@apple.com committed
498
            for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
darin's avatar
darin committed
499 500 501 502 503 504 505 506
                proposedNewNumValuesInVector += map->contains(j);
            if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
                break;
            newVectorLength = proposedNewVectorLength;
            newNumValuesInVector = proposedNewNumValuesInVector;
        }
    }

507
    void* baseStorage = storage->m_allocBase;
508 509
    
    if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) {
barraclough@apple.com's avatar
barraclough@apple.com committed
510 511 512
        throwOutOfMemoryError(exec);
        return;
    }
darin's avatar
darin committed
513

514
    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
515 516
    m_storage->m_allocBase = baseStorage;
    storage = m_storage;
517
    
518
    unsigned vectorLength = m_vectorLength;
519
    WriteBarrier<Unknown>* vector = storage->m_vector;
520

darin's avatar
darin committed
521 522
    if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
        for (unsigned j = vectorLength; j < newVectorLength; ++j)
523
            vector[j].clear();
barraclough@apple.com's avatar
barraclough@apple.com committed
524
        if (i > MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
525
            map->remove(i);
darin's avatar
darin committed
526
    } else {
barraclough@apple.com's avatar
barraclough@apple.com committed
527
        for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
528 529
            vector[j].clear();
        JSGlobalData& globalData = exec->globalData();
barraclough@apple.com's avatar
barraclough@apple.com committed
530
        for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
531
            vector[j].set(globalData, this, map->take(j));
darin's avatar
darin committed
532 533
    }

534
    ASSERT(i < newVectorLength);
darin's avatar
darin committed
535

536
    m_vectorLength = newVectorLength;
darin's avatar
darin committed
537
    storage->m_numValuesInVector = newNumValuesInVector;
ap@webkit.org's avatar
ap@webkit.org committed
538

539
    storage->m_vector[i].set(exec->globalData(), this, value);
540 541

    checkConsistency();
542 543

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

546 547
bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, const Identifier& propertyName)
{
548
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
549
    bool isArrayIndex;
550
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
551
    if (isArrayIndex)
552
        return thisObject->methodTable()->deletePropertyByIndex(thisObject, exec, i);
darin's avatar
darin committed
553 554 555 556

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

557
    return JSObject::deleteProperty(thisObject, exec, propertyName);
darin's avatar
darin committed
558 559
}

560
bool JSArray::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
561
{
562
    JSArray* thisObject = jsCast<JSArray*>(cell);
563 564 565
    thisObject->checkConsistency();

    ArrayStorage* storage = thisObject->m_storage;
566
    
567
    if (i < thisObject->m_vectorLength) {
568
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
569
        if (!valueSlot) {
570
            thisObject->checkConsistency();
571 572
            return false;
        }
573
        valueSlot.clear();
574
        --storage->m_numValuesInVector;
575
        thisObject->checkConsistency();
576
        return true;
darin's avatar
darin committed
577 578 579
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
580 581 582 583 584
        SparseArrayValueMap::iterator it = map->find(i);
        if (it != map->notFound()) {
            map->remove(it);
            thisObject->checkConsistency();
            return true;
darin's avatar
darin committed
585 586 587
        }
    }

588
    thisObject->checkConsistency();
589

barraclough@apple.com's avatar
barraclough@apple.com committed
590
    if (i > MAX_ARRAY_INDEX)
591
        return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, i));
darin's avatar
darin committed
592 593 594 595

    return false;
}

596
void JSArray::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
darin's avatar
darin committed
597
{
598
    JSArray* thisObject = jsCast<JSArray*>(object);
darin's avatar
darin committed
599
    // FIXME: Filling PropertyNameArray with an identifier for every integer
600 601
    // 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
602

603
    ArrayStorage* storage = thisObject->m_storage;
604
    
605
    unsigned usedVectorLength = min(storage->m_length, thisObject->m_vectorLength);
darin's avatar
darin committed
606
    for (unsigned i = 0; i < usedVectorLength; ++i) {
607
        if (storage->m_vector[i])
ap@webkit.org's avatar
ap@webkit.org committed
608
            propertyNames.add(Identifier::from(exec, i));
darin's avatar
darin committed
609 610 611
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
612 613
        SparseArrayValueMap::const_iterator end = map->end();
        for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
ap@webkit.org's avatar
ap@webkit.org committed
614
            propertyNames.add(Identifier::from(exec, it->first));
darin's avatar
darin committed
615
    }
616

617 618 619
    if (mode == IncludeDontEnumProperties)
        propertyNames.add(exec->propertyNames().length);

620
    JSObject::getOwnPropertyNames(thisObject, exec, propertyNames, mode);
darin's avatar
darin committed
621 622
}

623 624 625 626 627
ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
{
    ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);

    unsigned increasedLength;
628
    unsigned maxInitLength = min(m_storage->m_length, 100000U);
629

630 631
    if (desiredLength < maxInitLength)
        increasedLength = maxInitLength;
632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649
    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
650
bool JSArray::increaseVectorLength(unsigned newLength)
darin's avatar
darin committed
651
{
ap@webkit.org's avatar
ap@webkit.org committed
652 653 654
    // 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.

655
    ArrayStorage* storage = m_storage;
darin's avatar
darin committed
656

657
    unsigned vectorLength = m_vectorLength;
darin's avatar
darin committed
658
    ASSERT(newLength > vectorLength);
barraclough@apple.com's avatar
barraclough@apple.com committed
659
    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
660
    unsigned newVectorLength = getNewVectorLength(newLength);
661
    void* baseStorage = storage->m_allocBase;
darin's avatar
darin committed
662

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

666
    storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
667
    m_storage->m_allocBase = baseStorage;
668

669
    WriteBarrier<Unknown>* vector = storage->m_vector;
670
    for (unsigned i = vectorLength; i < newVectorLength; ++i)
671
        vector[i].clear();
ap@webkit.org's avatar
ap@webkit.org committed
672

673
    m_vectorLength = newVectorLength;
674 675
    
    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
darin's avatar
darin committed
676

677 678
    return true;
}
darin's avatar
darin committed
679

680 681 682 683 684
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.
    
685
    ArrayStorage* storage = m_storage;
686 687 688 689 690
    
    unsigned vectorLength = m_vectorLength;
    ASSERT(newLength > vectorLength);
    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
    unsigned newVectorLength = getNewVectorLength(newLength);
691 692

    void* newBaseStorage = fastMalloc(storageSize(newVectorLength + m_indexBias));
693 694 695 696 697
    if (!newBaseStorage)
        return false;
    
    m_indexBias += newVectorLength - newLength;
    
698
    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(newBaseStorage) + m_indexBias * sizeof(JSValue));
699

700 701
    memcpy(m_storage, storage, storageSize(0));
    memcpy(&m_storage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], vectorLength * sizeof(JSValue));
702
    
703
    m_storage->m_allocBase = newBaseStorage;
704 705
    m_vectorLength = newLength;
    
706
    fastFree(storage->m_allocBase);
707 708 709 710
    ASSERT(newLength > vectorLength);
    unsigned delta = newLength - vectorLength;
    for (unsigned i = 0; i < delta; i++)
        m_storage->m_vector[i].clear();
711
    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
712
    
ap@webkit.org's avatar
ap@webkit.org committed
713
    return true;
darin's avatar
darin committed
714
}
715
    
darin's avatar
darin committed
716

darin@apple.com's avatar
darin@apple.com committed
717
void JSArray::setLength(unsigned newLength)
darin's avatar
darin committed
718
{
719 720
    ArrayStorage* storage = m_storage;
    
721
#if CHECK_ARRAY_CONSISTENCY
722
    if (!storage->m_inCompactInitialization)
723 724
        checkConsistency();
    else
725
        storage->m_inCompactInitialization = false;
726
#endif
727

728
    unsigned length = storage->m_length;
darin's avatar
darin committed
729 730

    if (newLength < length) {
731
        unsigned usedVectorLength = min(length, m_vectorLength);
darin's avatar
darin committed
732
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
733
            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
734
            bool hadValue = valueSlot;
735
            valueSlot.clear();
darin's avatar
darin committed
736 737 738 739 740
            storage->m_numValuesInVector -= hadValue;
        }

        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
            SparseArrayValueMap copy = *map;
741 742
            SparseArrayValueMap::const_iterator end = copy.end();
            for (SparseArrayValueMap::const_iterator it = copy.begin(); it != end; ++it) {
darin's avatar
darin committed
743 744 745
                if (it->first >= newLength)
                    map->remove(it->first);
            }
746
            if (map->isEmpty() && !map->sparseMode()) {
darin's avatar
darin committed
747 748 749 750 751
                delete map;
                storage->m_sparseValueMap = 0;
            }
        }
    }
aroben@apple.com's avatar
aroben@apple.com committed
752

753
    storage->m_length = newLength;
754 755

    checkConsistency();
darin's avatar
darin committed
756 757
}

ggaren@apple.com's avatar
ggaren@apple.com committed
758
JSValue JSArray::pop()
759 760 761
{
    checkConsistency();

762
    ArrayStorage* storage = m_storage;
763 764
    
    unsigned length = storage->m_length;
765 766 767 768 769
    if (!length)
        return jsUndefined();

    --length;

ggaren@apple.com's avatar
ggaren@apple.com committed
770
    JSValue result;
771

772
    if (length < m_vectorLength) {
773
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[length];
774
        if (valueSlot) {
775
            --storage->m_numValuesInVector;
776 777
            result = valueSlot.get();
            valueSlot.clear();
778
        } else
779 780 781
            result = jsUndefined();
    } else {
        result = jsUndefined();
782
        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
783 784
            SparseArrayValueMap::iterator it = map->find(length);
            if (it != map->end()) {
785
                result = it->second.get();
786
                map->remove(it);
787
                if (map->isEmpty() && !map->sparseMode()) {
788
                    delete map;
789
                    storage->m_sparseValueMap = 0;
790