f0df029ac4af20347b53ff9ddeffe0d74cd27d14
[WebKit-https.git] / Source / JavaScriptCore / runtime / JSArray.cpp
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2003, 2007, 2008, 2009, 2012, 2013, 2015 Apple Inc. All rights reserved.
4  *  Copyright (C) 2003 Peter Kelly (pmk@post.com)
5  *  Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
6  *
7  *  This library is free software; you can redistribute it and/or
8  *  modify it under the terms of the GNU Lesser General Public
9  *  License as published by the Free Software Foundation; either
10  *  version 2 of the License, or (at your option) any later version.
11  *
12  *  This library is distributed in the hope that it will be useful,
13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  *  Lesser General Public License for more details.
16  *
17  *  You should have received a copy of the GNU Lesser General Public
18  *  License along with this library; if not, write to the Free Software
19  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
20  *
21  */
22
23 #include "config.h"
24 #include "JSArray.h"
25
26 #include "ArrayPrototype.h"
27 #include "ButterflyInlines.h"
28 #include "CachedCall.h"
29 #include "CopiedSpace.h"
30 #include "Error.h"
31 #include "Executable.h"
32 #include "GetterSetter.h"
33 #include "IndexingHeaderInlines.h"
34 #include "JSCInlines.h"
35 #include "PropertyNameArray.h"
36 #include "Reject.h"
37 #include <wtf/Assertions.h>
38
39 using namespace std;
40 using namespace WTF;
41
42 namespace JSC {
43
44 STATIC_ASSERT_IS_TRIVIALLY_DESTRUCTIBLE(JSArray);
45
46 const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, CREATE_METHOD_TABLE(JSArray)};
47
48 Butterfly* createArrayButterflyInDictionaryIndexingMode(
49     VM& vm, JSCell* intendedOwner, unsigned initialLength)
50 {
51     Butterfly* butterfly = Butterfly::create(
52         vm, intendedOwner, 0, 0, true, IndexingHeader(), ArrayStorage::sizeFor(0));
53     ArrayStorage* storage = butterfly->arrayStorage();
54     storage->setLength(initialLength);
55     storage->setVectorLength(0);
56     storage->m_indexBias = 0;
57     storage->m_sparseMap.clear();
58     storage->m_numValuesInVector = 0;
59     return butterfly;
60 }
61
62 void JSArray::setLengthWritable(ExecState* exec, bool writable)
63 {
64     ASSERT(isLengthWritable() || !writable);
65     if (!isLengthWritable() || writable)
66         return;
67
68     enterDictionaryIndexingMode(exec->vm());
69
70     SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get();
71     ASSERT(map);
72     map->setLengthIsReadOnly();
73 }
74
75 // Defined in ES5.1 15.4.5.1
76 bool JSArray::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, const PropertyDescriptor& descriptor, bool throwException)
77 {
78     JSArray* array = jsCast<JSArray*>(object);
79
80     // 3. If P is "length", then
81     if (propertyName == exec->propertyNames().length) {
82         // All paths through length definition call the default [[DefineOwnProperty]], hence:
83         // from ES5.1 8.12.9 7.a.
84         if (descriptor.configurablePresent() && descriptor.configurable())
85             return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property.");
86         // from ES5.1 8.12.9 7.b.
87         if (descriptor.enumerablePresent() && descriptor.enumerable())
88             return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property.");
89
90         // a. If the [[Value]] field of Desc is absent, then
91         // a.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", Desc, and Throw as arguments.
92         if (descriptor.isAccessorDescriptor())
93             return reject(exec, throwException, "Attempting to change access mechanism for an unconfigurable property.");
94         // from ES5.1 8.12.9 10.a.
95         if (!array->isLengthWritable() && descriptor.writablePresent() && descriptor.writable())
96             return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property.");
97         // This descriptor is either just making length read-only, or changing nothing!
98         if (!descriptor.value()) {
99             if (descriptor.writablePresent())
100                 array->setLengthWritable(exec, descriptor.writable());
101             return true;
102         }
103         
104         // b. Let newLenDesc be a copy of Desc.
105         // c. Let newLen be ToUint32(Desc.[[Value]]).
106         unsigned newLen = descriptor.value().toUInt32(exec);
107         // d. If newLen is not equal to ToNumber( Desc.[[Value]]), throw a RangeError exception.
108         if (newLen != descriptor.value().toNumber(exec)) {
109             exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length")));
110             return false;
111         }
112
113         // Based on SameValue check in 8.12.9, this is always okay.
114         if (newLen == array->length()) {
115             if (descriptor.writablePresent())
116                 array->setLengthWritable(exec, descriptor.writable());
117             return true;
118         }
119
120         // e. Set newLenDesc.[[Value] to newLen.
121         // f. If newLen >= oldLen, then
122         // f.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments.
123         // g. Reject if oldLenDesc.[[Writable]] is false.
124         if (!array->isLengthWritable())
125             return reject(exec, throwException, "Attempting to change value of a readonly property.");
126         
127         // h. If newLenDesc.[[Writable]] is absent or has the value true, let newWritable be true.
128         // i. Else,
129         // i.i. Need to defer setting the [[Writable]] attribute to false in case any elements cannot be deleted.
130         // i.ii. Let newWritable be false.
131         // i.iii. Set newLenDesc.[[Writable] to true.
132         // 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.
133         // k. If succeeded is false, return false.
134         // l. While newLen < oldLen repeat,
135         // l.i. Set oldLen to oldLen – 1.
136         // l.ii. Let deleteSucceeded be the result of calling the [[Delete]] internal method of A passing ToString(oldLen) and false as arguments.
137         // l.iii. If deleteSucceeded is false, then
138         if (!array->setLength(exec, newLen, throwException)) {
139             // 1. Set newLenDesc.[[Value] to oldLen+1.
140             // 2. If newWritable is false, set newLenDesc.[[Writable] to false.
141             // 3. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and false as arguments.
142             // 4. Reject.
143             if (descriptor.writablePresent())
144                 array->setLengthWritable(exec, descriptor.writable());
145             return false;
146         }
147
148         // m. If newWritable is false, then
149         // i. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length",
150         //    Property Descriptor{[[Writable]]: false}, and false as arguments. This call will always
151         //    return true.
152         if (descriptor.writablePresent())
153             array->setLengthWritable(exec, descriptor.writable());
154         // n. Return true.
155         return true;
156     }
157
158     // 4. Else if P is an array index (15.4), then
159     // a. Let index be ToUint32(P).
160     if (Optional<uint32_t> optionalIndex = parseIndex(propertyName)) {
161         // b. Reject if index >= oldLen and oldLenDesc.[[Writable]] is false.
162         uint32_t index = optionalIndex.value();
163         if (index >= array->length() && !array->isLengthWritable())
164             return reject(exec, throwException, "Attempting to define numeric property on array with non-writable length property.");
165         // 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.
166         // d. Reject if succeeded is false.
167         // e. If index >= oldLen
168         // e.i. Set oldLenDesc.[[Value]] to index + 1.
169         // 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.
170         // f. Return true.
171         return array->defineOwnIndexedProperty(exec, index, descriptor, throwException);
172     }
173
174     return array->JSObject::defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException);
175 }
176
177 bool JSArray::getOwnPropertySlot(JSObject* object, ExecState* exec, PropertyName propertyName, PropertySlot& slot)
178 {
179     JSArray* thisObject = jsCast<JSArray*>(object);
180     if (propertyName == exec->propertyNames().length) {
181         unsigned attributes = thisObject->isLengthWritable() ? DontDelete | DontEnum : DontDelete | DontEnum | ReadOnly;
182         slot.setValue(thisObject, attributes, jsNumber(thisObject->length()));
183         return true;
184     }
185
186     return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
187 }
188
189 // ECMA 15.4.5.1
190 void JSArray::put(JSCell* cell, ExecState* exec, PropertyName propertyName, JSValue value, PutPropertySlot& slot)
191 {
192     JSArray* thisObject = jsCast<JSArray*>(cell);
193
194     if (propertyName == exec->propertyNames().length) {
195         unsigned newLength = value.toUInt32(exec);
196         if (value.toNumber(exec) != static_cast<double>(newLength)) {
197             exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length")));
198             return;
199         }
200         thisObject->setLength(exec, newLength, slot.isStrictMode());
201         return;
202     }
203
204     JSObject::put(thisObject, exec, propertyName, value, slot);
205 }
206
207 bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName)
208 {
209     JSArray* thisObject = jsCast<JSArray*>(cell);
210
211     if (propertyName == exec->propertyNames().length)
212         return false;
213
214     return JSObject::deleteProperty(thisObject, exec, propertyName);
215 }
216
217 static int compareKeysForQSort(const void* a, const void* b)
218 {
219     unsigned da = *static_cast<const unsigned*>(a);
220     unsigned db = *static_cast<const unsigned*>(b);
221     return (da > db) - (da < db);
222 }
223
224 void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
225 {
226     JSArray* thisObject = jsCast<JSArray*>(object);
227
228     if (mode.includeDontEnumProperties())
229         propertyNames.add(exec->propertyNames().length);
230
231     JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode);
232 }
233
234 // This method makes room in the vector, but leaves the new space for count slots uncleared.
235 bool JSArray::unshiftCountSlowCase(VM& vm, bool addToFront, unsigned count)
236 {
237     ArrayStorage* storage = ensureArrayStorage(vm);
238     Butterfly* butterfly = storage->butterfly();
239     unsigned propertyCapacity = structure(vm)->outOfLineCapacity();
240     unsigned propertySize = structure(vm)->outOfLineSize();
241
242     // If not, we should have handled this on the fast path.
243     ASSERT(!addToFront || count > storage->m_indexBias);
244
245     // Step 1:
246     // Gather 4 key metrics:
247     //  * usedVectorLength - how many entries are currently in the vector (conservative estimate - fewer may be in use in sparse vectors).
248     //  * requiredVectorLength - how many entries are will there be in the vector, after allocating space for 'count' more.
249     //  * currentCapacity - what is the current size of the vector, including any pre-capacity.
250     //  * desiredCapacity - how large should we like to grow the vector to - based on 2x requiredVectorLength.
251
252     unsigned length = storage->length();
253     unsigned usedVectorLength = min(storage->vectorLength(), length);
254     ASSERT(usedVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
255     // Check that required vector length is possible, in an overflow-safe fashion.
256     if (count > MAX_STORAGE_VECTOR_LENGTH - usedVectorLength)
257         return false;
258     unsigned requiredVectorLength = usedVectorLength + count;
259     ASSERT(requiredVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
260     // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH.
261     ASSERT(storage->vectorLength() <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - storage->vectorLength()) >= storage->m_indexBias);
262     unsigned currentCapacity = storage->vectorLength() + storage->m_indexBias;
263     // The calculation of desiredCapacity won't overflow, due to the range of MAX_STORAGE_VECTOR_LENGTH.
264     unsigned desiredCapacity = min(MAX_STORAGE_VECTOR_LENGTH, max(BASE_VECTOR_LEN, requiredVectorLength) << 1);
265
266     // Step 2:
267     // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing one.
268
269     DeferGC deferGC(vm.heap);
270     void* newAllocBase = 0;
271     unsigned newStorageCapacity;
272     // If the current storage array is sufficiently large (but not too large!) then just keep using it.
273     if (currentCapacity > desiredCapacity && isDenseEnoughForVector(currentCapacity, requiredVectorLength)) {
274         newAllocBase = butterfly->base(structure(vm));
275         newStorageCapacity = currentCapacity;
276     } else {
277         size_t newSize = Butterfly::totalSize(0, propertyCapacity, true, ArrayStorage::sizeFor(desiredCapacity));
278         if (!vm.heap.tryAllocateStorage(this, newSize, &newAllocBase))
279             return false;
280         newStorageCapacity = desiredCapacity;
281     }
282
283     // Step 3:
284     // Work out where we're going to move things to.
285
286     // Determine how much of the vector to use as pre-capacity, and how much as post-capacity.
287     // If we're adding to the end, we'll add all the new space to the end.
288     // If the vector had no free post-capacity (length >= m_vectorLength), don't give it any.
289     // If it did, we calculate the amount that will remain based on an atomic decay - leave the
290     // vector with half the post-capacity it had previously.
291     unsigned postCapacity = 0;
292     if (!addToFront)
293         postCapacity = max(newStorageCapacity - requiredVectorLength, count);
294     else if (length < storage->vectorLength()) {
295         // Atomic decay, + the post-capacity cannot be greater than what is available.
296         postCapacity = min((storage->vectorLength() - length) >> 1, newStorageCapacity - requiredVectorLength);
297         // If we're moving contents within the same allocation, the post-capacity is being reduced.
298         ASSERT(newAllocBase != butterfly->base(structure(vm)) || postCapacity < storage->vectorLength() - length);
299     }
300
301     unsigned newVectorLength = requiredVectorLength + postCapacity;
302     unsigned newIndexBias = newStorageCapacity - newVectorLength;
303
304     Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity);
305
306     if (addToFront) {
307         ASSERT(count + usedVectorLength <= newVectorLength);
308         memmove(newButterfly->arrayStorage()->m_vector + count, storage->m_vector, sizeof(JSValue) * usedVectorLength);
309         memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
310     } else if ((newAllocBase != butterfly->base(structure(vm))) || (newIndexBias != storage->m_indexBias)) {
311         memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
312         memmove(newButterfly->arrayStorage()->m_vector, storage->m_vector, sizeof(JSValue) * usedVectorLength);
313
314         WriteBarrier<Unknown>* newVector = newButterfly->arrayStorage()->m_vector;
315         for (unsigned i = requiredVectorLength; i < newVectorLength; i++)
316             newVector[i].clear();
317     }
318
319     newButterfly->arrayStorage()->setVectorLength(newVectorLength);
320     newButterfly->arrayStorage()->m_indexBias = newIndexBias;
321     setButterflyWithoutChangingStructure(vm, newButterfly);
322
323     return true;
324 }
325
326 bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, bool throwException, ArrayStorage* storage)
327 {
328     unsigned length = storage->length();
329
330     // If the length is read only then we enter sparse mode, so should enter the following 'if'.
331     ASSERT(isLengthWritable() || storage->m_sparseMap);
332
333     if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
334         // Fail if the length is not writable.
335         if (map->lengthIsReadOnly())
336             return reject(exec, throwException, StrictModeReadonlyPropertyWriteError);
337
338         if (newLength < length) {
339             // Copy any keys we might be interested in into a vector.
340             Vector<unsigned, 0, UnsafeVectorOverflow> keys;
341             keys.reserveInitialCapacity(min(map->size(), static_cast<size_t>(length - newLength)));
342             SparseArrayValueMap::const_iterator end = map->end();
343             for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
344                 unsigned index = static_cast<unsigned>(it->key);
345                 if (index < length && index >= newLength)
346                     keys.append(index);
347             }
348
349             // Check if the array is in sparse mode. If so there may be non-configurable
350             // properties, so we have to perform deletion with caution, if not we can
351             // delete values in any order.
352             if (map->sparseMode()) {
353                 qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
354                 unsigned i = keys.size();
355                 while (i) {
356                     unsigned index = keys[--i];
357                     SparseArrayValueMap::iterator it = map->find(index);
358                     ASSERT(it != map->notFound());
359                     if (it->value.attributes & DontDelete) {
360                         storage->setLength(index + 1);
361                         return reject(exec, throwException, "Unable to delete property.");
362                     }
363                     map->remove(it);
364                 }
365             } else {
366                 for (unsigned i = 0; i < keys.size(); ++i)
367                     map->remove(keys[i]);
368                 if (map->isEmpty())
369                     deallocateSparseIndexMap();
370             }
371         }
372     }
373
374     if (newLength < length) {
375         // Delete properties from the vector.
376         unsigned usedVectorLength = min(length, storage->vectorLength());
377         for (unsigned i = newLength; i < usedVectorLength; ++i) {
378             WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
379             bool hadValue = valueSlot;
380             valueSlot.clear();
381             storage->m_numValuesInVector -= hadValue;
382         }
383     }
384
385     storage->setLength(newLength);
386
387     return true;
388 }
389
390 bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
391 {
392     switch (indexingType()) {
393     case ArrayClass:
394         if (!newLength)
395             return true;
396         if (newLength >= MIN_SPARSE_ARRAY_INDEX) {
397             return setLengthWithArrayStorage(
398                 exec, newLength, throwException,
399                 convertContiguousToArrayStorage(exec->vm()));
400         }
401         createInitialUndecided(exec->vm(), newLength);
402         return true;
403         
404     case ArrayWithUndecided:
405     case ArrayWithInt32:
406     case ArrayWithDouble:
407     case ArrayWithContiguous:
408         if (newLength == m_butterfly->publicLength())
409             return true;
410         if (newLength >= MAX_ARRAY_INDEX // This case ensures that we can do fast push.
411             || (newLength >= MIN_SPARSE_ARRAY_INDEX
412                 && !isDenseEnoughForVector(newLength, countElements()))) {
413             return setLengthWithArrayStorage(
414                 exec, newLength, throwException,
415                 ensureArrayStorage(exec->vm()));
416         }
417         if (newLength > m_butterfly->publicLength()) {
418             ensureLength(exec->vm(), newLength);
419             return true;
420         }
421         if (indexingType() == ArrayWithDouble) {
422             for (unsigned i = m_butterfly->publicLength(); i-- > newLength;)
423                 m_butterfly->contiguousDouble()[i] = PNaN;
424         } else {
425             for (unsigned i = m_butterfly->publicLength(); i-- > newLength;)
426                 m_butterfly->contiguous()[i].clear();
427         }
428         m_butterfly->setPublicLength(newLength);
429         return true;
430         
431     case ArrayWithArrayStorage:
432     case ArrayWithSlowPutArrayStorage:
433         return setLengthWithArrayStorage(exec, newLength, throwException, arrayStorage());
434         
435     default:
436         CRASH();
437         return false;
438     }
439 }
440
441 JSValue JSArray::pop(ExecState* exec)
442 {
443     switch (indexingType()) {
444     case ArrayClass:
445         return jsUndefined();
446         
447     case ArrayWithUndecided:
448         if (!m_butterfly->publicLength())
449             return jsUndefined();
450         // We have nothing but holes. So, drop down to the slow version.
451         break;
452         
453     case ArrayWithInt32:
454     case ArrayWithContiguous: {
455         unsigned length = m_butterfly->publicLength();
456         
457         if (!length--)
458             return jsUndefined();
459         
460         RELEASE_ASSERT(length < m_butterfly->vectorLength());
461         JSValue value = m_butterfly->contiguous()[length].get();
462         if (value) {
463             m_butterfly->contiguous()[length].clear();
464             m_butterfly->setPublicLength(length);
465             return value;
466         }
467         break;
468     }
469         
470     case ArrayWithDouble: {
471         unsigned length = m_butterfly->publicLength();
472         
473         if (!length--)
474             return jsUndefined();
475         
476         RELEASE_ASSERT(length < m_butterfly->vectorLength());
477         double value = m_butterfly->contiguousDouble()[length];
478         if (value == value) {
479             m_butterfly->contiguousDouble()[length] = PNaN;
480             m_butterfly->setPublicLength(length);
481             return JSValue(JSValue::EncodeAsDouble, value);
482         }
483         break;
484     }
485         
486     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
487         ArrayStorage* storage = m_butterfly->arrayStorage();
488     
489         unsigned length = storage->length();
490         if (!length) {
491             if (!isLengthWritable())
492                 throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
493             return jsUndefined();
494         }
495
496         unsigned index = length - 1;
497         if (index < storage->vectorLength()) {
498             WriteBarrier<Unknown>& valueSlot = storage->m_vector[index];
499             if (valueSlot) {
500                 --storage->m_numValuesInVector;
501                 JSValue element = valueSlot.get();
502                 valueSlot.clear();
503             
504                 RELEASE_ASSERT(isLengthWritable());
505                 storage->setLength(index);
506                 return element;
507             }
508         }
509         break;
510     }
511         
512     default:
513         CRASH();
514         return JSValue();
515     }
516     
517     unsigned index = getArrayLength() - 1;
518     // Let element be the result of calling the [[Get]] internal method of O with argument indx.
519     JSValue element = get(exec, index);
520     if (exec->hadException())
521         return jsUndefined();
522     // Call the [[Delete]] internal method of O with arguments indx and true.
523     if (!deletePropertyByIndex(this, exec, index)) {
524         throwTypeError(exec, ASCIILiteral("Unable to delete property."));
525         return jsUndefined();
526     }
527     // Call the [[Put]] internal method of O with arguments "length", indx, and true.
528     setLength(exec, index, true);
529     // Return element.
530     return element;
531 }
532
533 // Push & putIndex are almost identical, with two small differences.
534 //  - we always are writing beyond the current array bounds, so it is always necessary to update m_length & m_numValuesInVector.
535 //  - pushing to an array of length 2^32-1 stores the property, but throws a range error.
536 void JSArray::push(ExecState* exec, JSValue value)
537 {
538     switch (indexingType()) {
539     case ArrayClass: {
540         createInitialUndecided(exec->vm(), 0);
541         FALLTHROUGH;
542     }
543         
544     case ArrayWithUndecided: {
545         convertUndecidedForValue(exec->vm(), value);
546         push(exec, value);
547         return;
548     }
549         
550     case ArrayWithInt32: {
551         if (!value.isInt32()) {
552             convertInt32ForValue(exec->vm(), value);
553             push(exec, value);
554             return;
555         }
556
557         unsigned length = m_butterfly->publicLength();
558         ASSERT(length <= m_butterfly->vectorLength());
559         if (length < m_butterfly->vectorLength()) {
560             m_butterfly->contiguousInt32()[length].setWithoutWriteBarrier(value);
561             m_butterfly->setPublicLength(length + 1);
562             return;
563         }
564         
565         if (length > MAX_ARRAY_INDEX) {
566             methodTable(exec->vm())->putByIndex(this, exec, length, value, true);
567             if (!exec->hadException())
568                 exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length")));
569             return;
570         }
571         
572         putByIndexBeyondVectorLengthWithoutAttributes<Int32Shape>(exec, length, value);
573         return;
574     }
575
576     case ArrayWithContiguous: {
577         unsigned length = m_butterfly->publicLength();
578         ASSERT(length <= m_butterfly->vectorLength());
579         if (length < m_butterfly->vectorLength()) {
580             m_butterfly->contiguous()[length].set(exec->vm(), this, value);
581             m_butterfly->setPublicLength(length + 1);
582             return;
583         }
584         
585         if (length > MAX_ARRAY_INDEX) {
586             methodTable(exec->vm())->putByIndex(this, exec, length, value, true);
587             if (!exec->hadException())
588                 exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length")));
589             return;
590         }
591         
592         putByIndexBeyondVectorLengthWithoutAttributes<ContiguousShape>(exec, length, value);
593         return;
594     }
595         
596     case ArrayWithDouble: {
597         if (!value.isNumber()) {
598             convertDoubleToContiguous(exec->vm());
599             push(exec, value);
600             return;
601         }
602         double valueAsDouble = value.asNumber();
603         if (valueAsDouble != valueAsDouble) {
604             convertDoubleToContiguous(exec->vm());
605             push(exec, value);
606             return;
607         }
608
609         unsigned length = m_butterfly->publicLength();
610         ASSERT(length <= m_butterfly->vectorLength());
611         if (length < m_butterfly->vectorLength()) {
612             m_butterfly->contiguousDouble()[length] = valueAsDouble;
613             m_butterfly->setPublicLength(length + 1);
614             return;
615         }
616         
617         if (length > MAX_ARRAY_INDEX) {
618             methodTable(exec->vm())->putByIndex(this, exec, length, value, true);
619             if (!exec->hadException())
620                 exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length")));
621             return;
622         }
623         
624         putByIndexBeyondVectorLengthWithoutAttributes<DoubleShape>(exec, length, value);
625         break;
626     }
627         
628     case ArrayWithSlowPutArrayStorage: {
629         unsigned oldLength = length();
630         if (attemptToInterceptPutByIndexOnHole(exec, oldLength, value, true)) {
631             if (!exec->hadException() && oldLength < 0xFFFFFFFFu)
632                 setLength(exec, oldLength + 1, true);
633             return;
634         }
635         FALLTHROUGH;
636     }
637         
638     case ArrayWithArrayStorage: {
639         ArrayStorage* storage = m_butterfly->arrayStorage();
640
641         // Fast case - push within vector, always update m_length & m_numValuesInVector.
642         unsigned length = storage->length();
643         if (length < storage->vectorLength()) {
644             storage->m_vector[length].set(exec->vm(), this, value);
645             storage->setLength(length + 1);
646             ++storage->m_numValuesInVector;
647             return;
648         }
649
650         // Pushing to an array of invalid length (2^31-1) stores the property, but throws a range error.
651         if (storage->length() > MAX_ARRAY_INDEX) {
652             methodTable(exec->vm())->putByIndex(this, exec, storage->length(), value, true);
653             // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d.
654             if (!exec->hadException())
655                 exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length")));
656             return;
657         }
658
659         // Handled the same as putIndex.
660         putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage);
661         break;
662     }
663         
664     default:
665         RELEASE_ASSERT_NOT_REACHED();
666     }
667 }
668
669 bool JSArray::shiftCountWithArrayStorage(VM& vm, unsigned startIndex, unsigned count, ArrayStorage* storage)
670 {
671     unsigned oldLength = storage->length();
672     RELEASE_ASSERT(count <= oldLength);
673     
674     // If the array contains holes or is otherwise in an abnormal state,
675     // use the generic algorithm in ArrayPrototype.
676     if ((storage->hasHoles() && this->structure(vm)->holesMustForwardToPrototype(vm)) 
677         || hasSparseMap() 
678         || shouldUseSlowPut(indexingType())) {
679         return false;
680     }
681
682     if (!oldLength)
683         return true;
684     
685     unsigned length = oldLength - count;
686     
687     storage->m_numValuesInVector -= count;
688     storage->setLength(length);
689     
690     unsigned vectorLength = storage->vectorLength();
691     if (!vectorLength)
692         return true;
693     
694     if (startIndex >= vectorLength)
695         return true;
696     
697     if (startIndex + count > vectorLength)
698         count = vectorLength - startIndex;
699     
700     unsigned usedVectorLength = min(vectorLength, oldLength);
701     
702     unsigned numElementsBeforeShiftRegion = startIndex;
703     unsigned firstIndexAfterShiftRegion = startIndex + count;
704     unsigned numElementsAfterShiftRegion = usedVectorLength - firstIndexAfterShiftRegion;
705     ASSERT(numElementsBeforeShiftRegion + count + numElementsAfterShiftRegion == usedVectorLength);
706
707     // The point of this comparison seems to be to minimize the amount of elements that have to 
708     // be moved during a shift operation.
709     if (numElementsBeforeShiftRegion < numElementsAfterShiftRegion) {
710         // The number of elements before the shift region is less than the number of elements
711         // after the shift region, so we move the elements before to the right.
712         if (numElementsBeforeShiftRegion) {
713             RELEASE_ASSERT(count + startIndex <= vectorLength);
714             if (storage->hasHoles()) {
715                 for (unsigned i = startIndex; i-- > 0;) {
716                     unsigned destinationIndex = count + i;
717                     JSValue source = storage->m_vector[i].get();
718                     JSValue dest = storage->m_vector[destinationIndex].get();
719                     // Any time we overwrite a hole we know we overcounted the number of values we removed 
720                     // when we subtracted count from m_numValuesInVector above.
721                     if (!dest && destinationIndex >= firstIndexAfterShiftRegion)
722                         storage->m_numValuesInVector++;
723                     storage->m_vector[count + i].setWithoutWriteBarrier(source);
724                 }
725             } else {
726                 memmove(storage->m_vector + count,
727                     storage->m_vector,
728                     sizeof(JSValue) * startIndex);
729             }
730         }
731         // Adjust the Butterfly and the index bias. We only need to do this here because we're changing
732         // the start of the Butterfly, which needs to point at the first indexed property in the used
733         // portion of the vector.
734         m_butterfly.setWithoutWriteBarrier(m_butterfly->shift(structure(), count));
735         storage = m_butterfly->arrayStorage();
736         storage->m_indexBias += count;
737
738         // Since we're consuming part of the vector by moving its beginning to the left,
739         // we need to modify the vector length appropriately.
740         storage->setVectorLength(vectorLength - count);
741     } else {
742         // The number of elements before the shift region is greater than or equal to the number 
743         // of elements after the shift region, so we move the elements after the shift region to the left.
744         if (storage->hasHoles()) {
745             for (unsigned i = 0; i < numElementsAfterShiftRegion; ++i) {
746                 unsigned destinationIndex = startIndex + i;
747                 JSValue source = storage->m_vector[firstIndexAfterShiftRegion + i].get();
748                 JSValue dest = storage->m_vector[destinationIndex].get();
749                 // Any time we overwrite a hole we know we overcounted the number of values we removed 
750                 // when we subtracted count from m_numValuesInVector above.
751                 if (!dest && destinationIndex < firstIndexAfterShiftRegion)
752                     storage->m_numValuesInVector++;
753                 storage->m_vector[startIndex + i].setWithoutWriteBarrier(source);
754             }
755         } else {
756             memmove(storage->m_vector + startIndex,
757                 storage->m_vector + firstIndexAfterShiftRegion,
758                 sizeof(JSValue) * numElementsAfterShiftRegion);
759         }
760         // Clear the slots of the elements we just moved.
761         unsigned startOfEmptyVectorTail = usedVectorLength - count;
762         for (unsigned i = startOfEmptyVectorTail; i < usedVectorLength; ++i)
763             storage->m_vector[i].clear();
764         // We don't modify the index bias or the Butterfly pointer in this case because we're not changing 
765         // the start of the Butterfly, which needs to point at the first indexed property in the used 
766         // portion of the vector. We also don't modify the vector length because we're not actually changing
767         // its length; we're just using less of it.
768     }
769     
770     return true;
771 }
772
773 bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned& startIndex, unsigned count)
774 {
775     VM& vm = exec->vm();
776     RELEASE_ASSERT(count > 0);
777     
778     switch (indexingType()) {
779     case ArrayClass:
780         return true;
781         
782     case ArrayWithUndecided:
783         // Don't handle this because it's confusing and it shouldn't come up.
784         return false;
785         
786     case ArrayWithInt32:
787     case ArrayWithContiguous: {
788         unsigned oldLength = m_butterfly->publicLength();
789         RELEASE_ASSERT(count <= oldLength);
790         
791         // We may have to walk the entire array to do the shift. We're willing to do
792         // so only if it's not horribly slow.
793         if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
794             return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
795
796         // Storing to a hole is fine since we're still having a good time. But reading from a hole 
797         // is totally not fine, since we might have to read from the proto chain.
798         // We have to check for holes before we start moving things around so that we don't get halfway 
799         // through shifting and then realize we should have been in ArrayStorage mode.
800         unsigned end = oldLength - count;
801         if (this->structure(vm)->holesMustForwardToPrototype(vm)) {
802             for (unsigned i = startIndex; i < end; ++i) {
803                 JSValue v = m_butterfly->contiguous()[i + count].get();
804                 if (UNLIKELY(!v)) {
805                     startIndex = i;
806                     return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
807                 }
808                 m_butterfly->contiguous()[i].setWithoutWriteBarrier(v);
809             }
810         } else {
811             memmove(m_butterfly->contiguous().data() + startIndex, 
812                 m_butterfly->contiguous().data() + startIndex + count, 
813                 sizeof(JSValue) * (end - startIndex));
814         }
815
816         for (unsigned i = end; i < oldLength; ++i)
817             m_butterfly->contiguous()[i].clear();
818         
819         m_butterfly->setPublicLength(oldLength - count);
820         return true;
821     }
822         
823     case ArrayWithDouble: {
824         unsigned oldLength = m_butterfly->publicLength();
825         RELEASE_ASSERT(count <= oldLength);
826         
827         // We may have to walk the entire array to do the shift. We're willing to do
828         // so only if it's not horribly slow.
829         if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
830             return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
831
832         // Storing to a hole is fine since we're still having a good time. But reading from a hole 
833         // is totally not fine, since we might have to read from the proto chain.
834         // We have to check for holes before we start moving things around so that we don't get halfway 
835         // through shifting and then realize we should have been in ArrayStorage mode.
836         unsigned end = oldLength - count;
837         if (this->structure(vm)->holesMustForwardToPrototype(vm)) {
838             for (unsigned i = startIndex; i < end; ++i) {
839                 double v = m_butterfly->contiguousDouble()[i + count];
840                 if (UNLIKELY(v != v)) {
841                     startIndex = i;
842                     return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
843                 }
844                 m_butterfly->contiguousDouble()[i] = v;
845             }
846         } else {
847             memmove(m_butterfly->contiguousDouble().data() + startIndex,
848                 m_butterfly->contiguousDouble().data() + startIndex + count,
849                 sizeof(JSValue) * (end - startIndex));
850         }
851         for (unsigned i = end; i < oldLength; ++i)
852             m_butterfly->contiguousDouble()[i] = PNaN;
853         
854         m_butterfly->setPublicLength(oldLength - count);
855         return true;
856     }
857         
858     case ArrayWithArrayStorage:
859     case ArrayWithSlowPutArrayStorage:
860         return shiftCountWithArrayStorage(vm, startIndex, count, arrayStorage());
861         
862     default:
863         CRASH();
864         return false;
865     }
866 }
867
868 // Returns true if the unshift can be handled, false to fallback.    
869 bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, unsigned count, ArrayStorage* storage)
870 {
871     unsigned length = storage->length();
872
873     RELEASE_ASSERT(startIndex <= length);
874
875     // If the array contains holes or is otherwise in an abnormal state,
876     // use the generic algorithm in ArrayPrototype.
877     if (storage->hasHoles() || storage->inSparseMode() || shouldUseSlowPut(indexingType()))
878         return false;
879
880     bool moveFront = !startIndex || startIndex < length / 2;
881
882     unsigned vectorLength = storage->vectorLength();
883
884     if (moveFront && storage->m_indexBias >= count) {
885         Butterfly* newButterfly = storage->butterfly()->unshift(structure(), count);
886         storage = newButterfly->arrayStorage();
887         storage->m_indexBias -= count;
888         storage->setVectorLength(vectorLength + count);
889         setButterflyWithoutChangingStructure(exec->vm(), newButterfly);
890     } else if (!moveFront && vectorLength - length >= count)
891         storage = storage->butterfly()->arrayStorage();
892     else if (unshiftCountSlowCase(exec->vm(), moveFront, count))
893         storage = arrayStorage();
894     else {
895         throwOutOfMemoryError(exec);
896         return true;
897     }
898
899     WriteBarrier<Unknown>* vector = storage->m_vector;
900
901     if (startIndex) {
902         if (moveFront)
903             memmove(vector, vector + count, startIndex * sizeof(JSValue));
904         else if (length - startIndex)
905             memmove(vector + startIndex + count, vector + startIndex, (length - startIndex) * sizeof(JSValue));
906     }
907
908     for (unsigned i = 0; i < count; i++)
909         vector[i + startIndex].clear();
910     return true;
911 }
912
913 bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)
914 {
915     switch (indexingType()) {
916     case ArrayClass:
917     case ArrayWithUndecided:
918         // We could handle this. But it shouldn't ever come up, so we won't.
919         return false;
920
921     case ArrayWithInt32:
922     case ArrayWithContiguous: {
923         unsigned oldLength = m_butterfly->publicLength();
924         
925         // We may have to walk the entire array to do the unshift. We're willing to do so
926         // only if it's not horribly slow.
927         if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
928             return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
929         
930         ensureLength(exec->vm(), oldLength + count);
931
932         // We have to check for holes before we start moving things around so that we don't get halfway 
933         // through shifting and then realize we should have been in ArrayStorage mode.
934         for (unsigned i = oldLength; i-- > startIndex;) {
935             JSValue v = m_butterfly->contiguous()[i].get();
936             if (UNLIKELY(!v))
937                 return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
938         }
939
940         for (unsigned i = oldLength; i-- > startIndex;) {
941             JSValue v = m_butterfly->contiguous()[i].get();
942             ASSERT(v);
943             m_butterfly->contiguous()[i + count].setWithoutWriteBarrier(v);
944         }
945         
946         // NOTE: we're leaving being garbage in the part of the array that we shifted out
947         // of. This is fine because the caller is required to store over that area, and
948         // in contiguous mode storing into a hole is guaranteed to behave exactly the same
949         // as storing over an existing element.
950         
951         return true;
952     }
953         
954     case ArrayWithDouble: {
955         unsigned oldLength = m_butterfly->publicLength();
956         
957         // We may have to walk the entire array to do the unshift. We're willing to do so
958         // only if it's not horribly slow.
959         if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
960             return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
961         
962         ensureLength(exec->vm(), oldLength + count);
963         
964         // We have to check for holes before we start moving things around so that we don't get halfway 
965         // through shifting and then realize we should have been in ArrayStorage mode.
966         for (unsigned i = oldLength; i-- > startIndex;) {
967             double v = m_butterfly->contiguousDouble()[i];
968             if (UNLIKELY(v != v))
969                 return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
970         }
971
972         for (unsigned i = oldLength; i-- > startIndex;) {
973             double v = m_butterfly->contiguousDouble()[i];
974             ASSERT(v == v);
975             m_butterfly->contiguousDouble()[i + count] = v;
976         }
977         
978         // NOTE: we're leaving being garbage in the part of the array that we shifted out
979         // of. This is fine because the caller is required to store over that area, and
980         // in contiguous mode storing into a hole is guaranteed to behave exactly the same
981         // as storing over an existing element.
982         
983         return true;
984     }
985         
986     case ArrayWithArrayStorage:
987     case ArrayWithSlowPutArrayStorage:
988         return unshiftCountWithArrayStorage(exec, startIndex, count, arrayStorage());
989         
990     default:
991         CRASH();
992         return false;
993     }
994 }
995
996 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
997 {
998     unsigned i = 0;
999     unsigned vectorEnd;
1000     WriteBarrier<Unknown>* vector;
1001     
1002     switch (indexingType()) {
1003     case ArrayClass:
1004         return;
1005         
1006     case ArrayWithUndecided: {
1007         vector = 0;
1008         vectorEnd = 0;
1009         break;
1010     }
1011         
1012     case ArrayWithInt32:
1013     case ArrayWithContiguous: {
1014         vectorEnd = m_butterfly->publicLength();
1015         vector = m_butterfly->contiguous().data();
1016         break;
1017     }
1018         
1019     case ArrayWithDouble: {
1020         vector = 0;
1021         vectorEnd = 0;
1022         for (; i < m_butterfly->publicLength(); ++i) {
1023             double v = butterfly()->contiguousDouble()[i];
1024             if (v != v)
1025                 break;
1026             args.append(JSValue(JSValue::EncodeAsDouble, v));
1027         }
1028         break;
1029     }
1030     
1031     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
1032         ArrayStorage* storage = m_butterfly->arrayStorage();
1033         
1034         vector = storage->m_vector;
1035         vectorEnd = min(storage->length(), storage->vectorLength());
1036         break;
1037     }
1038         
1039     default:
1040         CRASH();
1041 #if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
1042         vector = 0;
1043         vectorEnd = 0;
1044         break;
1045 #endif
1046     }
1047     
1048     for (; i < vectorEnd; ++i) {
1049         WriteBarrier<Unknown>& v = vector[i];
1050         if (!v)
1051             break;
1052         args.append(v.get());
1053     }
1054     
1055     for (; i < length(); ++i)
1056         args.append(get(exec, i));
1057 }
1058
1059 void JSArray::copyToArguments(ExecState* exec, VirtualRegister firstElementDest, unsigned offset, unsigned length)
1060 {
1061     unsigned i = offset;
1062     WriteBarrier<Unknown>* vector;
1063     unsigned vectorEnd;
1064     length += offset; // We like to think of the length as being our length, rather than the output length.
1065     ASSERT(length == this->length());
1066     switch (indexingType()) {
1067     case ArrayClass:
1068         return;
1069         
1070     case ArrayWithUndecided: {
1071         vector = 0;
1072         vectorEnd = 0;
1073         break;
1074     }
1075         
1076     case ArrayWithInt32:
1077     case ArrayWithContiguous: {
1078         vector = m_butterfly->contiguous().data();
1079         vectorEnd = m_butterfly->publicLength();
1080         break;
1081     }
1082         
1083     case ArrayWithDouble: {
1084         vector = 0;
1085         vectorEnd = 0;
1086         for (; i < m_butterfly->publicLength(); ++i) {
1087             ASSERT(i < butterfly()->vectorLength());
1088             double v = m_butterfly->contiguousDouble()[i];
1089             if (v != v)
1090                 break;
1091             exec->r(firstElementDest + i - offset) = JSValue(JSValue::EncodeAsDouble, v);
1092         }
1093         break;
1094     }
1095         
1096     case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
1097         ArrayStorage* storage = m_butterfly->arrayStorage();
1098         vector = storage->m_vector;
1099         vectorEnd = min(length, storage->vectorLength());
1100         break;
1101     }
1102         
1103     default:
1104         CRASH();
1105 #if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
1106         vector = 0;
1107         vectorEnd = 0;
1108         break;
1109 #endif
1110     }
1111     
1112     for (; i < vectorEnd; ++i) {
1113         WriteBarrier<Unknown>& v = vector[i];
1114         if (!v)
1115             break;
1116         exec->r(firstElementDest + i - offset) = v.get();
1117     }
1118     
1119     for (; i < length; ++i) {
1120         exec->r(firstElementDest + i - offset) = get(exec, i);
1121         if (UNLIKELY(exec->vm().exception()))
1122             return;
1123     }
1124 }
1125
1126 } // namespace JSC