0578ed7f083bdfa913817be2c60fc58bd44a2c39
[WebKit-https.git] / JavaScriptCore / kjs / array_instance.cpp
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2003, 2007 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 "array_instance.h"
25
26 #include "JSGlobalObject.h"
27 #include "PropertyNameArray.h"
28 #include <wtf/Assertions.h>
29
30 using std::min;
31
32 namespace KJS {
33
34 typedef HashMap<unsigned, JSValue*> SparseArrayValueMap;
35
36 struct ArrayStorage {
37     unsigned m_numValuesInVector;
38     SparseArrayValueMap* m_sparseValueMap;
39     JSValue* m_vector[1];
40 };
41
42 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer
43 static const unsigned maxArrayIndex = 0xFFFFFFFEU;
44
45 // Our policy for when to use a vector and when to use a sparse map.
46 // For all array indices under sparseArrayCutoff, we always use a vector.
47 // When indices greater than sparseArrayCutoff are involved, we use a vector
48 // as long as it is 1/8 full. If more sparse than that, we use a map.
49 static const unsigned sparseArrayCutoff = 10000;
50 static const unsigned minDensityMultiplier = 8;
51
52 static const unsigned copyingSortCutoff = 50000;
53
54 const ClassInfo ArrayInstance::info = {"Array", 0, 0};
55
56 static inline size_t storageSize(unsigned vectorLength)
57 {
58     return sizeof(ArrayStorage) - sizeof(JSValue*) + vectorLength * sizeof(JSValue*);
59 }
60
61 static inline unsigned increasedVectorLength(unsigned newLength)
62 {
63     return (newLength * 3 + 1) / 2;
64 }
65
66 static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
67 {
68     return length / minDensityMultiplier <= numValues;
69 }
70
71 ArrayInstance::ArrayInstance(JSObject* prototype, unsigned initialLength)
72     : JSObject(prototype)
73 {
74     unsigned initialCapacity = min(initialLength, sparseArrayCutoff);
75
76     m_length = initialLength;
77     m_vectorLength = initialCapacity;
78     m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
79
80     Collector::reportExtraMemoryCost(initialCapacity * sizeof(JSValue*));
81 }
82
83 ArrayInstance::ArrayInstance(JSObject* prototype, const List& list)
84     : JSObject(prototype)
85 {
86     unsigned length = list.size();
87
88     m_length = length;
89     m_vectorLength = length;
90
91     ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(length)));
92
93     storage->m_numValuesInVector = length;
94     storage->m_sparseValueMap = 0;
95
96     size_t i = 0;
97     List::const_iterator end = list.end();
98     for (List::const_iterator it = list.begin(); it != end; ++it, ++i)
99         storage->m_vector[i] = *it;
100
101     m_storage = storage;
102
103     // When the array is created non-empty, its cells are filled, so it's really no worse than
104     // a property map. Therefore don't report extra memory cost.
105 }
106
107 ArrayInstance::~ArrayInstance()
108 {
109     delete m_storage->m_sparseValueMap;
110     fastFree(m_storage);
111 }
112
113 JSValue* ArrayInstance::getItem(unsigned i) const
114 {
115     ASSERT(i <= maxArrayIndex);
116
117     ArrayStorage* storage = m_storage;
118
119     if (i < m_vectorLength) {
120         JSValue* value = storage->m_vector[i];
121         return value ? value : jsUndefined();
122     }
123
124     SparseArrayValueMap* map = storage->m_sparseValueMap;
125     if (!map)
126         return jsUndefined();
127
128     JSValue* value = map->get(i);
129     return value ? value : jsUndefined();
130 }
131
132 JSValue* ArrayInstance::lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot& slot)
133 {
134     return jsNumber(static_cast<ArrayInstance*>(slot.slotBase())->m_length);
135 }
136
137 ALWAYS_INLINE bool ArrayInstance::inlineGetOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
138 {
139     ArrayStorage* storage = m_storage;
140
141     if (i >= m_length) {
142         if (i > maxArrayIndex)
143             return getOwnPropertySlot(exec, Identifier::from(i), slot);
144         return false;
145     }
146
147     if (i < m_vectorLength) {
148         JSValue*& valueSlot = storage->m_vector[i];
149         if (valueSlot) {
150             slot.setValueSlot(this, &valueSlot);
151             return true;
152         }
153     } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
154         if (i >= sparseArrayCutoff) {
155             SparseArrayValueMap::iterator it = map->find(i);
156             if (it != map->end()) {
157                 slot.setValueSlot(this, &it->second);
158                 return true;
159             }
160         }
161     }
162
163     return false;
164 }
165
166 bool ArrayInstance::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
167 {
168     if (propertyName == exec->propertyNames().length) {
169         slot.setCustom(this, lengthGetter);
170         return true;
171     }
172
173     bool isArrayIndex;
174     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
175     if (isArrayIndex)
176         return inlineGetOwnPropertySlot(exec, i, slot);
177
178     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
179 }
180
181 bool ArrayInstance::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
182 {
183     return inlineGetOwnPropertySlot(exec, i, slot);
184 }
185
186 // ECMA 15.4.5.1
187 void ArrayInstance::put(ExecState* exec, const Identifier& propertyName, JSValue* value, int attributes)
188 {
189     bool isArrayIndex;
190     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
191     if (isArrayIndex) {
192         put(exec, i, value, attributes);
193         return;
194     }
195
196     if (propertyName == exec->propertyNames().length) {
197         unsigned newLength = value->toUInt32(exec);
198         if (value->toNumber(exec) != static_cast<double>(newLength)) {
199             throwError(exec, RangeError, "Invalid array length.");
200             return;
201         }
202         setLength(newLength);
203         return;
204     }
205
206     JSObject::put(exec, propertyName, value, attributes);
207 }
208
209 void ArrayInstance::put(ExecState* exec, unsigned i, JSValue* value, int attributes)
210 {
211     if (i > maxArrayIndex) {
212         put(exec, Identifier::from(i), value, attributes);
213         return;
214     }
215
216     ArrayStorage* storage = m_storage;
217
218     unsigned length = m_length;
219     if (i >= length) {
220         length = i + 1;
221         m_length = length;
222     }
223
224     if (i < m_vectorLength) {
225         JSValue*& valueSlot = storage->m_vector[i];
226         storage->m_numValuesInVector += !valueSlot;
227         valueSlot = value;
228         return;
229     }
230
231     if (i < sparseArrayCutoff) {
232         increaseVectorLength(i + 1);
233         storage = m_storage;
234         ++storage->m_numValuesInVector;
235         storage->m_vector[i] = value;
236         return;
237     }
238
239     SparseArrayValueMap* map = storage->m_sparseValueMap;
240     if (!map || map->isEmpty()) {
241         if (isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
242             increaseVectorLength(i + 1);
243             storage = m_storage;
244             ++storage->m_numValuesInVector;
245             storage->m_vector[i] = value;
246             return;
247         }
248         if (!map) {
249             map = new SparseArrayValueMap;
250             storage->m_sparseValueMap = map;
251         }
252         map->set(i, value);
253         return;
254     }
255
256     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
257     if (!isDenseEnoughForVector(i + 1, newNumValuesInVector)) {
258         map->set(i, value);
259         return;
260     }
261
262     unsigned newVectorLength = increasedVectorLength(i + 1);
263     for (unsigned j = m_vectorLength; j < newVectorLength; ++j)
264         newNumValuesInVector += map->contains(j);
265     newNumValuesInVector -= map->contains(i);
266     if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
267         unsigned proposedNewNumValuesInVector = newNumValuesInVector;
268         while (true) {
269             unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
270             for (unsigned j = newVectorLength; j < proposedNewVectorLength; ++j)
271                 proposedNewNumValuesInVector += map->contains(j);
272             if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
273                 break;
274             newVectorLength = proposedNewVectorLength;
275             newNumValuesInVector = proposedNewNumValuesInVector;
276         }
277     }
278
279     storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength)));
280
281     unsigned vectorLength = m_vectorLength;
282     if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
283         for (unsigned j = vectorLength; j < newVectorLength; ++j)
284             storage->m_vector[j] = 0;
285         map->remove(i);
286     } else {
287         for (unsigned j = vectorLength; j < newVectorLength; ++j)
288             storage->m_vector[j] = map->take(j);
289     }
290
291     storage->m_vector[i] = value;
292
293     m_vectorLength = newVectorLength;
294     storage->m_numValuesInVector = newNumValuesInVector;
295 }
296
297 bool ArrayInstance::deleteProperty(ExecState* exec, const Identifier& propertyName)
298 {
299     bool isArrayIndex;
300     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
301     if (isArrayIndex)
302         return deleteProperty(exec, i);
303
304     if (propertyName == exec->propertyNames().length)
305         return false;
306
307     return JSObject::deleteProperty(exec, propertyName);
308 }
309
310 bool ArrayInstance::deleteProperty(ExecState* exec, unsigned i)
311 {
312     ArrayStorage* storage = m_storage;
313
314     if (i < m_vectorLength) {
315         JSValue*& valueSlot = storage->m_vector[i];
316         bool hadValue = valueSlot;
317         valueSlot = 0;
318         storage->m_numValuesInVector -= hadValue;
319         return hadValue;
320     }
321
322     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
323         if (i >= sparseArrayCutoff) {
324             SparseArrayValueMap::iterator it = map->find(i);
325             if (it != map->end()) {
326                 map->remove(it);
327                 return true;
328             }
329         }
330     }
331
332     if (i > maxArrayIndex)
333         return deleteProperty(exec, Identifier::from(i));
334
335     return false;
336 }
337
338 void ArrayInstance::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
339 {
340     // FIXME: Filling PropertyNameArray with an identifier for every integer
341     // is incredibly inefficient for large arrays. We need a different approach.
342
343     ArrayStorage* storage = m_storage;
344
345     unsigned usedVectorLength = min(m_length, m_vectorLength);
346     for (unsigned i = 0; i < usedVectorLength; ++i) {
347         if (storage->m_vector[i])
348             propertyNames.add(Identifier::from(i));
349     }
350
351     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
352         SparseArrayValueMap::iterator end = map->end();
353         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
354             propertyNames.add(Identifier::from(it->first));
355     }
356  
357     JSObject::getPropertyNames(exec, propertyNames);
358 }
359
360 void ArrayInstance::increaseVectorLength(unsigned newLength)
361 {
362     ArrayStorage* storage = m_storage;
363
364     unsigned vectorLength = m_vectorLength;
365     ASSERT(newLength > vectorLength);
366     unsigned newVectorLength = increasedVectorLength(newLength);
367
368     storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength)));
369     m_vectorLength = newVectorLength;
370
371     for (unsigned i = vectorLength; i < newVectorLength; ++i)
372         storage->m_vector[i] = 0;
373
374     m_storage = storage;
375 }
376
377 void ArrayInstance::setLength(unsigned newLength)
378 {
379     ArrayStorage* storage = m_storage;
380
381     unsigned length = m_length;
382
383     if (newLength < length) {
384         unsigned usedVectorLength = min(length, m_vectorLength);
385         for (unsigned i = newLength; i < usedVectorLength; ++i) {
386             JSValue*& valueSlot = storage->m_vector[i];
387             bool hadValue = valueSlot;
388             valueSlot = 0;
389             storage->m_numValuesInVector -= hadValue;
390         }
391
392         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
393             SparseArrayValueMap copy = *map;
394             SparseArrayValueMap::iterator end = copy.end();
395             for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
396                 if (it->first >= newLength)
397                     map->remove(it->first);
398             }
399             if (map->isEmpty()) {
400                 delete map;
401                 storage->m_sparseValueMap = 0;
402             }
403         }
404     }
405   
406     m_length = newLength;
407 }
408
409 void ArrayInstance::mark()
410 {
411     JSObject::mark();
412
413     ArrayStorage* storage = m_storage;
414
415     unsigned usedVectorLength = min(m_length, m_vectorLength);
416     for (unsigned i = 0; i < usedVectorLength; ++i) {
417         JSValue* value = storage->m_vector[i];
418         if (value && !value->marked())
419             value->mark();
420     }
421
422     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
423         SparseArrayValueMap::iterator end = map->end();
424         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
425             JSValue* value = it->second;
426             if (!value->marked())
427                 value->mark();
428         }
429     }
430 }
431
432 static int compareByStringPairForQSort(const void* a, const void* b)
433 {
434     const std::pair<JSValue*, UString>* va = static_cast<const std::pair<JSValue*, UString>*>(a);
435     const std::pair<JSValue*, UString>* vb = static_cast<const std::pair<JSValue*, UString>*>(b);
436     return compare(va->second, vb->second);
437 }
438
439 static ExecState* execForCompareByStringForQSort = 0;
440 static int compareByStringForQSort(const void* a, const void* b)
441 {
442     ExecState* exec = execForCompareByStringForQSort;
443
444     JSValue* va = *static_cast<JSValue* const*>(a);
445     JSValue* vb = *static_cast<JSValue* const*>(b);
446     ASSERT(!va->isUndefined());
447     ASSERT(!vb->isUndefined());
448
449     return compare(va->toString(exec), vb->toString(exec));
450 }
451
452 void ArrayInstance::sort(ExecState* exec)
453 {
454     unsigned lengthNotIncludingUndefined = compactForSorting();
455
456     if (lengthNotIncludingUndefined < copyingSortCutoff) {
457         // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
458         // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
459         // buffer.  For large arrays, we fall back to a qsort on the JavaScriptValues to avoid creating copies.
460
461         Vector<std::pair<JSValue*, UString> > values(lengthNotIncludingUndefined);
462         for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
463             JSValue* value = m_storage->m_vector[i];
464             ASSERT(!value->isUndefined());
465             values[i].first = value;
466             values[i].second = value->toString(exec);
467         }
468
469         // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
470         // than O(N log N).
471
472 #if HAVE(MERGESORT)
473         mergesort(values.begin(), values.size(), sizeof(std::pair<JSValue*, UString>), compareByStringPairForQSort);
474 #else
475         qsort(values.begin(), values.size(), sizeof(std::pair<JSValue*, UString>), compareByStringPairForQSort);
476 #endif
477         for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
478             m_storage->m_vector[i] = values[i].first;
479         return;
480     }
481
482     ExecState* oldExec = execForCompareByStringForQSort;
483     execForCompareByStringForQSort = exec;
484     qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
485     execForCompareByStringForQSort = oldExec;
486 }
487
488 struct CompareWithCompareFunctionArguments {
489     CompareWithCompareFunctionArguments(ExecState *e, JSObject *cf)
490         : exec(e)
491         , compareFunction(cf)
492         , globalObject(e->dynamicGlobalObject())
493     {
494     }
495
496     ExecState *exec;
497     JSObject *compareFunction;
498     List arguments;
499     JSGlobalObject* globalObject;
500 };
501
502 static CompareWithCompareFunctionArguments* compareWithCompareFunctionArguments = 0;
503
504 static int compareWithCompareFunctionForQSort(const void* a, const void* b)
505 {
506     CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments;
507
508     JSValue* va = *static_cast<JSValue* const*>(a);
509     JSValue* vb = *static_cast<JSValue* const*>(b);
510     ASSERT(!va->isUndefined());
511     ASSERT(!vb->isUndefined());
512
513     args->arguments.clear();
514     args->arguments.append(va);
515     args->arguments.append(vb);
516     double compareResult = args->compareFunction->call
517         (args->exec, args->globalObject, args->arguments)->toNumber(args->exec);
518     return compareResult < 0 ? -1 : compareResult > 0 ? 1 : 0;
519 }
520
521 void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction)
522 {
523     size_t lengthNotIncludingUndefined = compactForSorting();
524
525     CompareWithCompareFunctionArguments* oldArgs = compareWithCompareFunctionArguments;
526     CompareWithCompareFunctionArguments args(exec, compareFunction);
527     compareWithCompareFunctionArguments = &args;
528
529 #if HAVE(MERGESORT)
530     // Because mergesort usually does fewer compares, it is faster than qsort here.
531     // However, because it requires extra copies of the storage buffer, don't use it for very
532     // large arrays.
533
534     // FIXME: A tree sort using a perfectly balanced tree (e.g. an AVL tree) could do an even
535     // better job of minimizing compares.
536
537     if (lengthNotIncludingUndefined < copyingSortCutoff) {
538         // During the sort, we could do a garbage collect, and it's important to still
539         // have references to every object in the array for ArrayInstance::mark.
540         // The mergesort algorithm does not guarantee this, so we sort a copy rather
541         // than the original.
542         size_t size = storageSize(m_vectorLength);
543         ArrayStorage* copy = static_cast<ArrayStorage*>(fastMalloc(size));
544         memcpy(copy, m_storage, size);
545         mergesort(copy->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
546         fastFree(m_storage);
547         m_storage = copy;
548         compareWithCompareFunctionArguments = oldArgs;
549         return;
550     }
551 #endif
552
553     qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
554     compareWithCompareFunctionArguments = oldArgs;
555 }
556
557 unsigned ArrayInstance::compactForSorting()
558 {
559     ArrayStorage* storage = m_storage;
560
561     unsigned usedVectorLength = min(m_length, m_vectorLength);
562
563     unsigned numDefined = 0;
564     unsigned numUndefined = 0;
565
566     for (; numDefined < usedVectorLength; ++numDefined) {
567         JSValue* v = storage->m_vector[numDefined];
568         if (!v || v->isUndefined())
569             break;
570     }
571     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
572         if (JSValue* v = storage->m_vector[i]) {
573             if (v->isUndefined())
574                 ++numUndefined;
575             else
576                 storage->m_vector[numDefined++] = v;
577         }
578     }
579
580     unsigned newUsedVectorLength = numDefined + numUndefined;
581
582     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
583         newUsedVectorLength += map->size();
584         if (newUsedVectorLength > m_vectorLength) {
585             increaseVectorLength(newUsedVectorLength);
586             storage = m_storage;
587         }
588
589         SparseArrayValueMap::iterator end = map->end();
590         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
591             storage->m_vector[numDefined++] = it->second;
592
593         delete map;
594         storage->m_sparseValueMap = 0;
595     }
596
597     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
598         storage->m_vector[i] = jsUndefined();
599     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
600         storage->m_vector[i] = 0;
601
602     return numDefined;
603 }
604
605 }