← Back to branch summary

~ubuntu-branches/ubuntu/raring/qtwebkit-source/raring-proposed

« back to all changes in this revision

Viewing changes to Source/JavaScriptCore/runtime/JSArray.cpp

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2013-02-18 14:24:18 UTC
  • Revision ID: package-import@ubuntu.com-20130218142418-eon0jmjg3nj438uy
Tags: upstream-2.3
Import upstream version 2.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
Source/JavaScriptCore/runtime/JSArray.cpp
 
1
/*
 
2
 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
 
3
 *  Copyright (C) 2003, 2007, 2008, 2009, 2012 Apple Inc. All rights reserved.
 
4
 *  Copyright (C) 2003 Peter Kelly (pmk@post.com)
 
5
 *  Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
 
6
 *
 
7
 *  This library is free software; you can redistribute it and/or
 
8
 *  modify it under the terms of the GNU Lesser General Public
 
9
 *  License as published by the Free Software Foundation; either
 
10
 *  version 2 of the License, or (at your option) any later version.
 
11
 *
 
12
 *  This library is distributed in the hope that it will be useful,
 
13
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
14
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
15
 *  Lesser General Public License for more details.
 
16
 *
 
17
 *  You should have received a copy of the GNU Lesser General Public
 
18
 *  License along with this library; if not, write to the Free Software
 
19
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 
20
 *
 
21
 */
 
22
 
 
23
#include "config.h"
 
24
#include "JSArray.h"
 
25
 
 
26
#include "ArrayPrototype.h"
 
27
#include "ButterflyInlines.h"
 
28
#include "CachedCall.h"
 
29
#include "CopiedSpace.h"
 
30
#include "CopiedSpaceInlines.h"
 
31
#include "Error.h"
 
32
#include "Executable.h"
 
33
#include "GetterSetter.h"
 
34
#include "IndexingHeaderInlines.h"
 
35
#include "PropertyNameArray.h"
 
36
#include "Reject.h"
 
37
#include <wtf/AVLTree.h>
 
38
#include <wtf/Assertions.h>
 
39
#include <wtf/OwnPtr.h>
 
40
#include <Operations.h>
 
41
 
 
42
using namespace std;
 
43
using namespace WTF;
 
44
 
 
45
namespace JSC {
 
46
 
 
47
ASSERT_HAS_TRIVIAL_DESTRUCTOR(JSArray);
 
48
 
 
49
const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0, CREATE_METHOD_TABLE(JSArray)};
 
50
 
 
51
Butterfly* createArrayButterflyInDictionaryIndexingMode(JSGlobalData& globalData, unsigned initialLength)
 
52
{
 
53
    Butterfly* butterfly = Butterfly::create(
 
54
        globalData, 0, 0, true, IndexingHeader(), ArrayStorage::sizeFor(0));
 
55
    ArrayStorage* storage = butterfly->arrayStorage();
 
56
    storage->setLength(initialLength);
 
57
    storage->setVectorLength(0);
 
58
    storage->m_indexBias = 0;
 
59
    storage->m_sparseMap.clear();
 
60
    storage->m_numValuesInVector = 0;
 
61
    return butterfly;
 
62
}
 
63
 
 
64
void JSArray::setLengthWritable(ExecState* exec, bool writable)
 
65
{
 
66
    ASSERT(isLengthWritable() || !writable);
 
67
    if (!isLengthWritable() || writable)
 
68
        return;
 
69
 
 
70
    enterDictionaryIndexingMode(exec->globalData());
 
71
 
 
72
    SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get();
 
73
    ASSERT(map);
 
74
    map->setLengthIsReadOnly();
 
75
}
 
76
 
 
77
// Defined in ES5.1 15.4.5.1
 
78
bool JSArray::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor, bool throwException)
 
79
{
 
80
    JSArray* array = jsCast<JSArray*>(object);
 
81
 
 
82
    // 3. If P is "length", then
 
83
    if (propertyName == exec->propertyNames().length) {
 
84
        // All paths through length definition call the default [[DefineOwnProperty]], hence:
 
85
        // from ES5.1 8.12.9 7.a.
 
86
        if (descriptor.configurablePresent() && descriptor.configurable())
 
87
            return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property.");
 
88
        // from ES5.1 8.12.9 7.b.
 
89
        if (descriptor.enumerablePresent() && descriptor.enumerable())
 
90
            return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property.");
 
91
 
 
92
        // a. If the [[Value]] field of Desc is absent, then
 
93
        // a.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", Desc, and Throw as arguments.
 
94
        if (descriptor.isAccessorDescriptor())
 
95
            return reject(exec, throwException, "Attempting to change access mechanism for an unconfigurable property.");
 
96
        // from ES5.1 8.12.9 10.a.
 
97
        if (!array->isLengthWritable() && descriptor.writablePresent() && descriptor.writable())
 
98
            return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property.");
 
99
        // This descriptor is either just making length read-only, or changing nothing!
 
100
        if (!descriptor.value()) {
 
101
            if (descriptor.writablePresent())
 
102
                array->setLengthWritable(exec, descriptor.writable());
 
103
            return true;
 
104
        }
 
105
        
 
106
        // b. Let newLenDesc be a copy of Desc.
 
107
        // c. Let newLen be ToUint32(Desc.[[Value]]).
 
108
        unsigned newLen = descriptor.value().toUInt32(exec);
 
109
        // d. If newLen is not equal to ToNumber( Desc.[[Value]]), throw a RangeError exception.
 
110
        if (newLen != descriptor.value().toNumber(exec)) {
 
111
            throwError(exec, createRangeError(exec, "Invalid array length"));
 
112
            return false;
 
113
        }
 
114
 
 
115
        // Based on SameValue check in 8.12.9, this is always okay.
 
116
        if (newLen == array->length()) {
 
117
            if (descriptor.writablePresent())
 
118
                array->setLengthWritable(exec, descriptor.writable());
 
119
            return true;
 
120
        }
 
121
 
 
122
        // e. Set newLenDesc.[[Value] to newLen.
 
123
        // f. If newLen >= oldLen, then
 
124
        // f.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments.
 
125
        // g. Reject if oldLenDesc.[[Writable]] is false.
 
126
        if (!array->isLengthWritable())
 
127
            return reject(exec, throwException, "Attempting to change value of a readonly property.");
 
128
        
 
129
        // h. If newLenDesc.[[Writable]] is absent or has the value true, let newWritable be true.
 
130
        // i. Else,
 
131
        // i.i. Need to defer setting the [[Writable]] attribute to false in case any elements cannot be deleted.
 
132
        // i.ii. Let newWritable be false.
 
133
        // i.iii. Set newLenDesc.[[Writable] to true.
 
134
        // 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.
 
135
        // k. If succeeded is false, return false.
 
136
        // l. While newLen < oldLen repeat,
 
137
        // l.i. Set oldLen to oldLen – 1.
 
138
        // l.ii. Let deleteSucceeded be the result of calling the [[Delete]] internal method of A passing ToString(oldLen) and false as arguments.
 
139
        // l.iii. If deleteSucceeded is false, then
 
140
        if (!array->setLength(exec, newLen, throwException)) {
 
141
            // 1. Set newLenDesc.[[Value] to oldLen+1.
 
142
            // 2. If newWritable is false, set newLenDesc.[[Writable] to false.
 
143
            // 3. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and false as arguments.
 
144
            // 4. Reject.
 
145
            if (descriptor.writablePresent())
 
146
                array->setLengthWritable(exec, descriptor.writable());
 
147
            return false;
 
148
        }
 
149
 
 
150
        // m. If newWritable is false, then
 
151
        // i. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length",
 
152
        //    Property Descriptor{[[Writable]]: false}, and false as arguments. This call will always
 
153
        //    return true.
 
154
        if (descriptor.writablePresent())
 
155
            array->setLengthWritable(exec, descriptor.writable());
 
156
        // n. Return true.
 
157
        return true;
 
158
    }
 
159
 
 
160
    // 4. Else if P is an array index (15.4), then
 
161
    // a. Let index be ToUint32(P).
 
162
    unsigned index = propertyName.asIndex();
 
163
    if (index != PropertyName::NotAnIndex) {
 
164
        // b. Reject if index >= oldLen and oldLenDesc.[[Writable]] is false.
 
165
        if (index >= array->length() && !array->isLengthWritable())
 
166
            return reject(exec, throwException, "Attempting to define numeric property on array with non-writable length property.");
 
167
        // 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.
 
168
        // d. Reject if succeeded is false.
 
169
        // e. If index >= oldLen
 
170
        // e.i. Set oldLenDesc.[[Value]] to index + 1.
 
171
        // 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.
 
172
        // f. Return true.
 
173
        return array->defineOwnIndexedProperty(exec, index, descriptor, throwException);
 
174
    }
 
175
 
 
176
    return array->JSObject::defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException);
 
177
}
 
178
 
 
179
bool JSArray::getOwnPropertySlot(JSCell* cell, ExecState* exec, PropertyName propertyName, PropertySlot& slot)
 
180
{
 
181
    JSArray* thisObject = jsCast<JSArray*>(cell);
 
182
    if (propertyName == exec->propertyNames().length) {
 
183
        slot.setValue(jsNumber(thisObject->length()));
 
184
        return true;
 
185
    }
 
186
 
 
187
    return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
 
188
}
 
189
 
 
190
bool JSArray::getOwnPropertyDescriptor(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor)
 
191
{
 
192
    JSArray* thisObject = jsCast<JSArray*>(object);
 
193
    if (propertyName == exec->propertyNames().length) {
 
194
        descriptor.setDescriptor(jsNumber(thisObject->length()), thisObject->isLengthWritable() ? DontDelete | DontEnum : DontDelete | DontEnum | ReadOnly);
 
195
        return true;
 
196
    }
 
197
 
 
198
    return JSObject::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor);
 
199
}
 
200
 
 
201
// ECMA 15.4.5.1
 
202
void JSArray::put(JSCell* cell, ExecState* exec, PropertyName propertyName, JSValue value, PutPropertySlot& slot)
 
203
{
 
204
    JSArray* thisObject = jsCast<JSArray*>(cell);
 
205
 
 
206
    if (propertyName == exec->propertyNames().length) {
 
207
        unsigned newLength = value.toUInt32(exec);
 
208
        if (value.toNumber(exec) != static_cast<double>(newLength)) {
 
209
            throwError(exec, createRangeError(exec, ASCIILiteral("Invalid array length")));
 
210
            return;
 
211
        }
 
212
        thisObject->setLength(exec, newLength, slot.isStrictMode());
 
213
        return;
 
214
    }
 
215
 
 
216
    JSObject::put(thisObject, exec, propertyName, value, slot);
 
217
}
 
218
 
 
219
bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName)
 
220
{
 
221
    JSArray* thisObject = jsCast<JSArray*>(cell);
 
222
 
 
223
    if (propertyName == exec->propertyNames().length)
 
224
        return false;
 
225
 
 
226
    return JSObject::deleteProperty(thisObject, exec, propertyName);
 
227
}
 
228
 
 
229
static int compareKeysForQSort(const void* a, const void* b)
 
230
{
 
231
    unsigned da = *static_cast<const unsigned*>(a);
 
232
    unsigned db = *static_cast<const unsigned*>(b);
 
233
    return (da > db) - (da < db);
 
234
}
 
235
 
 
236
void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
 
237
{
 
238
    JSArray* thisObject = jsCast<JSArray*>(object);
 
239
 
 
240
    if (mode == IncludeDontEnumProperties)
 
241
        propertyNames.add(exec->propertyNames().length);
 
242
 
 
243
    JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode);
 
244
}
 
245
 
 
246
// This method makes room in the vector, but leaves the new space for count slots uncleared.
 
247
bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, bool addToFront, unsigned count)
 
248
{
 
249
    ArrayStorage* storage = ensureArrayStorage(globalData);
 
250
    Butterfly* butterfly = storage->butterfly();
 
251
    unsigned propertyCapacity = structure()->outOfLineCapacity();
 
252
    unsigned propertySize = structure()->outOfLineSize();
 
253
 
 
254
    // If not, we should have handled this on the fast path.
 
255
    ASSERT(!addToFront || count > storage->m_indexBias);
 
256
 
 
257
    // Step 1:
 
258
    // Gather 4 key metrics:
 
259
    //  * usedVectorLength - how many entries are currently in the vector (conservative estimate - fewer may be in use in sparse vectors).
 
260
    //  * requiredVectorLength - how many entries are will there be in the vector, after allocating space for 'count' more.
 
261
    //  * currentCapacity - what is the current size of the vector, including any pre-capacity.
 
262
    //  * desiredCapacity - how large should we like to grow the vector to - based on 2x requiredVectorLength.
 
263
 
 
264
    unsigned length = storage->length();
 
265
    unsigned usedVectorLength = min(storage->vectorLength(), length);
 
266
    ASSERT(usedVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
 
267
    // Check that required vector length is possible, in an overflow-safe fashion.
 
268
    if (count > MAX_STORAGE_VECTOR_LENGTH - usedVectorLength)
 
269
        return false;
 
270
    unsigned requiredVectorLength = usedVectorLength + count;
 
271
    ASSERT(requiredVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
 
272
    // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH.
 
273
    ASSERT(storage->vectorLength() <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - storage->vectorLength()) >= storage->m_indexBias);
 
274
    unsigned currentCapacity = storage->vectorLength() + storage->m_indexBias;
 
275
    // The calculation of desiredCapacity won't overflow, due to the range of MAX_STORAGE_VECTOR_LENGTH.
 
276
    unsigned desiredCapacity = min(MAX_STORAGE_VECTOR_LENGTH, max(BASE_VECTOR_LEN, requiredVectorLength) << 1);
 
277
 
 
278
    // Step 2:
 
279
    // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing one.
 
280
 
 
281
    void* newAllocBase = 0;
 
282
    unsigned newStorageCapacity;
 
283
    // If the current storage array is sufficiently large (but not too large!) then just keep using it.
 
284
    if (currentCapacity > desiredCapacity && isDenseEnoughForVector(currentCapacity, requiredVectorLength)) {
 
285
        newAllocBase = butterfly->base(structure());
 
286
        newStorageCapacity = currentCapacity;
 
287
    } else {
 
288
        size_t newSize = Butterfly::totalSize(0, propertyCapacity, true, ArrayStorage::sizeFor(desiredCapacity));
 
289
        if (!globalData.heap.tryAllocateStorage(newSize, &newAllocBase))
 
290
            return false;
 
291
        newStorageCapacity = desiredCapacity;
 
292
    }
 
293
 
 
294
    // Step 3:
 
295
    // Work out where we're going to move things to.
 
296
 
 
297
    // Determine how much of the vector to use as pre-capacity, and how much as post-capacity.
 
298
    // If we're adding to the end, we'll add all the new space to the end.
 
299
    // If the vector had no free post-capacity (length >= m_vectorLength), don't give it any.
 
300
    // If it did, we calculate the amount that will remain based on an atomic decay - leave the
 
301
    // vector with half the post-capacity it had previously.
 
302
    unsigned postCapacity = 0;
 
303
    if (!addToFront)
 
304
        postCapacity = max(newStorageCapacity - requiredVectorLength, count);
 
305
    else if (length < storage->vectorLength()) {
 
306
        // Atomic decay, + the post-capacity cannot be greater than what is available.
 
307
        postCapacity = min((storage->vectorLength() - length) >> 1, newStorageCapacity - requiredVectorLength);
 
308
        // If we're moving contents within the same allocation, the post-capacity is being reduced.
 
309
        ASSERT(newAllocBase != butterfly->base(structure()) || postCapacity < storage->vectorLength() - length);
 
310
    }
 
311
 
 
312
    unsigned newVectorLength = requiredVectorLength + postCapacity;
 
313
    unsigned newIndexBias = newStorageCapacity - newVectorLength;
 
314
 
 
315
    Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity);
 
316
 
 
317
    if (addToFront) {
 
318
        ASSERT(count + usedVectorLength <= newVectorLength);
 
319
        memmove(newButterfly->arrayStorage()->m_vector + count, storage->m_vector, sizeof(JSValue) * usedVectorLength);
 
320
        memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
 
321
    } else if ((newAllocBase != butterfly->base(structure())) || (newIndexBias != storage->m_indexBias)) {
 
322
        memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
 
323
        memmove(newButterfly->arrayStorage()->m_vector, storage->m_vector, sizeof(JSValue) * usedVectorLength);
 
324
 
 
325
        WriteBarrier<Unknown>* newVector = newButterfly->arrayStorage()->m_vector;
 
326
        for (unsigned i = requiredVectorLength; i < newVectorLength; i++)
 
327
            newVector[i].clear();
 
328
    }
 
329
 
 
330
    newButterfly->arrayStorage()->setVectorLength(newVectorLength);
 
331
    newButterfly->arrayStorage()->m_indexBias = newIndexBias;
 
332
 
 
333
    m_butterfly = newButterfly;
 
334
 
 
335
    return true;
 
336
}
 
337
 
 
338
bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, bool throwException, ArrayStorage* storage)
 
339
{
 
340
    unsigned length = storage->length();
 
341
 
 
342
    // If the length is read only then we enter sparse mode, so should enter the following 'if'.
 
343
    ASSERT(isLengthWritable() || storage->m_sparseMap);
 
344
 
 
345
    if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
 
346
        // Fail if the length is not writable.
 
347
        if (map->lengthIsReadOnly())
 
348
            return reject(exec, throwException, StrictModeReadonlyPropertyWriteError);
 
349
 
 
350
        if (newLength < length) {
 
351
            // Copy any keys we might be interested in into a vector.
 
352
            Vector<unsigned> keys;
 
353
            keys.reserveCapacity(min(map->size(), static_cast<size_t>(length - newLength)));
 
354
            SparseArrayValueMap::const_iterator end = map->end();
 
355
            for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
 
356
                unsigned index = static_cast<unsigned>(it->key);
 
357
                if (index < length && index >= newLength)
 
358
                    keys.append(index);
 
359
            }
 
360
 
 
361
            // Check if the array is in sparse mode. If so there may be non-configurable
 
362
            // properties, so we have to perform deletion with caution, if not we can
 
363
            // delete values in any order.
 
364
            if (map->sparseMode()) {
 
365
                qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
 
366
                unsigned i = keys.size();
 
367
                while (i) {
 
368
                    unsigned index = keys[--i];
 
369
                    SparseArrayValueMap::iterator it = map->find(index);
 
370
                    ASSERT(it != map->notFound());
 
371
                    if (it->value.attributes & DontDelete) {
 
372
                        storage->setLength(index + 1);
 
373
                        return reject(exec, throwException, "Unable to delete property.");
 
374
                    }
 
375
                    map->remove(it);
 
376
                }
 
377
            } else {
 
378
                for (unsigned i = 0; i < keys.size(); ++i)
 
379
                    map->remove(keys[i]);
 
380
                if (map->isEmpty())
 
381
                    deallocateSparseIndexMap();
 
382
            }
 
383
        }
 
384
    }
 
385
 
 
386
    if (newLength < length) {
 
387
        // Delete properties from the vector.
 
388
        unsigned usedVectorLength = min(length, storage->vectorLength());
 
389
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
 
390
            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
 
391
            bool hadValue = valueSlot;
 
392
            valueSlot.clear();
 
393
            storage->m_numValuesInVector -= hadValue;
 
394
        }
 
395
    }
 
396
 
 
397
    storage->setLength(newLength);
 
398
 
 
399
    return true;
 
400
}
 
401
 
 
402
bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
 
403
{
 
404
    switch (structure()->indexingType()) {
 
405
    case ArrayClass:
 
406
        if (!newLength)
 
407
            return true;
 
408
        if (newLength >= MIN_SPARSE_ARRAY_INDEX) {
 
409
            return setLengthWithArrayStorage(
 
410
                exec, newLength, throwException,
 
411
                convertContiguousToArrayStorage(exec->globalData()));
 
412
        }
 
413
        createInitialUndecided(exec->globalData(), newLength);
 
414
        return true;
 
415
        
 
416
    case ArrayWithUndecided:
 
417
    case ArrayWithInt32:
 
418
    case ArrayWithDouble:
 
419
    case ArrayWithContiguous:
 
420
        if (newLength == m_butterfly->publicLength())
 
421
            return true;
 
422
        if (newLength >= MAX_ARRAY_INDEX // This case ensures that we can do fast push.
 
423
            || (newLength >= MIN_SPARSE_ARRAY_INDEX
 
424
                && !isDenseEnoughForVector(newLength, countElements()))) {
 
425
            return setLengthWithArrayStorage(
 
426
                exec, newLength, throwException,
 
427
                ensureArrayStorage(exec->globalData()));
 
428
        }
 
429
        if (newLength > m_butterfly->publicLength()) {
 
430
            ensureLength(exec->globalData(), newLength);
 
431
            return true;
 
432
        }
 
433
        if (structure()->indexingType() == ArrayWithDouble) {
 
434
            for (unsigned i = m_butterfly->publicLength(); i-- > newLength;)
 
435
                m_butterfly->contiguousDouble()[i] = QNaN;
 
436
        } else {
 
437
            for (unsigned i = m_butterfly->publicLength(); i-- > newLength;)
 
438
                m_butterfly->contiguous()[i].clear();
 
439
        }
 
440
        m_butterfly->setPublicLength(newLength);
 
441
        return true;
 
442
        
 
443
    case ArrayWithArrayStorage:
 
444
    case ArrayWithSlowPutArrayStorage:
 
445
        return setLengthWithArrayStorage(exec, newLength, throwException, arrayStorage());
 
446
        
 
447
    default:
 
448
        CRASH();
 
449
        return false;
 
450
    }
 
451
}
 
452
 
 
453
JSValue JSArray::pop(ExecState* exec)
 
454
{
 
455
    switch (structure()->indexingType()) {
 
456
    case ArrayClass:
 
457
        return jsUndefined();
 
458
        
 
459
    case ArrayWithUndecided:
 
460
        if (!m_butterfly->publicLength())
 
461
            return jsUndefined();
 
462
        // We have nothing but holes. So, drop down to the slow version.
 
463
        break;
 
464
        
 
465
    case ArrayWithInt32:
 
466
    case ArrayWithContiguous: {
 
467
        unsigned length = m_butterfly->publicLength();
 
468
        
 
469
        if (!length--)
 
470
            return jsUndefined();
 
471
        
 
472
        ASSERT(length < m_butterfly->vectorLength());
 
473
        JSValue value = m_butterfly->contiguous()[length].get();
 
474
        if (value) {
 
475
            m_butterfly->contiguous()[length].clear();
 
476
            m_butterfly->setPublicLength(length);
 
477
            return value;
 
478
        }
 
479
        break;
 
480
    }
 
481
        
 
482
    case ArrayWithDouble: {
 
483
        unsigned length = m_butterfly->publicLength();
 
484
        
 
485
        if (!length--)
 
486
            return jsUndefined();
 
487
        
 
488
        ASSERT(length < m_butterfly->vectorLength());
 
489
        double value = m_butterfly->contiguousDouble()[length];
 
490
        if (value == value) {
 
491
            m_butterfly->contiguousDouble()[length] = QNaN;
 
492
            m_butterfly->setPublicLength(length);
 
493
            return JSValue(JSValue::EncodeAsDouble, value);
 
494
        }
 
495
        break;
 
496
    }
 
497
        
 
498
    case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
 
499
        ArrayStorage* storage = m_butterfly->arrayStorage();
 
500
    
 
501
        unsigned length = storage->length();
 
502
        if (!length) {
 
503
            if (!isLengthWritable())
 
504
                throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
 
505
            return jsUndefined();
 
506
        }
 
507
 
 
508
        unsigned index = length - 1;
 
509
        if (index < storage->vectorLength()) {
 
510
            WriteBarrier<Unknown>& valueSlot = storage->m_vector[index];
 
511
            if (valueSlot) {
 
512
                --storage->m_numValuesInVector;
 
513
                JSValue element = valueSlot.get();
 
514
                valueSlot.clear();
 
515
            
 
516
                ASSERT(isLengthWritable());
 
517
                storage->setLength(index);
 
518
                return element;
 
519
            }
 
520
        }
 
521
        break;
 
522
    }
 
523
        
 
524
    default:
 
525
        CRASH();
 
526
        return JSValue();
 
527
    }
 
528
    
 
529
    unsigned index = getArrayLength() - 1;
 
530
    // Let element be the result of calling the [[Get]] internal method of O with argument indx.
 
531
    JSValue element = get(exec, index);
 
532
    if (exec->hadException())
 
533
        return jsUndefined();
 
534
    // Call the [[Delete]] internal method of O with arguments indx and true.
 
535
    if (!deletePropertyByIndex(this, exec, index)) {
 
536
        throwTypeError(exec, "Unable to delete property.");
 
537
        return jsUndefined();
 
538
    }
 
539
    // Call the [[Put]] internal method of O with arguments "length", indx, and true.
 
540
    setLength(exec, index, true);
 
541
    // Return element.
 
542
    return element;
 
543
}
 
544
 
 
545
// Push & putIndex are almost identical, with two small differences.
 
546
//  - we always are writing beyond the current array bounds, so it is always necessary to update m_length & m_numValuesInVector.
 
547
//  - pushing to an array of length 2^32-1 stores the property, but throws a range error.
 
548
void JSArray::push(ExecState* exec, JSValue value)
 
549
{
 
550
    switch (structure()->indexingType()) {
 
551
    case ArrayClass: {
 
552
        createInitialUndecided(exec->globalData(), 0);
 
553
        // Fall through.
 
554
    }
 
555
        
 
556
    case ArrayWithUndecided: {
 
557
        convertUndecidedForValue(exec->globalData(), value);
 
558
        push(exec, value);
 
559
        return;
 
560
    }
 
561
        
 
562
    case ArrayWithInt32: {
 
563
        if (!value.isInt32()) {
 
564
            convertInt32ForValue(exec->globalData(), value);
 
565
            push(exec, value);
 
566
            return;
 
567
        }
 
568
 
 
569
        unsigned length = m_butterfly->publicLength();
 
570
        ASSERT(length <= m_butterfly->vectorLength());
 
571
        if (length < m_butterfly->vectorLength()) {
 
572
            m_butterfly->contiguousInt32()[length].setWithoutWriteBarrier(value);
 
573
            m_butterfly->setPublicLength(length + 1);
 
574
            return;
 
575
        }
 
576
        
 
577
        if (length > MAX_ARRAY_INDEX) {
 
578
            methodTable()->putByIndex(this, exec, length, value, true);
 
579
            if (!exec->hadException())
 
580
                throwError(exec, createRangeError(exec, "Invalid array length"));
 
581
            return;
 
582
        }
 
583
        
 
584
        putByIndexBeyondVectorLengthWithoutAttributes<Int32Shape>(exec, length, value);
 
585
        return;
 
586
    }
 
587
 
 
588
    case ArrayWithContiguous: {
 
589
        unsigned length = m_butterfly->publicLength();
 
590
        ASSERT(length <= m_butterfly->vectorLength());
 
591
        if (length < m_butterfly->vectorLength()) {
 
592
            m_butterfly->contiguous()[length].set(exec->globalData(), this, value);
 
593
            m_butterfly->setPublicLength(length + 1);
 
594
            return;
 
595
        }
 
596
        
 
597
        if (length > MAX_ARRAY_INDEX) {
 
598
            methodTable()->putByIndex(this, exec, length, value, true);
 
599
            if (!exec->hadException())
 
600
                throwError(exec, createRangeError(exec, "Invalid array length"));
 
601
            return;
 
602
        }
 
603
        
 
604
        putByIndexBeyondVectorLengthWithoutAttributes<ContiguousShape>(exec, length, value);
 
605
        return;
 
606
    }
 
607
        
 
608
    case ArrayWithDouble: {
 
609
        if (!value.isNumber()) {
 
610
            convertDoubleToContiguous(exec->globalData());
 
611
            push(exec, value);
 
612
            return;
 
613
        }
 
614
        double valueAsDouble = value.asNumber();
 
615
        if (valueAsDouble != valueAsDouble) {
 
616
            convertDoubleToContiguous(exec->globalData());
 
617
            push(exec, value);
 
618
            return;
 
619
        }
 
620
 
 
621
        unsigned length = m_butterfly->publicLength();
 
622
        ASSERT(length <= m_butterfly->vectorLength());
 
623
        if (length < m_butterfly->vectorLength()) {
 
624
            m_butterfly->contiguousDouble()[length] = valueAsDouble;
 
625
            m_butterfly->setPublicLength(length + 1);
 
626
            return;
 
627
        }
 
628
        
 
629
        if (length > MAX_ARRAY_INDEX) {
 
630
            methodTable()->putByIndex(this, exec, length, value, true);
 
631
            if (!exec->hadException())
 
632
                throwError(exec, createRangeError(exec, "Invalid array length"));
 
633
            return;
 
634
        }
 
635
        
 
636
        putByIndexBeyondVectorLengthWithoutAttributes<DoubleShape>(exec, length, value);
 
637
        break;
 
638
    }
 
639
        
 
640
    case ArrayWithSlowPutArrayStorage: {
 
641
        unsigned oldLength = length();
 
642
        if (attemptToInterceptPutByIndexOnHole(exec, oldLength, value, true)) {
 
643
            if (!exec->hadException() && oldLength < 0xFFFFFFFFu)
 
644
                setLength(exec, oldLength + 1, true);
 
645
            return;
 
646
        }
 
647
        // Fall through.
 
648
    }
 
649
        
 
650
    case ArrayWithArrayStorage: {
 
651
        ArrayStorage* storage = m_butterfly->arrayStorage();
 
652
 
 
653
        // Fast case - push within vector, always update m_length & m_numValuesInVector.
 
654
        unsigned length = storage->length();
 
655
        if (length < storage->vectorLength()) {
 
656
            storage->m_vector[length].set(exec->globalData(), this, value);
 
657
            storage->setLength(length + 1);
 
658
            ++storage->m_numValuesInVector;
 
659
            return;
 
660
        }
 
661
 
 
662
        // Pushing to an array of invalid length (2^31-1) stores the property, but throws a range error.
 
663
        if (storage->length() > MAX_ARRAY_INDEX) {
 
664
            methodTable()->putByIndex(this, exec, storage->length(), value, true);
 
665
            // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d.
 
666
            if (!exec->hadException())
 
667
                throwError(exec, createRangeError(exec, "Invalid array length"));
 
668
            return;
 
669
        }
 
670
 
 
671
        // Handled the same as putIndex.
 
672
        putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage);
 
673
        break;
 
674
    }
 
675
        
 
676
    default:
 
677
        ASSERT_NOT_REACHED();
 
678
    }
 
679
}
 
680
 
 
681
bool JSArray::shiftCountWithArrayStorage(unsigned startIndex, unsigned count, ArrayStorage* storage)
 
682
{
 
683
    unsigned oldLength = storage->length();
 
684
    ASSERT(count <= oldLength);
 
685
    
 
686
    // If the array contains holes or is otherwise in an abnormal state,
 
687
    // use the generic algorithm in ArrayPrototype.
 
688
    if (oldLength != storage->m_numValuesInVector || inSparseIndexingMode() || shouldUseSlowPut(structure()->indexingType()))
 
689
        return false;
 
690
 
 
691
    if (!oldLength)
 
692
        return true;
 
693
    
 
694
    unsigned length = oldLength - count;
 
695
    
 
696
    storage->m_numValuesInVector -= count;
 
697
    storage->setLength(length);
 
698
    
 
699
    unsigned vectorLength = storage->vectorLength();
 
700
    if (!vectorLength)
 
701
        return true;
 
702
    
 
703
    if (startIndex >= vectorLength)
 
704
        return true;
 
705
    
 
706
    if (startIndex + count > vectorLength)
 
707
        count = vectorLength - startIndex;
 
708
    
 
709
    unsigned usedVectorLength = min(vectorLength, oldLength);
 
710
    
 
711
    vectorLength -= count;
 
712
    storage->setVectorLength(vectorLength);
 
713
    
 
714
    if (vectorLength) {
 
715
        if (startIndex < usedVectorLength - (startIndex + count)) {
 
716
            if (startIndex) {
 
717
                memmove(
 
718
                    storage->m_vector + count,
 
719
                    storage->m_vector,
 
720
                    sizeof(JSValue) * startIndex);
 
721
            }
 
722
            m_butterfly = m_butterfly->shift(structure(), count);
 
723
            storage = m_butterfly->arrayStorage();
 
724
            storage->m_indexBias += count;
 
725
        } else {
 
726
            memmove(
 
727
                storage->m_vector + startIndex,
 
728
                storage->m_vector + startIndex + count,
 
729
                sizeof(JSValue) * (usedVectorLength - (startIndex + count)));
 
730
            for (unsigned i = usedVectorLength - count; i < usedVectorLength; ++i)
 
731
                storage->m_vector[i].clear();
 
732
        }
 
733
    }
 
734
    return true;
 
735
}
 
736
 
 
737
bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
 
738
{
 
739
    ASSERT(count > 0);
 
740
    
 
741
    switch (structure()->indexingType()) {
 
742
    case ArrayClass:
 
743
        return true;
 
744
        
 
745
    case ArrayWithUndecided:
 
746
        // Don't handle this because it's confusing and it shouldn't come up.
 
747
        return false;
 
748
        
 
749
    case ArrayWithInt32:
 
750
    case ArrayWithContiguous: {
 
751
        unsigned oldLength = m_butterfly->publicLength();
 
752
        ASSERT(count <= oldLength);
 
753
        
 
754
        // We may have to walk the entire array to do the shift. We're willing to do
 
755
        // so only if it's not horribly slow.
 
756
        if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
 
757
            return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->globalData()));
 
758
        
 
759
        unsigned end = oldLength - count;
 
760
        for (unsigned i = startIndex; i < end; ++i) {
 
761
            // Storing to a hole is fine since we're still having a good time. But reading
 
762
            // from a hole is totally not fine, since we might have to read from the proto
 
763
            // chain.
 
764
            JSValue v = m_butterfly->contiguous()[i + count].get();
 
765
            if (UNLIKELY(!v)) {
 
766
                // The purpose of this path is to ensure that we don't make the same
 
767
                // mistake in the future: shiftCountWithArrayStorage() can't do anything
 
768
                // about holes (at least for now), but it can detect them quickly. So
 
769
                // we convert to array storage and then allow the array storage path to
 
770
                // figure it out.
 
771
                return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->globalData()));
 
772
            }
 
773
            // No need for a barrier since we're just moving data around in the same vector.
 
774
            // This is in line with our standing assumption that we won't have a deletion
 
775
            // barrier.
 
776
            m_butterfly->contiguous()[i].setWithoutWriteBarrier(v);
 
777
        }
 
778
        for (unsigned i = end; i < oldLength; ++i)
 
779
            m_butterfly->contiguous()[i].clear();
 
780
        
 
781
        m_butterfly->setPublicLength(oldLength - count);
 
782
        return true;
 
783
    }
 
784
        
 
785
    case ArrayWithDouble: {
 
786
        unsigned oldLength = m_butterfly->publicLength();
 
787
        ASSERT(count <= oldLength);
 
788
        
 
789
        // We may have to walk the entire array to do the shift. We're willing to do
 
790
        // so only if it's not horribly slow.
 
791
        if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
 
792
            return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->globalData()));
 
793
        
 
794
        unsigned end = oldLength - count;
 
795
        for (unsigned i = startIndex; i < end; ++i) {
 
796
            // Storing to a hole is fine since we're still having a good time. But reading
 
797
            // from a hole is totally not fine, since we might have to read from the proto
 
798
            // chain.
 
799
            double v = m_butterfly->contiguousDouble()[i + count];
 
800
            if (UNLIKELY(v != v)) {
 
801
                // The purpose of this path is to ensure that we don't make the same
 
802
                // mistake in the future: shiftCountWithArrayStorage() can't do anything
 
803
                // about holes (at least for now), but it can detect them quickly. So
 
804
                // we convert to array storage and then allow the array storage path to
 
805
                // figure it out.
 
806
                return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->globalData()));
 
807
            }
 
808
            // No need for a barrier since we're just moving data around in the same vector.
 
809
            // This is in line with our standing assumption that we won't have a deletion
 
810
            // barrier.
 
811
            m_butterfly->contiguousDouble()[i] = v;
 
812
        }
 
813
        for (unsigned i = end; i < oldLength; ++i)
 
814
            m_butterfly->contiguousDouble()[i] = QNaN;
 
815
        
 
816
        m_butterfly->setPublicLength(oldLength - count);
 
817
        return true;
 
818
    }
 
819
        
 
820
    case ArrayWithArrayStorage:
 
821
    case ArrayWithSlowPutArrayStorage:
 
822
        return shiftCountWithArrayStorage(startIndex, count, arrayStorage());
 
823
        
 
824
    default:
 
825
        CRASH();
 
826
        return false;
 
827
    }
 
828
}
 
829
 
 
830
// Returns true if the unshift can be handled, false to fallback.    
 
831
bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, unsigned count, ArrayStorage* storage)
 
832
{
 
833
    unsigned length = storage->length();
 
834
 
 
835
    ASSERT(startIndex <= length);
 
836
 
 
837
    // If the array contains holes or is otherwise in an abnormal state,
 
838
    // use the generic algorithm in ArrayPrototype.
 
839
    if (length != storage->m_numValuesInVector || storage->inSparseMode() || shouldUseSlowPut(structure()->indexingType()))
 
840
        return false;
 
841
 
 
842
    bool moveFront = !startIndex || startIndex < length / 2;
 
843
 
 
844
    unsigned vectorLength = storage->vectorLength();
 
845
 
 
846
    if (moveFront && storage->m_indexBias >= count) {
 
847
        m_butterfly = storage->butterfly()->unshift(structure(), count);
 
848
        storage = m_butterfly->arrayStorage();
 
849
        storage->m_indexBias -= count;
 
850
        storage->setVectorLength(vectorLength + count);
 
851
    } else if (!moveFront && vectorLength - length >= count)
 
852
        storage = storage->butterfly()->arrayStorage();
 
853
    else if (unshiftCountSlowCase(exec->globalData(), moveFront, count))
 
854
        storage = arrayStorage();
 
855
    else {
 
856
        throwOutOfMemoryError(exec);
 
857
        return true;
 
858
    }
 
859
 
 
860
    WriteBarrier<Unknown>* vector = storage->m_vector;
 
861
 
 
862
    if (startIndex) {
 
863
        if (moveFront)
 
864
            memmove(vector, vector + count, startIndex * sizeof(JSValue));
 
865
        else if (length - startIndex)
 
866
            memmove(vector + startIndex + count, vector + startIndex, (length - startIndex) * sizeof(JSValue));
 
867
    }
 
868
 
 
869
    for (unsigned i = 0; i < count; i++)
 
870
        vector[i + startIndex].clear();
 
871
    return true;
 
872
}
 
873
 
 
874
bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
 
875
{
 
876
    switch (structure()->indexingType()) {
 
877
    case ArrayClass:
 
878
    case ArrayWithUndecided:
 
879
        // We could handle this. But it shouldn't ever come up, so we won't.
 
880
        return false;
 
881
 
 
882
    case ArrayWithInt32:
 
883
    case ArrayWithContiguous: {
 
884
        unsigned oldLength = m_butterfly->publicLength();
 
885
        
 
886
        // We may have to walk the entire array to do the unshift. We're willing to do so
 
887
        // only if it's not horribly slow.
 
888
        if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
 
889
            return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->globalData()));
 
890
        
 
891
        ensureLength(exec->globalData(), oldLength + count);
 
892
        
 
893
        for (unsigned i = oldLength; i-- > startIndex;) {
 
894
            JSValue v = m_butterfly->contiguous()[i].get();
 
895
            if (UNLIKELY(!v))
 
896
                return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->globalData()));
 
897
            m_butterfly->contiguous()[i + count].setWithoutWriteBarrier(v);
 
898
        }
 
899
        
 
900
        // NOTE: we're leaving being garbage in the part of the array that we shifted out
 
901
        // of. This is fine because the caller is required to store over that area, and
 
902
        // in contiguous mode storing into a hole is guaranteed to behave exactly the same
 
903
        // as storing over an existing element.
 
904
        
 
905
        return true;
 
906
    }
 
907
        
 
908
    case ArrayWithDouble: {
 
909
        unsigned oldLength = m_butterfly->publicLength();
 
910
        
 
911
        // We may have to walk the entire array to do the unshift. We're willing to do so
 
912
        // only if it's not horribly slow.
 
913
        if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
 
914
            return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->globalData()));
 
915
        
 
916
        ensureLength(exec->globalData(), oldLength + count);
 
917
        
 
918
        for (unsigned i = oldLength; i-- > startIndex;) {
 
919
            double v = m_butterfly->contiguousDouble()[i];
 
920
            if (UNLIKELY(v != v))
 
921
                return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->globalData()));
 
922
            m_butterfly->contiguousDouble()[i + count] = v;
 
923
        }
 
924
        
 
925
        // NOTE: we're leaving being garbage in the part of the array that we shifted out
 
926
        // of. This is fine because the caller is required to store over that area, and
 
927
        // in contiguous mode storing into a hole is guaranteed to behave exactly the same
 
928
        // as storing over an existing element.
 
929
        
 
930
        return true;
 
931
    }
 
932
        
 
933
    case ArrayWithArrayStorage:
 
934
    case ArrayWithSlowPutArrayStorage:
 
935
        return unshiftCountWithArrayStorage(exec, startIndex, count, arrayStorage());
 
936
        
 
937
    default:
 
938
        CRASH();
 
939
        return false;
 
940
    }
 
941
}
 
942
 
 
943
static int compareNumbersForQSortWithInt32(const void* a, const void* b)
 
944
{
 
945
    int32_t ia = static_cast<const JSValue*>(a)->asInt32();
 
946
    int32_t ib = static_cast<const JSValue*>(b)->asInt32();
 
947
    return ia - ib;
 
948
}
 
949
 
 
950
static int compareNumbersForQSortWithDouble(const void* a, const void* b)
 
951
{
 
952
    double da = *static_cast<const double*>(a);
 
953
    double db = *static_cast<const double*>(b);
 
954
    return (da > db) - (da < db);
 
955
}
 
956
 
 
957
static int compareNumbersForQSort(const void* a, const void* b)
 
958
{
 
959
    double da = static_cast<const JSValue*>(a)->asNumber();
 
960
    double db = static_cast<const JSValue*>(b)->asNumber();
 
961
    return (da > db) - (da < db);
 
962
}
 
963
 
 
964
static int compareByStringPairForQSort(const void* a, const void* b)
 
965
{
 
966
    const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
 
967
    const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
 
968
    return codePointCompare(va->second, vb->second);
 
969
}
 
970
 
 
971
template<IndexingType indexingType>
 
972
void JSArray::sortNumericVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
 
973
{
 
974
    ASSERT(indexingType == ArrayWithInt32 || indexingType == ArrayWithDouble || indexingType == ArrayWithContiguous || indexingType == ArrayWithArrayStorage);
 
975
    
 
976
    unsigned lengthNotIncludingUndefined;
 
977
    unsigned newRelevantLength;
 
978
    compactForSorting<indexingType>(
 
979
        lengthNotIncludingUndefined,
 
980
        newRelevantLength);
 
981
    
 
982
    WriteBarrier<Unknown>* data = indexingData<indexingType>();
 
983
    
 
984
    if (indexingType == ArrayWithArrayStorage && arrayStorage()->m_sparseMap.get()) {
 
985
        throwOutOfMemoryError(exec);
 
986
        return;
 
987
    }
 
988
    
 
989
    if (!lengthNotIncludingUndefined)
 
990
        return;
 
991
    
 
992
    bool allValuesAreNumbers = true;
 
993
    switch (indexingType) {
 
994
    case ArrayWithInt32:
 
995
    case ArrayWithDouble:
 
996
        break;
 
997
        
 
998
    default:
 
999
        for (size_t i = 0; i < newRelevantLength; ++i) {
 
1000
            if (!data[i].isNumber()) {
 
1001
                allValuesAreNumbers = false;
 
1002
                break;
 
1003
            }
 
1004
        }
 
1005
        break;
 
1006
    }
 
1007
    
 
1008
    if (!allValuesAreNumbers)
 
1009
        return sort(exec, compareFunction, callType, callData);
 
1010
    
 
1011
    // For numeric comparison, which is fast, qsort is faster than mergesort. We
 
1012
    // also don't require mergesort's stability, since there's no user visible
 
1013
    // side-effect from swapping the order of equal primitive values.
 
1014
    int (*compare)(const void*, const void*);
 
1015
    switch (indexingType) {
 
1016
    case ArrayWithInt32:
 
1017
        compare = compareNumbersForQSortWithInt32;
 
1018
        break;
 
1019
        
 
1020
    case ArrayWithDouble:
 
1021
        compare = compareNumbersForQSortWithDouble;
 
1022
        ASSERT(sizeof(WriteBarrier<Unknown>) == sizeof(double));
 
1023
        break;
 
1024
        
 
1025
    default:
 
1026
        compare = compareNumbersForQSort;
 
1027
        break;
 
1028
    }
 
1029
    
 
1030
    qsort(data, newRelevantLength, sizeof(WriteBarrier<Unknown>), compare);
 
1031
    return;
 
1032
}
 
1033
 
 
1034
void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
 
1035
{
 
1036
    ASSERT(!inSparseIndexingMode());
 
1037
 
 
1038
    switch (structure()->indexingType()) {
 
1039
    case ArrayClass:
 
1040
        return;
 
1041
        
 
1042
    case ArrayWithInt32:
 
1043
        sortNumericVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
 
1044
        break;
 
1045
        
 
1046
    case ArrayWithDouble:
 
1047
        sortNumericVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
 
1048
        break;
 
1049
        
 
1050
    case ArrayWithContiguous:
 
1051
        sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
 
1052
        return;
 
1053
 
 
1054
    case ArrayWithArrayStorage:
 
1055
        sortNumericVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
 
1056
        return;
 
1057
        
 
1058
    default:
 
1059
        CRASH();
 
1060
        return;
 
1061
    }
 
1062
}
 
1063
 
 
1064
template<IndexingType indexingType>
 
1065
void JSArray::sortCompactedVector(ExecState* exec, void* begin, unsigned relevantLength)
 
1066
{
 
1067
    if (!relevantLength)
 
1068
        return;
 
1069
    
 
1070
    JSGlobalData& globalData = exec->globalData();
 
1071
 
 
1072
    // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
 
1073
    // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
 
1074
    // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
 
1075
    // random or otherwise changing results, effectively making compare function inconsistent.
 
1076
        
 
1077
    Vector<ValueStringPair> values(relevantLength);
 
1078
    if (!values.begin()) {
 
1079
        throwOutOfMemoryError(exec);
 
1080
        return;
 
1081
    }
 
1082
        
 
1083
    Heap::heap(this)->pushTempSortVector(&values);
 
1084
        
 
1085
    bool isSortingPrimitiveValues = true;
 
1086
    switch (indexingType) {
 
1087
    case ArrayWithInt32:
 
1088
        for (size_t i = 0; i < relevantLength; i++) {
 
1089
            JSValue value = static_cast<WriteBarrier<Unknown>*>(begin)[i].get();
 
1090
            ASSERT(value.isInt32());
 
1091
            values[i].first = value;
 
1092
        }
 
1093
        break;
 
1094
        
 
1095
    case ArrayWithDouble:
 
1096
        for (size_t i = 0; i < relevantLength; i++) {
 
1097
            double value = static_cast<double*>(begin)[i];
 
1098
            ASSERT(value == value);
 
1099
            values[i].first = JSValue(JSValue::EncodeAsDouble, value);
 
1100
        }
 
1101
        break;
 
1102
        
 
1103
    default:
 
1104
        for (size_t i = 0; i < relevantLength; i++) {
 
1105
            JSValue value = static_cast<WriteBarrier<Unknown>*>(begin)[i].get();
 
1106
            ASSERT(!value.isUndefined());
 
1107
            values[i].first = value;
 
1108
            isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();
 
1109
        }
 
1110
        break;
 
1111
    }
 
1112
        
 
1113
    // FIXME: The following loop continues to call toString on subsequent values even after
 
1114
    // a toString call raises an exception.
 
1115
        
 
1116
    for (size_t i = 0; i < relevantLength; i++)
 
1117
        values[i].second = values[i].first.toWTFStringInline(exec);
 
1118
        
 
1119
    if (exec->hadException()) {
 
1120
        Heap::heap(this)->popTempSortVector(&values);
 
1121
        return;
 
1122
    }
 
1123
        
 
1124
    // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
 
1125
    // than O(N log N).
 
1126
        
 
1127
#if HAVE(MERGESORT)
 
1128
    if (isSortingPrimitiveValues)
 
1129
        qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 
1130
    else
 
1131
        mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 
1132
#else
 
1133
    // FIXME: The qsort library function is likely to not be a stable sort.
 
1134
    // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
 
1135
    qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 
1136
#endif
 
1137
    
 
1138
    // If the toString function changed the length of the array or vector storage,
 
1139
    // increase the length to handle the orignal number of actual values.
 
1140
    switch (indexingType) {
 
1141
    case ArrayWithInt32:
 
1142
    case ArrayWithDouble:
 
1143
    case ArrayWithContiguous:
 
1144
        ensureLength(globalData, relevantLength);
 
1145
        break;
 
1146
        
 
1147
    case ArrayWithArrayStorage:
 
1148
        if (arrayStorage()->vectorLength() < relevantLength) {
 
1149
            increaseVectorLength(exec->globalData(), relevantLength);
 
1150
            begin = arrayStorage()->m_vector;
 
1151
        }
 
1152
        if (arrayStorage()->length() < relevantLength)
 
1153
            arrayStorage()->setLength(relevantLength);
 
1154
        break;
 
1155
        
 
1156
    default:
 
1157
        CRASH();
 
1158
    }
 
1159
 
 
1160
    for (size_t i = 0; i < relevantLength; i++) {
 
1161
        if (indexingType == ArrayWithDouble)
 
1162
            static_cast<double*>(begin)[i] = values[i].first.asNumber();
 
1163
        else
 
1164
            static_cast<WriteBarrier<Unknown>*>(begin)[i].set(globalData, this, values[i].first);
 
1165
    }
 
1166
    
 
1167
    Heap::heap(this)->popTempSortVector(&values);
 
1168
}
 
1169
 
 
1170
void JSArray::sort(ExecState* exec)
 
1171
{
 
1172
    ASSERT(!inSparseIndexingMode());
 
1173
    
 
1174
    switch (structure()->indexingType()) {
 
1175
    case ArrayClass:
 
1176
    case ArrayWithUndecided:
 
1177
        return;
 
1178
        
 
1179
    case ArrayWithInt32: {
 
1180
        unsigned lengthNotIncludingUndefined;
 
1181
        unsigned newRelevantLength;
 
1182
        compactForSorting<ArrayWithInt32>(
 
1183
            lengthNotIncludingUndefined, newRelevantLength);
 
1184
        
 
1185
        sortCompactedVector<ArrayWithInt32>(
 
1186
            exec, m_butterfly->contiguousInt32(), lengthNotIncludingUndefined);
 
1187
        return;
 
1188
    }
 
1189
        
 
1190
    case ArrayWithDouble: {
 
1191
        unsigned lengthNotIncludingUndefined;
 
1192
        unsigned newRelevantLength;
 
1193
        compactForSorting<ArrayWithDouble>(
 
1194
            lengthNotIncludingUndefined, newRelevantLength);
 
1195
        
 
1196
        sortCompactedVector<ArrayWithDouble>(
 
1197
            exec, m_butterfly->contiguousDouble(), lengthNotIncludingUndefined);
 
1198
        return;
 
1199
    }
 
1200
        
 
1201
    case ArrayWithContiguous: {
 
1202
        unsigned lengthNotIncludingUndefined;
 
1203
        unsigned newRelevantLength;
 
1204
        compactForSorting<ArrayWithContiguous>(
 
1205
            lengthNotIncludingUndefined, newRelevantLength);
 
1206
        
 
1207
        sortCompactedVector<ArrayWithContiguous>(
 
1208
            exec, m_butterfly->contiguous(), lengthNotIncludingUndefined);
 
1209
        return;
 
1210
    }
 
1211
        
 
1212
    case ArrayWithArrayStorage: {
 
1213
        unsigned lengthNotIncludingUndefined;
 
1214
        unsigned newRelevantLength;
 
1215
        compactForSorting<ArrayWithArrayStorage>(
 
1216
            lengthNotIncludingUndefined, newRelevantLength);
 
1217
        ArrayStorage* storage = m_butterfly->arrayStorage();
 
1218
        ASSERT(!storage->m_sparseMap);
 
1219
        
 
1220
        sortCompactedVector<ArrayWithArrayStorage>(
 
1221
            exec, storage->m_vector, lengthNotIncludingUndefined);
 
1222
        return;
 
1223
    }
 
1224
        
 
1225
    default:
 
1226
        ASSERT_NOT_REACHED();
 
1227
    }
 
1228
}
 
1229
 
 
1230
struct AVLTreeNodeForArrayCompare {
 
1231
    JSValue value;
 
1232
 
 
1233
    // Child pointers.  The high bit of gt is robbed and used as the
 
1234
    // balance factor sign.  The high bit of lt is robbed and used as
 
1235
    // the magnitude of the balance factor.
 
1236
    int32_t gt;
 
1237
    int32_t lt;
 
1238
};
 
1239
 
 
1240
struct AVLTreeAbstractorForArrayCompare {
 
1241
    typedef int32_t handle; // Handle is an index into m_nodes vector.
 
1242
    typedef JSValue key;
 
1243
    typedef int32_t size;
 
1244
 
 
1245
    Vector<AVLTreeNodeForArrayCompare> m_nodes;
 
1246
    ExecState* m_exec;
 
1247
    JSValue m_compareFunction;
 
1248
    CallType m_compareCallType;
 
1249
    const CallData* m_compareCallData;
 
1250
    OwnPtr<CachedCall> m_cachedCall;
 
1251
 
 
1252
    handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
 
1253
    void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; }
 
1254
    handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; }
 
1255
    void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; }
 
1256
 
 
1257
    int get_balance_factor(handle h)
 
1258
    {
 
1259
        if (m_nodes[h].gt & 0x80000000)
 
1260
            return -1;
 
1261
        return static_cast<unsigned>(m_nodes[h].lt) >> 31;
 
1262
    }
 
1263
 
 
1264
    void set_balance_factor(handle h, int bf)
 
1265
    {
 
1266
        if (bf == 0) {
 
1267
            m_nodes[h].lt &= 0x7FFFFFFF;
 
1268
            m_nodes[h].gt &= 0x7FFFFFFF;
 
1269
        } else {
 
1270
            m_nodes[h].lt |= 0x80000000;
 
1271
            if (bf < 0)
 
1272
                m_nodes[h].gt |= 0x80000000;
 
1273
            else
 
1274
                m_nodes[h].gt &= 0x7FFFFFFF;
 
1275
        }
 
1276
    }
 
1277
 
 
1278
    int compare_key_key(key va, key vb)
 
1279
    {
 
1280
        ASSERT(!va.isUndefined());
 
1281
        ASSERT(!vb.isUndefined());
 
1282
 
 
1283
        if (m_exec->hadException())
 
1284
            return 1;
 
1285
 
 
1286
        double compareResult;
 
1287
        if (m_cachedCall) {
 
1288
            m_cachedCall->setThis(jsUndefined());
 
1289
            m_cachedCall->setArgument(0, va);
 
1290
            m_cachedCall->setArgument(1, vb);
 
1291
            compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec));
 
1292
        } else {
 
1293
            MarkedArgumentBuffer arguments;
 
1294
            arguments.append(va);
 
1295
            arguments.append(vb);
 
1296
            compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, jsUndefined(), arguments).toNumber(m_exec);
 
1297
        }
 
1298
        return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
 
1299
    }
 
1300
 
 
1301
    int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
 
1302
    int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }
 
1303
 
 
1304
    static handle null() { return 0x7FFFFFFF; }
 
1305
};
 
1306
 
 
1307
template<IndexingType indexingType>
 
1308
void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
 
1309
{
 
1310
    ASSERT(!inSparseIndexingMode());
 
1311
    ASSERT(indexingType == structure()->indexingType());
 
1312
    
 
1313
    // FIXME: This ignores exceptions raised in the compare function or in toNumber.
 
1314
        
 
1315
    // The maximum tree depth is compiled in - but the caller is clearly up to no good
 
1316
    // if a larger array is passed.
 
1317
    ASSERT(m_butterfly->publicLength() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
 
1318
    if (m_butterfly->publicLength() > static_cast<unsigned>(std::numeric_limits<int>::max()))
 
1319
        return;
 
1320
        
 
1321
    unsigned usedVectorLength = relevantLength<indexingType>();
 
1322
    unsigned nodeCount = usedVectorLength;
 
1323
        
 
1324
    if (!nodeCount)
 
1325
        return;
 
1326
        
 
1327
    AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
 
1328
    tree.abstractor().m_exec = exec;
 
1329
    tree.abstractor().m_compareFunction = compareFunction;
 
1330
    tree.abstractor().m_compareCallType = callType;
 
1331
    tree.abstractor().m_compareCallData = &callData;
 
1332
    tree.abstractor().m_nodes.grow(nodeCount);
 
1333
        
 
1334
    if (callType == CallTypeJS)
 
1335
        tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, jsCast<JSFunction*>(compareFunction), 2));
 
1336
        
 
1337
    if (!tree.abstractor().m_nodes.begin()) {
 
1338
        throwOutOfMemoryError(exec);
 
1339
        return;
 
1340
    }
 
1341
        
 
1342
    // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
 
1343
    // right out from under us while we're building the tree here.
 
1344
        
 
1345
    unsigned numDefined = 0;
 
1346
    unsigned numUndefined = 0;
 
1347
    
 
1348
    // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
 
1349
    for (; numDefined < usedVectorLength; ++numDefined) {
 
1350
        if (numDefined > m_butterfly->vectorLength())
 
1351
            break;
 
1352
        JSValue v = getHolyIndexQuickly(numDefined);
 
1353
        if (!v || v.isUndefined())
 
1354
            break;
 
1355
        tree.abstractor().m_nodes[numDefined].value = v;
 
1356
        tree.insert(numDefined);
 
1357
    }
 
1358
    for (unsigned i = numDefined; i < usedVectorLength; ++i) {
 
1359
        if (i > m_butterfly->vectorLength())
 
1360
            break;
 
1361
        JSValue v = getHolyIndexQuickly(i);
 
1362
        if (v) {
 
1363
            if (v.isUndefined())
 
1364
                ++numUndefined;
 
1365
            else {
 
1366
                tree.abstractor().m_nodes[numDefined].value = v;
 
1367
                tree.insert(numDefined);
 
1368
                ++numDefined;
 
1369
            }
 
1370
        }
 
1371
    }
 
1372
    
 
1373
    unsigned newUsedVectorLength = numDefined + numUndefined;
 
1374
        
 
1375
    // The array size may have changed. Figure out the new bounds.
 
1376
    unsigned newestUsedVectorLength = currentRelevantLength();
 
1377
        
 
1378
    unsigned elementsToExtractThreshold = min(min(newestUsedVectorLength, numDefined), static_cast<unsigned>(tree.abstractor().m_nodes.size()));
 
1379
    unsigned undefinedElementsThreshold = min(newestUsedVectorLength, newUsedVectorLength);
 
1380
    unsigned clearElementsThreshold = min(newestUsedVectorLength, usedVectorLength);
 
1381
        
 
1382
    // Copy the values back into m_storage.
 
1383
    AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
 
1384
    iter.start_iter_least(tree);
 
1385
    JSGlobalData& globalData = exec->globalData();
 
1386
    for (unsigned i = 0; i < elementsToExtractThreshold; ++i) {
 
1387
        if (structure()->indexingType() == ArrayWithDouble)
 
1388
            butterfly()->contiguousDouble()[i] = tree.abstractor().m_nodes[*iter].value.asNumber();
 
1389
        else
 
1390
            currentIndexingData()[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
 
1391
        ++iter;
 
1392
    }
 
1393
    // Put undefined values back in.
 
1394
    switch (structure()->indexingType()) {
 
1395
    case ArrayWithInt32:
 
1396
    case ArrayWithDouble:
 
1397
        ASSERT(elementsToExtractThreshold == undefinedElementsThreshold);
 
1398
        break;
 
1399
        
 
1400
    default:
 
1401
        for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i)
 
1402
            currentIndexingData()[i].setUndefined();
 
1403
    }
 
1404
 
 
1405
    // Ensure that unused values in the vector are zeroed out.
 
1406
    for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i) {
 
1407
        if (structure()->indexingType() == ArrayWithDouble)
 
1408
            butterfly()->contiguousDouble()[i] = QNaN;
 
1409
        else
 
1410
            currentIndexingData()[i].clear();
 
1411
    }
 
1412
    
 
1413
    if (hasArrayStorage(structure()->indexingType()))
 
1414
        arrayStorage()->m_numValuesInVector = newUsedVectorLength;
 
1415
}
 
1416
 
 
1417
void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
 
1418
{
 
1419
    ASSERT(!inSparseIndexingMode());
 
1420
    
 
1421
    switch (structure()->indexingType()) {
 
1422
    case ArrayClass:
 
1423
    case ArrayWithUndecided:
 
1424
        return;
 
1425
        
 
1426
    case ArrayWithInt32:
 
1427
        sortVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
 
1428
        return;
 
1429
 
 
1430
    case ArrayWithDouble:
 
1431
        sortVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
 
1432
        return;
 
1433
 
 
1434
    case ArrayWithContiguous:
 
1435
        sortVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
 
1436
        return;
 
1437
 
 
1438
    case ArrayWithArrayStorage:
 
1439
        sortVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
 
1440
        return;
 
1441
        
 
1442
    default:
 
1443
        ASSERT_NOT_REACHED();
 
1444
    }
 
1445
}
 
1446
 
 
1447
void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
 
1448
{
 
1449
    unsigned i = 0;
 
1450
    unsigned vectorEnd;
 
1451
    WriteBarrier<Unknown>* vector;
 
1452
    
 
1453
    switch (structure()->indexingType()) {
 
1454
    case ArrayClass:
 
1455
        return;
 
1456
        
 
1457
    case ArrayWithUndecided: {
 
1458
        vector = 0;
 
1459
        vectorEnd = 0;
 
1460
        break;
 
1461
    }
 
1462
        
 
1463
    case ArrayWithInt32:
 
1464
    case ArrayWithContiguous: {
 
1465
        vectorEnd = m_butterfly->publicLength();
 
1466
        vector = m_butterfly->contiguous();
 
1467
        break;
 
1468
    }
 
1469
        
 
1470
    case ArrayWithDouble: {
 
1471
        vector = 0;
 
1472
        vectorEnd = 0;
 
1473
        for (; i < m_butterfly->publicLength(); ++i) {
 
1474
            double v = butterfly()->contiguousDouble()[i];
 
1475
            if (v != v)
 
1476
                break;
 
1477
            args.append(JSValue(JSValue::EncodeAsDouble, v));
 
1478
        }
 
1479
        break;
 
1480
    }
 
1481
    
 
1482
    case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
 
1483
        ArrayStorage* storage = m_butterfly->arrayStorage();
 
1484
        
 
1485
        vector = storage->m_vector;
 
1486
        vectorEnd = min(storage->length(), storage->vectorLength());
 
1487
        break;
 
1488
    }
 
1489
        
 
1490
    default:
 
1491
        CRASH();
 
1492
        vector = 0;
 
1493
        vectorEnd = 0;
 
1494
        break;
 
1495
    }
 
1496
    
 
1497
    for (; i < vectorEnd; ++i) {
 
1498
        WriteBarrier<Unknown>& v = vector[i];
 
1499
        if (!v)
 
1500
            break;
 
1501
        args.append(v.get());
 
1502
    }
 
1503
    
 
1504
    for (; i < length(); ++i)
 
1505
        args.append(get(exec, i));
 
1506
}
 
1507
 
 
1508
void JSArray::copyToArguments(ExecState* exec, CallFrame* callFrame, uint32_t length)
 
1509
{
 
1510
    unsigned i = 0;
 
1511
    WriteBarrier<Unknown>* vector;
 
1512
    unsigned vectorEnd;
 
1513
    
 
1514
    ASSERT(length == this->length());
 
1515
    switch (structure()->indexingType()) {
 
1516
    case ArrayClass:
 
1517
        return;
 
1518
        
 
1519
    case ArrayWithUndecided: {
 
1520
        vector = 0;
 
1521
        vectorEnd = 0;
 
1522
        break;
 
1523
    }
 
1524
        
 
1525
    case ArrayWithInt32:
 
1526
    case ArrayWithContiguous: {
 
1527
        vector = m_butterfly->contiguous();
 
1528
        vectorEnd = m_butterfly->publicLength();
 
1529
        break;
 
1530
    }
 
1531
        
 
1532
    case ArrayWithDouble: {
 
1533
        vector = 0;
 
1534
        vectorEnd = 0;
 
1535
        for (; i < m_butterfly->publicLength(); ++i) {
 
1536
            double v = m_butterfly->contiguousDouble()[i];
 
1537
            if (v != v)
 
1538
                break;
 
1539
            callFrame->setArgument(i, JSValue(JSValue::EncodeAsDouble, v));
 
1540
        }
 
1541
        break;
 
1542
    }
 
1543
        
 
1544
    case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
 
1545
        ArrayStorage* storage = m_butterfly->arrayStorage();
 
1546
        vector = storage->m_vector;
 
1547
        vectorEnd = min(length, storage->vectorLength());
 
1548
        break;
 
1549
    }
 
1550
        
 
1551
    default:
 
1552
        CRASH();
 
1553
        vector = 0;
 
1554
        vectorEnd = 0;
 
1555
        break;
 
1556
    }
 
1557
    
 
1558
    for (; i < vectorEnd; ++i) {
 
1559
        WriteBarrier<Unknown>& v = vector[i];
 
1560
        if (!v)
 
1561
            break;
 
1562
        callFrame->setArgument(i, v.get());
 
1563
    }
 
1564
    
 
1565
    for (; i < length; ++i)
 
1566
        callFrame->setArgument(i, get(exec, i));
 
1567
}
 
1568
 
 
1569
template<IndexingType indexingType>
 
1570
void JSArray::compactForSorting(unsigned& numDefined, unsigned& newRelevantLength)
 
1571
{
 
1572
    ASSERT(!inSparseIndexingMode());
 
1573
    ASSERT(indexingType == structure()->indexingType());
 
1574
 
 
1575
    unsigned myRelevantLength = relevantLength<indexingType>();
 
1576
    
 
1577
    numDefined = 0;
 
1578
    unsigned numUndefined = 0;
 
1579
        
 
1580
    for (; numDefined < myRelevantLength; ++numDefined) {
 
1581
        if (indexingType == ArrayWithInt32) {
 
1582
            JSValue v = m_butterfly->contiguousInt32()[numDefined].get();
 
1583
            if (!v)
 
1584
                break;
 
1585
            ASSERT(v.isInt32());
 
1586
            continue;
 
1587
        }
 
1588
        if (indexingType == ArrayWithDouble) {
 
1589
            double v = m_butterfly->contiguousDouble()[numDefined];
 
1590
            if (v != v)
 
1591
                break;
 
1592
            continue;
 
1593
        }
 
1594
        JSValue v = indexingData<indexingType>()[numDefined].get();
 
1595
        if (!v || v.isUndefined())
 
1596
            break;
 
1597
    }
 
1598
        
 
1599
    for (unsigned i = numDefined; i < myRelevantLength; ++i) {
 
1600
        if (indexingType == ArrayWithInt32) {
 
1601
            JSValue v = m_butterfly->contiguousInt32()[i].get();
 
1602
            if (!v)
 
1603
                continue;
 
1604
            ASSERT(v.isInt32());
 
1605
            m_butterfly->contiguousInt32()[numDefined++].setWithoutWriteBarrier(v);
 
1606
            continue;
 
1607
        }
 
1608
        if (indexingType == ArrayWithDouble) {
 
1609
            double v = m_butterfly->contiguousDouble()[i];
 
1610
            if (v != v)
 
1611
                continue;
 
1612
            m_butterfly->contiguousDouble()[numDefined++] = v;
 
1613
            continue;
 
1614
        }
 
1615
        JSValue v = indexingData<indexingType>()[i].get();
 
1616
        if (v) {
 
1617
            if (v.isUndefined())
 
1618
                ++numUndefined;
 
1619
            else
 
1620
                indexingData<indexingType>()[numDefined++].setWithoutWriteBarrier(v);
 
1621
        }
 
1622
    }
 
1623
        
 
1624
    newRelevantLength = numDefined + numUndefined;
 
1625
    
 
1626
    if (hasArrayStorage(indexingType))
 
1627
        ASSERT(!arrayStorage()->m_sparseMap);
 
1628
    
 
1629
    switch (indexingType) {
 
1630
    case ArrayWithInt32:
 
1631
    case ArrayWithDouble:
 
1632
        ASSERT(numDefined == newRelevantLength);
 
1633
        break;
 
1634
        
 
1635
    default:
 
1636
        for (unsigned i = numDefined; i < newRelevantLength; ++i)
 
1637
            indexingData<indexingType>()[i].setUndefined();
 
1638
        break;
 
1639
    }
 
1640
    for (unsigned i = newRelevantLength; i < myRelevantLength; ++i) {
 
1641
        if (indexingType == ArrayWithDouble)
 
1642
            m_butterfly->contiguousDouble()[i] = QNaN;
 
1643
        else
 
1644
            indexingData<indexingType>()[i].clear();
 
1645
    }
 
1646
 
 
1647
    if (hasArrayStorage(indexingType))
 
1648
        arrayStorage()->m_numValuesInVector = newRelevantLength;
 
1649
}
 
1650
 
 
1651
} // namespace JSC