JSArray.cpp 49.2 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 "ButterflyInlineMethods.h"
mhahnenberg@apple.com's avatar
mhahnenberg@apple.com committed
28 29
#include "CopiedSpace.h"
#include "CopiedSpaceInlineMethods.h"
30
#include "CachedCall.h"
31
#include "Error.h"
32
#include "Executable.h"
33
#include "GetterSetter.h"
34
#include "IndexingHeaderInlineMethods.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 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444
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()));
        }
        createInitialContiguous(exec->globalData(), newLength);
        return true;
        
    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
                && !isDenseEnoughForVector(newLength, countElementsInContiguous(m_butterfly)))) {
            return setLengthWithArrayStorage(
                exec, newLength, throwException,
                convertContiguousToArrayStorage(exec->globalData()));
        }
        if (newLength > m_butterfly->publicLength()) {
            ensureContiguousLength(exec->globalData(), newLength);
            return true;
        }
        for (unsigned i = m_butterfly->publicLength(); i-- > newLength;)
            m_butterfly->contiguous()[i].clear();
        m_butterfly->setPublicLength(newLength);
        return true;
        
    case ArrayWithArrayStorage:
    case ArrayWithSlowPutArrayStorage:
        return setLengthWithArrayStorage(exec, newLength, throwException, arrayStorage());
        
    default:
        CRASH();
        return false;
    }
}

445
JSValue JSArray::pop(ExecState* exec)
446
{
447
    switch (structure()->indexingType()) {
448
    case ArrayClass:
449
        return jsUndefined();
450
        
451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466
    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;
    }
        
467
    case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
468 469 470 471 472 473 474 475
        ArrayStorage* storage = m_butterfly->arrayStorage();
    
        unsigned length = storage->length();
        if (!length) {
            if (!isLengthWritable())
                throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
            return jsUndefined();
        }
476

477 478 479 480 481 482 483
        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();
484
            
485 486 487 488
                ASSERT(isLengthWritable());
                storage->setLength(index);
                return element;
            }
489
        }
490
        break;
491 492 493
    }
        
    default:
494
        CRASH();
495
        return JSValue();
496
    }
497 498 499 500 501 502 503 504 505 506 507 508 509 510 511
    
    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;
512 513
}

514 515 516
// 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
517
void JSArray::push(ExecState* exec, JSValue value)
518
{
519
    switch (structure()->indexingType()) {
520
    case ArrayClass: {
521 522
        putByIndexBeyondVectorLengthWithArrayStorage(exec, 0, value, true, createInitialArrayStorage(exec->globalData()));
        break;
523
    }
524
        
525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544
    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;
        }
        
        putByIndexBeyondVectorLengthContiguousWithoutAttributes(exec, length, value);
        return;
    }
        
545 546 547 548 549 550 551 552 553 554
    case ArrayWithSlowPutArrayStorage: {
        unsigned oldLength = length();
        if (attemptToInterceptPutByIndexOnHole(exec, oldLength, value, true)) {
            if (!exec->hadException() && oldLength < 0xFFFFFFFFu)
                setLength(exec, oldLength + 1, true);
            return;
        }
        // Fall through.
    }
        
555 556 557 558 559 560 561 562 563 564 565
    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;
        }
566

567 568
        // Pushing to an array of invalid length (2^31-1) stores the property, but throws a range error.
        if (storage->length() > MAX_ARRAY_INDEX) {
569 570 571 572 573 574
            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;
        }
575

576 577 578 579 580 581 582 583
        // Handled the same as putIndex.
        putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage);
        break;
    }
        
    default:
        ASSERT_NOT_REACHED();
    }
584 585
}

586
bool JSArray::shiftCountWithArrayStorage(unsigned startIndex, unsigned count, ArrayStorage* storage)
587
{
588
    unsigned oldLength = storage->length();
589
    ASSERT(count <= oldLength);
590
    
591 592
    // If the array contains holes or is otherwise in an abnormal state,
    // use the generic algorithm in ArrayPrototype.
593
    if (oldLength != storage->m_numValuesInVector || inSparseIndexingMode() || shouldUseSlowPut(structure()->indexingType()))
594
        return false;
595

596 597
    if (!oldLength)
        return true;
598
    
599 600
    unsigned length = oldLength - count;
    
601
    storage->m_numValuesInVector -= count;
602
    storage->setLength(length);
603
    
604
    unsigned vectorLength = storage->vectorLength();
605 606 607 608 609 610 611 612 613 614 615 616 617 618
    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);
    
619
    if (vectorLength) {
620 621 622 623 624 625 626
        if (startIndex < usedVectorLength - (startIndex + count)) {
            if (startIndex) {
                memmove(
                    storage->m_vector + count,
                    storage->m_vector,
                    sizeof(JSValue) * startIndex);
            }
627 628 629
            m_butterfly = m_butterfly->shift(structure(), count);
            storage = m_butterfly->arrayStorage();
            storage->m_indexBias += count;
630 631 632 633 634 635 636
        } 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();
637 638
        }
    }
639
    return true;
640
}
641

642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694
bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
{
    ASSERT(count > 0);
    
    switch (structure()->indexingType()) {
    case ArrayClass:
        return true;
        
    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)
            return shiftCountWithArrayStorage(startIndex, count, convertContiguousToArrayStorage(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.
            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.
                return shiftCountWithArrayStorage(startIndex, count, convertContiguousToArrayStorage(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->contiguous()[i].setWithoutWriteBarrier(v);
        }
        for (unsigned i = end; i < oldLength; ++i)
            m_butterfly->contiguous()[i].clear();
        
        m_butterfly->setPublicLength(oldLength - count);
        return true;
    }
        
    case ArrayWithArrayStorage:
    case ArrayWithSlowPutArrayStorage:
        return shiftCountWithArrayStorage(startIndex, count, arrayStorage());
        
    default:
        CRASH();
        return false;
    }
}

695
// Returns true if the unshift can be handled, false to fallback.    
696
bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, unsigned count, ArrayStorage* storage)
697
{
698
    unsigned length = storage->length();
699

700 701
    ASSERT(startIndex <= length);

702 703
    // If the array contains holes or is otherwise in an abnormal state,
    // use the generic algorithm in ArrayPrototype.
704
    if (length != storage->m_numValuesInVector || storage->inSparseMode() || shouldUseSlowPut(structure()->indexingType()))
705 706
        return false;

707 708 709 710 711
    bool moveFront = !startIndex || startIndex < length / 2;

    unsigned vectorLength = storage->vectorLength();

    if (moveFront && storage->m_indexBias >= count) {
712 713 714
        m_butterfly = storage->butterfly()->unshift(structure(), count);
        storage = m_butterfly->arrayStorage();
        storage->m_indexBias -= count;
715 716 717 718
        storage->setVectorLength(vectorLength + count);
    } else if (!moveFront && vectorLength - length >= count)
        storage = storage->butterfly()->arrayStorage();
    else if (unshiftCountSlowCase(exec->globalData(), moveFront, count))
719 720
        storage = arrayStorage();
    else {
721
        throwOutOfMemoryError(exec);
722
        return true;
723
    }
724

725
    WriteBarrier<Unknown>* vector = storage->m_vector;
726 727 728 729

    if (startIndex) {
        if (moveFront)
            memmove(vector, vector + count, startIndex * sizeof(JSValue));
730
        else if (length - startIndex)
731 732 733
            memmove(vector + startIndex + count, vector + startIndex, (length - startIndex) * sizeof(JSValue));
    }

734
    for (unsigned i = 0; i < count; i++)
735
        vector[i + startIndex].clear();
736
    return true;
737 738
}

739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780
bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
{
    switch (structure()->indexingType()) {
    case ArrayClass:
        // We could handle this. But it shouldn't ever come up, so we won't.
        return false;
        
    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)
            return unshiftCountWithArrayStorage(exec, startIndex, count, convertContiguousToArrayStorage(exec->globalData()));
        
        ensureContiguousLength(exec->globalData(), oldLength + count);
        
        for (unsigned i = oldLength; i-- > startIndex;) {
            JSValue v = m_butterfly->contiguous()[i].get();
            if (UNLIKELY(!v))
                return unshiftCountWithArrayStorage(exec, startIndex, count, convertContiguousToArrayStorage(exec->globalData()));
            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;
    }
        
    case ArrayWithArrayStorage:
    case ArrayWithSlowPutArrayStorage:
        return unshiftCountWithArrayStorage(exec, startIndex, count, arrayStorage());
        
    default:
        CRASH();
        return false;
    }
}

ggaren@apple.com's avatar
ggaren@apple.com committed
781 782
static int compareNumbersForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
783 784
    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
785 786 787
    return (da > db) - (da < db);
}

788 789
static int compareByStringPairForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
790 791
    const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
    const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
792
    return codePointCompare(va->second, vb->second);
793
}
darin's avatar
darin committed
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 820 821 822 823 824 825 826 827 828 829 830 831 832 833
template<IndexingType indexingType>
void JSArray::sortNumericVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
{
    ASSERT(indexingType == ArrayWithContiguous || indexingType == ArrayWithArrayStorage);
    
    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;
    for (size_t i = 0; i < newRelevantLength; ++i) {
        if (!data[i].isNumber()) {
            allValuesAreNumbers = false;
            break;
        }
    }
    
    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.
    qsort(data, newRelevantLength, sizeof(WriteBarrier<Unknown>), compareNumbersForQSort);
    return;
}

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

838
    switch (structure()->indexingType()) {
839
    case ArrayClass:
ggaren@apple.com's avatar
ggaren@apple.com committed
840 841
        return;
        
842 843 844
    case ArrayWithContiguous:
        sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
        return;
845

846 847
    case ArrayWithArrayStorage:
        sortNumericVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
848 849 850
        return;
        
    default:
851 852
        CRASH();
        return;
ggaren@apple.com's avatar
ggaren@apple.com committed
853 854 855
    }
}

856 857
template<IndexingType indexingType>
void JSArray::sortCompactedVector(ExecState* exec, WriteBarrier<Unknown>* begin, unsigned relevantLength)
darin's avatar
darin committed
858
{
859
    if (!relevantLength)
ap@webkit.org's avatar
ap@webkit.org committed
860
        return;
861 862 863 864 865 866 867
    
    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.
868
        
869 870 871 872 873
    Vector<ValueStringPair> values(relevantLength);
    if (!values.begin()) {
        throwOutOfMemoryError(exec);
        return;
    }
874
        
875
    Heap::heap(this)->pushTempSortVector(&values);
876
        
877 878 879 880 881 882 883
    bool isSortingPrimitiveValues = true;
    for (size_t i = 0; i < relevantLength; i++) {
        JSValue value = begin[i].get();
        ASSERT(!value.isUndefined());
        values[i].first = value;
        isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();
    }
884
        
885 886
    // FIXME: The following loop continues to call toString on subsequent values even after
    // a toString call raises an exception.
887
        
888 889
    for (size_t i = 0; i < relevantLength; i++)
        values[i].second = values[i].first.toWTFStringInline(exec);
890
        
891 892 893 894
    if (exec->hadException()) {
        Heap::heap(this)->popTempSortVector(&values);
        return;
    }
895
        
896 897
    // 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).
898
        
899
#if HAVE(MERGESORT)
900
    if (isSortingPrimitiveValues)
901
        qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
902 903 904 905 906 907
    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);
908
#endif
909 910 911 912 913 914 915
    
    // 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) {
    case ArrayWithContiguous:
        ensureContiguousLength(globalData, relevantLength);
        break;
916
        
917 918 919 920
    case ArrayWithArrayStorage:
        if (arrayStorage()->vectorLength() < relevantLength) {
            increaseVectorLength(exec->globalData(), relevantLength);
            begin = arrayStorage()->m_vector;
921
        }
922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942
        if (arrayStorage()->length() < relevantLength)
            arrayStorage()->setLength(relevantLength);
        break;
        
    default:
        CRASH();
    }

    for (size_t i = 0; i < relevantLength; i++)
        begin[i].set(globalData, this, values[i].first);
    
    Heap::heap(this)->popTempSortVector(&values);
}

void JSArray::sort(ExecState* exec)
{
    ASSERT(!inSparseIndexingMode());
    
    switch (structure()->indexingType()) {
    case ArrayClass:
        return;
943
        
944 945 946 947 948
    case ArrayWithContiguous: {
        unsigned lengthNotIncludingUndefined;
        unsigned newRelevantLength;
        compactForSorting<ArrayWithContiguous>(
            lengthNotIncludingUndefined, newRelevantLength);
949
        
950 951 952 953
        sortCompactedVector<ArrayWithContiguous>(
            exec, m_butterfly->contiguous(), lengthNotIncludingUndefined);
        return;
    }
954
        
955 956 957 958 959 960 961 962 963 964
    case ArrayWithArrayStorage: {
        unsigned lengthNotIncludingUndefined;
        unsigned newRelevantLength;
        compactForSorting<ArrayWithArrayStorage>(
            lengthNotIncludingUndefined, newRelevantLength);
        ArrayStorage* storage = m_butterfly->arrayStorage();
        ASSERT(!storage->m_sparseMap);
        
        sortCompactedVector<ArrayWithArrayStorage>(
            exec, storage->m_vector, lengthNotIncludingUndefined);
965 966 967 968 969 970
        return;
    }
        
    default:
        ASSERT_NOT_REACHED();
    }
darin's avatar
darin committed
971 972
}

ap@webkit.org's avatar
ap@webkit.org committed
973
struct AVLTreeNodeForArrayCompare {
ggaren@apple.com's avatar
ggaren@apple.com committed
974
    JSValue value;
ap@webkit.org's avatar
ap@webkit.org committed
975 976 977 978 979 980 981 982 983 984

    // Child pointers.  The high bit of gt is robbed and used as the
    // balance factor sign.  The high bit of lt is robbed and used as
    // the magnitude of the balance factor.
    int32_t gt;
    int32_t lt;
};

struct AVLTreeAbstractorForArrayCompare {
    typedef int32_t handle; // Handle is an index into m_nodes vector.
ggaren@apple.com's avatar
ggaren@apple.com committed
985
    typedef JSValue key;
ap@webkit.org's avatar
ap@webkit.org committed
986 987 988 989
    typedef int32_t size;

    Vector<AVLTreeNodeForArrayCompare> m_nodes;
    ExecState* m_exec;
ggaren@apple.com's avatar
ggaren@apple.com committed
990
    JSValue m_compareFunction;
darin@apple.com's avatar
darin@apple.com committed
991 992
    CallType m_compareCallType;
    const CallData* m_compareCallData;
993
    OwnPtr<CachedCall> m_cachedCall;
ap@webkit.org's avatar
ap@webkit.org committed
994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007

    handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
    void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; }
    handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; }
    void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; }

    int get_balance_factor(handle h)
    {
        if (m_nodes[h].gt & 0x80000000)
            return -1;
        return static_cast<unsigned>(m_nodes[h].lt) >> 31;
    }

    void set_balance_factor(handle h, int bf)
darin's avatar
darin committed
1008
    {
ap@webkit.org's avatar
ap@webkit.org committed
1009 1010 1011 1012 1013 1014 1015
        if (bf == 0) {
            m_nodes[h].lt &= 0x7FFFFFFF;
            m_nodes[h].gt &= 0x7FFFFFFF;
        } else {
            m_nodes[h].lt |= 0x80000000;
            if (bf < 0)
                m_nodes[h].gt |= 0x80000000;
ap@webkit.org's avatar
ap@webkit.org committed
1016 1017
            else
                m_nodes[h].gt &= 0x7FFFFFFF;
ap@webkit.org's avatar
ap@webkit.org committed
1018
        }
darin's avatar
darin committed
1019 1020
    }

ap@webkit.org's avatar
ap@webkit.org committed
1021
    int compare_key_key(key va, key vb)
ap@webkit.org's avatar
ap@webkit.org committed
1022
    {
weinig@apple.com's avatar
weinig@apple.com committed
1023 1024
        ASSERT(!va.isUndefined());
        ASSERT(!vb.isUndefined());
darin's avatar
darin committed
1025

ggaren@apple.com's avatar
ggaren@apple.com committed
1026 1027 1028
        if (m_exec->hadException())
            return 1;

1029 1030
        double compareResult;
        if (m_cachedCall) {
1031
            m_cachedCall->setThis(jsUndefined());
1032 1033
            m_cachedCall->setArgument(0, va);
            m_cachedCall->setArgument(1, vb);
1034
            compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec));
1035
        } else {
1036
            MarkedArgumentBuffer arguments;
1037 1038
            arguments.append(va);
            arguments.append(vb);
1039
            compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, jsUndefined(), arguments).toNumber(m_exec);
1040
        }
ap@webkit.org's avatar
ap@webkit.org committed
1041
        return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
ap@webkit.org's avatar
ap@webkit.org committed
1042
    }
darin's avatar
darin committed
1043

ap@webkit.org's avatar
ap@webkit.org committed
1044 1045 1046 1047
    int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
    int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }

    static handle null() { return 0x7FFFFFFF; }
ap@webkit.org's avatar
ap@webkit.org committed
1048
};
darin's avatar
darin committed
1049

1050 1051
template<IndexingType indexingType>
void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
darin's avatar
darin committed
1052
{
1053
    ASSERT(!inSparseIndexingMode());
1054
    ASSERT(indexingType == structure()->indexingType());
1055
    
1056
    // FIXME: This ignores exceptions raised in the compare function or in toNumber.
1057
        
1058 1059 1060 1061 1062
    // The maximum tree depth is compiled in - but the caller is clearly up to no good
    // if a larger array is passed.
    ASSERT(m_butterfly->publicLength() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
    if (m_butterfly->publicLength() > static_cast<unsigned>(std::numeric_limits<int>::max()))
        return;
1063
        
1064 1065
    unsigned usedVectorLength = relevantLength<indexingType>();
    unsigned nodeCount = usedVectorLength;
1066
        
1067 1068
    if (!nodeCount)
        return;
1069
        
1070 1071 1072 1073 1074 1075
    AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
    tree.abstractor().m_exec = exec;
    tree.abstractor().m_compareFunction = compareFunction;
    tree.abstractor().m_compareCallType = callType;
    tree.abstractor().m_compareCallData = &callData;
    tree.abstractor().m_nodes.grow(nodeCount);
1076
        
1077 1078
    if (callType == CallTypeJS)
        tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, jsCast<JSFunction*>(compareFunction), 2));
1079
        
1080 1081 1082 1083
    if (!tree.abstractor().m_nodes.begin()) {
        throwOutOfMemoryError(exec);
        return;
    }
1084
        
1085 1086 1087 1088 1089 1090 1091 1092 1093 1094
    // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
    // right out from under us while we're building the tree here.
        
    unsigned numDefined = 0;
    unsigned numUndefined = 0;
        
    // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
    for (; numDefined < usedVectorLength; ++numDefined) {
        if (numDefined > m_butterfly->vectorLength())
            break;
1095
        JSValue v = currentIndexingData()[numDefined].get();
1096 1097 1098 1099 1100 1101 1102 1103
        if (!v || v.isUndefined())
            break;
        tree.abstractor().m_nodes[numDefined].value = v;
        tree.insert(numDefined);
    }
    for (unsigned i = numDefined; i < usedVectorLength; ++i) {
        if (i > m_butterfly->vectorLength())
            break;
1104
        JSValue v = currentIndexingData()[i].get();
1105 1106 1107 1108 1109 1110 1111
        if (v) {
            if (v.isUndefined())
                ++numUndefined;
            else {
                tree.abstractor().m_nodes[numDefined].value = v;
                tree.insert(numDefined);
                ++numDefined;
ap@webkit.org's avatar
ap@webkit.org committed
1112 1113
            }
        }
1114
    }
1115
        
1116
    unsigned newUsedVectorLength = numDefined + numUndefined;