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