JSArray.cpp 50.6 KB
Newer Older
darin's avatar
darin committed
1 2
/*
 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3
 *  Copyright (C) 2003, 2007, 2008, 2009 Apple Inc. All rights reserved.
darin's avatar
darin committed
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
 *  Copyright (C) 2003 Peter Kelly (pmk@post.com)
 *  Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 *
 */

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

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

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

39
namespace JSC {
darin's avatar
darin committed
40

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

barraclough@apple.com's avatar
barraclough@apple.com committed
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
// 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 558 559 560
    // Fast case - there is no precapacity. In these cases a realloc makes sense.
    if (LIKELY(!m_indexBias)) {
        if (!tryFastRealloc(baseStorage, storageSize(newVectorLength)).getValue(baseStorage))
            return false;
561

562 563
        storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(baseStorage);
        m_storage->m_allocBase = baseStorage;
564

565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587
        WriteBarrier<Unknown>* vector = storage->m_vector;
        for (unsigned i = vectorLength; i < newVectorLength; ++i)
            vector[i].clear();

        m_vectorLength = newVectorLength;
        
        Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
        return true;
    }

    // Remove some, but not all of the precapacity. Atomic decay, & capped to not overflow array length.
    unsigned newIndexBias = min(m_indexBias >> 1, MAX_STORAGE_VECTOR_LENGTH - newVectorLength);
    // Calculate new stoarge capcity, allowing room for the pre-capacity.
    unsigned newStorageCapacity = newVectorLength + newIndexBias;
    void* newAllocBase;
    if (!tryFastMalloc(storageSize(newStorageCapacity)).getValue(newAllocBase))
        return false;
    // 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;
    // Currently there is no way to report to the heap that the extra capacity is shrinking!
    if (newStorageCapacity > currentCapacity)
        Heap::heap(this)->reportExtraMemoryCost((newStorageCapacity - currentCapacity) * sizeof(WriteBarrier<Unknown>));
ap@webkit.org's avatar
ap@webkit.org committed
588

589
    m_vectorLength = newVectorLength;
590 591 592 593 594 595 596 597 598 599 600
    m_indexBias = newIndexBias;
    m_storage = reinterpret_cast_ptr<ArrayStorage*>(reinterpret_cast<WriteBarrier<Unknown>*>(newAllocBase) + m_indexBias);

    // Copy the ArrayStorage header & current contents of the vector, clear the new post-capacity.
    memmove(m_storage, storage, storageSize(vectorLength));
    for (unsigned i = vectorLength; i < m_vectorLength; ++i)
        m_storage->m_vector[i].clear();

    // Free the old allocation, update m_allocBase.
    fastFree(m_storage->m_allocBase);
    m_storage->m_allocBase = newAllocBase;
darin's avatar
darin committed
601

602 603
    return true;
}
darin's avatar
darin committed
604

605 606
// This method makes room in the vector, but leaves the new space uncleared.
bool JSArray::unshiftCountSlowCase(unsigned count)
607
{
608 609
    // If not, we should have handled this on the fast path.
    ASSERT(count > m_indexBias);
610

611
    ArrayStorage* storage = m_storage;
612

613 614 615 616 617 618 619 620 621 622 623 624
    // 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)
625
        return false;
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 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691
    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();
    }
692

ap@webkit.org's avatar
ap@webkit.org committed
693
    return true;
darin's avatar
darin committed
694 695
}

darin@apple.com's avatar
darin@apple.com committed
696
void JSArray::setLength(unsigned newLength)
darin's avatar
darin committed
697
{
698 699
    checkConsistency();

700 701
    ArrayStorage* storage = m_storage;
    
702
    unsigned length = storage->m_length;
darin's avatar
darin committed
703 704

    if (newLength < length) {
705
        unsigned usedVectorLength = min(length, m_vectorLength);
darin's avatar
darin committed
706
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
707
            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
708
            bool hadValue = valueSlot;
709
            valueSlot.clear();
darin's avatar
darin committed
710 711 712 713 714
            storage->m_numValuesInVector -= hadValue;
        }

        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
            SparseArrayValueMap copy = *map;
715 716
            SparseArrayValueMap::const_iterator end = copy.end();
            for (SparseArrayValueMap::const_iterator it = copy.begin(); it != end; ++it) {
darin's avatar
darin committed
717 718 719
                if (it->first >= newLength)
                    map->remove(it->first);
            }
720
            if (map->isEmpty() && !map->sparseMode()) {
darin's avatar
darin committed
721 722 723 724 725
                delete map;
                storage->m_sparseValueMap = 0;
            }
        }
    }
aroben@apple.com's avatar
aroben@apple.com committed
726

727
    storage->m_length = newLength;
728 729

    checkConsistency();
darin's avatar
darin committed
730 731
}

ggaren@apple.com's avatar
ggaren@apple.com committed
732
JSValue JSArray::pop()
733 734 735
{
    checkConsistency();

736
    ArrayStorage* storage = m_storage;
737 738
    
    unsigned length = storage->m_length;
739 740 741 742 743
    if (!length)
        return jsUndefined();

    --length;

ggaren@apple.com's avatar
ggaren@apple.com committed
744
    JSValue result;
745

746
    if (length < m_vectorLength) {
747
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[length];
748
        if (valueSlot) {
749
            --storage->m_numValuesInVector;
750 751
            result = valueSlot.get();
            valueSlot.clear();
752
        } else
753 754 755
            result = jsUndefined();
    } else {
        result = jsUndefined();
756
        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
757
            SparseArrayValueMap::iterator it = map->find(length);
758
            if (it != map->notFound()) {
759
                result = it->second.get();
760
                map->remove(it);
761
                if (map->isEmpty() && !map->sparseMode()) {
762
                    delete map;
763
                    storage->m_sparseValueMap = 0;
764 765 766 767 768
                }
            }
        }
    }

769
    storage->m_length = length;
770 771 772 773 774 775

    checkConsistency();

    return result;
}

776 777 778
// 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
779
void JSArray::push(ExecState* exec, JSValue value)
780 781
{
    checkConsistency();
782
    ArrayStorage* storage = m_storage;
783

784 785 786 787 788
    // 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;
789
        ++storage->m_numValuesInVector;
790 791 792 793
        checkConsistency();
        return;
    }

794 795 796 797 798 799
    // 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;
800 801
    }

802 803 804
    // Handled the same as putIndex.
    putByIndexBeyondVectorLength(exec->globalData(), storage->m_length, value);
    checkConsistency();
805 806
}

807
void JSArray::shiftCount(ExecState* exec, unsigned count)
808 809 810
{
    ASSERT(count > 0);
    
811
    ArrayStorage* storage = m_storage;
812 813 814 815 816 817 818 819 820 821 822 823
    
    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) {
824
            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
825 826 827
                PropertySlot slot(this);
                JSValue p = prototype();
                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
828
                    methodTable()->putByIndex(this, exec, i, slot.getValue(exec, i));
829 830 831
            }
        }

832
        storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
833 834 835

        // Need to decrement numValuesInvector based on number of real entries
        for (unsigned i = 0; i < (unsigned)count; ++i)
836
            if ((i < m_vectorLength) && (storage->m_vector[i]))
837 838 839 840 841 842 843 844 845 846 847 848
                --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) {
849
            char* newBaseStorage = reinterpret_cast<char*>(storage) + count * sizeof(WriteBarrier<Unknown>);
850
            memmove(newBaseStorage, storage, storageSize(0));
851
            m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
852 853 854 855 856 857

            m_indexBias += count;
        }
    }
}
    
858
void JSArray::unshiftCount(ExecState* exec, unsigned count)
859
{
860
    ArrayStorage* storage = m_storage;
861
    unsigned length = storage->m_length;
862

863 864 865 866 867 868
    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) {
869
            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
870 871 872
                PropertySlot slot(this);
                JSValue p = prototype();
                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
873
                    methodTable()->putByIndex(this, exec, i, slot.getValue(exec, i));
874 875 876 877
            }
        }
    }
    
878
    storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
879 880 881
    
    if (m_indexBias >= count) {
        m_indexBias -= count;
882
        char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(WriteBarrier<Unknown>);
883
        memmove(newBaseStorage, storage, storageSize(0));
884
        m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
885
        m_vectorLength += count;
886
    } else if (!unshiftCountSlowCase(count)) {
887 888 889
        throwOutOfMemoryError(exec);
        return;
    }
890

891
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
892
    for (unsigned i = 0; i < count; i++)
893
        vector[i].clear();
894 895
}

896 897
void JSArray::visitChildren(JSCell* cell, SlotVisitor& visitor)
{
898
    JSArray* thisObject = jsCast<JSArray*>(cell);
899
    ASSERT_GC_OBJECT_INHERITS(thisObject, &s_info);
900
    COMPILE_ASSERT(StructureFlags & OverridesVisitChildren, OverridesVisitChildrenWithoutSettingFlag);
901
    ASSERT(thisObject->structure()->typeInfo().overridesVisitChildren());
ggaren@apple.com's avatar
ggaren@apple.com committed
902 903 904 905 906 907 908 909

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

910 911
    if (SparseArrayValueMap* map = storage->m_sparseValueMap)
        map->visitChildren(visitor);
darin's avatar
darin committed
912 913
}

ggaren@apple.com's avatar
ggaren@apple.com committed
914 915
static int compareNumbersForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
916 917
    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
918 919 920
    return (da > db) - (da < db);
}

921 922
static int compareByStringPairForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
923 924
    const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
    const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
925
    return codePointCompare(va->second, vb->second);
926
}
darin's avatar
darin committed
927

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

932
    ArrayStorage* storage = m_storage;
933

ggaren@apple.com's avatar
ggaren@apple.com committed
934
    unsigned lengthNotIncludingUndefined = compactForSorting();
935
    if (storage->m_sparseValueMap) {
ggaren@apple.com's avatar
ggaren@apple.com committed
936 937 938 939 940 941 942 943
        throwOutOfMemoryError(exec);
        return;
    }

    if (!lengthNotIncludingUndefined)
        return;
        
    bool allValuesAreNumbers = true;
944
    size_t size = storage->m_numValuesInVector;
ggaren@apple.com's avatar
ggaren@apple.com committed
945
    for (size_t i = 0; i < size; ++i) {
946
        if (!storage->m_vector[i].isNumber()) {
ggaren@apple.com's avatar
ggaren@apple.com committed
947 948 949 950 951 952 953 954 955 956 957
            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.
958
    qsort(storage->m_vector, size, sizeof(WriteBarrier<Unknown>), compareNumbersForQSort);
ggaren@apple.com's avatar
ggaren@apple.com committed
959 960 961 962

    checkConsistency(SortConsistencyCheck);
}

darin@apple.com's avatar
darin@apple.com committed
963
void JSArray::sort(ExecState* exec)
darin's avatar
darin committed
964
{
965 966
    ASSERT(!inSparseMode());

967
    ArrayStorage* storage = m_storage;
968

darin's avatar
darin committed
969
    unsigned lengthNotIncludingUndefined = compactForSorting();
970
    if (storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
971
        throwOutOfMemoryError(exec);
ap@webkit.org's avatar
ap@webkit.org committed
972 973
        return;
    }
darin's avatar
darin committed
974

ap@webkit.org's avatar
ap@webkit.org committed
975 976 977 978 979 980 981 982
    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
983
    Vector<ValueStringPair> values(lengthNotIncludingUndefined);
ap@webkit.org's avatar
ap@webkit.org committed
984
    if (!values.begin()) {
barraclough@apple.com's avatar
barraclough@apple.com committed
985
        throwOutOfMemoryError(exec);