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