Move the setting up of callee's callFrame from pushFrame to callToJavaScript thunk
[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 STATIC_ASSERT_IS_TRIVIALLY_DESTRUCTIBLE(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             exec->vm().throwException(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             exec->vm().throwException(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                 exec->vm().throwException(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                 exec->vm().throwException(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                 exec->vm().throwException(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                 exec->vm().throwException(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     unsigned numElementsBeforeShiftRegion = startIndex;
704     unsigned firstIndexAfterShiftRegion = startIndex + count;
705     unsigned numElementsAfterShiftRegion = usedVectorLength - firstIndexAfterShiftRegion;
706     ASSERT(numElementsBeforeShiftRegion + count + numElementsAfterShiftRegion == usedVectorLength);
707
708     // The point of this comparison seems to be to minimize the amount of elements that have to 
709     // be moved during a shift operation.
710     if (numElementsBeforeShiftRegion < numElementsAfterShiftRegion) {
711         // The number of elements before the shift region is less than the number of elements
712         // after the shift region, so we move the elements before to the right.
713         if (numElementsBeforeShiftRegion) {
714             RELEASE_ASSERT(count + startIndex <= vectorLength);
715             memmove(
716                 storage->m_vector + count,
717                 storage->m_vector,
718                 sizeof(JSValue) * startIndex);
719         }
720         // Adjust the Butterfly and the index bias. We only need to do this here because we're changing
721         // the start of the Butterfly, which needs to point at the first indexed property in the used
722         // portion of the vector.
723         m_butterfly = m_butterfly->shift(structure(), count);
724         storage = m_butterfly->arrayStorage();
725         storage->m_indexBias += count;
726
727         // Since we're consuming part of the vector by moving its beginning to the left,
728         // we need to modify the vector length appropriately.
729         storage->setVectorLength(vectorLength - count);
730     } else {
731         // The number of elements before the shift region is greater than or equal to the number 
732         // of elements after the shift region, so we move the elements after the shift region to the left.
733         memmove(
734             storage->m_vector + startIndex,
735             storage->m_vector + firstIndexAfterShiftRegion,
736             sizeof(JSValue) * numElementsAfterShiftRegion);
737         // Clear the slots of the elements we just moved.
738         unsigned startOfEmptyVectorTail = usedVectorLength - count;
739         for (unsigned i = startOfEmptyVectorTail; i < usedVectorLength; ++i)
740             storage->m_vector[i].clear();
741         // We don't modify the index bias or the Butterfly pointer in this case because we're not changing 
742         // the start of the Butterfly, which needs to point at the first indexed property in the used 
743         // portion of the vector. We also don't modify the vector length because we're not actually changing
744         // its length; we're just using less of it.
745     }
746     
747     return true;
748 }
749
750 bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
751 {
752     RELEASE_ASSERT(count > 0);
753     
754     switch (structure()->indexingType()) {
755     case ArrayClass:
756         return true;
757         
758     case ArrayWithUndecided:
759         // Don't handle this because it's confusing and it shouldn't come up.
760         return false;
761         
762     case ArrayWithInt32:
763     case ArrayWithContiguous: {
764         unsigned oldLength = m_butterfly->publicLength();
765         RELEASE_ASSERT(count <= oldLength);
766         
767         // We may have to walk the entire array to do the shift. We're willing to do
768         // so only if it's not horribly slow.
769         if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
770             return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm()));
771
772         // Storing to a hole is fine since we're still having a good time. But reading from a hole 
773         // is totally not fine, since we might have to read from the proto chain.
774         // We have to check for holes before we start moving things around so that we don't get halfway 
775         // through shifting and then realize we should have been in ArrayStorage mode.
776         unsigned end = oldLength - count;
777         for (unsigned i = startIndex; i < end; ++i) {
778             JSValue v = m_butterfly->contiguous()[i + count].get();
779             if (UNLIKELY(!v))
780                 return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm()));
781         }
782
783         for (unsigned i = startIndex; i < end; ++i) {
784             JSValue v = m_butterfly->contiguous()[i + count].get();
785             ASSERT(v);
786             // No need for a barrier since we're just moving data around in the same vector.
787             // This is in line with our standing assumption that we won't have a deletion
788             // barrier.
789             m_butterfly->contiguous()[i].setWithoutWriteBarrier(v);
790         }
791         for (unsigned i = end; i < oldLength; ++i)
792             m_butterfly->contiguous()[i].clear();
793         
794         m_butterfly->setPublicLength(oldLength - count);
795         return true;
796     }
797         
798     case ArrayWithDouble: {
799         unsigned oldLength = m_butterfly->publicLength();
800         RELEASE_ASSERT(count <= oldLength);
801         
802         // We may have to walk the entire array to do the shift. We're willing to do
803         // so only if it's not horribly slow.
804         if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
805             return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm()));
806
807         // Storing to a hole is fine since we're still having a good time. But reading from a hole 
808         // is totally not fine, since we might have to read from the proto chain.
809         // We have to check for holes before we start moving things around so that we don't get halfway 
810         // through shifting and then realize we should have been in ArrayStorage mode.
811         unsigned end = oldLength - count;
812         for (unsigned i = startIndex; i < end; ++i) {
813             double v = m_butterfly->contiguousDouble()[i + count];
814             if (UNLIKELY(v != v))
815                 return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm()));
816         }
817             
818         for (unsigned i = startIndex; i < end; ++i) {
819             double v = m_butterfly->contiguousDouble()[i + count];
820             ASSERT(v == v);
821             // No need for a barrier since we're just moving data around in the same vector.
822             // This is in line with our standing assumption that we won't have a deletion
823             // barrier.
824             m_butterfly->contiguousDouble()[i] = v;
825         }
826         for (unsigned i = end; i < oldLength; ++i)
827             m_butterfly->contiguousDouble()[i] = QNaN;
828         
829         m_butterfly->setPublicLength(oldLength - count);
830         return true;
831     }
832         
833     case ArrayWithArrayStorage:
834     case ArrayWithSlowPutArrayStorage:
835         return shiftCountWithArrayStorage(startIndex, count, arrayStorage());
836         
837     default:
838         CRASH();
839         return false;
840     }
841 }
842
843 // Returns true if the unshift can be handled, false to fallback.    
844 bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, unsigned count, ArrayStorage* storage)
845 {
846     unsigned length = storage->length();
847
848     RELEASE_ASSERT(startIndex <= length);
849
850     // If the array contains holes or is otherwise in an abnormal state,
851     // use the generic algorithm in ArrayPrototype.
852     if (length != storage->m_numValuesInVector || storage->inSparseMode() || shouldUseSlowPut(structure()->indexingType()))
853         return false;
854
855     bool moveFront = !startIndex || startIndex < length / 2;
856
857     unsigned vectorLength = storage->vectorLength();
858
859     if (moveFront && storage->m_indexBias >= count) {
860         m_butterfly = storage->butterfly()->unshift(structure(), count);
861         storage = m_butterfly->arrayStorage();
862         storage->m_indexBias -= count;
863         storage->setVectorLength(vectorLength + count);
864     } else if (!moveFront && vectorLength - length >= count)
865         storage = storage->butterfly()->arrayStorage();
866     else if (unshiftCountSlowCase(exec->vm(), moveFront, count))
867         storage = arrayStorage();
868     else {
869         throwOutOfMemoryError(exec);
870         return true;
871     }
872
873     WriteBarrier<Unknown>* vector = storage->m_vector;
874
875     if (startIndex) {
876         if (moveFront)
877             memmove(vector, vector + count, startIndex * sizeof(JSValue));
878         else if (length - startIndex)
879             memmove(vector + startIndex + count, vector + startIndex, (length - startIndex) * sizeof(JSValue));
880     }
881
882     for (unsigned i = 0; i < count; i++)
883         vector[i + startIndex].clear();
884     return true;
885 }
886
887 bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
888 {
889     switch (structure()->indexingType()) {
890     case ArrayClass:
891     case ArrayWithUndecided:
892         // We could handle this. But it shouldn't ever come up, so we won't.
893         return false;
894
895     case ArrayWithInt32:
896     case ArrayWithContiguous: {
897         unsigned oldLength = m_butterfly->publicLength();
898         
899         // We may have to walk the entire array to do the unshift. We're willing to do so
900         // only if it's not horribly slow.
901         if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
902             return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
903         
904         ensureLength(exec->vm(), oldLength + count);
905
906         // We have to check for holes before we start moving things around so that we don't get halfway 
907         // through shifting and then realize we should have been in ArrayStorage mode.
908         for (unsigned i = oldLength; i-- > startIndex;) {
909             JSValue v = m_butterfly->contiguous()[i].get();
910             if (UNLIKELY(!v))
911                 return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
912         }
913
914         for (unsigned i = oldLength; i-- > startIndex;) {
915             JSValue v = m_butterfly->contiguous()[i].get();
916             ASSERT(v);
917             m_butterfly->contiguous()[i + count].setWithoutWriteBarrier(v);
918         }
919         
920         // NOTE: we're leaving being garbage in the part of the array that we shifted out
921         // of. This is fine because the caller is required to store over that area, and
922         // in contiguous mode storing into a hole is guaranteed to behave exactly the same
923         // as storing over an existing element.
924         
925         return true;
926     }
927         
928     case ArrayWithDouble: {
929         unsigned oldLength = m_butterfly->publicLength();
930         
931         // We may have to walk the entire array to do the unshift. We're willing to do so
932         // only if it's not horribly slow.
933         if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
934             return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
935         
936         ensureLength(exec->vm(), oldLength + count);
937         
938         // We have to check for holes before we start moving things around so that we don't get halfway 
939         // through shifting and then realize we should have been in ArrayStorage mode.
940         for (unsigned i = oldLength; i-- > startIndex;) {
941             double v = m_butterfly->contiguousDouble()[i];
942             if (UNLIKELY(v != v))
943                 return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
944         }
945
946         for (unsigned i = oldLength; i-- > startIndex;) {
947             double v = m_butterfly->contiguousDouble()[i];
948             ASSERT(v == v);
949             m_butterfly->contiguousDouble()[i + count] = v;
950         }
951         
952         // NOTE: we're leaving being garbage in the part of the array that we shifted out
953         // of. This is fine because the caller is required to store over that area, and
954         // in contiguous mode storing into a hole is guaranteed to behave exactly the same
955         // as storing over an existing element.
956         
957         return true;
958     }
959         
960     case ArrayWithArrayStorage:
961     case ArrayWithSlowPutArrayStorage:
962         return unshiftCountWithArrayStorage(exec, startIndex, count, arrayStorage());
963         
964     default:
965         CRASH();
966         return false;
967     }
968 }
969
970 static int compareNumbersForQSortWithInt32(const void* a, const void* b)
971 {
972     int32_t ia = static_cast<const JSValue*>(a)->asInt32();
973     int32_t ib = static_cast<const JSValue*>(b)->asInt32();
974     return ia - ib;
975 }
976
977 static int compareNumbersForQSortWithDouble(const void* a, const void* b)
978 {
979     double da = *static_cast<const double*>(a);
980     double db = *static_cast<const double*>(b);
981     return (da > db) - (da < db);
982 }
983
984 static int compareNumbersForQSort(const void* a, const void* b)
985 {
986     double da = static_cast<const JSValue*>(a)->asNumber();
987     double db = static_cast<const JSValue*>(b)->asNumber();
988     return (da > db) - (da < db);
989 }
990
991 static int compareByStringPairForQSort(const void* a, const void* b)
992 {
993     const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
994     const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
995     return codePointCompare(va->second, vb->second);
996 }
997
998 template<IndexingType indexingType>
999 void JSArray::sortNumericVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
1000 {
1001     ASSERT(indexingType == ArrayWithInt32 || indexingType == ArrayWithDouble || indexingType == ArrayWithContiguous || indexingType == ArrayWithArrayStorage);
1002     
1003     unsigned lengthNotIncludingUndefined;
1004     unsigned newRelevantLength;
1005     compactForSorting<indexingType>(
1006         lengthNotIncludingUndefined,
1007         newRelevantLength);
1008     
1009     ContiguousJSValues data = indexingData<indexingType>();
1010     
1011     if (indexingType == ArrayWithArrayStorage && arrayStorage()->m_sparseMap.get()) {
1012         throwOutOfMemoryError(exec);
1013         return;
1014     }
1015     
1016     if (!lengthNotIncludingUndefined)
1017         return;
1018     
1019     bool allValuesAreNumbers = true;
1020     switch (indexingType) {
1021     case ArrayWithInt32:
1022     case ArrayWithDouble:
1023         break;
1024         
1025     default:
1026         for (size_t i = 0; i < newRelevantLength; ++i) {
1027             if (!data[i].isNumber()) {
1028                 allValuesAreNumbers = false;
1029                 break;
1030             }
1031         }
1032         break;
1033     }
1034     
1035     if (!allValuesAreNumbers)
1036         return sort(exec, compareFunction, callType, callData);
1037     
1038     // For numeric comparison, which is fast, qsort is faster than mergesort. We
1039     // also don't require mergesort's stability, since there's no user visible
1040     // side-effect from swapping the order of equal primitive values.
1041     int (*compare)(const void*, const void*);
1042     switch (indexingType) {
1043     case ArrayWithInt32:
1044         compare = compareNumbersForQSortWithInt32;
1045         break;
1046         
1047     case ArrayWithDouble:
1048         compare = compareNumbersForQSortWithDouble;
1049         ASSERT(sizeof(WriteBarrier<Unknown>) == sizeof(double));
1050         break;
1051         
1052     default:
1053         compare = compareNumbersForQSort;
1054         break;
1055     }
1056     ASSERT(data.length() >= newRelevantLength);
1057     qsort(data.data(), newRelevantLength, sizeof(WriteBarrier<Unknown>), compare);
1058     return;
1059 }
1060
1061 void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
1062 {
1063     ASSERT(!inSparseIndexingMode());
1064
1065     switch (structure()->indexingType()) {
1066     case ArrayClass:
1067         return;
1068         
1069     case ArrayWithInt32:
1070         sortNumericVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
1071         break;
1072         
1073     case ArrayWithDouble:
1074         sortNumericVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
1075         break;
1076         
1077     case ArrayWithContiguous:
1078         sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
1079         return;
1080
1081     case ArrayWithArrayStorage:
1082         sortNumericVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
1083         return;
1084         
1085     default:
1086         CRASH();
1087         return;
1088     }
1089 }
1090
1091 template <IndexingType> struct ContiguousTypeAccessor {
1092     typedef WriteBarrier<Unknown> Type;
1093     static JSValue getAsValue(ContiguousData<Type> data, size_t i) { return data[i].get(); }
1094     static void setWithValue(VM& vm, JSArray* thisValue, ContiguousData<Type> data, size_t i, JSValue value)
1095     {
1096         data[i].set(vm, thisValue, value);
1097     }
1098     static void replaceDataReference(ContiguousData<Type>* outData, ContiguousJSValues inData)
1099     {
1100         *outData = inData;
1101     }
1102 };
1103
1104 template <> struct ContiguousTypeAccessor<ArrayWithDouble> {
1105     typedef double Type;
1106     static JSValue getAsValue(ContiguousData<Type> data, size_t i) { ASSERT(data[i] == data[i]); return JSValue(JSValue::EncodeAsDouble, data[i]); }
1107     static void setWithValue(VM&, JSArray*, ContiguousData<Type> data, size_t i, JSValue value)
1108     {
1109         data[i] = value.asNumber();
1110     }
1111     static NO_RETURN_DUE_TO_CRASH void replaceDataReference(ContiguousData<Type>*, ContiguousJSValues)
1112     {
1113         RELEASE_ASSERT_WITH_MESSAGE(0, "Inconsistent indexing types during compact array sort.");
1114     }
1115 };
1116
1117
1118 template<IndexingType indexingType, typename StorageType>
1119 void JSArray::sortCompactedVector(ExecState* exec, ContiguousData<StorageType> data, unsigned relevantLength)
1120 {
1121     if (!relevantLength)
1122         return;
1123     
1124     VM& vm = exec->vm();
1125
1126     // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
1127     // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
1128     // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
1129     // random or otherwise changing results, effectively making compare function inconsistent.
1130         
1131     Vector<ValueStringPair, 0, UnsafeVectorOverflow> values(relevantLength);
1132     if (!values.begin()) {
1133         throwOutOfMemoryError(exec);
1134         return;
1135     }
1136         
1137     Heap::heap(this)->pushTempSortVector(&values);
1138         
1139     bool isSortingPrimitiveValues = true;
1140
1141     for (size_t i = 0; i < relevantLength; i++) {
1142         JSValue value = ContiguousTypeAccessor<indexingType>::getAsValue(data, i);
1143         ASSERT(indexingType != ArrayWithInt32 || value.isInt32());
1144         ASSERT(!value.isUndefined());
1145         values[i].first = value;
1146         if (indexingType != ArrayWithDouble && indexingType != ArrayWithInt32)
1147             isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();
1148     }
1149         
1150     // FIXME: The following loop continues to call toString on subsequent values even after
1151     // a toString call raises an exception.
1152         
1153     for (size_t i = 0; i < relevantLength; i++)
1154         values[i].second = values[i].first.toWTFStringInline(exec);
1155         
1156     if (exec->hadException()) {
1157         Heap::heap(this)->popTempSortVector(&values);
1158         return;
1159     }
1160         
1161     // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
1162     // than O(N log N).
1163         
1164 #if HAVE(MERGESORT)
1165     if (isSortingPrimitiveValues)
1166         qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
1167     else
1168         mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
1169 #else
1170     // FIXME: The qsort library function is likely to not be a stable sort.
1171     // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
1172     qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
1173 #endif
1174     
1175     // If the toString function changed the length of the array or vector storage,
1176     // increase the length to handle the orignal number of actual values.
1177     switch (indexingType) {
1178     case ArrayWithInt32:
1179     case ArrayWithDouble:
1180     case ArrayWithContiguous:
1181         ensureLength(vm, relevantLength);
1182         break;
1183         
1184     case ArrayWithArrayStorage:
1185         if (arrayStorage()->vectorLength() < relevantLength) {
1186             increaseVectorLength(exec->vm(), relevantLength);
1187             ContiguousTypeAccessor<indexingType>::replaceDataReference(&data, arrayStorage()->vector());
1188         }
1189         if (arrayStorage()->length() < relevantLength)
1190             arrayStorage()->setLength(relevantLength);
1191         break;
1192         
1193     default:
1194         CRASH();
1195     }
1196
1197     for (size_t i = 0; i < relevantLength; i++)
1198         ContiguousTypeAccessor<indexingType>::setWithValue(vm, this, data, i, values[i].first);
1199     
1200     Heap::heap(this)->popTempSortVector(&values);
1201 }
1202
1203 void JSArray::sort(ExecState* exec)
1204 {
1205     ASSERT(!inSparseIndexingMode());
1206     
1207     switch (structure()->indexingType()) {
1208     case ArrayClass:
1209     case ArrayWithUndecided:
1210         return;
1211         
1212     case ArrayWithInt32: {
1213         unsigned lengthNotIncludingUndefined;
1214         unsigned newRelevantLength;
1215         compactForSorting<ArrayWithInt32>(
1216             lengthNotIncludingUndefined, newRelevantLength);
1217         
1218         sortCompactedVector<ArrayWithInt32>(
1219             exec, m_butterfly->contiguousInt32(), lengthNotIncludingUndefined);
1220         return;
1221     }
1222         
1223     case ArrayWithDouble: {
1224         unsigned lengthNotIncludingUndefined;
1225         unsigned newRelevantLength;
1226         compactForSorting<ArrayWithDouble>(
1227             lengthNotIncludingUndefined, newRelevantLength);
1228         
1229         sortCompactedVector<ArrayWithDouble>(
1230             exec, m_butterfly->contiguousDouble(), lengthNotIncludingUndefined);
1231         return;
1232     }
1233         
1234     case ArrayWithContiguous: {
1235         unsigned lengthNotIncludingUndefined;
1236         unsigned newRelevantLength;
1237         compactForSorting<ArrayWithContiguous>(
1238             lengthNotIncludingUndefined, newRelevantLength);
1239         
1240         sortCompactedVector<ArrayWithContiguous>(
1241             exec, m_butterfly->contiguous(), lengthNotIncludingUndefined);
1242         return;
1243     }
1244         
1245     case ArrayWithArrayStorage: {
1246         unsigned lengthNotIncludingUndefined;
1247         unsigned newRelevantLength;
1248         compactForSorting<ArrayWithArrayStorage>(
1249             lengthNotIncludingUndefined, newRelevantLength);
1250         ArrayStorage* storage = m_butterfly->arrayStorage();
1251         ASSERT(!storage->m_sparseMap);
1252         
1253         sortCompactedVector<ArrayWithArrayStorage>(exec, storage->vector(), lengthNotIncludingUndefined);
1254         return;
1255     }
1256         
1257     default:
1258         RELEASE_ASSERT_NOT_REACHED();
1259     }
1260 }
1261
1262 struct AVLTreeNodeForArrayCompare {
1263     JSValue value;
1264
1265     // Child pointers.  The high bit of gt is robbed and used as the
1266     // balance factor sign.  The high bit of lt is robbed and used as
1267     // the magnitude of the balance factor.
1268     int32_t gt;
1269     int32_t lt;
1270 };
1271
1272 struct AVLTreeAbstractorForArrayCompare {
1273     typedef int32_t handle; // Handle is an index into m_nodes vector.
1274     typedef JSValue key;
1275     typedef int32_t size;
1276
1277     Vector<AVLTreeNodeForArrayCompare, 0, UnsafeVectorOverflow> m_nodes;
1278     ExecState* m_exec;
1279     JSValue m_compareFunction;
1280     CallType m_compareCallType;
1281     const CallData* m_compareCallData;
1282     OwnPtr<CachedCall> m_cachedCall;
1283
1284     handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
1285     void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; }
1286     handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; }
1287     void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; }
1288
1289     int get_balance_factor(handle h)
1290     {
1291         if (m_nodes[h].gt & 0x80000000)
1292             return -1;
1293         return static_cast<unsigned>(m_nodes[h].lt) >> 31;
1294     }
1295
1296     void set_balance_factor(handle h, int bf)
1297     {
1298         if (bf == 0) {
1299             m_nodes[h].lt &= 0x7FFFFFFF;
1300             m_nodes[h].gt &= 0x7FFFFFFF;
1301         } else {
1302             m_nodes[h].lt |= 0x80000000;
1303             if (bf < 0)
1304                 m_nodes[h].gt |= 0x80000000;
1305             else
1306                 m_nodes[h].gt &= 0x7FFFFFFF;
1307         }
1308     }
1309
1310     int compare_key_key(key va, key vb)
1311     {
1312         ASSERT(!va.isUndefined());
1313         ASSERT(!vb.isUndefined());
1314
1315         if (m_exec->hadException())
1316             return 1;
1317
1318         double compareResult;
1319         if (m_cachedCall) {
1320             m_cachedCall->setThis(jsUndefined());
1321             m_cachedCall->setArgument(0, va);
1322             m_cachedCall->setArgument(1, vb);
1323 #if ENABLE(LLINT_C_LOOP)
1324             compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec));
1325 #else
1326             compareResult = m_cachedCall->call().toNumber(m_exec);
1327 #endif
1328         } else {
1329             MarkedArgumentBuffer arguments;
1330             arguments.append(va);
1331             arguments.append(vb);
1332             compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, jsUndefined(), arguments).toNumber(m_exec);
1333         }
1334         return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
1335     }
1336
1337     int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
1338     int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }
1339
1340     static handle null() { return 0x7FFFFFFF; }
1341 };
1342
1343 template<IndexingType indexingType>
1344 void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
1345 {
1346     ASSERT(!inSparseIndexingMode());
1347     ASSERT(indexingType == structure()->indexingType());
1348     
1349     // FIXME: This ignores exceptions raised in the compare function or in toNumber.
1350         
1351     // The maximum tree depth is compiled in - but the caller is clearly up to no good
1352     // if a larger array is passed.
1353     ASSERT(m_butterfly->publicLength() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
1354     if (m_butterfly->publicLength() > static_cast<unsigned>(std::numeric_limits<int>::max()))
1355         return;
1356         
1357     unsigned usedVectorLength = relevantLength<indexingType>();
1358     unsigned nodeCount = usedVectorLength;
1359         
1360     if (!nodeCount)
1361         return;
1362         
1363     AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
1364     tree.abstractor().m_exec = exec;
1365     tree.abstractor().m_compareFunction = compareFunction;
1366     tree.abstractor().m_compareCallType = callType;
1367     tree.abstractor().m_compareCallData = &callData;
1368     tree.abstractor().m_nodes.grow(nodeCount);
1369         
1370     if (callType == CallTypeJS)
1371         tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, jsCast<JSFunction*>(compareFunction), 2));
1372         
1373     if (!tree.abstractor().m_nodes.begin()) {
1374         throwOutOfMemoryError(exec);
1375         return;
1376     }
1377         
1378     // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
1379     // right out from under us while we're building the tree here.
1380         
1381     unsigned numDefined = 0;
1382     unsigned numUndefined = 0;
1383     
1384     // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
1385     for (; numDefined < usedVectorLength; ++numDefined) {
1386         if (numDefined >= m_butterfly->vectorLength())
1387             break;
1388         JSValue v = getHolyIndexQuickly(numDefined);
1389         if (!v || v.isUndefined())
1390             break;
1391         tree.abstractor().m_nodes[numDefined].value = v;
1392         tree.insert(numDefined);
1393     }
1394     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
1395         if (i >= m_butterfly->vectorLength())
1396             break;
1397         JSValue v = getHolyIndexQuickly(i);
1398         if (v) {
1399             if (v.isUndefined())
1400                 ++numUndefined;
1401             else {
1402                 tree.abstractor().m_nodes[numDefined].value = v;
1403                 tree.insert(numDefined);
1404                 ++numDefined;
1405             }
1406         }
1407     }
1408     
1409     unsigned newUsedVectorLength = numDefined + numUndefined;
1410         
1411     // The array size may have changed. Figure out the new bounds.
1412     unsigned newestUsedVectorLength = currentRelevantLength();
1413         
1414     unsigned elementsToExtractThreshold = min(min(newestUsedVectorLength, numDefined), static_cast<unsigned>(tree.abstractor().m_nodes.size()));
1415     unsigned undefinedElementsThreshold = min(newestUsedVectorLength, newUsedVectorLength);
1416     unsigned clearElementsThreshold = min(newestUsedVectorLength, usedVectorLength);
1417         
1418     // Copy the values back into m_storage.
1419     AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
1420     iter.start_iter_least(tree);
1421     VM& vm = exec->vm();
1422     for (unsigned i = 0; i < elementsToExtractThreshold; ++i) {
1423         ASSERT(i < butterfly()->vectorLength());
1424         if (structure()->indexingType() == ArrayWithDouble)
1425             butterfly()->contiguousDouble()[i] = tree.abstractor().m_nodes[*iter].value.asNumber();
1426         else
1427             currentIndexingData()[i].set(vm, this, tree.abstractor().m_nodes[*iter].value);
1428         ++iter;
1429     }
1430     // Put undefined values back in.
1431     switch (structure()->indexingType()) {
1432     case ArrayWithInt32:
1433     case ArrayWithDouble:
1434         ASSERT(elementsToExtractThreshold == undefinedElementsThreshold);
1435         break;
1436         
1437     default:
1438         for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i) {
1439             ASSERT(i < butterfly()->vectorLength());
1440             currentIndexingData()[i].setUndefined();
1441         }
1442     }
1443
1444     // Ensure that unused values in the vector are zeroed out.
1445     for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i) {
1446         ASSERT(i < butterfly()->vectorLength());
1447         if (structure()->indexingType() == ArrayWithDouble)
1448             butterfly()->contiguousDouble()[i] = QNaN;
1449         else
1450             currentIndexingData()[i].clear();
1451     }
1452     
1453     if (hasArrayStorage(structure()->indexingType()))
1454         arrayStorage()->m_numValuesInVector = newUsedVectorLength;
1455 }
1456
1457 void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
1458 {
1459     ASSERT(!inSparseIndexingMode());
1460     
1461     switch (structure()->indexingType()) {
1462     case ArrayClass:
1463     case ArrayWithUndecided:
1464         return;
1465         
1466     case ArrayWithInt32:
1467         sortVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
1468         return;
1469
1470     case ArrayWithDouble:
1471         sortVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
1472         return;
1473
1474     case ArrayWithContiguous:
1475         sortVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
1476         return;
1477
1478     case ArrayWithArrayStorage:
1479         sortVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
1480         return;
1481         
1482     default:
1483         RELEASE_ASSERT_NOT_REACHED();
1484     }
1485 }
1486
1487 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
1488 {
1489     unsigned i = 0;
1490     unsigned vectorEnd;
1491     WriteBarrier<Unknown>* vector;
1492     
1493     switch (structure()->indexingType()) {
1494     case ArrayClass:
1495         return;
1496         
1497     case ArrayWithUndecided: {
1498         vector = 0;
1499         vectorEnd = 0;
1500         break;
1501     }
1502         
1503     case ArrayWithInt32:
1504     case ArrayWithContiguous: {
1505         vectorEnd = m_butterfly->publicLength();
1506         vector = m_butterfly->contiguous().data();
1507         break;
1508     }
1509         
1510     case ArrayWithDouble: {
1511         vector = 0;
1512         vectorEnd = 0;
1513         for (; i < m_butterfly->publicLength(); ++i) {
1514             double v = butterfly()->contiguousDouble()[i];
1515             if (v != v)
1516                 break;
1517             args.append(JSValue(JSValue::EncodeAsDouble, v));
1518         }
1519         break;
1520     }
1521     
1522     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
1523         ArrayStorage* storage = m_butterfly->arrayStorage();
1524         
1525         vector = storage->m_vector;
1526         vectorEnd = min(storage->length(), storage->vectorLength());
1527         break;
1528     }
1529         
1530     default:
1531         CRASH();
1532         vector = 0;
1533         vectorEnd = 0;
1534         break;
1535     }
1536     
1537     for (; i < vectorEnd; ++i) {
1538         WriteBarrier<Unknown>& v = vector[i];
1539         if (!v)
1540             break;
1541         args.append(v.get());
1542     }
1543     
1544     for (; i < length(); ++i)
1545         args.append(get(exec, i));
1546 }
1547
1548 void JSArray::copyToArguments(ExecState* exec, CallFrame* callFrame, uint32_t length)
1549 {
1550     unsigned i = 0;
1551     WriteBarrier<Unknown>* vector;
1552     unsigned vectorEnd;
1553     
1554     ASSERT(length == this->length());
1555     switch (structure()->indexingType()) {
1556     case ArrayClass:
1557         return;
1558         
1559     case ArrayWithUndecided: {
1560         vector = 0;
1561         vectorEnd = 0;
1562         break;
1563     }
1564         
1565     case ArrayWithInt32:
1566     case ArrayWithContiguous: {
1567         vector = m_butterfly->contiguous().data();
1568         vectorEnd = m_butterfly->publicLength();
1569         break;
1570     }
1571         
1572     case ArrayWithDouble: {
1573         vector = 0;
1574         vectorEnd = 0;
1575         for (; i < m_butterfly->publicLength(); ++i) {
1576             ASSERT(i < butterfly()->vectorLength());
1577             double v = m_butterfly->contiguousDouble()[i];
1578             if (v != v)
1579                 break;
1580             callFrame->setArgument(i, JSValue(JSValue::EncodeAsDouble, v));
1581         }
1582         break;
1583     }
1584         
1585     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
1586         ArrayStorage* storage = m_butterfly->arrayStorage();
1587         vector = storage->m_vector;
1588         vectorEnd = min(length, storage->vectorLength());
1589         break;
1590     }
1591         
1592     default:
1593         CRASH();
1594         vector = 0;
1595         vectorEnd = 0;
1596         break;
1597     }
1598     
1599     for (; i < vectorEnd; ++i) {
1600         WriteBarrier<Unknown>& v = vector[i];
1601         if (!v)
1602             break;
1603         callFrame->setArgument(i, v.get());
1604     }
1605     
1606     for (; i < length; ++i)
1607         callFrame->setArgument(i, get(exec, i));
1608 }
1609
1610 template<IndexingType indexingType>
1611 void JSArray::compactForSorting(unsigned& numDefined, unsigned& newRelevantLength)
1612 {
1613     ASSERT(!inSparseIndexingMode());
1614     ASSERT(indexingType == structure()->indexingType());
1615
1616     unsigned myRelevantLength = relevantLength<indexingType>();
1617     
1618     numDefined = 0;
1619     unsigned numUndefined = 0;
1620         
1621     for (; numDefined < myRelevantLength; ++numDefined) {
1622         ASSERT(numDefined < m_butterfly->vectorLength());
1623         if (indexingType == ArrayWithInt32) {
1624             JSValue v = m_butterfly->contiguousInt32()[numDefined].get();
1625             if (!v)
1626                 break;
1627             ASSERT(v.isInt32());
1628             continue;
1629         }
1630         if (indexingType == ArrayWithDouble) {
1631             double v = m_butterfly->contiguousDouble()[numDefined];
1632             if (v != v)
1633                 break;
1634             continue;
1635         }
1636         JSValue v = indexingData<indexingType>()[numDefined].get();
1637         if (!v || v.isUndefined())
1638             break;
1639     }
1640         
1641     for (unsigned i = numDefined; i < myRelevantLength; ++i) {
1642         ASSERT(i < m_butterfly->vectorLength());
1643         if (indexingType == ArrayWithInt32) {
1644             JSValue v = m_butterfly->contiguousInt32()[i].get();
1645             if (!v)
1646                 continue;
1647             ASSERT(v.isInt32());
1648             ASSERT(numDefined < m_butterfly->vectorLength());
1649             m_butterfly->contiguousInt32()[numDefined++].setWithoutWriteBarrier(v);
1650             continue;
1651         }
1652         if (indexingType == ArrayWithDouble) {
1653             double v = m_butterfly->contiguousDouble()[i];
1654             if (v != v)
1655                 continue;
1656             ASSERT(numDefined < m_butterfly->vectorLength());
1657             m_butterfly->contiguousDouble()[numDefined++] = v;
1658             continue;
1659         }
1660         JSValue v = indexingData<indexingType>()[i].get();
1661         if (v) {
1662             if (v.isUndefined())
1663                 ++numUndefined;
1664             else {
1665                 ASSERT(numDefined < m_butterfly->vectorLength());
1666                 indexingData<indexingType>()[numDefined++].setWithoutWriteBarrier(v);
1667             }
1668         }
1669     }
1670         
1671     newRelevantLength = numDefined + numUndefined;
1672     
1673     if (hasArrayStorage(indexingType))
1674         RELEASE_ASSERT(!arrayStorage()->m_sparseMap);
1675     
1676     switch (indexingType) {
1677     case ArrayWithInt32:
1678     case ArrayWithDouble:
1679         RELEASE_ASSERT(numDefined == newRelevantLength);
1680         break;
1681         
1682     default:
1683         for (unsigned i = numDefined; i < newRelevantLength; ++i) {
1684             ASSERT(i < m_butterfly->vectorLength());
1685             indexingData<indexingType>()[i].setUndefined();
1686         }
1687         break;
1688     }
1689     for (unsigned i = newRelevantLength; i < myRelevantLength; ++i) {
1690         ASSERT(i < m_butterfly->vectorLength());
1691         if (indexingType == ArrayWithDouble)
1692             m_butterfly->contiguousDouble()[i] = QNaN;
1693         else
1694             indexingData<indexingType>()[i].clear();
1695     }
1696
1697     if (hasArrayStorage(indexingType))
1698         arrayStorage()->m_numValuesInVector = newRelevantLength;
1699 }
1700
1701 } // namespace JSC