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