Implement fast path for op_new_array in the baseline JIT
[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 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 "CopiedSpace.h"
28 #include "CopiedSpaceInlineMethods.h"
29 #include "CachedCall.h"
30 #include "Error.h"
31 #include "Executable.h"
32 #include "GetterSetter.h"
33 #include "PropertyNameArray.h"
34 #include <wtf/AVLTree.h>
35 #include <wtf/Assertions.h>
36 #include <wtf/OwnPtr.h>
37 #include <Operations.h>
38
39 using namespace std;
40 using namespace WTF;
41
42 namespace JSC {
43
44 ASSERT_CLASS_FITS_IN_CELL(JSArray);
45 ASSERT_HAS_TRIVIAL_DESTRUCTOR(JSArray);
46
47 // Overview of JSArray
48 //
49 // Properties of JSArray objects may be stored in one of three locations:
50 //   * The regular JSObject property map.
51 //   * A storage vector.
52 //   * A sparse map of array entries.
53 //
54 // Properties with non-numeric identifiers, with identifiers that are not representable
55 // as an unsigned integer, or where the value is greater than  MAX_ARRAY_INDEX
56 // (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit
57 // integer) are not considered array indices and will be stored in the JSObject property map.
58 //
59 // All properties with a numeric identifer, representable as an unsigned integer i,
60 // where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the
61 // storage vector or the sparse map.  An array index i will be handled in the following
62 // fashion:
63 //
64 //   * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector,
65 //     unless the array is in SparseMode in which case all properties go into the map.
66 //   * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either
67 //     be stored in the storage vector or in the sparse array, depending on the density of
68 //     data that would be stored in the vector (a vector being used where at least
69 //     (1 / minDensityMultiplier) of the entries would be populated).
70 //   * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored
71 //     in the sparse array.
72
73 // The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
74 // function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
75 // size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) +
76 // (vectorLength * sizeof(WriteBarrier<Unknown>)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
77 #define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>))
78
79 // These values have to be macros to be used in max() and min() without introducing
80 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
81 #define MIN_SPARSE_ARRAY_INDEX 10000U
82 #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
83 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
84 #define MAX_ARRAY_INDEX 0xFFFFFFFEU
85
86 // The value BASE_VECTOR_LEN is the maximum number of vector elements we'll allocate
87 // for an array that was created with a sepcified length (e.g. a = new Array(123))
88 #define BASE_VECTOR_LEN 4U
89     
90 // The upper bound to the size we'll grow a zero length array when the first element
91 // is added.
92 #define FIRST_VECTOR_GROW 4U
93
94 // Our policy for when to use a vector and when to use a sparse map.
95 // For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
96 // When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
97 // as long as it is 1/8 full. If more sparse than that, we use a map.
98 static const unsigned minDensityMultiplier = 8;
99
100 const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0, CREATE_METHOD_TABLE(JSArray)};
101
102 // We keep track of the size of the last array after it was grown.  We use this
103 // as a simple heuristic for as the value to grow the next array from size 0.
104 // This value is capped by the constant FIRST_VECTOR_GROW defined above.
105 static unsigned lastArraySize = 0;
106
107 static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
108 {
109     return length <= MIN_SPARSE_ARRAY_INDEX || length / minDensityMultiplier <= numValues;
110 }
111
112 #if !CHECK_ARRAY_CONSISTENCY
113
114 inline void JSArray::checkConsistency(ConsistencyCheckType)
115 {
116 }
117
118 #endif
119
120 JSArray::JSArray(JSGlobalData& globalData, Structure* structure)
121     : JSNonFinalObject(globalData, structure)
122     , m_indexBias(0)
123     , m_storage(0)
124     , m_sparseValueMap(0)
125     , m_subclassData(0)
126 {
127 }
128
129 void JSArray::finishCreation(JSGlobalData& globalData, unsigned initialLength)
130 {
131     Base::finishCreation(globalData);
132     ASSERT(inherits(&s_info));
133
134     unsigned initialVectorLength = BASE_VECTOR_LEN;
135     unsigned initialStorageSize = storageSize(initialVectorLength);
136
137     void* newStorage = 0;
138     if (!globalData.heap.tryAllocateStorage(initialStorageSize, &newStorage))
139         CRASH();
140     
141     m_storage = static_cast<ArrayStorage*>(newStorage);
142     m_storage->m_allocBase = m_storage;
143     m_storage->m_length = initialLength;
144     m_vectorLength = initialVectorLength;
145     m_storage->m_numValuesInVector = 0;
146 #if CHECK_ARRAY_CONSISTENCY
147     m_storage->m_inCompactInitialization = false;
148 #endif
149
150     checkConsistency();
151 }
152
153 JSArray* JSArray::tryFinishCreationUninitialized(JSGlobalData& globalData, unsigned initialLength)
154 {
155     Base::finishCreation(globalData);
156     ASSERT(inherits(&s_info));
157
158     // Check for lengths larger than we can handle with a vector.
159     if (initialLength > MAX_STORAGE_VECTOR_LENGTH)
160         return 0;
161
162     unsigned initialVectorLength = max(initialLength, BASE_VECTOR_LEN);
163     unsigned initialStorageSize = storageSize(initialVectorLength);
164
165     void* newStorage = 0;
166     if (!globalData.heap.tryAllocateStorage(initialStorageSize, &newStorage))
167         CRASH();
168     
169     m_storage = static_cast<ArrayStorage*>(newStorage);
170     m_storage->m_allocBase = m_storage;
171     m_storage->m_length = 0;
172     m_vectorLength = initialVectorLength;
173     m_storage->m_numValuesInVector = initialLength;
174
175 #if CHECK_ARRAY_CONSISTENCY
176     m_storage->m_inCompactInitialization = true;
177 #endif
178
179     return this;
180 }
181
182 // This function can be called multiple times on the same object.
183 void JSArray::finalize(JSCell* cell)
184 {
185     JSArray* thisObject = jsCast<JSArray*>(cell);
186     thisObject->checkConsistency(DestructorConsistencyCheck);
187     thisObject->deallocateSparseMap();
188 }
189
190 inline std::pair<SparseArrayValueMap::iterator, bool> SparseArrayValueMap::add(JSArray* array, unsigned i)
191 {
192     SparseArrayEntry entry;
193     std::pair<iterator, bool> result = m_map.add(i, entry);
194     size_t capacity = m_map.capacity();
195     if (capacity != m_reportedCapacity) {
196         Heap::heap(array)->reportExtraMemoryCost((capacity - m_reportedCapacity) * (sizeof(unsigned) + sizeof(WriteBarrier<Unknown>)));
197         m_reportedCapacity = capacity;
198     }
199     return result;
200 }
201
202 inline void SparseArrayValueMap::put(ExecState* exec, JSArray* array, unsigned i, JSValue value)
203 {
204     std::pair<SparseArrayValueMap::iterator, bool> result = add(array, i);
205     SparseArrayEntry& entry = result.first->second;
206
207     // To save a separate find & add, we first always add to the sparse map.
208     // In the uncommon case that this is a new property, and the array is not
209     // extensible, this is not the right thing to have done - so remove again.
210     if (result.second && !array->isExtensible()) {
211         remove(result.first);
212         // FIXME: should throw in strict mode.
213         return;
214     }
215
216     if (!(entry.attributes & Accessor)) {
217         if (entry.attributes & ReadOnly) {
218             // FIXME: should throw if being called from strict mode.
219             // throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
220             return;
221         }
222
223         entry.set(exec->globalData(), array, value);
224         return;
225     }
226
227     JSValue accessor = entry.Base::get();
228     ASSERT(accessor.isGetterSetter());
229     JSObject* setter = asGetterSetter(accessor)->setter();
230     
231     if (!setter) {
232         // FIXME: should throw if being called from strict mode.
233         // throwTypeError(exec, "setting a property that has only a getter");
234         return;
235     }
236
237     CallData callData;
238     CallType callType = setter->methodTable()->getCallData(setter, callData);
239     MarkedArgumentBuffer args;
240     args.append(value);
241     call(exec, setter, callType, callData, array, args);
242 }
243
244 inline void SparseArrayEntry::get(PropertySlot& slot) const
245 {
246     JSValue value = Base::get();
247     ASSERT(value);
248
249     if (LIKELY(!value.isGetterSetter())) {
250         slot.setValue(value);
251         return;
252     }
253
254     JSObject* getter = asGetterSetter(value)->getter();
255     if (!getter) {
256         slot.setUndefined();
257         return;
258     }
259
260     slot.setGetterSlot(getter);
261 }
262
263 inline void SparseArrayEntry::get(PropertyDescriptor& descriptor) const
264 {
265     descriptor.setDescriptor(Base::get(), attributes);
266 }
267
268 inline JSValue SparseArrayEntry::get(ExecState* exec, JSArray* array) const
269 {
270     JSValue result = Base::get();
271     ASSERT(result);
272
273     if (LIKELY(!result.isGetterSetter()))
274         return result;
275
276     JSObject* getter = asGetterSetter(result)->getter();
277     if (!getter)
278         return jsUndefined();
279
280     CallData callData;
281     CallType callType = getter->methodTable()->getCallData(getter, callData);
282     return call(exec, getter, callType, callData, array, exec->emptyList());
283 }
284
285 inline JSValue SparseArrayEntry::getNonSparseMode() const
286 {
287     ASSERT(!attributes);
288     return Base::get();
289 }
290
291 inline void SparseArrayValueMap::visitChildren(SlotVisitor& visitor)
292 {
293     iterator end = m_map.end();
294     for (iterator it = m_map.begin(); it != end; ++it)
295         visitor.append(&it->second);
296 }
297
298 void JSArray::allocateSparseMap(JSGlobalData& globalData)
299 {
300     m_sparseValueMap = new SparseArrayValueMap;
301     globalData.heap.addFinalizer(this, finalize);
302 }
303
304 void JSArray::deallocateSparseMap()
305 {
306     delete m_sparseValueMap;
307     m_sparseValueMap = 0;
308 }
309
310 void JSArray::enterDictionaryMode(JSGlobalData& globalData)
311 {
312     ArrayStorage* storage = m_storage;
313     SparseArrayValueMap* map = m_sparseValueMap;
314
315     if (!map) {
316         allocateSparseMap(globalData);
317         map = m_sparseValueMap;
318     }
319
320     if (map->sparseMode())
321         return;
322
323     map->setSparseMode();
324
325     unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
326     for (unsigned i = 0; i < usedVectorLength; ++i) {
327         JSValue value = storage->m_vector[i].get();
328         // This will always be a new entry in the map, so no need to check we can write,
329         // and attributes are default so no need to set them.
330         if (value)
331             map->add(this, i).first->second.set(globalData, this, value);
332     }
333
334     void* newRawStorage = 0;
335     if (!globalData.heap.tryAllocateStorage(storageSize(0), &newRawStorage))
336         CRASH();
337     
338     ArrayStorage* newStorage = static_cast<ArrayStorage*>(newRawStorage);
339     memcpy(newStorage, m_storage, storageSize(0));
340     newStorage->m_allocBase = newStorage;
341     m_storage = newStorage;
342     m_indexBias = 0;
343     m_vectorLength = 0;
344 }
345
346 void JSArray::putDescriptor(ExecState* exec, SparseArrayEntry* entryInMap, PropertyDescriptor& descriptor, PropertyDescriptor& oldDescriptor)
347 {
348     if (descriptor.isDataDescriptor()) {
349         if (descriptor.value())
350             entryInMap->set(exec->globalData(), this, descriptor.value());
351         else if (oldDescriptor.isAccessorDescriptor())
352             entryInMap->set(exec->globalData(), this, jsUndefined());
353         entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor) & ~Accessor;
354         return;
355     }
356
357     if (descriptor.isAccessorDescriptor()) {
358         JSObject* getter = 0;
359         if (descriptor.getterPresent())
360             getter = descriptor.getterObject();
361         else if (oldDescriptor.isAccessorDescriptor())
362             getter = oldDescriptor.getterObject();
363         JSObject* setter = 0;
364         if (descriptor.setterPresent())
365             setter = descriptor.setterObject();
366         else if (oldDescriptor.isAccessorDescriptor())
367             setter = oldDescriptor.setterObject();
368
369         GetterSetter* accessor = GetterSetter::create(exec);
370         if (getter)
371             accessor->setGetter(exec->globalData(), getter);
372         if (setter)
373             accessor->setSetter(exec->globalData(), setter);
374
375         entryInMap->set(exec->globalData(), this, accessor);
376         entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor) & ~ReadOnly;
377         return;
378     }
379
380     ASSERT(descriptor.isGenericDescriptor());
381     entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor);
382 }
383
384 static bool reject(ExecState* exec, bool throwException, const char* message)
385 {
386     if (throwException)
387         throwTypeError(exec, message);
388     return false;
389 }
390
391 // Defined in ES5.1 8.12.9
392 bool JSArray::defineOwnNumericProperty(ExecState* exec, unsigned index, PropertyDescriptor& descriptor, bool throwException)
393 {
394     ASSERT(index != 0xFFFFFFFF);
395
396     if (!inSparseMode()) {
397         // Fast case: we're putting a regular property to a regular array
398         // FIXME: this will pessimistically assume that if attributes are missing then they'll default to false
399         // – however if the property currently exists missing attributes will override from their current 'true'
400         // state (i.e. defineOwnProperty could be used to set a value without needing to entering 'SparseMode').
401         if (!descriptor.attributes()) {
402             ASSERT(!descriptor.isAccessorDescriptor());
403             putByIndex(this, exec, index, descriptor.value());
404             return true;
405         }
406
407         enterDictionaryMode(exec->globalData());
408     }
409
410     SparseArrayValueMap* map = m_sparseValueMap;
411     ASSERT(map);
412
413     // 1. Let current be the result of calling the [[GetOwnProperty]] internal method of O with property name P.
414     std::pair<SparseArrayValueMap::iterator, bool> result = map->add(this, index);
415     SparseArrayEntry* entryInMap = &result.first->second;
416
417     // 2. Let extensible be the value of the [[Extensible]] internal property of O.
418     // 3. If current is undefined and extensible is false, then Reject.
419     // 4. If current is undefined and extensible is true, then
420     if (result.second) {
421         if (!isExtensible()) {
422             map->remove(result.first);
423             return reject(exec, throwException, "Attempting to define property on object that is not extensible.");
424         }
425
426         // 4.a. If IsGenericDescriptor(Desc) or IsDataDescriptor(Desc) is true, then create an own data property
427         // named P of object O whose [[Value]], [[Writable]], [[Enumerable]] and [[Configurable]] attribute values
428         // are described by Desc. If the value of an attribute field of Desc is absent, the attribute of the newly
429         // created property is set to its default value.
430         // 4.b. Else, Desc must be an accessor Property Descriptor so, create an own accessor property named P of
431         // object O whose [[Get]], [[Set]], [[Enumerable]] and [[Configurable]] attribute values are described by
432         // Desc. If the value of an attribute field of Desc is absent, the attribute of the newly created property
433         // is set to its default value.
434         // 4.c. Return true.
435
436         PropertyDescriptor defaults;
437         entryInMap->setWithoutWriteBarrier(jsUndefined());
438         entryInMap->attributes = DontDelete | DontEnum | ReadOnly;
439         entryInMap->get(defaults);
440
441         putDescriptor(exec, entryInMap, descriptor, defaults);
442         if (index >= m_storage->m_length)
443             m_storage->m_length = index + 1;
444         return true;
445     }
446
447     // 5. Return true, if every field in Desc is absent.
448     // 6. Return true, if every field in Desc also occurs in current and the value of every field in Desc is the same value as the corresponding field in current when compared using the SameValue algorithm (9.12).
449     PropertyDescriptor current;
450     entryInMap->get(current);
451     if (descriptor.isEmpty() || descriptor.equalTo(exec, current))
452         return true;
453
454     // 7. If the [[Configurable]] field of current is false then
455     if (!current.configurable()) {
456         // 7.a. Reject, if the [[Configurable]] field of Desc is true.
457         if (descriptor.configurablePresent() && descriptor.configurable())
458             return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property.");
459         // 7.b. Reject, if the [[Enumerable]] field of Desc is present and the [[Enumerable]] fields of current and Desc are the Boolean negation of each other.
460         if (descriptor.enumerablePresent() && current.enumerable() != descriptor.enumerable())
461             return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property.");
462     }
463
464     // 8. If IsGenericDescriptor(Desc) is true, then no further validation is required.
465     if (!descriptor.isGenericDescriptor()) {
466         // 9. Else, if IsDataDescriptor(current) and IsDataDescriptor(Desc) have different results, then
467         if (current.isDataDescriptor() != descriptor.isDataDescriptor()) {
468             // 9.a. Reject, if the [[Configurable]] field of current is false.
469             if (!current.configurable())
470                 return reject(exec, throwException, "Attempting to change access mechanism for an unconfigurable property.");
471             // 9.b. If IsDataDescriptor(current) is true, then convert the property named P of object O from a
472             // data property to an accessor property. Preserve the existing values of the converted property‘s
473             // [[Configurable]] and [[Enumerable]] attributes and set the rest of the property‘s attributes to
474             // their default values.
475             // 9.c. Else, convert the property named P of object O from an accessor property to a data property.
476             // Preserve the existing values of the converted property‘s [[Configurable]] and [[Enumerable]]
477             // attributes and set the rest of the property‘s attributes to their default values.
478         } else if (current.isDataDescriptor() && descriptor.isDataDescriptor()) {
479             // 10. Else, if IsDataDescriptor(current) and IsDataDescriptor(Desc) are both true, then
480             // 10.a. If the [[Configurable]] field of current is false, then
481             if (!current.configurable() && !current.writable()) {
482                 // 10.a.i. Reject, if the [[Writable]] field of current is false and the [[Writable]] field of Desc is true.
483                 if (descriptor.writable())
484                     return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property.");
485                 // 10.a.ii. If the [[Writable]] field of current is false, then
486                 // 10.a.ii.1. Reject, if the [[Value]] field of Desc is present and SameValue(Desc.[[Value]], current.[[Value]]) is false.
487                 if (descriptor.value() && !sameValue(exec, descriptor.value(), current.value()))
488                     return reject(exec, throwException, "Attempting to change value of a readonly property.");
489             }
490             // 10.b. else, the [[Configurable]] field of current is true, so any change is acceptable.
491         } else {
492             ASSERT(current.isAccessorDescriptor() && current.getterPresent() && current.setterPresent());
493             // 11. Else, IsAccessorDescriptor(current) and IsAccessorDescriptor(Desc) are both true so, if the [[Configurable]] field of current is false, then
494             if (!current.configurable()) {
495                 // 11.i. Reject, if the [[Set]] field of Desc is present and SameValue(Desc.[[Set]], current.[[Set]]) is false.
496                 if (descriptor.setterPresent() && descriptor.setter() != current.setter())
497                     return reject(exec, throwException, "Attempting to change the setter of an unconfigurable property.");
498                 // 11.ii. Reject, if the [[Get]] field of Desc is present and SameValue(Desc.[[Get]], current.[[Get]]) is false.
499                 if (descriptor.getterPresent() && descriptor.getter() != current.getter())
500                     return reject(exec, throwException, "Attempting to change the getter of an unconfigurable property.");
501             }
502         }
503     }
504
505     // 12. For each attribute field of Desc that is present, set the correspondingly named attribute of the property named P of object O to the value of the field.
506     putDescriptor(exec, entryInMap, descriptor, current);
507     // 13. Return true.
508     return true;
509 }
510
511 void JSArray::setLengthWritable(ExecState* exec, bool writable)
512 {
513     ASSERT(isLengthWritable() || !writable);
514     if (!isLengthWritable() || writable)
515         return;
516
517     enterDictionaryMode(exec->globalData());
518
519     SparseArrayValueMap* map = m_sparseValueMap;
520     ASSERT(map);
521     map->setLengthIsReadOnly();
522 }
523
524 // Defined in ES5.1 15.4.5.1
525 bool JSArray::defineOwnProperty(JSObject* object, ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor, bool throwException)
526 {
527     JSArray* array = static_cast<JSArray*>(object);
528
529     // 3. If P is "length", then
530     if (propertyName == exec->propertyNames().length) {
531         // All paths through length definition call the default [[DefineOwnProperty]], hence:
532         // from ES5.1 8.12.9 7.a.
533         if (descriptor.configurablePresent() && descriptor.configurable())
534             return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property.");
535         // from ES5.1 8.12.9 7.b.
536         if (descriptor.enumerablePresent() && descriptor.enumerable())
537             return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property.");
538
539         // a. If the [[Value]] field of Desc is absent, then
540         // a.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", Desc, and Throw as arguments.
541         if (descriptor.isAccessorDescriptor())
542             return reject(exec, throwException, "Attempting to change access mechanism for an unconfigurable property.");
543         // from ES5.1 8.12.9 10.a.
544         if (!array->isLengthWritable() && descriptor.writablePresent() && descriptor.writable())
545             return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property.");
546         // This descriptor is either just making length read-only, or changing nothing!
547         if (!descriptor.value()) {
548             if (descriptor.writablePresent())
549                 array->setLengthWritable(exec, descriptor.writable());
550             return true;
551         }
552         
553         // b. Let newLenDesc be a copy of Desc.
554         // c. Let newLen be ToUint32(Desc.[[Value]]).
555         unsigned newLen = descriptor.value().toUInt32(exec);
556         // d. If newLen is not equal to ToNumber( Desc.[[Value]]), throw a RangeError exception.
557         if (newLen != descriptor.value().toNumber(exec)) {
558             throwError(exec, createRangeError(exec, "Invalid array length"));
559             return false;
560         }
561
562         // Based on SameValue check in 8.12.9, this is always okay.
563         if (newLen == array->length()) {
564             if (descriptor.writablePresent())
565                 array->setLengthWritable(exec, descriptor.writable());
566             return true;
567         }
568
569         // e. Set newLenDesc.[[Value] to newLen.
570         // f. If newLen >= oldLen, then
571         // f.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments.
572         // g. Reject if oldLenDesc.[[Writable]] is false.
573         if (!array->isLengthWritable())
574             return reject(exec, throwException, "Attempting to change value of a readonly property.");
575         
576         // h. If newLenDesc.[[Writable]] is absent or has the value true, let newWritable be true.
577         // i. Else,
578         // i.i. Need to defer setting the [[Writable]] attribute to false in case any elements cannot be deleted.
579         // i.ii. Let newWritable be false.
580         // i.iii. Set newLenDesc.[[Writable] to true.
581         // 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.
582         // k. If succeeded is false, return false.
583         // l. While newLen < oldLen repeat,
584         // l.i. Set oldLen to oldLen – 1.
585         // l.ii. Let deleteSucceeded be the result of calling the [[Delete]] internal method of A passing ToString(oldLen) and false as arguments.
586         // l.iii. If deleteSucceeded is false, then
587         if (!array->setLength(exec, newLen, throwException)) {
588             // 1. Set newLenDesc.[[Value] to oldLen+1.
589             // 2. If newWritable is false, set newLenDesc.[[Writable] to false.
590             // 3. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and false as arguments.
591             // 4. Reject.
592             if (descriptor.writablePresent())
593                 array->setLengthWritable(exec, descriptor.writable());
594             return false;
595         }
596
597         // m. If newWritable is false, then
598         // i. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length",
599         //    Property Descriptor{[[Writable]]: false}, and false as arguments. This call will always
600         //    return true.
601         if (descriptor.writablePresent())
602             array->setLengthWritable(exec, descriptor.writable());
603         // n. Return true.
604         return true;
605     }
606
607     // 4. Else if P is an array index (15.4), then
608     bool isArrayIndex;
609     // a. Let index be ToUint32(P).
610     unsigned index = propertyName.toArrayIndex(isArrayIndex);
611     if (isArrayIndex) {
612         // b. Reject if index >= oldLen and oldLenDesc.[[Writable]] is false.
613         if (index >= array->length() && !array->isLengthWritable())
614             return reject(exec, throwException, "Attempting to define numeric property on array with non-writable length property.");
615         // 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.
616         // d. Reject if succeeded is false.
617         // e. If index >= oldLen
618         // e.i. Set oldLenDesc.[[Value]] to index + 1.
619         // 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.
620         // f. Return true.
621         return array->defineOwnNumericProperty(exec, index, descriptor, throwException);
622     }
623
624     return JSObject::defineOwnProperty(object, exec, propertyName, descriptor, throwException);
625 }
626
627 bool JSArray::getOwnPropertySlotByIndex(JSCell* cell, ExecState* exec, unsigned i, PropertySlot& slot)
628 {
629     JSArray* thisObject = jsCast<JSArray*>(cell);
630     ArrayStorage* storage = thisObject->m_storage;
631
632     if (i >= storage->m_length) {
633         if (i > MAX_ARRAY_INDEX)
634             return thisObject->methodTable()->getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
635         return false;
636     }
637
638     if (i < thisObject->m_vectorLength) {
639         JSValue value = storage->m_vector[i].get();
640         if (value) {
641             slot.setValue(value);
642             return true;
643         }
644     } else if (SparseArrayValueMap* map = thisObject->m_sparseValueMap) {
645         SparseArrayValueMap::iterator it = map->find(i);
646         if (it != map->notFound()) {
647             it->second.get(slot);
648             return true;
649         }
650     }
651
652     return JSObject::getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
653 }
654
655 bool JSArray::getOwnPropertySlot(JSCell* cell, ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
656 {
657     JSArray* thisObject = jsCast<JSArray*>(cell);
658     if (propertyName == exec->propertyNames().length) {
659         slot.setValue(jsNumber(thisObject->length()));
660         return true;
661     }
662
663     bool isArrayIndex;
664     unsigned i = propertyName.toArrayIndex(isArrayIndex);
665     if (isArrayIndex)
666         return JSArray::getOwnPropertySlotByIndex(thisObject, exec, i, slot);
667
668     return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
669 }
670
671 bool JSArray::getOwnPropertyDescriptor(JSObject* object, ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
672 {
673     JSArray* thisObject = jsCast<JSArray*>(object);
674     if (propertyName == exec->propertyNames().length) {
675         descriptor.setDescriptor(jsNumber(thisObject->length()), thisObject->isLengthWritable() ? DontDelete | DontEnum : DontDelete | DontEnum | ReadOnly);
676         return true;
677     }
678
679     ArrayStorage* storage = thisObject->m_storage;
680     
681     bool isArrayIndex;
682     unsigned i = propertyName.toArrayIndex(isArrayIndex);
683     if (isArrayIndex) {
684         if (i >= storage->m_length)
685             return false;
686         if (i < thisObject->m_vectorLength) {
687             WriteBarrier<Unknown>& value = storage->m_vector[i];
688             if (value) {
689                 descriptor.setDescriptor(value.get(), 0);
690                 return true;
691             }
692         } else if (SparseArrayValueMap* map = thisObject->m_sparseValueMap) {
693             SparseArrayValueMap::iterator it = map->find(i);
694             if (it != map->notFound()) {
695                 it->second.get(descriptor);
696                 return true;
697             }
698         }
699     }
700     return JSObject::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor);
701 }
702
703 // ECMA 15.4.5.1
704 void JSArray::put(JSCell* cell, ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
705 {
706     JSArray* thisObject = jsCast<JSArray*>(cell);
707     bool isArrayIndex;
708     unsigned i = propertyName.toArrayIndex(isArrayIndex);
709     if (isArrayIndex) {
710         putByIndex(thisObject, exec, i, value);
711         return;
712     }
713
714     if (propertyName == exec->propertyNames().length) {
715         unsigned newLength = value.toUInt32(exec);
716         if (value.toNumber(exec) != static_cast<double>(newLength)) {
717             throwError(exec, createRangeError(exec, "Invalid array length"));
718             return;
719         }
720         thisObject->setLength(exec, newLength, slot.isStrictMode());
721         return;
722     }
723
724     JSObject::put(thisObject, exec, propertyName, value, slot);
725 }
726
727 void JSArray::putByIndex(JSCell* cell, ExecState* exec, unsigned i, JSValue value)
728 {
729     JSArray* thisObject = jsCast<JSArray*>(cell);
730     thisObject->checkConsistency();
731
732     ArrayStorage* storage = thisObject->m_storage;
733
734     // Fast case - store to the vector.
735     if (i < thisObject->m_vectorLength) {
736         WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
737         unsigned length = storage->m_length;
738
739         // Update m_length & m_numValuesInVector as necessary.
740         if (i >= length) {
741             length = i + 1;
742             storage->m_length = length;
743             ++storage->m_numValuesInVector;
744         } else if (!valueSlot)
745             ++storage->m_numValuesInVector;
746
747         valueSlot.set(exec->globalData(), thisObject, value);
748         thisObject->checkConsistency();
749         return;
750     }
751
752     // Handle 2^32-1 - this is not an array index (see ES5.1 15.4), and is treated as a regular property.
753     if (UNLIKELY(i > MAX_ARRAY_INDEX)) {
754         PutPropertySlot slot;
755         thisObject->methodTable()->put(thisObject, exec, Identifier::from(exec, i), value, slot);
756         return;
757     }
758
759     // For all other cases, call putByIndexBeyondVectorLength.
760     thisObject->putByIndexBeyondVectorLength(exec, i, value);
761     thisObject->checkConsistency();
762 }
763
764 NEVER_INLINE void JSArray::putByIndexBeyondVectorLength(ExecState* exec, unsigned i, JSValue value)
765 {
766     JSGlobalData& globalData = exec->globalData();
767
768     // i should be a valid array index that is outside of the current vector.
769     ASSERT(i >= m_vectorLength);
770     ASSERT(i <= MAX_ARRAY_INDEX);
771
772     ArrayStorage* storage = m_storage;
773     SparseArrayValueMap* map = m_sparseValueMap;
774
775     // First, handle cases where we don't currently have a sparse map.
776     if (LIKELY(!map)) {
777         // If the array is not extensible, we should have entered dictionary mode, and created the spare map.
778         ASSERT(isExtensible());
779     
780         // Update m_length if necessary.
781         if (i >= storage->m_length)
782             storage->m_length = i + 1;
783
784         // Check that it is sensible to still be using a vector, and then try to grow the vector.
785         if (LIKELY((isDenseEnoughForVector(i, storage->m_numValuesInVector)) && increaseVectorLength(globalData, i + 1))) {
786             // success! - reread m_storage since it has likely been reallocated, and store to the vector.
787             storage = m_storage;
788             storage->m_vector[i].set(globalData, this, value);
789             ++storage->m_numValuesInVector;
790             return;
791         }
792         // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
793         allocateSparseMap(exec->globalData());
794         map = m_sparseValueMap;
795         map->put(exec, this, i, value);
796         return;
797     }
798
799     // Update m_length if necessary.
800     unsigned length = storage->m_length;
801     if (i >= length) {
802         // Prohibit growing the array if length is not writable.
803         if (map->lengthIsReadOnly() || !isExtensible()) {
804             // FIXME: should throw in strict mode.
805             return;
806         }
807         length = i + 1;
808         storage->m_length = length;
809     }
810
811     // We are currently using a map - check whether we still want to be doing so.
812     // We will continue  to use a sparse map if SparseMode is set, a vector would be too sparse, or if allocation fails.
813     unsigned numValuesInArray = storage->m_numValuesInVector + map->size();
814     if (map->sparseMode() || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(exec->globalData(), length)) {
815         map->put(exec, this, i, value);
816         return;
817     }
818
819     // Reread m_storage afterincreaseVectorLength, update m_numValuesInVector.
820     storage = m_storage;
821     storage->m_numValuesInVector = numValuesInArray;
822
823     // Copy all values from the map into the vector, and delete the map.
824     WriteBarrier<Unknown>* vector = storage->m_vector;
825     SparseArrayValueMap::const_iterator end = map->end();
826     for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
827         vector[it->first].set(globalData, this, it->second.getNonSparseMode());
828     deallocateSparseMap();
829
830     // Store the new property into the vector.
831     WriteBarrier<Unknown>& valueSlot = vector[i];
832     if (!valueSlot)
833         ++storage->m_numValuesInVector;
834     valueSlot.set(globalData, this, value);
835 }
836
837 bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, const Identifier& propertyName)
838 {
839     JSArray* thisObject = jsCast<JSArray*>(cell);
840     bool isArrayIndex;
841     unsigned i = propertyName.toArrayIndex(isArrayIndex);
842     if (isArrayIndex)
843         return thisObject->methodTable()->deletePropertyByIndex(thisObject, exec, i);
844
845     if (propertyName == exec->propertyNames().length)
846         return false;
847
848     return JSObject::deleteProperty(thisObject, exec, propertyName);
849 }
850
851 bool JSArray::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
852 {
853     JSArray* thisObject = jsCast<JSArray*>(cell);
854     thisObject->checkConsistency();
855
856     if (i > MAX_ARRAY_INDEX)
857         return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, i));
858
859     ArrayStorage* storage = thisObject->m_storage;
860     
861     if (i < thisObject->m_vectorLength) {
862         WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
863         if (valueSlot) {
864             valueSlot.clear();
865             --storage->m_numValuesInVector;
866         }
867     } else if (SparseArrayValueMap* map = thisObject->m_sparseValueMap) {
868         SparseArrayValueMap::iterator it = map->find(i);
869         if (it != map->notFound()) {
870             if (it->second.attributes & DontDelete)
871                 return false;
872             map->remove(it);
873         }
874     }
875
876     thisObject->checkConsistency();
877     return true;
878 }
879
880 static int compareKeysForQSort(const void* a, const void* b)
881 {
882     unsigned da = *static_cast<const unsigned*>(a);
883     unsigned db = *static_cast<const unsigned*>(b);
884     return (da > db) - (da < db);
885 }
886
887 void JSArray::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
888 {
889     JSArray* thisObject = jsCast<JSArray*>(object);
890     // FIXME: Filling PropertyNameArray with an identifier for every integer
891     // is incredibly inefficient for large arrays. We need a different approach,
892     // which almost certainly means a different structure for PropertyNameArray.
893
894     ArrayStorage* storage = thisObject->m_storage;
895     
896     unsigned usedVectorLength = min(storage->m_length, thisObject->m_vectorLength);
897     for (unsigned i = 0; i < usedVectorLength; ++i) {
898         if (storage->m_vector[i])
899             propertyNames.add(Identifier::from(exec, i));
900     }
901
902     if (SparseArrayValueMap* map = thisObject->m_sparseValueMap) {
903         Vector<unsigned> keys;
904         keys.reserveCapacity(map->size());
905         
906         SparseArrayValueMap::const_iterator end = map->end();
907         for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
908             if (mode == IncludeDontEnumProperties || !(it->second.attributes & DontEnum))
909                 keys.append(static_cast<unsigned>(it->first));
910         }
911
912         qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
913         for (unsigned i = 0; i < keys.size(); ++i)
914             propertyNames.add(Identifier::from(exec, keys[i]));
915     }
916
917     if (mode == IncludeDontEnumProperties)
918         propertyNames.add(exec->propertyNames().length);
919
920     JSObject::getOwnPropertyNames(thisObject, exec, propertyNames, mode);
921 }
922
923 ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
924 {
925     ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);
926
927     unsigned increasedLength;
928     unsigned maxInitLength = min(m_storage->m_length, 100000U);
929
930     if (desiredLength < maxInitLength)
931         increasedLength = maxInitLength;
932     else if (!m_vectorLength)
933         increasedLength = max(desiredLength, lastArraySize);
934     else {
935         // Mathematically equivalent to:
936         //   increasedLength = (newLength * 3 + 1) / 2;
937         // or:
938         //   increasedLength = (unsigned)ceil(newLength * 1.5));
939         // This form is not prone to internal overflow.
940         increasedLength = desiredLength + (desiredLength >> 1) + (desiredLength & 1);
941     }
942
943     ASSERT(increasedLength >= desiredLength);
944
945     lastArraySize = min(increasedLength, FIRST_VECTOR_GROW);
946
947     return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
948 }
949
950 bool JSArray::increaseVectorLength(JSGlobalData& globalData, unsigned newLength)
951 {
952     // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
953     // to the vector. Callers have to account for that, because they can do it more efficiently.
954     if (newLength > MAX_STORAGE_VECTOR_LENGTH)
955         return false;
956
957     ArrayStorage* storage = m_storage;
958
959     unsigned vectorLength = m_vectorLength;
960     ASSERT(newLength > vectorLength);
961     unsigned newVectorLength = getNewVectorLength(newLength);
962
963     // Fast case - there is no precapacity. In these cases a realloc makes sense.
964     if (LIKELY(!m_indexBias)) {
965         void* newStorage = storage->m_allocBase;
966         if (!globalData.heap.tryReallocateStorage(&newStorage, storageSize(vectorLength), storageSize(newVectorLength)))
967             return false;
968
969         storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(newStorage));
970         m_storage->m_allocBase = newStorage;
971         ASSERT(m_storage->m_allocBase);
972
973         m_vectorLength = newVectorLength;
974         
975         return true;
976     }
977
978     // Remove some, but not all of the precapacity. Atomic decay, & capped to not overflow array length.
979     unsigned newIndexBias = min(m_indexBias >> 1, MAX_STORAGE_VECTOR_LENGTH - newVectorLength);
980     // Calculate new stoarge capcity, allowing room for the pre-capacity.
981     unsigned newStorageCapacity = newVectorLength + newIndexBias;
982     void* newAllocBase = 0;
983     if (!globalData.heap.tryAllocateStorage(storageSize(newStorageCapacity), &newAllocBase))    
984         return false;
985     // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH.
986     ASSERT(m_vectorLength <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - m_vectorLength) >= m_indexBias);
987
988     m_vectorLength = newVectorLength;
989     m_indexBias = newIndexBias;
990     m_storage = reinterpret_cast_ptr<ArrayStorage*>(reinterpret_cast<WriteBarrier<Unknown>*>(newAllocBase) + m_indexBias);
991
992     // Copy the ArrayStorage header & current contents of the vector.
993     memmove(m_storage, storage, storageSize(vectorLength));
994
995     // Free the old allocation, update m_allocBase.
996     m_storage->m_allocBase = newAllocBase;
997
998     return true;
999 }
1000
1001 // This method makes room in the vector, but leaves the new space uncleared.
1002 bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, unsigned count)
1003 {
1004     // If not, we should have handled this on the fast path.
1005     ASSERT(count > m_indexBias);
1006
1007     ArrayStorage* storage = m_storage;
1008
1009     // Step 1:
1010     // Gather 4 key metrics:
1011     //  * usedVectorLength - how many entries are currently in the vector (conservative estimate - fewer may be in use in sparse vectors).
1012     //  * requiredVectorLength - how many entries are will there be in the vector, after allocating space for 'count' more.
1013     //  * currentCapacity - what is the current size of the vector, including any pre-capacity.
1014     //  * desiredCapacity - how large should we like to grow the vector to - based on 2x requiredVectorLength.
1015
1016     unsigned length = storage->m_length;
1017     unsigned usedVectorLength = min(m_vectorLength, length);
1018     ASSERT(usedVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
1019     // Check that required vector length is possible, in an overflow-safe fashion.
1020     if (count > MAX_STORAGE_VECTOR_LENGTH - usedVectorLength)
1021         return false;
1022     unsigned requiredVectorLength = usedVectorLength + count;
1023     ASSERT(requiredVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
1024     // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH.
1025     ASSERT(m_vectorLength <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - m_vectorLength) >= m_indexBias);
1026     unsigned currentCapacity = m_vectorLength + m_indexBias;
1027     // The calculation of desiredCapacity won't overflow, due to the range of MAX_STORAGE_VECTOR_LENGTH.
1028     unsigned desiredCapacity = min(MAX_STORAGE_VECTOR_LENGTH, max(BASE_VECTOR_LEN, requiredVectorLength) << 1);
1029
1030     // Step 2:
1031     // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing on.
1032
1033     void* newAllocBase = 0;
1034     unsigned newStorageCapacity;
1035     // If the current storage array is sufficiently large (but not too large!) then just keep using it.
1036     if (currentCapacity > desiredCapacity && isDenseEnoughForVector(currentCapacity, requiredVectorLength)) {
1037         newAllocBase = storage->m_allocBase;
1038         newStorageCapacity = currentCapacity;
1039     } else {
1040         if (!globalData.heap.tryAllocateStorage(storageSize(desiredCapacity), &newAllocBase))
1041             return false;
1042         newStorageCapacity = desiredCapacity;
1043     }
1044
1045     // Step 3:
1046     // Work out where we're going to move things to.
1047
1048     // Determine how much of the vector to use as pre-capacity, and how much as post-capacity.
1049     // If the vector had no free post-capacity (length >= m_vectorLength), don't give it any.
1050     // If it did, we calculate the amount that will remain based on an atomic decay - leave the
1051     // vector with half the post-capacity it had previously.
1052     unsigned postCapacity = 0;
1053     if (length < m_vectorLength) {
1054         // Atomic decay, + the post-capacity cannot be greater than what is available.
1055         postCapacity = min((m_vectorLength - length) >> 1, newStorageCapacity - requiredVectorLength);
1056         // If we're moving contents within the same allocation, the post-capacity is being reduced.
1057         ASSERT(newAllocBase != storage->m_allocBase || postCapacity < m_vectorLength - length);
1058     }
1059
1060     m_vectorLength = requiredVectorLength + postCapacity;
1061     m_indexBias = newStorageCapacity - m_vectorLength;
1062     m_storage = reinterpret_cast_ptr<ArrayStorage*>(reinterpret_cast<WriteBarrier<Unknown>*>(newAllocBase) + m_indexBias);
1063
1064     // Step 4:
1065     // Copy array data / header into their new locations, clear post-capacity & free any old allocation.
1066
1067     // If this is being moved within the existing buffer of memory, we are always shifting data
1068     // to the right (since count > m_indexBias). As such this memmove cannot trample the header.
1069     memmove(m_storage->m_vector + count, storage->m_vector, sizeof(WriteBarrier<Unknown>) * usedVectorLength);
1070     memmove(m_storage, storage, storageSize(0));
1071
1072     // Are we copying into a new allocation?
1073     if (newAllocBase != m_storage->m_allocBase) {
1074         // Free the old allocation, update m_allocBase.
1075         m_storage->m_allocBase = newAllocBase;
1076     }
1077
1078     return true;
1079 }
1080
1081 bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
1082 {
1083     checkConsistency();
1084
1085     ArrayStorage* storage = m_storage;
1086     unsigned length = storage->m_length;
1087
1088     // If the length is read only then we enter sparse mode, so should enter the following 'if'.
1089     ASSERT(isLengthWritable() || m_sparseValueMap);
1090
1091     if (SparseArrayValueMap* map = m_sparseValueMap) {
1092         // Fail if the length is not writable.
1093         if (map->lengthIsReadOnly())
1094             return reject(exec, throwException, StrictModeReadonlyPropertyWriteError);
1095
1096         if (newLength < length) {
1097             // Copy any keys we might be interested in into a vector.
1098             Vector<unsigned> keys;
1099             keys.reserveCapacity(min(map->size(), static_cast<size_t>(length - newLength)));
1100             SparseArrayValueMap::const_iterator end = map->end();
1101             for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
1102                 unsigned index = static_cast<unsigned>(it->first);
1103                 if (index < length && index >= newLength)
1104                     keys.append(index);
1105             }
1106
1107             // Check if the array is in sparse mode. If so there may be non-configurable
1108             // properties, so we have to perform deletion with caution, if not we can
1109             // delete values in any order.
1110             if (map->sparseMode()) {
1111                 qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
1112                 unsigned i = keys.size();
1113                 while (i) {
1114                     unsigned index = keys[--i];
1115                     SparseArrayValueMap::iterator it = map->find(index);
1116                     ASSERT(it != map->notFound());
1117                     if (it->second.attributes & DontDelete) {
1118                         storage->m_length = index + 1;
1119                         return reject(exec, throwException, "Unable to delete property.");
1120                     }
1121                     map->remove(it);
1122                 }
1123             } else {
1124                 for (unsigned i = 0; i < keys.size(); ++i)
1125                     map->remove(keys[i]);
1126                 if (map->isEmpty())
1127                     deallocateSparseMap();
1128             }
1129         }
1130     }
1131
1132     if (newLength < length) {
1133         // Delete properties from the vector.
1134         unsigned usedVectorLength = min(length, m_vectorLength);
1135         for (unsigned i = newLength; i < usedVectorLength; ++i) {
1136             WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
1137             bool hadValue = valueSlot;
1138             valueSlot.clear();
1139             storage->m_numValuesInVector -= hadValue;
1140         }
1141     }
1142
1143     storage->m_length = newLength;
1144
1145     checkConsistency();
1146     return true;
1147 }
1148
1149 JSValue JSArray::pop(ExecState* exec)
1150 {
1151     checkConsistency();
1152     ArrayStorage* storage = m_storage;
1153     
1154     unsigned length = storage->m_length;
1155     if (!length) {
1156         if (!isLengthWritable())
1157             throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
1158         return jsUndefined();
1159     }
1160
1161     unsigned index = length - 1;
1162     if (index < m_vectorLength) {
1163         WriteBarrier<Unknown>& valueSlot = storage->m_vector[index];
1164         if (valueSlot) {
1165             --storage->m_numValuesInVector;
1166             JSValue element = valueSlot.get();
1167             valueSlot.clear();
1168             
1169             ASSERT(isLengthWritable());
1170             storage->m_length = index;
1171             checkConsistency();
1172             return element;
1173         }
1174     }
1175
1176     // Let element be the result of calling the [[Get]] internal method of O with argument indx.
1177     JSValue element = get(exec, index);
1178     if (exec->hadException())
1179         return jsUndefined();
1180     // Call the [[Delete]] internal method of O with arguments indx and true.
1181     deletePropertyByIndex(this, exec, index);
1182     // Call the [[Put]] internal method of O with arguments "length", indx, and true.
1183     setLength(exec, index, true);
1184     // Return element.
1185     checkConsistency();
1186     return element;
1187 }
1188
1189 // Push & putIndex are almost identical, with two small differences.
1190 //  - we always are writing beyond the current array bounds, so it is always necessary to update m_length & m_numValuesInVector.
1191 //  - pushing to an array of length 2^32-1 stores the property, but throws a range error.
1192 void JSArray::push(ExecState* exec, JSValue value)
1193 {
1194     checkConsistency();
1195     ArrayStorage* storage = m_storage;
1196
1197     // Fast case - push within vector, always update m_length & m_numValuesInVector.
1198     unsigned length = storage->m_length;
1199     if (length < m_vectorLength) {
1200         storage->m_vector[length].set(exec->globalData(), this, value);
1201         storage->m_length = length + 1;
1202         ++storage->m_numValuesInVector;
1203         checkConsistency();
1204         return;
1205     }
1206
1207     // Pushing to an array of length 2^32-1 stores the property, but throws a range error.
1208     if (UNLIKELY(storage->m_length == 0xFFFFFFFFu)) {
1209         methodTable()->putByIndex(this, exec, storage->m_length, value);
1210         // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d.
1211         throwError(exec, createRangeError(exec, "Invalid array length"));
1212         return;
1213     }
1214
1215     // Handled the same as putIndex.
1216     putByIndexBeyondVectorLength(exec, storage->m_length, value);
1217     checkConsistency();
1218 }
1219
1220 void JSArray::shiftCount(ExecState* exec, unsigned count)
1221 {
1222     ASSERT(count > 0);
1223     
1224     ArrayStorage* storage = m_storage;
1225     
1226     unsigned oldLength = storage->m_length;
1227     
1228     if (!oldLength)
1229         return;
1230     
1231     if (oldLength != storage->m_numValuesInVector) {
1232         // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
1233         // which means we need to go through each entry looking for the the "empty"
1234         // slots and then fill them with possible properties.  See ECMA spec.
1235         // 15.4.4.9 steps 11 through 13.
1236         for (unsigned i = count; i < oldLength; ++i) {
1237             if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
1238                 PropertySlot slot(this);
1239                 JSValue p = prototype();
1240                 if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
1241                     methodTable()->putByIndex(this, exec, i, slot.getValue(exec, i));
1242             }
1243         }
1244
1245         storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
1246
1247         // Need to decrement numValuesInvector based on number of real entries
1248         for (unsigned i = 0; i < (unsigned)count; ++i)
1249             if ((i < m_vectorLength) && (storage->m_vector[i]))
1250                 --storage->m_numValuesInVector;
1251     } else
1252         storage->m_numValuesInVector -= count;
1253     
1254     storage->m_length -= count;
1255     
1256     if (m_vectorLength) {
1257         count = min(m_vectorLength, (unsigned)count);
1258         
1259         m_vectorLength -= count;
1260         
1261         if (m_vectorLength) {
1262             char* newBaseStorage = reinterpret_cast<char*>(storage) + count * sizeof(WriteBarrier<Unknown>);
1263             memmove(newBaseStorage, storage, storageSize(0));
1264             m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
1265
1266             m_indexBias += count;
1267         }
1268     }
1269 }
1270     
1271 void JSArray::unshiftCount(ExecState* exec, unsigned count)
1272 {
1273     ArrayStorage* storage = m_storage;
1274     unsigned length = storage->m_length;
1275
1276     if (length != storage->m_numValuesInVector) {
1277         // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
1278         // which means we need to go through each entry looking for the the "empty"
1279         // slots and then fill them with possible properties.  See ECMA spec.
1280         // 15.4.4.13 steps 8 through 10.
1281         for (unsigned i = 0; i < length; ++i) {
1282             if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
1283                 PropertySlot slot(this);
1284                 JSValue p = prototype();
1285                 if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
1286                     methodTable()->putByIndex(this, exec, i, slot.getValue(exec, i));
1287             }
1288         }
1289     }
1290     
1291     storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
1292     
1293     if (m_indexBias >= count) {
1294         m_indexBias -= count;
1295         char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(WriteBarrier<Unknown>);
1296         memmove(newBaseStorage, storage, storageSize(0));
1297         m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
1298         m_vectorLength += count;
1299     } else if (!unshiftCountSlowCase(exec->globalData(), count)) {
1300         throwOutOfMemoryError(exec);
1301         return;
1302     }
1303
1304     WriteBarrier<Unknown>* vector = m_storage->m_vector;
1305     for (unsigned i = 0; i < count; i++)
1306         vector[i].clear();
1307 }
1308
1309 void JSArray::visitChildren(JSCell* cell, SlotVisitor& visitor)
1310 {
1311     JSArray* thisObject = jsCast<JSArray*>(cell);
1312     ASSERT_GC_OBJECT_INHERITS(thisObject, &s_info);
1313     COMPILE_ASSERT(StructureFlags & OverridesVisitChildren, OverridesVisitChildrenWithoutSettingFlag);
1314     ASSERT(thisObject->structure()->typeInfo().overridesVisitChildren());
1315
1316     JSNonFinalObject::visitChildren(thisObject, visitor);
1317
1318     if (thisObject->m_storage) {
1319         ArrayStorage* storage = thisObject->m_storage;
1320         void* baseStorage = storage->m_allocBase;
1321
1322         visitor.copyAndAppend(reinterpret_cast<void**>(&baseStorage), storageSize(thisObject->m_vectorLength + thisObject->m_indexBias), storage->m_vector->slot(), thisObject->m_vectorLength);
1323
1324         if (baseStorage != thisObject->m_storage->m_allocBase) {
1325             thisObject->m_storage = reinterpret_cast<ArrayStorage*>(static_cast<char*>(baseStorage) + sizeof(JSValue) * thisObject->m_indexBias);
1326             thisObject->m_storage->m_allocBase = baseStorage;
1327             ASSERT(thisObject->m_storage->m_allocBase);
1328         }
1329     }
1330
1331     if (SparseArrayValueMap* map = thisObject->m_sparseValueMap)
1332         map->visitChildren(visitor);
1333 }
1334
1335 static int compareNumbersForQSort(const void* a, const void* b)
1336 {
1337     double da = static_cast<const JSValue*>(a)->asNumber();
1338     double db = static_cast<const JSValue*>(b)->asNumber();
1339     return (da > db) - (da < db);
1340 }
1341
1342 static int compareByStringPairForQSort(const void* a, const void* b)
1343 {
1344     const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
1345     const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
1346     return codePointCompare(va->second, vb->second);
1347 }
1348
1349 void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
1350 {
1351     ASSERT(!inSparseMode());
1352
1353     ArrayStorage* storage = m_storage;
1354
1355     unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
1356     if (m_sparseValueMap) {
1357         throwOutOfMemoryError(exec);
1358         return;
1359     }
1360
1361     if (!lengthNotIncludingUndefined)
1362         return;
1363         
1364     bool allValuesAreNumbers = true;
1365     size_t size = storage->m_numValuesInVector;
1366     for (size_t i = 0; i < size; ++i) {
1367         if (!storage->m_vector[i].isNumber()) {
1368             allValuesAreNumbers = false;
1369             break;
1370         }
1371     }
1372
1373     if (!allValuesAreNumbers)
1374         return sort(exec, compareFunction, callType, callData);
1375
1376     // For numeric comparison, which is fast, qsort is faster than mergesort. We
1377     // also don't require mergesort's stability, since there's no user visible
1378     // side-effect from swapping the order of equal primitive values.
1379     qsort(storage->m_vector, size, sizeof(WriteBarrier<Unknown>), compareNumbersForQSort);
1380
1381     checkConsistency(SortConsistencyCheck);
1382 }
1383
1384 void JSArray::sort(ExecState* exec)
1385 {
1386     ASSERT(!inSparseMode());
1387
1388     unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
1389     if (m_sparseValueMap) {
1390         throwOutOfMemoryError(exec);
1391         return;
1392     }
1393
1394     if (!lengthNotIncludingUndefined)
1395         return;
1396
1397     // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
1398     // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
1399     // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
1400     // random or otherwise changing results, effectively making compare function inconsistent.
1401
1402     Vector<ValueStringPair> values(lengthNotIncludingUndefined);
1403     if (!values.begin()) {
1404         throwOutOfMemoryError(exec);
1405         return;
1406     }
1407     
1408     Heap::heap(this)->pushTempSortVector(&values);
1409
1410     for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
1411         JSValue value = m_storage->m_vector[i].get();
1412         ASSERT(!value.isUndefined());
1413         values[i].first = value;
1414     }
1415
1416     // FIXME: The following loop continues to call toString on subsequent values even after
1417     // a toString call raises an exception.
1418
1419     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
1420         values[i].second = values[i].first.toString(exec)->value(exec);
1421
1422     if (exec->hadException()) {
1423         Heap::heap(this)->popTempSortVector(&values);
1424         return;
1425     }
1426
1427     // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
1428     // than O(N log N).
1429
1430 #if HAVE(MERGESORT)
1431     mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
1432 #else
1433     // FIXME: The qsort library function is likely to not be a stable sort.
1434     // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
1435     qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
1436 #endif
1437
1438     // If the toString function changed the length of the array or vector storage,
1439     // increase the length to handle the orignal number of actual values.
1440     if (m_vectorLength < lengthNotIncludingUndefined)
1441         increaseVectorLength(exec->globalData(), lengthNotIncludingUndefined);
1442     if (m_storage->m_length < lengthNotIncludingUndefined)
1443         m_storage->m_length = lengthNotIncludingUndefined;
1444
1445     JSGlobalData& globalData = exec->globalData();
1446     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
1447         m_storage->m_vector[i].set(globalData, this, values[i].first);
1448
1449     Heap::heap(this)->popTempSortVector(&values);
1450     
1451     checkConsistency(SortConsistencyCheck);
1452 }
1453
1454 struct AVLTreeNodeForArrayCompare {
1455     JSValue value;
1456
1457     // Child pointers.  The high bit of gt is robbed and used as the
1458     // balance factor sign.  The high bit of lt is robbed and used as
1459     // the magnitude of the balance factor.
1460     int32_t gt;
1461     int32_t lt;
1462 };
1463
1464 struct AVLTreeAbstractorForArrayCompare {
1465     typedef int32_t handle; // Handle is an index into m_nodes vector.
1466     typedef JSValue key;
1467     typedef int32_t size;
1468
1469     Vector<AVLTreeNodeForArrayCompare> m_nodes;
1470     ExecState* m_exec;
1471     JSValue m_compareFunction;
1472     CallType m_compareCallType;
1473     const CallData* m_compareCallData;
1474     OwnPtr<CachedCall> m_cachedCall;
1475
1476     handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
1477     void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; }
1478     handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; }
1479     void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; }
1480
1481     int get_balance_factor(handle h)
1482     {
1483         if (m_nodes[h].gt & 0x80000000)
1484             return -1;
1485         return static_cast<unsigned>(m_nodes[h].lt) >> 31;
1486     }
1487
1488     void set_balance_factor(handle h, int bf)
1489     {
1490         if (bf == 0) {
1491             m_nodes[h].lt &= 0x7FFFFFFF;
1492             m_nodes[h].gt &= 0x7FFFFFFF;
1493         } else {
1494             m_nodes[h].lt |= 0x80000000;
1495             if (bf < 0)
1496                 m_nodes[h].gt |= 0x80000000;
1497             else
1498                 m_nodes[h].gt &= 0x7FFFFFFF;
1499         }
1500     }
1501
1502     int compare_key_key(key va, key vb)
1503     {
1504         ASSERT(!va.isUndefined());
1505         ASSERT(!vb.isUndefined());
1506
1507         if (m_exec->hadException())
1508             return 1;
1509
1510         double compareResult;
1511         if (m_cachedCall) {
1512             m_cachedCall->setThis(jsUndefined());
1513             m_cachedCall->setArgument(0, va);
1514             m_cachedCall->setArgument(1, vb);
1515             compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec));
1516         } else {
1517             MarkedArgumentBuffer arguments;
1518             arguments.append(va);
1519             arguments.append(vb);
1520             compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, jsUndefined(), arguments).toNumber(m_exec);
1521         }
1522         return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
1523     }
1524
1525     int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
1526     int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }
1527
1528     static handle null() { return 0x7FFFFFFF; }
1529 };
1530
1531 void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
1532 {
1533     ASSERT(!inSparseMode());
1534
1535     checkConsistency();
1536
1537     // FIXME: This ignores exceptions raised in the compare function or in toNumber.
1538
1539     // The maximum tree depth is compiled in - but the caller is clearly up to no good
1540     // if a larger array is passed.
1541     ASSERT(m_storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
1542     if (m_storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
1543         return;
1544
1545     unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength);
1546     unsigned nodeCount = usedVectorLength + (m_sparseValueMap ? m_sparseValueMap->size() : 0);
1547
1548     if (!nodeCount)
1549         return;
1550
1551     AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
1552     tree.abstractor().m_exec = exec;
1553     tree.abstractor().m_compareFunction = compareFunction;
1554     tree.abstractor().m_compareCallType = callType;
1555     tree.abstractor().m_compareCallData = &callData;
1556     tree.abstractor().m_nodes.grow(nodeCount);
1557
1558     if (callType == CallTypeJS)
1559         tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, asFunction(compareFunction), 2));
1560
1561     if (!tree.abstractor().m_nodes.begin()) {
1562         throwOutOfMemoryError(exec);
1563         return;
1564     }
1565
1566     // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
1567     // right out from under us while we're building the tree here.
1568
1569     unsigned numDefined = 0;
1570     unsigned numUndefined = 0;
1571
1572     // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
1573     for (; numDefined < usedVectorLength; ++numDefined) {
1574         JSValue v = m_storage->m_vector[numDefined].get();
1575         if (!v || v.isUndefined())
1576             break;
1577         tree.abstractor().m_nodes[numDefined].value = v;
1578         tree.insert(numDefined);
1579     }
1580     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
1581         JSValue v = m_storage->m_vector[i].get();
1582         if (v) {
1583             if (v.isUndefined())
1584                 ++numUndefined;
1585             else {
1586                 tree.abstractor().m_nodes[numDefined].value = v;
1587                 tree.insert(numDefined);
1588                 ++numDefined;
1589             }
1590         }
1591     }
1592
1593     unsigned newUsedVectorLength = numDefined + numUndefined;
1594
1595     if (SparseArrayValueMap* map = m_sparseValueMap) {
1596         newUsedVectorLength += map->size();
1597         if (newUsedVectorLength > m_vectorLength) {
1598             // Check that it is possible to allocate an array large enough to hold all the entries.
1599             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(exec->globalData(), newUsedVectorLength)) {
1600                 throwOutOfMemoryError(exec);
1601                 return;
1602             }
1603         }
1604
1605         SparseArrayValueMap::const_iterator end = map->end();
1606         for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
1607             tree.abstractor().m_nodes[numDefined].value = it->second.getNonSparseMode();
1608             tree.insert(numDefined);
1609             ++numDefined;
1610         }
1611
1612         deallocateSparseMap();
1613     }
1614
1615     ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
1616
1617     // FIXME: If the compare function changed the length of the array, the following might be
1618     // modifying the vector incorrectly.
1619
1620     // Copy the values back into m_storage.
1621     AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
1622     iter.start_iter_least(tree);
1623     JSGlobalData& globalData = exec->globalData();
1624     for (unsigned i = 0; i < numDefined; ++i) {
1625         m_storage->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
1626         ++iter;
1627     }
1628
1629     // Put undefined values back in.
1630     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
1631         m_storage->m_vector[i].setUndefined();
1632
1633     // Ensure that unused values in the vector are zeroed out.
1634     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
1635         m_storage->m_vector[i].clear();
1636
1637     m_storage->m_numValuesInVector = newUsedVectorLength;
1638
1639     checkConsistency(SortConsistencyCheck);
1640 }
1641
1642 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
1643 {
1644     ArrayStorage* storage = m_storage;
1645
1646     WriteBarrier<Unknown>* vector = storage->m_vector;
1647     unsigned vectorEnd = min(storage->m_length, m_vectorLength);
1648     unsigned i = 0;
1649     for (; i < vectorEnd; ++i) {
1650         WriteBarrier<Unknown>& v = vector[i];
1651         if (!v)
1652             break;
1653         args.append(v.get());
1654     }
1655
1656     for (; i < storage->m_length; ++i)
1657         args.append(get(exec, i));
1658 }
1659
1660 void JSArray::copyToArguments(ExecState* exec, CallFrame* callFrame, uint32_t length)
1661 {
1662     ASSERT(length == this->length());
1663     UNUSED_PARAM(length);
1664     unsigned i = 0;
1665     WriteBarrier<Unknown>* vector = m_storage->m_vector;
1666     unsigned vectorEnd = min(length, m_vectorLength);
1667     for (; i < vectorEnd; ++i) {
1668         WriteBarrier<Unknown>& v = vector[i];
1669         if (!v)
1670             break;
1671         callFrame->setArgument(i, v.get());
1672     }
1673
1674     for (; i < length; ++i)
1675         callFrame->setArgument(i, get(exec, i));
1676 }
1677
1678 unsigned JSArray::compactForSorting(JSGlobalData& globalData)
1679 {
1680     ASSERT(!inSparseMode());
1681
1682     checkConsistency();
1683
1684     ArrayStorage* storage = m_storage;
1685
1686     unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
1687
1688     unsigned numDefined = 0;
1689     unsigned numUndefined = 0;
1690
1691     for (; numDefined < usedVectorLength; ++numDefined) {
1692         JSValue v = storage->m_vector[numDefined].get();
1693         if (!v || v.isUndefined())
1694             break;
1695     }
1696
1697     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
1698         JSValue v = storage->m_vector[i].get();
1699         if (v) {
1700             if (v.isUndefined())
1701                 ++numUndefined;
1702             else
1703                 storage->m_vector[numDefined++].setWithoutWriteBarrier(v);
1704         }
1705     }
1706
1707     unsigned newUsedVectorLength = numDefined + numUndefined;
1708
1709     if (SparseArrayValueMap* map = m_sparseValueMap) {
1710         newUsedVectorLength += map->size();
1711         if (newUsedVectorLength > m_vectorLength) {
1712             // Check that it is possible to allocate an array large enough to hold all the entries - if not,
1713             // exception is thrown by caller.
1714             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(globalData, newUsedVectorLength))
1715                 return 0;
1716
1717             storage = m_storage;
1718         }
1719
1720         SparseArrayValueMap::const_iterator end = map->end();
1721         for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
1722             storage->m_vector[numDefined++].setWithoutWriteBarrier(it->second.getNonSparseMode());
1723
1724         deallocateSparseMap();
1725     }
1726
1727     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
1728         storage->m_vector[i].setUndefined();
1729     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
1730         storage->m_vector[i].clear();
1731
1732     storage->m_numValuesInVector = newUsedVectorLength;
1733
1734     checkConsistency(SortConsistencyCheck);
1735
1736     return numDefined;
1737 }
1738
1739 void* JSArray::subclassData() const
1740 {
1741     return m_subclassData;
1742 }
1743
1744 void JSArray::setSubclassData(void* d)
1745 {
1746     m_subclassData = d;
1747 }
1748
1749 #if CHECK_ARRAY_CONSISTENCY
1750
1751 void JSArray::checkConsistency(ConsistencyCheckType type)
1752 {
1753     ArrayStorage* storage = m_storage;
1754
1755     ASSERT(!storage->m_inCompactInitialization);
1756
1757     ASSERT(storage);
1758     if (type == SortConsistencyCheck)
1759         ASSERT(!m_sparseValueMap);
1760
1761     unsigned numValuesInVector = 0;
1762     for (unsigned i = 0; i < m_vectorLength; ++i) {
1763         if (JSValue value = storage->m_vector[i]) {
1764             ASSERT(i < storage->m_length);
1765             if (type != DestructorConsistencyCheck)
1766                 value.isUndefined(); // Likely to crash if the object was deallocated.
1767             ++numValuesInVector;
1768         } else {
1769             if (type == SortConsistencyCheck)
1770                 ASSERT(i >= storage->m_numValuesInVector);
1771         }
1772     }
1773     ASSERT(numValuesInVector == storage->m_numValuesInVector);
1774     ASSERT(numValuesInVector <= storage->m_length);
1775
1776     if (m_sparseValueMap) {
1777         SparseArrayValueMap::iterator end = m_sparseValueMap->end();
1778         for (SparseArrayValueMap::iterator it = m_sparseValueMap->begin(); it != end; ++it) {
1779             unsigned index = it->first;
1780             ASSERT(index < storage->m_length);
1781             ASSERT(index >= storage->m_vectorLength);
1782             ASSERT(index <= MAX_ARRAY_INDEX);
1783             ASSERT(it->second);
1784             if (type != DestructorConsistencyCheck)
1785                 it->second.isUndefined(); // Likely to crash if the object was deallocated.
1786         }
1787     }
1788 }
1789
1790 #endif
1791
1792 } // namespace JSC