2011-01-27 Oliver Hunt <oliver@apple.com>
[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 "CachedCall.h"
28 #include "Error.h"
29 #include "Executable.h"
30 #include "PropertyNameArray.h"
31 #include <wtf/AVLTree.h>
32 #include <wtf/Assertions.h>
33 #include <wtf/OwnPtr.h>
34 #include <Operations.h>
35
36 using namespace std;
37 using namespace WTF;
38
39 namespace JSC {
40
41 ASSERT_CLASS_FITS_IN_CELL(JSArray);
42
43 // Overview of JSArray
44 //
45 // Properties of JSArray objects may be stored in one of three locations:
46 //   * The regular JSObject property map.
47 //   * A storage vector.
48 //   * A sparse map of array entries.
49 //
50 // Properties with non-numeric identifiers, with identifiers that are not representable
51 // as an unsigned integer, or where the value is greater than  MAX_ARRAY_INDEX
52 // (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit
53 // integer) are not considered array indices and will be stored in the JSObject property map.
54 //
55 // All properties with a numeric identifer, representable as an unsigned integer i,
56 // where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the
57 // storage vector or the sparse map.  An array index i will be handled in the following
58 // fashion:
59 //
60 //   * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector.
61 //   * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either
62 //     be stored in the storage vector or in the sparse array, depending on the density of
63 //     data that would be stored in the vector (a vector being used where at least
64 //     (1 / minDensityMultiplier) of the entries would be populated).
65 //   * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored
66 //     in the sparse array.
67
68 // The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
69 // function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
70 // size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(JSValue)) +
71 // (vectorLength * sizeof(JSValue)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
72 #define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue))
73
74 // These values have to be macros to be used in max() and min() without introducing
75 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
76 #define MIN_SPARSE_ARRAY_INDEX 10000U
77 #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
78 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
79 #define MAX_ARRAY_INDEX 0xFFFFFFFEU
80
81 // The value BASE_VECTOR_LEN is the maximum number of vector elements we'll allocate
82 // for an array that was created with a sepcified length (e.g. a = new Array(123))
83 #define BASE_VECTOR_LEN 4U
84     
85 // The upper bound to the size we'll grow a zero length array when the first element
86 // is added.
87 #define FIRST_VECTOR_GROW 4U
88
89 // Our policy for when to use a vector and when to use a sparse map.
90 // For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
91 // When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
92 // as long as it is 1/8 full. If more sparse than that, we use a map.
93 static const unsigned minDensityMultiplier = 8;
94
95 const ClassInfo JSArray::info = {"Array", 0, 0, 0};
96
97 // We keep track of the size of the last array after it was grown.  We use this
98 // as a simple heuristic for as the value to grow the next array from size 0.
99 // This value is capped by the constant FIRST_VECTOR_GROW defined above.
100 static unsigned lastArraySize = 0;
101
102 static inline size_t storageSize(unsigned vectorLength)
103 {
104     ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);
105
106     // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
107     // - as asserted above - the following calculation cannot overflow.
108     size_t size = (sizeof(ArrayStorage) - sizeof(JSValue)) + (vectorLength * sizeof(JSValue));
109     // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
110     // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
111     ASSERT(((size - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValue))));
112
113     return size;
114 }
115
116 static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
117 {
118     return length / minDensityMultiplier <= numValues;
119 }
120
121 #if !CHECK_ARRAY_CONSISTENCY
122
123 inline void JSArray::checkConsistency(ConsistencyCheckType)
124 {
125 }
126
127 #endif
128
129 JSArray::JSArray(VPtrStealingHackType)
130     : JSObject(createStructure(jsNull()))
131 {
132     unsigned initialCapacity = 0;
133
134     m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
135     m_storage->m_allocBase = m_storage;
136     m_indexBias = 0;
137     m_vectorLength = initialCapacity;
138
139     checkConsistency();
140     
141     // It's not safe to call Heap::heap(this) in order to report extra memory
142     // cost here, because the VPtrStealingHackType JSArray is not allocated on
143     // the heap. For the same reason, it's OK not to report extra cost.
144 }
145
146 JSArray::JSArray(NonNullPassRefPtr<Structure> structure)
147     : JSObject(structure)
148 {
149     unsigned initialCapacity = 0;
150
151     m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
152     m_storage->m_allocBase = m_storage;
153     m_indexBias = 0;
154     m_vectorLength = initialCapacity;
155
156     checkConsistency();
157
158     Heap::heap(this)->reportExtraMemoryCost(storageSize(0));
159 }
160
161 JSArray::JSArray(NonNullPassRefPtr<Structure> structure, unsigned initialLength, ArrayCreationMode creationMode)
162     : JSObject(structure)
163 {
164     unsigned initialCapacity;
165     if (creationMode == CreateCompact)
166         initialCapacity = initialLength;
167     else
168         initialCapacity = min(BASE_VECTOR_LEN, MIN_SPARSE_ARRAY_INDEX);
169     
170     m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
171     m_storage->m_allocBase = m_storage;
172     m_storage->m_length = initialLength;
173     m_indexBias = 0;
174     m_vectorLength = initialCapacity;
175     m_storage->m_sparseValueMap = 0;
176     m_storage->subclassData = 0;
177     m_storage->reportedMapCapacity = 0;
178
179     if (creationMode == CreateCompact) {
180 #if CHECK_ARRAY_CONSISTENCY
181         m_storage->m_inCompactInitialization = !!initialCapacity;
182 #endif
183         m_storage->m_length = 0;
184         m_storage->m_numValuesInVector = initialCapacity;
185     } else {
186 #if CHECK_ARRAY_CONSISTENCY
187         storage->m_inCompactInitialization = false;
188 #endif
189         m_storage->m_length = initialLength;
190         m_storage->m_numValuesInVector = 0;
191         WriteBarrier<Unknown>* vector = m_storage->m_vector;
192         for (size_t i = 0; i < initialCapacity; ++i)
193             vector[i].clear();
194     }
195
196     checkConsistency();
197     
198     Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity));
199 }
200
201 JSArray::JSArray(JSGlobalData& globalData, NonNullPassRefPtr<Structure> structure, const ArgList& list)
202     : JSObject(structure)
203 {
204     unsigned initialCapacity = list.size();
205     unsigned initialStorage;
206     
207     // If the ArgList is empty, allocate space for 3 entries.  This value empirically
208     // works well for benchmarks.
209     if (!initialCapacity)
210         initialStorage = 3;
211     else
212         initialStorage = initialCapacity;
213     
214     m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialStorage)));
215     m_storage->m_allocBase = m_storage;
216     m_indexBias = 0;
217     m_storage->m_length = initialCapacity;
218     m_vectorLength = initialStorage;
219     m_storage->m_numValuesInVector = initialCapacity;
220     m_storage->m_sparseValueMap = 0;
221     m_storage->subclassData = 0;
222     m_storage->reportedMapCapacity = 0;
223 #if CHECK_ARRAY_CONSISTENCY
224     m_storage->m_inCompactInitialization = false;
225 #endif
226
227     size_t i = 0;
228     WriteBarrier<Unknown>* vector = m_storage->m_vector;
229     ArgList::const_iterator end = list.end();
230     for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
231         vector[i].set(globalData, this, *it);
232     for (; i < initialStorage; i++)
233         vector[i].clear();
234
235     checkConsistency();
236
237     Heap::heap(this)->reportExtraMemoryCost(storageSize(initialStorage));
238 }
239
240 JSArray::~JSArray()
241 {
242     ASSERT(vptr() == JSGlobalData::jsArrayVPtr);
243     checkConsistency(DestructorConsistencyCheck);
244
245     delete m_storage->m_sparseValueMap;
246     fastFree(m_storage->m_allocBase);
247 }
248
249 bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
250 {
251     ArrayStorage* storage = m_storage;
252     
253     if (i >= storage->m_length) {
254         if (i > MAX_ARRAY_INDEX)
255             return getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
256         return false;
257     }
258
259     if (i < m_vectorLength) {
260         WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
261         if (valueSlot) {
262             slot.setValueSlot(valueSlot.slot());
263             return true;
264         }
265     } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
266         if (i >= MIN_SPARSE_ARRAY_INDEX) {
267             SparseArrayValueMap::iterator it = map->find(i);
268             if (it != map->end()) {
269                 slot.setValueSlot(it->second.slot());
270                 return true;
271             }
272         }
273     }
274
275     return JSObject::getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
276 }
277
278 bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
279 {
280     if (propertyName == exec->propertyNames().length) {
281         slot.setValue(jsNumber(length()));
282         return true;
283     }
284
285     bool isArrayIndex;
286     unsigned i = propertyName.toArrayIndex(isArrayIndex);
287     if (isArrayIndex)
288         return JSArray::getOwnPropertySlot(exec, i, slot);
289
290     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
291 }
292
293 bool JSArray::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
294 {
295     if (propertyName == exec->propertyNames().length) {
296         descriptor.setDescriptor(jsNumber(length()), DontDelete | DontEnum);
297         return true;
298     }
299
300     ArrayStorage* storage = m_storage;
301     
302     bool isArrayIndex;
303     unsigned i = propertyName.toArrayIndex(isArrayIndex);
304     if (isArrayIndex) {
305         if (i >= storage->m_length)
306             return false;
307         if (i < m_vectorLength) {
308             WriteBarrier<Unknown>& value = storage->m_vector[i];
309             if (value) {
310                 descriptor.setDescriptor(value.get(), 0);
311                 return true;
312             }
313         } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
314             if (i >= MIN_SPARSE_ARRAY_INDEX) {
315                 SparseArrayValueMap::iterator it = map->find(i);
316                 if (it != map->end()) {
317                     descriptor.setDescriptor(it->second.get(), 0);
318                     return true;
319                 }
320             }
321         }
322     }
323     return JSObject::getOwnPropertyDescriptor(exec, propertyName, descriptor);
324 }
325
326 // ECMA 15.4.5.1
327 void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
328 {
329     bool isArrayIndex;
330     unsigned i = propertyName.toArrayIndex(isArrayIndex);
331     if (isArrayIndex) {
332         put(exec, i, value);
333         return;
334     }
335
336     if (propertyName == exec->propertyNames().length) {
337         unsigned newLength = value.toUInt32(exec);
338         if (value.toNumber(exec) != static_cast<double>(newLength)) {
339             throwError(exec, createRangeError(exec, "Invalid array length."));
340             return;
341         }
342         setLength(newLength);
343         return;
344     }
345
346     JSObject::put(exec, propertyName, value, slot);
347 }
348
349 void JSArray::put(ExecState* exec, unsigned i, JSValue value)
350 {
351     checkConsistency();
352
353     ArrayStorage* storage = m_storage;
354
355     unsigned length = storage->m_length;
356     if (i >= length && i <= MAX_ARRAY_INDEX) {
357         length = i + 1;
358         storage->m_length = length;
359     }
360
361     if (i < m_vectorLength) {
362         WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
363         if (valueSlot) {
364             valueSlot.set(exec->globalData(), this, value);
365             checkConsistency();
366             return;
367         }
368         valueSlot.set(exec->globalData(), this, value);
369         ++storage->m_numValuesInVector;
370         checkConsistency();
371         return;
372     }
373
374     putSlowCase(exec, i, value);
375 }
376
377 NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
378 {
379     ArrayStorage* storage = m_storage;
380     
381     SparseArrayValueMap* map = storage->m_sparseValueMap;
382
383     if (i >= MIN_SPARSE_ARRAY_INDEX) {
384         if (i > MAX_ARRAY_INDEX) {
385             PutPropertySlot slot;
386             put(exec, Identifier::from(exec, i), value, slot);
387             return;
388         }
389
390         // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
391         // (which will only be compacted as we reach indices that are less than MIN_SPARSE_ARRAY_INDEX) - but this makes the check much faster.
392         if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
393             if (!map) {
394                 map = new SparseArrayValueMap;
395                 storage->m_sparseValueMap = map;
396             }
397
398             WriteBarrier<Unknown> temp;
399             pair<SparseArrayValueMap::iterator, bool> result = map->add(i, temp);
400             result.first->second.set(exec->globalData(), this, value);
401             if (!result.second) // pre-existing entry
402                 return;
403
404             size_t capacity = map->capacity();
405             if (capacity != storage->reportedMapCapacity) {
406                 Heap::heap(this)->reportExtraMemoryCost((capacity - storage->reportedMapCapacity) * (sizeof(unsigned) + sizeof(JSValue)));
407                 storage->reportedMapCapacity = capacity;
408             }
409             return;
410         }
411     }
412
413     // We have decided that we'll put the new item into the vector.
414     // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
415     if (!map || map->isEmpty()) {
416         if (increaseVectorLength(i + 1)) {
417             storage = m_storage;
418             storage->m_vector[i].set(exec->globalData(), this, value);
419             ++storage->m_numValuesInVector;
420             checkConsistency();
421         } else
422             throwOutOfMemoryError(exec);
423         return;
424     }
425
426     // Decide how many values it would be best to move from the map.
427     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
428     unsigned newVectorLength = getNewVectorLength(i + 1);
429     for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
430         newNumValuesInVector += map->contains(j);
431     if (i >= MIN_SPARSE_ARRAY_INDEX)
432         newNumValuesInVector -= map->contains(i);
433     if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
434         unsigned needLength = max(i + 1, storage->m_length);
435         unsigned proposedNewNumValuesInVector = newNumValuesInVector;
436         // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
437         while ((newVectorLength < needLength) && (newVectorLength < MAX_STORAGE_VECTOR_LENGTH)) {
438             unsigned proposedNewVectorLength = getNewVectorLength(newVectorLength + 1);
439             for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
440                 proposedNewNumValuesInVector += map->contains(j);
441             if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
442                 break;
443             newVectorLength = proposedNewVectorLength;
444             newNumValuesInVector = proposedNewNumValuesInVector;
445         }
446     }
447
448     void* baseStorage = storage->m_allocBase;
449     
450     if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) {
451         throwOutOfMemoryError(exec);
452         return;
453     }
454
455     m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
456     m_storage->m_allocBase = baseStorage;
457     storage = m_storage;
458     
459     unsigned vectorLength = m_vectorLength;
460     WriteBarrier<Unknown>* vector = storage->m_vector;
461
462     if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
463         for (unsigned j = vectorLength; j < newVectorLength; ++j)
464             vector[j].clear();
465         if (i > MIN_SPARSE_ARRAY_INDEX)
466             map->remove(i);
467     } else {
468         for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
469             vector[j].clear();
470         JSGlobalData& globalData = exec->globalData();
471         for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
472             vector[j].set(globalData, this, map->take(j).get());
473     }
474
475     ASSERT(i < newVectorLength);
476
477     m_vectorLength = newVectorLength;
478     storage->m_numValuesInVector = newNumValuesInVector;
479
480     storage->m_vector[i].set(exec->globalData(), this, value);
481
482     checkConsistency();
483
484     Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
485 }
486
487 bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)
488 {
489     bool isArrayIndex;
490     unsigned i = propertyName.toArrayIndex(isArrayIndex);
491     if (isArrayIndex)
492         return deleteProperty(exec, i);
493
494     if (propertyName == exec->propertyNames().length)
495         return false;
496
497     return JSObject::deleteProperty(exec, propertyName);
498 }
499
500 bool JSArray::deleteProperty(ExecState* exec, unsigned i)
501 {
502     checkConsistency();
503
504     ArrayStorage* storage = m_storage;
505     
506     if (i < m_vectorLength) {
507         WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
508         if (!valueSlot) {
509             checkConsistency();
510             return false;
511         }
512         valueSlot.clear();
513         --storage->m_numValuesInVector;
514         checkConsistency();
515         return true;
516     }
517
518     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
519         if (i >= MIN_SPARSE_ARRAY_INDEX) {
520             SparseArrayValueMap::iterator it = map->find(i);
521             if (it != map->end()) {
522                 map->remove(it);
523                 checkConsistency();
524                 return true;
525             }
526         }
527     }
528
529     checkConsistency();
530
531     if (i > MAX_ARRAY_INDEX)
532         return deleteProperty(exec, Identifier::from(exec, i));
533
534     return false;
535 }
536
537 void JSArray::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
538 {
539     // FIXME: Filling PropertyNameArray with an identifier for every integer
540     // is incredibly inefficient for large arrays. We need a different approach,
541     // which almost certainly means a different structure for PropertyNameArray.
542
543     ArrayStorage* storage = m_storage;
544     
545     unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
546     for (unsigned i = 0; i < usedVectorLength; ++i) {
547         if (storage->m_vector[i])
548             propertyNames.add(Identifier::from(exec, i));
549     }
550
551     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
552         SparseArrayValueMap::iterator end = map->end();
553         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
554             propertyNames.add(Identifier::from(exec, it->first));
555     }
556
557     if (mode == IncludeDontEnumProperties)
558         propertyNames.add(exec->propertyNames().length);
559
560     JSObject::getOwnPropertyNames(exec, propertyNames, mode);
561 }
562
563 ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
564 {
565     ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);
566
567     unsigned increasedLength;
568     unsigned maxInitLength = min(m_storage->m_length, 100000U);
569
570     if (desiredLength < maxInitLength)
571         increasedLength = maxInitLength;
572     else if (!m_vectorLength)
573         increasedLength = max(desiredLength, lastArraySize);
574     else {
575         // Mathematically equivalent to:
576         //   increasedLength = (newLength * 3 + 1) / 2;
577         // or:
578         //   increasedLength = (unsigned)ceil(newLength * 1.5));
579         // This form is not prone to internal overflow.
580         increasedLength = desiredLength + (desiredLength >> 1) + (desiredLength & 1);
581     }
582
583     ASSERT(increasedLength >= desiredLength);
584
585     lastArraySize = min(increasedLength, FIRST_VECTOR_GROW);
586
587     return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
588 }
589
590 bool JSArray::increaseVectorLength(unsigned newLength)
591 {
592     // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
593     // to the vector. Callers have to account for that, because they can do it more efficiently.
594
595     ArrayStorage* storage = m_storage;
596
597     unsigned vectorLength = m_vectorLength;
598     ASSERT(newLength > vectorLength);
599     ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
600     unsigned newVectorLength = getNewVectorLength(newLength);
601     void* baseStorage = storage->m_allocBase;
602
603     if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage))
604         return false;
605
606     storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
607     m_storage->m_allocBase = baseStorage;
608
609     WriteBarrier<Unknown>* vector = storage->m_vector;
610     for (unsigned i = vectorLength; i < newVectorLength; ++i)
611         vector[i].clear();
612
613     m_vectorLength = newVectorLength;
614     
615     Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
616
617     return true;
618 }
619
620 bool JSArray::increaseVectorPrefixLength(unsigned newLength)
621 {
622     // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
623     // to the vector. Callers have to account for that, because they can do it more efficiently.
624     
625     ArrayStorage* storage = m_storage;
626     
627     unsigned vectorLength = m_vectorLength;
628     ASSERT(newLength > vectorLength);
629     ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
630     unsigned newVectorLength = getNewVectorLength(newLength);
631
632     void* newBaseStorage = fastMalloc(storageSize(newVectorLength + m_indexBias));
633     if (!newBaseStorage)
634         return false;
635     
636     m_indexBias += newVectorLength - newLength;
637     
638     m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(newBaseStorage) + m_indexBias * sizeof(JSValue));
639
640     memcpy(m_storage, storage, storageSize(0));
641     memcpy(&m_storage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], vectorLength * sizeof(JSValue));
642     
643     m_storage->m_allocBase = newBaseStorage;
644     m_vectorLength = newLength;
645     
646     fastFree(storage->m_allocBase);
647
648     Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
649     
650     return true;
651 }
652     
653
654 void JSArray::setLength(unsigned newLength)
655 {
656     ArrayStorage* storage = m_storage;
657     
658 #if CHECK_ARRAY_CONSISTENCY
659     if (!storage->m_inCompactInitialization)
660         checkConsistency();
661     else
662         storage->m_inCompactInitialization = false;
663 #endif
664
665     unsigned length = storage->m_length;
666
667     if (newLength < length) {
668         unsigned usedVectorLength = min(length, m_vectorLength);
669         for (unsigned i = newLength; i < usedVectorLength; ++i) {
670             WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
671             bool hadValue = valueSlot;
672             valueSlot.clear();
673             storage->m_numValuesInVector -= hadValue;
674         }
675
676         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
677             SparseArrayValueMap copy = *map;
678             SparseArrayValueMap::iterator end = copy.end();
679             for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
680                 if (it->first >= newLength)
681                     map->remove(it->first);
682             }
683             if (map->isEmpty()) {
684                 delete map;
685                 storage->m_sparseValueMap = 0;
686             }
687         }
688     }
689
690     storage->m_length = newLength;
691
692     checkConsistency();
693 }
694
695 JSValue JSArray::pop()
696 {
697     checkConsistency();
698
699     ArrayStorage* storage = m_storage;
700     
701     unsigned length = storage->m_length;
702     if (!length)
703         return jsUndefined();
704
705     --length;
706
707     JSValue result;
708
709     if (length < m_vectorLength) {
710         WriteBarrier<Unknown>& valueSlot = storage->m_vector[length];
711         if (valueSlot) {
712             --storage->m_numValuesInVector;
713             result = valueSlot.get();
714             valueSlot.clear();
715         } else
716             result = jsUndefined();
717     } else {
718         result = jsUndefined();
719         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
720             SparseArrayValueMap::iterator it = map->find(length);
721             if (it != map->end()) {
722                 result = it->second.get();
723                 map->remove(it);
724                 if (map->isEmpty()) {
725                     delete map;
726                     storage->m_sparseValueMap = 0;
727                 }
728             }
729         }
730     }
731
732     storage->m_length = length;
733
734     checkConsistency();
735
736     return result;
737 }
738
739 void JSArray::push(ExecState* exec, JSValue value)
740 {
741     checkConsistency();
742     
743     ArrayStorage* storage = m_storage;
744
745     if (storage->m_length < m_vectorLength) {
746         storage->m_vector[storage->m_length].set(exec->globalData(), this, value);
747         ++storage->m_numValuesInVector;
748         ++storage->m_length;
749         checkConsistency();
750         return;
751     }
752
753     if (storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
754         SparseArrayValueMap* map = storage->m_sparseValueMap;
755         if (!map || map->isEmpty()) {
756             if (increaseVectorLength(storage->m_length + 1)) {
757                 storage = m_storage;
758                 storage->m_vector[storage->m_length].set(exec->globalData(), this, value);
759                 ++storage->m_numValuesInVector;
760                 ++storage->m_length;
761                 checkConsistency();
762                 return;
763             }
764             checkConsistency();
765             throwOutOfMemoryError(exec);
766             return;
767         }
768     }
769
770     putSlowCase(exec, storage->m_length++, value);
771 }
772
773 void JSArray::shiftCount(ExecState* exec, int count)
774 {
775     ASSERT(count > 0);
776     
777     ArrayStorage* storage = m_storage;
778     
779     unsigned oldLength = storage->m_length;
780     
781     if (!oldLength)
782         return;
783     
784     if (oldLength != storage->m_numValuesInVector) {
785         // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
786         // which means we need to go through each entry looking for the the "empty"
787         // slots and then fill them with possible properties.  See ECMA spec.
788         // 15.4.4.9 steps 11 through 13.
789         for (unsigned i = count; i < oldLength; ++i) {
790             if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
791                 PropertySlot slot(this);
792                 JSValue p = prototype();
793                 if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
794                     put(exec, i, slot.getValue(exec, i));
795             }
796         }
797
798         storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
799
800         // Need to decrement numValuesInvector based on number of real entries
801         for (unsigned i = 0; i < (unsigned)count; ++i)
802             if ((i < m_vectorLength) && (storage->m_vector[i]))
803                 --storage->m_numValuesInVector;
804     } else
805         storage->m_numValuesInVector -= count;
806     
807     storage->m_length -= count;
808     
809     if (m_vectorLength) {
810         count = min(m_vectorLength, (unsigned)count);
811         
812         m_vectorLength -= count;
813         
814         if (m_vectorLength) {
815             char* newBaseStorage = reinterpret_cast<char*>(storage) + count * sizeof(JSValue);
816             memmove(newBaseStorage, storage, storageSize(0));
817             m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
818
819             m_indexBias += count;
820         }
821     }
822 }
823     
824 void JSArray::unshiftCount(ExecState* exec, int count)
825 {
826     ArrayStorage* storage = m_storage;
827
828     ASSERT(m_indexBias >= 0);
829     ASSERT(count >= 0);
830     
831     unsigned length = storage->m_length;
832     
833     if (length != storage->m_numValuesInVector) {
834         // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
835         // which means we need to go through each entry looking for the the "empty"
836         // slots and then fill them with possible properties.  See ECMA spec.
837         // 15.4.4.13 steps 8 through 10.
838         for (unsigned i = 0; i < length; ++i) {
839             if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
840                 PropertySlot slot(this);
841                 JSValue p = prototype();
842                 if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
843                     put(exec, i, slot.getValue(exec, i));
844             }
845         }
846     }
847     
848     storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
849     
850     if (m_indexBias >= count) {
851         m_indexBias -= count;
852         char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(JSValue);
853         memmove(newBaseStorage, storage, storageSize(0));
854         m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
855         m_vectorLength += count;
856     } else if (!increaseVectorPrefixLength(m_vectorLength + count)) {
857         throwOutOfMemoryError(exec);
858         return;
859     }
860
861     WriteBarrier<Unknown>* vector = m_storage->m_vector;
862     for (int i = 0; i < count; i++)
863         vector[i].clear();
864 }
865
866 void JSArray::markChildren(MarkStack& markStack)
867 {
868     markChildrenDirect(markStack);
869 }
870
871 static int compareNumbersForQSort(const void* a, const void* b)
872 {
873     double da = static_cast<const JSValue*>(a)->uncheckedGetNumber();
874     double db = static_cast<const JSValue*>(b)->uncheckedGetNumber();
875     return (da > db) - (da < db);
876 }
877
878 static int compareByStringPairForQSort(const void* a, const void* b)
879 {
880     const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
881     const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
882     return codePointCompare(va->second, vb->second);
883 }
884
885 void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
886 {
887     ArrayStorage* storage = m_storage;
888
889     unsigned lengthNotIncludingUndefined = compactForSorting();
890     if (storage->m_sparseValueMap) {
891         throwOutOfMemoryError(exec);
892         return;
893     }
894
895     if (!lengthNotIncludingUndefined)
896         return;
897         
898     bool allValuesAreNumbers = true;
899     size_t size = storage->m_numValuesInVector;
900     for (size_t i = 0; i < size; ++i) {
901         if (!storage->m_vector[i].isNumber()) {
902             allValuesAreNumbers = false;
903             break;
904         }
905     }
906
907     if (!allValuesAreNumbers)
908         return sort(exec, compareFunction, callType, callData);
909
910     // For numeric comparison, which is fast, qsort is faster than mergesort. We
911     // also don't require mergesort's stability, since there's no user visible
912     // side-effect from swapping the order of equal primitive values.
913     qsort(storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort);
914
915     checkConsistency(SortConsistencyCheck);
916 }
917
918 void JSArray::sort(ExecState* exec)
919 {
920     ArrayStorage* storage = m_storage;
921
922     unsigned lengthNotIncludingUndefined = compactForSorting();
923     if (storage->m_sparseValueMap) {
924         throwOutOfMemoryError(exec);
925         return;
926     }
927
928     if (!lengthNotIncludingUndefined)
929         return;
930
931     // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
932     // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
933     // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
934     // random or otherwise changing results, effectively making compare function inconsistent.
935
936     Vector<ValueStringPair> values(lengthNotIncludingUndefined);
937     if (!values.begin()) {
938         throwOutOfMemoryError(exec);
939         return;
940     }
941     
942     Heap::heap(this)->pushTempSortVector(&values);
943
944     for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
945         JSValue value = storage->m_vector[i].get();
946         ASSERT(!value.isUndefined());
947         values[i].first = value;
948     }
949
950     // FIXME: The following loop continues to call toString on subsequent values even after
951     // a toString call raises an exception.
952
953     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
954         values[i].second = values[i].first.toString(exec);
955
956     if (exec->hadException()) {
957         Heap::heap(this)->popTempSortVector(&values);
958         return;
959     }
960
961     // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
962     // than O(N log N).
963
964 #if HAVE(MERGESORT)
965     mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
966 #else
967     // FIXME: The qsort library function is likely to not be a stable sort.
968     // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
969     qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
970 #endif
971
972     // If the toString function changed the length of the array or vector storage,
973     // increase the length to handle the orignal number of actual values.
974     if (m_vectorLength < lengthNotIncludingUndefined)
975         increaseVectorLength(lengthNotIncludingUndefined);
976     if (storage->m_length < lengthNotIncludingUndefined)
977         storage->m_length = lengthNotIncludingUndefined;
978
979     JSGlobalData& globalData = exec->globalData();
980     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
981         storage->m_vector[i].set(globalData, this, values[i].first);
982
983     Heap::heap(this)->popTempSortVector(&values);
984     
985     checkConsistency(SortConsistencyCheck);
986 }
987
988 struct AVLTreeNodeForArrayCompare {
989     JSValue value;
990
991     // Child pointers.  The high bit of gt is robbed and used as the
992     // balance factor sign.  The high bit of lt is robbed and used as
993     // the magnitude of the balance factor.
994     int32_t gt;
995     int32_t lt;
996 };
997
998 struct AVLTreeAbstractorForArrayCompare {
999     typedef int32_t handle; // Handle is an index into m_nodes vector.
1000     typedef JSValue key;
1001     typedef int32_t size;
1002
1003     Vector<AVLTreeNodeForArrayCompare> m_nodes;
1004     ExecState* m_exec;
1005     JSValue m_compareFunction;
1006     CallType m_compareCallType;
1007     const CallData* m_compareCallData;
1008     JSValue m_globalThisValue;
1009     OwnPtr<CachedCall> m_cachedCall;
1010
1011     handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
1012     void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; }
1013     handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; }
1014     void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; }
1015
1016     int get_balance_factor(handle h)
1017     {
1018         if (m_nodes[h].gt & 0x80000000)
1019             return -1;
1020         return static_cast<unsigned>(m_nodes[h].lt) >> 31;
1021     }
1022
1023     void set_balance_factor(handle h, int bf)
1024     {
1025         if (bf == 0) {
1026             m_nodes[h].lt &= 0x7FFFFFFF;
1027             m_nodes[h].gt &= 0x7FFFFFFF;
1028         } else {
1029             m_nodes[h].lt |= 0x80000000;
1030             if (bf < 0)
1031                 m_nodes[h].gt |= 0x80000000;
1032             else
1033                 m_nodes[h].gt &= 0x7FFFFFFF;
1034         }
1035     }
1036
1037     int compare_key_key(key va, key vb)
1038     {
1039         ASSERT(!va.isUndefined());
1040         ASSERT(!vb.isUndefined());
1041
1042         if (m_exec->hadException())
1043             return 1;
1044
1045         double compareResult;
1046         if (m_cachedCall) {
1047             m_cachedCall->setThis(m_globalThisValue);
1048             m_cachedCall->setArgument(0, va);
1049             m_cachedCall->setArgument(1, vb);
1050             compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec));
1051         } else {
1052             MarkedArgumentBuffer arguments;
1053             arguments.append(va);
1054             arguments.append(vb);
1055             compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, m_globalThisValue, arguments).toNumber(m_exec);
1056         }
1057         return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
1058     }
1059
1060     int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
1061     int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }
1062
1063     static handle null() { return 0x7FFFFFFF; }
1064 };
1065
1066 void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
1067 {
1068     checkConsistency();
1069
1070     ArrayStorage* storage = m_storage;
1071
1072     // FIXME: This ignores exceptions raised in the compare function or in toNumber.
1073
1074     // The maximum tree depth is compiled in - but the caller is clearly up to no good
1075     // if a larger array is passed.
1076     ASSERT(storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
1077     if (storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
1078         return;
1079
1080     unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
1081     unsigned nodeCount = usedVectorLength + (storage->m_sparseValueMap ? storage->m_sparseValueMap->size() : 0);
1082
1083     if (!nodeCount)
1084         return;
1085
1086     AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
1087     tree.abstractor().m_exec = exec;
1088     tree.abstractor().m_compareFunction = compareFunction;
1089     tree.abstractor().m_compareCallType = callType;
1090     tree.abstractor().m_compareCallData = &callData;
1091     tree.abstractor().m_globalThisValue = exec->globalThisValue();
1092     tree.abstractor().m_nodes.grow(nodeCount);
1093
1094     if (callType == CallTypeJS)
1095         tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, asFunction(compareFunction), 2));
1096
1097     if (!tree.abstractor().m_nodes.begin()) {
1098         throwOutOfMemoryError(exec);
1099         return;
1100     }
1101
1102     // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
1103     // right out from under us while we're building the tree here.
1104
1105     unsigned numDefined = 0;
1106     unsigned numUndefined = 0;
1107
1108     // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
1109     for (; numDefined < usedVectorLength; ++numDefined) {
1110         JSValue v = storage->m_vector[numDefined].get();
1111         if (!v || v.isUndefined())
1112             break;
1113         tree.abstractor().m_nodes[numDefined].value = v;
1114         tree.insert(numDefined);
1115     }
1116     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
1117         JSValue v = storage->m_vector[i].get();
1118         if (v) {
1119             if (v.isUndefined())
1120                 ++numUndefined;
1121             else {
1122                 tree.abstractor().m_nodes[numDefined].value = v;
1123                 tree.insert(numDefined);
1124                 ++numDefined;
1125             }
1126         }
1127     }
1128
1129     unsigned newUsedVectorLength = numDefined + numUndefined;
1130
1131     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
1132         newUsedVectorLength += map->size();
1133         if (newUsedVectorLength > m_vectorLength) {
1134             // Check that it is possible to allocate an array large enough to hold all the entries.
1135             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) {
1136                 throwOutOfMemoryError(exec);
1137                 return;
1138             }
1139         }
1140         
1141         storage = m_storage;
1142
1143         SparseArrayValueMap::iterator end = map->end();
1144         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
1145             tree.abstractor().m_nodes[numDefined].value = it->second.get();
1146             tree.insert(numDefined);
1147             ++numDefined;
1148         }
1149
1150         delete map;
1151         storage->m_sparseValueMap = 0;
1152     }
1153
1154     ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
1155
1156     // FIXME: If the compare function changed the length of the array, the following might be
1157     // modifying the vector incorrectly.
1158
1159     // Copy the values back into m_storage.
1160     AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
1161     iter.start_iter_least(tree);
1162     JSGlobalData& globalData = exec->globalData();
1163     for (unsigned i = 0; i < numDefined; ++i) {
1164         storage->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
1165         ++iter;
1166     }
1167
1168     // Put undefined values back in.
1169     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
1170         storage->m_vector[i].setUndefined();
1171
1172     // Ensure that unused values in the vector are zeroed out.
1173     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
1174         storage->m_vector[i].clear();
1175
1176     storage->m_numValuesInVector = newUsedVectorLength;
1177
1178     checkConsistency(SortConsistencyCheck);
1179 }
1180
1181 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
1182 {
1183     ArrayStorage* storage = m_storage;
1184
1185     WriteBarrier<Unknown>* vector = storage->m_vector;
1186     unsigned vectorEnd = min(storage->m_length, m_vectorLength);
1187     unsigned i = 0;
1188     for (; i < vectorEnd; ++i) {
1189         WriteBarrier<Unknown>& v = vector[i];
1190         if (!v)
1191             break;
1192         args.append(v.get());
1193     }
1194
1195     for (; i < storage->m_length; ++i)
1196         args.append(get(exec, i));
1197 }
1198
1199 void JSArray::copyToRegisters(ExecState* exec, Register* buffer, uint32_t maxSize)
1200 {
1201     ASSERT(m_storage->m_length >= maxSize);
1202     UNUSED_PARAM(maxSize);
1203     WriteBarrier<Unknown>* vector = m_storage->m_vector;
1204     unsigned vectorEnd = min(maxSize, m_vectorLength);
1205     unsigned i = 0;
1206     for (; i < vectorEnd; ++i) {
1207         WriteBarrier<Unknown>& v = vector[i];
1208         if (!v)
1209             break;
1210         buffer[i] = v.get();
1211     }
1212
1213     for (; i < maxSize; ++i)
1214         buffer[i] = get(exec, i);
1215 }
1216
1217 unsigned JSArray::compactForSorting()
1218 {
1219     checkConsistency();
1220
1221     ArrayStorage* storage = m_storage;
1222
1223     unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
1224
1225     unsigned numDefined = 0;
1226     unsigned numUndefined = 0;
1227
1228     for (; numDefined < usedVectorLength; ++numDefined) {
1229         JSValue v = storage->m_vector[numDefined].get();
1230         if (!v || v.isUndefined())
1231             break;
1232     }
1233
1234     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
1235         JSValue v = storage->m_vector[i].get();
1236         if (v) {
1237             if (v.isUndefined())
1238                 ++numUndefined;
1239             else
1240                 storage->m_vector[numDefined++].setWithoutWriteBarrier(v);
1241         }
1242     }
1243
1244     unsigned newUsedVectorLength = numDefined + numUndefined;
1245
1246     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
1247         newUsedVectorLength += map->size();
1248         if (newUsedVectorLength > m_vectorLength) {
1249             // Check that it is possible to allocate an array large enough to hold all the entries - if not,
1250             // exception is thrown by caller.
1251             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength))
1252                 return 0;
1253
1254             storage = m_storage;
1255         }
1256
1257         SparseArrayValueMap::iterator end = map->end();
1258         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
1259             storage->m_vector[numDefined++].setWithoutWriteBarrier(it->second.get());
1260
1261         delete map;
1262         storage->m_sparseValueMap = 0;
1263     }
1264
1265     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
1266         storage->m_vector[i].setUndefined();
1267     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
1268         storage->m_vector[i].clear();
1269
1270     storage->m_numValuesInVector = newUsedVectorLength;
1271
1272     checkConsistency(SortConsistencyCheck);
1273
1274     return numDefined;
1275 }
1276
1277 void* JSArray::subclassData() const
1278 {
1279     return m_storage->subclassData;
1280 }
1281
1282 void JSArray::setSubclassData(void* d)
1283 {
1284     m_storage->subclassData = d;
1285 }
1286
1287 #if CHECK_ARRAY_CONSISTENCY
1288
1289 void JSArray::checkConsistency(ConsistencyCheckType type)
1290 {
1291     ArrayStorage* storage = m_storage;
1292
1293     ASSERT(storage);
1294     if (type == SortConsistencyCheck)
1295         ASSERT(!storage->m_sparseValueMap);
1296
1297     unsigned numValuesInVector = 0;
1298     for (unsigned i = 0; i < m_vectorLength; ++i) {
1299         if (JSValue value = storage->m_vector[i]) {
1300             ASSERT(i < storage->m_length);
1301             if (type != DestructorConsistencyCheck)
1302                 value.isUndefined(); // Likely to crash if the object was deallocated.
1303             ++numValuesInVector;
1304         } else {
1305             if (type == SortConsistencyCheck)
1306                 ASSERT(i >= storage->m_numValuesInVector);
1307         }
1308     }
1309     ASSERT(numValuesInVector == storage->m_numValuesInVector);
1310     ASSERT(numValuesInVector <= storage->m_length);
1311
1312     if (storage->m_sparseValueMap) {
1313         SparseArrayValueMap::iterator end = storage->m_sparseValueMap->end();
1314         for (SparseArrayValueMap::iterator it = storage->m_sparseValueMap->begin(); it != end; ++it) {
1315             unsigned index = it->first;
1316             ASSERT(index < storage->m_length);
1317             ASSERT(index >= storage->m_vectorLength);
1318             ASSERT(index <= MAX_ARRAY_INDEX);
1319             ASSERT(it->second);
1320             if (type != DestructorConsistencyCheck)
1321                 it->second.isUndefined(); // Likely to crash if the object was deallocated.
1322         }
1323     }
1324 }
1325
1326 #endif
1327
1328 } // namespace JSC