JSArray.cpp 47.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;

95
const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0, CREATE_METHOD_TABLE(JSArray)};
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
JSArray::JSArray(VPtrStealingHackType)
130
    : JSNonFinalObject(VPtrStealingHack)
131
132
133
{
}

134
135
JSArray::JSArray(JSGlobalData& globalData, Structure* structure)
    : JSNonFinalObject(globalData, structure)
weinig@apple.com's avatar
weinig@apple.com committed
136
{
137
138
139
140
141
}

void JSArray::finishCreation(JSGlobalData& globalData)
{
    Base::finishCreation(globalData);
142
143
    ASSERT(inherits(&s_info));

weinig@apple.com's avatar
weinig@apple.com committed
144
145
    unsigned initialCapacity = 0;

146
147
    m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
    m_storage->m_allocBase = m_storage;
148
    m_indexBias = 0;
149
    m_vectorLength = initialCapacity;
weinig@apple.com's avatar
weinig@apple.com committed
150
151

    checkConsistency();
152
153

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

156
void JSArray::finishCreation(JSGlobalData& globalData, unsigned initialLength, ArrayCreationMode creationMode)
darin's avatar
darin committed
157
{
158
    Base::finishCreation(globalData);
159
160
    ASSERT(inherits(&s_info));

161
162
163
164
    unsigned initialCapacity;
    if (creationMode == CreateCompact)
        initialCapacity = initialLength;
    else
165
166
        initialCapacity = min(BASE_VECTOR_LEN, MIN_SPARSE_ARRAY_INDEX);
    
167
168
169
    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
    m_storage->m_allocBase = m_storage;
    m_storage->m_length = initialLength;
170
    m_indexBias = 0;
171
    m_vectorLength = initialCapacity;
172
173
174
    m_storage->m_sparseValueMap = 0;
    m_storage->subclassData = 0;
    m_storage->reportedMapCapacity = 0;
darin's avatar
darin committed
175

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

193
    checkConsistency();
194
    
195
    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity));
darin's avatar
darin committed
196
197
}

198
void JSArray::finishCreation(JSGlobalData& globalData, const ArgList& list)
darin's avatar
darin committed
199
{
200
    Base::finishCreation(globalData);
201
202
    ASSERT(inherits(&s_info));

203
    unsigned initialCapacity = list.size();
204
205
206
207
208
209
210
211
212
213
    unsigned initialStorage;
    
    // If the ArgList is empty, allocate space for 3 entries.  This value empirically
    // works well for benchmarks.
    if (!initialCapacity)
        initialStorage = 3;
    else
        initialStorage = initialCapacity;
    
    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialStorage)));
214
    m_storage->m_allocBase = m_storage;
215
    m_indexBias = 0;
216
    m_storage->m_length = initialCapacity;
217
    m_vectorLength = initialStorage;
218
219
220
221
    m_storage->m_numValuesInVector = initialCapacity;
    m_storage->m_sparseValueMap = 0;
    m_storage->subclassData = 0;
    m_storage->reportedMapCapacity = 0;
222
#if CHECK_ARRAY_CONSISTENCY
223
    m_storage->m_inCompactInitialization = false;
224
#endif
darin's avatar
darin committed
225

ggaren's avatar
ggaren committed
226
    size_t i = 0;
227
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
darin@apple.com's avatar
darin@apple.com committed
228
229
    ArgList::const_iterator end = list.end();
    for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
230
        vector[i].set(globalData, this, *it);
231
    for (; i < initialStorage; i++)
232
        vector[i].clear();
darin's avatar
darin committed
233

234
    checkConsistency();
235

236
    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialStorage));
darin's avatar
darin committed
237
238
}

darin@apple.com's avatar
darin@apple.com committed
239
JSArray::~JSArray()
darin's avatar
darin committed
240
{
ap@apple.com's avatar
ap@apple.com committed
241
    ASSERT(vptr() == JSGlobalData::jsArrayVPtr);
242
243
    checkConsistency(DestructorConsistencyCheck);

244
245
    delete m_storage->m_sparseValueMap;
    fastFree(m_storage->m_allocBase);
darin's avatar
darin committed
246
247
}

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

259
    if (i < thisObject->m_vectorLength) {
260
261
262
        JSValue value = storage->m_vector[i].get();
        if (value) {
            slot.setValue(value);
darin's avatar
darin committed
263
264
265
            return true;
        }
    } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
266
        if (i >= MIN_SPARSE_ARRAY_INDEX) {
darin@apple.com's avatar
darin@apple.com committed
267
268
            SparseArrayValueMap::iterator it = map->find(i);
            if (it != map->end()) {
269
                slot.setValue(it->second.get());
darin@apple.com's avatar
darin@apple.com committed
270
271
                return true;
            }
darin's avatar
darin committed
272
273
274
        }
    }

275
    return JSObject::getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
276
277
}

278
279
280
bool JSArray::getOwnPropertySlot(JSCell* cell, ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
{
    JSArray* thisObject = static_cast<JSArray*>(cell);
darin's avatar
darin committed
281
    if (propertyName == exec->propertyNames().length) {
282
        slot.setValue(jsNumber(thisObject->length()));
darin's avatar
darin committed
283
284
285
286
        return true;
    }

    bool isArrayIndex;
287
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
288
    if (isArrayIndex)
289
        return JSArray::getOwnPropertySlotByIndex(thisObject, exec, i, slot);
darin's avatar
darin committed
290

291
    return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
darin's avatar
darin committed
292
293
}

294
295
296
bool JSArray::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
{
    if (propertyName == exec->propertyNames().length) {
297
        descriptor.setDescriptor(jsNumber(length()), DontDelete | DontEnum);
298
299
        return true;
    }
300

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

327
328
329
330
// ECMA 15.4.5.1
void JSArray::put(JSCell* cell, ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
{
    JSArray* thisObject = static_cast<JSArray*>(cell);
darin's avatar
darin committed
331
    bool isArrayIndex;
332
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
333
    if (isArrayIndex) {
334
        putByIndex(thisObject, exec, i, value);
darin's avatar
darin committed
335
336
337
338
        return;
    }

    if (propertyName == exec->propertyNames().length) {
weinig@apple.com's avatar
weinig@apple.com committed
339
340
        unsigned newLength = value.toUInt32(exec);
        if (value.toNumber(exec) != static_cast<double>(newLength)) {
341
            throwError(exec, createRangeError(exec, "Invalid array length"));
darin's avatar
darin committed
342
343
            return;
        }
344
        thisObject->setLength(newLength);
darin's avatar
darin committed
345
346
347
        return;
    }

348
    JSObject::put(thisObject, exec, propertyName, value, slot);
darin's avatar
darin committed
349
350
}

351
void JSArray::putByIndex(JSCell* cell, ExecState* exec, unsigned i, JSValue value)
352
353
354
355
356
{
    JSArray* thisObject = static_cast<JSArray*>(cell);
    thisObject->checkConsistency();

    ArrayStorage* storage = thisObject->m_storage;
357
358

    unsigned length = storage->m_length;
barraclough@apple.com's avatar
barraclough@apple.com committed
359
    if (i >= length && i <= MAX_ARRAY_INDEX) {
darin's avatar
darin committed
360
        length = i + 1;
361
        storage->m_length = length;
darin's avatar
darin committed
362
363
    }

364
    if (i < thisObject->m_vectorLength) {
365
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
366
        if (valueSlot) {
367
368
            valueSlot.set(exec->globalData(), thisObject, value);
            thisObject->checkConsistency();
369
370
            return;
        }
371
        valueSlot.set(exec->globalData(), thisObject, value);
372
        ++storage->m_numValuesInVector;
373
        thisObject->checkConsistency();
darin's avatar
darin committed
374
375
376
        return;
    }

377
    thisObject->putSlowCase(exec, i, value);
378
379
}

ggaren@apple.com's avatar
ggaren@apple.com committed
380
NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
381
{
382
    ArrayStorage* storage = m_storage;
383
    
darin's avatar
darin committed
384
    SparseArrayValueMap* map = storage->m_sparseValueMap;
ap@webkit.org's avatar
ap@webkit.org committed
385

barraclough@apple.com's avatar
barraclough@apple.com committed
386
387
    if (i >= MIN_SPARSE_ARRAY_INDEX) {
        if (i > MAX_ARRAY_INDEX) {
weinig@apple.com's avatar
weinig@apple.com committed
388
            PutPropertySlot slot;
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
389
            methodTable()->put(this, exec, Identifier::from(exec, i), value, slot);
390
391
392
            return;
        }

ap@webkit.org's avatar
ap@webkit.org committed
393
        // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
394
        // (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
395
        if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
ap@webkit.org's avatar
ap@webkit.org committed
396
397
398
399
            if (!map) {
                map = new SparseArrayValueMap;
                storage->m_sparseValueMap = map;
            }
400

401
402
403
404
            WriteBarrier<Unknown> temp;
            pair<SparseArrayValueMap::iterator, bool> result = map->add(i, temp);
            result.first->second.set(exec->globalData(), this, value);
            if (!result.second) // pre-existing entry
405
406
407
408
409
410
411
                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
412
413
414
415
            return;
        }
    }

ap@webkit.org's avatar
ap@webkit.org committed
416
417
418
    // 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
419
        if (increaseVectorLength(i + 1)) {
420
            storage = m_storage;
421
            storage->m_vector[i].set(exec->globalData(), this, value);
422
            ++storage->m_numValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
423
424
425
            checkConsistency();
        } else
            throwOutOfMemoryError(exec);
darin's avatar
darin committed
426
427
428
        return;
    }

ap@webkit.org's avatar
ap@webkit.org committed
429
430
    // Decide how many values it would be best to move from the map.
    unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
431
    unsigned newVectorLength = getNewVectorLength(i + 1);
432
    for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
darin's avatar
darin committed
433
        newNumValuesInVector += map->contains(j);
barraclough@apple.com's avatar
barraclough@apple.com committed
434
    if (i >= MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
435
        newNumValuesInVector -= map->contains(i);
darin's avatar
darin committed
436
    if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
437
        unsigned needLength = max(i + 1, storage->m_length);
darin's avatar
darin committed
438
        unsigned proposedNewNumValuesInVector = newNumValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
439
        // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
440
        while ((newVectorLength < needLength) && (newVectorLength < MAX_STORAGE_VECTOR_LENGTH)) {
441
            unsigned proposedNewVectorLength = getNewVectorLength(newVectorLength + 1);
barraclough@apple.com's avatar
barraclough@apple.com committed
442
            for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
darin's avatar
darin committed
443
444
445
446
447
448
449
450
                proposedNewNumValuesInVector += map->contains(j);
            if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
                break;
            newVectorLength = proposedNewVectorLength;
            newNumValuesInVector = proposedNewNumValuesInVector;
        }
    }

451
    void* baseStorage = storage->m_allocBase;
452
453
    
    if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) {
barraclough@apple.com's avatar
barraclough@apple.com committed
454
455
456
        throwOutOfMemoryError(exec);
        return;
    }
darin's avatar
darin committed
457

458
    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
459
460
    m_storage->m_allocBase = baseStorage;
    storage = m_storage;
461
    
462
    unsigned vectorLength = m_vectorLength;
463
    WriteBarrier<Unknown>* vector = storage->m_vector;
464

darin's avatar
darin committed
465
466
    if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
        for (unsigned j = vectorLength; j < newVectorLength; ++j)
467
            vector[j].clear();
barraclough@apple.com's avatar
barraclough@apple.com committed
468
        if (i > MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
469
            map->remove(i);
darin's avatar
darin committed
470
    } else {
barraclough@apple.com's avatar
barraclough@apple.com committed
471
        for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
472
473
            vector[j].clear();
        JSGlobalData& globalData = exec->globalData();
barraclough@apple.com's avatar
barraclough@apple.com committed
474
        for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
475
            vector[j].set(globalData, this, map->take(j).get());
darin's avatar
darin committed
476
477
    }

478
    ASSERT(i < newVectorLength);
darin's avatar
darin committed
479

480
    m_vectorLength = newVectorLength;
darin's avatar
darin committed
481
    storage->m_numValuesInVector = newNumValuesInVector;
ap@webkit.org's avatar
ap@webkit.org committed
482

483
    storage->m_vector[i].set(exec->globalData(), this, value);
484
485

    checkConsistency();
486
487

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

490
491
492
bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, const Identifier& propertyName)
{
    JSArray* thisObject = static_cast<JSArray*>(cell);
darin's avatar
darin committed
493
    bool isArrayIndex;
494
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
495
    if (isArrayIndex)
496
        return thisObject->methodTable()->deletePropertyByIndex(thisObject, exec, i);
darin's avatar
darin committed
497
498
499
500

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

501
    return JSObject::deleteProperty(thisObject, exec, propertyName);
darin's avatar
darin committed
502
503
}

504
bool JSArray::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
505
506
507
508
509
{
    JSArray* thisObject = static_cast<JSArray*>(cell);
    thisObject->checkConsistency();

    ArrayStorage* storage = thisObject->m_storage;
510
    
511
    if (i < thisObject->m_vectorLength) {
512
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
513
        if (!valueSlot) {
514
            thisObject->checkConsistency();
515
516
            return false;
        }
517
        valueSlot.clear();
518
        --storage->m_numValuesInVector;
519
        thisObject->checkConsistency();
520
        return true;
darin's avatar
darin committed
521
522
523
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
524
        if (i >= MIN_SPARSE_ARRAY_INDEX) {
darin@apple.com's avatar
darin@apple.com committed
525
526
527
            SparseArrayValueMap::iterator it = map->find(i);
            if (it != map->end()) {
                map->remove(it);
528
                thisObject->checkConsistency();
darin@apple.com's avatar
darin@apple.com committed
529
530
                return true;
            }
darin's avatar
darin committed
531
532
533
        }
    }

534
    thisObject->checkConsistency();
535

barraclough@apple.com's avatar
barraclough@apple.com committed
536
    if (i > MAX_ARRAY_INDEX)
537
        return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, i));
darin's avatar
darin committed
538
539
540
541

    return false;
}

542
void JSArray::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
darin's avatar
darin committed
543
{
544
    JSArray* thisObject = static_cast<JSArray*>(object);
darin's avatar
darin committed
545
    // FIXME: Filling PropertyNameArray with an identifier for every integer
546
547
    // 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
548

549
    ArrayStorage* storage = thisObject->m_storage;
550
    
551
    unsigned usedVectorLength = min(storage->m_length, thisObject->m_vectorLength);
darin's avatar
darin committed
552
    for (unsigned i = 0; i < usedVectorLength; ++i) {
553
        if (storage->m_vector[i])
ap@webkit.org's avatar
ap@webkit.org committed
554
            propertyNames.add(Identifier::from(exec, i));
darin's avatar
darin committed
555
556
557
558
559
    }

    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
560
            propertyNames.add(Identifier::from(exec, it->first));
darin's avatar
darin committed
561
    }
562

563
564
565
    if (mode == IncludeDontEnumProperties)
        propertyNames.add(exec->propertyNames().length);

566
    JSObject::getOwnPropertyNames(thisObject, exec, propertyNames, mode);
darin's avatar
darin committed
567
568
}

569
570
571
572
573
ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
{
    ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);

    unsigned increasedLength;
574
    unsigned maxInitLength = min(m_storage->m_length, 100000U);
575

576
577
    if (desiredLength < maxInitLength)
        increasedLength = maxInitLength;
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
    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
596
bool JSArray::increaseVectorLength(unsigned newLength)
darin's avatar
darin committed
597
{
ap@webkit.org's avatar
ap@webkit.org committed
598
599
600
    // 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.

601
    ArrayStorage* storage = m_storage;
darin's avatar
darin committed
602

603
    unsigned vectorLength = m_vectorLength;
darin's avatar
darin committed
604
    ASSERT(newLength > vectorLength);
barraclough@apple.com's avatar
barraclough@apple.com committed
605
    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
606
    unsigned newVectorLength = getNewVectorLength(newLength);
607
    void* baseStorage = storage->m_allocBase;
darin's avatar
darin committed
608

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

612
    storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
613
    m_storage->m_allocBase = baseStorage;
614

615
    WriteBarrier<Unknown>* vector = storage->m_vector;
616
    for (unsigned i = vectorLength; i < newVectorLength; ++i)
617
        vector[i].clear();
ap@webkit.org's avatar
ap@webkit.org committed
618

619
    m_vectorLength = newVectorLength;
620
621
    
    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
darin's avatar
darin committed
622

623
624
    return true;
}
darin's avatar
darin committed
625

626
627
628
629
630
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.
    
631
    ArrayStorage* storage = m_storage;
632
633
634
635
636
    
    unsigned vectorLength = m_vectorLength;
    ASSERT(newLength > vectorLength);
    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
    unsigned newVectorLength = getNewVectorLength(newLength);
637
638

    void* newBaseStorage = fastMalloc(storageSize(newVectorLength + m_indexBias));
639
640
641
642
643
    if (!newBaseStorage)
        return false;
    
    m_indexBias += newVectorLength - newLength;
    
644
    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(newBaseStorage) + m_indexBias * sizeof(JSValue));
645

646
647
    memcpy(m_storage, storage, storageSize(0));
    memcpy(&m_storage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], vectorLength * sizeof(JSValue));
648
    
649
    m_storage->m_allocBase = newBaseStorage;
650
651
    m_vectorLength = newLength;
    
652
    fastFree(storage->m_allocBase);
653
654
655
656
    ASSERT(newLength > vectorLength);
    unsigned delta = newLength - vectorLength;
    for (unsigned i = 0; i < delta; i++)
        m_storage->m_vector[i].clear();
657
    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
658
    
ap@webkit.org's avatar
ap@webkit.org committed
659
    return true;
darin's avatar
darin committed
660
}
661
    
darin's avatar
darin committed
662

darin@apple.com's avatar
darin@apple.com committed
663
void JSArray::setLength(unsigned newLength)
darin's avatar
darin committed
664
{
665
666
    ArrayStorage* storage = m_storage;
    
667
#if CHECK_ARRAY_CONSISTENCY
668
    if (!storage->m_inCompactInitialization)
669
670
        checkConsistency();
    else
671
        storage->m_inCompactInitialization = false;
672
#endif
673

674
    unsigned length = storage->m_length;
darin's avatar
darin committed
675
676

    if (newLength < length) {
677
        unsigned usedVectorLength = min(length, m_vectorLength);
darin's avatar
darin committed
678
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
679
            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
680
            bool hadValue = valueSlot;
681
            valueSlot.clear();
darin's avatar
darin committed
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
            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
698

699
    storage->m_length = newLength;
700
701

    checkConsistency();
darin's avatar
darin committed
702
703
}

ggaren@apple.com's avatar
ggaren@apple.com committed
704
JSValue JSArray::pop()
705
706
707
{
    checkConsistency();

708
    ArrayStorage* storage = m_storage;
709
710
    
    unsigned length = storage->m_length;
711
712
713
714
715
    if (!length)
        return jsUndefined();

    --length;

ggaren@apple.com's avatar
ggaren@apple.com committed
716
    JSValue result;
717

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

741
    storage->m_length = length;
742
743
744
745
746
747

    checkConsistency();

    return result;
}

ggaren@apple.com's avatar
ggaren@apple.com committed
748
void JSArray::push(ExecState* exec, JSValue value)
749
750
{
    checkConsistency();
751
    
752
    ArrayStorage* storage = m_storage;
753

754
    if (UNLIKELY(storage->m_length == 0xFFFFFFFFu)) {
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
755
        methodTable()->putByIndex(this, exec, storage->m_length, value);
756
757
758
759
        throwError(exec, createRangeError(exec, "Invalid array length"));
        return;
    }

760
    if (storage->m_length < m_vectorLength) {
761
        storage->m_vector[storage->m_length].set(exec->globalData(), this, value);
762
763
        ++storage->m_numValuesInVector;
        ++storage->m_length;
764
765
766
767
        checkConsistency();
        return;
    }

768
769
    if (storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
        SparseArrayValueMap* map = storage->m_sparseValueMap;
770
        if (!map || map->isEmpty()) {
771
            if (increaseVectorLength(storage->m_length + 1)) {
772
                storage = m_storage;
773
                storage->m_vector[storage->m_length].set(exec->globalData(), this, value);
774
775
                ++storage->m_numValuesInVector;
                ++storage->m_length;
776
777
778
779
780
781
782
783
784
                checkConsistency();
                return;
            }
            checkConsistency();
            throwOutOfMemoryError(exec);
            return;
        }
    }

785
786
787
788
789
790
791
    putSlowCase(exec, storage->m_length++, value);
}

void JSArray::shiftCount(ExecState* exec, int count)
{
    ASSERT(count > 0);
    
792
    ArrayStorage* storage = m_storage;
793
794
795
796
797
798
799
800
801
802
803
804
    
    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) {
805
            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
806
807
808
                PropertySlot slot(this);
                JSValue p = prototype();
                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
809
                    methodTable()->putByIndex(this, exec, i, slot.getValue(exec, i));
810
811
812
            }
        }

813
        storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
814
815
816

        // Need to decrement numValuesInvector based on number of real entries
        for (unsigned i = 0; i < (unsigned)count; ++i)
817
            if ((i < m_vectorLength) && (storage->m_vector[i]))
818
819
820
821
822
823
824
825
826
827
828
829
830
831
                --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));
832
            m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
833
834
835
836
837
838
839
840

            m_indexBias += count;
        }
    }
}
    
void JSArray::unshiftCount(ExecState* exec, int count)
{
841
    ArrayStorage* storage = m_storage;
842
843
844
845
846
847
848
849
850
851
852
853

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