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

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

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

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

39
namespace JSC {
darin's avatar
darin committed
40

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

barraclough@apple.com's avatar
barraclough@apple.com committed
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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;
ggaren@apple.com's avatar
ggaren@apple.com committed
228
229
    for (; i < list.size(); ++i)
        vector[i].set(globalData, this, list.at(i));
230
    for (; i < initialStorage; i++)
231
        vector[i].clear();
darin's avatar
darin committed
232

233
    checkConsistency();
234

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

238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
void JSArray::finishCreation(JSGlobalData& globalData, const JSValue* values, size_t length)
{
    Base::finishCreation(globalData);
    ASSERT(inherits(&s_info));

    unsigned initialCapacity = length;
    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)));
    m_storage->m_allocBase = m_storage;
    m_indexBias = 0;
    m_storage->m_length = initialCapacity;
    m_vectorLength = initialStorage;
    m_storage->m_numValuesInVector = initialCapacity;
    m_storage->m_sparseValueMap = 0;
    m_storage->subclassData = 0;
    m_storage->reportedMapCapacity = 0;
#if CHECK_ARRAY_CONSISTENCY
    m_storage->m_inCompactInitialization = false;
#endif

    size_t i = 0;
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
    for ( ; i != length; ++i)
        vector[i].set(globalData, this, values[i]);
    for (; i < initialStorage; i++)
        vector[i].clear();

    checkConsistency();

    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialStorage));
}

darin@apple.com's avatar
darin@apple.com committed
278
JSArray::~JSArray()
darin's avatar
darin committed
279
{
ap@apple.com's avatar
ap@apple.com committed
280
    ASSERT(vptr() == JSGlobalData::jsArrayVPtr);
281
282
    checkConsistency(DestructorConsistencyCheck);

283
284
    delete m_storage->m_sparseValueMap;
    fastFree(m_storage->m_allocBase);
darin's avatar
darin committed
285
286
}

287
bool JSArray::getOwnPropertySlotByIndex(JSCell* cell, ExecState* exec, unsigned i, PropertySlot& slot)
288
{
289
    JSArray* thisObject = jsCast<JSArray*>(cell);
290
    ArrayStorage* storage = thisObject->m_storage;
291
    
ggaren@apple.com's avatar
ggaren@apple.com committed
292
    if (i >= storage->m_length) {
barraclough@apple.com's avatar
barraclough@apple.com committed
293
        if (i > MAX_ARRAY_INDEX)
294
            return thisObject->methodTable()->getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
295
296
297
        return false;
    }

298
    if (i < thisObject->m_vectorLength) {
299
300
301
        JSValue value = storage->m_vector[i].get();
        if (value) {
            slot.setValue(value);
darin's avatar
darin committed
302
303
304
            return true;
        }
    } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
305
        if (i >= MIN_SPARSE_ARRAY_INDEX) {
darin@apple.com's avatar
darin@apple.com committed
306
307
            SparseArrayValueMap::iterator it = map->find(i);
            if (it != map->end()) {
308
                slot.setValue(it->second.get());
darin@apple.com's avatar
darin@apple.com committed
309
310
                return true;
            }
darin's avatar
darin committed
311
312
313
        }
    }

314
    return JSObject::getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
315
316
}

317
318
bool JSArray::getOwnPropertySlot(JSCell* cell, ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
{
319
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
320
    if (propertyName == exec->propertyNames().length) {
321
        slot.setValue(jsNumber(thisObject->length()));
darin's avatar
darin committed
322
323
324
325
        return true;
    }

    bool isArrayIndex;
326
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
327
    if (isArrayIndex)
328
        return JSArray::getOwnPropertySlotByIndex(thisObject, exec, i, slot);
darin's avatar
darin committed
329

330
    return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
darin's avatar
darin committed
331
332
}

333
bool JSArray::getOwnPropertyDescriptor(JSObject* object, ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
334
{
335
    JSArray* thisObject = jsCast<JSArray*>(object);
336
    if (propertyName == exec->propertyNames().length) {
337
        descriptor.setDescriptor(jsNumber(thisObject->length()), DontDelete | DontEnum);
338
339
        return true;
    }
340

341
    ArrayStorage* storage = thisObject->m_storage;
342
343
    
    bool isArrayIndex;
344
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
345
    if (isArrayIndex) {
346
        if (i >= storage->m_length)
347
            return false;
348
        if (i < thisObject->m_vectorLength) {
349
            WriteBarrier<Unknown>& value = storage->m_vector[i];
350
            if (value) {
351
                descriptor.setDescriptor(value.get(), 0);
352
353
                return true;
            }
354
        } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
355
356
357
            if (i >= MIN_SPARSE_ARRAY_INDEX) {
                SparseArrayValueMap::iterator it = map->find(i);
                if (it != map->end()) {
358
                    descriptor.setDescriptor(it->second.get(), 0);
359
360
361
362
363
                    return true;
                }
            }
        }
    }
364
    return JSObject::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor);
365
366
}

367
368
369
// ECMA 15.4.5.1
void JSArray::put(JSCell* cell, ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
{
370
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
371
    bool isArrayIndex;
372
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
373
    if (isArrayIndex) {
374
        putByIndex(thisObject, exec, i, value);
darin's avatar
darin committed
375
376
377
378
        return;
    }

    if (propertyName == exec->propertyNames().length) {
weinig@apple.com's avatar
weinig@apple.com committed
379
380
        unsigned newLength = value.toUInt32(exec);
        if (value.toNumber(exec) != static_cast<double>(newLength)) {
381
            throwError(exec, createRangeError(exec, "Invalid array length"));
darin's avatar
darin committed
382
383
            return;
        }
384
        thisObject->setLength(newLength);
darin's avatar
darin committed
385
386
387
        return;
    }

388
    JSObject::put(thisObject, exec, propertyName, value, slot);
darin's avatar
darin committed
389
390
}

391
void JSArray::putByIndex(JSCell* cell, ExecState* exec, unsigned i, JSValue value)
392
{
393
    JSArray* thisObject = jsCast<JSArray*>(cell);
394
395
396
    thisObject->checkConsistency();

    ArrayStorage* storage = thisObject->m_storage;
397
398

    unsigned length = storage->m_length;
barraclough@apple.com's avatar
barraclough@apple.com committed
399
    if (i >= length && i <= MAX_ARRAY_INDEX) {
darin's avatar
darin committed
400
        length = i + 1;
401
        storage->m_length = length;
darin's avatar
darin committed
402
403
    }

404
    if (i < thisObject->m_vectorLength) {
405
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
406
        if (valueSlot) {
407
408
            valueSlot.set(exec->globalData(), thisObject, value);
            thisObject->checkConsistency();
409
410
            return;
        }
411
        valueSlot.set(exec->globalData(), thisObject, value);
412
        ++storage->m_numValuesInVector;
413
        thisObject->checkConsistency();
darin's avatar
darin committed
414
415
416
        return;
    }

417
    thisObject->putSlowCase(exec, i, value);
418
419
}

ggaren@apple.com's avatar
ggaren@apple.com committed
420
NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
421
{
422
    ArrayStorage* storage = m_storage;
423
    
darin's avatar
darin committed
424
    SparseArrayValueMap* map = storage->m_sparseValueMap;
ap@webkit.org's avatar
ap@webkit.org committed
425

barraclough@apple.com's avatar
barraclough@apple.com committed
426
427
    if (i >= MIN_SPARSE_ARRAY_INDEX) {
        if (i > MAX_ARRAY_INDEX) {
weinig@apple.com's avatar
weinig@apple.com committed
428
            PutPropertySlot slot;
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
429
            methodTable()->put(this, exec, Identifier::from(exec, i), value, slot);
430
431
432
            return;
        }

ap@webkit.org's avatar
ap@webkit.org committed
433
        // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
434
        // (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
435
        if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
ap@webkit.org's avatar
ap@webkit.org committed
436
437
438
439
            if (!map) {
                map = new SparseArrayValueMap;
                storage->m_sparseValueMap = map;
            }
440

441
442
443
444
            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
445
446
447
448
449
450
451
                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
452
453
454
455
            return;
        }
    }

ap@webkit.org's avatar
ap@webkit.org committed
456
457
458
    // 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
459
        if (increaseVectorLength(i + 1)) {
460
            storage = m_storage;
461
            storage->m_vector[i].set(exec->globalData(), this, value);
462
            ++storage->m_numValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
463
464
465
            checkConsistency();
        } else
            throwOutOfMemoryError(exec);
darin's avatar
darin committed
466
467
468
        return;
    }

ap@webkit.org's avatar
ap@webkit.org committed
469
470
    // Decide how many values it would be best to move from the map.
    unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
471
    unsigned newVectorLength = getNewVectorLength(i + 1);
472
    for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
darin's avatar
darin committed
473
        newNumValuesInVector += map->contains(j);
barraclough@apple.com's avatar
barraclough@apple.com committed
474
    if (i >= MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
475
        newNumValuesInVector -= map->contains(i);
darin's avatar
darin committed
476
    if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
477
        unsigned needLength = max(i + 1, storage->m_length);
darin's avatar
darin committed
478
        unsigned proposedNewNumValuesInVector = newNumValuesInVector;
barraclough@apple.com's avatar
barraclough@apple.com committed
479
        // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
480
        while ((newVectorLength < needLength) && (newVectorLength < MAX_STORAGE_VECTOR_LENGTH)) {
481
            unsigned proposedNewVectorLength = getNewVectorLength(newVectorLength + 1);
barraclough@apple.com's avatar
barraclough@apple.com committed
482
            for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
darin's avatar
darin committed
483
484
485
486
487
488
489
490
                proposedNewNumValuesInVector += map->contains(j);
            if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
                break;
            newVectorLength = proposedNewVectorLength;
            newNumValuesInVector = proposedNewNumValuesInVector;
        }
    }

491
    void* baseStorage = storage->m_allocBase;
492
493
    
    if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) {
barraclough@apple.com's avatar
barraclough@apple.com committed
494
495
496
        throwOutOfMemoryError(exec);
        return;
    }
darin's avatar
darin committed
497

498
    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
499
500
    m_storage->m_allocBase = baseStorage;
    storage = m_storage;
501
    
502
    unsigned vectorLength = m_vectorLength;
503
    WriteBarrier<Unknown>* vector = storage->m_vector;
504

darin's avatar
darin committed
505
506
    if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
        for (unsigned j = vectorLength; j < newVectorLength; ++j)
507
            vector[j].clear();
barraclough@apple.com's avatar
barraclough@apple.com committed
508
        if (i > MIN_SPARSE_ARRAY_INDEX)
ap@webkit.org's avatar
ap@webkit.org committed
509
            map->remove(i);
darin's avatar
darin committed
510
    } else {
barraclough@apple.com's avatar
barraclough@apple.com committed
511
        for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
512
513
            vector[j].clear();
        JSGlobalData& globalData = exec->globalData();
barraclough@apple.com's avatar
barraclough@apple.com committed
514
        for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
515
            vector[j].set(globalData, this, map->take(j).get());
darin's avatar
darin committed
516
517
    }

518
    ASSERT(i < newVectorLength);
darin's avatar
darin committed
519

520
    m_vectorLength = newVectorLength;
darin's avatar
darin committed
521
    storage->m_numValuesInVector = newNumValuesInVector;
ap@webkit.org's avatar
ap@webkit.org committed
522

523
    storage->m_vector[i].set(exec->globalData(), this, value);
524
525

    checkConsistency();
526
527

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

530
531
bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, const Identifier& propertyName)
{
532
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
533
    bool isArrayIndex;
534
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
535
    if (isArrayIndex)
536
        return thisObject->methodTable()->deletePropertyByIndex(thisObject, exec, i);
darin's avatar
darin committed
537
538
539
540

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

541
    return JSObject::deleteProperty(thisObject, exec, propertyName);
darin's avatar
darin committed
542
543
}

544
bool JSArray::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
545
{
546
    JSArray* thisObject = jsCast<JSArray*>(cell);
547
548
549
    thisObject->checkConsistency();

    ArrayStorage* storage = thisObject->m_storage;
550
    
551
    if (i < thisObject->m_vectorLength) {
552
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
553
        if (!valueSlot) {
554
            thisObject->checkConsistency();
555
556
            return false;
        }
557
        valueSlot.clear();
558
        --storage->m_numValuesInVector;
559
        thisObject->checkConsistency();
560
        return true;
darin's avatar
darin committed
561
562
563
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
barraclough@apple.com's avatar
barraclough@apple.com committed
564
        if (i >= MIN_SPARSE_ARRAY_INDEX) {
darin@apple.com's avatar
darin@apple.com committed
565
566
567
            SparseArrayValueMap::iterator it = map->find(i);
            if (it != map->end()) {
                map->remove(it);
568
                thisObject->checkConsistency();
darin@apple.com's avatar
darin@apple.com committed
569
570
                return true;
            }
darin's avatar
darin committed
571
572
573
        }
    }

574
    thisObject->checkConsistency();
575

barraclough@apple.com's avatar
barraclough@apple.com committed
576
    if (i > MAX_ARRAY_INDEX)
577
        return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, i));
darin's avatar
darin committed
578
579
580
581

    return false;
}

582
void JSArray::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
darin's avatar
darin committed
583
{
584
    JSArray* thisObject = jsCast<JSArray*>(object);
darin's avatar
darin committed
585
    // FIXME: Filling PropertyNameArray with an identifier for every integer
586
587
    // 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
588

589
    ArrayStorage* storage = thisObject->m_storage;
590
    
591
    unsigned usedVectorLength = min(storage->m_length, thisObject->m_vectorLength);
darin's avatar
darin committed
592
    for (unsigned i = 0; i < usedVectorLength; ++i) {
593
        if (storage->m_vector[i])
ap@webkit.org's avatar
ap@webkit.org committed
594
            propertyNames.add(Identifier::from(exec, i));
darin's avatar
darin committed
595
596
597
598
599
    }

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

603
604
605
    if (mode == IncludeDontEnumProperties)
        propertyNames.add(exec->propertyNames().length);

606
    JSObject::getOwnPropertyNames(thisObject, exec, propertyNames, mode);
darin's avatar
darin committed
607
608
}

609
610
611
612
613
ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
{
    ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);

    unsigned increasedLength;
614
    unsigned maxInitLength = min(m_storage->m_length, 100000U);
615

616
617
    if (desiredLength < maxInitLength)
        increasedLength = maxInitLength;
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
    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
636
bool JSArray::increaseVectorLength(unsigned newLength)
darin's avatar
darin committed
637
{
ap@webkit.org's avatar
ap@webkit.org committed
638
639
640
    // 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.

641
    ArrayStorage* storage = m_storage;
darin's avatar
darin committed
642

643
    unsigned vectorLength = m_vectorLength;
darin's avatar
darin committed
644
    ASSERT(newLength > vectorLength);
barraclough@apple.com's avatar
barraclough@apple.com committed
645
    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
646
    unsigned newVectorLength = getNewVectorLength(newLength);
647
    void* baseStorage = storage->m_allocBase;
darin's avatar
darin committed
648

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

652
    storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
653
    m_storage->m_allocBase = baseStorage;
654

655
    WriteBarrier<Unknown>* vector = storage->m_vector;
656
    for (unsigned i = vectorLength; i < newVectorLength; ++i)
657
        vector[i].clear();
ap@webkit.org's avatar
ap@webkit.org committed
658

659
    m_vectorLength = newVectorLength;
660
661
    
    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
darin's avatar
darin committed
662

663
664
    return true;
}
darin's avatar
darin committed
665

666
667
668
669
670
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.
    
671
    ArrayStorage* storage = m_storage;
672
673
674
675
676
    
    unsigned vectorLength = m_vectorLength;
    ASSERT(newLength > vectorLength);
    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
    unsigned newVectorLength = getNewVectorLength(newLength);
677
678

    void* newBaseStorage = fastMalloc(storageSize(newVectorLength + m_indexBias));
679
680
681
682
683
    if (!newBaseStorage)
        return false;
    
    m_indexBias += newVectorLength - newLength;
    
684
    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(newBaseStorage) + m_indexBias * sizeof(JSValue));
685

686
687
    memcpy(m_storage, storage, storageSize(0));
    memcpy(&m_storage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], vectorLength * sizeof(JSValue));
688
    
689
    m_storage->m_allocBase = newBaseStorage;
690
691
    m_vectorLength = newLength;
    
692
    fastFree(storage->m_allocBase);
693
694
695
696
    ASSERT(newLength > vectorLength);
    unsigned delta = newLength - vectorLength;
    for (unsigned i = 0; i < delta; i++)
        m_storage->m_vector[i].clear();
697
    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
698
    
ap@webkit.org's avatar
ap@webkit.org committed
699
    return true;
darin's avatar
darin committed
700
}
701
    
darin's avatar
darin committed
702

darin@apple.com's avatar
darin@apple.com committed
703
void JSArray::setLength(unsigned newLength)
darin's avatar
darin committed
704
{
705
706
    ArrayStorage* storage = m_storage;
    
707
#if CHECK_ARRAY_CONSISTENCY
708
    if (!storage->m_inCompactInitialization)
709
710
        checkConsistency();
    else
711
        storage->m_inCompactInitialization = false;
712
#endif
713

714
    unsigned length = storage->m_length;
darin's avatar
darin committed
715
716

    if (newLength < length) {
717
        unsigned usedVectorLength = min(length, m_vectorLength);
darin's avatar
darin committed
718
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
719
            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
720
            bool hadValue = valueSlot;
721
            valueSlot.clear();
darin's avatar
darin committed
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
            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
738

739
    storage->m_length = newLength;
740
741

    checkConsistency();
darin's avatar
darin committed
742
743
}

ggaren@apple.com's avatar
ggaren@apple.com committed
744
JSValue JSArray::pop()
745
746
747
{
    checkConsistency();

748
    ArrayStorage* storage = m_storage;
749
750
    
    unsigned length = storage->m_length;
751
752
753
754
755
    if (!length)
        return jsUndefined();

    --length;

ggaren@apple.com's avatar
ggaren@apple.com committed
756
    JSValue result;
757

758
    if (length < m_vectorLength) {
759
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[length];
760
        if (valueSlot) {
761
            --storage->m_numValuesInVector;
762
763
            result = valueSlot.get();
            valueSlot.clear();
764
        } else
765
766
767
            result = jsUndefined();
    } else {
        result = jsUndefined();
768
        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
769
770
            SparseArrayValueMap::iterator it = map->find(length);
            if (it != map->end()) {
771
                result = it->second.get();
772
773
774
                map->remove(it);
                if (map->isEmpty()) {
                    delete map;
775
                    storage->m_sparseValueMap = 0;
776
777
778
779
780
                }
            }
        }
    }

781
    storage->m_length = length;
782
783
784
785
786
787

    checkConsistency();

    return result;
}

ggaren@apple.com's avatar
ggaren@apple.com committed
788
void JSArray::push(ExecState* exec, JSValue value)
789
790
{
    checkConsistency();
791
    
792
    ArrayStorage* storage = m_storage;
793

794
    if (UNLIKELY(storage->m_length == 0xFFFFFFFFu)) {
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
795
        methodTable()->putByIndex(this, exec, storage->m_length, value);
796
797
798
799
        throwError(exec, createRangeError(exec, "Invalid array length"));
        return;
    }

800
    if (storage->m_length < m_vectorLength) {
801
        storage->m_vector[storage->m_length].set(exec->globalData(), this, value);
802
803
        ++storage->m_numValuesInVector;
        ++storage->m_length;
804
805
806
807
        checkConsistency();
        return;
    }

808
809
    if (storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
        SparseArrayValueMap* map = storage->m_sparseValueMap;
810
        if (!map || map->isEmpty()) {
811
            if (increaseVectorLength(storage->m_length + 1)) {
812
                storage = m_storage;
813
                storage->m_vector[storage->m_length].set(exec->globalData(), this, value);
814
815
                ++storage->m_numValuesInVector;
                ++storage->m_length;
816
817
818
819
820
821
822
823
824
                checkConsistency();
                return;
            }
            checkConsistency();
            throwOutOfMemoryError(exec);
            return;
        }
    }

825
826
827
828
829
830
831
    putSlowCase(exec, storage->m_length++, value);
}

void JSArray::shiftCount(ExecState* exec, int count)
{
    ASSERT(count > 0);
    
832
    ArrayStorage* storage = m_storage;
833
834
835
836
837
838
839
840
841
842
843
844
    
    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) {