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