Storing new CopiedSpace memory into a JSObject should fire a write barrier
[WebKit-https.git] / Source / JavaScriptCore / runtime / JSArray.cpp
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2003, 2007, 2008, 2009, 2012, 2013 Apple Inc. All rights reserved.
4  *  Copyright (C) 2003 Peter Kelly (pmk@post.com)
5  *  Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
6  *
7  *  This library is free software; you can redistribute it and/or
8  *  modify it under the terms of the GNU Lesser General Public
9  *  License as published by the Free Software Foundation; either
10  *  version 2 of the License, or (at your option) any later version.
11  *
12  *  This library is distributed in the hope that it will be useful,
13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  *  Lesser General Public License for more details.
16  *
17  *  You should have received a copy of the GNU Lesser General Public
18  *  License along with this library; if not, write to the Free Software
19  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
20  *
21  */
22
23 #include "config.h"
24 #include "JSArray.h"
25
26 #include "ArrayPrototype.h"
27 #include "ButterflyInlines.h"
28 #include "CachedCall.h"
29 #include "CopiedSpace.h"
30 #include "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     setButterflyWithoutChangingStructure(vm, newButterfly);
325
326     return true;
327 }
328
329 bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, bool throwException, ArrayStorage* storage)
330 {
331     unsigned length = storage->length();
332
333     // If the length is read only then we enter sparse mode, so should enter the following 'if'.
334     ASSERT(isLengthWritable() || storage->m_sparseMap);
335
336     if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
337         // Fail if the length is not writable.
338         if (map->lengthIsReadOnly())
339             return reject(exec, throwException, StrictModeReadonlyPropertyWriteError);
340
341         if (newLength < length) {
342             // Copy any keys we might be interested in into a vector.
343             Vector<unsigned, 0, UnsafeVectorOverflow> keys;
344             keys.reserveInitialCapacity(min(map->size(), static_cast<size_t>(length - newLength)));
345             SparseArrayValueMap::const_iterator end = map->end();
346             for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
347                 unsigned index = static_cast<unsigned>(it->key);
348                 if (index < length && index >= newLength)
349                     keys.append(index);
350             }
351
352             // Check if the array is in sparse mode. If so there may be non-configurable
353             // properties, so we have to perform deletion with caution, if not we can
354             // delete values in any order.
355             if (map->sparseMode()) {
356                 qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
357                 unsigned i = keys.size();
358                 while (i) {
359                     unsigned index = keys[--i];
360                     SparseArrayValueMap::iterator it = map->find(index);
361                     ASSERT(it != map->notFound());
362                     if (it->value.attributes & DontDelete) {
363                         storage->setLength(index + 1);
364                         return reject(exec, throwException, "Unable to delete property.");
365                     }
366                     map->remove(it);
367                 }
368             } else {
369                 for (unsigned i = 0; i < keys.size(); ++i)
370                     map->remove(keys[i]);
371                 if (map->isEmpty())
372                     deallocateSparseIndexMap();
373             }
374         }
375     }
376
377     if (newLength < length) {
378         // Delete properties from the vector.
379         unsigned usedVectorLength = min(length, storage->vectorLength());
380         for (unsigned i = newLength; i < usedVectorLength; ++i) {
381             WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
382             bool hadValue = valueSlot;
383             valueSlot.clear();
384             storage->m_numValuesInVector -= hadValue;
385         }
386     }
387
388     storage->setLength(newLength);
389
390     return true;
391 }
392
393 bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
394 {
395     switch (structure()->indexingType()) {
396     case ArrayClass:
397         if (!newLength)
398             return true;
399         if (newLength >= MIN_SPARSE_ARRAY_INDEX) {
400             return setLengthWithArrayStorage(
401                 exec, newLength, throwException,
402                 convertContiguousToArrayStorage(exec->vm()));
403         }
404         createInitialUndecided(exec->vm(), newLength);
405         return true;
406         
407     case ArrayWithUndecided:
408     case ArrayWithInt32:
409     case ArrayWithDouble:
410     case ArrayWithContiguous:
411         if (newLength == m_butterfly->publicLength())
412             return true;
413         if (newLength >= MAX_ARRAY_INDEX // This case ensures that we can do fast push.
414             || (newLength >= MIN_SPARSE_ARRAY_INDEX
415                 && !isDenseEnoughForVector(newLength, countElements()))) {
416             return setLengthWithArrayStorage(
417                 exec, newLength, throwException,
418                 ensureArrayStorage(exec->vm()));
419         }
420         if (newLength > m_butterfly->publicLength()) {
421             ensureLength(exec->vm(), newLength);
422             return true;
423         }
424         if (structure()->indexingType() == ArrayWithDouble) {
425             for (unsigned i = m_butterfly->publicLength(); i-- > newLength;)
426                 m_butterfly->contiguousDouble()[i] = QNaN;
427         } else {
428             for (unsigned i = m_butterfly->publicLength(); i-- > newLength;)
429                 m_butterfly->contiguous()[i].clear();
430         }
431         m_butterfly->setPublicLength(newLength);
432         return true;
433         
434     case ArrayWithArrayStorage:
435     case ArrayWithSlowPutArrayStorage:
436         return setLengthWithArrayStorage(exec, newLength, throwException, arrayStorage());
437         
438     default:
439         CRASH();
440         return false;
441     }
442 }
443
444 JSValue JSArray::pop(ExecState* exec)
445 {
446     switch (structure()->indexingType()) {
447     case ArrayClass:
448         return jsUndefined();
449         
450     case ArrayWithUndecided:
451         if (!m_butterfly->publicLength())
452             return jsUndefined();
453         // We have nothing but holes. So, drop down to the slow version.
454         break;
455         
456     case ArrayWithInt32:
457     case ArrayWithContiguous: {
458         unsigned length = m_butterfly->publicLength();
459         
460         if (!length--)
461             return jsUndefined();
462         
463         RELEASE_ASSERT(length < m_butterfly->vectorLength());
464         JSValue value = m_butterfly->contiguous()[length].get();
465         if (value) {
466             m_butterfly->contiguous()[length].clear();
467             m_butterfly->setPublicLength(length);
468             return value;
469         }
470         break;
471     }
472         
473     case ArrayWithDouble: {
474         unsigned length = m_butterfly->publicLength();
475         
476         if (!length--)
477             return jsUndefined();
478         
479         RELEASE_ASSERT(length < m_butterfly->vectorLength());
480         double value = m_butterfly->contiguousDouble()[length];
481         if (value == value) {
482             m_butterfly->contiguousDouble()[length] = QNaN;
483             m_butterfly->setPublicLength(length);
484             return JSValue(JSValue::EncodeAsDouble, value);
485         }
486         break;
487     }
488         
489     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
490         ArrayStorage* storage = m_butterfly->arrayStorage();
491     
492         unsigned length = storage->length();
493         if (!length) {
494             if (!isLengthWritable())
495                 throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
496             return jsUndefined();
497         }
498
499         unsigned index = length - 1;
500         if (index < storage->vectorLength()) {
501             WriteBarrier<Unknown>& valueSlot = storage->m_vector[index];
502             if (valueSlot) {
503                 --storage->m_numValuesInVector;
504                 JSValue element = valueSlot.get();
505                 valueSlot.clear();
506             
507                 RELEASE_ASSERT(isLengthWritable());
508                 storage->setLength(index);
509                 return element;
510             }
511         }
512         break;
513     }
514         
515     default:
516         CRASH();
517         return JSValue();
518     }
519     
520     unsigned index = getArrayLength() - 1;
521     // Let element be the result of calling the [[Get]] internal method of O with argument indx.
522     JSValue element = get(exec, index);
523     if (exec->hadException())
524         return jsUndefined();
525     // Call the [[Delete]] internal method of O with arguments indx and true.
526     if (!deletePropertyByIndex(this, exec, index)) {
527         throwTypeError(exec, "Unable to delete property.");
528         return jsUndefined();
529     }
530     // Call the [[Put]] internal method of O with arguments "length", indx, and true.
531     setLength(exec, index, true);
532     // Return element.
533     return element;
534 }
535
536 // Push & putIndex are almost identical, with two small differences.
537 //  - we always are writing beyond the current array bounds, so it is always necessary to update m_length & m_numValuesInVector.
538 //  - pushing to an array of length 2^32-1 stores the property, but throws a range error.
539 void JSArray::push(ExecState* exec, JSValue value)
540 {
541     switch (structure()->indexingType()) {
542     case ArrayClass: {
543         createInitialUndecided(exec->vm(), 0);
544         // Fall through.
545     }
546         
547     case ArrayWithUndecided: {
548         convertUndecidedForValue(exec->vm(), value);
549         push(exec, value);
550         return;
551     }
552         
553     case ArrayWithInt32: {
554         if (!value.isInt32()) {
555             convertInt32ForValue(exec->vm(), value);
556             push(exec, value);
557             return;
558         }
559
560         unsigned length = m_butterfly->publicLength();
561         ASSERT(length <= m_butterfly->vectorLength());
562         if (length < m_butterfly->vectorLength()) {
563             m_butterfly->contiguousInt32()[length].setWithoutWriteBarrier(value);
564             m_butterfly->setPublicLength(length + 1);
565             return;
566         }
567         
568         if (length > MAX_ARRAY_INDEX) {
569             methodTable()->putByIndex(this, exec, length, value, true);
570             if (!exec->hadException())
571                 exec->vm().throwException(exec, createRangeError(exec, "Invalid array length"));
572             return;
573         }
574         
575         putByIndexBeyondVectorLengthWithoutAttributes<Int32Shape>(exec, length, value);
576         return;
577     }
578
579     case ArrayWithContiguous: {
580         unsigned length = m_butterfly->publicLength();
581         ASSERT(length <= m_butterfly->vectorLength());
582         if (length < m_butterfly->vectorLength()) {
583             m_butterfly->contiguous()[length].set(exec->vm(), this, value);
584             m_butterfly->setPublicLength(length + 1);
585             return;
586         }
587         
588         if (length > MAX_ARRAY_INDEX) {
589             methodTable()->putByIndex(this, exec, length, value, true);
590             if (!exec->hadException())
591                 exec->vm().throwException(exec, createRangeError(exec, "Invalid array length"));
592             return;
593         }
594         
595         putByIndexBeyondVectorLengthWithoutAttributes<ContiguousShape>(exec, length, value);
596         return;
597     }
598         
599     case ArrayWithDouble: {
600         if (!value.isNumber()) {
601             convertDoubleToContiguous(exec->vm());
602             push(exec, value);
603             return;
604         }
605         double valueAsDouble = value.asNumber();
606         if (valueAsDouble != valueAsDouble) {
607             convertDoubleToContiguous(exec->vm());
608             push(exec, value);
609             return;
610         }
611
612         unsigned length = m_butterfly->publicLength();
613         ASSERT(length <= m_butterfly->vectorLength());
614         if (length < m_butterfly->vectorLength()) {
615             m_butterfly->contiguousDouble()[length] = valueAsDouble;
616             m_butterfly->setPublicLength(length + 1);
617             return;
618         }
619         
620         if (length > MAX_ARRAY_INDEX) {
621             methodTable()->putByIndex(this, exec, length, value, true);
622             if (!exec->hadException())
623                 exec->vm().throwException(exec, createRangeError(exec, "Invalid array length"));
624             return;
625         }
626         
627         putByIndexBeyondVectorLengthWithoutAttributes<DoubleShape>(exec, length, value);
628         break;
629     }
630         
631     case ArrayWithSlowPutArrayStorage: {
632         unsigned oldLength = length();
633         if (attemptToInterceptPutByIndexOnHole(exec, oldLength, value, true)) {
634             if (!exec->hadException() && oldLength < 0xFFFFFFFFu)
635                 setLength(exec, oldLength + 1, true);
636             return;
637         }
638         // Fall through.
639     }
640         
641     case ArrayWithArrayStorage: {
642         ArrayStorage* storage = m_butterfly->arrayStorage();
643
644         // Fast case - push within vector, always update m_length & m_numValuesInVector.
645         unsigned length = storage->length();
646         if (length < storage->vectorLength()) {
647             storage->m_vector[length].set(exec->vm(), this, value);
648             storage->setLength(length + 1);
649             ++storage->m_numValuesInVector;
650             return;
651         }
652
653         // Pushing to an array of invalid length (2^31-1) stores the property, but throws a range error.
654         if (storage->length() > MAX_ARRAY_INDEX) {
655             methodTable()->putByIndex(this, exec, storage->length(), value, true);
656             // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d.
657             if (!exec->hadException())
658                 exec->vm().throwException(exec, createRangeError(exec, "Invalid array length"));
659             return;
660         }
661
662         // Handled the same as putIndex.
663         putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage);
664         break;
665     }
666         
667     default:
668         RELEASE_ASSERT_NOT_REACHED();
669     }
670 }
671
672 bool JSArray::shiftCountWithArrayStorage(unsigned startIndex, unsigned count, ArrayStorage* storage)
673 {
674     unsigned oldLength = storage->length();
675     RELEASE_ASSERT(count <= oldLength);
676     
677     // If the array contains holes or is otherwise in an abnormal state,
678     // use the generic algorithm in ArrayPrototype.
679     if (oldLength != storage->m_numValuesInVector || inSparseIndexingMode() || shouldUseSlowPut(structure()->indexingType()))
680         return false;
681
682     if (!oldLength)
683         return true;
684     
685     unsigned length = oldLength - count;
686     
687     storage->m_numValuesInVector -= count;
688     storage->setLength(length);
689     
690     unsigned vectorLength = storage->vectorLength();
691     if (!vectorLength)
692         return true;
693     
694     if (startIndex >= vectorLength)
695         return true;
696     
697     if (startIndex + count > vectorLength)
698         count = vectorLength - startIndex;
699     
700     unsigned usedVectorLength = min(vectorLength, oldLength);
701     
702     unsigned numElementsBeforeShiftRegion = startIndex;
703     unsigned firstIndexAfterShiftRegion = startIndex + count;
704     unsigned numElementsAfterShiftRegion = usedVectorLength - firstIndexAfterShiftRegion;
705     ASSERT(numElementsBeforeShiftRegion + count + numElementsAfterShiftRegion == usedVectorLength);
706
707     // The point of this comparison seems to be to minimize the amount of elements that have to 
708     // be moved during a shift operation.
709     if (numElementsBeforeShiftRegion < numElementsAfterShiftRegion) {
710         // The number of elements before the shift region is less than the number of elements
711         // after the shift region, so we move the elements before to the right.
712         if (numElementsBeforeShiftRegion) {
713             RELEASE_ASSERT(count + startIndex <= vectorLength);
714             memmove(
715                 storage->m_vector + count,
716                 storage->m_vector,
717                 sizeof(JSValue) * startIndex);
718         }
719         // Adjust the Butterfly and the index bias. We only need to do this here because we're changing
720         // the start of the Butterfly, which needs to point at the first indexed property in the used
721         // portion of the vector.
722         m_butterfly.setWithoutWriteBarrier(m_butterfly->shift(structure(), count));
723         storage = m_butterfly->arrayStorage();
724         storage->m_indexBias += count;
725
726         // Since we're consuming part of the vector by moving its beginning to the left,
727         // we need to modify the vector length appropriately.
728         storage->setVectorLength(vectorLength - count);
729     } else {
730         // The number of elements before the shift region is greater than or equal to the number 
731         // of elements after the shift region, so we move the elements after the shift region to the left.
732         memmove(
733             storage->m_vector + startIndex,
734             storage->m_vector + firstIndexAfterShiftRegion,
735             sizeof(JSValue) * numElementsAfterShiftRegion);
736         // Clear the slots of the elements we just moved.
737         unsigned startOfEmptyVectorTail = usedVectorLength - count;
738         for (unsigned i = startOfEmptyVectorTail; i < usedVectorLength; ++i)
739             storage->m_vector[i].clear();
740         // We don't modify the index bias or the Butterfly pointer in this case because we're not changing 
741         // the start of the Butterfly, which needs to point at the first indexed property in the used 
742         // portion of the vector. We also don't modify the vector length because we're not actually changing
743         // its length; we're just using less of it.
744     }
745     
746     return true;
747 }
748
749 bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
750 {
751     RELEASE_ASSERT(count > 0);
752     
753     switch (structure()->indexingType()) {
754     case ArrayClass:
755         return true;
756         
757     case ArrayWithUndecided:
758         // Don't handle this because it's confusing and it shouldn't come up.
759         return false;
760         
761     case ArrayWithInt32:
762     case ArrayWithContiguous: {
763         unsigned oldLength = m_butterfly->publicLength();
764         RELEASE_ASSERT(count <= oldLength);
765         
766         // We may have to walk the entire array to do the shift. We're willing to do
767         // so only if it's not horribly slow.
768         if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
769             return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm()));
770
771         // Storing to a hole is fine since we're still having a good time. But reading from a hole 
772         // is totally not fine, since we might have to read from the proto chain.
773         // We have to check for holes before we start moving things around so that we don't get halfway 
774         // through shifting and then realize we should have been in ArrayStorage mode.
775         unsigned end = oldLength - count;
776         for (unsigned i = startIndex; i < end; ++i) {
777             JSValue v = m_butterfly->contiguous()[i + count].get();
778             if (UNLIKELY(!v))
779                 return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm()));
780         }
781
782         for (unsigned i = startIndex; i < end; ++i) {
783             JSValue v = m_butterfly->contiguous()[i + count].get();
784             ASSERT(v);
785             // No need for a barrier since we're just moving data around in the same vector.
786             // This is in line with our standing assumption that we won't have a deletion
787             // barrier.
788             m_butterfly->contiguous()[i].setWithoutWriteBarrier(v);
789         }
790         for (unsigned i = end; i < oldLength; ++i)
791             m_butterfly->contiguous()[i].clear();
792         
793         m_butterfly->setPublicLength(oldLength - count);
794         return true;
795     }
796         
797     case ArrayWithDouble: {
798         unsigned oldLength = m_butterfly->publicLength();
799         RELEASE_ASSERT(count <= oldLength);
800         
801         // We may have to walk the entire array to do the shift. We're willing to do
802         // so only if it's not horribly slow.
803         if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
804             return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm()));
805
806         // Storing to a hole is fine since we're still having a good time. But reading from a hole 
807         // is totally not fine, since we might have to read from the proto chain.
808         // We have to check for holes before we start moving things around so that we don't get halfway 
809         // through shifting and then realize we should have been in ArrayStorage mode.
810         unsigned end = oldLength - count;
811         for (unsigned i = startIndex; i < end; ++i) {
812             double v = m_butterfly->contiguousDouble()[i + count];
813             if (UNLIKELY(v != v))
814                 return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm()));
815         }
816             
817         for (unsigned i = startIndex; i < end; ++i) {
818             double v = m_butterfly->contiguousDouble()[i + count];
819             ASSERT(v == v);
820             // No need for a barrier since we're just moving data around in the same vector.
821             // This is in line with our standing assumption that we won't have a deletion
822             // barrier.
823             m_butterfly->contiguousDouble()[i] = v;
824         }
825         for (unsigned i = end; i < oldLength; ++i)
826             m_butterfly->contiguousDouble()[i] = QNaN;
827         
828         m_butterfly->setPublicLength(oldLength - count);
829         return true;
830     }
831         
832     case ArrayWithArrayStorage:
833     case ArrayWithSlowPutArrayStorage:
834         return shiftCountWithArrayStorage(startIndex, count, arrayStorage());
835         
836     default:
837         CRASH();
838         return false;
839     }
840 }
841
842 // Returns true if the unshift can be handled, false to fallback.    
843 bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, unsigned count, ArrayStorage* storage)
844 {
845     unsigned length = storage->length();
846
847     RELEASE_ASSERT(startIndex <= length);
848
849     // If the array contains holes or is otherwise in an abnormal state,
850     // use the generic algorithm in ArrayPrototype.
851     if (length != storage->m_numValuesInVector || storage->inSparseMode() || shouldUseSlowPut(structure()->indexingType()))
852         return false;
853
854     bool moveFront = !startIndex || startIndex < length / 2;
855
856     unsigned vectorLength = storage->vectorLength();
857
858     if (moveFront && storage->m_indexBias >= count) {
859         Butterfly* newButterfly = storage->butterfly()->unshift(structure(), count);
860         storage = newButterfly->arrayStorage();
861         storage->m_indexBias -= count;
862         storage->setVectorLength(vectorLength + count);
863         setButterflyWithoutChangingStructure(exec->vm(), newButterfly);
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             compareResult = m_cachedCall->call().toNumber(m_exec);
1324         } else {
1325             MarkedArgumentBuffer arguments;
1326             arguments.append(va);
1327             arguments.append(vb);
1328             compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, jsUndefined(), arguments).toNumber(m_exec);
1329         }
1330         return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
1331     }
1332
1333     int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
1334     int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }
1335
1336     static handle null() { return 0x7FFFFFFF; }
1337 };
1338
1339 template<IndexingType indexingType>
1340 void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
1341 {
1342     ASSERT(!inSparseIndexingMode());
1343     ASSERT(indexingType == structure()->indexingType());
1344     
1345     // FIXME: This ignores exceptions raised in the compare function or in toNumber.
1346         
1347     // The maximum tree depth is compiled in - but the caller is clearly up to no good
1348     // if a larger array is passed.
1349     ASSERT(m_butterfly->publicLength() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
1350     if (m_butterfly->publicLength() > static_cast<unsigned>(std::numeric_limits<int>::max()))
1351         return;
1352         
1353     unsigned usedVectorLength = relevantLength<indexingType>();
1354     unsigned nodeCount = usedVectorLength;
1355         
1356     if (!nodeCount)
1357         return;
1358         
1359     AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
1360     tree.abstractor().m_exec = exec;
1361     tree.abstractor().m_compareFunction = compareFunction;
1362     tree.abstractor().m_compareCallType = callType;
1363     tree.abstractor().m_compareCallData = &callData;
1364     tree.abstractor().m_nodes.grow(nodeCount);
1365         
1366     if (callType == CallTypeJS)
1367         tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, jsCast<JSFunction*>(compareFunction), 2));
1368         
1369     if (!tree.abstractor().m_nodes.begin()) {
1370         throwOutOfMemoryError(exec);
1371         return;
1372     }
1373         
1374     // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
1375     // right out from under us while we're building the tree here.
1376         
1377     unsigned numDefined = 0;
1378     unsigned numUndefined = 0;
1379     
1380     // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
1381     for (; numDefined < usedVectorLength; ++numDefined) {
1382         if (numDefined >= m_butterfly->vectorLength())
1383             break;
1384         JSValue v = getHolyIndexQuickly(numDefined);
1385         if (!v || v.isUndefined())
1386             break;
1387         tree.abstractor().m_nodes[numDefined].value = v;
1388         tree.insert(numDefined);
1389     }
1390     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
1391         if (i >= m_butterfly->vectorLength())
1392             break;
1393         JSValue v = getHolyIndexQuickly(i);
1394         if (v) {
1395             if (v.isUndefined())
1396                 ++numUndefined;
1397             else {
1398                 tree.abstractor().m_nodes[numDefined].value = v;
1399                 tree.insert(numDefined);
1400                 ++numDefined;
1401             }
1402         }
1403     }
1404     
1405     unsigned newUsedVectorLength = numDefined + numUndefined;
1406         
1407     // The array size may have changed. Figure out the new bounds.
1408     unsigned newestUsedVectorLength = currentRelevantLength();
1409         
1410     unsigned elementsToExtractThreshold = min(min(newestUsedVectorLength, numDefined), static_cast<unsigned>(tree.abstractor().m_nodes.size()));
1411     unsigned undefinedElementsThreshold = min(newestUsedVectorLength, newUsedVectorLength);
1412     unsigned clearElementsThreshold = min(newestUsedVectorLength, usedVectorLength);
1413         
1414     // Copy the values back into m_storage.
1415     AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
1416     iter.start_iter_least(tree);
1417     VM& vm = exec->vm();
1418     for (unsigned i = 0; i < elementsToExtractThreshold; ++i) {
1419         ASSERT(i < butterfly()->vectorLength());
1420         if (structure()->indexingType() == ArrayWithDouble)
1421             butterfly()->contiguousDouble()[i] = tree.abstractor().m_nodes[*iter].value.asNumber();
1422         else
1423             currentIndexingData()[i].set(vm, this, tree.abstractor().m_nodes[*iter].value);
1424         ++iter;
1425     }
1426     // Put undefined values back in.
1427     switch (structure()->indexingType()) {
1428     case ArrayWithInt32:
1429     case ArrayWithDouble:
1430         ASSERT(elementsToExtractThreshold == undefinedElementsThreshold);
1431         break;
1432         
1433     default:
1434         for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i) {
1435             ASSERT(i < butterfly()->vectorLength());
1436             currentIndexingData()[i].setUndefined();
1437         }
1438     }
1439
1440     // Ensure that unused values in the vector are zeroed out.
1441     for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i) {
1442         ASSERT(i < butterfly()->vectorLength());
1443         if (structure()->indexingType() == ArrayWithDouble)
1444             butterfly()->contiguousDouble()[i] = QNaN;
1445         else
1446             currentIndexingData()[i].clear();
1447     }
1448     
1449     if (hasArrayStorage(structure()->indexingType()))
1450         arrayStorage()->m_numValuesInVector = newUsedVectorLength;
1451 }
1452
1453 void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
1454 {
1455     ASSERT(!inSparseIndexingMode());
1456     
1457     switch (structure()->indexingType()) {
1458     case ArrayClass:
1459     case ArrayWithUndecided:
1460         return;
1461         
1462     case ArrayWithInt32:
1463         sortVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
1464         return;
1465
1466     case ArrayWithDouble:
1467         sortVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
1468         return;
1469
1470     case ArrayWithContiguous:
1471         sortVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
1472         return;
1473
1474     case ArrayWithArrayStorage:
1475         sortVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
1476         return;
1477         
1478     default:
1479         RELEASE_ASSERT_NOT_REACHED();
1480     }
1481 }
1482
1483 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
1484 {
1485     unsigned i = 0;
1486     unsigned vectorEnd;
1487     WriteBarrier<Unknown>* vector;
1488     
1489     switch (structure()->indexingType()) {
1490     case ArrayClass:
1491         return;
1492         
1493     case ArrayWithUndecided: {
1494         vector = 0;
1495         vectorEnd = 0;
1496         break;
1497     }
1498         
1499     case ArrayWithInt32:
1500     case ArrayWithContiguous: {
1501         vectorEnd = m_butterfly->publicLength();
1502         vector = m_butterfly->contiguous().data();
1503         break;
1504     }
1505         
1506     case ArrayWithDouble: {
1507         vector = 0;
1508         vectorEnd = 0;
1509         for (; i < m_butterfly->publicLength(); ++i) {
1510             double v = butterfly()->contiguousDouble()[i];
1511             if (v != v)
1512                 break;
1513             args.append(JSValue(JSValue::EncodeAsDouble, v));
1514         }
1515         break;
1516     }
1517     
1518     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
1519         ArrayStorage* storage = m_butterfly->arrayStorage();
1520         
1521         vector = storage->m_vector;
1522         vectorEnd = min(storage->length(), storage->vectorLength());
1523         break;
1524     }
1525         
1526     default:
1527         CRASH();
1528         vector = 0;
1529         vectorEnd = 0;
1530         break;
1531     }
1532     
1533     for (; i < vectorEnd; ++i) {
1534         WriteBarrier<Unknown>& v = vector[i];
1535         if (!v)
1536             break;
1537         args.append(v.get());
1538     }
1539     
1540     for (; i < length(); ++i)
1541         args.append(get(exec, i));
1542 }
1543
1544 void JSArray::copyToArguments(ExecState* exec, CallFrame* callFrame, uint32_t length)
1545 {
1546     unsigned i = 0;
1547     WriteBarrier<Unknown>* vector;
1548     unsigned vectorEnd;
1549     
1550     ASSERT(length == this->length());
1551     switch (structure()->indexingType()) {
1552     case ArrayClass:
1553         return;
1554         
1555     case ArrayWithUndecided: {
1556         vector = 0;
1557         vectorEnd = 0;
1558         break;
1559     }
1560         
1561     case ArrayWithInt32:
1562     case ArrayWithContiguous: {
1563         vector = m_butterfly->contiguous().data();
1564         vectorEnd = m_butterfly->publicLength();
1565         break;
1566     }
1567         
1568     case ArrayWithDouble: {
1569         vector = 0;
1570         vectorEnd = 0;
1571         for (; i < m_butterfly->publicLength(); ++i) {
1572             ASSERT(i < butterfly()->vectorLength());
1573             double v = m_butterfly->contiguousDouble()[i];
1574             if (v != v)
1575                 break;
1576             callFrame->setArgument(i, JSValue(JSValue::EncodeAsDouble, v));
1577         }
1578         break;
1579     }
1580         
1581     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
1582         ArrayStorage* storage = m_butterfly->arrayStorage();
1583         vector = storage->m_vector;
1584         vectorEnd = min(length, storage->vectorLength());
1585         break;
1586     }
1587         
1588     default:
1589         CRASH();
1590         vector = 0;
1591         vectorEnd = 0;
1592         break;
1593     }
1594     
1595     for (; i < vectorEnd; ++i) {
1596         WriteBarrier<Unknown>& v = vector[i];
1597         if (!v)
1598             break;
1599         callFrame->setArgument(i, v.get());
1600     }
1601     
1602     for (; i < length; ++i)
1603         callFrame->setArgument(i, get(exec, i));
1604 }
1605
1606 template<IndexingType indexingType>
1607 void JSArray::compactForSorting(unsigned& numDefined, unsigned& newRelevantLength)
1608 {
1609     ASSERT(!inSparseIndexingMode());
1610     ASSERT(indexingType == structure()->indexingType());
1611
1612     unsigned myRelevantLength = relevantLength<indexingType>();
1613     
1614     numDefined = 0;
1615     unsigned numUndefined = 0;
1616         
1617     for (; numDefined < myRelevantLength; ++numDefined) {
1618         ASSERT(numDefined < m_butterfly->vectorLength());
1619         if (indexingType == ArrayWithInt32) {
1620             JSValue v = m_butterfly->contiguousInt32()[numDefined].get();
1621             if (!v)
1622                 break;
1623             ASSERT(v.isInt32());
1624             continue;
1625         }
1626         if (indexingType == ArrayWithDouble) {
1627             double v = m_butterfly->contiguousDouble()[numDefined];
1628             if (v != v)
1629                 break;
1630             continue;
1631         }
1632         JSValue v = indexingData<indexingType>()[numDefined].get();
1633         if (!v || v.isUndefined())
1634             break;
1635     }
1636         
1637     for (unsigned i = numDefined; i < myRelevantLength; ++i) {
1638         ASSERT(i < m_butterfly->vectorLength());
1639         if (indexingType == ArrayWithInt32) {
1640             JSValue v = m_butterfly->contiguousInt32()[i].get();
1641             if (!v)
1642                 continue;
1643             ASSERT(v.isInt32());
1644             ASSERT(numDefined < m_butterfly->vectorLength());
1645             m_butterfly->contiguousInt32()[numDefined++].setWithoutWriteBarrier(v);
1646             continue;
1647         }
1648         if (indexingType == ArrayWithDouble) {
1649             double v = m_butterfly->contiguousDouble()[i];
1650             if (v != v)
1651                 continue;
1652             ASSERT(numDefined < m_butterfly->vectorLength());
1653             m_butterfly->contiguousDouble()[numDefined++] = v;
1654             continue;
1655         }
1656         JSValue v = indexingData<indexingType>()[i].get();
1657         if (v) {
1658             if (v.isUndefined())
1659                 ++numUndefined;
1660             else {
1661                 ASSERT(numDefined < m_butterfly->vectorLength());
1662                 indexingData<indexingType>()[numDefined++].setWithoutWriteBarrier(v);
1663             }
1664         }
1665     }
1666         
1667     newRelevantLength = numDefined + numUndefined;
1668     
1669     if (hasArrayStorage(indexingType))
1670         RELEASE_ASSERT(!arrayStorage()->m_sparseMap);
1671     
1672     switch (indexingType) {
1673     case ArrayWithInt32:
1674     case ArrayWithDouble:
1675         RELEASE_ASSERT(numDefined == newRelevantLength);
1676         break;
1677         
1678     default:
1679         for (unsigned i = numDefined; i < newRelevantLength; ++i) {
1680             ASSERT(i < m_butterfly->vectorLength());
1681             indexingData<indexingType>()[i].setUndefined();
1682         }
1683         break;
1684     }
1685     for (unsigned i = newRelevantLength; i < myRelevantLength; ++i) {
1686         ASSERT(i < m_butterfly->vectorLength());
1687         if (indexingType == ArrayWithDouble)
1688             m_butterfly->contiguousDouble()[i] = QNaN;
1689         else
1690             indexingData<indexingType>()[i].clear();
1691     }
1692
1693     if (hasArrayStorage(indexingType))
1694         arrayStorage()->m_numValuesInVector = newRelevantLength;
1695 }
1696
1697 } // namespace JSC