JSArray.cpp 49 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
71 72 73
// size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) +
// (vectorLength * sizeof(WriteBarrier<Unknown>)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
#define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>))
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.
109
    size_t size = (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) + (vectorLength * sizeof(WriteBarrier<Unknown>));
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).
112
    ASSERT(((size - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))));
barraclough@apple.com's avatar
barraclough@apple.com committed
113 114

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

static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
{
119
    return length <= MIN_SPARSE_ARRAY_INDEX || length / minDensityMultiplier <= numValues;
darin's avatar
darin committed
120 121
}

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
SparseArrayValueMap::iterator SparseArrayValueMap::find(unsigned i)
{
    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) {
230
        Heap::heap(array)->reportExtraMemoryCost((capacity - m_reportedCapacity) * (sizeof(unsigned) + sizeof(WriteBarrier<Unknown>)));
231 232 233 234 235 236 237 238 239 240 241
        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);
}

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

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

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

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

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

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

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

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

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

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

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

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

    ArrayStorage* storage = thisObject->m_storage;
348

349
    // Fast case - store to the vector.
350
    if (i < thisObject->m_vectorLength) {
351
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
352 353 354 355 356 357 358 359 360 361
        unsigned length = storage->m_length;

        // Update m_length & m_numValuesInVector as necessary.
        if (i >= length) {
            length = i + 1;
            storage->m_length = length;
            ++storage->m_numValuesInVector;
        } else if (!valueSlot)
            ++storage->m_numValuesInVector;

362 363
        valueSlot.set(exec->globalData(), thisObject, value);
        thisObject->checkConsistency();
darin's avatar
darin committed
364 365 366
        return;
    }

367 368 369 370 371 372 373 374 375 376
    // Handle 2^32-1 - this is not an array index (see ES5.1 15.4), and is treated as a regular property.
    if (UNLIKELY(i > MAX_ARRAY_INDEX)) {
        PutPropertySlot slot;
        thisObject->methodTable()->put(thisObject, exec, Identifier::from(exec, i), value, slot);
        return;
    }

    // For all other cases, call putByIndexBeyondVectorLength.
    thisObject->putByIndexBeyondVectorLength(exec->globalData(), i, value);
    thisObject->checkConsistency();
377 378
}

379
NEVER_INLINE void JSArray::putByIndexBeyondVectorLength(JSGlobalData& globalData, unsigned i, JSValue value)
380
{
381
    // i should be a valid array index that is outside of the current vector.
382
    ASSERT(i >= m_vectorLength);
383
    ASSERT(i <= MAX_ARRAY_INDEX);
384

385
    ArrayStorage* storage = m_storage;
darin's avatar
darin committed
386
    SparseArrayValueMap* map = storage->m_sparseValueMap;
ap@webkit.org's avatar
ap@webkit.org committed
387

388 389 390 391 392
    // Update m_length if necessary.
    unsigned length = storage->m_length;
    if (i >= length) {
        length = i + 1;
        storage->m_length = length;
darin's avatar
darin committed
393 394
    }

395 396 397 398 399
    // First, handle cases where we don't currently have a sparse map.
    if (LIKELY(!map)) {
        // Check that it is sensible to still be using a vector, and then try to grow the vector.
        if (LIKELY((isDenseEnoughForVector(i, storage->m_numValuesInVector)) && increaseVectorLength(i + 1))) {
            // success! - reread m_storage since it has likely been reallocated, and store to the vector.
400
            storage = m_storage;
401
            storage->m_vector[i].set(globalData, this, value);
402
            ++storage->m_numValuesInVector;
403
            return;
darin's avatar
darin committed
404
        }
405 406 407 408 409
        // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
        map = new SparseArrayValueMap;
        storage->m_sparseValueMap = map;
        map->put(globalData, this, i, value);
        return;
darin's avatar
darin committed
410 411
    }

412 413 414 415 416
    // We are currently using a map - check whether we still want to be doing so.
    // We will continue  to use a sparse map if SparseMode is set, a vector would be too sparse, or if allocation fails.
    unsigned numValuesInArray = storage->m_numValuesInVector + map->size();
    if (map->sparseMode() || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(length)) {
        map->put(globalData, this, i, value);
barraclough@apple.com's avatar
barraclough@apple.com committed
417 418
        return;
    }
darin's avatar
darin committed
419

420
    // Reread m_storage afterincreaseVectorLength, update m_numValuesInVector.
421
    storage = m_storage;
422
    storage->m_numValuesInVector = numValuesInArray;
423

424 425 426 427 428 429 430 431 432 433 434 435 436
    // Copy all values from the map into the vector, and delete the map.
    WriteBarrier<Unknown>* vector = storage->m_vector;
    SparseArrayValueMap::const_iterator end = map->end();
    for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
        vector[it->first].set(globalData, this, it->second.get());
    delete map;
    storage->m_sparseValueMap = 0;

    // Store the new property into the vector.
    WriteBarrier<Unknown>& valueSlot = vector[i];
    if (!valueSlot)
        ++storage->m_numValuesInVector;
    valueSlot.set(globalData, this, value);
darin's avatar
darin committed
437 438
}

439 440
bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, const Identifier& propertyName)
{
441
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
442
    bool isArrayIndex;
443
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
444
    if (isArrayIndex)
445
        return thisObject->methodTable()->deletePropertyByIndex(thisObject, exec, i);
darin's avatar
darin committed
446 447 448 449

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

450
    return JSObject::deleteProperty(thisObject, exec, propertyName);
darin's avatar
darin committed
451 452
}

453
bool JSArray::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
454
{
455
    JSArray* thisObject = jsCast<JSArray*>(cell);
456 457 458
    thisObject->checkConsistency();

    ArrayStorage* storage = thisObject->m_storage;
459
    
460
    if (i < thisObject->m_vectorLength) {
461
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
462
        if (!valueSlot) {
463
            thisObject->checkConsistency();
464 465
            return false;
        }
466
        valueSlot.clear();
467
        --storage->m_numValuesInVector;
468
        thisObject->checkConsistency();
469
        return true;
darin's avatar
darin committed
470 471 472
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
473 474 475 476 477
        SparseArrayValueMap::iterator it = map->find(i);
        if (it != map->notFound()) {
            map->remove(it);
            thisObject->checkConsistency();
            return true;
darin's avatar
darin committed
478 479 480
        }
    }

481
    thisObject->checkConsistency();
482

barraclough@apple.com's avatar
barraclough@apple.com committed
483
    if (i > MAX_ARRAY_INDEX)
484
        return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, i));
darin's avatar
darin committed
485 486 487 488

    return false;
}

489
void JSArray::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
darin's avatar
darin committed
490
{
491
    JSArray* thisObject = jsCast<JSArray*>(object);
darin's avatar
darin committed
492
    // FIXME: Filling PropertyNameArray with an identifier for every integer
493 494
    // 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
495

496
    ArrayStorage* storage = thisObject->m_storage;
497
    
498
    unsigned usedVectorLength = min(storage->m_length, thisObject->m_vectorLength);
darin's avatar
darin committed
499
    for (unsigned i = 0; i < usedVectorLength; ++i) {
500
        if (storage->m_vector[i])
ap@webkit.org's avatar
ap@webkit.org committed
501
            propertyNames.add(Identifier::from(exec, i));
darin's avatar
darin committed
502 503 504
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
505 506
        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
507
            propertyNames.add(Identifier::from(exec, it->first));
darin's avatar
darin committed
508
    }
509

510 511 512
    if (mode == IncludeDontEnumProperties)
        propertyNames.add(exec->propertyNames().length);

513
    JSObject::getOwnPropertyNames(thisObject, exec, propertyNames, mode);
darin's avatar
darin committed
514 515
}

516 517 518 519 520
ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
{
    ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);

    unsigned increasedLength;
521
    unsigned maxInitLength = min(m_storage->m_length, 100000U);
522

523 524
    if (desiredLength < maxInitLength)
        increasedLength = maxInitLength;
525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542
    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
543
bool JSArray::increaseVectorLength(unsigned newLength)
darin's avatar
darin committed
544
{
ap@webkit.org's avatar
ap@webkit.org committed
545 546
    // 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.
547 548
    if (newLength > MAX_STORAGE_VECTOR_LENGTH)
        return false;
ap@webkit.org's avatar
ap@webkit.org committed
549

550
    ArrayStorage* storage = m_storage;
darin's avatar
darin committed
551

552
    unsigned vectorLength = m_vectorLength;
darin's avatar
darin committed
553
    ASSERT(newLength > vectorLength);
554
    unsigned newVectorLength = getNewVectorLength(newLength);
555
    void* baseStorage = storage->m_allocBase;
darin's avatar
darin committed
556

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

560
    storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(WriteBarrier<Unknown>));
561
    m_storage->m_allocBase = baseStorage;
562

563
    WriteBarrier<Unknown>* vector = storage->m_vector;
564
    for (unsigned i = vectorLength; i < newVectorLength; ++i)
565
        vector[i].clear();
ap@webkit.org's avatar
ap@webkit.org committed
566

567
    m_vectorLength = newVectorLength;
568 569
    
    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
darin's avatar
darin committed
570

571 572
    return true;
}
darin's avatar
darin committed
573

574 575
// This method makes room in the vector, but leaves the new space uncleared.
bool JSArray::unshiftCountSlowCase(unsigned count)
576
{
577 578
    // If not, we should have handled this on the fast path.
    ASSERT(count > m_indexBias);
579

580
    ArrayStorage* storage = m_storage;
581

582 583 584 585 586 587 588 589 590 591 592 593
    // Step 1:
    // Gather 4 key metrics:
    //  * usedVectorLength - how many entries are currently in the vector (conservative estimate - fewer may be in use in sparse vectors).
    //  * requiredVectorLength - how many entries are will there be in the vector, after allocating space for 'count' more.
    //  * currentCapacity - what is the current size of the vector, including any pre-capacity.
    //  * desiredCapacity - how large should we like to grow the vector to - based on 2x requiredVectorLength.

    unsigned length = storage->m_length;
    unsigned usedVectorLength = min(m_vectorLength, length);
    ASSERT(usedVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
    // Check that required vector length is possible, in an overflow-safe fashion.
    if (count > MAX_STORAGE_VECTOR_LENGTH - usedVectorLength)
594
        return false;
595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660
    unsigned requiredVectorLength = usedVectorLength + count;
    ASSERT(requiredVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
    // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH.
    ASSERT(m_vectorLength <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - m_vectorLength) >= m_indexBias);
    unsigned currentCapacity = m_vectorLength + m_indexBias;
    // The calculation of desiredCapacity won't overflow, due to the range of MAX_STORAGE_VECTOR_LENGTH.
    unsigned desiredCapacity = min(MAX_STORAGE_VECTOR_LENGTH, max(BASE_VECTOR_LEN, requiredVectorLength) << 1);

    // Step 2:
    // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing on.

    void* newAllocBase;
    unsigned newStorageCapacity;
    // If the current storage array is sufficiently large (but not too large!) then just keep using it.
    if (currentCapacity > desiredCapacity && isDenseEnoughForVector(currentCapacity, requiredVectorLength)) {
        newAllocBase = storage->m_allocBase;
        newStorageCapacity = currentCapacity;
    } else {
        if (!tryFastMalloc(storageSize(desiredCapacity)).getValue(newAllocBase))
            return false;
        newStorageCapacity = desiredCapacity;
        // Currently there is no way to report to the heap that the extra capacity is shrinking!
        if (desiredCapacity > currentCapacity)
            Heap::heap(this)->reportExtraMemoryCost((desiredCapacity - currentCapacity) * sizeof(WriteBarrier<Unknown>));
    }

    // Step 3:
    // Work out where we're going to move things to.

    // Determine how much of the vector to use as pre-capacity, and how much as post-capacity.
    // If the vector had no free post-capacity (length >= m_vectorLength), don't give it any.
    // If it did, we calculate the amount that will remain based on an atomic decay - leave the
    // vector with half the post-capacity it had previously.
    unsigned postCapacity = 0;
    if (length < m_vectorLength) {
        // Atomic decay, + the post-capacity cannot be greater than what is available.
        postCapacity = min((m_vectorLength - length) >> 1, newStorageCapacity - requiredVectorLength);
        // If we're moving contents within the same allocation, the post-capacity is being reduced.
        ASSERT(newAllocBase != storage->m_allocBase || postCapacity < m_vectorLength - length);
    }

    m_vectorLength = requiredVectorLength + postCapacity;
    m_indexBias = newStorageCapacity - m_vectorLength;
    m_storage = reinterpret_cast_ptr<ArrayStorage*>(reinterpret_cast<WriteBarrier<Unknown>*>(newAllocBase) + m_indexBias);

    // Step 4:
    // Copy array data / header into their new locations, clear post-capacity & free any old allocation.

    // If this is being moved within the existing buffer of memory, we are always shifting data
    // to the right (since count > m_indexBias). As such this memmove cannot trample the header.
    memmove(m_storage->m_vector + count, storage->m_vector, sizeof(WriteBarrier<Unknown>) * usedVectorLength);
    memmove(m_storage, storage, storageSize(0));

    // Are we copying into a new allocation?
    if (newAllocBase != m_storage->m_allocBase) {
        // Free the old allocation, update m_allocBase.
        fastFree(m_storage->m_allocBase);
        m_storage->m_allocBase = newAllocBase;

        // We need to clear any entries in the vector beyond length. We only need to
        // do this if this was a new allocation, because if we're using an existing
        // allocation the post-capacity will already be cleared, and in an existing
        // allocation we can only beshrinking the amount of post capacity.
        for (unsigned i = requiredVectorLength; i < m_vectorLength; ++i)
            m_storage->m_vector[i].clear();
    }
661

ap@webkit.org's avatar
ap@webkit.org committed
662
    return true;
darin's avatar
darin committed
663 664
}

darin@apple.com's avatar
darin@apple.com committed
665
void JSArray::setLength(unsigned newLength)
darin's avatar
darin committed
666
{
667 668
    checkConsistency();

669 670
    ArrayStorage* storage = m_storage;
    
671
    unsigned length = storage->m_length;
darin's avatar
darin committed
672 673

    if (newLength < length) {
674
        unsigned usedVectorLength = min(length, m_vectorLength);
darin's avatar
darin committed
675
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
676
            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
677
            bool hadValue = valueSlot;
678
            valueSlot.clear();
darin's avatar
darin committed
679 680 681 682 683
            storage->m_numValuesInVector -= hadValue;
        }

        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
            SparseArrayValueMap copy = *map;
684 685
            SparseArrayValueMap::const_iterator end = copy.end();
            for (SparseArrayValueMap::const_iterator it = copy.begin(); it != end; ++it) {
darin's avatar
darin committed
686 687 688
                if (it->first >= newLength)
                    map->remove(it->first);
            }
689
            if (map->isEmpty() && !map->sparseMode()) {
darin's avatar
darin committed
690 691 692 693 694
                delete map;
                storage->m_sparseValueMap = 0;
            }
        }
    }
aroben@apple.com's avatar
aroben@apple.com committed
695

696
    storage->m_length = newLength;
697 698

    checkConsistency();
darin's avatar
darin committed
699 700
}

ggaren@apple.com's avatar
ggaren@apple.com committed
701
JSValue JSArray::pop()
702 703 704
{
    checkConsistency();

705
    ArrayStorage* storage = m_storage;
706 707
    
    unsigned length = storage->m_length;
708 709 710 711 712
    if (!length)
        return jsUndefined();

    --length;

ggaren@apple.com's avatar
ggaren@apple.com committed
713
    JSValue result;
714

715
    if (length < m_vectorLength) {
716
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[length];
717
        if (valueSlot) {
718
            --storage->m_numValuesInVector;
719 720
            result = valueSlot.get();
            valueSlot.clear();
721
        } else
722 723 724
            result = jsUndefined();
    } else {
        result = jsUndefined();
725
        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
726 727
            SparseArrayValueMap::iterator it = map->find(length);
            if (it != map->end()) {
728
                result = it->second.get();
729
                map->remove(it);
730
                if (map->isEmpty() && !map->sparseMode()) {
731
                    delete map;
732
                    storage->m_sparseValueMap = 0;
733 734 735 736 737
                }
            }
        }
    }

738
    storage->m_length = length;
739 740 741 742 743 744

    checkConsistency();

    return result;
}

745 746 747
// Push & putIndex are almost identical, with two small differences.
//  - we always are writing beyond the current array bounds, so it is always necessary to update m_length & m_numValuesInVector.
//  - pushing to an array of length 2^32-1 stores the property, but throws a range error.
ggaren@apple.com's avatar
ggaren@apple.com committed
748
void JSArray::push(ExecState* exec, JSValue value)
749 750
{
    checkConsistency();
751
    ArrayStorage* storage = m_storage;
752

753 754 755 756 757
    // Fast case - push within vector, always update m_length & m_numValuesInVector.
    unsigned length = storage->m_length;
    if (length < m_vectorLength) {
        storage->m_vector[length].set(exec->globalData(), this, value);
        storage->m_length = length + 1;
758
        ++storage->m_numValuesInVector;
759 760 761 762
        checkConsistency();
        return;
    }

763 764 765 766 767 768
    // Pushing to an array of length 2^32-1 stores the property, but throws a range error.
    if (UNLIKELY(storage->m_length == 0xFFFFFFFFu)) {
        methodTable()->putByIndex(this, exec, storage->m_length, value);
        // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d.
        throwError(exec, createRangeError(exec, "Invalid array length"));
        return;
769 770
    }

771 772 773
    // Handled the same as putIndex.
    putByIndexBeyondVectorLength(exec->globalData(), storage->m_length, value);
    checkConsistency();
774 775
}

776
void JSArray::shiftCount(ExecState* exec, unsigned count)
777 778 779
{
    ASSERT(count > 0);
    
780
    ArrayStorage* storage = m_storage;
781 782 783 784 785 786 787 788 789 790 791 792
    
    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) {
793
            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
794 795 796
                PropertySlot slot(this);
                JSValue p = prototype();
                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
797
                    methodTable()->putByIndex(this, exec, i, slot.getValue(exec, i));
798 799 800
            }
        }

801
        storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
802 803 804

        // Need to decrement numValuesInvector based on number of real entries
        for (unsigned i = 0; i < (unsigned)count; ++i)
805
            if ((i < m_vectorLength) && (storage->m_vector[i]))
806 807 808 809 810 811 812 813 814 815 816 817
                --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) {
818
            char* newBaseStorage = reinterpret_cast<char*>(storage) + count * sizeof(WriteBarrier<Unknown>);
819
            memmove(newBaseStorage, storage, storageSize(0));
820
            m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
821 822 823 824 825 826

            m_indexBias += count;
        }
    }
}
    
827
void JSArray::unshiftCount(ExecState* exec, unsigned count)
828
{
829
    ArrayStorage* storage = m_storage;
830 831 832 833 834 835 836 837 838 839 840 841

    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) {
842
            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
843 844 845
                PropertySlot slot(this);
                JSValue p = prototype();
                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
846
                    methodTable()->putByIndex(this, exec, i, slot.getValue(exec, i));
847 848 849 850
            }
        }
    }
    
851
    storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
852 853 854
    
    if (m_indexBias >= count) {
        m_indexBias -= count;
855
        char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(WriteBarrier<Unknown>);
856
        memmove(newBaseStorage, storage, storageSize(0));
857
        m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
858
        m_vectorLength += count;
859
    } else if (!unshiftCountSlowCase(count)) {
860 861 862
        throwOutOfMemoryError(exec);
        return;
    }
863

864
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
865
    for (unsigned i = 0; i < count; i++)
866
        vector[i].clear();
867 868
}

869 870
void JSArray::visitChildren(JSCell* cell, SlotVisitor& visitor)
{
871
    JSArray* thisObject = jsCast<JSArray*>(cell);
872
    ASSERT_GC_OBJECT_INHERITS(thisObject, &s_info);
873
    COMPILE_ASSERT(StructureFlags & OverridesVisitChildren, OverridesVisitChildrenWithoutSettingFlag);
874
    ASSERT(thisObject->structure()->typeInfo().overridesVisitChildren());
ggaren@apple.com's avatar
ggaren@apple.com committed
875 876 877 878 879 880 881 882

    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);

883 884
    if (SparseArrayValueMap* map = storage->m_sparseValueMap)
        map->visitChildren(visitor);
darin's avatar
darin committed
885 886
}

ggaren@apple.com's avatar
ggaren@apple.com committed
887 888
static int compareNumbersForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
889 890
    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
891 892 893
    return (da > db) - (da < db);
}

894 895
static int compareByStringPairForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
896 897
    const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
    const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
898
    return codePointCompare(va->second, vb->second);
899
}
darin's avatar
darin committed
900

ggaren@apple.com's avatar
ggaren@apple.com committed
901
void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
ggaren@apple.com's avatar
ggaren@apple.com committed
902
{
903 904
    ASSERT(!inSparseMode());

905
    ArrayStorage* storage = m_storage;
906

ggaren@apple.com's avatar
ggaren@apple.com committed
907
    unsigned lengthNotIncludingUndefined = compactForSorting();
908
    if (storage->m_sparseValueMap) {
ggaren@apple.com's avatar
ggaren@apple.com committed
909 910 911 912 913 914 915 916
        throwOutOfMemoryError(exec);
        return;
    }

    if (!lengthNotIncludingUndefined)
        return;
        
    bool allValuesAreNumbers = true;
917
    size_t size = storage->m_numValuesInVector;
ggaren@apple.com's avatar
ggaren@apple.com committed
918
    for (size_t i = 0; i < size; ++i) {
919
        if (!storage->m_vector[i].isNumber()) {
ggaren@apple.com's avatar
ggaren@apple.com committed
920 921 922 923 924 925 926 927 928 929 930
            allValuesAreNumbers = false;
            break;
        }
    }

    if (!allValuesAreNumbers)
        return sort(exec, compareFunction, callType, callData);

    // For numeric comparison, which is fast, qsort is faster than mergesort. We
    // also don't require mergesort's stability, since there's no user visible
    // side-effect from swapping the order of equal primitive values.
931
    qsort(storage->m_vector, size, sizeof(WriteBarrier<Unknown>), compareNumbersForQSort);
ggaren@apple.com's avatar
ggaren@apple.com committed
932 933 934 935

    checkConsistency(SortConsistencyCheck);
}

darin@apple.com's avatar
darin@apple.com committed
936
void JSArray::sort(ExecState* exec)
darin's avatar
darin committed
937
{
938 939
    ASSERT(!inSparseMode());

940
    ArrayStorage* storage = m_storage;
941

darin's avatar
darin committed
942
    unsigned lengthNotIncludingUndefined = compactForSorting();
943
    if (storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
944
        throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
945 946
        return;
    }
darin's avatar
darin committed
947

ap@webkit.org's avatar
ap@webkit.org committed
948 949 950 951 952 953 954 955
    if (!lengthNotIncludingUndefined)
        return;

    // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
    // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
    // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
    // random or otherwise changing results, effectively making compare function inconsistent.

ggaren@apple.com's avatar
ggaren@apple.com committed
956
    Vector<ValueStringPair> values(lengthNotIncludingUndefined);
ap@webkit.org's avatar
ap@webkit.org committed
957
    if (!values.begin()) {
barraclough@apple.com's avatar
barraclough@apple.com committed
958
        throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
959 960
        return;
    }
961 962
    
    Heap::heap(this)->pushTempSortVector(&values);
darin's avatar
darin committed
963

ap@webkit.org's avatar
ap@webkit.org committed
964
    for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {