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 = {.className: "Array" , .parentClass: 0, .staticPropHashTable: 0, .classPropHashTableGetterFunction: 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(a: 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(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 | |
144 | JSArray::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 | |
166 | JSArray::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 | |
189 | JSArray::~JSArray() |
190 | { |
191 | ASSERT(vptr() == JSGlobalData::jsArrayVPtr); |
192 | checkConsistency(DestructorConsistencyCheck); |
193 | |
194 | delete m_storage->m_sparseValueMap; |
195 | fastFree(m_storage); |
196 | } |
197 | |
198 | bool 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 | |
227 | bool 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 | |
242 | bool 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 |
274 | void 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 | |
296 | void 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 | |
322 | NEVER_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 | |
422 | bool 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 | |
435 | bool 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 | |
472 | void 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 | |
498 | bool 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 | |
525 | void 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 | |
561 | JSValue 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 | |
603 | void 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 | |
634 | void JSArray::markChildren(MarkStack& markStack) |
635 | { |
636 | markChildrenDirect(markStack); |
637 | } |
638 | |
639 | static 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 | |
646 | typedef std::pair<JSValue, UString> ValueStringPair; |
647 | |
648 | static 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 | |
655 | void 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 | |
686 | void 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 | |
746 | struct 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 | |
756 | struct 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 | |
824 | void 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 | |
933 | void 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 | |
949 | void 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 | |
967 | unsigned 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 | |
1025 | void* JSArray::lazyCreationData() |
1026 | { |
1027 | return m_storage->lazyCreationData; |
1028 | } |
1029 | |
1030 | void JSArray::setLazyCreationData(void* d) |
1031 | { |
1032 | m_storage->lazyCreationData = d; |
1033 | } |
1034 | |
1035 | #if CHECK_ARRAY_CONSISTENCY |
1036 | |
1037 | void 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 | |