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

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

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

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

39
namespace JSC {
darin's avatar
darin committed
40

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

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

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

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

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

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

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

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

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

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

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

static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
{
119
    return length <= MIN_SPARSE_ARRAY_INDEX || length / minDensityMultiplier <= numValues;
darin's avatar
darin committed
120
121
}

122
123
#if !CHECK_ARRAY_CONSISTENCY

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

#endif

130
131
JSArray::JSArray(JSGlobalData& globalData, Structure* structure)
    : JSNonFinalObject(globalData, structure)
132
    , m_storage(0)
weinig@apple.com's avatar
weinig@apple.com committed
133
{
134
135
}

136
void JSArray::finishCreation(JSGlobalData& globalData, unsigned initialLength)
137
138
{
    Base::finishCreation(globalData);
139
140
    ASSERT(inherits(&s_info));

141
142
    unsigned initialVectorLength = BASE_VECTOR_LEN;
    unsigned initialStorageSize = storageSize(initialVectorLength);
weinig@apple.com's avatar
weinig@apple.com committed
143

144
    m_storage = static_cast<ArrayStorage*>(fastMalloc(initialStorageSize));
145
    m_storage->m_allocBase = m_storage;
146
    m_storage->m_length = initialLength;
147
    m_indexBias = 0;
148
149
150
151
152
153
154
    m_vectorLength = initialVectorLength;
    m_storage->m_sparseValueMap = 0;
    m_storage->subclassData = 0;
    m_storage->m_numValuesInVector = 0;
#if CHECK_ARRAY_CONSISTENCY
    m_storage->m_inCompactInitialization = false;
#endif
weinig@apple.com's avatar
weinig@apple.com committed
155

156
157
158
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
    for (size_t i = 0; i < initialVectorLength; ++i)
        vector[i].clear();
159

160
161
162
    checkConsistency();
    
    Heap::heap(this)->reportExtraMemoryCost(initialStorageSize);
weinig@apple.com's avatar
weinig@apple.com committed
163
164
}

165
JSArray* JSArray::tryFinishCreationUninitialized(JSGlobalData& globalData, unsigned initialLength)
darin's avatar
darin committed
166
{
167
    Base::finishCreation(globalData);
168
169
    ASSERT(inherits(&s_info));

170
171
172
173
174
175
176
177
    // Check for lengths larger than we can handle with a vector.
    if (initialLength > MAX_STORAGE_VECTOR_LENGTH)
        return 0;

    unsigned initialVectorLength = max(initialLength, BASE_VECTOR_LEN);
    unsigned initialStorageSize = storageSize(initialVectorLength);

    m_storage = static_cast<ArrayStorage*>(fastMalloc(initialStorageSize));
178
    m_storage->m_allocBase = m_storage;
179
    m_storage->m_length = 0;
180
    m_indexBias = 0;
181
    m_vectorLength = initialVectorLength;
182
183
    m_storage->m_sparseValueMap = 0;
    m_storage->subclassData = 0;
184
    m_storage->m_numValuesInVector = initialLength;
185
#if CHECK_ARRAY_CONSISTENCY
186
    m_storage->m_inCompactInitialization = true;
187
#endif
188

189
190
191
192
193
194
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
    for (size_t i = initialLength; i < initialVectorLength; ++i)
        vector[i].clear();

    Heap::heap(this)->reportExtraMemoryCost(initialStorageSize);
    return this;
darin's avatar
darin committed
195
196
}

darin@apple.com's avatar
darin@apple.com committed
197
JSArray::~JSArray()
darin's avatar
darin committed
198
{
199
    ASSERT(jsCast<JSArray*>(this));
200

201
202
203
204
205
    // If we are unable to allocate memory for m_storage then this may be null.
    if (!m_storage)
        return;

    checkConsistency(DestructorConsistencyCheck);
206
207
    delete m_storage->m_sparseValueMap;
    fastFree(m_storage->m_allocBase);
darin's avatar
darin committed
208
209
}

210
211
212
213
214
void JSArray::destroy(JSCell* cell)
{
    jsCast<JSArray*>(cell)->JSArray::~JSArray();
}

215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
SparseArrayValueMap::iterator SparseArrayValueMap::find(unsigned i)
{
    return m_map.find(i);
}

inline void SparseArrayValueMap::put(JSGlobalData& globalData, JSArray* array, unsigned i, JSValue value)
{
    SparseArrayEntry temp;
    pair<Map::iterator, bool> result = m_map.add(i, temp);
    result.first->second.set(globalData, array, value);
    if (!result.second) // pre-existing entry
        return;

    size_t capacity = m_map.capacity();
    if (capacity != m_reportedCapacity) {
230
        Heap::heap(array)->reportExtraMemoryCost((capacity - m_reportedCapacity) * (sizeof(unsigned) + sizeof(WriteBarrier<Unknown>)));
231
232
233
234
235
236
237
238
239
240
241
        m_reportedCapacity = capacity;
    }
}

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

242
bool JSArray::getOwnPropertySlotByIndex(JSCell* cell, ExecState* exec, unsigned i, PropertySlot& slot)
243
{
244
    JSArray* thisObject = jsCast<JSArray*>(cell);
245
    ArrayStorage* storage = thisObject->m_storage;
246
    
ggaren@apple.com's avatar
ggaren@apple.com committed
247
    if (i >= storage->m_length) {
barraclough@apple.com's avatar
barraclough@apple.com committed
248
        if (i > MAX_ARRAY_INDEX)
249
            return thisObject->methodTable()->getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
250
251
252
        return false;
    }

253
    if (i < thisObject->m_vectorLength) {
254
255
256
        JSValue value = storage->m_vector[i].get();
        if (value) {
            slot.setValue(value);
darin's avatar
darin committed
257
258
259
            return true;
        }
    } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
260
261
262
263
        SparseArrayValueMap::iterator it = map->find(i);
        if (it != map->notFound()) {
            slot.setValue(it->second.get());
            return true;
darin's avatar
darin committed
264
265
266
        }
    }

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

270
271
bool JSArray::getOwnPropertySlot(JSCell* cell, ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
{
272
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
273
    if (propertyName == exec->propertyNames().length) {
274
        slot.setValue(jsNumber(thisObject->length()));
darin's avatar
darin committed
275
276
277
278
        return true;
    }

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

283
    return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
darin's avatar
darin committed
284
285
}

286
bool JSArray::getOwnPropertyDescriptor(JSObject* object, ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
287
{
288
    JSArray* thisObject = jsCast<JSArray*>(object);
289
    if (propertyName == exec->propertyNames().length) {
290
        descriptor.setDescriptor(jsNumber(thisObject->length()), DontDelete | DontEnum);
291
292
        return true;
    }
293

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

318
319
320
// ECMA 15.4.5.1
void JSArray::put(JSCell* cell, ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
{
321
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
322
    bool isArrayIndex;
323
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
324
    if (isArrayIndex) {
325
        putByIndex(thisObject, exec, i, value);
darin's avatar
darin committed
326
327
328
329
        return;
    }

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

339
    JSObject::put(thisObject, exec, propertyName, value, slot);
darin's avatar
darin committed
340
341
}

342
void JSArray::putByIndex(JSCell* cell, ExecState* exec, unsigned i, JSValue value)
343
{
344
    JSArray* thisObject = jsCast<JSArray*>(cell);
345
346
347
    thisObject->checkConsistency();

    ArrayStorage* storage = thisObject->m_storage;
348

349
    // Fast case - store to the vector.
350
    if (i < thisObject->m_vectorLength) {
351
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
352
353
354
355
356
357
358
359
360
361
        unsigned length = storage->m_length;

        // Update m_length & m_numValuesInVector as necessary.
        if (i >= length) {
            length = i + 1;
            storage->m_length = length;
            ++storage->m_numValuesInVector;
        } else if (!valueSlot)
            ++storage->m_numValuesInVector;

362
363
        valueSlot.set(exec->globalData(), thisObject, value);
        thisObject->checkConsistency();
darin's avatar
darin committed
364
365
366
        return;
    }

367
368
369
370
371
372
373
374
375
376
    // Handle 2^32-1 - this is not an array index (see ES5.1 15.4), and is treated as a regular property.
    if (UNLIKELY(i > MAX_ARRAY_INDEX)) {
        PutPropertySlot slot;
        thisObject->methodTable()->put(thisObject, exec, Identifier::from(exec, i), value, slot);
        return;
    }

    // For all other cases, call putByIndexBeyondVectorLength.
    thisObject->putByIndexBeyondVectorLength(exec->globalData(), i, value);
    thisObject->checkConsistency();
377
378
}

379
NEVER_INLINE void JSArray::putByIndexBeyondVectorLength(JSGlobalData& globalData, unsigned i, JSValue value)
380
{
381
    // i should be a valid array index that is outside of the current vector.
382
    ASSERT(i >= m_vectorLength);
383
    ASSERT(i <= MAX_ARRAY_INDEX);
384

385
    ArrayStorage* storage = m_storage;
darin's avatar
darin committed
386
    SparseArrayValueMap* map = storage->m_sparseValueMap;
ap@webkit.org's avatar
ap@webkit.org committed
387

388
389
390
391
392
    // Update m_length if necessary.
    unsigned length = storage->m_length;
    if (i >= length) {
        length = i + 1;
        storage->m_length = length;
darin's avatar
darin committed
393
394
    }

395
396
397
398
399
    // First, handle cases where we don't currently have a sparse map.
    if (LIKELY(!map)) {
        // Check that it is sensible to still be using a vector, and then try to grow the vector.
        if (LIKELY((isDenseEnoughForVector(i, storage->m_numValuesInVector)) && increaseVectorLength(i + 1))) {
            // success! - reread m_storage since it has likely been reallocated, and store to the vector.
400
            storage = m_storage;
401
            storage->m_vector[i].set(globalData, this, value);
402
            ++storage->m_numValuesInVector;
403
            return;
darin's avatar
darin committed
404
        }
405
406
407
408
409
        // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
        map = new SparseArrayValueMap;
        storage->m_sparseValueMap = map;
        map->put(globalData, this, i, value);
        return;
darin's avatar
darin committed
410
411
    }

412
413
414
415
416
    // We are currently using a map - check whether we still want to be doing so.
    // We will continue  to use a sparse map if SparseMode is set, a vector would be too sparse, or if allocation fails.
    unsigned numValuesInArray = storage->m_numValuesInVector + map->size();
    if (map->sparseMode() || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(length)) {
        map->put(globalData, this, i, value);
barraclough@apple.com's avatar
barraclough@apple.com committed
417
418
        return;
    }
darin's avatar
darin committed
419

420
    // Reread m_storage afterincreaseVectorLength, update m_numValuesInVector.
421
    storage = m_storage;
422
    storage->m_numValuesInVector = numValuesInArray;
423

424
425
426
427
428
429
430
431
432
433
434
435
436
    // Copy all values from the map into the vector, and delete the map.
    WriteBarrier<Unknown>* vector = storage->m_vector;
    SparseArrayValueMap::const_iterator end = map->end();
    for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
        vector[it->first].set(globalData, this, it->second.get());
    delete map;
    storage->m_sparseValueMap = 0;

    // Store the new property into the vector.
    WriteBarrier<Unknown>& valueSlot = vector[i];
    if (!valueSlot)
        ++storage->m_numValuesInVector;
    valueSlot.set(globalData, this, value);
darin's avatar
darin committed
437
438
}

439
440
bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, const Identifier& propertyName)
{
441
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
442
    bool isArrayIndex;
443
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
444
    if (isArrayIndex)
445
        return thisObject->methodTable()->deletePropertyByIndex(thisObject, exec, i);
darin's avatar
darin committed
446
447
448
449

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

450
    return JSObject::deleteProperty(thisObject, exec, propertyName);
darin's avatar
darin committed
451
452
}

453
bool JSArray::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
454
{
455
    JSArray* thisObject = jsCast<JSArray*>(cell);
456
457
458
    thisObject->checkConsistency();

    ArrayStorage* storage = thisObject->m_storage;
459
    
460
    if (i < thisObject->m_vectorLength) {
461
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
462
        if (!valueSlot) {
463
            thisObject->checkConsistency();
464
465
            return false;
        }
466
        valueSlot.clear();
467
        --storage->m_numValuesInVector;
468
        thisObject->checkConsistency();
469
        return true;
darin's avatar
darin committed
470
471
472
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
473
474
475
476
477
        SparseArrayValueMap::iterator it = map->find(i);
        if (it != map->notFound()) {
            map->remove(it);
            thisObject->checkConsistency();
            return true;
darin's avatar
darin committed
478
479
480
        }
    }

481
    thisObject->checkConsistency();
482

barraclough@apple.com's avatar
barraclough@apple.com committed
483
    if (i > MAX_ARRAY_INDEX)
484
        return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, i));
darin's avatar
darin committed
485
486
487
488

    return false;
}

489
void JSArray::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
darin's avatar
darin committed
490
{
491
    JSArray* thisObject = jsCast<JSArray*>(object);
darin's avatar
darin committed
492
    // FIXME: Filling PropertyNameArray with an identifier for every integer
493
494
    // is incredibly inefficient for large arrays. We need a different approach,
    // which almost certainly means a different structure for PropertyNameArray.
darin's avatar
darin committed
495

496
    ArrayStorage* storage = thisObject->m_storage;
497
    
498
    unsigned usedVectorLength = min(storage->m_length, thisObject->m_vectorLength);
darin's avatar
darin committed
499
    for (unsigned i = 0; i < usedVectorLength; ++i) {
500
        if (storage->m_vector[i])
ap@webkit.org's avatar
ap@webkit.org committed
501
            propertyNames.add(Identifier::from(exec, i));
darin's avatar
darin committed
502
503
504
    }

    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
505
506
        SparseArrayValueMap::const_iterator end = map->end();
        for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
ap@webkit.org's avatar
ap@webkit.org committed
507
            propertyNames.add(Identifier::from(exec, it->first));
darin's avatar
darin committed
508
    }
509

510
511
512
    if (mode == IncludeDontEnumProperties)
        propertyNames.add(exec->propertyNames().length);

513
    JSObject::getOwnPropertyNames(thisObject, exec, propertyNames, mode);
darin's avatar
darin committed
514
515
}

516
517
518
519
520
ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
{
    ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);

    unsigned increasedLength;
521
    unsigned maxInitLength = min(m_storage->m_length, 100000U);
522

523
524
    if (desiredLength < maxInitLength)
        increasedLength = maxInitLength;
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
    else if (!m_vectorLength)
        increasedLength = max(desiredLength, lastArraySize);
    else {
        // Mathematically equivalent to:
        //   increasedLength = (newLength * 3 + 1) / 2;
        // or:
        //   increasedLength = (unsigned)ceil(newLength * 1.5));
        // This form is not prone to internal overflow.
        increasedLength = desiredLength + (desiredLength >> 1) + (desiredLength & 1);
    }

    ASSERT(increasedLength >= desiredLength);

    lastArraySize = min(increasedLength, FIRST_VECTOR_GROW);

    return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
}

darin@apple.com's avatar
darin@apple.com committed
543
bool JSArray::increaseVectorLength(unsigned newLength)
darin's avatar
darin committed
544
{
ap@webkit.org's avatar
ap@webkit.org committed
545
546
    // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
    // to the vector. Callers have to account for that, because they can do it more efficiently.
547
548
    if (newLength > MAX_STORAGE_VECTOR_LENGTH)
        return false;
ap@webkit.org's avatar
ap@webkit.org committed
549

550
    ArrayStorage* storage = m_storage;
darin's avatar
darin committed
551

552
    unsigned vectorLength = m_vectorLength;
darin's avatar
darin committed
553
    ASSERT(newLength > vectorLength);
554
    unsigned newVectorLength = getNewVectorLength(newLength);
555
    void* baseStorage = storage->m_allocBase;
darin's avatar
darin committed
556

557
558
559
560
    // Fast case - there is no precapacity. In these cases a realloc makes sense.
    if (LIKELY(!m_indexBias)) {
        if (!tryFastRealloc(baseStorage, storageSize(newVectorLength)).getValue(baseStorage))
            return false;
561

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

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

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

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

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

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

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

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

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

611
    ArrayStorage* storage = m_storage;
612

613
614
615
616
617
618
619
620
621
622
623
624
    // Step 1:
    // Gather 4 key metrics:
    //  * usedVectorLength - how many entries are currently in the vector (conservative estimate - fewer may be in use in sparse vectors).
    //  * requiredVectorLength - how many entries are will there be in the vector, after allocating space for 'count' more.
    //  * currentCapacity - what is the current size of the vector, including any pre-capacity.
    //  * desiredCapacity - how large should we like to grow the vector to - based on 2x requiredVectorLength.

    unsigned length = storage->m_length;
    unsigned usedVectorLength = min(m_vectorLength, length);
    ASSERT(usedVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
    // Check that required vector length is possible, in an overflow-safe fashion.
    if (count > MAX_STORAGE_VECTOR_LENGTH - usedVectorLength)
625
        return false;
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
    unsigned requiredVectorLength = usedVectorLength + count;
    ASSERT(requiredVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
    // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH.
    ASSERT(m_vectorLength <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - m_vectorLength) >= m_indexBias);
    unsigned currentCapacity = m_vectorLength + m_indexBias;
    // The calculation of desiredCapacity won't overflow, due to the range of MAX_STORAGE_VECTOR_LENGTH.
    unsigned desiredCapacity = min(MAX_STORAGE_VECTOR_LENGTH, max(BASE_VECTOR_LEN, requiredVectorLength) << 1);

    // Step 2:
    // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing on.

    void* newAllocBase;
    unsigned newStorageCapacity;
    // If the current storage array is sufficiently large (but not too large!) then just keep using it.
    if (currentCapacity > desiredCapacity && isDenseEnoughForVector(currentCapacity, requiredVectorLength)) {
        newAllocBase = storage->m_allocBase;
        newStorageCapacity = currentCapacity;
    } else {
        if (!tryFastMalloc(storageSize(desiredCapacity)).getValue(newAllocBase))
            return false;
        newStorageCapacity = desiredCapacity;
        // Currently there is no way to report to the heap that the extra capacity is shrinking!
        if (desiredCapacity > currentCapacity)
            Heap::heap(this)->reportExtraMemoryCost((desiredCapacity - currentCapacity) * sizeof(WriteBarrier<Unknown>));
    }

    // Step 3:
    // Work out where we're going to move things to.

    // Determine how much of the vector to use as pre-capacity, and how much as post-capacity.
    // If the vector had no free post-capacity (length >= m_vectorLength), don't give it any.
    // If it did, we calculate the amount that will remain based on an atomic decay - leave the
    // vector with half the post-capacity it had previously.
    unsigned postCapacity = 0;
    if (length < m_vectorLength) {
        // Atomic decay, + the post-capacity cannot be greater than what is available.
        postCapacity = min((m_vectorLength - length) >> 1, newStorageCapacity - requiredVectorLength);
        // If we're moving contents within the same allocation, the post-capacity is being reduced.
        ASSERT(newAllocBase != storage->m_allocBase || postCapacity < m_vectorLength - length);
    }

    m_vectorLength = requiredVectorLength + postCapacity;
    m_indexBias = newStorageCapacity - m_vectorLength;
    m_storage = reinterpret_cast_ptr<ArrayStorage*>(reinterpret_cast<WriteBarrier<Unknown>*>(newAllocBase) + m_indexBias);

    // Step 4:
    // Copy array data / header into their new locations, clear post-capacity & free any old allocation.

    // If this is being moved within the existing buffer of memory, we are always shifting data
    // to the right (since count > m_indexBias). As such this memmove cannot trample the header.
    memmove(m_storage->m_vector + count, storage->m_vector, sizeof(WriteBarrier<Unknown>) * usedVectorLength);
    memmove(m_storage, storage, storageSize(0));

    // Are we copying into a new allocation?
    if (newAllocBase != m_storage->m_allocBase) {
        // Free the old allocation, update m_allocBase.
        fastFree(m_storage->m_allocBase);
        m_storage->m_allocBase = newAllocBase;

        // We need to clear any entries in the vector beyond length. We only need to
        // do this if this was a new allocation, because if we're using an existing
        // allocation the post-capacity will already be cleared, and in an existing
        // allocation we can only beshrinking the amount of post capacity.
        for (unsigned i = requiredVectorLength; i < m_vectorLength; ++i)
            m_storage->m_vector[i].clear();
    }
692

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

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

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

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

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

727
    storage->m_length = newLength;
728
729

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

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

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

    --length;

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

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

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

    checkConsistency();

    return result;
}

776
777
778
// Push & putIndex are almost identical, with two small differences.
//  - we always are writing beyond the current array bounds, so it is always necessary to update m_length & m_numValuesInVector.
//  - pushing to an array of length 2^32-1 stores the property, but throws a range error.
ggaren@apple.com's avatar
ggaren@apple.com committed
779
void JSArray::push(ExecState* exec, JSValue value)
780
781
{
    checkConsistency();
782
    ArrayStorage* storage = m_storage;
783

784
785
786
787
788
    // Fast case - push within vector, always update m_length & m_numValuesInVector.
    unsigned length = storage->m_length;
    if (length < m_vectorLength) {
        storage->m_vector[length].set(exec->globalData(), this, value);
        storage->m_length = length + 1;
789
        ++storage->m_numValuesInVector;
790
791
792
793
        checkConsistency();
        return;
    }

794
795
796
797
798
799
    // Pushing to an array of length 2^32-1 stores the property, but throws a range error.
    if (UNLIKELY(storage->m_length == 0xFFFFFFFFu)) {
        methodTable()->putByIndex(this, exec, storage->m_length, value);
        // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d.
        throwError(exec, createRangeError(exec, "Invalid array length"));
        return;
800
801
    }

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

807
void JSArray::shiftCount(ExecState* exec, unsigned count)
808
809
810
{
    ASSERT(count > 0);
    
811
    ArrayStorage* storage = m_storage;
812
813
814
815
816
817
818
819
820
821
822
823
    
    unsigned oldLength = storage->m_length;
    
    if (!oldLength)
        return;
    
    if (oldLength != storage->m_numValuesInVector) {
        // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
        // which means we need to go through each entry looking for the the "empty"
        // slots and then fill them with possible properties.  See ECMA spec.
        // 15.4.4.9 steps 11 through 13.
        for (unsigned i = count; i < oldLength; ++i) {
824
            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
825
826
827
                PropertySlot slot(this);
                JSValue p = prototype();
                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
828
                    methodTable()->putByIndex(this, exec, i, slot.getValue(exec, i));
829
830
831
            }
        }

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

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

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

863
864
865
866
867
868
    if (length != storage->m_numValuesInVector) {
        // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
        // which means we need to go through each entry looking for the the "empty"
        // slots and then fill them with possible properties.  See ECMA spec.
        // 15.4.4.13 steps 8 through 10.
        for (unsigned i = 0; i < length; ++i) {
869
            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
870
871
872
                PropertySlot slot(this);
                JSValue p = prototype();
                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
873
                    methodTable()->putByIndex(this, exec, i, slot.getValue(exec, i));
874
875
876
877
            }
        }
    }
    
878
    storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
879
880
881
    
    if (m_indexBias >= count) {
        m_indexBias -= count;
882
        char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(WriteBarrier<Unknown>);
883
        memmove(newBaseStorage, storage, storageSize(0));
884
        m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
885
        m_vectorLength += count;
886
    } else if (!unshiftCountSlowCase(count)) {
887
888
889
        throwOutOfMemoryError(exec);
        return;
    }
890

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

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

    JSNonFinalObject::visitChildren(thisObject, visitor);
    
    ArrayStorage* storage = thisObject->m_storage;

    unsigned usedVectorLength = std::min(storage->m_length, thisObject->m_vectorLength);
    visitor.appendValues(storage->m_vector, usedVectorLength);

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

ggaren@apple.com's avatar
ggaren@apple.com committed
914
915
static int compareNumbersForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
916
917
    double da = static_cast<const JSValue*>(a)->asNumber();
    double db = static_cast<const JSValue*>(b)->asNumber();
ggaren@apple.com's avatar
ggaren@apple.com committed
918
919
920
    return (da > db) - (da < db);
}

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

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

932
    ArrayStorage* storage = m_storage;
933

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

    if (!lengthNotIncludingUndefined)
        return;
        
    bool allValuesAreNumbers = true;
944
    size_t size = storage->m_numValuesInVector;
ggaren@apple.com's avatar
ggaren@apple.com committed
945
    for (size_t i = 0; i < size; ++i) {
946
        if (!storage->m_vector[i].isNumber()) {
ggaren@apple.com's avatar
ggaren@apple.com committed
947
948
949
950
951
952
953
954
955