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