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