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