JSArray.cpp 44.3 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 60 61 62 63 64 65 66 67 68 69
// 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:
//
//   * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector.
//   * 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
70 71 72
// 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
73 74 75 76 77

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

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

darin@apple.com's avatar
darin@apple.com committed
95
const ClassInfo JSArray::info = {"Array", 0, 0, 0};
darin's avatar
darin committed
96

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

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

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

121 122
#if !CHECK_ARRAY_CONSISTENCY

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

#endif

129 130 131 132 133
JSArray::JSArray(VPtrStealingHackType)
    : JSObject(createStructure(jsNull()))
{
    unsigned initialCapacity = 0;

134 135
    m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
    m_storage->m_allocBase = m_storage;
136 137 138 139 140 141 142 143 144 145
    m_indexBias = 0;
    m_vectorLength = initialCapacity;

    checkConsistency();
    
    // It's not safe to call Heap::heap(this) in order to report extra memory
    // cost here, because the VPtrStealingHackType JSArray is not allocated on
    // the heap. For the same reason, it's OK not to report extra cost.
}

146
JSArray::JSArray(NonNullPassRefPtr<Structure> structure)
darin@apple.com's avatar
darin@apple.com committed
147
    : JSObject(structure)
weinig@apple.com's avatar
weinig@apple.com committed
148 149 150
{
    unsigned initialCapacity = 0;

151 152
    m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
    m_storage->m_allocBase = m_storage;
153
    m_indexBias = 0;
154
    m_vectorLength = initialCapacity;
weinig@apple.com's avatar
weinig@apple.com committed
155 156

    checkConsistency();
157 158

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

161
JSArray::JSArray(NonNullPassRefPtr<Structure> structure, unsigned initialLength, ArrayCreationMode creationMode)
darin@apple.com's avatar
darin@apple.com committed
162
    : JSObject(structure)
darin's avatar
darin committed
163
{
164 165 166 167
    unsigned initialCapacity;
    if (creationMode == CreateCompact)
        initialCapacity = initialLength;
    else
168 169
        initialCapacity = min(BASE_VECTOR_LEN, MIN_SPARSE_ARRAY_INDEX);
    
170 171 172
    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
    m_storage->m_allocBase = m_storage;
    m_storage->m_length = initialLength;
173
    m_indexBias = 0;
174
    m_vectorLength = initialCapacity;
175 176 177
    m_storage->m_sparseValueMap = 0;
    m_storage->subclassData = 0;
    m_storage->reportedMapCapacity = 0;
darin's avatar
darin committed
178

179 180
    if (creationMode == CreateCompact) {
#if CHECK_ARRAY_CONSISTENCY
181
        m_storage->m_inCompactInitialization = !!initialCapacity;
182
#endif
183 184
        m_storage->m_length = 0;
        m_storage->m_numValuesInVector = initialCapacity;
185 186
    } else {
#if CHECK_ARRAY_CONSISTENCY
187
        storage->m_inCompactInitialization = false;
188
#endif
189 190 191
        m_storage->m_length = initialLength;
        m_storage->m_numValuesInVector = 0;
        JSValue* vector = m_storage->m_vector;
192 193 194
        for (size_t i = 0; i < initialCapacity; ++i)
            vector[i] = JSValue();
    }
195

196
    checkConsistency();
197
    
198
    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity));
darin's avatar
darin committed
199 200
}

201
JSArray::JSArray(NonNullPassRefPtr<Structure> structure, const ArgList& list)
darin@apple.com's avatar
darin@apple.com committed
202
    : JSObject(structure)
darin's avatar
darin committed
203
{
204
    unsigned initialCapacity = list.size();
darin's avatar
darin committed
205

206 207
    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
    m_storage->m_allocBase = m_storage;
208
    m_indexBias = 0;
209
    m_storage->m_length = initialCapacity;
210
    m_vectorLength = initialCapacity;
211 212 213 214
    m_storage->m_numValuesInVector = initialCapacity;
    m_storage->m_sparseValueMap = 0;
    m_storage->subclassData = 0;
    m_storage->reportedMapCapacity = 0;
215
#if CHECK_ARRAY_CONSISTENCY
216
    m_storage->m_inCompactInitialization = false;
217
#endif
darin's avatar
darin committed
218

ggaren's avatar
ggaren committed
219
    size_t i = 0;
220
    JSValue* vector = m_storage->m_vector;
darin@apple.com's avatar
darin@apple.com committed
221 222
    ArgList::const_iterator end = list.end();
    for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
223
        vector[i] = *it;
darin's avatar
darin committed
224

225
    checkConsistency();
226 227

    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity));
darin's avatar
darin committed
228 229
}

darin@apple.com's avatar
darin@apple.com committed
230
JSArray::~JSArray()
darin's avatar
darin committed
231
{
ap@apple.com's avatar
ap@apple.com committed
232
    ASSERT(vptr() == JSGlobalData::jsArrayVPtr);
233 234
    checkConsistency(DestructorConsistencyCheck);

235 236
    delete m_storage->m_sparseValueMap;
    fastFree(m_storage->m_allocBase);
darin's avatar
darin committed
237 238
}

239
bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
darin's avatar
darin committed
240
{
241
    ArrayStorage* storage = m_storage;
242
    
ggaren@apple.com's avatar
ggaren@apple.com committed
243
    if (i >= storage->m_length) {
barraclough@apple.com's avatar
barraclough@apple.com committed
244
        if (i > MAX_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
245
            return getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
246 247 248
        return false;
    }

249
    if (i < m_vectorLength) {
250
        JSValue& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
251
        if (valueSlot) {
darin@apple.com's avatar
darin@apple.com committed
252
            slot.setValueSlot(&valueSlot);
darin's avatar
darin committed
253 254 255
            return true;
        }
    } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
256
        if (i >= MIN_SPARSE_ARRAY_INDEX) {
darin@apple.com's avatar
darin@apple.com committed
257 258
            SparseArrayValueMap::iterator it = map->find(i);
            if (it != map->end()) {
darin@apple.com's avatar
darin@apple.com committed
259
                slot.setValueSlot(&it->second);
darin@apple.com's avatar
darin@apple.com committed
260 261
                return true;
            }
darin's avatar
darin committed
262 263 264
        }
    }

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

darin@apple.com's avatar
darin@apple.com committed
268
bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
darin's avatar
darin committed
269 270
{
    if (propertyName == exec->propertyNames().length) {
ggaren@apple.com's avatar
ggaren@apple.com committed
271
        slot.setValue(jsNumber(exec, length()));
darin's avatar
darin committed
272 273 274 275
        return true;
    }

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

    return JSObject::getOwnPropertySlot(exec, propertyName, slot);
}

283 284 285 286 287 288
bool JSArray::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
{
    if (propertyName == exec->propertyNames().length) {
        descriptor.setDescriptor(jsNumber(exec, length()), DontDelete | DontEnum);
        return true;
    }
289

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

darin's avatar
darin committed
316
// ECMA 15.4.5.1
ggaren@apple.com's avatar
ggaren@apple.com committed
317
void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
darin's avatar
darin committed
318 319
{
    bool isArrayIndex;
320
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
321
    if (isArrayIndex) {
darin@apple.com's avatar
darin@apple.com committed
322
        put(exec, i, value);
darin's avatar
darin committed
323 324 325 326
        return;
    }

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

weinig@apple.com's avatar
weinig@apple.com committed
336
    JSObject::put(exec, propertyName, value, slot);
darin's avatar
darin committed
337 338
}

ggaren@apple.com's avatar
ggaren@apple.com committed
339
void JSArray::put(ExecState* exec, unsigned i, JSValue value)
darin's avatar
darin committed
340
{
341 342
    checkConsistency();

343
    ArrayStorage* storage = m_storage;
344 345

    unsigned length = storage->m_length;
barraclough@apple.com's avatar
barraclough@apple.com committed
346
    if (i >= length && i <= MAX_ARRAY_INDEX) {
darin's avatar
darin committed
347
        length = i + 1;
348
        storage->m_length = length;
darin's avatar
darin committed
349 350
    }

351
    if (i < m_vectorLength) {
352
        JSValue& valueSlot = storage->m_vector[i];
353 354 355 356 357
        if (valueSlot) {
            valueSlot = value;
            checkConsistency();
            return;
        }
darin's avatar
darin committed
358
        valueSlot = value;
359
        ++storage->m_numValuesInVector;
360
        checkConsistency();
darin's avatar
darin committed
361 362 363
        return;
    }

364 365 366
    putSlowCase(exec, i, value);
}

ggaren@apple.com's avatar
ggaren@apple.com committed
367
NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
368
{
369
    ArrayStorage* storage = m_storage;
370
    
darin's avatar
darin committed
371
    SparseArrayValueMap* map = storage->m_sparseValueMap;
ap@webkit.org's avatar
ap@webkit.org committed
372

barraclough@apple.com's avatar
barraclough@apple.com committed
373 374
    if (i >= MIN_SPARSE_ARRAY_INDEX) {
        if (i > MAX_ARRAY_INDEX) {
weinig@apple.com's avatar
weinig@apple.com committed
375 376
            PutPropertySlot slot;
            put(exec, Identifier::from(exec, i), value, slot);
377 378 379
            return;
        }

ap@webkit.org's avatar
ap@webkit.org committed
380
        // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
381
        // (which will only be compacted as we reach indices that are less than MIN_SPARSE_ARRAY_INDEX) - but this makes the check much faster.
barraclough@apple.com's avatar
barraclough@apple.com committed
382
        if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
ap@webkit.org's avatar
ap@webkit.org committed
383 384 385 386
            if (!map) {
                map = new SparseArrayValueMap;
                storage->m_sparseValueMap = map;
            }
387 388 389 390 391 392 393 394 395 396 397 398

            pair<SparseArrayValueMap::iterator, bool> result = map->add(i, value);
            if (!result.second) { // pre-existing entry
                result.first->second = value;
                return;
            }

            size_t capacity = map->capacity();
            if (capacity != storage->reportedMapCapacity) {
                Heap::heap(this)->reportExtraMemoryCost((capacity - storage->reportedMapCapacity) * (sizeof(unsigned) + sizeof(JSValue)));
                storage->reportedMapCapacity = capacity;
            }
darin's avatar
darin committed
399 400 401 402
            return;
        }
    }

ap@webkit.org's avatar
ap@webkit.org committed
403 404 405
    // We have decided that we'll put the new item into the vector.
    // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
    if (!map || map->isEmpty()) {
barraclough@apple.com's avatar
barraclough@apple.com committed
406
        if (increaseVectorLength(i + 1)) {
407 408 409
            storage = m_storage;
            storage->m_vector[i] = value;
            ++storage->m_numValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
410 411 412
            checkConsistency();
        } else
            throwOutOfMemoryError(exec);
darin's avatar
darin committed
413 414 415
        return;
    }

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

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

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

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

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

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

469
    storage->m_vector[i] = value;
470 471

    checkConsistency();
472 473

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

darin@apple.com's avatar
darin@apple.com committed
476
bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)
darin's avatar
darin committed
477 478
{
    bool isArrayIndex;
479
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
480 481 482 483 484 485 486 487 488
    if (isArrayIndex)
        return deleteProperty(exec, i);

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

    return JSObject::deleteProperty(exec, propertyName);
}

darin@apple.com's avatar
darin@apple.com committed
489
bool JSArray::deleteProperty(ExecState* exec, unsigned i)
darin's avatar
darin committed
490
{
491 492
    checkConsistency();

493
    ArrayStorage* storage = m_storage;
494
    
495
    if (i < m_vectorLength) {
496
        JSValue& valueSlot = storage->m_vector[i];
497 498 499 500
        if (!valueSlot) {
            checkConsistency();
            return false;
        }
ggaren@apple.com's avatar
ggaren@apple.com committed
501
        valueSlot = JSValue();
502
        --storage->m_numValuesInVector;
503
        checkConsistency();
504
        return true;
darin's avatar
darin committed
505 506 507
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
508
        if (i >= MIN_SPARSE_ARRAY_INDEX) {
darin@apple.com's avatar
darin@apple.com committed
509 510 511
            SparseArrayValueMap::iterator it = map->find(i);
            if (it != map->end()) {
                map->remove(it);
512
                checkConsistency();
darin@apple.com's avatar
darin@apple.com committed
513 514
                return true;
            }
darin's avatar
darin committed
515 516 517
        }
    }

518 519
    checkConsistency();

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

    return false;
}

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

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

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
        SparseArrayValueMap::iterator end = map->end();
        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
ap@webkit.org's avatar
ap@webkit.org committed
543
            propertyNames.add(Identifier::from(exec, it->first));
darin's avatar
darin committed
544
    }
545

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

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

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

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

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

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

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

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

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

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

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

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

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

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

629 630
    memcpy(m_storage, storage, storageSize(0));
    memcpy(&m_storage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], vectorLength * sizeof(JSValue));
631
    
632
    m_storage->m_allocBase = newBaseStorage;
633 634
    m_vectorLength = newLength;
    
635
    fastFree(storage->m_allocBase);
636 637

    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
638
    
ap@webkit.org's avatar
ap@webkit.org committed
639
    return true;
darin's avatar
darin committed
640
}
641
    
darin's avatar
darin committed
642

darin@apple.com's avatar
darin@apple.com committed
643
void JSArray::setLength(unsigned newLength)
darin's avatar
darin committed
644
{
645 646
    ArrayStorage* storage = m_storage;
    
647
#if CHECK_ARRAY_CONSISTENCY
648
    if (!storage->m_inCompactInitialization)
649 650
        checkConsistency();
    else
651
        storage->m_inCompactInitialization = false;
652
#endif
653

654
    unsigned length = storage->m_length;
darin's avatar
darin committed
655 656

    if (newLength < length) {
657
        unsigned usedVectorLength = min(length, m_vectorLength);
darin's avatar
darin committed
658
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
659
            JSValue& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
660
            bool hadValue = valueSlot;
ggaren@apple.com's avatar
ggaren@apple.com committed
661
            valueSlot = JSValue();
darin's avatar
darin committed
662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677
            storage->m_numValuesInVector -= hadValue;
        }

        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
            SparseArrayValueMap copy = *map;
            SparseArrayValueMap::iterator end = copy.end();
            for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
                if (it->first >= newLength)
                    map->remove(it->first);
            }
            if (map->isEmpty()) {
                delete map;
                storage->m_sparseValueMap = 0;
            }
        }
    }
aroben@apple.com's avatar
aroben@apple.com committed
678

679
    storage->m_length = newLength;
680 681

    checkConsistency();
darin's avatar
darin committed
682 683
}

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

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

    --length;

ggaren@apple.com's avatar
ggaren@apple.com committed
696
    JSValue result;
697

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

721
    storage->m_length = length;
722 723 724 725 726 727

    checkConsistency();

    return result;
}

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

734
    if (storage->m_length < m_vectorLength) {
735
        storage->m_vector[storage->m_length] = value;
736 737
        ++storage->m_numValuesInVector;
        ++storage->m_length;
738 739 740 741
        checkConsistency();
        return;
    }

742 743
    if (storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
        SparseArrayValueMap* map = storage->m_sparseValueMap;
744
        if (!map || map->isEmpty()) {
745
            if (increaseVectorLength(storage->m_length + 1)) {
746 747
                storage = m_storage;
                storage->m_vector[storage->m_length] = value;
748 749
                ++storage->m_numValuesInVector;
                ++storage->m_length;
750 751 752 753 754 755 756 757 758
                checkConsistency();
                return;
            }
            checkConsistency();
            throwOutOfMemoryError(exec);
            return;
        }
    }

759 760 761 762 763 764 765
    putSlowCase(exec, storage->m_length++, value);
}

void JSArray::shiftCount(ExecState* exec, int count)
{
    ASSERT(count > 0);
    
766
    ArrayStorage* storage = m_storage;
767 768 769