JavaScriptCore:
[WebKit-https.git] / JavaScriptCore / runtime / 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 #include <Operations.h>
31
32 #define CHECK_ARRAY_CONSISTENCY 0
33
34 using namespace std;
35 using namespace WTF;
36
37 namespace JSC {
38
39 ASSERT_CLASS_FITS_IN_CELL(JSArray);
40
41 // Overview of JSArray
42 //
43 // Properties of JSArray objects may be stored in one of three locations:
44 //   * The regular JSObject property map.
45 //   * A storage vector.
46 //   * A sparse map of array entries.
47 //
48 // Properties with non-numeric identifiers, with identifiers that are not representable
49 // as an unsigned integer, or where the value is greater than  MAX_ARRAY_INDEX
50 // (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit
51 // integer) are not considered array indices and will be stored in the JSObject property map.
52 //
53 // All properties with a numeric identifer, representable as an unsigned integer i,
54 // where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the
55 // storage vector or the sparse map.  An array index i will be handled in the following
56 // fashion:
57 //
58 //   * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector.
59 //   * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either
60 //     be stored in the storage vector or in the sparse array, depending on the density of
61 //     data that would be stored in the vector (a vector being used where at least
62 //     (1 / minDensityMultiplier) of the entries would be populated).
63 //   * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored
64 //     in the sparse array.
65
66 // The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
67 // function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
68 // size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(JSValuePtr)) +
69 // (vectorLength * sizeof(JSValuePtr)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
70 #define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(JSValuePtr))) / sizeof(JSValuePtr))
71
72 // These values have to be macros to be used in max() and min() without introducing
73 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
74 #define MIN_SPARSE_ARRAY_INDEX 10000U
75 #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
76 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
77 #define MAX_ARRAY_INDEX 0xFFFFFFFEU
78
79 // Our policy for when to use a vector and when to use a sparse map.
80 // For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
81 // When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
82 // as long as it is 1/8 full. If more sparse than that, we use a map.
83 static const unsigned minDensityMultiplier = 8;
84
85 const ClassInfo JSArray::info = {"Array", 0, 0, 0};
86
87 static inline size_t storageSize(unsigned vectorLength)
88 {
89     ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);
90
91     // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
92     // - as asserted above - the following calculation cannot overflow.
93     size_t size = (sizeof(ArrayStorage) - sizeof(JSValuePtr)) + (vectorLength * sizeof(JSValuePtr));
94     // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
95     // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
96     ASSERT(((size - (sizeof(ArrayStorage) - sizeof(JSValuePtr))) / sizeof(JSValuePtr) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValuePtr))));
97
98     return size;
99 }
100
101 static inline unsigned increasedVectorLength(unsigned newLength)
102 {
103     ASSERT(newLength <= MAX_STORAGE_VECTOR_LENGTH);
104
105     // Mathematically equivalent to:
106     //   increasedLength = (newLength * 3 + 1) / 2;
107     // or:
108     //   increasedLength = (unsigned)ceil(newLength * 1.5));
109     // This form is not prone to internal overflow.
110     unsigned increasedLength = newLength + (newLength >> 1) + (newLength & 1);
111     ASSERT(increasedLength >= newLength);
112
113     return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
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(PassRefPtr<Structure> structure)
130     : JSObject(structure)
131 {
132     unsigned initialCapacity = 0;
133
134     m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
135     m_fastAccessCutoff = 0;
136     m_storage->m_vectorLength = initialCapacity;
137     m_storage->m_length = 0;
138
139     checkConsistency();
140 }
141
142 JSArray::JSArray(PassRefPtr<Structure> structure, unsigned initialLength)
143     : JSObject(structure)
144 {
145     unsigned initialCapacity = min(initialLength, MIN_SPARSE_ARRAY_INDEX);
146
147     m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
148     m_fastAccessCutoff = 0;
149     m_storage->m_vectorLength = initialCapacity;
150     m_storage->m_length = initialLength;
151
152     Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValuePtr));
153
154     checkConsistency();
155 }
156
157 JSArray::JSArray(ExecState* exec, PassRefPtr<Structure> structure, const ArgList& list)
158     : JSObject(structure)
159 {
160     unsigned length = list.size();
161
162     m_fastAccessCutoff = length;
163
164     ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(length)));
165
166     storage->m_vectorLength = length;
167     storage->m_numValuesInVector = length;
168     storage->m_sparseValueMap = 0;
169     storage->m_length = length;
170
171     size_t i = 0;
172     ArgList::const_iterator end = list.end();
173     for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
174         storage->m_vector[i] = (*it).jsValue(exec);
175
176     m_storage = storage;
177
178     Heap::heap(this)->reportExtraMemoryCost(storageSize(length));
179
180     checkConsistency();
181 }
182
183 JSArray::~JSArray()
184 {
185     checkConsistency(DestructorConsistencyCheck);
186
187     delete m_storage->m_sparseValueMap;
188     fastFree(m_storage);
189 }
190
191 bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
192 {
193     ArrayStorage* storage = m_storage;
194
195     if (i >= storage->m_length) {
196         if (i > MAX_ARRAY_INDEX)
197             return getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
198         return false;
199     }
200
201     if (i < storage->m_vectorLength) {
202         JSValuePtr& valueSlot = storage->m_vector[i];
203         if (valueSlot) {
204             slot.setValueSlot(&valueSlot);
205             return true;
206         }
207     } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
208         if (i >= MIN_SPARSE_ARRAY_INDEX) {
209             SparseArrayValueMap::iterator it = map->find(i);
210             if (it != map->end()) {
211                 slot.setValueSlot(&it->second);
212                 return true;
213             }
214         }
215     }
216
217     return false;
218 }
219
220 bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
221 {
222     if (propertyName == exec->propertyNames().length) {
223         slot.setValue(jsNumber(exec, length()));
224         return true;
225     }
226
227     bool isArrayIndex;
228     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
229     if (isArrayIndex)
230         return JSArray::getOwnPropertySlot(exec, i, slot);
231
232     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
233 }
234
235 // ECMA 15.4.5.1
236 void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValuePtr value, PutPropertySlot& slot)
237 {
238     bool isArrayIndex;
239     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
240     if (isArrayIndex) {
241         put(exec, i, value);
242         return;
243     }
244
245     if (propertyName == exec->propertyNames().length) {
246         unsigned newLength = value.toUInt32(exec);
247         if (value.toNumber(exec) != static_cast<double>(newLength)) {
248             throwError(exec, RangeError, "Invalid array length.");
249             return;
250         }
251         setLength(newLength);
252         return;
253     }
254
255     JSObject::put(exec, propertyName, value, slot);
256 }
257
258 void JSArray::put(ExecState* exec, unsigned i, JSValuePtr value)
259 {
260     checkConsistency();
261
262     unsigned length = m_storage->m_length;
263     if (i >= length && i <= MAX_ARRAY_INDEX) {
264         length = i + 1;
265         m_storage->m_length = length;
266     }
267
268     if (i < m_storage->m_vectorLength) {
269         JSValuePtr& valueSlot = m_storage->m_vector[i];
270         if (valueSlot) {
271             valueSlot = value;
272             checkConsistency();
273             return;
274         }
275         valueSlot = value;
276         if (++m_storage->m_numValuesInVector == m_storage->m_length)
277             m_fastAccessCutoff = m_storage->m_length;
278         checkConsistency();
279         return;
280     }
281
282     putSlowCase(exec, i, value);
283 }
284
285 NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValuePtr value)
286 {
287     ArrayStorage* storage = m_storage;
288     SparseArrayValueMap* map = storage->m_sparseValueMap;
289
290     if (i >= MIN_SPARSE_ARRAY_INDEX) {
291         if (i > MAX_ARRAY_INDEX) {
292             PutPropertySlot slot;
293             put(exec, Identifier::from(exec, i), value, slot);
294             return;
295         }
296
297         // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
298         // (which will only be compacted as we reach indices that are less than cutoff) - but this makes the check much faster.
299         if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
300             if (!map) {
301                 map = new SparseArrayValueMap;
302                 storage->m_sparseValueMap = map;
303             }
304             map->set(i, value);
305             return;
306         }
307     }
308
309     // We have decided that we'll put the new item into the vector.
310     // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
311     if (!map || map->isEmpty()) {
312         if (increaseVectorLength(i + 1)) {
313             storage = m_storage;
314             storage->m_vector[i] = value;
315             if (++storage->m_numValuesInVector == storage->m_length)
316                 m_fastAccessCutoff = storage->m_length;
317             checkConsistency();
318         } else
319             throwOutOfMemoryError(exec);
320         return;
321     }
322
323     // Decide how many values it would be best to move from the map.
324     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
325     unsigned newVectorLength = increasedVectorLength(i + 1);
326     for (unsigned j = max(storage->m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
327         newNumValuesInVector += map->contains(j);
328     if (i >= MIN_SPARSE_ARRAY_INDEX)
329         newNumValuesInVector -= map->contains(i);
330     if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
331         unsigned proposedNewNumValuesInVector = newNumValuesInVector;
332         // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
333         while (newVectorLength < MAX_STORAGE_VECTOR_LENGTH) {
334             unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
335             for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
336                 proposedNewNumValuesInVector += map->contains(j);
337             if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
338                 break;
339             newVectorLength = proposedNewVectorLength;
340             newNumValuesInVector = proposedNewNumValuesInVector;
341         }
342     }
343
344     storage = static_cast<ArrayStorage*>(tryFastRealloc(storage, storageSize(newVectorLength)));
345     if (!storage) {
346         throwOutOfMemoryError(exec);
347         return;
348     }
349
350     unsigned vectorLength = storage->m_vectorLength;
351
352     Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
353
354     if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
355         for (unsigned j = vectorLength; j < newVectorLength; ++j)
356             storage->m_vector[j] = noValue();
357         if (i > MIN_SPARSE_ARRAY_INDEX)
358             map->remove(i);
359     } else {
360         for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
361             storage->m_vector[j] = noValue();
362         for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
363             storage->m_vector[j] = map->take(j);
364     }
365
366     storage->m_vector[i] = value;
367
368     storage->m_vectorLength = newVectorLength;
369     storage->m_numValuesInVector = newNumValuesInVector;
370
371     m_storage = storage;
372
373     checkConsistency();
374 }
375
376 bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)
377 {
378     bool isArrayIndex;
379     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
380     if (isArrayIndex)
381         return deleteProperty(exec, i);
382
383     if (propertyName == exec->propertyNames().length)
384         return false;
385
386     return JSObject::deleteProperty(exec, propertyName);
387 }
388
389 bool JSArray::deleteProperty(ExecState* exec, unsigned i)
390 {
391     checkConsistency();
392
393     ArrayStorage* storage = m_storage;
394
395     if (i < storage->m_vectorLength) {
396         JSValuePtr& valueSlot = storage->m_vector[i];
397         if (!valueSlot) {
398             checkConsistency();
399             return false;
400         }
401         valueSlot = noValue();
402         --storage->m_numValuesInVector;
403         if (m_fastAccessCutoff > i)
404             m_fastAccessCutoff = i;
405         checkConsistency();
406         return true;
407     }
408
409     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
410         if (i >= MIN_SPARSE_ARRAY_INDEX) {
411             SparseArrayValueMap::iterator it = map->find(i);
412             if (it != map->end()) {
413                 map->remove(it);
414                 checkConsistency();
415                 return true;
416             }
417         }
418     }
419
420     checkConsistency();
421
422     if (i > MAX_ARRAY_INDEX)
423         return deleteProperty(exec, Identifier::from(exec, i));
424
425     return false;
426 }
427
428 void JSArray::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
429 {
430     // FIXME: Filling PropertyNameArray with an identifier for every integer
431     // is incredibly inefficient for large arrays. We need a different approach,
432     // which almost certainly means a different structure for PropertyNameArray.
433
434     ArrayStorage* storage = m_storage;
435
436     unsigned usedVectorLength = min(storage->m_length, storage->m_vectorLength);
437     for (unsigned i = 0; i < usedVectorLength; ++i) {
438         if (storage->m_vector[i])
439             propertyNames.add(Identifier::from(exec, i));
440     }
441
442     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
443         SparseArrayValueMap::iterator end = map->end();
444         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
445             propertyNames.add(Identifier::from(exec, it->first));
446     }
447
448     JSObject::getPropertyNames(exec, propertyNames);
449 }
450
451 bool JSArray::increaseVectorLength(unsigned newLength)
452 {
453     // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
454     // to the vector. Callers have to account for that, because they can do it more efficiently.
455
456     ArrayStorage* storage = m_storage;
457
458     unsigned vectorLength = storage->m_vectorLength;
459     ASSERT(newLength > vectorLength);
460     ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
461     unsigned newVectorLength = increasedVectorLength(newLength);
462
463     storage = static_cast<ArrayStorage*>(tryFastRealloc(storage, storageSize(newVectorLength)));
464     if (!storage)
465         return false;
466
467     Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
468     storage->m_vectorLength = newVectorLength;
469
470     for (unsigned i = vectorLength; i < newVectorLength; ++i)
471         storage->m_vector[i] = noValue();
472
473     m_storage = storage;
474     return true;
475 }
476
477 void JSArray::setLength(unsigned newLength)
478 {
479     checkConsistency();
480
481     ArrayStorage* storage = m_storage;
482
483     unsigned length = m_storage->m_length;
484
485     if (newLength < length) {
486         if (m_fastAccessCutoff > newLength)
487             m_fastAccessCutoff = newLength;
488
489         unsigned usedVectorLength = min(length, storage->m_vectorLength);
490         for (unsigned i = newLength; i < usedVectorLength; ++i) {
491             JSValuePtr& valueSlot = storage->m_vector[i];
492             bool hadValue = valueSlot;
493             valueSlot = noValue();
494             storage->m_numValuesInVector -= hadValue;
495         }
496
497         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
498             SparseArrayValueMap copy = *map;
499             SparseArrayValueMap::iterator end = copy.end();
500             for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
501                 if (it->first >= newLength)
502                     map->remove(it->first);
503             }
504             if (map->isEmpty()) {
505                 delete map;
506                 storage->m_sparseValueMap = 0;
507             }
508         }
509     }
510
511     m_storage->m_length = newLength;
512
513     checkConsistency();
514 }
515
516 JSValuePtr JSArray::pop()
517 {
518     checkConsistency();
519
520     unsigned length = m_storage->m_length;
521     if (!length)
522         return jsUndefined();
523
524     --length;
525
526     JSValuePtr result;
527
528     if (m_fastAccessCutoff > length) {
529         JSValuePtr& valueSlot = m_storage->m_vector[length];
530         result = valueSlot;
531         ASSERT(result);
532         valueSlot = noValue();
533         --m_storage->m_numValuesInVector;
534         m_fastAccessCutoff = length;
535     } else if (length < m_storage->m_vectorLength) {
536         JSValuePtr& valueSlot = m_storage->m_vector[length];
537         result = valueSlot;
538         valueSlot = noValue();
539         if (result)
540             --m_storage->m_numValuesInVector;
541         else
542             result = jsUndefined();
543     } else {
544         result = jsUndefined();
545         if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
546             SparseArrayValueMap::iterator it = map->find(length);
547             if (it != map->end()) {
548                 result = it->second;
549                 map->remove(it);
550                 if (map->isEmpty()) {
551                     delete map;
552                     m_storage->m_sparseValueMap = 0;
553                 }
554             }
555         }
556     }
557
558     m_storage->m_length = length;
559
560     checkConsistency();
561
562     return result;
563 }
564
565 void JSArray::push(ExecState* exec, JSValuePtr value)
566 {
567     checkConsistency();
568
569     if (m_storage->m_length < m_storage->m_vectorLength) {
570         ASSERT(!m_storage->m_vector[m_storage->m_length]);
571         m_storage->m_vector[m_storage->m_length] = value;
572         if (++m_storage->m_numValuesInVector == ++m_storage->m_length)
573             m_fastAccessCutoff = m_storage->m_length;
574         checkConsistency();
575         return;
576     }
577
578     if (m_storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
579         SparseArrayValueMap* map = m_storage->m_sparseValueMap;
580         if (!map || map->isEmpty()) {
581             if (increaseVectorLength(m_storage->m_length + 1)) {
582                 m_storage->m_vector[m_storage->m_length] = value;
583                 if (++m_storage->m_numValuesInVector == ++m_storage->m_length)
584                     m_fastAccessCutoff = m_storage->m_length;
585                 checkConsistency();
586                 return;
587             }
588             checkConsistency();
589             throwOutOfMemoryError(exec);
590             return;
591         }
592     }
593
594     putSlowCase(exec, m_storage->m_length++, value);
595 }
596
597 void JSArray::mark()
598 {
599     JSObject::mark();
600
601     ArrayStorage* storage = m_storage;
602
603     unsigned usedVectorLength = min(storage->m_length, storage->m_vectorLength);
604     for (unsigned i = 0; i < usedVectorLength; ++i) {
605         JSValuePtr value = storage->m_vector[i];
606         if (value && !value.marked())
607             value.mark();
608     }
609
610     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
611         SparseArrayValueMap::iterator end = map->end();
612         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
613             JSValuePtr value = it->second;
614             if (!value.marked())
615                 value.mark();
616         }
617     }
618 }
619
620 static int compareNumbersForQSort(const void* a, const void* b)
621 {
622     double da = static_cast<const JSValuePtr*>(a)->uncheckedGetNumber();
623     double db = static_cast<const JSValuePtr*>(b)->uncheckedGetNumber();
624     return (da > db) - (da < db);
625 }
626
627 typedef std::pair<JSValuePtr, UString> ValueStringPair;
628
629 static int compareByStringPairForQSort(const void* a, const void* b)
630 {
631     const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
632     const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
633     return compare(va->second, vb->second);
634 }
635
636 void JSArray::sortNumeric(ExecState* exec, JSValuePtr compareFunction, CallType callType, const CallData& callData)
637 {
638     unsigned lengthNotIncludingUndefined = compactForSorting();
639     if (m_storage->m_sparseValueMap) {
640         throwOutOfMemoryError(exec);
641         return;
642     }
643
644     if (!lengthNotIncludingUndefined)
645         return;
646         
647     bool allValuesAreNumbers = true;
648     size_t size = m_storage->m_numValuesInVector;
649     for (size_t i = 0; i < size; ++i) {
650         if (!m_storage->m_vector[i].isNumber()) {
651             allValuesAreNumbers = false;
652             break;
653         }
654     }
655
656     if (!allValuesAreNumbers)
657         return sort(exec, compareFunction, callType, callData);
658
659     // For numeric comparison, which is fast, qsort is faster than mergesort. We
660     // also don't require mergesort's stability, since there's no user visible
661     // side-effect from swapping the order of equal primitive values.
662     qsort(m_storage->m_vector, size, sizeof(JSValuePtr), compareNumbersForQSort);
663
664     checkConsistency(SortConsistencyCheck);
665 }
666
667 void JSArray::sort(ExecState* exec)
668 {
669     unsigned lengthNotIncludingUndefined = compactForSorting();
670     if (m_storage->m_sparseValueMap) {
671         throwOutOfMemoryError(exec);
672         return;
673     }
674
675     if (!lengthNotIncludingUndefined)
676         return;
677
678     // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
679     // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
680     // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
681     // random or otherwise changing results, effectively making compare function inconsistent.
682
683     Vector<ValueStringPair> values(lengthNotIncludingUndefined);
684     if (!values.begin()) {
685         throwOutOfMemoryError(exec);
686         return;
687     }
688
689     for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
690         JSValuePtr value = m_storage->m_vector[i];
691         ASSERT(!value.isUndefined());
692         values[i].first = value;
693     }
694
695     // FIXME: While calling these toString functions, the array could be mutated.
696     // In that case, objects pointed to by values in this vector might get garbage-collected!
697
698     // FIXME: The following loop continues to call toString on subsequent values even after
699     // a toString call raises an exception.
700
701     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
702         values[i].second = values[i].first.toString(exec);
703
704     if (exec->hadException())
705         return;
706
707     // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
708     // than O(N log N).
709
710 #if HAVE(MERGESORT)
711     mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
712 #else
713     // FIXME: The qsort library function is likely to not be a stable sort.
714     // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
715     qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
716 #endif
717
718     // FIXME: If the toString function changed the length of the array, this might be
719     // modifying the vector incorrectly.
720
721     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
722         m_storage->m_vector[i] = values[i].first;
723
724     checkConsistency(SortConsistencyCheck);
725 }
726
727 struct AVLTreeNodeForArrayCompare {
728     JSValuePtr value;
729
730     // Child pointers.  The high bit of gt is robbed and used as the
731     // balance factor sign.  The high bit of lt is robbed and used as
732     // the magnitude of the balance factor.
733     int32_t gt;
734     int32_t lt;
735 };
736
737 struct AVLTreeAbstractorForArrayCompare {
738     typedef int32_t handle; // Handle is an index into m_nodes vector.
739     typedef JSValuePtr key;
740     typedef int32_t size;
741
742     Vector<AVLTreeNodeForArrayCompare> m_nodes;
743     ExecState* m_exec;
744     JSValuePtr m_compareFunction;
745     CallType m_compareCallType;
746     const CallData* m_compareCallData;
747     JSValuePtr m_globalThisValue;
748
749     handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
750     void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; }
751     handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; }
752     void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; }
753
754     int get_balance_factor(handle h)
755     {
756         if (m_nodes[h].gt & 0x80000000)
757             return -1;
758         return static_cast<unsigned>(m_nodes[h].lt) >> 31;
759     }
760
761     void set_balance_factor(handle h, int bf)
762     {
763         if (bf == 0) {
764             m_nodes[h].lt &= 0x7FFFFFFF;
765             m_nodes[h].gt &= 0x7FFFFFFF;
766         } else {
767             m_nodes[h].lt |= 0x80000000;
768             if (bf < 0)
769                 m_nodes[h].gt |= 0x80000000;
770             else
771                 m_nodes[h].gt &= 0x7FFFFFFF;
772         }
773     }
774
775     int compare_key_key(key va, key vb)
776     {
777         ASSERT(!va.isUndefined());
778         ASSERT(!vb.isUndefined());
779
780         if (m_exec->hadException())
781             return 1;
782
783         ArgList arguments;
784         arguments.append(va);
785         arguments.append(vb);
786         double compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, m_globalThisValue, arguments).toNumber(m_exec);
787         return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
788     }
789
790     int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
791     int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }
792
793     static handle null() { return 0x7FFFFFFF; }
794 };
795
796 void JSArray::sort(ExecState* exec, JSValuePtr compareFunction, CallType callType, const CallData& callData)
797 {
798     checkConsistency();
799
800     // FIXME: This ignores exceptions raised in the compare function or in toNumber.
801
802     // The maximum tree depth is compiled in - but the caller is clearly up to no good
803     // if a larger array is passed.
804     ASSERT(m_storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
805     if (m_storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
806         return;
807
808     if (!m_storage->m_length)
809         return;
810
811     unsigned usedVectorLength = min(m_storage->m_length, m_storage->m_vectorLength);
812
813     AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
814     tree.abstractor().m_exec = exec;
815     tree.abstractor().m_compareFunction = compareFunction;
816     tree.abstractor().m_compareCallType = callType;
817     tree.abstractor().m_compareCallData = &callData;
818     tree.abstractor().m_globalThisValue = exec->globalThisValue();
819     tree.abstractor().m_nodes.resize(usedVectorLength + (m_storage->m_sparseValueMap ? m_storage->m_sparseValueMap->size() : 0));
820
821     if (!tree.abstractor().m_nodes.begin()) {
822         throwOutOfMemoryError(exec);
823         return;
824     }
825
826     // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
827     // right out from under us while we're building the tree here.
828
829     unsigned numDefined = 0;
830     unsigned numUndefined = 0;
831
832     // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
833     for (; numDefined < usedVectorLength; ++numDefined) {
834         JSValuePtr v = m_storage->m_vector[numDefined];
835         if (!v || v.isUndefined())
836             break;
837         tree.abstractor().m_nodes[numDefined].value = v;
838         tree.insert(numDefined);
839     }
840     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
841         JSValuePtr v = m_storage->m_vector[i];
842         if (v) {
843             if (v.isUndefined())
844                 ++numUndefined;
845             else {
846                 tree.abstractor().m_nodes[numDefined].value = v;
847                 tree.insert(numDefined);
848                 ++numDefined;
849             }
850         }
851     }
852
853     unsigned newUsedVectorLength = numDefined + numUndefined;
854
855     if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
856         newUsedVectorLength += map->size();
857         if (newUsedVectorLength > m_storage->m_vectorLength) {
858             // Check that it is possible to allocate an array large enough to hold all the entries.
859             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) {
860                 throwOutOfMemoryError(exec);
861                 return;
862             }
863         }
864
865         SparseArrayValueMap::iterator end = map->end();
866         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
867             tree.abstractor().m_nodes[numDefined].value = it->second;
868             tree.insert(numDefined);
869             ++numDefined;
870         }
871
872         delete map;
873         m_storage->m_sparseValueMap = 0;
874     }
875
876     ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
877
878     // FIXME: If the compare function changed the length of the array, the following might be
879     // modifying the vector incorrectly.
880
881     // Copy the values back into m_storage.
882     AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
883     iter.start_iter_least(tree);
884     for (unsigned i = 0; i < numDefined; ++i) {
885         m_storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value;
886         ++iter;
887     }
888
889     // Put undefined values back in.
890     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
891         m_storage->m_vector[i] = jsUndefined();
892
893     // Ensure that unused values in the vector are zeroed out.
894     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
895         m_storage->m_vector[i] = noValue();
896
897     m_fastAccessCutoff = newUsedVectorLength;
898     m_storage->m_numValuesInVector = newUsedVectorLength;
899
900     checkConsistency(SortConsistencyCheck);
901 }
902
903 void JSArray::fillArgList(ExecState* exec, ArgList& args)
904 {
905     unsigned fastAccessLength = min(m_storage->m_length, m_fastAccessCutoff);
906     unsigned i = 0;
907     for (; i < fastAccessLength; ++i)
908         args.append(getIndex(i));
909     for (; i < m_storage->m_length; ++i)
910         args.append(get(exec, i));
911 }
912
913 unsigned JSArray::compactForSorting()
914 {
915     checkConsistency();
916
917     ArrayStorage* storage = m_storage;
918
919     unsigned usedVectorLength = min(m_storage->m_length, storage->m_vectorLength);
920
921     unsigned numDefined = 0;
922     unsigned numUndefined = 0;
923
924     for (; numDefined < usedVectorLength; ++numDefined) {
925         JSValuePtr v = storage->m_vector[numDefined];
926         if (!v || v.isUndefined())
927             break;
928     }
929     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
930         JSValuePtr v = storage->m_vector[i];
931         if (v) {
932             if (v.isUndefined())
933                 ++numUndefined;
934             else
935                 storage->m_vector[numDefined++] = v;
936         }
937     }
938
939     unsigned newUsedVectorLength = numDefined + numUndefined;
940
941     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
942         newUsedVectorLength += map->size();
943         if (newUsedVectorLength > storage->m_vectorLength) {
944             // Check that it is possible to allocate an array large enough to hold all the entries - if not,
945             // exception is thrown by caller.
946             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength))
947                 return 0;
948             storage = m_storage;
949         }
950
951         SparseArrayValueMap::iterator end = map->end();
952         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
953             storage->m_vector[numDefined++] = it->second;
954
955         delete map;
956         storage->m_sparseValueMap = 0;
957     }
958
959     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
960         storage->m_vector[i] = jsUndefined();
961     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
962         storage->m_vector[i] = noValue();
963
964     m_fastAccessCutoff = newUsedVectorLength;
965     storage->m_numValuesInVector = newUsedVectorLength;
966
967     checkConsistency(SortConsistencyCheck);
968
969     return numDefined;
970 }
971
972 void* JSArray::lazyCreationData()
973 {
974     return m_storage->lazyCreationData;
975 }
976
977 void JSArray::setLazyCreationData(void* d)
978 {
979     m_storage->lazyCreationData = d;
980 }
981
982 #if CHECK_ARRAY_CONSISTENCY
983
984 void JSArray::checkConsistency(ConsistencyCheckType type)
985 {
986     ASSERT(m_storage);
987     if (type == SortConsistencyCheck)
988         ASSERT(!m_storage->m_sparseValueMap);
989
990     ASSERT(m_fastAccessCutoff <= m_storage->m_length);
991     ASSERT(m_fastAccessCutoff <= m_storage->m_numValuesInVector);
992
993     unsigned numValuesInVector = 0;
994     for (unsigned i = 0; i < m_storage->m_vectorLength; ++i) {
995         if (JSValuePtr value = m_storage->m_vector[i]) {
996             ASSERT(i < m_storage->m_length);
997             if (type != DestructorConsistencyCheck)
998                 value->type(); // Likely to crash if the object was deallocated.
999             ++numValuesInVector;
1000         } else {
1001             ASSERT(i >= m_fastAccessCutoff);
1002             if (type == SortConsistencyCheck)
1003                 ASSERT(i >= m_storage->m_numValuesInVector);
1004         }
1005     }
1006     ASSERT(numValuesInVector == m_storage->m_numValuesInVector);
1007
1008     if (m_storage->m_sparseValueMap) {
1009         SparseArrayValueMap::iterator end = m_storage->m_sparseValueMap->end();
1010         for (SparseArrayValueMap::iterator it = m_storage->m_sparseValueMap->begin(); it != end; ++it) {
1011             unsigned index = it->first;
1012             ASSERT(index < m_storage->m_length);
1013             ASSERT(index >= m_storage->m_vectorLength);
1014             ASSERT(index <= MAX_ARRAY_INDEX);
1015             ASSERT(it->second);
1016             if (type != DestructorConsistencyCheck)
1017                 it->second->type(); // Likely to crash if the object was deallocated.
1018         }
1019     }
1020 }
1021
1022 #endif
1023
1024 JSArray* constructEmptyArray(ExecState* exec)
1025 {
1026     return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure());
1027 }
1028
1029 JSArray* constructEmptyArray(ExecState* exec, unsigned initialLength)
1030 {
1031     return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure(), initialLength);
1032 }
1033
1034 JSArray* constructArray(ExecState* exec, JSValuePtr singleItemValue)
1035 {
1036     ArgList values;
1037     values.append(singleItemValue);
1038     return new (exec) JSArray(exec, exec->lexicalGlobalObject()->arrayStructure(), values);
1039 }
1040
1041 JSArray* constructArray(ExecState* exec, const ArgList& values)
1042 {
1043     return new (exec) JSArray(exec, exec->lexicalGlobalObject()->arrayStructure(), values);
1044 }
1045
1046 } // namespace JSC