JSArray.cpp 40.6 KB
Newer Older
darin's avatar
darin committed
1 2
/*
 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3
 *  Copyright (C) 2003, 2007, 2008, 2009, 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

ggaren@apple.com's avatar
ggaren@apple.com committed
48
ASSERT_CLASS_FITS_IN_CELL(JSArray);
49
ASSERT_HAS_TRIVIAL_DESTRUCTOR(JSArray);
ggaren@apple.com's avatar
ggaren@apple.com committed
50

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

53
Butterfly* createArrayButterflyInDictionaryIndexingMode(JSGlobalData& globalData, unsigned initialLength)
darin's avatar
darin committed
54
{
55 56 57 58 59 60 61 62
    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;
63
#if CHECK_ARRAY_CONSISTENCY
64 65
    storage->m_initializationIndex = 0;
    storage->m_inCompactInitialization = 0;
66
#endif
67
    return butterfly;
68 69 70 71 72 73 74 75
}

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

76
    enterDictionaryIndexingMode(exec->globalData());
77

78
    SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get();
79 80 81 82 83
    ASSERT(map);
    map->setLengthIsReadOnly();
}

// Defined in ES5.1 15.4.5.1
84
bool JSArray::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor, bool throwException)
85
{
86
    JSArray* array = jsCast<JSArray*>(object);
87 88 89 90 91

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

        // m. If newWritable is false, then
157 158 159 160 161
        // 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());
162 163 164 165 166 167
        // n. Return true.
        return true;
    }

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

182
    return array->JSObject::defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException);
darin's avatar
darin committed
183 184
}

185
bool JSArray::getOwnPropertySlot(JSCell* cell, ExecState* exec, PropertyName propertyName, PropertySlot& slot)
186
{
187
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
188
    if (propertyName == exec->propertyNames().length) {
189
        slot.setValue(jsNumber(thisObject->length()));
darin's avatar
darin committed
190 191 192
        return true;
    }

193
    return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
darin's avatar
darin committed
194 195
}

196
bool JSArray::getOwnPropertyDescriptor(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor)
197
{
198
    JSArray* thisObject = jsCast<JSArray*>(object);
199
    if (propertyName == exec->propertyNames().length) {
200
        descriptor.setDescriptor(jsNumber(thisObject->length()), thisObject->isLengthWritable() ? DontDelete | DontEnum : DontDelete | DontEnum | ReadOnly);
201 202
        return true;
    }
203

204
    return JSObject::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor);
205 206
}

207
// ECMA 15.4.5.1
208
void JSArray::put(JSCell* cell, ExecState* exec, PropertyName propertyName, JSValue value, PutPropertySlot& slot)
209
{
210
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
211 212

    if (propertyName == exec->propertyNames().length) {
weinig@apple.com's avatar
weinig@apple.com committed
213 214
        unsigned newLength = value.toUInt32(exec);
        if (value.toNumber(exec) != static_cast<double>(newLength)) {
215
            throwError(exec, createRangeError(exec, ASCIILiteral("Invalid array length")));
darin's avatar
darin committed
216 217
            return;
        }
218
        thisObject->setLength(exec, newLength, slot.isStrictMode());
darin's avatar
darin committed
219 220 221
        return;
    }

222
    JSObject::put(thisObject, exec, propertyName, value, slot);
darin's avatar
darin committed
223 224
}

225
bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName)
226
{
227
    JSArray* thisObject = jsCast<JSArray*>(cell);
darin's avatar
darin committed
228 229 230 231

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

232
    return JSObject::deleteProperty(thisObject, exec, propertyName);
darin's avatar
darin committed
233 234
}

235 236
static int compareKeysForQSort(const void* a, const void* b)
{
237 238
    unsigned da = *static_cast<const unsigned*>(a);
    unsigned db = *static_cast<const unsigned*>(b);
239
    return (da > db) - (da < db);
darin's avatar
darin committed
240 241
}

242
void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
darin's avatar
darin committed
243
{
244
    JSArray* thisObject = jsCast<JSArray*>(object);
245

246 247 248
    if (mode == IncludeDontEnumProperties)
        propertyNames.add(exec->propertyNames().length);

249
    JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode);
250
}
darin's avatar
darin committed
251

252
// This method makes room in the vector, but leaves the new space uncleared.
253
bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, unsigned count)
254
{
255 256 257 258
    ArrayStorage* storage = ensureArrayStorage(globalData);
    Butterfly* butterfly = storage->butterfly();
    unsigned propertyCapacity = structure()->outOfLineCapacity();
    unsigned propertySize = structure()->outOfLineSize();
259

260 261
    // If not, we should have handled this on the fast path.
    ASSERT(count > storage->m_indexBias);
262

263 264 265 266 267 268 269
    // 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.

270 271
    unsigned length = storage->length();
    unsigned usedVectorLength = min(storage->vectorLength(), length);
272 273 274
    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)
275
        return false;
276 277 278
    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.
279 280
    ASSERT(storage->vectorLength() <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - storage->vectorLength()) >= storage->m_indexBias);
    unsigned currentCapacity = storage->vectorLength() + storage->m_indexBias;
281 282 283 284 285 286
    // The calculation of desiredCapacity won't overflow, due to the range of MAX_STORAGE_VECTOR_LENGTH.
    unsigned desiredCapacity = min(MAX_STORAGE_VECTOR_LENGTH, max(BASE_VECTOR_LEN, requiredVectorLength) << 1);

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

287
    void* newAllocBase = 0;
288 289 290
    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)) {
291
        newAllocBase = butterfly->base(structure());
292 293
        newStorageCapacity = currentCapacity;
    } else {
294 295
        size_t newSize = Butterfly::totalSize(0, propertyCapacity, true, ArrayStorage::sizeFor(desiredCapacity));
        if (!globalData.heap.tryAllocateStorage(newSize, &newAllocBase))
296 297 298 299 300 301 302 303 304 305 306 307
            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.
    // 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;
308
    if (length < storage->vectorLength()) {
309
        // Atomic decay, + the post-capacity cannot be greater than what is available.
310 311 312
        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);
313
    }
314 315 316 317 318 319 320 321 322 323 324 325 326
    
    unsigned newVectorLength = requiredVectorLength + postCapacity;
    unsigned newIndexBias = newStorageCapacity - newVectorLength;

    Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity);
    
    memmove(newButterfly->arrayStorage()->m_vector + count, storage->m_vector, sizeof(JSValue) * usedVectorLength);
    memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
    
    newButterfly->arrayStorage()->setVectorLength(newVectorLength);
    newButterfly->arrayStorage()->m_indexBias = newIndexBias;
    
    m_butterfly = newButterfly;
327

ap@webkit.org's avatar
ap@webkit.org committed
328
    return true;
darin's avatar
darin committed
329 330
}

331
bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
darin's avatar
darin committed
332
{
333
    checkIndexingConsistency();
334

335 336
    ArrayStorage* storage = ensureArrayStorage(exec->globalData());
    unsigned length = storage->length();
darin's avatar
darin committed
337

338
    // If the length is read only then we enter sparse mode, so should enter the following 'if'.
339
    ASSERT(isLengthWritable() || storage->m_sparseMap);
340

341
    if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
342 343 344 345 346 347 348 349 350 351
        // 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) {
352
                unsigned index = static_cast<unsigned>(it->first);
353 354 355 356 357 358 359 360 361 362 363 364 365 366
                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());
367
                    if (it->second.attributes & DontDelete) {
368
                        storage->setLength(index + 1);
369 370 371 372 373 374 375
                        return reject(exec, throwException, "Unable to delete property.");
                    }
                    map->remove(it);
                }
            } else {
                for (unsigned i = 0; i < keys.size(); ++i)
                    map->remove(keys[i]);
376
                if (map->isEmpty())
377
                    deallocateSparseIndexMap();
378 379 380 381
            }
        }
    }

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

393
    storage->setLength(newLength);
394

395
    checkIndexingConsistency();
396
    return true;
darin's avatar
darin committed
397 398
}

399
JSValue JSArray::pop(ExecState* exec)
400
{
401
    checkIndexingConsistency();
402
    
403
    switch (structure()->indexingType()) {
404
    case ArrayClass:
405
        return jsUndefined();
406 407 408 409 410 411 412 413 414 415
        
    case ArrayWithArrayStorage: {
        ArrayStorage* storage = m_butterfly->arrayStorage();
    
        unsigned length = storage->length();
        if (!length) {
            if (!isLengthWritable())
                throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
            return jsUndefined();
        }
416

417 418 419 420 421 422 423
        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();
424
            
425 426 427 428 429
                ASSERT(isLengthWritable());
                storage->setLength(index);
                checkIndexingConsistency();
                return element;
            }
430 431
        }

432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450
        // 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.
        checkIndexingConsistency();
        return element;
    }
        
    default:
        ASSERT_NOT_REACHED();
        return JSValue();
451
    }
452 453
}

454 455 456
// 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
457
void JSArray::push(ExecState* exec, JSValue value)
458
{
459 460 461
    checkIndexingConsistency();
    
    switch (structure()->indexingType()) {
462
    case ArrayClass: {
463 464
        putByIndexBeyondVectorLengthWithArrayStorage(exec, 0, value, true, createInitialArrayStorage(exec->globalData()));
        break;
465
    }
466 467 468 469 470 471 472 473 474 475 476 477 478
        
    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;
            checkIndexingConsistency();
            return;
        }
479

480 481 482 483 484 485 486 487
        // Pushing to an array of length 2^32-1 stores the property, but throws a range error.
        if (UNLIKELY(storage->length() == 0xFFFFFFFFu)) {
            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;
        }
488

489 490 491 492 493 494 495 496 497
        // Handled the same as putIndex.
        putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage);
        checkIndexingConsistency();
        break;
    }
        
    default:
        ASSERT_NOT_REACHED();
    }
498 499
}

500
bool JSArray::shiftCount(ExecState* exec, unsigned count)
501 502 503
{
    ASSERT(count > 0);
    
504
    ArrayStorage* storage = ensureArrayStorage(exec->globalData());
505
    
506
    unsigned oldLength = storage->length();
507
    
508 509
    // If the array contains holes or is otherwise in an abnormal state,
    // use the generic algorithm in ArrayPrototype.
510
    if (oldLength != storage->m_numValuesInVector || inSparseIndexingMode())
511
        return false;
512

513 514
    if (!oldLength)
        return true;
515
    
516
    storage->m_numValuesInVector -= count;
517
    storage->setLength(oldLength - count);
518
    
519 520 521
    unsigned vectorLength = storage->vectorLength();
    if (vectorLength) {
        count = min(vectorLength, (unsigned)count);
522
        
523 524
        vectorLength -= count;
        storage->setVectorLength(vectorLength);
525
        
526 527 528 529
        if (vectorLength) {
            m_butterfly = m_butterfly->shift(structure(), count);
            storage = m_butterfly->arrayStorage();
            storage->m_indexBias += count;
530 531
        }
    }
532
    return true;
533
}
534 535 536

// Returns true if the unshift can be handled, false to fallback.    
bool JSArray::unshiftCount(ExecState* exec, unsigned count)
537
{
538 539
    ArrayStorage* storage = ensureArrayStorage(exec->globalData());
    unsigned length = storage->length();
540

541 542
    // If the array contains holes or is otherwise in an abnormal state,
    // use the generic algorithm in ArrayPrototype.
543
    if (length != storage->m_numValuesInVector || storage->inSparseMode())
544 545
        return false;

546 547 548 549 550
    if (storage->m_indexBias >= count) {
        m_butterfly = storage->butterfly()->unshift(structure(), count);
        storage = m_butterfly->arrayStorage();
        storage->m_indexBias -= count;
        storage->setVectorLength(storage->vectorLength() + count);
551 552 553
    } else if (unshiftCountSlowCase(exec->globalData(), count))
        storage = arrayStorage();
    else {
554
        throwOutOfMemoryError(exec);
555
        return true;
556
    }
557

558
    WriteBarrier<Unknown>* vector = storage->m_vector;
559
    for (unsigned i = 0; i < count; i++)
560
        vector[i].clear();
561
    return true;
562 563
}

ggaren@apple.com's avatar
ggaren@apple.com committed
564 565
static int compareNumbersForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
566 567
    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
568 569 570
    return (da > db) - (da < db);
}

571 572
static int compareByStringPairForQSort(const void* a, const void* b)
{
ggaren@apple.com's avatar
ggaren@apple.com committed
573 574
    const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
    const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
575
    return codePointCompare(va->second, vb->second);
576
}
darin's avatar
darin committed
577

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

582
    switch (structure()->indexingType()) {
583
    case ArrayClass:
ggaren@apple.com's avatar
ggaren@apple.com committed
584 585
        return;
        
586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604
    case ArrayWithArrayStorage: {
        unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
        ArrayStorage* storage = m_butterfly->arrayStorage();
        
        if (storage->m_sparseMap.get()) {
            throwOutOfMemoryError(exec);
            return;
        }
        
        if (!lengthNotIncludingUndefined)
            return;
        
        bool allValuesAreNumbers = true;
        size_t size = storage->m_numValuesInVector;
        for (size_t i = 0; i < size; ++i) {
            if (!storage->m_vector[i].isNumber()) {
                allValuesAreNumbers = false;
                break;
            }
ggaren@apple.com's avatar
ggaren@apple.com committed
605
        }
606 607 608 609 610 611 612 613 614 615 616 617 618 619 620
        
        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(storage->m_vector, size, sizeof(WriteBarrier<Unknown>), compareNumbersForQSort);
        
        checkIndexingConsistency(SortConsistencyCheck);
        return;
    }
        
    default:
        ASSERT_NOT_REACHED();
ggaren@apple.com's avatar
ggaren@apple.com committed
621 622 623
    }
}

darin@apple.com's avatar
darin@apple.com committed
624
void JSArray::sort(ExecState* exec)
darin's avatar
darin committed
625
{
626
    ASSERT(!inSparseIndexingMode());
627
    
628
    switch (structure()->indexingType()) {
629
    case ArrayClass:
ap@webkit.org's avatar
ap@webkit.org committed
630
        return;
631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677
        
    case ArrayWithArrayStorage: {
        unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
        ArrayStorage* storage = m_butterfly->arrayStorage();
        if (storage->m_sparseMap.get()) {
            throwOutOfMemoryError(exec);
            return;
        }
        
        if (!lengthNotIncludingUndefined)
            return;
        
        // 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.
        
        Vector<ValueStringPair> values(lengthNotIncludingUndefined);
        if (!values.begin()) {
            throwOutOfMemoryError(exec);
            return;
        }
        
        Heap::heap(this)->pushTempSortVector(&values);
        
        bool isSortingPrimitiveValues = true;
        for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
            JSValue value = storage->m_vector[i].get();
            ASSERT(!value.isUndefined());
            values[i].first = value;
            isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();
        }
        
        // FIXME: The following loop continues to call toString on subsequent values even after
        // a toString call raises an exception.
        
        for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
            values[i].second = values[i].first.toWTFStringInline(exec);
        
        if (exec->hadException()) {
            Heap::heap(this)->popTempSortVector(&values);
            return;
        }
        
        // 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).
        
678
#if HAVE(MERGESORT)
679 680 681 682
        if (isSortingPrimitiveValues)
            qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
        else
            mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
683
#else
684 685 686
        // 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);
687
#endif
688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710
        
        // If the toString function changed the length of the array or vector storage,
        // increase the length to handle the orignal number of actual values.
        if (storage->vectorLength() < lengthNotIncludingUndefined) {
            increaseVectorLength(exec->globalData(), lengthNotIncludingUndefined);
            storage = m_butterfly->arrayStorage();
        }
        if (storage->length() < lengthNotIncludingUndefined)
            storage->setLength(lengthNotIncludingUndefined);
        
        JSGlobalData& globalData = exec->globalData();
        for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
            storage->m_vector[i].set(globalData, this, values[i].first);
        
        Heap::heap(this)->popTempSortVector(&values);
        
        checkIndexingConsistency(SortConsistencyCheck);
        return;
    }
        
    default:
        ASSERT_NOT_REACHED();
    }
darin's avatar
darin committed
711 712
}

ap@webkit.org's avatar
ap@webkit.org committed
713
struct AVLTreeNodeForArrayCompare {
ggaren@apple.com's avatar
ggaren@apple.com committed
714
    JSValue value;
ap@webkit.org's avatar
ap@webkit.org committed
715 716 717 718 719 720 721 722 723 724

    // 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
725
    typedef JSValue key;
ap@webkit.org's avatar
ap@webkit.org committed
726 727 728 729
    typedef int32_t size;

    Vector<AVLTreeNodeForArrayCompare> m_nodes;
    ExecState* m_exec;
ggaren@apple.com's avatar
ggaren@apple.com committed
730
    JSValue m_compareFunction;
darin@apple.com's avatar
darin@apple.com committed
731 732
    CallType m_compareCallType;
    const CallData* m_compareCallData;
733
    OwnPtr<CachedCall> m_cachedCall;
ap@webkit.org's avatar
ap@webkit.org committed
734 735 736 737 738 739 740 741 742 743 744 745 746 747

    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
748
    {
ap@webkit.org's avatar
ap@webkit.org committed
749 750 751 752 753 754 755
        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
756 757
            else
                m_nodes[h].gt &= 0x7FFFFFFF;
ap@webkit.org's avatar
ap@webkit.org committed
758
        }
darin's avatar
darin committed
759 760
    }

ap@webkit.org's avatar
ap@webkit.org committed
761
    int compare_key_key(key va, key vb)
ap@webkit.org's avatar
ap@webkit.org committed
762
    {
weinig@apple.com's avatar
weinig@apple.com committed
763 764
        ASSERT(!va.isUndefined());
        ASSERT(!vb.isUndefined());
darin's avatar
darin committed
765

ggaren@apple.com's avatar
ggaren@apple.com committed
766 767 768
        if (m_exec->hadException())
            return 1;

769 770
        double compareResult;
        if (m_cachedCall) {
771
            m_cachedCall->setThis(jsUndefined());
772 773
            m_cachedCall->setArgument(0, va);
            m_cachedCall->setArgument(1, vb);
774
            compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec));
775
        } else {
776
            MarkedArgumentBuffer arguments;
777 778
            arguments.append(va);
            arguments.append(vb);
779
            compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, jsUndefined(), arguments).toNumber(m_exec);
780
        }
ap@webkit.org's avatar
ap@webkit.org committed
781
        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
782
    }
darin's avatar
darin committed
783

ap@webkit.org's avatar
ap@webkit.org committed
784 785 786 787
    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
788
};
darin's avatar
darin committed
789

ggaren@apple.com's avatar
ggaren@apple.com committed
790
void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
darin's avatar
darin committed
791
{
792 793 794
    ASSERT(!inSparseIndexingMode());
    
    switch (structure()->indexingType()) {
795
    case ArrayClass:
ap@webkit.org's avatar
ap@webkit.org committed
796
        return;
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 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854
        
    case ArrayWithArrayStorage: {
        ArrayStorage* storage = m_butterfly->arrayStorage();
        checkIndexingConsistency();
        
        // FIXME: This ignores exceptions raised in the compare function or in toNumber.
        
        // The maximum tree depth is compiled in - but the caller is clearly up to no good
        // if a larger array is passed.
        ASSERT(storage->length() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
        if (storage->length() > static_cast<unsigned>(std::numeric_limits<int>::max()))
            return;
        
        unsigned usedVectorLength = min(storage->length(), storage->vectorLength());
        unsigned nodeCount = usedVectorLength + (storage->m_sparseMap ? storage->m_sparseMap->size() : 0);
        
        if (!nodeCount)
            return;
        
        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);
        
        if (callType == CallTypeJS)
            tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, jsCast<JSFunction*>(compareFunction), 2));
        
        if (!tree.abstractor().m_nodes.begin()) {
            throwOutOfMemoryError(exec);
            return;
        }
        
        // 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) {
            JSValue v = storage->m_vector[numDefined].get();
            if (!v || v.isUndefined())
                break;
            tree.abstractor().m_nodes[numDefined].value = v;
            tree.insert(numDefined);
        }
        for (unsigned i = numDefined; i < usedVectorLength; ++i) {
            JSValue v = storage->m_vector[i].get();
            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
855 856
            }
        }
857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875
        
        unsigned newUsedVectorLength = numDefined + numUndefined;
        
        if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
            newUsedVectorLength += map->size();
            if (newUsedVectorLength > storage->vectorLength()) {
                // Check that it is possible to allocate an array large enough to hold all the entries.
                if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(exec->globalData(), newUsedVectorLength)) {
                    throwOutOfMemoryError(exec);
                    return;
                }
                storage = m_butterfly->arrayStorage();
            }
            
            SparseArrayValueMap::const_iterator end = map->end();
            for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
                tree.abstractor().m_nodes[numDefined].value = it->second.getNonSparseMode();
                tree.insert(numDefined);
                ++numDefined;
ap@webkit.org's avatar
ap@webkit.org committed
876
            }
877 878
            
            deallocateSparseIndexMap();
ap@webkit.org's avatar
ap@webkit.org committed
879
        }
880 881 882 883 884 885 886 887 888 889 890 891 892
        
        ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
        
        // FIXME: If the compare function changed the length of the array, the following might be
        // modifying the vector incorrectly.
        
        // Copy the values back into m_storage.
        AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
        iter.start_iter_least(tree);
        JSGlobalData& globalData = exec->globalData();
        for (unsigned i = 0; i < numDefined; ++i) {
            storage->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
            ++iter;
ap@webkit.org's avatar
ap@webkit.org committed
893
        }
894 895 896 897 898 899 900 901 902 903 904 905 906
        
        // Put undefined values back in.
        for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
            storage->m_vector[i].setUndefined();
        
        // Ensure that unused values in the vector are zeroed out.
        for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
            storage->m_vector[i].clear();
        
        storage->m_numValuesInVector = newUsedVectorLength;
        
        checkIndexingConsistency(SortConsistencyCheck);
        return;
ap@webkit.org's avatar
ap@webkit.org committed
907
    }
908 909 910
        
    default:
        ASSERT_NOT_REACHED();
ap@webkit.org's avatar
ap@webkit.org committed
911
    }
darin's avatar
darin committed
912 913
}

914
void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
weinig@apple.com's avatar
weinig@apple.com committed
915
{
916
    switch (structure()->indexingType()) {
917
    case ArrayClass:
918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939
        return;
    
    case ArrayWithArrayStorage: {
        ArrayStorage* storage = m_butterfly->arrayStorage();
        
        WriteBarrier<Unknown>* vector = storage->m_vector;
        unsigned vectorEnd = min(storage->length(), storage->vectorLength());
        unsigned i = 0;
        for (; i < vectorEnd; ++i) {
            WriteBarrier<Unknown>& v = vector[i];
            if (!v)
                break;
            args.append(v.get());
        }
        
        for (; i < storage->length(); ++i)
            args.append(get(exec, i));
        return;
    }
        
    default:
        ASSERT_NOT_REACHED();
940
    }
weinig@apple.com's avatar
weinig@apple.com committed
941 942
}

943
void JSArray::copyToArguments(ExecState* exec, CallFrame* callFrame, uint32_t length)
944
{
945
    ASSERT(length == this->length());
946
    switch (structure()->indexingType()) {
947
    case ArrayClass:
948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968
        return;
        
    case ArrayWithArrayStorage: {
        ArrayStorage* storage = m_butterfly->arrayStorage();
        unsigned i = 0;
        WriteBarrier<Unknown>* vector = storage->m_vector;
        unsigned vectorEnd = min(length, storage->vectorLength());
        for (; i < vectorEnd; ++i) {
            WriteBarrier<Unknown>& v = vector[i];
            if (!v)
                break;
            callFrame->setArgument(i, v.get());
        }
        
        for (; i < length; ++i)
            callFrame->setArgument(i, get(exec, i));
        return;
    }
        
    default:
        ASSERT_NOT_REACHED();
969
    }
970 971
}

972
unsigned JSArray::compactForSorting(JSGlobalData& globalData)
darin's avatar
darin committed
973
{
974
    ASSERT(!inSparseIndexingMode());
darin's avatar
darin committed
975

976 977 978
    checkIndexingConsistency();
    
    switch (structure()->indexingType()) {
979
    case ArrayClass:
980
        return 0;
981

982 983 984 985 986 987 988 989 990 991 992 993
    case ArrayWithArrayStorage: {
        ArrayStorage* storage = m_butterfly->arrayStorage();
        
        unsigned usedVectorLength = min(storage->length(), storage->vectorLength());
        
        unsigned numDefined = 0;
        unsigned numUndefined = 0;
        
        for (; numDefined < usedVectorLength; ++numDefined) {
            JSValue v = storage->m_vector[numDefined].get();
            if (!v || v.isUndefined())
                break;
darin's avatar
darin committed
994
        }
995 996 997 998 999 1000 1001 1002 1003
        
        for (unsigned i = numDefined; i < usedVectorLength; ++i) {
            JSValue v = storage->m_vector[i].get();
            if (v) {
                if (v.isUndefined())
                    ++numUndefined;
                else
                    storage->m_vector[numDefined++].setWithoutWriteBarrier(v);
            }
darin's avatar
darin committed
1004
        }
1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023
        
        unsigned newUsedVectorLength = numDefined + numUndefined;
        
        if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
            newUsedVectorLength += map->size();
            if (newUsedVectorLength > storage->vectorLength()) {
                // Check that it is possible to allocate an array large enough to hold all the entries - if not,
                // exception is thrown by caller.
                if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(globalData, newUsedVectorLength))
                    return 0;
                
                storage = m_butterfly->arrayStorage();
            }
            
            SparseArrayValueMap::const_iterator end = map->end();
            for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
                storage->m_vector[numDefined++].setWithoutWriteBarrier(it->second.getNonSparseMode());
            
            deallocateSparseIndexMap();
1024
        }
1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035
        
        for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
            storage->m_vector[i].setUndefined();
        for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
            storage->m_vector[i].clear();
        
        storage->m_numValuesInVector = newUsedVectorLength;
        
        checkIndexingConsistency(SortConsistencyCheck);
        
        return numDefined;
1036
    }
1037 1038 1039 1040
        
    default:
        ASSERT_NOT_REACHED();
        return 0;
1041 1042 1043 1044
    }
}


1045
} // namespace JSC