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