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

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

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

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

39
namespace JSC {
darin's avatar
darin committed
40

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

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

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

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

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

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

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

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

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

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

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

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

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

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(JSValue));
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 576 577
bool JSArray::increaseVectorPrefixLength(unsigned newLength)
{
    // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
    // to the vector. Callers have to account for that, because they can do it more efficiently.
578 579 580
    if (newLength > MAX_STORAGE_VECTOR_LENGTH)
        return false;

581
    ArrayStorage* storage = m_storage;
582 583 584 585 586
    
    unsigned vectorLength = m_vectorLength;
    ASSERT(newLength > vectorLength);
    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
    unsigned newVectorLength = getNewVectorLength(newLength);
587 588

    void* newBaseStorage = fastMalloc(storageSize(newVectorLength + m_indexBias));
589 590 591 592 593
    if (!newBaseStorage)
        return false;
    
    m_indexBias += newVectorLength - newLength;
    
594
    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(newBaseStorage) + m_indexBias * sizeof(JSValue));
595

596 597
    memcpy(m_storage, storage, storageSize(0));
    memcpy(&m_storage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], vectorLength * sizeof(JSValue));
598
    
599
    m_storage->m_allocBase = newBaseStorage;
600 601
    m_vectorLength = newLength;
    
602
    fastFree(storage->m_allocBase);
603 604 605 606
    ASSERT(newLength > vectorLength);
    unsigned delta = newLength - vectorLength;
    for (unsigned i = 0; i < delta; i++)
        m_storage->m_vector[i].clear();
607
    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
608
    
ap@webkit.org's avatar
ap@webkit.org committed
609
    return true;
darin's avatar
darin committed
610 611
}

darin@apple.com's avatar
darin@apple.com committed
612
void JSArray::setLength(unsigned newLength)
darin's avatar
darin committed
613
{
614 615
    checkConsistency();

616 617
    ArrayStorage* storage = m_storage;
    
618
    unsigned length = storage->m_length;
darin's avatar
darin committed
619 620

    if (newLength < length) {
621
        unsigned usedVectorLength = min(length, m_vectorLength);
darin's avatar
darin committed
622
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
623
            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
624
            bool hadValue = valueSlot;
625
            valueSlot.clear();
darin's avatar
darin committed
626 627 628 629 630
            storage->m_numValuesInVector -= hadValue;
        }

        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
            SparseArrayValueMap copy = *map;
631 632
            SparseArrayValueMap::const_iterator end = copy.end();
            for (SparseArrayValueMap::const_iterator it = copy.begin(); it != end; ++it) {
darin's avatar
darin committed
633 634 635
                if (it->first >= newLength)
                    map->remove(it->first);
            }
636
            if (map->isEmpty() && !map->sparseMode()) {
darin's avatar
darin committed
637 638 639 640 641
                delete map;
                storage->m_sparseValueMap = 0;
            }
        }
    }
aroben@apple.com's avatar
aroben@apple.com committed
642

643
    storage->m_length = newLength;
644 645

    checkConsistency();
darin's avatar
darin committed
646 647
}

ggaren@apple.com's avatar
ggaren@apple.com committed
648
JSValue JSArray::pop()
649 650 651
{
    checkConsistency();

652
    ArrayStorage* storage = m_storage;
653 654
    
    unsigned length = storage->m_length;
655 656 657 658 659
    if (!length)
        return jsUndefined();

    --length;

ggaren@apple.com's avatar
ggaren@apple.com committed
660
    JSValue result;
661

662
    if (length < m_vectorLength) {
663
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[length];
664
        if (valueSlot) {
665
            --storage->m_numValuesInVector;
666 667
            result = valueSlot.get();
            valueSlot.clear();
668
        } else
669 670 671
            result = jsUndefined();
    } else {
        result = jsUndefined();
672
        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
673 674
            SparseArrayValueMap::iterator it = map->find(length);
            if (it != map->end()) {
675
                result = it->second.get();
676
                map->remove(it);
677
                if (map->isEmpty() && !map->sparseMode()) {
678
                    delete map;
679
                    storage->m_sparseValueMap = 0;
680 681 682 683 684
                }
            }
        }
    }

685
    storage->m_length = length;
686 687 688 689 690 691

    checkConsistency();

    return result;
}

692 693 694
// 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
695
void JSArray::push(ExecState* exec, JSValue value)
696 697
{
    checkConsistency();
698
    ArrayStorage* storage = m_storage;
699

700 701 702 703 704
    // 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;
705
        ++storage->m_numValuesInVector;
706 707 708 709
        checkConsistency();
        return;
    }

710 711 712 713 714 715
    // 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;
716 717
    }

718 719 720
    // Handled the same as putIndex.
    putByIndexBeyondVectorLength(exec->globalData(), storage->m_length, value);
    checkConsistency();
721 722 723 724 725 726
}

void JSArray::shiftCount(ExecState* exec, int count)
{
    ASSERT(count > 0);
    
727
    ArrayStorage* storage = m_storage;
728 729 730 731 732 733 734 735 736 737 738 739
    
    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) {
740
            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
741 742 743
                PropertySlot slot(this);
                JSValue p = prototype();
                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
744
                    methodTable()->putByIndex(this, exec, i, slot.getValue(exec, i));
745 746 747
            }
        }

748
        storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
749 750 751

        // Need to decrement numValuesInvector based on number of real entries
        for (unsigned i = 0; i < (unsigned)count; ++i)
752
            if ((i < m_vectorLength) && (storage->m_vector[i]))
753 754 755 756 757 758 759 760 761 762 763 764 765 766
                --storage->m_numValuesInVector;
    } else
        storage->m_numValuesInVector -= count;
    
    storage->m_length -= count;
    
    if (m_vectorLength) {
        count = min(m_vectorLength, (unsigned)count);
        
        m_vectorLength -= count;
        
        if (m_vectorLength) {
            char* newBaseStorage = reinterpret_cast<char*>(storage) + count * sizeof(JSValue);
            memmove(newBaseStorage, storage, storageSize(0));
767
            m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
768 769 770 771 772 773 774 775

            m_indexBias += count;
        }
    }
}
    
void JSArray::unshiftCount(ExecState* exec, int count)
{
776
    ArrayStorage* storage = m_storage;
777 778 779 780 781 782 783 784 785 786 787 788

    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) {
789
            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
790 791 792
                PropertySlot slot(this);
                JSValue p = prototype();
                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
793
                    methodTable()->putByIndex(this, exec, i, slot.getValue(exec, i));
794 795 796 797
            }
        }
    }
    
798
    storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
799 800 801 802 803
    
    if (m_indexBias >= count) {
        m_indexBias -= count;
        char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(JSValue);
        memmove(newBaseStorage, storage, storageSize(0));
804
        m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
805
        m_vectorLength += count;
806
    } else if (!increaseVectorPrefixLength(m_vectorLength + count)) {
807 808 809
        throwOutOfMemoryError(exec);
        return;
    }
810

811
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
812
    for (int i = 0; i < count; i++)
813
        vector[i].clear();
814 815
}

816 817
void JSArray::visitChildren(JSCell* cell, SlotVisitor& visitor)
{
818
    JSArray* thisObject = jsCast<JSArray*>(cell);
819
    ASSERT_GC_OBJECT_INHERITS(thisObject, &s_info);
820
    COMPILE_ASSERT(StructureFlags & OverridesVisitChildren, OverridesVisitChildrenWithoutSettingFlag);
821
    ASSERT(thisObject->structure()->typeInfo().overridesVisitChildren());
ggaren@apple.com's avatar
ggaren@apple.com committed
822 823 824 825 826 827 828 829

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

830 831
    if (SparseArrayValueMap* map = storage->m_sparseValueMap)
        map->visitChildren(visitor);
darin's avatar
darin committed
832 833
}

ggaren@apple.com's avatar
ggaren@apple.com committed
834 835
static int compareNumbersForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
836 837
    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
838 839 840
    return (da > db) - (da < db);
}

841 842
static int compareByStringPairForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
843 844
    const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
    const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
845
    return codePointCompare(va->second, vb->second);
846
}
darin's avatar
darin committed