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