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