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

source code of qtscript/src/3rdparty/javascriptcore/JavaScriptCore/runtime/JSArray.cpp