1 /* 2 * Copyright (C) 1999-2000 Harri Porten (porten (at) kde.org) 3 * Copyright (C) 2003, 2007, 2008, 2009 Apple Inc. All rights reserved. 4 * Copyright (C) 2003 Peter Kelly (pmk (at) post.com) 5 * Copyright (C) 2006 Alexey Proskuryakov (ap (at) 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 using namespace std; 37 using namespace WTF; 38 39 namespace JSC { 40 41 ASSERT_CLASS_FITS_IN_CELL(JSArray); 42 43 // Overview of JSArray 44 // 45 // Properties of JSArray objects may be stored in one of three locations: 46 // * The regular JSObject property map. 47 // * A storage vector. 48 // * A sparse map of array entries. 49 // 50 // Properties with non-numeric identifiers, with identifiers that are not representable 51 // as an unsigned integer, or where the value is greater than MAX_ARRAY_INDEX 52 // (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit 53 // integer) are not considered array indices and will be stored in the JSObject property map. 54 // 55 // All properties with a numeric identifer, representable as an unsigned integer i, 56 // where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the 57 // storage vector or the sparse map. An array index i will be handled in the following 58 // fashion: 59 // 60 // * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector. 61 // * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either 62 // be stored in the storage vector or in the sparse array, depending on the density of 63 // data that would be stored in the vector (a vector being used where at least 64 // (1 / minDensityMultiplier) of the entries would be populated). 65 // * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored 66 // in the sparse array. 67 68 // The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize 69 // function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage 70 // size calculation cannot overflow. (sizeof(ArrayStorage) - sizeof(JSValue)) + 71 // (vectorLength * sizeof(JSValue)) must be <= 0xFFFFFFFFU (which is maximum value of size_t). 72 #define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue)) 73 74 // These values have to be macros to be used in max() and min() without introducing 75 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>. 76 #define MIN_SPARSE_ARRAY_INDEX 10000U 77 #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1) 78 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer. 79 #define MAX_ARRAY_INDEX 0xFFFFFFFEU 80 81 // The value BASE_VECTOR_LEN is the maximum number of vector elements we'll allocate 82 // for an array that was created with a sepcified length (e.g. a = new Array(123)) 83 #define BASE_VECTOR_LEN 4U 84 85 // The upper bound to the size we'll grow a zero length array when the first element 86 // is added. 87 #define FIRST_VECTOR_GROW 4U 88 89 // Our policy for when to use a vector and when to use a sparse map. 90 // For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector. 91 // When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector 92 // as long as it is 1/8 full. If more sparse than that, we use a map. 93 static const unsigned minDensityMultiplier = 8; 94 95 const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0}; 96 97 // We keep track of the size of the last array after it was grown. We use this 98 // as a simple heuristic for as the value to grow the next array from size 0. 99 // This value is capped by the constant FIRST_VECTOR_GROW defined above. 100 static unsigned lastArraySize = 0; 101 102 static inline size_t storageSize(unsigned vectorLength) 103 { 104 ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH); 105 106 // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH) 107 // - as asserted above - the following calculation cannot overflow. 108 size_t size = (sizeof(ArrayStorage) - sizeof(JSValue)) + (vectorLength * sizeof(JSValue)); 109 // Assertion to detect integer overflow in previous calculation (should not be possible, provided that 110 // MAX_STORAGE_VECTOR_LENGTH is correctly defined). 111 ASSERT(((size - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValue)))); 112 113 return size; 114 } 115 116 static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues) 117 { 118 return length / minDensityMultiplier <= numValues; 119 } 120 121 #if !CHECK_ARRAY_CONSISTENCY 122 123 inline void JSArray::checkConsistency(ConsistencyCheckType) 124 { 125 } 126 127 #endif 128 129 JSArray::JSArray(VPtrStealingHackType) 130 : JSNonFinalObject(VPtrStealingHack) 131 { 132 } 133 134 JSArray::JSArray(JSGlobalData& globalData, Structure* structure) 135 : JSNonFinalObject(globalData, structure) 136 { 137 ASSERT(inherits(&s_info)); 138 139 unsigned initialCapacity = 0; 140 141 m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity))); 142 m_storage->m_allocBase = m_storage; 143 m_indexBias = 0; 144 m_vectorLength = initialCapacity; 145 146 checkConsistency(); 147 148 Heap::heap(this)->reportExtraMemoryCost(storageSize(0)); 149 } 150 151 JSArray::JSArray(JSGlobalData& globalData, Structure* structure, unsigned initialLength, ArrayCreationMode creationMode) 152 : JSNonFinalObject(globalData, structure) 153 { 154 ASSERT(inherits(&s_info)); 155 156 unsigned initialCapacity; 157 if (creationMode == CreateCompact) 158 initialCapacity = initialLength; 159 else 160 initialCapacity = min(BASE_VECTOR_LEN, MIN_SPARSE_ARRAY_INDEX); 161 162 m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity))); 163 m_storage->m_allocBase = m_storage; 164 m_storage->m_length = initialLength; 165 m_indexBias = 0; 166 m_vectorLength = initialCapacity; 167 m_storage->m_sparseValueMap = 0; 168 m_storage->subclassData = 0; 169 m_storage->reportedMapCapacity = 0; 170 171 if (creationMode == CreateCompact) { 172 #if CHECK_ARRAY_CONSISTENCY 173 m_storage->m_inCompactInitialization = !!initialCapacity; 174 #endif 175 m_storage->m_length = 0; 176 m_storage->m_numValuesInVector = initialCapacity; 177 } else { 178 #if CHECK_ARRAY_CONSISTENCY 179 storage->m_inCompactInitialization = false; 180 #endif 181 m_storage->m_length = initialLength; 182 m_storage->m_numValuesInVector = 0; 183 WriteBarrier<Unknown>* vector = m_storage->m_vector; 184 for (size_t i = 0; i < initialCapacity; ++i) 185 vector[i].clear(); 186 } 187 188 checkConsistency(); 189 190 Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity)); 191 } 192 193 JSArray::JSArray(JSGlobalData& globalData, Structure* structure, const ArgList& list) 194 : JSNonFinalObject(globalData, structure) 195 { 196 ASSERT(inherits(&s_info)); 197 198 unsigned initialCapacity = list.size(); 199 unsigned initialStorage; 200 201 // If the ArgList is empty, allocate space for 3 entries. This value empirically 202 // works well for benchmarks. 203 if (!initialCapacity) 204 initialStorage = 3; 205 else 206 initialStorage = initialCapacity; 207 208 m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialStorage))); 209 m_storage->m_allocBase = m_storage; 210 m_indexBias = 0; 211 m_storage->m_length = initialCapacity; 212 m_vectorLength = initialStorage; 213 m_storage->m_numValuesInVector = initialCapacity; 214 m_storage->m_sparseValueMap = 0; 215 m_storage->subclassData = 0; 216 m_storage->reportedMapCapacity = 0; 217 #if CHECK_ARRAY_CONSISTENCY 218 m_storage->m_inCompactInitialization = false; 219 #endif 220 221 size_t i = 0; 222 WriteBarrier<Unknown>* vector = m_storage->m_vector; 223 ArgList::const_iterator end = list.end(); 224 for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i) 225 vector[i].set(globalData, this, *it); 226 for (; i < initialStorage; i++) 227 vector[i].clear(); 228 229 checkConsistency(); 230 231 Heap::heap(this)->reportExtraMemoryCost(storageSize(initialStorage)); 232 } 233 234 JSArray::~JSArray() 235 { 236 ASSERT(vptr() == JSGlobalData::jsArrayVPtr); 237 checkConsistency(DestructorConsistencyCheck); 238 239 delete m_storage->m_sparseValueMap; 240 fastFree(m_storage->m_allocBase); 241 } 242 243 bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot) 244 { 245 ArrayStorage* storage = m_storage; 246 247 if (i >= storage->m_length) { 248 if (i > MAX_ARRAY_INDEX) 249 return getOwnPropertySlot(exec, Identifier::from(exec, i), slot); 250 return false; 251 } 252 253 if (i < m_vectorLength) { 254 JSValue value = storage->m_vector[i].get(); 255 if (value) { 256 slot.setValue(value); 257 return true; 258 } 259 } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) { 260 if (i >= MIN_SPARSE_ARRAY_INDEX) { 261 SparseArrayValueMap::iterator it = map->find(i); 262 if (it != map->end()) { 263 slot.setValue(it->second.get()); 264 return true; 265 } 266 } 267 } 268 269 return JSObject::getOwnPropertySlot(exec, Identifier::from(exec, i), slot); 270 } 271 272 bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot) 273 { 274 if (propertyName == exec->propertyNames().length) { 275 slot.setValue(jsNumber(length())); 276 return true; 277 } 278 279 bool isArrayIndex; 280 unsigned i = propertyName.toArrayIndex(isArrayIndex); 281 if (isArrayIndex) 282 return JSArray::getOwnPropertySlot(exec, i, slot); 283 284 return JSObject::getOwnPropertySlot(exec, propertyName, slot); 285 } 286 287 bool JSArray::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor) 288 { 289 if (propertyName == exec->propertyNames().length) { 290 descriptor.setDescriptor(jsNumber(length()), DontDelete | DontEnum); 291 return true; 292 } 293 294 ArrayStorage* storage = m_storage; 295 296 bool isArrayIndex; 297 unsigned i = propertyName.toArrayIndex(isArrayIndex); 298 if (isArrayIndex) { 299 if (i >= storage->m_length) 300 return false; 301 if (i < m_vectorLength) { 302 WriteBarrier<Unknown>& value = storage->m_vector[i]; 303 if (value) { 304 descriptor.setDescriptor(value.get(), 0); 305 return true; 306 } 307 } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) { 308 if (i >= MIN_SPARSE_ARRAY_INDEX) { 309 SparseArrayValueMap::iterator it = map->find(i); 310 if (it != map->end()) { 311 descriptor.setDescriptor(it->second.get(), 0); 312 return true; 313 } 314 } 315 } 316 } 317 return JSObject::getOwnPropertyDescriptor(exec, propertyName, descriptor); 318 } 319 320 // ECMA 15.4.5.1 321 void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot) 322 { 323 bool isArrayIndex; 324 unsigned i = propertyName.toArrayIndex(isArrayIndex); 325 if (isArrayIndex) { 326 put(exec, i, value); 327 return; 328 } 329 330 if (propertyName == exec->propertyNames().length) { 331 unsigned newLength = value.toUInt32(exec); 332 if (value.toNumber(exec) != static_cast<double>(newLength)) { 333 throwError(exec, createRangeError(exec, "Invalid array length.")); 334 return; 335 } 336 setLength(newLength); 337 return; 338 } 339 340 JSObject::put(exec, propertyName, value, slot); 341 } 342 343 void JSArray::put(ExecState* exec, unsigned i, JSValue value) 344 { 345 checkConsistency(); 346 347 ArrayStorage* storage = m_storage; 348 349 unsigned length = storage->m_length; 350 if (i >= length && i <= MAX_ARRAY_INDEX) { 351 length = i + 1; 352 storage->m_length = length; 353 } 354 355 if (i < m_vectorLength) { 356 WriteBarrier<Unknown>& valueSlot = storage->m_vector[i]; 357 if (valueSlot) { 358 valueSlot.set(exec->globalData(), this, value); 359 checkConsistency(); 360 return; 361 } 362 valueSlot.set(exec->globalData(), this, value); 363 ++storage->m_numValuesInVector; 364 checkConsistency(); 365 return; 366 } 367 368 putSlowCase(exec, i, value); 369 } 370 371 NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value) 372 { 373 ArrayStorage* storage = m_storage; 374 375 SparseArrayValueMap* map = storage->m_sparseValueMap; 376 377 if (i >= MIN_SPARSE_ARRAY_INDEX) { 378 if (i > MAX_ARRAY_INDEX) { 379 PutPropertySlot slot; 380 put(exec, Identifier::from(exec, i), value, slot); 381 return; 382 } 383 384 // We miss some cases where we could compact the storage, such as a large array that is being filled from the end 385 // (which will only be compacted as we reach indices that are less than MIN_SPARSE_ARRAY_INDEX) - but this makes the check much faster. 386 if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) { 387 if (!map) { 388 map = new SparseArrayValueMap; 389 storage->m_sparseValueMap = map; 390 } 391 392 WriteBarrier<Unknown> temp; 393 pair<SparseArrayValueMap::iterator, bool> result = map->add(i, temp); 394 result.first->second.set(exec->globalData(), this, value); 395 if (!result.second) // pre-existing entry 396 return; 397 398 size_t capacity = map->capacity(); 399 if (capacity != storage->reportedMapCapacity) { 400 Heap::heap(this)->reportExtraMemoryCost((capacity - storage->reportedMapCapacity) * (sizeof(unsigned) + sizeof(JSValue))); 401 storage->reportedMapCapacity = capacity; 402 } 403 return; 404 } 405 } 406 407 // We have decided that we'll put the new item into the vector. 408 // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it. 409 if (!map || map->isEmpty()) { 410 if (increaseVectorLength(i + 1)) { 411 storage = m_storage; 412 storage->m_vector[i].set(exec->globalData(), this, value); 413 ++storage->m_numValuesInVector; 414 checkConsistency(); 415 } else 416 throwOutOfMemoryError(exec); 417 return; 418 } 419 420 // Decide how many values it would be best to move from the map. 421 unsigned newNumValuesInVector = storage->m_numValuesInVector + 1; 422 unsigned newVectorLength = getNewVectorLength(i + 1); 423 for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j) 424 newNumValuesInVector += map->contains(j); 425 if (i >= MIN_SPARSE_ARRAY_INDEX) 426 newNumValuesInVector -= map->contains(i); 427 if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) { 428 unsigned needLength = max(i + 1, storage->m_length); 429 unsigned proposedNewNumValuesInVector = newNumValuesInVector; 430 // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further. 431 while ((newVectorLength < needLength) && (newVectorLength < MAX_STORAGE_VECTOR_LENGTH)) { 432 unsigned proposedNewVectorLength = getNewVectorLength(newVectorLength + 1); 433 for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j) 434 proposedNewNumValuesInVector += map->contains(j); 435 if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector)) 436 break; 437 newVectorLength = proposedNewVectorLength; 438 newNumValuesInVector = proposedNewNumValuesInVector; 439 } 440 } 441 442 void* baseStorage = storage->m_allocBase; 443 444 if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) { 445 throwOutOfMemoryError(exec); 446 return; 447 } 448 449 m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue)); 450 m_storage->m_allocBase = baseStorage; 451 storage = m_storage; 452 453 unsigned vectorLength = m_vectorLength; 454 WriteBarrier<Unknown>* vector = storage->m_vector; 455 456 if (newNumValuesInVector == storage->m_numValuesInVector + 1) { 457 for (unsigned j = vectorLength; j < newVectorLength; ++j) 458 vector[j].clear(); 459 if (i > MIN_SPARSE_ARRAY_INDEX) 460 map->remove(i); 461 } else { 462 for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j) 463 vector[j].clear(); 464 JSGlobalData& globalData = exec->globalData(); 465 for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j) 466 vector[j].set(globalData, this, map->take(j).get()); 467 } 468 469 ASSERT(i < newVectorLength); 470 471 m_vectorLength = newVectorLength; 472 storage->m_numValuesInVector = newNumValuesInVector; 473 474 storage->m_vector[i].set(exec->globalData(), this, value); 475 476 checkConsistency(); 477 478 Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); 479 } 480 481 bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName) 482 { 483 bool isArrayIndex; 484 unsigned i = propertyName.toArrayIndex(isArrayIndex); 485 if (isArrayIndex) 486 return deleteProperty(exec, i); 487 488 if (propertyName == exec->propertyNames().length) 489 return false; 490 491 return JSObject::deleteProperty(exec, propertyName); 492 } 493 494 bool JSArray::deleteProperty(ExecState* exec, unsigned i) 495 { 496 checkConsistency(); 497 498 ArrayStorage* storage = m_storage; 499 500 if (i < m_vectorLength) { 501 WriteBarrier<Unknown>& valueSlot = storage->m_vector[i]; 502 if (!valueSlot) { 503 checkConsistency(); 504 return false; 505 } 506 valueSlot.clear(); 507 --storage->m_numValuesInVector; 508 checkConsistency(); 509 return true; 510 } 511 512 if (SparseArrayValueMap* map = storage->m_sparseValueMap) { 513 if (i >= MIN_SPARSE_ARRAY_INDEX) { 514 SparseArrayValueMap::iterator it = map->find(i); 515 if (it != map->end()) { 516 map->remove(it); 517 checkConsistency(); 518 return true; 519 } 520 } 521 } 522 523 checkConsistency(); 524 525 if (i > MAX_ARRAY_INDEX) 526 return deleteProperty(exec, Identifier::from(exec, i)); 527 528 return false; 529 } 530 531 void JSArray::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode) 532 { 533 // FIXME: Filling PropertyNameArray with an identifier for every integer 534 // is incredibly inefficient for large arrays. We need a different approach, 535 // which almost certainly means a different structure for PropertyNameArray. 536 537 ArrayStorage* storage = m_storage; 538 539 unsigned usedVectorLength = min(storage->m_length, m_vectorLength); 540 for (unsigned i = 0; i < usedVectorLength; ++i) { 541 if (storage->m_vector[i]) 542 propertyNames.add(Identifier::from(exec, i)); 543 } 544 545 if (SparseArrayValueMap* map = storage->m_sparseValueMap) { 546 SparseArrayValueMap::iterator end = map->end(); 547 for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) 548 propertyNames.add(Identifier::from(exec, it->first)); 549 } 550 551 if (mode == IncludeDontEnumProperties) 552 propertyNames.add(exec->propertyNames().length); 553 554 JSObject::getOwnPropertyNames(exec, propertyNames, mode); 555 } 556 557 ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength) 558 { 559 ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH); 560 561 unsigned increasedLength; 562 unsigned maxInitLength = min(m_storage->m_length, 100000U); 563 564 if (desiredLength < maxInitLength) 565 increasedLength = maxInitLength; 566 else if (!m_vectorLength) 567 increasedLength = max(desiredLength, lastArraySize); 568 else { 569 // Mathematically equivalent to: 570 // increasedLength = (newLength * 3 + 1) / 2; 571 // or: 572 // increasedLength = (unsigned)ceil(newLength * 1.5)); 573 // This form is not prone to internal overflow. 574 increasedLength = desiredLength + (desiredLength >> 1) + (desiredLength & 1); 575 } 576 577 ASSERT(increasedLength >= desiredLength); 578 579 lastArraySize = min(increasedLength, FIRST_VECTOR_GROW); 580 581 return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH); 582 } 583 584 bool JSArray::increaseVectorLength(unsigned newLength) 585 { 586 // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map 587 // to the vector. Callers have to account for that, because they can do it more efficiently. 588 589 ArrayStorage* storage = m_storage; 590 591 unsigned vectorLength = m_vectorLength; 592 ASSERT(newLength > vectorLength); 593 ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX); 594 unsigned newVectorLength = getNewVectorLength(newLength); 595 void* baseStorage = storage->m_allocBase; 596 597 if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) 598 return false; 599 600 storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue)); 601 m_storage->m_allocBase = baseStorage; 602 603 WriteBarrier<Unknown>* vector = storage->m_vector; 604 for (unsigned i = vectorLength; i < newVectorLength; ++i) 605 vector[i].clear(); 606 607 m_vectorLength = newVectorLength; 608 609 Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); 610 611 return true; 612 } 613 614 bool JSArray::increaseVectorPrefixLength(unsigned newLength) 615 { 616 // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map 617 // to the vector. Callers have to account for that, because they can do it more efficiently. 618 619 ArrayStorage* storage = m_storage; 620 621 unsigned vectorLength = m_vectorLength; 622 ASSERT(newLength > vectorLength); 623 ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX); 624 unsigned newVectorLength = getNewVectorLength(newLength); 625 626 void* newBaseStorage = fastMalloc(storageSize(newVectorLength + m_indexBias)); 627 if (!newBaseStorage) 628 return false; 629 630 m_indexBias += newVectorLength - newLength; 631 632 m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(newBaseStorage) + m_indexBias * sizeof(JSValue)); 633 634 memcpy(m_storage, storage, storageSize(0)); 635 memcpy(&m_storage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], vectorLength * sizeof(JSValue)); 636 637 m_storage->m_allocBase = newBaseStorage; 638 m_vectorLength = newLength; 639 640 fastFree(storage->m_allocBase); 641 642 Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength)); 643 644 return true; 645 } 646 647 648 void JSArray::setLength(unsigned newLength) 649 { 650 ArrayStorage* storage = m_storage; 651 652 #if CHECK_ARRAY_CONSISTENCY 653 if (!storage->m_inCompactInitialization) 654 checkConsistency(); 655 else 656 storage->m_inCompactInitialization = false; 657 #endif 658 659 unsigned length = storage->m_length; 660 661 if (newLength < length) { 662 unsigned usedVectorLength = min(length, m_vectorLength); 663 for (unsigned i = newLength; i < usedVectorLength; ++i) { 664 WriteBarrier<Unknown>& valueSlot = storage->m_vector[i]; 665 bool hadValue = valueSlot; 666 valueSlot.clear(); 667 storage->m_numValuesInVector -= hadValue; 668 } 669 670 if (SparseArrayValueMap* map = storage->m_sparseValueMap) { 671 SparseArrayValueMap copy = *map; 672 SparseArrayValueMap::iterator end = copy.end(); 673 for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) { 674 if (it->first >= newLength) 675 map->remove(it->first); 676 } 677 if (map->isEmpty()) { 678 delete map; 679 storage->m_sparseValueMap = 0; 680 } 681 } 682 } 683 684 storage->m_length = newLength; 685 686 checkConsistency(); 687 } 688 689 JSValue JSArray::pop() 690 { 691 checkConsistency(); 692 693 ArrayStorage* storage = m_storage; 694 695 unsigned length = storage->m_length; 696 if (!length) 697 return jsUndefined(); 698 699 --length; 700 701 JSValue result; 702 703 if (length < m_vectorLength) { 704 WriteBarrier<Unknown>& valueSlot = storage->m_vector[length]; 705 if (valueSlot) { 706 --storage->m_numValuesInVector; 707 result = valueSlot.get(); 708 valueSlot.clear(); 709 } else 710 result = jsUndefined(); 711 } else { 712 result = jsUndefined(); 713 if (SparseArrayValueMap* map = storage->m_sparseValueMap) { 714 SparseArrayValueMap::iterator it = map->find(length); 715 if (it != map->end()) { 716 result = it->second.get(); 717 map->remove(it); 718 if (map->isEmpty()) { 719 delete map; 720 storage->m_sparseValueMap = 0; 721 } 722 } 723 } 724 } 725 726 storage->m_length = length; 727 728 checkConsistency(); 729 730 return result; 731 } 732 733 void JSArray::push(ExecState* exec, JSValue value) 734 { 735 checkConsistency(); 736 737 ArrayStorage* storage = m_storage; 738 739 if (storage->m_length < m_vectorLength) { 740 storage->m_vector[storage->m_length].set(exec->globalData(), this, value); 741 ++storage->m_numValuesInVector; 742 ++storage->m_length; 743 checkConsistency(); 744 return; 745 } 746 747 if (storage->m_length < MIN_SPARSE_ARRAY_INDEX) { 748 SparseArrayValueMap* map = storage->m_sparseValueMap; 749 if (!map || map->isEmpty()) { 750 if (increaseVectorLength(storage->m_length + 1)) { 751 storage = m_storage; 752 storage->m_vector[storage->m_length].set(exec->globalData(), this, value); 753 ++storage->m_numValuesInVector; 754 ++storage->m_length; 755 checkConsistency(); 756 return; 757 } 758 checkConsistency(); 759 throwOutOfMemoryError(exec); 760 return; 761 } 762 } 763 764 putSlowCase(exec, storage->m_length++, value); 765 } 766 767 void JSArray::shiftCount(ExecState* exec, int count) 768 { 769 ASSERT(count > 0); 770 771 ArrayStorage* storage = m_storage; 772 773 unsigned oldLength = storage->m_length; 774 775 if (!oldLength) 776 return; 777 778 if (oldLength != storage->m_numValuesInVector) { 779 // If m_length and m_numValuesInVector aren't the same, we have a sparse vector 780 // which means we need to go through each entry looking for the the "empty" 781 // slots and then fill them with possible properties. See ECMA spec. 782 // 15.4.4.9 steps 11 through 13. 783 for (unsigned i = count; i < oldLength; ++i) { 784 if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) { 785 PropertySlot slot(this); 786 JSValue p = prototype(); 787 if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot))) 788 put(exec, i, slot.getValue(exec, i)); 789 } 790 } 791 792 storage = m_storage; // The put() above could have grown the vector and realloc'ed storage. 793 794 // Need to decrement numValuesInvector based on number of real entries 795 for (unsigned i = 0; i < (unsigned)count; ++i) 796 if ((i < m_vectorLength) && (storage->m_vector[i])) 797 --storage->m_numValuesInVector; 798 } else 799 storage->m_numValuesInVector -= count; 800 801 storage->m_length -= count; 802 803 if (m_vectorLength) { 804 count = min(m_vectorLength, (unsigned)count); 805 806 m_vectorLength -= count; 807 808 if (m_vectorLength) { 809 char* newBaseStorage = reinterpret_cast<char*>(storage) + count * sizeof(JSValue); 810 memmove(newBaseStorage, storage, storageSize(0)); 811 m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage); 812 813 m_indexBias += count; 814 } 815 } 816 } 817 818 void JSArray::unshiftCount(ExecState* exec, int count) 819 { 820 ArrayStorage* storage = m_storage; 821 822 ASSERT(m_indexBias >= 0); 823 ASSERT(count >= 0); 824 825 unsigned length = storage->m_length; 826 827 if (length != storage->m_numValuesInVector) { 828 // If m_length and m_numValuesInVector aren't the same, we have a sparse vector 829 // which means we need to go through each entry looking for the the "empty" 830 // slots and then fill them with possible properties. See ECMA spec. 831 // 15.4.4.13 steps 8 through 10. 832 for (unsigned i = 0; i < length; ++i) { 833 if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) { 834 PropertySlot slot(this); 835 JSValue p = prototype(); 836 if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot))) 837 put(exec, i, slot.getValue(exec, i)); 838 } 839 } 840 } 841 842 storage = m_storage; // The put() above could have grown the vector and realloc'ed storage. 843 844 if (m_indexBias >= count) { 845 m_indexBias -= count; 846 char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(JSValue); 847 memmove(newBaseStorage, storage, storageSize(0)); 848 m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage); 849 m_vectorLength += count; 850 } else if (!increaseVectorPrefixLength(m_vectorLength + count)) { 851 throwOutOfMemoryError(exec); 852 return; 853 } 854 855 WriteBarrier<Unknown>* vector = m_storage->m_vector; 856 for (int i = 0; i < count; i++) 857 vector[i].clear(); 858 } 859 860 void JSArray::markChildren(MarkStack& markStack) 861 { 862 markChildrenDirect(markStack); 863 } 864 865 static int compareNumbersForQSort(const void* a, const void* b) 866 { 867 double da = static_cast<const JSValue*>(a)->uncheckedGetNumber(); 868 double db = static_cast<const JSValue*>(b)->uncheckedGetNumber(); 869 return (da > db) - (da < db); 870 } 871 872 static int compareByStringPairForQSort(const void* a, const void* b) 873 { 874 const ValueStringPair* va = static_cast<const ValueStringPair*>(a); 875 const ValueStringPair* vb = static_cast<const ValueStringPair*>(b); 876 return codePointCompare(va->second, vb->second); 877 } 878 879 void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) 880 { 881 ArrayStorage* storage = m_storage; 882 883 unsigned lengthNotIncludingUndefined = compactForSorting(); 884 if (storage->m_sparseValueMap) { 885 throwOutOfMemoryError(exec); 886 return; 887 } 888 889 if (!lengthNotIncludingUndefined) 890 return; 891 892 bool allValuesAreNumbers = true; 893 size_t size = storage->m_numValuesInVector; 894 for (size_t i = 0; i < size; ++i) { 895 if (!storage->m_vector[i].isNumber()) { 896 allValuesAreNumbers = false; 897 break; 898 } 899 } 900 901 if (!allValuesAreNumbers) 902 return sort(exec, compareFunction, callType, callData); 903 904 // For numeric comparison, which is fast, qsort is faster than mergesort. We 905 // also don't require mergesort's stability, since there's no user visible 906 // side-effect from swapping the order of equal primitive values. 907 qsort(storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort); 908 909 checkConsistency(SortConsistencyCheck); 910 } 911 912 void JSArray::sort(ExecState* exec) 913 { 914 ArrayStorage* storage = m_storage; 915 916 unsigned lengthNotIncludingUndefined = compactForSorting(); 917 if (storage->m_sparseValueMap) { 918 throwOutOfMemoryError(exec); 919 return; 920 } 921 922 if (!lengthNotIncludingUndefined) 923 return; 924 925 // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that. 926 // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary 927 // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return 928 // random or otherwise changing results, effectively making compare function inconsistent. 929 930 Vector<ValueStringPair> values(lengthNotIncludingUndefined); 931 if (!values.begin()) { 932 throwOutOfMemoryError(exec); 933 return; 934 } 935 936 Heap::heap(this)->pushTempSortVector(&values); 937 938 for (size_t i = 0; i < lengthNotIncludingUndefined; i++) { 939 JSValue value = storage->m_vector[i].get(); 940 ASSERT(!value.isUndefined()); 941 values[i].first = value; 942 } 943 944 // FIXME: The following loop continues to call toString on subsequent values even after 945 // a toString call raises an exception. 946 947 for (size_t i = 0; i < lengthNotIncludingUndefined; i++) 948 values[i].second = values[i].first.toString(exec); 949 950 if (exec->hadException()) { 951 Heap::heap(this)->popTempSortVector(&values); 952 return; 953 } 954 955 // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather 956 // than O(N log N). 957 958 #if HAVE(MERGESORT) 959 mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort); 960 #else 961 // FIXME: The qsort library function is likely to not be a stable sort. 962 // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort. 963 qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort); 964 #endif 965 966 // If the toString function changed the length of the array or vector storage, 967 // increase the length to handle the orignal number of actual values. 968 if (m_vectorLength < lengthNotIncludingUndefined) 969 increaseVectorLength(lengthNotIncludingUndefined); 970 if (storage->m_length < lengthNotIncludingUndefined) 971 storage->m_length = lengthNotIncludingUndefined; 972 973 JSGlobalData& globalData = exec->globalData(); 974 for (size_t i = 0; i < lengthNotIncludingUndefined; i++) 975 storage->m_vector[i].set(globalData, this, values[i].first); 976 977 Heap::heap(this)->popTempSortVector(&values); 978 979 checkConsistency(SortConsistencyCheck); 980 } 981 982 struct AVLTreeNodeForArrayCompare { 983 JSValue value; 984 985 // Child pointers. The high bit of gt is robbed and used as the 986 // balance factor sign. The high bit of lt is robbed and used as 987 // the magnitude of the balance factor. 988 int32_t gt; 989 int32_t lt; 990 }; 991 992 struct AVLTreeAbstractorForArrayCompare { 993 typedef int32_t handle; // Handle is an index into m_nodes vector. 994 typedef JSValue key; 995 typedef int32_t size; 996 997 Vector<AVLTreeNodeForArrayCompare> m_nodes; 998 ExecState* m_exec; 999 JSValue m_compareFunction; 1000 CallType m_compareCallType; 1001 const CallData* m_compareCallData; 1002 JSValue m_globalThisValue; 1003 OwnPtr<CachedCall> m_cachedCall; 1004 1005 handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; } 1006 void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; } 1007 handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; } 1008 void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; } 1009 1010 int get_balance_factor(handle h) 1011 { 1012 if (m_nodes[h].gt & 0x80000000) 1013 return -1; 1014 return static_cast<unsigned>(m_nodes[h].lt) >> 31; 1015 } 1016 1017 void set_balance_factor(handle h, int bf) 1018 { 1019 if (bf == 0) { 1020 m_nodes[h].lt &= 0x7FFFFFFF; 1021 m_nodes[h].gt &= 0x7FFFFFFF; 1022 } else { 1023 m_nodes[h].lt |= 0x80000000; 1024 if (bf < 0) 1025 m_nodes[h].gt |= 0x80000000; 1026 else 1027 m_nodes[h].gt &= 0x7FFFFFFF; 1028 } 1029 } 1030 1031 int compare_key_key(key va, key vb) 1032 { 1033 ASSERT(!va.isUndefined()); 1034 ASSERT(!vb.isUndefined()); 1035 1036 if (m_exec->hadException()) 1037 return 1; 1038 1039 double compareResult; 1040 if (m_cachedCall) { 1041 m_cachedCall->setThis(m_globalThisValue); 1042 m_cachedCall->setArgument(0, va); 1043 m_cachedCall->setArgument(1, vb); 1044 compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec)); 1045 } else { 1046 MarkedArgumentBuffer arguments; 1047 arguments.append(va); 1048 arguments.append(vb); 1049 compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, m_globalThisValue, arguments).toNumber(m_exec); 1050 } 1051 return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent. 1052 } 1053 1054 int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); } 1055 int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); } 1056 1057 static handle null() { return 0x7FFFFFFF; } 1058 }; 1059 1060 void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) 1061 { 1062 checkConsistency(); 1063 1064 ArrayStorage* storage = m_storage; 1065 1066 // FIXME: This ignores exceptions raised in the compare function or in toNumber. 1067 1068 // The maximum tree depth is compiled in - but the caller is clearly up to no good 1069 // if a larger array is passed. 1070 ASSERT(storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max())); 1071 if (storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max())) 1072 return; 1073 1074 unsigned usedVectorLength = min(storage->m_length, m_vectorLength); 1075 unsigned nodeCount = usedVectorLength + (storage->m_sparseValueMap ? storage->m_sparseValueMap->size() : 0); 1076 1077 if (!nodeCount) 1078 return; 1079 1080 AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items 1081 tree.abstractor().m_exec = exec; 1082 tree.abstractor().m_compareFunction = compareFunction; 1083 tree.abstractor().m_compareCallType = callType; 1084 tree.abstractor().m_compareCallData = &callData; 1085 tree.abstractor().m_globalThisValue = exec->globalThisValue(); 1086 tree.abstractor().m_nodes.grow(nodeCount); 1087 1088 if (callType == CallTypeJS) 1089 tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, asFunction(compareFunction), 2)); 1090 1091 if (!tree.abstractor().m_nodes.begin()) { 1092 throwOutOfMemoryError(exec); 1093 return; 1094 } 1095 1096 // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified 1097 // right out from under us while we're building the tree here. 1098 1099 unsigned numDefined = 0; 1100 unsigned numUndefined = 0; 1101 1102 // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree. 1103 for (; numDefined < usedVectorLength; ++numDefined) { 1104 JSValue v = storage->m_vector[numDefined].get(); 1105 if (!v || v.isUndefined()) 1106 break; 1107 tree.abstractor().m_nodes[numDefined].value = v; 1108 tree.insert(numDefined); 1109 } 1110 for (unsigned i = numDefined; i < usedVectorLength; ++i) { 1111 JSValue v = storage->m_vector[i].get(); 1112 if (v) { 1113 if (v.isUndefined()) 1114 ++numUndefined; 1115 else { 1116 tree.abstractor().m_nodes[numDefined].value = v; 1117 tree.insert(numDefined); 1118 ++numDefined; 1119 } 1120 } 1121 } 1122 1123 unsigned newUsedVectorLength = numDefined + numUndefined; 1124 1125 if (SparseArrayValueMap* map = storage->m_sparseValueMap) { 1126 newUsedVectorLength += map->size(); 1127 if (newUsedVectorLength > m_vectorLength) { 1128 // Check that it is possible to allocate an array large enough to hold all the entries. 1129 if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) { 1130 throwOutOfMemoryError(exec); 1131 return; 1132 } 1133 } 1134 1135 storage = m_storage; 1136 1137 SparseArrayValueMap::iterator end = map->end(); 1138 for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) { 1139 tree.abstractor().m_nodes[numDefined].value = it->second.get(); 1140 tree.insert(numDefined); 1141 ++numDefined; 1142 } 1143 1144 delete map; 1145 storage->m_sparseValueMap = 0; 1146 } 1147 1148 ASSERT(tree.abstractor().m_nodes.size() >= numDefined); 1149 1150 // FIXME: If the compare function changed the length of the array, the following might be 1151 // modifying the vector incorrectly. 1152 1153 // Copy the values back into m_storage. 1154 AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter; 1155 iter.start_iter_least(tree); 1156 JSGlobalData& globalData = exec->globalData(); 1157 for (unsigned i = 0; i < numDefined; ++i) { 1158 storage->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value); 1159 ++iter; 1160 } 1161 1162 // Put undefined values back in. 1163 for (unsigned i = numDefined; i < newUsedVectorLength; ++i) 1164 storage->m_vector[i].setUndefined(); 1165 1166 // Ensure that unused values in the vector are zeroed out. 1167 for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) 1168 storage->m_vector[i].clear(); 1169 1170 storage->m_numValuesInVector = newUsedVectorLength; 1171 1172 checkConsistency(SortConsistencyCheck); 1173 } 1174 1175 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args) 1176 { 1177 ArrayStorage* storage = m_storage; 1178 1179 WriteBarrier<Unknown>* vector = storage->m_vector; 1180 unsigned vectorEnd = min(storage->m_length, m_vectorLength); 1181 unsigned i = 0; 1182 for (; i < vectorEnd; ++i) { 1183 WriteBarrier<Unknown>& v = vector[i]; 1184 if (!v) 1185 break; 1186 args.append(v.get()); 1187 } 1188 1189 for (; i < storage->m_length; ++i) 1190 args.append(get(exec, i)); 1191 } 1192 1193 void JSArray::copyToRegisters(ExecState* exec, Register* buffer, uint32_t maxSize) 1194 { 1195 ASSERT(m_storage->m_length >= maxSize); 1196 UNUSED_PARAM(maxSize); 1197 WriteBarrier<Unknown>* vector = m_storage->m_vector; 1198 unsigned vectorEnd = min(maxSize, m_vectorLength); 1199 unsigned i = 0; 1200 for (; i < vectorEnd; ++i) { 1201 WriteBarrier<Unknown>& v = vector[i]; 1202 if (!v) 1203 break; 1204 buffer[i] = v.get(); 1205 } 1206 1207 for (; i < maxSize; ++i) 1208 buffer[i] = get(exec, i); 1209 } 1210 1211 unsigned JSArray::compactForSorting() 1212 { 1213 checkConsistency(); 1214 1215 ArrayStorage* storage = m_storage; 1216 1217 unsigned usedVectorLength = min(storage->m_length, m_vectorLength); 1218 1219 unsigned numDefined = 0; 1220 unsigned numUndefined = 0; 1221 1222 for (; numDefined < usedVectorLength; ++numDefined) { 1223 JSValue v = storage->m_vector[numDefined].get(); 1224 if (!v || v.isUndefined()) 1225 break; 1226 } 1227 1228 for (unsigned i = numDefined; i < usedVectorLength; ++i) { 1229 JSValue v = storage->m_vector[i].get(); 1230 if (v) { 1231 if (v.isUndefined()) 1232 ++numUndefined; 1233 else 1234 storage->m_vector[numDefined++].setWithoutWriteBarrier(v); 1235 } 1236 } 1237 1238 unsigned newUsedVectorLength = numDefined + numUndefined; 1239 1240 if (SparseArrayValueMap* map = storage->m_sparseValueMap) { 1241 newUsedVectorLength += map->size(); 1242 if (newUsedVectorLength > m_vectorLength) { 1243 // Check that it is possible to allocate an array large enough to hold all the entries - if not, 1244 // exception is thrown by caller. 1245 if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) 1246 return 0; 1247 1248 storage = m_storage; 1249 } 1250 1251 SparseArrayValueMap::iterator end = map->end(); 1252 for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) 1253 storage->m_vector[numDefined++].setWithoutWriteBarrier(it->second.get()); 1254 1255 delete map; 1256 storage->m_sparseValueMap = 0; 1257 } 1258 1259 for (unsigned i = numDefined; i < newUsedVectorLength; ++i) 1260 storage->m_vector[i].setUndefined(); 1261 for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) 1262 storage->m_vector[i].clear(); 1263 1264 storage->m_numValuesInVector = newUsedVectorLength; 1265 1266 checkConsistency(SortConsistencyCheck); 1267 1268 return numDefined; 1269 } 1270 1271 void* JSArray::subclassData() const 1272 { 1273 return m_storage->subclassData; 1274 } 1275 1276 void JSArray::setSubclassData(void* d) 1277 { 1278 m_storage->subclassData = d; 1279 } 1280 1281 #if CHECK_ARRAY_CONSISTENCY 1282 1283 void JSArray::checkConsistency(ConsistencyCheckType type) 1284 { 1285 ArrayStorage* storage = m_storage; 1286 1287 ASSERT(storage); 1288 if (type == SortConsistencyCheck) 1289 ASSERT(!storage->m_sparseValueMap); 1290 1291 unsigned numValuesInVector = 0; 1292 for (unsigned i = 0; i < m_vectorLength; ++i) { 1293 if (JSValue value = storage->m_vector[i]) { 1294 ASSERT(i < storage->m_length); 1295 if (type != DestructorConsistencyCheck) 1296 value.isUndefined(); // Likely to crash if the object was deallocated. 1297 ++numValuesInVector; 1298 } else { 1299 if (type == SortConsistencyCheck) 1300 ASSERT(i >= storage->m_numValuesInVector); 1301 } 1302 } 1303 ASSERT(numValuesInVector == storage->m_numValuesInVector); 1304 ASSERT(numValuesInVector <= storage->m_length); 1305 1306 if (storage->m_sparseValueMap) { 1307 SparseArrayValueMap::iterator end = storage->m_sparseValueMap->end(); 1308 for (SparseArrayValueMap::iterator it = storage->m_sparseValueMap->begin(); it != end; ++it) { 1309 unsigned index = it->first; 1310 ASSERT(index < storage->m_length); 1311 ASSERT(index >= storage->m_vectorLength); 1312 ASSERT(index <= MAX_ARRAY_INDEX); 1313 ASSERT(it->second); 1314 if (type != DestructorConsistencyCheck) 1315 it->second.isUndefined(); // Likely to crash if the object was deallocated. 1316 } 1317 } 1318 } 1319 1320 #endif 1321 1322 } // namespace JSC 1323