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

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

darin@apple.com's avatar
darin@apple.com committed
26
#include "ArrayPrototype.h"
27
#include "ButterflyInlines.h"
28
#include "CachedCall.h"
29 30
#include "CopiedSpace.h"
#include "CopiedSpaceInlines.h"
31
#include "Error.h"
32
#include "Executable.h"
33
#include "GetterSetter.h"
34
#include "IndexingHeaderInlines.h"
darin's avatar
darin committed
35
#include "PropertyNameArray.h"
36
#include "Reject.h"
ap@webkit.org's avatar
ap@webkit.org committed
37
#include <wtf/AVLTree.h>
38
#include <wtf/Assertions.h>
39
#include <wtf/OwnPtr.h>
40
#include <Operations.h>
darin's avatar
darin committed
41

42
using namespace std;
ap@webkit.org's avatar
ap@webkit.org committed
43
using namespace WTF;
bdash's avatar
bdash committed
44

45
namespace JSC {
darin's avatar
darin committed
46

47
ASSERT_HAS_TRIVIAL_DESTRUCTOR(JSArray);
ggaren@apple.com's avatar
ggaren@apple.com committed
48

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

51
Butterfly* createArrayButterflyInDictionaryIndexingMode(JSGlobalData& globalData, unsigned initialLength)
darin's avatar
darin committed
52
{
53 54 55 56 57 58 59 60 61
    Butterfly* butterfly = Butterfly::create(
        globalData, 0, 0, true, IndexingHeader(), ArrayStorage::sizeFor(0));
    ArrayStorage* storage = butterfly->arrayStorage();
    storage->setLength(initialLength);
    storage->setVectorLength(0);
    storage->m_indexBias = 0;
    storage->m_sparseMap.clear();
    storage->m_numValuesInVector = 0;
    return butterfly;
62 63 64 65 66 67 68 69
}

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

70
    enterDictionaryIndexingMode(exec->globalData());
71

72
    SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get();
73 74 75 76 77
    ASSERT(map);
    map->setLengthIsReadOnly();
}

// 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 83 84 85

    // 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.
86
        if (descriptor.configurablePresent() && descriptor.configurable())
87 88
            return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property.");
        // from ES5.1 8.12.9 7.b.
89
        if (descriptor.enumerablePresent() && descriptor.enumerable())
90 91 92 93 94 95 96
            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.
97
        if (!array->isLengthWritable() && descriptor.writablePresent() && descriptor.writable())
98 99 100
            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()) {
101 102
            if (descriptor.writablePresent())
                array->setLengthWritable(exec, descriptor.writable());
103 104 105 106 107 108 109 110 111 112 113 114 115 116
            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()) {
117 118
            if (descriptor.writablePresent())
                array->setLengthWritable(exec, descriptor.writable());
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139
            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
140
        if (!array->setLength(exec, newLen, throwException)) {
141 142 143 144
            // 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.
145 146
            if (descriptor.writablePresent())
                array->setLengthWritable(exec, descriptor.writable());
147 148 149 150
            return false;
        }

        // m. If newWritable is false, then
151 152 153 154 155
        // 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());
156 157 158 159 160 161
        // n. Return true.
        return true;
    }

    // 4. Else if P is an array index (15.4), then
    // a. Let index be ToUint32(P).
162 163
    unsigned index = propertyName.asIndex();
    if (index != PropertyName::NotAnIndex) {
164 165 166 167 168 169 170 171 172
        // 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.
173
        return array->defineOwnIndexedProperty(exec, index, descriptor, throwException);
darin's avatar
darin committed
174 175
    }

176
    return array->JSObject::defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException);
darin's avatar
darin committed
177 178
}

179
bool JSArray::getOwnPropertySlot(JSCell* cell, ExecState* exec, PropertyName propertyName, PropertySlot& slot)
180
{
181
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
182
    if (propertyName == exec->propertyNames().length) {
183
        slot.setValue(jsNumber(thisObject->length()));
darin's avatar
darin committed
184 185 186
        return true;
    }

187
    return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
darin's avatar
darin committed
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 196
        return true;
    }
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);
darin's avatar
darin committed
205 206

    if (propertyName == exec->propertyNames().length) {
weinig@apple.com's avatar
weinig@apple.com committed
207 208
        unsigned newLength = value.toUInt32(exec);
        if (value.toNumber(exec) != static_cast<double>(newLength)) {
209
            throwError(exec, createRangeError(exec, ASCIILiteral("Invalid array length")));
darin's avatar
darin committed
210 211
            return;
        }
212
        thisObject->setLength(exec, newLength, slot.isStrictMode());
darin's avatar
darin committed
213 214 215
        return;
    }

216
    JSObject::put(thisObject, exec, propertyName, value, slot);
darin's avatar
darin committed
217 218
}

219
bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName)
220
{
221
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
222 223 224 225

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

226
    return JSObject::deleteProperty(thisObject, exec, propertyName);
darin's avatar
darin committed
227 228
}

229 230
static int compareKeysForQSort(const void* a, const void* b)
{
231 232
    unsigned da = *static_cast<const unsigned*>(a);
    unsigned db = *static_cast<const unsigned*>(b);
233
    return (da > db) - (da < db);
darin's avatar
darin committed
234 235
}

236
void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
darin's avatar
darin committed
237
{
238
    JSArray* thisObject = jsCast<JSArray*>(object);
239

240 241 242
    if (mode == IncludeDontEnumProperties)
        propertyNames.add(exec->propertyNames().length);

243
    JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode);
244
}
darin's avatar
darin committed
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 250 251 252
    ArrayStorage* storage = ensureArrayStorage(globalData);
    Butterfly* butterfly = storage->butterfly();
    unsigned propertyCapacity = structure()->outOfLineCapacity();
    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 258 259 260 261 262 263
    // 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.

264 265
    unsigned length = storage->length();
    unsigned usedVectorLength = min(storage->vectorLength(), length);
266 267 268
    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)
269
        return false;
270 271 272
    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.
273 274
    ASSERT(storage->vectorLength() <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - storage->vectorLength()) >= storage->m_indexBias);
    unsigned currentCapacity = storage->vectorLength() + storage->m_indexBias;
275 276 277 278
    // 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:
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 283 284
    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)) {
285
        newAllocBase = butterfly->base(structure());
286 287
        newStorageCapacity = currentCapacity;
    } else {
288 289
        size_t newSize = Butterfly::totalSize(0, propertyCapacity, true, ArrayStorage::sizeFor(desiredCapacity));
        if (!globalData.heap.tryAllocateStorage(newSize, &newAllocBase))
290 291 292 293 294 295 296 297
            return false;
        newStorageCapacity = desiredCapacity;
    }

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

    // Determine how much of the vector to use as pre-capacity, and how much as post-capacity.
298
    // If we're adding to the end, we'll add all the new space to the end.
299 300 301 302
    // If the vector had no free post-capacity (length >= m_vectorLength), don't give it any.
    // If it did, we calculate the amount that will remain based on an atomic decay - leave the
    // vector with half the post-capacity it had previously.
    unsigned postCapacity = 0;
303 304 305
    if (!addToFront)
        postCapacity = max(newStorageCapacity - requiredVectorLength, count);
    else if (length < storage->vectorLength()) {
306
        // Atomic decay, + the post-capacity cannot be greater than what is available.
307 308 309
        postCapacity = min((storage->vectorLength() - length) >> 1, newStorageCapacity - requiredVectorLength);
        // If we're moving contents within the same allocation, the post-capacity is being reduced.
        ASSERT(newAllocBase != butterfly->base(structure()) || postCapacity < storage->vectorLength() - length);
310
    }
311

312 313 314 315
    unsigned newVectorLength = requiredVectorLength + postCapacity;
    unsigned newIndexBias = newStorageCapacity - newVectorLength;

    Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity);
316

317 318
    if (addToFront) {
        ASSERT(count + usedVectorLength <= newVectorLength);
319
        memmove(newButterfly->arrayStorage()->m_vector + count, storage->m_vector, sizeof(JSValue) * usedVectorLength);
320 321 322
        memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
    } else if ((newAllocBase != butterfly->base(structure())) || (newIndexBias != storage->m_indexBias)) {
        memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
323 324
        memmove(newButterfly->arrayStorage()->m_vector, storage->m_vector, sizeof(JSValue) * usedVectorLength);

325 326 327 328 329
        WriteBarrier<Unknown>* newVector = newButterfly->arrayStorage()->m_vector;
        for (unsigned i = requiredVectorLength; i < newVectorLength; i++)
            newVector[i].clear();
    }

330 331
    newButterfly->arrayStorage()->setVectorLength(newVectorLength);
    newButterfly->arrayStorage()->m_indexBias = newIndexBias;
332

333
    m_butterfly = newButterfly;
334

ap@webkit.org's avatar
ap@webkit.org committed
335
    return true;
darin's avatar
darin committed
336 337
}

338
bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, bool throwException, ArrayStorage* storage)
darin's avatar
darin committed
339
{
340
    unsigned length = storage->length();
darin's avatar
darin committed
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 347 348 349 350 351 352 353 354 355
        // Fail if the length is not writable.
        if (map->lengthIsReadOnly())
            return reject(exec, throwException, StrictModeReadonlyPropertyWriteError);

        if (newLength < length) {
            // Copy any keys we might be interested in into a vector.
            Vector<unsigned> keys;
            keys.reserveCapacity(min(map->size(), static_cast<size_t>(length - newLength)));
            SparseArrayValueMap::const_iterator end = map->end();
            for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
356
                unsigned index = static_cast<unsigned>(it->key);
357 358 359 360 361 362 363 364 365 366 367 368 369 370
                if (index < length && index >= newLength)
                    keys.append(index);
            }

            // Check if the array is in sparse mode. If so there may be non-configurable
            // properties, so we have to perform deletion with caution, if not we can
            // delete values in any order.
            if (map->sparseMode()) {
                qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
                unsigned i = keys.size();
                while (i) {
                    unsigned index = keys[--i];
                    SparseArrayValueMap::iterator it = map->find(index);
                    ASSERT(it != map->notFound());
371
                    if (it->value.attributes & DontDelete) {
372
                        storage->setLength(index + 1);
373 374 375 376 377 378 379
                        return reject(exec, throwException, "Unable to delete property.");
                    }
                    map->remove(it);
                }
            } else {
                for (unsigned i = 0; i < keys.size(); ++i)
                    map->remove(keys[i]);
380
                if (map->isEmpty())
381
                    deallocateSparseIndexMap();
382 383 384 385
            }
        }
    }

darin's avatar
darin committed
386
    if (newLength < length) {
387
        // Delete properties from the vector.
388
        unsigned usedVectorLength = min(length, storage->vectorLength());
darin's avatar
darin committed
389
        for (unsigned i = newLength; i < usedVectorLength; ++i) {
390
            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
darin's avatar
darin committed
391
            bool hadValue = valueSlot;
392
            valueSlot.clear();
darin's avatar
darin committed
393 394 395
            storage->m_numValuesInVector -= hadValue;
        }
    }
aroben@apple.com's avatar
aroben@apple.com committed
396

397
    storage->setLength(newLength);
398

399
    return true;
darin's avatar
darin committed
400 401
}

402 403 404 405 406 407 408 409 410 411 412
bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
{
    switch (structure()->indexingType()) {
    case ArrayClass:
        if (!newLength)
            return true;
        if (newLength >= MIN_SPARSE_ARRAY_INDEX) {
            return setLengthWithArrayStorage(
                exec, newLength, throwException,
                convertContiguousToArrayStorage(exec->globalData()));
        }
413
        createInitialUndecided(exec->globalData(), newLength);
414 415
        return true;
        
416 417 418
    case ArrayWithUndecided:
    case ArrayWithInt32:
    case ArrayWithDouble:
419 420 421 422 423
    case ArrayWithContiguous:
        if (newLength == m_butterfly->publicLength())
            return true;
        if (newLength >= MAX_ARRAY_INDEX // This case ensures that we can do fast push.
            || (newLength >= MIN_SPARSE_ARRAY_INDEX
424
                && !isDenseEnoughForVector(newLength, countElements()))) {
425 426
            return setLengthWithArrayStorage(
                exec, newLength, throwException,
427
                ensureArrayStorage(exec->globalData()));
428 429
        }
        if (newLength > m_butterfly->publicLength()) {
430
            ensureLength(exec->globalData(), newLength);
431 432
            return true;
        }
433 434 435 436 437 438 439
        if (structure()->indexingType() == ArrayWithDouble) {
            for (unsigned i = m_butterfly->publicLength(); i-- > newLength;)
                m_butterfly->contiguousDouble()[i] = QNaN;
        } else {
            for (unsigned i = m_butterfly->publicLength(); i-- > newLength;)
                m_butterfly->contiguous()[i].clear();
        }
440 441 442 443 444 445 446 447 448 449 450 451 452
        m_butterfly->setPublicLength(newLength);
        return true;
        
    case ArrayWithArrayStorage:
    case ArrayWithSlowPutArrayStorage:
        return setLengthWithArrayStorage(exec, newLength, throwException, arrayStorage());
        
    default:
        CRASH();
        return false;
    }
}

453
JSValue JSArray::pop(ExecState* exec)
454
{
455
    switch (structure()->indexingType()) {
456
    case ArrayClass:
457
        return jsUndefined();
458
        
459 460 461 462 463 464 465
    case ArrayWithUndecided:
        if (!m_butterfly->publicLength())
            return jsUndefined();
        // We have nothing but holes. So, drop down to the slow version.
        break;
        
    case ArrayWithInt32:
466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481
    case ArrayWithContiguous: {
        unsigned length = m_butterfly->publicLength();
        
        if (!length--)
            return jsUndefined();
        
        ASSERT(length < m_butterfly->vectorLength());
        JSValue value = m_butterfly->contiguous()[length].get();
        if (value) {
            m_butterfly->contiguous()[length].clear();
            m_butterfly->setPublicLength(length);
            return value;
        }
        break;
    }
        
482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497
    case ArrayWithDouble: {
        unsigned length = m_butterfly->publicLength();
        
        if (!length--)
            return jsUndefined();
        
        ASSERT(length < m_butterfly->vectorLength());
        double value = m_butterfly->contiguousDouble()[length];
        if (value == value) {
            m_butterfly->contiguousDouble()[length] = QNaN;
            m_butterfly->setPublicLength(length);
            return JSValue(JSValue::EncodeAsDouble, value);
        }
        break;
    }
        
498
    case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
499 500 501 502 503 504 505 506
        ArrayStorage* storage = m_butterfly->arrayStorage();
    
        unsigned length = storage->length();
        if (!length) {
            if (!isLengthWritable())
                throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
            return jsUndefined();
        }
507

508 509 510 511 512 513 514
        unsigned index = length - 1;
        if (index < storage->vectorLength()) {
            WriteBarrier<Unknown>& valueSlot = storage->m_vector[index];
            if (valueSlot) {
                --storage->m_numValuesInVector;
                JSValue element = valueSlot.get();
                valueSlot.clear();
515
            
516 517 518 519
                ASSERT(isLengthWritable());
                storage->setLength(index);
                return element;
            }
520
        }
521
        break;
522 523 524
    }
        
    default:
525
        CRASH();
526
        return JSValue();
527
    }
528 529 530 531 532 533 534 535 536 537 538 539 540 541 542
    
    unsigned index = getArrayLength() - 1;
    // Let element be the result of calling the [[Get]] internal method of O with argument indx.
    JSValue element = get(exec, index);
    if (exec->hadException())
        return jsUndefined();
    // Call the [[Delete]] internal method of O with arguments indx and true.
    if (!deletePropertyByIndex(this, exec, index)) {
        throwTypeError(exec, "Unable to delete property.");
        return jsUndefined();
    }
    // Call the [[Put]] internal method of O with arguments "length", indx, and true.
    setLength(exec, index, true);
    // Return element.
    return element;
543 544
}

545 546 547
// Push & putIndex are almost identical, with two small differences.
//  - we always are writing beyond the current array bounds, so it is always necessary to update m_length & m_numValuesInVector.
//  - pushing to an array of length 2^32-1 stores the property, but throws a range error.
ggaren@apple.com's avatar
ggaren@apple.com committed
548
void JSArray::push(ExecState* exec, JSValue value)
549
{
550
    switch (structure()->indexingType()) {
551
    case ArrayClass: {
552 553 554 555 556 557 558 559
        createInitialUndecided(exec->globalData(), 0);
        // Fall through.
    }
        
    case ArrayWithUndecided: {
        convertUndecidedForValue(exec->globalData(), value);
        push(exec, value);
        return;
560
    }
561
        
562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587
    case ArrayWithInt32: {
        if (!value.isInt32()) {
            convertInt32ForValue(exec->globalData(), value);
            push(exec, value);
            return;
        }

        unsigned length = m_butterfly->publicLength();
        ASSERT(length <= m_butterfly->vectorLength());
        if (length < m_butterfly->vectorLength()) {
            m_butterfly->contiguousInt32()[length].setWithoutWriteBarrier(value);
            m_butterfly->setPublicLength(length + 1);
            return;
        }
        
        if (length > MAX_ARRAY_INDEX) {
            methodTable()->putByIndex(this, exec, length, value, true);
            if (!exec->hadException())
                throwError(exec, createRangeError(exec, "Invalid array length"));
            return;
        }
        
        putByIndexBeyondVectorLengthWithoutAttributes<Int32Shape>(exec, length, value);
        return;
    }

588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603
    case ArrayWithContiguous: {
        unsigned length = m_butterfly->publicLength();
        ASSERT(length <= m_butterfly->vectorLength());
        if (length < m_butterfly->vectorLength()) {
            m_butterfly->contiguous()[length].set(exec->globalData(), this, value);
            m_butterfly->setPublicLength(length + 1);
            return;
        }
        
        if (length > MAX_ARRAY_INDEX) {
            methodTable()->putByIndex(this, exec, length, value, true);
            if (!exec->hadException())
                throwError(exec, createRangeError(exec, "Invalid array length"));
            return;
        }
        
604
        putByIndexBeyondVectorLengthWithoutAttributes<ContiguousShape>(exec, length, value);
605 606 607
        return;
    }
        
608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639
    case ArrayWithDouble: {
        if (!value.isNumber()) {
            convertDoubleToContiguous(exec->globalData());
            push(exec, value);
            return;
        }
        double valueAsDouble = value.asNumber();
        if (valueAsDouble != valueAsDouble) {
            convertDoubleToContiguous(exec->globalData());
            push(exec, value);
            return;
        }

        unsigned length = m_butterfly->publicLength();
        ASSERT(length <= m_butterfly->vectorLength());
        if (length < m_butterfly->vectorLength()) {
            m_butterfly->contiguousDouble()[length] = valueAsDouble;
            m_butterfly->setPublicLength(length + 1);
            return;
        }
        
        if (length > MAX_ARRAY_INDEX) {
            methodTable()->putByIndex(this, exec, length, value, true);
            if (!exec->hadException())
                throwError(exec, createRangeError(exec, "Invalid array length"));
            return;
        }
        
        putByIndexBeyondVectorLengthWithoutAttributes<DoubleShape>(exec, length, value);
        break;
    }
        
640 641 642 643 644 645 646 647 648 649
    case ArrayWithSlowPutArrayStorage: {
        unsigned oldLength = length();
        if (attemptToInterceptPutByIndexOnHole(exec, oldLength, value, true)) {
            if (!exec->hadException() && oldLength < 0xFFFFFFFFu)
                setLength(exec, oldLength + 1, true);
            return;
        }
        // Fall through.
    }
        
650 651 652 653 654 655 656 657 658 659 660
    case ArrayWithArrayStorage: {
        ArrayStorage* storage = m_butterfly->arrayStorage();

        // Fast case - push within vector, always update m_length & m_numValuesInVector.
        unsigned length = storage->length();
        if (length < storage->vectorLength()) {
            storage->m_vector[length].set(exec->globalData(), this, value);
            storage->setLength(length + 1);
            ++storage->m_numValuesInVector;
            return;
        }
661

662 663
        // Pushing to an array of invalid length (2^31-1) stores the property, but throws a range error.
        if (storage->length() > MAX_ARRAY_INDEX) {
664 665 666 667 668 669
            methodTable()->putByIndex(this, exec, storage->length(), value, true);
            // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d.
            if (!exec->hadException())
                throwError(exec, createRangeError(exec, "Invalid array length"));
            return;
        }
670

671 672 673 674 675 676 677 678
        // Handled the same as putIndex.
        putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage);
        break;
    }
        
    default:
        ASSERT_NOT_REACHED();
    }
679 680
}

681
bool JSArray::shiftCountWithArrayStorage(unsigned startIndex, unsigned count, ArrayStorage* storage)
682
{
683
    unsigned oldLength = storage->length();
684
    ASSERT(count <= oldLength);
685
    
686 687
    // If the array contains holes or is otherwise in an abnormal state,
    // use the generic algorithm in ArrayPrototype.
688
    if (oldLength != storage->m_numValuesInVector || inSparseIndexingMode() || shouldUseSlowPut(structure()->indexingType()))
689
        return false;
690

691 692
    if (!oldLength)
        return true;
693
    
694 695
    unsigned length = oldLength - count;
    
696
    storage->m_numValuesInVector -= count;
697
    storage->setLength(length);
698
    
699
    unsigned vectorLength = storage->vectorLength();
700 701 702 703 704 705 706 707 708 709 710 711 712 713
    if (!vectorLength)
        return true;
    
    if (startIndex >= vectorLength)
        return true;
    
    if (startIndex + count > vectorLength)
        count = vectorLength - startIndex;
    
    unsigned usedVectorLength = min(vectorLength, oldLength);
    
    vectorLength -= count;
    storage->setVectorLength(vectorLength);
    
714
    if (vectorLength) {
715 716 717 718 719 720 721
        if (startIndex < usedVectorLength - (startIndex + count)) {
            if (startIndex) {
                memmove(
                    storage->m_vector + count,
                    storage->m_vector,
                    sizeof(JSValue) * startIndex);
            }
722 723 724
            m_butterfly = m_butterfly->shift(structure(), count);
            storage = m_butterfly->arrayStorage();
            storage->m_indexBias += count;
725 726 727 728 729 730 731
        } else {
            memmove(
                storage->m_vector + startIndex,
                storage->m_vector + startIndex + count,
                sizeof(JSValue) * (usedVectorLength - (startIndex + count)));
            for (unsigned i = usedVectorLength - count; i < usedVectorLength; ++i)
                storage->m_vector[i].clear();
732 733
        }
    }
734
    return true;
735
}
736

737 738 739 740 741 742 743 744
bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
{
    ASSERT(count > 0);
    
    switch (structure()->indexingType()) {
    case ArrayClass:
        return true;
        
745 746 747 748 749
    case ArrayWithUndecided:
        // Don't handle this because it's confusing and it shouldn't come up.
        return false;
        
    case ArrayWithInt32:
750 751 752 753 754 755 756
    case ArrayWithContiguous: {
        unsigned oldLength = m_butterfly->publicLength();
        ASSERT(count <= oldLength);
        
        // We may have to walk the entire array to do the shift. We're willing to do
        // so only if it's not horribly slow.
        if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
757
            return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->globalData()));
758 759 760 761 762 763 764 765 766 767 768 769 770
        
        unsigned end = oldLength - count;
        for (unsigned i = startIndex; i < end; ++i) {
            // Storing to a hole is fine since we're still having a good time. But reading
            // from a hole is totally not fine, since we might have to read from the proto
            // chain.
            JSValue v = m_butterfly->contiguous()[i + count].get();
            if (UNLIKELY(!v)) {
                // The purpose of this path is to ensure that we don't make the same
                // mistake in the future: shiftCountWithArrayStorage() can't do anything
                // about holes (at least for now), but it can detect them quickly. So
                // we convert to array storage and then allow the array storage path to
                // figure it out.
771
                return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->globalData()));
772 773 774 775 776 777 778 779 780 781 782 783 784
            }
            // No need for a barrier since we're just moving data around in the same vector.
            // This is in line with our standing assumption that we won't have a deletion
            // barrier.
            m_butterfly->contiguous()[i].setWithoutWriteBarrier(v);
        }
        for (unsigned i = end; i < oldLength; ++i)
            m_butterfly->contiguous()[i].clear();
        
        m_butterfly->setPublicLength(oldLength - count);
        return true;
    }
        
785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819
    case ArrayWithDouble: {
        unsigned oldLength = m_butterfly->publicLength();
        ASSERT(count <= oldLength);
        
        // We may have to walk the entire array to do the shift. We're willing to do
        // so only if it's not horribly slow.
        if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
            return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->globalData()));
        
        unsigned end = oldLength - count;
        for (unsigned i = startIndex; i < end; ++i) {
            // Storing to a hole is fine since we're still having a good time. But reading
            // from a hole is totally not fine, since we might have to read from the proto
            // chain.
            double v = m_butterfly->contiguousDouble()[i + count];
            if (UNLIKELY(v != v)) {
                // The purpose of this path is to ensure that we don't make the same
                // mistake in the future: shiftCountWithArrayStorage() can't do anything
                // about holes (at least for now), but it can detect them quickly. So
                // we convert to array storage and then allow the array storage path to
                // figure it out.
                return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->globalData()));
            }
            // No need for a barrier since we're just moving data around in the same vector.
            // This is in line with our standing assumption that we won't have a deletion
            // barrier.
            m_butterfly->contiguousDouble()[i] = v;
        }
        for (unsigned i = end; i < oldLength; ++i)
            m_butterfly->contiguousDouble()[i] = QNaN;
        
        m_butterfly->setPublicLength(oldLength - count);
        return true;
    }
        
820 821 822 823 824 825 826 827 828 829
    case ArrayWithArrayStorage:
    case ArrayWithSlowPutArrayStorage:
        return shiftCountWithArrayStorage(startIndex, count, arrayStorage());
        
    default:
        CRASH();
        return false;
    }
}

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 836
    ASSERT(startIndex <= length);

837 838
    // If the array contains holes or is otherwise in an abnormal state,
    // use the generic algorithm in ArrayPrototype.
839
    if (length != storage->m_numValuesInVector || storage->inSparseMode() || shouldUseSlowPut(structure()->indexingType()))
840 841
        return false;

842 843 844 845 846
    bool moveFront = !startIndex || startIndex < length / 2;

    unsigned vectorLength = storage->vectorLength();

    if (moveFront && storage->m_indexBias >= count) {
847 848 849
        m_butterfly = storage->butterfly()->unshift(structure(), count);
        storage = m_butterfly->arrayStorage();
        storage->m_indexBias -= count;
850 851 852 853
        storage->setVectorLength(vectorLength + count);
    } else if (!moveFront && vectorLength - length >= count)
        storage = storage->butterfly()->arrayStorage();
    else if (unshiftCountSlowCase(exec->globalData(), moveFront, count))
854 855
        storage = arrayStorage();
    else {
856
        throwOutOfMemoryError(exec);
857
        return true;
858
    }
859

860
    WriteBarrier<Unknown>* vector = storage->m_vector;
861 862 863 864

    if (startIndex) {
        if (moveFront)
            memmove(vector, vector + count, startIndex * sizeof(JSValue));
865
        else if (length - startIndex)
866 867 868
            memmove(vector + startIndex + count, vector + startIndex, (length - startIndex) * sizeof(JSValue));
    }

869
    for (unsigned i = 0; i < count; i++)
870
        vector[i + startIndex].clear();
871
    return true;
872 873
}

874 875 876 877
bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
{
    switch (structure()->indexingType()) {
    case ArrayClass:
878
    case ArrayWithUndecided:
879 880
        // We could handle this. But it shouldn't ever come up, so we won't.
        return false;
881 882

    case ArrayWithInt32:
883 884 885 886 887 888
    case ArrayWithContiguous: {
        unsigned oldLength = m_butterfly->publicLength();
        
        // We may have to walk the entire array to do the unshift. We're willing to do so
        // only if it's not horribly slow.
        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 894 895
        
        for (unsigned i = oldLength; i-- > startIndex;) {
            JSValue v = m_butterfly->contiguous()[i].get();
            if (UNLIKELY(!v))
896
                return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->globalData()));
897 898 899 900 901 902 903 904 905 906 907
            m_butterfly->contiguous()[i + count].setWithoutWriteBarrier(v);
        }
        
        // NOTE: we're leaving being garbage in the part of the array that we shifted out
        // of. This is fine because the caller is required to store over that area, and
        // in contiguous mode storing into a hole is guaranteed to behave exactly the same
        // as storing over an existing element.
        
        return true;
    }
        
908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932
    case ArrayWithDouble: {
        unsigned oldLength = m_butterfly->publicLength();
        
        // We may have to walk the entire array to do the unshift. We're willing to do so
        // only if it's not horribly slow.
        if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
            return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->globalData()));
        
        ensureLength(exec->globalData(), oldLength + count);
        
        for (unsigned i = oldLength; i-- > startIndex;) {
            double v = m_butterfly->contiguousDouble()[i];
            if (UNLIKELY(v != v))
                return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->globalData()));
            m_butterfly->contiguousDouble()[i + count] = v;
        }
        
        // NOTE: we're leaving being garbage in the part of the array that we shifted out
        // of. This is fine because the caller is required to store over that area, and
        // in contiguous mode storing into a hole is guaranteed to behave exactly the same
        // as storing over an existing element.
        
        return true;
    }
        
933 934 935 936 937 938 939 940 941 942
    case ArrayWithArrayStorage:
    case ArrayWithSlowPutArrayStorage:
        return unshiftCountWithArrayStorage(exec, startIndex, count, arrayStorage());
        
    default:
        CRASH();
        return false;
    }
}

943 944 945 946 947 948 949 950 951 952 953 954 955 956
static int compareNumbersForQSortWithInt32(const void* a, const void* b)
{
    int32_t ia = static_cast<const JSValue*>(a)->asInt32();
    int32_t ib = static_cast<const JSValue*>(b)->asInt32();
    return ia - ib;
}

static int compareNumbersForQSortWithDouble(const void* a, const void* b)
{
    double da = *static_cast<const double*>(a);
    double db = *static_cast<const double*>(b);
    return (da > db) - (da < db);
}

ggaren@apple.com's avatar
ggaren@apple.com committed
957 958
static int compareNumbersForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
959 960
    double da = static_cast<const JSValue*>(a)->asNumber();
    double db = static_cast<const JSValue*>(b)->asNumber();
ggaren@apple.com's avatar
ggaren@apple.com committed
961 962 963
    return (da > db) - (da < db);
}

964 965
static int compareByStringPairForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
966 967
    const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
    const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
968
    return codePointCompare(va->second, vb->second);
969
}
darin's avatar
darin committed
970

971 972 973
template<IndexingType indexingType>
void JSArray::sortNumericVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
{
974
    ASSERT(indexingType == ArrayWithInt32 || indexingType == ArrayWithDouble || indexingType == ArrayWithContiguous || indexingType == ArrayWithArrayStorage);
975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992
    
    unsigned lengthNotIncludingUndefined;
    unsigned newRelevantLength;
    compactForSorting<indexingType>(
        lengthNotIncludingUndefined,
        newRelevantLength);
    
    WriteBarrier<Unknown>* data = indexingData<indexingType>();
    
    if (indexingType == ArrayWithArrayStorage && arrayStorage()->m_sparseMap.get()) {
        throwOutOfMemoryError(exec);
        return;
    }
    
    if (!lengthNotIncludingUndefined)
        return;
    
    bool allValuesAreNumbers = true;
993 994 995 996 997 998 999 1000 1001 1002 1003
    switch (indexingType) {
    case ArrayWithInt32:
    case ArrayWithDouble:
        break;
        
    default:
        for (size_t i = 0; i < newRelevantLength; ++i) {
            if (!data[i].isNumber()) {
                allValuesAreNumbers = false;
                break;
            }
1004
        }
1005
        break;
1006 1007 1008 1009 1010 1011 1012 1013
    }
    
    if (!allValuesAreNumbers)
        return sort(exec, compareFunction, callType, callData);
    
    // For numeric comparison, which is fast, qsort is faster than mergesort. We
    // also don't require mergesort's stability, since there's no user visible
    // side-effect from swapping the order of equal primitive values.
1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030
    int (*compare)(const void*, const void*);
    switch (indexingType) {
    case ArrayWithInt32:
        compare = compareNumbersForQSortWithInt32;
        break;
        
    case ArrayWithDouble:
        compare = compareNumbersForQSortWithDouble;
        ASSERT(sizeof(WriteBarrier<Unknown>) == sizeof(double));
        break;
        
    default:
        compare = compareNumbersForQSort;
        break;
    }
    
    qsort(data, newRelevantLength, sizeof(WriteBarrier<Unknown>), compare);
1031 1032 1033
    return;
}

ggaren@apple.com's avatar
ggaren@apple.com committed
1034
void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
ggaren@apple.com's avatar
ggaren@apple.com committed
1035
{
1036
    ASSERT(!inSparseIndexingMode());
ggaren@apple.com's avatar
ggaren@apple.com committed
1037

1038
    switch (structure()->indexingType()) {
1039
    case ArrayClass:
ggaren@apple.com's avatar
ggaren@apple.com committed
1040 1041
        return;
        
1042 1043 1044 1045 1046 1047 1048 1049
    case ArrayWithInt32:
        sortNumericVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
        break;
        
    case ArrayWithDouble:
        sortNumericVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
        break;
        
1050 1051 1052
    case ArrayWithContiguous:
        sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
        return;
1053

1054 1055
    case ArrayWithArrayStorage:
        sortNumericVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
1056 1057 1058
        return;
        
    default:
1059 1060
        CRASH();
        return;
ggaren@apple.com's avatar
ggaren@apple.com committed
1061 1062 1063
    }
}

1064
template<IndexingType indexingType>
1065
void JSArray::sortCompactedVector(ExecState* exec, void* begin, unsigned relevantLength)
darin's avatar
darin committed
1066
{
1067
    if (!relevantLength)
ap@webkit.org's avatar
ap@webkit.org committed
1068
        return;
1069 1070 1071 1072 1073 1074 1075
    
    JSGlobalData& globalData = exec->globalData();

    // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
    // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
    // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
    // random or otherwise changing results, effectively making compare function inconsistent.
1076
        
1077 1078 1079 1080 1081
    Vector<ValueStringPair> values(relevantLength);
    if (!values.begin()) {
        throwOutOfMemoryError(exec);
        return;
    }
1082
        
1083
    Heap::heap(this)->pushTempSortVector(&values);
1084
        
1085
    bool isSortingPrimitiveValues = true;
1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110
    switch (indexingType) {
    case ArrayWithInt32:
        for (size_t i = 0; i < relevantLength; i++) {
            JSValue value = static_cast<WriteBarrier<Unknown>*>(begin)[i].get();
            ASSERT(value.isInt32());
            values[i].first = value;
        }
        break;
        
    case ArrayWithDouble:
        for (size_t i = 0; i < relevantLength; i++) {
            double value = static_cast<double*>(begin)[i];
            ASSERT(value == value);
            values[i].first = JSValue(JSValue::EncodeAsDouble, value);
        }
        break;
        
    default:
        for (size_t i = 0; i < relevantLength; i++) {
            JSValue value = static_cast<WriteBarrier<Unknown>*>(begin)[i].get();
            ASSERT(!value.isUndefined());
            values[i].first = value;
            isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();
        }
        break;
1111
    }
1112
        
1113 1114
    // FIXME: The following loop continues to call toString on subsequent values even after
    // a toString call raises an exception.
1115
        
1116 1117
    for (size_t i = 0; i < relevantLength; i++)
        values[i].second = values[i].first.toWTFStringInline(exec);
1118
        
1119 1120 1121 1122
    if (exec->hadException()) {
        Heap::heap(this)->popTempSortVector(&values);
        return;
    }
1123
        
1124 1125
    // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
    // than O(N log N).
1126
        
1127
#if HAVE(MERGESORT)
1128
    if (isSortingPrimitiveValues)
1129
        qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
1130 1131 1132 1133 1134 1135
    else
        mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
#else
    // FIXME: The qsort library function is likely to not be a stable sort.
    // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
    qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
1136
#endif
1137 1138 1139 1140
    
    // If the toString function changed the length of the array or vector storage,
    // increase the length to handle the orignal number of actual values.
    switch (indexingType) {
1141 1142
    case ArrayWithInt32:
    case ArrayWithDouble:
1143
    case ArrayWithContiguous:
1144
        ensureLength(globalData, relevantLength);
1145
        break;
1146
        
1147 1148 1149 1150
    case ArrayWithArrayStorage:
        if (arrayStorage()->vectorLength() < relevantLength) {
            increaseVectorLength(exec->globalData(), relevantLength);
            begin = arrayStorage()->m_vector;
1151
        }
1152 1153 1154 1155 1156 1157 1158 1159
        if (arrayStorage()->length() < relevantLength)
            arrayStorage()->setLength(relevantLength);
        break;
        
    default:
        CRASH();
    }

1160 1161 1162 1163 1164 1165
    for (size_t i = 0; i < relevantLength; i++) {
        if (indexingType == ArrayWithDouble)
            static_cast<double*>(begin)[i] = values[i].first.asNumber();
        else
            static_cast<WriteBarrier<Unknown>*>(begin)[i].set(globalData, this, values[i].first);
    }
1166 1167 1168 1169 1170 1171 1172 1173 1174 1175
    
    Heap::heap(this)->popTempSortVector(&am