JSArray.cpp 46.7 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)
132
    , m_storage(0)
weinig@apple.com's avatar
weinig@apple.com committed
133
{
134 135
}

136
void JSArray::finishCreation(JSGlobalData& globalData, unsigned initialLength)
137 138
{
    Base::finishCreation(globalData);
139 140
    ASSERT(inherits(&s_info));

141 142
    unsigned initialVectorLength = BASE_VECTOR_LEN;
    unsigned initialStorageSize = storageSize(initialVectorLength);
weinig@apple.com's avatar
weinig@apple.com committed
143

144
    m_storage = static_cast<ArrayStorage*>(fastMalloc(initialStorageSize));
145
    m_storage->m_allocBase = m_storage;
146
    m_storage->m_length = initialLength;
147
    m_indexBias = 0;
148 149 150 151 152 153 154
    m_vectorLength = initialVectorLength;
    m_storage->m_sparseValueMap = 0;
    m_storage->subclassData = 0;
    m_storage->m_numValuesInVector = 0;
#if CHECK_ARRAY_CONSISTENCY
    m_storage->m_inCompactInitialization = false;
#endif
weinig@apple.com's avatar
weinig@apple.com committed
155

156 157 158
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
    for (size_t i = 0; i < initialVectorLength; ++i)
        vector[i].clear();
159

160 161 162
    checkConsistency();
    
    Heap::heap(this)->reportExtraMemoryCost(initialStorageSize);
weinig@apple.com's avatar
weinig@apple.com committed
163 164
}

165
JSArray* JSArray::tryFinishCreationUninitialized(JSGlobalData& globalData, unsigned initialLength)
darin's avatar
darin committed
166
{
167
    Base::finishCreation(globalData);
168 169
    ASSERT(inherits(&s_info));

170 171 172 173 174 175 176 177
    // Check for lengths larger than we can handle with a vector.
    if (initialLength > MAX_STORAGE_VECTOR_LENGTH)
        return 0;

    unsigned initialVectorLength = max(initialLength, BASE_VECTOR_LEN);
    unsigned initialStorageSize = storageSize(initialVectorLength);

    m_storage = static_cast<ArrayStorage*>(fastMalloc(initialStorageSize));
178
    m_storage->m_allocBase = m_storage;
179
    m_storage->m_length = 0;
180
    m_indexBias = 0;
181
    m_vectorLength = initialVectorLength;
182 183
    m_storage->m_sparseValueMap = 0;
    m_storage->subclassData = 0;
184
    m_storage->m_numValuesInVector = initialLength;
185
#if CHECK_ARRAY_CONSISTENCY
186
    m_storage->m_inCompactInitialization = true;
187
#endif
188

189 190 191 192 193 194
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
    for (size_t i = initialLength; i < initialVectorLength; ++i)
        vector[i].clear();

    Heap::heap(this)->reportExtraMemoryCost(initialStorageSize);
    return this;
darin's avatar
darin committed
195 196
}

darin@apple.com's avatar
darin@apple.com committed
197
JSArray::~JSArray()
darin's avatar
darin committed
198
{
199
    ASSERT(jsCast<JSArray*>(this));
200

201 202 203 204 205
    // If we are unable to allocate memory for m_storage then this may be null.
    if (!m_storage)
        return;

    checkConsistency(DestructorConsistencyCheck);
206 207
    delete m_storage->m_sparseValueMap;
    fastFree(m_storage->m_allocBase);
darin's avatar
darin committed
208 209
}

210 211 212 213 214
void JSArray::destroy(JSCell* cell)
{
    jsCast<JSArray*>(cell)->JSArray::~JSArray();
}

215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243
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);
}

244
bool JSArray::getOwnPropertySlotByIndex(JSCell* cell, ExecState* exec, unsigned i, PropertySlot& slot)
245
{
246
    JSArray* thisObject = jsCast<JSArray*>(cell);
247
    ArrayStorage* storage = thisObject->m_storage;
248
    
ggaren@apple.com's avatar
ggaren@apple.com committed
249
    if (i >= storage->m_length) {
barraclough@apple.com's avatar
barraclough@apple.com committed
250
        if (i > MAX_ARRAY_INDEX)
251
            return thisObject->methodTable()->getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
252 253 254
        return false;
    }

255
    if (i < thisObject->m_vectorLength) {
256 257 258
        JSValue value = storage->m_vector[i].get();
        if (value) {
            slot.setValue(value);
darin's avatar
darin committed
259 260 261
            return true;
        }
    } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
262 263 264 265
        SparseArrayValueMap::iterator it = map->find(i);
        if (it != map->notFound()) {
            slot.setValue(it->second.get());
            return true;
darin's avatar
darin committed
266 267 268
        }
    }

269
    return JSObject::getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
270 271
}

272 273
bool JSArray::getOwnPropertySlot(JSCell* cell, ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
{
274
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
275
    if (propertyName == exec->propertyNames().length) {
276
        slot.setValue(jsNumber(thisObject->length()));
darin's avatar
darin committed
277 278 279 280
        return true;
    }

    bool isArrayIndex;
281
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
282
    if (isArrayIndex)
283
        return JSArray::getOwnPropertySlotByIndex(thisObject, exec, i, slot);
darin's avatar
darin committed
284

285
    return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
darin's avatar
darin committed
286 287
}

288
bool JSArray::getOwnPropertyDescriptor(JSObject* object, ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
289
{
290
    JSArray* thisObject = jsCast<JSArray*>(object);
291
    if (propertyName == exec->propertyNames().length) {
292
        descriptor.setDescriptor(jsNumber(thisObject->length()), DontDelete | DontEnum);
293 294
        return true;
    }
295

296
    ArrayStorage* storage = thisObject->m_storage;
297 298
    
    bool isArrayIndex;
299
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
300
    if (isArrayIndex) {
301
        if (i >= storage->m_length)
302
            return false;
303
        if (i < thisObject->m_vectorLength) {
304
            WriteBarrier<Unknown>& value = storage->m_vector[i];
305
            if (value) {
306
                descriptor.setDescriptor(value.get(), 0);
307 308
                return true;
            }
309
        } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
310 311 312 313
            SparseArrayValueMap::iterator it = map->find(i);
            if (it != map->notFound()) {
                descriptor.setDescriptor(it->second.get(), 0);
                return true;
314 315 316
            }
        }
    }
317
    return JSObject::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor);
318 319
}

320 321 322
// ECMA 15.4.5.1
void JSArray::put(JSCell* cell, ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
{
323
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
324
    bool isArrayIndex;
325
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
326
    if (isArrayIndex) {
327
        putByIndex(thisObject, exec, i, value);
darin's avatar
darin committed
328 329 330 331
        return;
    }

    if (propertyName == exec->propertyNames().length) {
weinig@apple.com's avatar
weinig@apple.com committed
332 333
        unsigned newLength = value.toUInt32(exec);
        if (value.toNumber(exec) != static_cast<double>(newLength)) {
334
            throwError(exec, createRangeError(exec, "Invalid array length"));
darin's avatar
darin committed
335 336
            return;
        }
337
        thisObject->setLength(newLength);
darin's avatar
darin committed
338 339 340
        return;
    }

341
    JSObject::put(thisObject, exec, propertyName, value, slot);
darin's avatar
darin committed
342 343
}

344
void JSArray::putByIndex(JSCell* cell, ExecState* exec, unsigned i, JSValue value)
345
{
346
    JSArray* thisObject = jsCast<JSArray*>(cell);
347 348 349
    thisObject->checkConsistency();

    ArrayStorage* storage = thisObject->m_storage;
350 351

    unsigned length = storage->m_length;
barraclough@apple.com's avatar
barraclough@apple.com committed
352
    if (i >= length && i <= MAX_ARRAY_INDEX) {
darin's avatar
darin committed
353
        length = i + 1;
354
        storage->m_length = length;
darin's avatar
darin committed
355 356
    }

357
    if (i < thisObject->m_vectorLength) {
358
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
359
        if (valueSlot) {
360 361
            valueSlot.set(exec->globalData(), thisObject, value);
            thisObject->checkConsistency();
362 363
            return;
        }
364
        valueSlot.set(exec->globalData(), thisObject, value);
365
        ++storage->m_numValuesInVector;
366
        thisObject->checkConsistency();
darin's avatar
darin committed
367 368 369
        return;
    }

370
    thisObject->putSlowCase(exec, i, value);
371 372
}

ggaren@apple.com's avatar
ggaren@apple.com committed
373
NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
374
{
375 376
    ASSERT(i >= m_vectorLength);

377
    ArrayStorage* storage = m_storage;
378
    
darin's avatar
darin committed
379
    SparseArrayValueMap* map = storage->m_sparseValueMap;
ap@webkit.org's avatar
ap@webkit.org committed
380

381 382 383
    if ((map && map->sparseMode())
        || ((i >= MIN_SPARSE_ARRAY_INDEX)
            && ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)))) {
384 385 386
        // 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
387
        if (i > MAX_ARRAY_INDEX) {
weinig@apple.com's avatar
weinig@apple.com committed
388
            PutPropertySlot slot;
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
389
            methodTable()->put(this, exec, Identifier::from(exec, i), value, slot);
390 391 392
            return;
        }

393 394 395
        if (!map) {
            map = new SparseArrayValueMap;
            storage->m_sparseValueMap = map;
darin's avatar
darin committed
396
        }
397 398 399

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

ap@webkit.org's avatar
ap@webkit.org committed
402 403 404
    // 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
405
        if (increaseVectorLength(i + 1)) {
406
            storage = m_storage;
407
            storage->m_vector[i].set(exec->globalData(), this, value);
408
            ++storage->m_numValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
409 410 411
            checkConsistency();
        } else
            throwOutOfMemoryError(exec);
darin's avatar
darin committed
412 413 414
        return;
    }

ap@webkit.org's avatar
ap@webkit.org committed
415 416
    // Decide how many values it would be best to move from the map.
    unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
417
    unsigned newVectorLength = getNewVectorLength(i + 1);
418
    for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
darin's avatar
darin committed
419
        newNumValuesInVector += map->contains(j);
barraclough@apple.com's avatar
barraclough@apple.com committed
420
    if (i >= MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
421
        newNumValuesInVector -= map->contains(i);
darin's avatar
darin committed
422
    if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
423
        unsigned needLength = max(i + 1, storage->m_length);
darin's avatar
darin committed
424
        unsigned proposedNewNumValuesInVector = newNumValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
425
        // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
426
        while ((newVectorLength < needLength) && (newVectorLength < MAX_STORAGE_VECTOR_LENGTH)) {
427
            unsigned proposedNewVectorLength = getNewVectorLength(newVectorLength + 1);
barraclough@apple.com's avatar
barraclough@apple.com committed
428
            for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
darin's avatar
darin committed
429 430 431 432 433 434 435 436
                proposedNewNumValuesInVector += map->contains(j);
            if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
                break;
            newVectorLength = proposedNewVectorLength;
            newNumValuesInVector = proposedNewNumValuesInVector;
        }
    }

437
    void* baseStorage = storage->m_allocBase;
438 439
    
    if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) {
barraclough@apple.com's avatar
barraclough@apple.com committed
440 441 442
        throwOutOfMemoryError(exec);
        return;
    }
darin's avatar
darin committed
443

444
    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
445 446
    m_storage->m_allocBase = baseStorage;
    storage = m_storage;
447
    
448
    unsigned vectorLength = m_vectorLength;
449
    WriteBarrier<Unknown>* vector = storage->m_vector;
450

darin's avatar
darin committed
451 452
    if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
        for (unsigned j = vectorLength; j < newVectorLength; ++j)
453
            vector[j].clear();
barraclough@apple.com's avatar
barraclough@apple.com committed
454
        if (i > MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
455
            map->remove(i);
darin's avatar
darin committed
456
    } else {
barraclough@apple.com's avatar
barraclough@apple.com committed
457
        for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
458 459
            vector[j].clear();
        JSGlobalData& globalData = exec->globalData();
barraclough@apple.com's avatar
barraclough@apple.com committed
460
        for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
461
            vector[j].set(globalData, this, map->take(j));
darin's avatar
darin committed
462 463
    }

464
    ASSERT(i < newVectorLength);
darin's avatar
darin committed
465

466
    m_vectorLength = newVectorLength;
darin's avatar
darin committed
467
    storage->m_numValuesInVector = newNumValuesInVector;
ap@webkit.org's avatar
ap@webkit.org committed
468

469
    storage->m_vector[i].set(exec->globalData(), this, value);
470 471

    checkConsistency();
472 473

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

476 477
bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, const Identifier& propertyName)
{
478
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
479
    bool isArrayIndex;
480
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
481
    if (isArrayIndex)
482
        return thisObject->methodTable()->deletePropertyByIndex(thisObject, exec, i);
darin's avatar
darin committed
483 484 485 486

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

487
    return JSObject::deleteProperty(thisObject, exec, propertyName);
darin's avatar
darin committed
488 489
}

490
bool JSArray::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
491
{
492
    JSArray* thisObject = jsCast<JSArray*>(cell);
493 494 495
    thisObject->checkConsistency();

    ArrayStorage* storage = thisObject->m_storage;
496
    
497
    if (i < thisObject->m_vectorLength) {
498
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
499
        if (!valueSlot) {
500
            thisObject->checkConsistency();
501 502
            return false;
        }
503
        valueSlot.clear();
504
        --storage->m_numValuesInVector;
505
        thisObject->checkConsistency();
506
        return true;
darin's avatar
darin committed
507 508 509
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
510 511 512 513 514
        SparseArrayValueMap::iterator it = map->find(i);
        if (it != map->notFound()) {
            map->remove(it);
            thisObject->checkConsistency();
            return true;
darin's avatar
darin committed
515 516 517
        }
    }

518
    thisObject->checkConsistency();
519

barraclough@apple.com's avatar
barraclough@apple.com committed
520
    if (i > MAX_ARRAY_INDEX)
521
        return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, i));
darin's avatar
darin committed
522 523 524 525

    return false;
}

526
void JSArray::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
darin's avatar
darin committed
527
{
528
    JSArray* thisObject = jsCast<JSArray*>(object);
darin's avatar
darin committed
529
    // FIXME: Filling PropertyNameArray with an identifier for every integer
530 531
    // 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
532

533
    ArrayStorage* storage = thisObject->m_storage;
534
    
535
    unsigned usedVectorLength = min(storage->m_length, thisObject->m_vectorLength);
darin's avatar
darin committed
536
    for (unsigned i = 0; i < usedVectorLength; ++i) {
537
        if (storage->m_vector[i])
ap@webkit.org's avatar
ap@webkit.org committed
538
            propertyNames.add(Identifier::from(exec, i));
darin's avatar
darin committed
539 540 541
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
542 543
        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
544
            propertyNames.add(Identifier::from(exec, it->first));
darin's avatar
darin committed
545
    }
546

547 548 549
    if (mode == IncludeDontEnumProperties)
        propertyNames.add(exec->propertyNames().length);

550
    JSObject::getOwnPropertyNames(thisObject, exec, propertyNames, mode);
darin's avatar
darin committed
551 552
}

553 554 555 556 557
ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
{
    ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);

    unsigned increasedLength;
558
    unsigned maxInitLength = min(m_storage->m_length, 100000U);
559

560 561
    if (desiredLength < maxInitLength)
        increasedLength = maxInitLength;
562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579
    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
580
bool JSArray::increaseVectorLength(unsigned newLength)
darin's avatar
darin committed
581
{
ap@webkit.org's avatar
ap@webkit.org committed
582 583 584
    // 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.

585
    ArrayStorage* storage = m_storage;
darin's avatar
darin committed
586

587
    unsigned vectorLength = m_vectorLength;
darin's avatar
darin committed
588
    ASSERT(newLength > vectorLength);
barraclough@apple.com's avatar
barraclough@apple.com committed
589
    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
590
    unsigned newVectorLength = getNewVectorLength(newLength);
591
    void* baseStorage = storage->m_allocBase;
darin's avatar
darin committed
592

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

596
    storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
597
    m_storage->m_allocBase = baseStorage;
598

599
    WriteBarrier<Unknown>* vector = storage->m_vector;
600
    for (unsigned i = vectorLength; i < newVectorLength; ++i)
601
        vector[i].clear();
ap@webkit.org's avatar
ap@webkit.org committed
602

603
    m_vectorLength = newVectorLength;
604 605
    
    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
darin's avatar
darin committed
606

607 608
    return true;
}
darin's avatar
darin committed
609

610 611 612 613 614
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.
    
615
    ArrayStorage* storage = m_storage;
616 617 618 619 620
    
    unsigned vectorLength = m_vectorLength;
    ASSERT(newLength > vectorLength);
    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
    unsigned newVectorLength = getNewVectorLength(newLength);
621 622

    void* newBaseStorage = fastMalloc(storageSize(newVectorLength + m_indexBias));
623 624 625 626 627
    if (!newBaseStorage)
        return false;
    
    m_indexBias += newVectorLength - newLength;
    
628
    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(newBaseStorage) + m_indexBias * sizeof(JSValue));
629

630 631
    memcpy(m_storage, storage, storageSize(0));
    memcpy(&m_storage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], vectorLength * sizeof(JSValue));
632
    
633
    m_storage->m_allocBase = newBaseStorage;
634 635
    m_vectorLength = newLength;
    
636
    fastFree(storage->m_allocBase);
637 638 639 640
    ASSERT(newLength > vectorLength);
    unsigned delta = newLength - vectorLength;
    for (unsigned i = 0; i < delta; i++)
        m_storage->m_vector[i].clear();
641
    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
642
    
ap@webkit.org's avatar
ap@webkit.org committed
643
    return true;
darin's avatar
darin committed
644 645
}

darin@apple.com's avatar
darin@apple.com committed
646
void JSArray::setLength(unsigned newLength)
darin's avatar
darin committed
647
{
648 649
    checkConsistency();

650 651
    ArrayStorage* storage = m_storage;
    
652
    unsigned length = storage->m_length;
darin's avatar
darin committed
653 654

    if (newLength < length) {
655
        unsigned usedVectorLength = min(length, m_vectorLength);
darin's avatar
darin committed
656
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
657
            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
658
            bool hadValue = valueSlot;
659
            valueSlot.clear();
darin's avatar
darin committed
660 661 662 663 664
            storage->m_numValuesInVector -= hadValue;
        }

        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
            SparseArrayValueMap copy = *map;
665 666
            SparseArrayValueMap::const_iterator end = copy.end();
            for (SparseArrayValueMap::const_iterator it = copy.begin(); it != end; ++it) {
darin's avatar
darin committed
667 668 669
                if (it->first >= newLength)
                    map->remove(it->first);
            }
670
            if (map->isEmpty() && !map->sparseMode()) {
darin's avatar
darin committed
671 672 673 674 675
                delete map;
                storage->m_sparseValueMap = 0;
            }
        }
    }
aroben@apple.com's avatar
aroben@apple.com committed
676

677
    storage->m_length = newLength;
678 679

    checkConsistency();
darin's avatar
darin committed
680 681
}

ggaren@apple.com's avatar
ggaren@apple.com committed
682
JSValue JSArray::pop()
683 684 685
{
    checkConsistency();

686
    ArrayStorage* storage = m_storage;
687 688
    
    unsigned length = storage->m_length;
689 690 691 692 693
    if (!length)
        return jsUndefined();

    --length;

ggaren@apple.com's avatar
ggaren@apple.com committed
694
    JSValue result;
695

696
    if (length < m_vectorLength) {
697
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[length];
698
        if (valueSlot) {
699
            --storage->m_numValuesInVector;
700 701
            result = valueSlot.get();
            valueSlot.clear();
702
        } else
703 704 705
            result = jsUndefined();
    } else {
        result = jsUndefined();
706
        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
707 708
            SparseArrayValueMap::iterator it = map->find(length);
            if (it != map->end()) {
709
                result = it->second.get();
710
                map->remove(it);
711
                if (map->isEmpty() && !map->sparseMode()) {
712
                    delete map;
713
                    storage->m_sparseValueMap = 0;
714 715 716 717 718
                }
            }
        }
    }

719
    storage->m_length = length;
720 721 722 723 724 725

    checkConsistency();

    return result;
}

ggaren@apple.com's avatar
ggaren@apple.com committed
726
void JSArray::push(ExecState* exec, JSValue value)
727 728
{
    checkConsistency();
729
    
730
    ArrayStorage* storage = m_storage;
731

732
    if (UNLIKELY(storage->m_length == 0xFFFFFFFFu)) {
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
733
        methodTable()->putByIndex(this, exec, storage->m_length, value);
734 735 736 737
        throwError(exec, createRangeError(exec, "Invalid array length"));
        return;
    }

738
    if (storage->m_length < m_vectorLength) {
739
        storage->m_vector[storage->m_length].set(exec->globalData(), this, value);
740 741
        ++storage->m_numValuesInVector;
        ++storage->m_length;
742 743 744 745
        checkConsistency();
        return;
    }

746 747
    if (storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
        SparseArrayValueMap* map = storage->m_sparseValueMap;
748
        if (!map || map->isEmpty()) {
749
            if (increaseVectorLength(storage->m_length + 1)) {
750
                storage = m_storage;
751
                storage->m_vector[storage->m_length].set(exec->globalData(), this, value);
752 753
                ++storage->m_numValuesInVector;
                ++storage->m_length;
754 755 756 757 758 759 760 761 762
                checkConsistency();
                return;
            }
            checkConsistency();
            throwOutOfMemoryError(exec);
            return;
        }
    }

763 764 765 766 767 768 769
    putSlowCase(exec, storage->m_length++, value);
}

void JSArray::shiftCount(ExecState* exec, int count)
{
    ASSERT(count > 0);
    
770
    ArrayStorage* storage = m_storage;
771 772 773 774 775 776 777 778 779 780 781 782
    
    unsigned oldLength = storage->m_length;
    
    if (!oldLength)
        return;
    
    if (oldLength != storage->m_numValuesInVector) {
        // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
        // which means we need to go through each entry looking for the the "empty"
        // slots and then fill them with possible properties.  See ECMA spec.
        // 15.4.4.9 steps 11 through 13.
        for (unsigned i = count; i < oldLength; ++i) {
783
            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
784 785 786
                PropertySlot slot(this);
                JSValue p = prototype();
                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
787
                    methodTable()->putByIndex(this, exec, i, slot.getValue(exec, i));
788 789 790
            }
        }

791
        storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
792 793 794

        // Need to decrement numValuesInvector based on number of real entries
        for (unsigned i = 0; i < (unsigned)count; ++i)
795
            if ((i < m_vectorLength) && (storage->m_vector[i]))
796 797 798 799 800 801 802 803 804 805 806 807 808 809
                --storage->m_numValuesInVector;
    } else
        storage->m_numValuesInVector -= count;
    
    storage->m_length -= count;
    
    if (m_vectorLength) {
        count = min(m_vectorLength, (unsigned)count);
        
        m_vectorLength -= count;
        
        if (m_vectorLength) {
            char* newBaseStorage = reinterpret_cast<char*>(storage) + count * sizeof(JSValue);
            memmove(newBaseStorage, storage, storageSize(0));
810
            m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
811 812 813 814 815 816 817 818

            m_indexBias += count;
        }
    }
}
    
void JSArray::unshiftCount(ExecState* exec, int count)
{
819
    ArrayStorage* storage = m_storage;
820 821 822 823 824 825 826 827 828 829 830 831

    ASSERT(m_indexBias >= 0);
    ASSERT(count >= 0);
    
    unsigned length = storage->m_length;
    
    if (length != storage->m_numValuesInVector) {
        // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
        // which means we need to go through each entry looking for the the "empty"
        // slots and then fill them with possible properties.  See ECMA spec.
        // 15.4.4.13 steps 8 through 10.
        for (unsigned i = 0; i < length; ++i) {
832
            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
833 834 835
                PropertySlot slot(this);
                JSValue p = prototype();
                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
836
                    methodTable()->putByIndex(this, exec, i, slot.getValue(exec, i));
837 838 839 840
            }
        }
    }
    
841
    storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
842 843 844 845 846
    
    if (m_indexBias >= count) {
        m_indexBias -= count;
        char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(JSValue);
        memmove(newBaseStorage, storage, storageSize(0));
847
        m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
848
        m_vectorLength += count;
849
    } else if (!increaseVectorPrefixLength(m_vectorLength + count)) {
850 851 852
        throwOutOfMemoryError(exec);
        return;
    }
853

854
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
855
    for (int i = 0; i < count; i++)
856
        vector[i].clear();
857 858
}

859 860
void JSArray::visitChildren(JSCell* cell, SlotVisitor& visitor)
{
861
    JSArray* thisObject = jsCast<JSArray*>(cell);
862
    ASSERT_GC_OBJECT_INHERITS(thisObject, &s_info);
863
    COMPILE_ASSERT(StructureFlags & OverridesVisitChildren, OverridesVisitChildrenWithoutSettingFlag);
864
    ASSERT(thisObject->structure()->typeInfo().overridesVisitChildren());
ggaren@apple.com's avatar
ggaren@apple.com committed
865 866 867 868 869 870 871 872

    JSNonFinalObject::visitChildren(thisObject, visitor);
    
    ArrayStorage* storage = thisObject->m_storage;

    unsigned usedVectorLength = std::min(storage->m_length, thisObject->m_vectorLength);
    visitor.appendValues(storage->m_vector, usedVectorLength);

873 874
    if (SparseArrayValueMap* map = storage->m_sparseValueMap)
        map->visitChildren(visitor);
darin's avatar
darin committed
875 876
}

ggaren@apple.com's avatar
ggaren@apple.com committed
877 878
static int compareNumbersForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
879 880
    double da = static_cast<const JSValue*>(a)->asNumber();
    double db = static_cast<const JSValue*>(b)->asNumber();
ggaren@apple.com's avatar
ggaren@apple.com committed
881 882 883
    return (da > db) - (da < db);
}

884 885
static int compareByStringPairForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
886 887
    const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
    const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
888
    return codePointCompare(va->second, vb->second);
889
}
darin's avatar
darin committed
890

ggaren@apple.com's avatar
ggaren@apple.com committed