JSArray.cpp 72 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"
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
27
28
#include "CopiedSpace.h"
#include "CopiedSpaceInlineMethods.h"
29
#include "CachedCall.h"
30
#include "Error.h"
31
#include "Executable.h"
32
#include "GetterSetter.h"
darin's avatar
darin committed
33
#include "PropertyNameArray.h"
ap@webkit.org's avatar
ap@webkit.org committed
34
#include <wtf/AVLTree.h>
35
#include <wtf/Assertions.h>
36
#include <wtf/OwnPtr.h>
37
#include <Operations.h>
darin's avatar
darin committed
38

39
using namespace std;
ap@webkit.org's avatar
ap@webkit.org committed
40
using namespace WTF;
bdash's avatar
bdash committed
41

42
namespace JSC {
darin's avatar
darin committed
43

ggaren@apple.com's avatar
ggaren@apple.com committed
44
ASSERT_CLASS_FITS_IN_CELL(JSArray);
45
ASSERT_HAS_TRIVIAL_DESTRUCTOR(JSArray);
ggaren@apple.com's avatar
ggaren@apple.com committed
46

barraclough@apple.com's avatar
barraclough@apple.com committed
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 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:
//
64
65
//   * 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
66
67
68
69
70
71
72
73
74
//   * 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
75
76
77
// 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
78
79
80
81
82

// 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)
83
// 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
84
#define MAX_ARRAY_INDEX 0xFFFFFFFEU
darin's avatar
darin committed
85

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

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

102
103
104
105
106
// 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
107
108
static inline size_t storageSize(unsigned vectorLength)
{
barraclough@apple.com's avatar
barraclough@apple.com committed
109
110
111
112
    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.
113
    size_t size = (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) + (vectorLength * sizeof(WriteBarrier<Unknown>));
barraclough@apple.com's avatar
barraclough@apple.com committed
114
115
    // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
    // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
116
    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
117
118

    return size;
darin's avatar
darin committed
119
120
121
122
}

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

126
127
#if !CHECK_ARRAY_CONSISTENCY

darin@apple.com's avatar
darin@apple.com committed
128
inline void JSArray::checkConsistency(ConsistencyCheckType)
129
130
131
132
133
{
}

#endif

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

143
void JSArray::finishCreation(JSGlobalData& globalData, unsigned initialLength)
144
145
{
    Base::finishCreation(globalData);
146
147
    ASSERT(inherits(&s_info));

148
149
    unsigned initialVectorLength = BASE_VECTOR_LEN;
    unsigned initialStorageSize = storageSize(initialVectorLength);
weinig@apple.com's avatar
weinig@apple.com committed
150

151
152
153
154
155
    void* newStorage = 0;
    if (!globalData.heap.tryAllocateStorage(initialStorageSize, &newStorage))
        CRASH();
    
    m_storage = static_cast<ArrayStorage*>(newStorage);
156
    m_storage->m_allocBase = m_storage;
157
158
159
160
161
162
    m_storage->m_length = initialLength;
    m_vectorLength = initialVectorLength;
    m_storage->m_numValuesInVector = 0;
#if CHECK_ARRAY_CONSISTENCY
    m_storage->m_inCompactInitialization = false;
#endif
weinig@apple.com's avatar
weinig@apple.com committed
163

164
165
166
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
    for (size_t i = 0; i < initialVectorLength; ++i)
        vector[i].clear();
167

168
    checkConsistency();
weinig@apple.com's avatar
weinig@apple.com committed
169
170
}

171
JSArray* JSArray::tryFinishCreationUninitialized(JSGlobalData& globalData, unsigned initialLength)
darin's avatar
darin committed
172
{
173
    Base::finishCreation(globalData);
174
175
    ASSERT(inherits(&s_info));

176
177
178
179
180
181
182
    // 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);

183
184
185
186
187
    void* newStorage = 0;
    if (!globalData.heap.tryAllocateStorage(initialStorageSize, &newStorage))
        CRASH();
    
    m_storage = static_cast<ArrayStorage*>(newStorage);
188
    m_storage->m_allocBase = m_storage;
189
190
191
    m_storage->m_length = 0;
    m_vectorLength = initialVectorLength;
    m_storage->m_numValuesInVector = initialLength;
192

193
#if CHECK_ARRAY_CONSISTENCY
194
    m_storage->m_inCompactInitialization = true;
195
#endif
196

197
198
199
200
201
    WriteBarrier<Unknown>* vector = m_storage->m_vector;
    for (size_t i = initialLength; i < initialVectorLength; ++i)
        vector[i].clear();

    return this;
darin's avatar
darin committed
202
203
}

204
205
// This function can be called multiple times on the same object.
void JSArray::finalize(JSCell* cell)
darin's avatar
darin committed
206
{
207
208
209
    JSArray* thisObject = jsCast<JSArray*>(cell);
    thisObject->checkConsistency(DestructorConsistencyCheck);
    thisObject->deallocateSparseMap();
210
211
}

212
inline std::pair<SparseArrayValueMap::iterator, bool> SparseArrayValueMap::add(JSArray* array, unsigned i)
213
{
214
215
216
217
218
219
220
221
    SparseArrayEntry entry;
    std::pair<iterator, bool> result = m_map.add(i, entry);
    size_t capacity = m_map.capacity();
    if (capacity != m_reportedCapacity) {
        Heap::heap(array)->reportExtraMemoryCost((capacity - m_reportedCapacity) * (sizeof(unsigned) + sizeof(WriteBarrier<Unknown>)));
        m_reportedCapacity = capacity;
    }
    return result;
222
223
}

224
inline void SparseArrayValueMap::put(ExecState* exec, JSArray* array, unsigned i, JSValue value)
225
{
226
227
228
    // If the array is not extensible, we shouldn't get here!
    ASSERT(array->isExtensible());

229
230
    SparseArrayEntry& entry = add(array, i).first->second;

231
    if (!(entry.attributes & Accessor)) {
232
233
234
235
236
237
238
        if (entry.attributes & ReadOnly) {
            // FIXME: should throw if being called from strict mode.
            // throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
            return;
        }

        entry.set(exec->globalData(), array, value);
239
        return;
240
    }
241

242
243
244
245
246
    JSValue accessor = entry.Base::get();
    ASSERT(accessor.isGetterSetter());
    JSObject* setter = asGetterSetter(accessor)->setter();
    
    if (!setter) {
247
248
        // FIXME: should throw if being called from strict mode.
        // throwTypeError(exec, "setting a property that has only a getter");
249
        return;
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
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303

    CallData callData;
    CallType callType = setter->methodTable()->getCallData(setter, callData);
    MarkedArgumentBuffer args;
    args.append(value);
    call(exec, setter, callType, callData, array, args);
}

inline void SparseArrayEntry::get(PropertySlot& slot) const
{
    JSValue value = Base::get();
    ASSERT(value);

    if (LIKELY(!value.isGetterSetter())) {
        slot.setValue(value);
        return;
    }

    JSObject* getter = asGetterSetter(value)->getter();
    if (!getter) {
        slot.setUndefined();
        return;
    }

    slot.setGetterSlot(getter);
}

inline void SparseArrayEntry::get(PropertyDescriptor& descriptor) const
{
    descriptor.setDescriptor(Base::get(), attributes);
}

inline JSValue SparseArrayEntry::get(ExecState* exec, JSArray* array) const
{
    JSValue result = Base::get();
    ASSERT(result);

    if (LIKELY(!result.isGetterSetter()))
        return result;

    JSObject* getter = asGetterSetter(result)->getter();
    if (!getter)
        return jsUndefined();

    CallData callData;
    CallType callType = getter->methodTable()->getCallData(getter, callData);
    return call(exec, getter, callType, callData, array, exec->emptyList());
}

inline JSValue SparseArrayEntry::getNonSparseMode() const
{
    ASSERT(!attributes);
    return Base::get();
304
305
306
307
308
309
310
311
312
}

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

313
314
315
316
317
318
319
320
321
322
323
324
325
void JSArray::allocateSparseMap(JSGlobalData& globalData)
{
    m_sparseValueMap = new SparseArrayValueMap;
    globalData.heap.addFinalizer(this, finalize);
}

void JSArray::deallocateSparseMap()
{
    delete m_sparseValueMap;
    m_sparseValueMap = 0;
}

void JSArray::enterDictionaryMode(JSGlobalData& globalData)
326
327
{
    ArrayStorage* storage = m_storage;
328
    SparseArrayValueMap* map = m_sparseValueMap;
329

330
331
332
333
    if (!map) {
        allocateSparseMap(globalData);
        map = m_sparseValueMap;
    }
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348

    if (map->sparseMode())
        return;

    map->setSparseMode();

    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
    for (unsigned i = 0; i < usedVectorLength; ++i) {
        JSValue value = storage->m_vector[i].get();
        // This will always be a new entry in the map, so no need to check we can write,
        // and attributes are default so no need to set them.
        if (value)
            map->add(this, i).first->second.set(globalData, this, value);
    }

349
350
351
352
353
    void* newRawStorage = 0;
    if (!globalData.heap.tryAllocateStorage(storageSize(0), &newRawStorage))
        CRASH();
    
    ArrayStorage* newStorage = static_cast<ArrayStorage*>(newRawStorage);
354
355
356
357
358
359
360
361
362
363
364
365
    memcpy(newStorage, m_storage, storageSize(0));
    newStorage->m_allocBase = newStorage;
    m_storage = newStorage;
    m_indexBias = 0;
    m_vectorLength = 0;
}

void JSArray::putDescriptor(ExecState* exec, SparseArrayEntry* entryInMap, PropertyDescriptor& descriptor, PropertyDescriptor& oldDescriptor)
{
    if (descriptor.isDataDescriptor()) {
        if (descriptor.value())
            entryInMap->set(exec->globalData(), this, descriptor.value());
366
367
        else if (oldDescriptor.isAccessorDescriptor())
            entryInMap->set(exec->globalData(), this, jsUndefined());
368
        entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor) & ~Accessor;
369
370
371
372
373
        return;
    }

    if (descriptor.isAccessorDescriptor()) {
        JSObject* getter = 0;
374
375
376
377
        if (descriptor.getterPresent())
            getter = descriptor.getterObject();
        else if (oldDescriptor.isAccessorDescriptor())
            getter = oldDescriptor.getterObject();
378
        JSObject* setter = 0;
379
380
381
382
        if (descriptor.setterPresent())
            setter = descriptor.setterObject();
        else if (oldDescriptor.isAccessorDescriptor())
            setter = oldDescriptor.setterObject();
383
384
385
386
387
388
389
390

        GetterSetter* accessor = GetterSetter::create(exec);
        if (getter)
            accessor->setGetter(exec->globalData(), getter);
        if (setter)
            accessor->setSetter(exec->globalData(), setter);

        entryInMap->set(exec->globalData(), this, accessor);
391
        entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor) & ~ReadOnly;
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
        return;
    }

    ASSERT(descriptor.isGenericDescriptor());
    entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor);
}

static bool reject(ExecState* exec, bool throwException, const char* message)
{
    if (throwException)
        throwTypeError(exec, message);
    return false;
}

// Defined in ES5.1 8.12.9
bool JSArray::defineOwnNumericProperty(ExecState* exec, unsigned index, PropertyDescriptor& descriptor, bool throwException)
{
    ASSERT(index != 0xFFFFFFFF);

    if (!inSparseMode()) {
        // Fast case: we're putting a regular property to a regular array
        // FIXME: this will pessimistically assume that if attributes are missing then they'll default to false
        // – however if the property currently exists missing attributes will override from their current 'true'
        // state (i.e. defineOwnProperty could be used to set a value without needing to entering 'SparseMode').
        if (!descriptor.attributes()) {
            ASSERT(!descriptor.isAccessorDescriptor());
            putByIndex(this, exec, index, descriptor.value());
            return true;
        }

422
        enterDictionaryMode(exec->globalData());
423
424
    }

425
    SparseArrayValueMap* map = m_sparseValueMap;
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
    ASSERT(map);

    // 1. Let current be the result of calling the [[GetOwnProperty]] internal method of O with property name P.
    std::pair<SparseArrayValueMap::iterator, bool> result = map->add(this, index);
    SparseArrayEntry* entryInMap = &result.first->second;

    // 2. Let extensible be the value of the [[Extensible]] internal property of O.
    // 3. If current is undefined and extensible is false, then Reject.
    // 4. If current is undefined and extensible is true, then
    if (result.second) {
        if (!isExtensible()) {
            map->remove(result.first);
            return reject(exec, throwException, "Attempting to define property on object that is not extensible.");
        }

        // 4.a. If IsGenericDescriptor(Desc) or IsDataDescriptor(Desc) is true, then create an own data property
        // named P of object O whose [[Value]], [[Writable]], [[Enumerable]] and [[Configurable]] attribute values
        // are described by Desc. If the value of an attribute field of Desc is absent, the attribute of the newly
        // created property is set to its default value.
        // 4.b. Else, Desc must be an accessor Property Descriptor so, create an own accessor property named P of
        // object O whose [[Get]], [[Set]], [[Enumerable]] and [[Configurable]] attribute values are described by
        // Desc. If the value of an attribute field of Desc is absent, the attribute of the newly created property
        // is set to its default value.
        // 4.c. Return true.

        PropertyDescriptor defaults;
        entryInMap->setWithoutWriteBarrier(jsUndefined());
        entryInMap->attributes = DontDelete | DontEnum | ReadOnly;
        entryInMap->get(defaults);

        putDescriptor(exec, entryInMap, descriptor, defaults);
        if (index >= m_storage->m_length)
            m_storage->m_length = index + 1;
        return true;
    }

    // 5. Return true, if every field in Desc is absent.
    // 6. Return true, if every field in Desc also occurs in current and the value of every field in Desc is the same value as the corresponding field in current when compared using the SameValue algorithm (9.12).
    PropertyDescriptor current;
    entryInMap->get(current);
    if (descriptor.isEmpty() || descriptor.equalTo(exec, current))
        return true;

    // 7. If the [[Configurable]] field of current is false then
    if (!current.configurable()) {
        // 7.a. Reject, if the [[Configurable]] field of Desc is true.
472
        if (descriptor.configurablePresent() && descriptor.configurable())
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
            return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property.");
        // 7.b. Reject, if the [[Enumerable]] field of Desc is present and the [[Enumerable]] fields of current and Desc are the Boolean negation of each other.
        if (descriptor.enumerablePresent() && current.enumerable() != descriptor.enumerable())
            return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property.");
    }

    // 8. If IsGenericDescriptor(Desc) is true, then no further validation is required.
    if (!descriptor.isGenericDescriptor()) {
        // 9. Else, if IsDataDescriptor(current) and IsDataDescriptor(Desc) have different results, then
        if (current.isDataDescriptor() != descriptor.isDataDescriptor()) {
            // 9.a. Reject, if the [[Configurable]] field of current is false.
            if (!current.configurable())
                return reject(exec, throwException, "Attempting to change access mechanism for an unconfigurable property.");
            // 9.b. If IsDataDescriptor(current) is true, then convert the property named P of object O from a
            // data property to an accessor property. Preserve the existing values of the converted property‘s
            // [[Configurable]] and [[Enumerable]] attributes and set the rest of the property‘s attributes to
            // their default values.
            // 9.c. Else, convert the property named P of object O from an accessor property to a data property.
            // Preserve the existing values of the converted property‘s [[Configurable]] and [[Enumerable]]
            // attributes and set the rest of the property‘s attributes to their default values.
        } else if (current.isDataDescriptor() && descriptor.isDataDescriptor()) {
            // 10. Else, if IsDataDescriptor(current) and IsDataDescriptor(Desc) are both true, then
            // 10.a. If the [[Configurable]] field of current is false, then
            if (!current.configurable() && !current.writable()) {
                // 10.a.i. Reject, if the [[Writable]] field of current is false and the [[Writable]] field of Desc is true.
                if (descriptor.writable())
                    return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property.");
                // 10.a.ii. If the [[Writable]] field of current is false, then
                // 10.a.ii.1. Reject, if the [[Value]] field of Desc is present and SameValue(Desc.[[Value]], current.[[Value]]) is false.
                if (descriptor.value() && !sameValue(exec, descriptor.value(), current.value()))
                    return reject(exec, throwException, "Attempting to change value of a readonly property.");
            }
            // 10.b. else, the [[Configurable]] field of current is true, so any change is acceptable.
        } else {
507
            ASSERT(current.isAccessorDescriptor() && current.getterPresent() && current.setterPresent());
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
            // 11. Else, IsAccessorDescriptor(current) and IsAccessorDescriptor(Desc) are both true so, if the [[Configurable]] field of current is false, then
            if (!current.configurable()) {
                // 11.i. Reject, if the [[Set]] field of Desc is present and SameValue(Desc.[[Set]], current.[[Set]]) is false.
                if (descriptor.setterPresent() && descriptor.setter() != current.setter())
                    return reject(exec, throwException, "Attempting to change the setter of an unconfigurable property.");
                // 11.ii. Reject, if the [[Get]] field of Desc is present and SameValue(Desc.[[Get]], current.[[Get]]) is false.
                if (descriptor.getterPresent() && descriptor.getter() != current.getter())
                    return reject(exec, throwException, "Attempting to change the getter of an unconfigurable property.");
            }
        }
    }

    // 12. For each attribute field of Desc that is present, set the correspondingly named attribute of the property named P of object O to the value of the field.
    putDescriptor(exec, entryInMap, descriptor, current);
    // 13. Return true.
    return true;
}

void JSArray::setLengthWritable(ExecState* exec, bool writable)
{
    ASSERT(isLengthWritable() || !writable);
    if (!isLengthWritable() || writable)
        return;

532
    enterDictionaryMode(exec->globalData());
533

534
    SparseArrayValueMap* map = m_sparseValueMap;
535
536
537
538
539
540
541
542
543
544
545
546
547
    ASSERT(map);
    map->setLengthIsReadOnly();
}

// Defined in ES5.1 15.4.5.1
bool JSArray::defineOwnProperty(JSObject* object, ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor, bool throwException)
{
    JSArray* array = static_cast<JSArray*>(object);

    // 3. If P is "length", then
    if (propertyName == exec->propertyNames().length) {
        // All paths through length definition call the default [[DefineOwnProperty]], hence:
        // from ES5.1 8.12.9 7.a.
548
        if (descriptor.configurablePresent() && descriptor.configurable())
549
550
            return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property.");
        // from ES5.1 8.12.9 7.b.
551
        if (descriptor.enumerablePresent() && descriptor.enumerable())
552
553
554
555
556
557
558
            return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property.");

        // a. If the [[Value]] field of Desc is absent, then
        // a.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", Desc, and Throw as arguments.
        if (descriptor.isAccessorDescriptor())
            return reject(exec, throwException, "Attempting to change access mechanism for an unconfigurable property.");
        // from ES5.1 8.12.9 10.a.
559
        if (!array->isLengthWritable() && descriptor.writablePresent() && descriptor.writable())
560
561
562
            return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property.");
        // This descriptor is either just making length read-only, or changing nothing!
        if (!descriptor.value()) {
563
564
            if (descriptor.writablePresent())
                array->setLengthWritable(exec, descriptor.writable());
565
566
567
568
569
570
571
572
573
574
575
576
577
578
            return true;
        }
        
        // b. Let newLenDesc be a copy of Desc.
        // c. Let newLen be ToUint32(Desc.[[Value]]).
        unsigned newLen = descriptor.value().toUInt32(exec);
        // d. If newLen is not equal to ToNumber( Desc.[[Value]]), throw a RangeError exception.
        if (newLen != descriptor.value().toNumber(exec)) {
            throwError(exec, createRangeError(exec, "Invalid array length"));
            return false;
        }

        // Based on SameValue check in 8.12.9, this is always okay.
        if (newLen == array->length()) {
579
580
            if (descriptor.writablePresent())
                array->setLengthWritable(exec, descriptor.writable());
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
            return true;
        }

        // e. Set newLenDesc.[[Value] to newLen.
        // f. If newLen >= oldLen, then
        // f.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments.
        // g. Reject if oldLenDesc.[[Writable]] is false.
        if (!array->isLengthWritable())
            return reject(exec, throwException, "Attempting to change value of a readonly property.");
        
        // h. If newLenDesc.[[Writable]] is absent or has the value true, let newWritable be true.
        // i. Else,
        // i.i. Need to defer setting the [[Writable]] attribute to false in case any elements cannot be deleted.
        // i.ii. Let newWritable be false.
        // i.iii. Set newLenDesc.[[Writable] to true.
        // j. Let succeeded be the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments.
        // k. If succeeded is false, return false.
        // l. While newLen < oldLen repeat,
        // l.i. Set oldLen to oldLen – 1.
        // l.ii. Let deleteSucceeded be the result of calling the [[Delete]] internal method of A passing ToString(oldLen) and false as arguments.
        // l.iii. If deleteSucceeded is false, then
602
        if (!array->setLength(exec, newLen, throwException)) {
603
604
605
606
            // 1. Set newLenDesc.[[Value] to oldLen+1.
            // 2. If newWritable is false, set newLenDesc.[[Writable] to false.
            // 3. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and false as arguments.
            // 4. Reject.
607
608
            if (descriptor.writablePresent())
                array->setLengthWritable(exec, descriptor.writable());
609
610
611
612
            return false;
        }

        // m. If newWritable is false, then
613
614
615
616
617
        // i. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length",
        //    Property Descriptor{[[Writable]]: false}, and false as arguments. This call will always
        //    return true.
        if (descriptor.writablePresent())
            array->setLengthWritable(exec, descriptor.writable());
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
        // n. Return true.
        return true;
    }

    // 4. Else if P is an array index (15.4), then
    bool isArrayIndex;
    // a. Let index be ToUint32(P).
    unsigned index = propertyName.toArrayIndex(isArrayIndex);
    if (isArrayIndex) {
        // b. Reject if index >= oldLen and oldLenDesc.[[Writable]] is false.
        if (index >= array->length() && !array->isLengthWritable())
            return reject(exec, throwException, "Attempting to define numeric property on array with non-writable length property.");
        // c. Let succeeded be the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing P, Desc, and false as arguments.
        // d. Reject if succeeded is false.
        // e. If index >= oldLen
        // e.i. Set oldLenDesc.[[Value]] to index + 1.
        // e.ii. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", oldLenDesc, and false as arguments. This call will always return true.
        // f. Return true.
        return array->defineOwnNumericProperty(exec, index, descriptor, throwException);
    }

    return JSObject::defineOwnProperty(object, exec, propertyName, descriptor, throwException);
}

642
bool JSArray::getOwnPropertySlotByIndex(JSCell* cell, ExecState* exec, unsigned i, PropertySlot& slot)
643
{
644
    JSArray* thisObject = jsCast<JSArray*>(cell);
645
    ArrayStorage* storage = thisObject->m_storage;
646

ggaren@apple.com's avatar
ggaren@apple.com committed
647
    if (i >= storage->m_length) {
barraclough@apple.com's avatar
barraclough@apple.com committed
648
        if (i > MAX_ARRAY_INDEX)
649
            return thisObject->methodTable()->getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
650
651
652
        return false;
    }

653
    if (i < thisObject->m_vectorLength) {
654
655
656
        JSValue value = storage->m_vector[i].get();
        if (value) {
            slot.setValue(value);
darin's avatar
darin committed
657
658
            return true;
        }
659
    } else if (SparseArrayValueMap* map = thisObject->m_sparseValueMap) {
660
661
        SparseArrayValueMap::iterator it = map->find(i);
        if (it != map->notFound()) {
662
            it->second.get(slot);
663
            return true;
darin's avatar
darin committed
664
665
666
        }
    }

667
    return JSObject::getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
darin's avatar
darin committed
668
669
}

670
671
bool JSArray::getOwnPropertySlot(JSCell* cell, ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
{
672
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
673
    if (propertyName == exec->propertyNames().length) {
674
        slot.setValue(jsNumber(thisObject->length()));
darin's avatar
darin committed
675
676
677
678
        return true;
    }

    bool isArrayIndex;
679
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
680
    if (isArrayIndex)
681
        return JSArray::getOwnPropertySlotByIndex(thisObject, exec, i, slot);
darin's avatar
darin committed
682

683
    return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
darin's avatar
darin committed
684
685
}

686
bool JSArray::getOwnPropertyDescriptor(JSObject* object, ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
687
{
688
    JSArray* thisObject = jsCast<JSArray*>(object);
689
    if (propertyName == exec->propertyNames().length) {
690
        descriptor.setDescriptor(jsNumber(thisObject->length()), DontDelete | DontEnum);
691
692
        return true;
    }
693

694
    ArrayStorage* storage = thisObject->m_storage;
695
696
    
    bool isArrayIndex;
697
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
698
    if (isArrayIndex) {
699
        if (i >= storage->m_length)
700
            return false;
701
        if (i < thisObject->m_vectorLength) {
702
            WriteBarrier<Unknown>& value = storage->m_vector[i];
703
            if (value) {
704
                descriptor.setDescriptor(value.get(), 0);
705
706
                return true;
            }
707
        } else if (SparseArrayValueMap* map = thisObject->m_sparseValueMap) {
708
709
            SparseArrayValueMap::iterator it = map->find(i);
            if (it != map->notFound()) {
710
                it->second.get(descriptor);
711
                return true;
712
713
714
            }
        }
    }
715
    return JSObject::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor);
716
717
}

718
719
720
// ECMA 15.4.5.1
void JSArray::put(JSCell* cell, ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
{
721
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
722
    bool isArrayIndex;
723
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
724
    if (isArrayIndex) {
725
        putByIndex(thisObject, exec, i, value);
darin's avatar
darin committed
726
727
728
729
        return;
    }

    if (propertyName == exec->propertyNames().length) {
weinig@apple.com's avatar
weinig@apple.com committed
730
731
        unsigned newLength = value.toUInt32(exec);
        if (value.toNumber(exec) != static_cast<double>(newLength)) {
732
            throwError(exec, createRangeError(exec, "Invalid array length"));
darin's avatar
darin committed
733
734
            return;
        }
735
        thisObject->setLength(exec, newLength, slot.isStrictMode());
darin's avatar
darin committed
736
737
738
        return;
    }

739
    JSObject::put(thisObject, exec, propertyName, value, slot);
darin's avatar
darin committed
740
741
}

742
void JSArray::putByIndex(JSCell* cell, ExecState* exec, unsigned i, JSValue value)
743
{
744
    JSArray* thisObject = jsCast<JSArray*>(cell);
745
746
747
    thisObject->checkConsistency();

    ArrayStorage* storage = thisObject->m_storage;
748

749
    // Fast case - store to the vector.
750
    if (i < thisObject->m_vectorLength) {
751
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
752
753
754
755
756
757
758
759
760
761
        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;

762
763
        valueSlot.set(exec->globalData(), thisObject, value);
        thisObject->checkConsistency();
darin's avatar
darin committed
764
765
766
        return;
    }

767
768
769
770
771
772
773
774
    // 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.
775
    thisObject->putByIndexBeyondVectorLength(exec, i, value);
776
    thisObject->checkConsistency();
777
778
}

779
NEVER_INLINE void JSArray::putByIndexBeyondVectorLength(ExecState* exec, unsigned i, JSValue value)
780
{
781
782
    JSGlobalData& globalData = exec->globalData();

783
    // i should be a valid array index that is outside of the current vector.
784
    ASSERT(i >= m_vectorLength);
785
    ASSERT(i <= MAX_ARRAY_INDEX);
786

787
    ArrayStorage* storage = m_storage;
788
    SparseArrayValueMap* map = m_sparseValueMap;
ap@webkit.org's avatar
ap@webkit.org committed
789

790
791
    // First, handle cases where we don't currently have a sparse map.
    if (LIKELY(!map)) {
792
793
794
        // If the array is not extensible, we should have entered dictionary mode, and created the spare map.
        ASSERT(isExtensible());
    
795
796
797
798
        // Update m_length if necessary.
        if (i >= storage->m_length)
            storage->m_length = i + 1;

799
        // Check that it is sensible to still be using a vector, and then try to grow the vector.
800
        if (LIKELY((isDenseEnoughForVector(i, storage->m_numValuesInVector)) && increaseVectorLength(globalData, i + 1))) {
801
            // success! - reread m_storage since it has likely been reallocated, and store to the vector.
802
            storage = m_storage;
803
            storage->m_vector[i].set(globalData, this, value);
804
            ++storage->m_numValuesInVector;
805
            return;
darin's avatar
darin committed
806
        }
807
        // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
808
809
        allocateSparseMap(exec->globalData());
        map = m_sparseValueMap;
810
        map->put(exec, this, i, value);
811
        return;
darin's avatar
darin committed
812
813
    }

814
815
816
817
    // Update m_length if necessary.
    unsigned length = storage->m_length;
    if (i >= length) {
        // Prohibit growing the array if length is not writable.
818
        if (map->lengthIsReadOnly() || !isExtensible()) {
819
820
821
822
823
824
825
            // FIXME: should throw in strict mode.
            return;
        }
        length = i + 1;
        storage->m_length = length;
    }

826
827
828
    // 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();
829
    if (map->sparseMode() || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(exec->globalData(), length)) {
830
        map->put(exec, this, i, value);
barraclough@apple.com's avatar
barraclough@apple.com committed
831
832
        return;
    }
darin's avatar
darin committed
833

834
    // Reread m_storage afterincreaseVectorLength, update m_numValuesInVector.
835
    storage = m_storage;
836
    storage->m_numValuesInVector = numValuesInArray;
837

838
839
840
841
    // 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)
842
        vector[it->first].set(globalData, this, it->second.getNonSparseMode());
843
    deallocateSparseMap();
844
845
846
847
848
849

    // 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
850
851
}

852
853
bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, const Identifier& propertyName)
{
854
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
855
    bool isArrayIndex;
856
    unsigned i = propertyName.toArrayIndex(isArrayIndex);
darin's avatar
darin committed
857
    if (isArrayIndex)
858
        return thisObject->methodTable()->deletePropertyByIndex(thisObject, exec, i);
darin's avatar
darin committed
859
860
861
862

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

863
    return JSObject::deleteProperty(thisObject, exec, propertyName);
darin's avatar
darin committed
864
865
}

866
bool JSArray::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
867
{
868
    JSArray* thisObject = jsCast<JSArray*>(cell);
869
870
    thisObject->checkConsistency();

871
872
873
    if (i > MAX_ARRAY_INDEX)
        return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, i));

874
    ArrayStorage* storage = thisObject->m_storage;
875
    
876
    if (i < thisObject->m_vectorLength) {
877
        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
878
879
880
        if (valueSlot) {
            valueSlot.clear();
            --storage->m_numValuesInVector;
881
        }
882
    } else if (SparseArrayValueMap* map = thisObject->m_sparseValueMap) {
883
884
        SparseArrayValueMap::iterator it = map->find(i);
        if (it != map->notFound()) {
885
886
            if (it->second.attributes & DontDelete)
                return false;
887
            map->remove(it);
darin's avatar
darin committed
888
889
890
        }
    }

891
    thisObject->checkConsistency();
892
893
    return true;
}
894

895
896
static int compareKeysForQSort(const void* a, const void* b)
{
897
898
    unsigned da = *static_cast<const unsigned*>(a);
    unsigned db = *static_cast<const unsigned*>(b);
899
    return (da > db) - (da < db);
darin's avatar
darin committed
900
901
}

902
void JSArray::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
darin's avatar
darin committed
903
{
904
    JSArray* thisObject = jsCast<JSArray*>(object);
darin's avatar
darin committed
905
    // FIXME: Filling PropertyNameArray with an identifier for every integer
906
907
    // 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
908

909
    ArrayStorage* storage = thisObject->m_storage;
910
    
911
    unsigned usedVectorLength = min(storage->m_length, thisObject->m_vectorLength);
darin's avatar
darin committed
912
    for (unsigned i = 0; i < usedVectorLength; ++i) {
913
        if (storage->m_vector[i])
ap@webkit.org's avatar
ap@webkit.org committed
914
            propertyNames.add(Identifier::from(exec, i));
darin's avatar
darin committed
915
916
    }

917
    if (SparseArrayValueMap* map = thisObject->m_sparseValueMap) {
918
        Vector<unsigned> keys;
919
920
        keys.reserveCapacity(map->size());
        
921
        SparseArrayValueMap::const_iterator end = map->end();
922
923
        for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
            if (mode == IncludeDontEnumProperties || !(it->second.attributes & DontEnum))
924
                keys.append(static_cast<unsigned>(it->first));
925
926
        }

927
        qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
928
        for (unsigned i = 0; i < keys.size(); ++i)
929
            propertyNames.add(Identifier::from(exec, keys[i]));
darin's avatar
darin committed
930
    }
931

932
933
934
    if (mode == IncludeDontEnumProperties)
        propertyNames.add(exec->propertyNames().length);

935
    JSObject::getOwnPropertyNames(thisObject, exec, propertyNames, mode);
darin's avatar
darin committed
936
937
}

938
939
940
941
942
ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
{
    ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);

    unsigned increasedLength;
943
    unsigned maxInitLength = min(m_storage->m_length, 100000U);
944

945
946
    if (desiredLength < maxInitLength)
        increasedLength = maxInitLength;
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
    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);
}

965
bool JSArray::increaseVectorLength(JSGlobalData& globalData, unsigned newLength)
darin's avatar
darin committed
966
{
ap@webkit.org's avatar
ap@webkit.org committed
967
968
    // 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.
969
970
    if (newLength > MAX_STORAGE_VECTOR_LENGTH)
        return false;
ap@webkit.org's avatar
ap@webkit.org committed
971

972
    ArrayStorage* storage = m_storage;
darin's avatar
darin committed
973

974
    unsigned vectorLength = m_vectorLength;
darin's avatar
darin committed
975
    ASSERT(newLength > vectorLength);
976
    unsigned newVectorLength = getNewVectorLength(newLength);
darin's avatar
darin committed
977

978
979
    // Fast case - there is no precapacity. In these cases a realloc makes sense.
    if (LIKELY(!m_indexBias)) {
980
981
        void* newStorage = storage->m_allocBase;
        if (!globalData.heap.tryReallocateStorage(&newStorage, storageSize(vectorLength), storageSize(newVectorLength)))
982
            return false;
983

984
985
986
        storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(newStorage));
        m_storage->m_allocBase = newStorage;
        ASSERT(m_storage->m_allocBase);
987

988
989
990
991
992
993
994
995
996
997
998
999
1000
        WriteBarrier<Unknown>* vector = storage->m_vector;
        for (unsigned i = vectorLength; i < newVectorLength; ++i)
            vector[i].clear();

        m_vectorLength = newVectorLength;
        
        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;
1001
1002
    void* newAllocBase = 0;
    if (!globalData.heap.tryAllocateStorage(storageSize(newStorageCapacity), &newAllocBase))    
1003
1004
1005
        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);
ap@webkit.org's avatar
ap@webkit.org committed
1006

1007
    m_vectorLength = newVectorLength;
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
    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.
    m_storage->m_allocBase = newAllocBase;
darin's avatar
darin committed
1018

1019
1020
    return true;
}
darin's avatar
darin committed
1021

1022
// This method makes room in the vector, but leaves the new space uncleared.
1023
bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, unsigned count)
1024
{
1025
1026
    // If not, we should have handled this on the fast path.
    ASSERT(count > m_indexBias);
1027

1028
    ArrayStorage* storage = m_storage;
1029

1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
    // 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)
1042
        return false;
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
    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.

1054
    void* newAllocBase = 0;
1055
1056
1057
1058
1059
1060
    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 {
1061
        if (!globalData.heap.tryAllocateStorage(storageSize(desiredCapacity), &newAllocBase))