492e07731fa71b65cc08d3ba371431ac8427cead
[WebKit-https.git] / JavaScriptCore / kjs / JSArray.cpp
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2003, 2007, 2008 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 "PropertyNameArray.h"
28 #include <wtf/AVLTree.h>
29 #include <wtf/Assertions.h>
30
31 #define CHECK_ARRAY_CONSISTENCY 0
32
33 using namespace std;
34
35 namespace KJS {
36
37 typedef HashMap<unsigned, JSValue*> SparseArrayValueMap;
38
39 struct ArrayStorage {
40     unsigned m_vectorLength;
41     unsigned m_numValuesInVector;
42     SparseArrayValueMap* m_sparseValueMap;
43     void* lazyCreationData; // An JSArray subclass can use this to fill the vector lazily.
44     JSValue* m_vector[1];
45 };
46
47 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
48 static const unsigned maxArrayIndex = 0xFFFFFFFEU;
49
50 // Our policy for when to use a vector and when to use a sparse map.
51 // For all array indices under sparseArrayCutoff, we always use a vector.
52 // When indices greater than sparseArrayCutoff are involved, we use a vector
53 // as long as it is 1/8 full. If more sparse than that, we use a map.
54 // This value has to be a macro to be used in max() and min() without introducing
55 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
56 #define sparseArrayCutoff 10000U
57 static const unsigned minDensityMultiplier = 8;
58
59 const ClassInfo JSArray::info = {"Array", 0, 0, 0};
60
61 static inline size_t storageSize(unsigned vectorLength)
62 {
63     return sizeof(ArrayStorage) - sizeof(JSValue*) + vectorLength * sizeof(JSValue*);
64 }
65
66 static inline unsigned increasedVectorLength(unsigned newLength)
67 {
68     return (newLength * 3 + 1) / 2;
69 }
70
71 static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
72 {
73     return length / minDensityMultiplier <= numValues;
74 }
75
76 #if !CHECK_ARRAY_CONSISTENCY
77
78 inline void JSArray::checkConsistency(ConsistencyCheckType)
79 {
80 }
81
82 #endif
83
84 JSArray::JSArray(JSObject* prototype, unsigned initialLength)
85     : JSObject(prototype)
86 {
87     unsigned initialCapacity = min(initialLength, sparseArrayCutoff);
88
89     m_length = initialLength;
90     m_fastAccessCutoff = 0;
91     m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
92     m_storage->m_vectorLength = initialCapacity;
93
94     Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValue*));
95
96     checkConsistency();
97 }
98
99 JSArray::JSArray(JSObject* prototype, const ArgList& list)
100     : JSObject(prototype)
101 {
102     unsigned length = list.size();
103
104     m_length = length;
105     m_fastAccessCutoff = length;
106
107     ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(length)));
108
109     storage->m_vectorLength = length;
110     storage->m_numValuesInVector = length;
111     storage->m_sparseValueMap = 0;
112
113     size_t i = 0;
114     ArgList::const_iterator end = list.end();
115     for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
116         storage->m_vector[i] = *it;
117
118     m_storage = storage;
119
120     // When the array is created non-empty, its cells are filled, so it's really no worse than
121     // a property map. Therefore don't report extra memory cost.
122
123     checkConsistency();
124 }
125
126 JSArray::~JSArray()
127 {
128     checkConsistency(DestructorConsistencyCheck);
129
130     delete m_storage->m_sparseValueMap;
131     fastFree(m_storage);
132 }
133
134 JSValue* JSArray::lengthGetter(ExecState* exec, const Identifier&, const PropertySlot& slot)
135 {
136     return jsNumber(exec, static_cast<JSArray*>(slot.slotBase())->m_length);
137 }
138
139 NEVER_INLINE bool JSArray::getOwnPropertySlotSlowCase(ExecState* exec, unsigned i, PropertySlot& slot)
140 {
141     ArrayStorage* storage = m_storage;
142
143     if (i >= m_length) {
144         if (i > maxArrayIndex)
145             return getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
146         return false;
147     }
148
149     if (i < storage->m_vectorLength) {
150         JSValue*& valueSlot = storage->m_vector[i];
151         if (valueSlot) {
152             slot.setValueSlot(&valueSlot);
153             return true;
154         }
155     } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
156         if (i >= sparseArrayCutoff) {
157             SparseArrayValueMap::iterator it = map->find(i);
158             if (it != map->end()) {
159                 slot.setValueSlot(&it->second);
160                 return true;
161             }
162         }
163     }
164
165     return false;
166 }
167
168 bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
169 {
170     if (propertyName == exec->propertyNames().length) {
171         slot.setCustom(this, lengthGetter);
172         return true;
173     }
174
175     bool isArrayIndex;
176     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
177     if (isArrayIndex)
178         return JSArray::getOwnPropertySlot(exec, i, slot);
179
180     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
181 }
182
183 bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
184 {
185     if (i < m_fastAccessCutoff) {
186         slot.setValueSlot(&m_storage->m_vector[i]);
187         return true;
188     }
189
190     return getOwnPropertySlotSlowCase(exec, i, slot);
191 }
192
193 // ECMA 15.4.5.1
194 void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue* value)
195 {
196     bool isArrayIndex;
197     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
198     if (isArrayIndex) {
199         put(exec, i, value);
200         return;
201     }
202
203     if (propertyName == exec->propertyNames().length) {
204         unsigned newLength = value->toUInt32(exec);
205         if (value->toNumber(exec) != static_cast<double>(newLength)) {
206             throwError(exec, RangeError, "Invalid array length.");
207             return;
208         }
209         setLength(newLength);
210         return;
211     }
212
213     JSObject::put(exec, propertyName, value);
214 }
215
216 void JSArray::put(ExecState* exec, unsigned i, JSValue* value)
217 {
218     checkConsistency();
219
220     if (i < m_fastAccessCutoff) {
221         m_storage->m_vector[i] = value;
222         checkConsistency();
223         return;
224     }
225
226     unsigned length = m_length;
227     if (i >= length && i <= maxArrayIndex) {
228         length = i + 1;
229         m_length = length;
230     }
231
232     if (i < m_storage->m_vectorLength) {
233         JSValue*& valueSlot = m_storage->m_vector[i];
234         if (valueSlot) {
235             valueSlot = value;
236             checkConsistency();
237             return;
238         }
239         valueSlot = value;
240         if (++m_storage->m_numValuesInVector == m_length)
241             m_fastAccessCutoff = m_length;
242         checkConsistency();
243         return;
244     }
245
246     putSlowCase(exec, i, value);
247 }
248
249 NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue* value)
250 {
251     ArrayStorage* storage = m_storage;
252     SparseArrayValueMap* map = storage->m_sparseValueMap;
253
254     if (i >= sparseArrayCutoff) {
255         if (i > maxArrayIndex) {
256             put(exec, Identifier::from(exec, i), value);
257             return;
258         }
259
260         // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
261         // (which will only be compacted as we reach indices that are less than cutoff) - but this makes the check much faster.
262         if (!isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
263             if (!map) {
264                 map = new SparseArrayValueMap;
265                 storage->m_sparseValueMap = map;
266             }
267             map->set(i, value);
268             return;
269         }
270     }
271
272     // We have decided that we'll put the new item into the vector.
273     // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
274     if (!map || map->isEmpty()) {
275         increaseVectorLength(i + 1);
276         storage = m_storage;
277         ++storage->m_numValuesInVector;
278         storage->m_vector[i] = value;
279         checkConsistency();
280         return;
281     }
282
283     // Decide how many values it would be best to move from the map.
284     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
285     unsigned newVectorLength = increasedVectorLength(i + 1);
286     for (unsigned j = max(storage->m_vectorLength, sparseArrayCutoff); j < newVectorLength; ++j)
287         newNumValuesInVector += map->contains(j);
288     if (i >= sparseArrayCutoff)
289         newNumValuesInVector -= map->contains(i);
290     if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
291         unsigned proposedNewNumValuesInVector = newNumValuesInVector;
292         while (true) {
293             unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
294             for (unsigned j = max(newVectorLength, sparseArrayCutoff); j < proposedNewVectorLength; ++j)
295                 proposedNewNumValuesInVector += map->contains(j);
296             if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
297                 break;
298             newVectorLength = proposedNewVectorLength;
299             newNumValuesInVector = proposedNewNumValuesInVector;
300         }
301     }
302
303     storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength)));
304
305     unsigned vectorLength = storage->m_vectorLength;
306     if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
307         for (unsigned j = vectorLength; j < newVectorLength; ++j)
308             storage->m_vector[j] = 0;
309         if (i > sparseArrayCutoff)
310             map->remove(i);
311     } else {
312         for (unsigned j = vectorLength; j < max(vectorLength, sparseArrayCutoff); ++j)
313             storage->m_vector[j] = 0;
314         for (unsigned j = max(vectorLength, sparseArrayCutoff); j < newVectorLength; ++j)
315             storage->m_vector[j] = map->take(j);
316     }
317
318     storage->m_vector[i] = value;
319
320     storage->m_vectorLength = newVectorLength;
321     storage->m_numValuesInVector = newNumValuesInVector;
322
323     m_storage = storage;
324
325     checkConsistency();
326 }
327
328 bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)
329 {
330     bool isArrayIndex;
331     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
332     if (isArrayIndex)
333         return deleteProperty(exec, i);
334
335     if (propertyName == exec->propertyNames().length)
336         return false;
337
338     return JSObject::deleteProperty(exec, propertyName);
339 }
340
341 bool JSArray::deleteProperty(ExecState* exec, unsigned i)
342 {
343     checkConsistency();
344
345     ArrayStorage* storage = m_storage;
346
347     if (i < storage->m_vectorLength) {
348         JSValue*& valueSlot = storage->m_vector[i];
349         if (!valueSlot) {
350             checkConsistency();
351             return false;
352         }
353         valueSlot = 0;
354         --storage->m_numValuesInVector;
355         if (m_fastAccessCutoff > i)
356             m_fastAccessCutoff = i;
357         checkConsistency();
358         return true;
359     }
360
361     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
362         if (i >= sparseArrayCutoff) {
363             SparseArrayValueMap::iterator it = map->find(i);
364             if (it != map->end()) {
365                 map->remove(it);
366                 checkConsistency();
367                 return true;
368             }
369         }
370     }
371
372     checkConsistency();
373
374     if (i > maxArrayIndex)
375         return deleteProperty(exec, Identifier::from(exec, i));
376
377     return false;
378 }
379
380 void JSArray::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
381 {
382     // FIXME: Filling PropertyNameArray with an identifier for every integer
383     // is incredibly inefficient for large arrays. We need a different approach,
384     // which almost certainly means a different structure for PropertyNameArray.
385
386     ArrayStorage* storage = m_storage;
387
388     unsigned usedVectorLength = min(m_length, storage->m_vectorLength);
389     for (unsigned i = 0; i < usedVectorLength; ++i) {
390         if (storage->m_vector[i])
391             propertyNames.add(Identifier::from(exec, i));
392     }
393
394     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
395         SparseArrayValueMap::iterator end = map->end();
396         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
397             propertyNames.add(Identifier::from(exec, it->first));
398     }
399
400     JSObject::getPropertyNames(exec, propertyNames);
401 }
402
403 bool JSArray::increaseVectorLength(unsigned newLength)
404 {
405     // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
406     // to the vector. Callers have to account for that, because they can do it more efficiently.
407
408     ArrayStorage* storage = m_storage;
409
410     unsigned vectorLength = storage->m_vectorLength;
411     ASSERT(newLength > vectorLength);
412     unsigned newVectorLength = increasedVectorLength(newLength);
413
414     storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength)));
415     if (!storage)
416         return false;
417
418     storage->m_vectorLength = newVectorLength;
419
420     for (unsigned i = vectorLength; i < newVectorLength; ++i)
421         storage->m_vector[i] = 0;
422
423     m_storage = storage;
424     return true;
425 }
426
427 void JSArray::setLength(unsigned newLength)
428 {
429     checkConsistency();
430
431     ArrayStorage* storage = m_storage;
432
433     unsigned length = m_length;
434
435     if (newLength < length) {
436         if (m_fastAccessCutoff > newLength)
437             m_fastAccessCutoff = newLength;
438
439         unsigned usedVectorLength = min(length, storage->m_vectorLength);
440         for (unsigned i = newLength; i < usedVectorLength; ++i) {
441             JSValue*& valueSlot = storage->m_vector[i];
442             bool hadValue = valueSlot;
443             valueSlot = 0;
444             storage->m_numValuesInVector -= hadValue;
445         }
446
447         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
448             SparseArrayValueMap copy = *map;
449             SparseArrayValueMap::iterator end = copy.end();
450             for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
451                 if (it->first >= newLength)
452                     map->remove(it->first);
453             }
454             if (map->isEmpty()) {
455                 delete map;
456                 storage->m_sparseValueMap = 0;
457             }
458         }
459     }
460
461     m_length = newLength;
462
463     checkConsistency();
464 }
465
466 void JSArray::mark()
467 {
468     JSObject::mark();
469
470     ArrayStorage* storage = m_storage;
471
472     unsigned usedVectorLength = min(m_length, storage->m_vectorLength);
473     for (unsigned i = 0; i < usedVectorLength; ++i) {
474         JSValue* value = storage->m_vector[i];
475         if (value && !value->marked())
476             value->mark();
477     }
478
479     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
480         SparseArrayValueMap::iterator end = map->end();
481         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
482             JSValue* value = it->second;
483             if (!value->marked())
484                 value->mark();
485         }
486     }
487 }
488
489 typedef std::pair<JSValue*, UString> ArrayQSortPair;
490
491 static int compareByStringPairForQSort(const void* a, const void* b)
492 {
493     const ArrayQSortPair* va = static_cast<const ArrayQSortPair*>(a);
494     const ArrayQSortPair* vb = static_cast<const ArrayQSortPair*>(b);
495     return compare(va->second, vb->second);
496 }
497
498 void JSArray::sort(ExecState* exec)
499 {
500     unsigned lengthNotIncludingUndefined = compactForSorting();
501     if (m_storage->m_sparseValueMap) {
502         exec->setException(Error::create(exec, GeneralError, "Out of memory"));
503         return;
504     }
505
506     if (!lengthNotIncludingUndefined)
507         return;
508
509     // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
510     // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
511     // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
512     // random or otherwise changing results, effectively making compare function inconsistent.
513
514     Vector<ArrayQSortPair> values(lengthNotIncludingUndefined);
515     if (!values.begin()) {
516         exec->setException(Error::create(exec, GeneralError, "Out of memory"));
517         return;
518     }
519
520     for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
521         JSValue* value = m_storage->m_vector[i];
522         ASSERT(!value->isUndefined());
523         values[i].first = value;
524     }
525
526     // FIXME: While calling these toString functions, the array could be mutated.
527     // In that case, objects pointed to by values in this vector might get garbage-collected!
528
529     // FIXME: The following loop continues to call toString on subsequent values even after
530     // a toString call raises an exception.
531
532     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
533         values[i].second = values[i].first->toString(exec);
534
535     if (exec->hadException())
536         return;
537
538     // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
539     // than O(N log N).
540
541 #if HAVE(MERGESORT)
542     mergesort(values.begin(), values.size(), sizeof(ArrayQSortPair), compareByStringPairForQSort);
543 #else
544     // FIXME: The qsort library function is likely to not be a stable sort.
545     // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
546     qsort(values.begin(), values.size(), sizeof(ArrayQSortPair), compareByStringPairForQSort);
547 #endif
548
549     // FIXME: If the toString function changed the length of the array, this might be
550     // modifying the vector incorrectly.
551
552     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
553         m_storage->m_vector[i] = values[i].first;
554
555     checkConsistency(SortConsistencyCheck);
556 }
557
558 struct AVLTreeNodeForArrayCompare {
559     JSValue* value;
560
561     // Child pointers.  The high bit of gt is robbed and used as the
562     // balance factor sign.  The high bit of lt is robbed and used as
563     // the magnitude of the balance factor.
564     int32_t gt;
565     int32_t lt;
566 };
567
568 struct AVLTreeAbstractorForArrayCompare {
569     typedef int32_t handle; // Handle is an index into m_nodes vector.
570     typedef JSValue* key;
571     typedef int32_t size;
572
573     Vector<AVLTreeNodeForArrayCompare> m_nodes;
574     ExecState* m_exec;
575     JSValue* m_compareFunction;
576     CallType m_compareCallType;
577     const CallData* m_compareCallData;
578     JSValue* m_globalThisValue;
579
580     handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
581     void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; }
582     handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; }
583     void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; }
584
585     int get_balance_factor(handle h)
586     {
587         if (m_nodes[h].gt & 0x80000000)
588             return -1;
589         return static_cast<unsigned>(m_nodes[h].lt) >> 31;
590     }
591
592     void set_balance_factor(handle h, int bf)
593     {
594         if (bf == 0) {
595             m_nodes[h].lt &= 0x7FFFFFFF;
596             m_nodes[h].gt &= 0x7FFFFFFF;
597         } else {
598             m_nodes[h].lt |= 0x80000000;
599             if (bf < 0)
600                 m_nodes[h].gt |= 0x80000000;
601             else
602                 m_nodes[h].gt &= 0x7FFFFFFF;
603         }
604     }
605
606     int compare_key_key(key va, key vb)
607     {
608         ASSERT(!va->isUndefined());
609         ASSERT(!vb->isUndefined());
610
611         if (m_exec->hadException())
612             return 1;
613
614         ArgList arguments;
615         arguments.append(va);
616         arguments.append(vb);
617         double compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, m_globalThisValue, arguments)->toNumber(m_exec);
618         return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
619     }
620
621     int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
622     int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }
623
624     static handle null() { return 0x7FFFFFFF; }
625 };
626
627 void JSArray::sort(ExecState* exec, JSValue* compareFunction, CallType callType, const CallData& callData)
628 {
629     checkConsistency();
630
631     // FIXME: This ignores exceptions raised in the compare function or in toNumber.
632
633     // The maximum tree depth is compiled in - but the caller is clearly up to no good
634     // if a larger array is passed.
635     ASSERT(m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
636     if (m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
637         return;
638
639     if (!m_length)
640         return;
641
642     unsigned usedVectorLength = min(m_length, m_storage->m_vectorLength);
643
644     AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
645     tree.abstractor().m_exec = exec;
646     tree.abstractor().m_compareFunction = compareFunction;
647     tree.abstractor().m_compareCallType = callType;
648     tree.abstractor().m_compareCallData = &callData;
649     tree.abstractor().m_globalThisValue = exec->globalThisValue();
650     tree.abstractor().m_nodes.resize(usedVectorLength + (m_storage->m_sparseValueMap ? m_storage->m_sparseValueMap->size() : 0));
651
652     if (!tree.abstractor().m_nodes.begin()) {
653         exec->setException(Error::create(exec, GeneralError, "Out of memory"));
654         return;
655     }
656
657     // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
658     // right out from under us while we're building the tree here.
659
660     unsigned numDefined = 0;
661     unsigned numUndefined = 0;
662
663     // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
664     for (; numDefined < usedVectorLength; ++numDefined) {
665         JSValue* v = m_storage->m_vector[numDefined];
666         if (!v || v->isUndefined())
667             break;
668         tree.abstractor().m_nodes[numDefined].value = v;
669         tree.insert(numDefined);
670     }
671     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
672         if (JSValue* v = m_storage->m_vector[i]) {
673             if (v->isUndefined())
674                 ++numUndefined;
675             else {
676                 tree.abstractor().m_nodes[numDefined].value = v;
677                 tree.insert(numDefined);
678                 ++numDefined;
679             }
680         }
681     }
682
683     unsigned newUsedVectorLength = numDefined + numUndefined;
684
685     if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
686         newUsedVectorLength += map->size();
687         if (newUsedVectorLength > m_storage->m_vectorLength) {
688             if (!increaseVectorLength(newUsedVectorLength)) {
689                 exec->setException(Error::create(exec, GeneralError, "Out of memory"));
690                 return;
691             }
692         }
693
694         SparseArrayValueMap::iterator end = map->end();
695         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
696             tree.abstractor().m_nodes[numDefined].value = it->second;
697             tree.insert(numDefined);
698             ++numDefined;
699         }
700
701         delete map;
702         m_storage->m_sparseValueMap = 0;
703     }
704
705     ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
706
707     // FIXME: If the compare function changed the length of the array, the following might be
708     // modifying the vector incorrectly.
709
710     // Copy the values back into m_storage.
711     AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
712     iter.start_iter_least(tree);
713     for (unsigned i = 0; i < numDefined; ++i) {
714         m_storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value;
715         ++iter;
716     }
717
718     // Put undefined values back in.
719     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
720         m_storage->m_vector[i] = jsUndefined();
721
722     // Ensure that unused values in the vector are zeroed out.
723     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
724         m_storage->m_vector[i] = 0;
725
726     m_fastAccessCutoff = newUsedVectorLength;
727     m_storage->m_numValuesInVector = newUsedVectorLength;
728
729     checkConsistency(SortConsistencyCheck);
730 }
731
732 unsigned JSArray::compactForSorting()
733 {
734     checkConsistency();
735
736     ArrayStorage* storage = m_storage;
737
738     unsigned usedVectorLength = min(m_length, storage->m_vectorLength);
739
740     unsigned numDefined = 0;
741     unsigned numUndefined = 0;
742
743     for (; numDefined < usedVectorLength; ++numDefined) {
744         JSValue* v = storage->m_vector[numDefined];
745         if (!v || v->isUndefined())
746             break;
747     }
748     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
749         if (JSValue* v = storage->m_vector[i]) {
750             if (v->isUndefined())
751                 ++numUndefined;
752             else
753                 storage->m_vector[numDefined++] = v;
754         }
755     }
756
757     unsigned newUsedVectorLength = numDefined + numUndefined;
758
759     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
760         newUsedVectorLength += map->size();
761         if (newUsedVectorLength > storage->m_vectorLength) {
762             if (!increaseVectorLength(newUsedVectorLength))
763                 return 0;
764             storage = m_storage;
765         }
766
767         SparseArrayValueMap::iterator end = map->end();
768         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
769             storage->m_vector[numDefined++] = it->second;
770
771         delete map;
772         storage->m_sparseValueMap = 0;
773     }
774
775     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
776         storage->m_vector[i] = jsUndefined();
777     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
778         storage->m_vector[i] = 0;
779
780     m_fastAccessCutoff = newUsedVectorLength;
781     storage->m_numValuesInVector = newUsedVectorLength;
782
783     checkConsistency(SortConsistencyCheck);
784
785     return numDefined;
786 }
787
788 void* JSArray::lazyCreationData()
789 {
790     return m_storage->lazyCreationData;
791 }
792
793 void JSArray::setLazyCreationData(void* d)
794 {
795     m_storage->lazyCreationData = d;
796 }
797
798 #if CHECK_ARRAY_CONSISTENCY
799
800 void JSArray::checkConsistency(ConsistencyCheckType type)
801 {
802     ASSERT(m_storage);
803     if (type == SortConsistencyCheck)
804         ASSERT(!m_storage->m_sparseValueMap);
805
806     ASSERT(m_fastAccessCutoff <= m_length);
807     ASSERT(m_fastAccessCutoff <= m_storage->m_numValuesInVector);
808
809     unsigned numValuesInVector = 0;
810     for (unsigned i = 0; i < m_storage->m_vectorLength; ++i) {
811         if (JSValue* value = m_storage->m_vector[i]) {
812             ASSERT(i < m_length);
813             if (type != DestructorConsistencyCheck)
814                 value->type(); // Likely to crash if the object was deallocated.
815             ++numValuesInVector;
816         } else {
817             ASSERT(i >= m_fastAccessCutoff);
818             if (type == SortConsistencyCheck)
819                 ASSERT(i >= m_storage->m_numValuesInVector);
820         }
821     }
822     ASSERT(numValuesInVector == m_storage->m_numValuesInVector);
823
824     if (m_storage->m_sparseValueMap) {
825         SparseArrayValueMap::iterator end = m_storage->m_sparseValueMap->end();
826         for (SparseArrayValueMap::iterator it = m_storage->m_sparseValueMap->begin(); it != end; ++it) {
827             unsigned index = it->first;
828             ASSERT(index < m_length);
829             ASSERT(index >= m_storage->m_vectorLength);
830             ASSERT(index <= maxArrayIndex);
831             ASSERT(it->second);
832             if (type != DestructorConsistencyCheck)
833                 it->second->type(); // Likely to crash if the object was deallocated.
834         }
835     }
836 }
837
838 #endif
839
840 JSArray* constructEmptyArray(ExecState* exec)
841 {
842     return new (exec) JSArray(exec->lexicalGlobalObject()->arrayPrototype(), 0);
843 }
844
845 JSArray* constructEmptyArray(ExecState* exec, unsigned initialLength)
846 {
847     return new (exec) JSArray(exec->lexicalGlobalObject()->arrayPrototype(), initialLength);
848 }
849
850 JSArray* constructArray(ExecState* exec, JSValue* singleItemValue)
851 {
852     ArgList values;
853     values.append(singleItemValue);
854     return new (exec) JSArray(exec->lexicalGlobalObject()->arrayPrototype(), values);
855 }
856
857 JSArray* constructArray(ExecState* exec, const ArgList& values)
858 {
859     return new (exec) JSArray(exec->lexicalGlobalObject()->arrayPrototype(), values);
860 }
861
862 }