1/* 2 * Copyright (C) 1999-2000 Harri Porten (porten@kde.org) 3 * Copyright (C) 2003, 2007, 2008, 2009, 2012 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 "ButterflyInlines.h" 28#include "CachedCall.h" 29#include "CopiedSpace.h" 30#include "CopiedSpaceInlines.h" 31#include "Error.h" 32#include "Executable.h" 33#include "GetterSetter.h" 34#include "IndexingHeaderInlines.h" 35#include "PropertyNameArray.h" 36#include "Reject.h" 37#include <wtf/AVLTree.h> 38#include <wtf/Assertions.h> 39#include <wtf/OwnPtr.h> 40#include <Operations.h> 41 42using namespace std; 43using namespace WTF; 44 45namespace JSC { 46 47ASSERT_HAS_TRIVIAL_DESTRUCTOR(JSArray); 48 49const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0, CREATE_METHOD_TABLE(JSArray)}; 50 51Butterfly* createArrayButterflyInDictionaryIndexingMode(VM& vm, unsigned initialLength) 52{ 53 Butterfly* butterfly = Butterfly::create( 54 vm, 0, 0, true, IndexingHeader(), ArrayStorage::sizeFor(0)); 55 ArrayStorage* storage = butterfly->arrayStorage(); 56 storage->setLength(initialLength); 57 storage->setVectorLength(0); 58 storage->m_indexBias = 0; 59 storage->m_sparseMap.clear(); 60 storage->m_numValuesInVector = 0; 61 return butterfly; 62} 63 64void JSArray::setLengthWritable(ExecState* exec, bool writable) 65{ 66 ASSERT(isLengthWritable() || !writable); 67 if (!isLengthWritable() || writable) 68 return; 69 70 enterDictionaryIndexingMode(exec->vm()); 71 72 SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get(); 73 ASSERT(map); 74 map->setLengthIsReadOnly(); 75} 76 77// Defined in ES5.1 15.4.5.1 78bool JSArray::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor, bool throwException) 79{ 80 JSArray* array = jsCast<JSArray*>(object); 81 82 // 3. If P is "length", then 83 if (propertyName == exec->propertyNames().length) { 84 // All paths through length definition call the default [[DefineOwnProperty]], hence: 85 // from ES5.1 8.12.9 7.a. 86 if (descriptor.configurablePresent() && descriptor.configurable()) 87 return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property."); 88 // from ES5.1 8.12.9 7.b. 89 if (descriptor.enumerablePresent() && descriptor.enumerable()) 90 return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property."); 91 92 // a. If the [[Value]] field of Desc is absent, then 93 // a.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", Desc, and Throw as arguments. 94 if (descriptor.isAccessorDescriptor()) 95 return reject(exec, throwException, "Attempting to change access mechanism for an unconfigurable property."); 96 // from ES5.1 8.12.9 10.a. 97 if (!array->isLengthWritable() && descriptor.writablePresent() && descriptor.writable()) 98 return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property."); 99 // This descriptor is either just making length read-only, or changing nothing! 100 if (!descriptor.value()) { 101 if (descriptor.writablePresent()) 102 array->setLengthWritable(exec, descriptor.writable()); 103 return true; 104 } 105 106 // b. Let newLenDesc be a copy of Desc. 107 // c. Let newLen be ToUint32(Desc.[[Value]]). 108 unsigned newLen = descriptor.value().toUInt32(exec); 109 // d. If newLen is not equal to ToNumber( Desc.[[Value]]), throw a RangeError exception. 110 if (newLen != descriptor.value().toNumber(exec)) { 111 throwError(exec, createRangeError(exec, "Invalid array length")); 112 return false; 113 } 114 115 // Based on SameValue check in 8.12.9, this is always okay. 116 if (newLen == array->length()) { 117 if (descriptor.writablePresent()) 118 array->setLengthWritable(exec, descriptor.writable()); 119 return true; 120 } 121 122 // e. Set newLenDesc.[[Value] to newLen. 123 // f. If newLen >= oldLen, then 124 // f.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments. 125 // g. Reject if oldLenDesc.[[Writable]] is false. 126 if (!array->isLengthWritable()) 127 return reject(exec, throwException, "Attempting to change value of a readonly property."); 128 129 // h. If newLenDesc.[[Writable]] is absent or has the value true, let newWritable be true. 130 // i. Else, 131 // i.i. Need to defer setting the [[Writable]] attribute to false in case any elements cannot be deleted. 132 // i.ii. Let newWritable be false. 133 // i.iii. Set newLenDesc.[[Writable] to true. 134 // j. Let succeeded be the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments. 135 // k. If succeeded is false, return false. 136 // l. While newLen < oldLen repeat, 137 // l.i. Set oldLen to oldLen – 1. 138 // l.ii. Let deleteSucceeded be the result of calling the [[Delete]] internal method of A passing ToString(oldLen) and false as arguments. 139 // l.iii. If deleteSucceeded is false, then 140 if (!array->setLength(exec, newLen, throwException)) { 141 // 1. Set newLenDesc.[[Value] to oldLen+1. 142 // 2. If newWritable is false, set newLenDesc.[[Writable] to false. 143 // 3. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and false as arguments. 144 // 4. Reject. 145 if (descriptor.writablePresent()) 146 array->setLengthWritable(exec, descriptor.writable()); 147 return false; 148 } 149 150 // m. If newWritable is false, then 151 // i. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", 152 // Property Descriptor{[[Writable]]: false}, and false as arguments. This call will always 153 // return true. 154 if (descriptor.writablePresent()) 155 array->setLengthWritable(exec, descriptor.writable()); 156 // n. Return true. 157 return true; 158 } 159 160 // 4. Else if P is an array index (15.4), then 161 // a. Let index be ToUint32(P). 162 unsigned index = propertyName.asIndex(); 163 if (index != PropertyName::NotAnIndex) { 164 // b. Reject if index >= oldLen and oldLenDesc.[[Writable]] is false. 165 if (index >= array->length() && !array->isLengthWritable()) 166 return reject(exec, throwException, "Attempting to define numeric property on array with non-writable length property."); 167 // c. Let succeeded be the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing P, Desc, and false as arguments. 168 // d. Reject if succeeded is false. 169 // e. If index >= oldLen 170 // e.i. Set oldLenDesc.[[Value]] to index + 1. 171 // e.ii. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", oldLenDesc, and false as arguments. This call will always return true. 172 // f. Return true. 173 return array->defineOwnIndexedProperty(exec, index, descriptor, throwException); 174 } 175 176 return array->JSObject::defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException); 177} 178 179bool JSArray::getOwnPropertySlot(JSCell* cell, ExecState* exec, PropertyName propertyName, PropertySlot& slot) 180{ 181 JSArray* thisObject = jsCast<JSArray*>(cell); 182 if (propertyName == exec->propertyNames().length) { 183 slot.setValue(jsNumber(thisObject->length())); 184 return true; 185 } 186 187 return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot); 188} 189 190bool JSArray::getOwnPropertyDescriptor(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor) 191{ 192 JSArray* thisObject = jsCast<JSArray*>(object); 193 if (propertyName == exec->propertyNames().length) { 194 descriptor.setDescriptor(jsNumber(thisObject->length()), thisObject->isLengthWritable() ? DontDelete | DontEnum : DontDelete | DontEnum | ReadOnly); 195 return true; 196 } 197 198 return JSObject::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor); 199} 200 201// ECMA 15.4.5.1 202void JSArray::put(JSCell* cell, ExecState* exec, PropertyName propertyName, JSValue value, PutPropertySlot& slot) 203{ 204 JSArray* thisObject = jsCast<JSArray*>(cell); 205 206 if (propertyName == exec->propertyNames().length) { 207 unsigned newLength = value.toUInt32(exec); 208 if (value.toNumber(exec) != static_cast<double>(newLength)) { 209 throwError(exec, createRangeError(exec, ASCIILiteral("Invalid array length"))); 210 return; 211 } 212 thisObject->setLength(exec, newLength, slot.isStrictMode()); 213 return; 214 } 215 216 JSObject::put(thisObject, exec, propertyName, value, slot); 217} 218 219bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName) 220{ 221 JSArray* thisObject = jsCast<JSArray*>(cell); 222 223 if (propertyName == exec->propertyNames().length) 224 return false; 225 226 return JSObject::deleteProperty(thisObject, exec, propertyName); 227} 228 229static int compareKeysForQSort(const void* a, const void* b) 230{ 231 unsigned da = *static_cast<const unsigned*>(a); 232 unsigned db = *static_cast<const unsigned*>(b); 233 return (da > db) - (da < db); 234} 235 236void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode) 237{ 238 JSArray* thisObject = jsCast<JSArray*>(object); 239 240 if (mode == IncludeDontEnumProperties) 241 propertyNames.add(exec->propertyNames().length); 242 243 JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode); 244} 245 246// This method makes room in the vector, but leaves the new space for count slots uncleared. 247bool JSArray::unshiftCountSlowCase(VM& vm, bool addToFront, unsigned count) 248{ 249 ArrayStorage* storage = ensureArrayStorage(vm); 250 Butterfly* butterfly = storage->butterfly(); 251 unsigned propertyCapacity = structure()->outOfLineCapacity(); 252 unsigned propertySize = structure()->outOfLineSize(); 253 254 // If not, we should have handled this on the fast path. 255 ASSERT(!addToFront || count > storage->m_indexBias); 256 257 // Step 1: 258 // Gather 4 key metrics: 259 // * usedVectorLength - how many entries are currently in the vector (conservative estimate - fewer may be in use in sparse vectors). 260 // * requiredVectorLength - how many entries are will there be in the vector, after allocating space for 'count' more. 261 // * currentCapacity - what is the current size of the vector, including any pre-capacity. 262 // * desiredCapacity - how large should we like to grow the vector to - based on 2x requiredVectorLength. 263 264 unsigned length = storage->length(); 265 unsigned usedVectorLength = min(storage->vectorLength(), length); 266 ASSERT(usedVectorLength <= MAX_STORAGE_VECTOR_LENGTH); 267 // Check that required vector length is possible, in an overflow-safe fashion. 268 if (count > MAX_STORAGE_VECTOR_LENGTH - usedVectorLength) 269 return false; 270 unsigned requiredVectorLength = usedVectorLength + count; 271 ASSERT(requiredVectorLength <= MAX_STORAGE_VECTOR_LENGTH); 272 // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH. 273 ASSERT(storage->vectorLength() <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - storage->vectorLength()) >= storage->m_indexBias); 274 unsigned currentCapacity = storage->vectorLength() + storage->m_indexBias; 275 // The calculation of desiredCapacity won't overflow, due to the range of MAX_STORAGE_VECTOR_LENGTH. 276 unsigned desiredCapacity = min(MAX_STORAGE_VECTOR_LENGTH, max(BASE_VECTOR_LEN, requiredVectorLength) << 1); 277 278 // Step 2: 279 // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing one. 280 281 void* newAllocBase = 0; 282 unsigned newStorageCapacity; 283 // If the current storage array is sufficiently large (but not too large!) then just keep using it. 284 if (currentCapacity > desiredCapacity && isDenseEnoughForVector(currentCapacity, requiredVectorLength)) { 285 newAllocBase = butterfly->base(structure()); 286 newStorageCapacity = currentCapacity; 287 } else { 288 size_t newSize = Butterfly::totalSize(0, propertyCapacity, true, ArrayStorage::sizeFor(desiredCapacity)); 289 if (!vm.heap.tryAllocateStorage(newSize, &newAllocBase)) 290 return false; 291 newStorageCapacity = desiredCapacity; 292 } 293 294 // Step 3: 295 // Work out where we're going to move things to. 296 297 // Determine how much of the vector to use as pre-capacity, and how much as post-capacity. 298 // If we're adding to the end, we'll add all the new space to the end. 299 // If the vector had no free post-capacity (length >= m_vectorLength), don't give it any. 300 // If it did, we calculate the amount that will remain based on an atomic decay - leave the 301 // vector with half the post-capacity it had previously. 302 unsigned postCapacity = 0; 303 if (!addToFront) 304 postCapacity = max(newStorageCapacity - requiredVectorLength, count); 305 else if (length < storage->vectorLength()) { 306 // Atomic decay, + the post-capacity cannot be greater than what is available. 307 postCapacity = min((storage->vectorLength() - length) >> 1, newStorageCapacity - requiredVectorLength); 308 // If we're moving contents within the same allocation, the post-capacity is being reduced. 309 ASSERT(newAllocBase != butterfly->base(structure()) || postCapacity < storage->vectorLength() - length); 310 } 311 312 unsigned newVectorLength = requiredVectorLength + postCapacity; 313 unsigned newIndexBias = newStorageCapacity - newVectorLength; 314 315 Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity); 316 317 if (addToFront) { 318 ASSERT(count + usedVectorLength <= newVectorLength); 319 memmove(newButterfly->arrayStorage()->m_vector + count, storage->m_vector, sizeof(JSValue) * usedVectorLength); 320 memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0)); 321 } else if ((newAllocBase != butterfly->base(structure())) || (newIndexBias != storage->m_indexBias)) { 322 memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0)); 323 memmove(newButterfly->arrayStorage()->m_vector, storage->m_vector, sizeof(JSValue) * usedVectorLength); 324 325 WriteBarrier<Unknown>* newVector = newButterfly->arrayStorage()->m_vector; 326 for (unsigned i = requiredVectorLength; i < newVectorLength; i++) 327 newVector[i].clear(); 328 } 329 330 newButterfly->arrayStorage()->setVectorLength(newVectorLength); 331 newButterfly->arrayStorage()->m_indexBias = newIndexBias; 332 333 m_butterfly = newButterfly; 334 335 return true; 336} 337 338bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, bool throwException, ArrayStorage* storage) 339{ 340 unsigned length = storage->length(); 341 342 // If the length is read only then we enter sparse mode, so should enter the following 'if'. 343 ASSERT(isLengthWritable() || storage->m_sparseMap); 344 345 if (SparseArrayValueMap* map = storage->m_sparseMap.get()) { 346 // Fail if the length is not writable. 347 if (map->lengthIsReadOnly()) 348 return reject(exec, throwException, StrictModeReadonlyPropertyWriteError); 349 350 if (newLength < length) { 351 // Copy any keys we might be interested in into a vector. 352 Vector<unsigned, 0, UnsafeVectorOverflow> keys; 353 keys.reserveInitialCapacity(min(map->size(), static_cast<size_t>(length - newLength))); 354 SparseArrayValueMap::const_iterator end = map->end(); 355 for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) { 356 unsigned index = static_cast<unsigned>(it->key); 357 if (index < length && index >= newLength) 358 keys.append(index); 359 } 360 361 // Check if the array is in sparse mode. If so there may be non-configurable 362 // properties, so we have to perform deletion with caution, if not we can 363 // delete values in any order. 364 if (map->sparseMode()) { 365 qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort); 366 unsigned i = keys.size(); 367 while (i) { 368 unsigned index = keys[--i]; 369 SparseArrayValueMap::iterator it = map->find(index); 370 ASSERT(it != map->notFound()); 371 if (it->value.attributes & DontDelete) { 372 storage->setLength(index + 1); 373 return reject(exec, throwException, "Unable to delete property."); 374 } 375 map->remove(it); 376 } 377 } else { 378 for (unsigned i = 0; i < keys.size(); ++i) 379 map->remove(keys[i]); 380 if (map->isEmpty()) 381 deallocateSparseIndexMap(); 382 } 383 } 384 } 385 386 if (newLength < length) { 387 // Delete properties from the vector. 388 unsigned usedVectorLength = min(length, storage->vectorLength()); 389 for (unsigned i = newLength; i < usedVectorLength; ++i) { 390 WriteBarrier<Unknown>& valueSlot = storage->m_vector[i]; 391 bool hadValue = valueSlot; 392 valueSlot.clear(); 393 storage->m_numValuesInVector -= hadValue; 394 } 395 } 396 397 storage->setLength(newLength); 398 399 return true; 400} 401 402bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException) 403{ 404 switch (structure()->indexingType()) { 405 case ArrayClass: 406 if (!newLength) 407 return true; 408 if (newLength >= MIN_SPARSE_ARRAY_INDEX) { 409 return setLengthWithArrayStorage( 410 exec, newLength, throwException, 411 convertContiguousToArrayStorage(exec->vm())); 412 } 413 createInitialUndecided(exec->vm(), newLength); 414 return true; 415 416 case ArrayWithUndecided: 417 case ArrayWithInt32: 418 case ArrayWithDouble: 419 case ArrayWithContiguous: 420 if (newLength == m_butterfly->publicLength()) 421 return true; 422 if (newLength >= MAX_ARRAY_INDEX // This case ensures that we can do fast push. 423 || (newLength >= MIN_SPARSE_ARRAY_INDEX 424 && !isDenseEnoughForVector(newLength, countElements()))) { 425 return setLengthWithArrayStorage( 426 exec, newLength, throwException, 427 ensureArrayStorage(exec->vm())); 428 } 429 if (newLength > m_butterfly->publicLength()) { 430 ensureLength(exec->vm(), newLength); 431 return true; 432 } 433 if (structure()->indexingType() == ArrayWithDouble) { 434 for (unsigned i = m_butterfly->publicLength(); i-- > newLength;) 435 m_butterfly->contiguousDouble()[i] = QNaN; 436 } else { 437 for (unsigned i = m_butterfly->publicLength(); i-- > newLength;) 438 m_butterfly->contiguous()[i].clear(); 439 } 440 m_butterfly->setPublicLength(newLength); 441 return true; 442 443 case ArrayWithArrayStorage: 444 case ArrayWithSlowPutArrayStorage: 445 return setLengthWithArrayStorage(exec, newLength, throwException, arrayStorage()); 446 447 default: 448 CRASH(); 449 return false; 450 } 451} 452 453JSValue JSArray::pop(ExecState* exec) 454{ 455 switch (structure()->indexingType()) { 456 case ArrayClass: 457 return jsUndefined(); 458 459 case ArrayWithUndecided: 460 if (!m_butterfly->publicLength()) 461 return jsUndefined(); 462 // We have nothing but holes. So, drop down to the slow version. 463 break; 464 465 case ArrayWithInt32: 466 case ArrayWithContiguous: { 467 unsigned length = m_butterfly->publicLength(); 468 469 if (!length--) 470 return jsUndefined(); 471 472 RELEASE_ASSERT(length < m_butterfly->vectorLength()); 473 JSValue value = m_butterfly->contiguous()[length].get(); 474 if (value) { 475 m_butterfly->contiguous()[length].clear(); 476 m_butterfly->setPublicLength(length); 477 return value; 478 } 479 break; 480 } 481 482 case ArrayWithDouble: { 483 unsigned length = m_butterfly->publicLength(); 484 485 if (!length--) 486 return jsUndefined(); 487 488 RELEASE_ASSERT(length < m_butterfly->vectorLength()); 489 double value = m_butterfly->contiguousDouble()[length]; 490 if (value == value) { 491 m_butterfly->contiguousDouble()[length] = QNaN; 492 m_butterfly->setPublicLength(length); 493 return JSValue(JSValue::EncodeAsDouble, value); 494 } 495 break; 496 } 497 498 case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: { 499 ArrayStorage* storage = m_butterfly->arrayStorage(); 500 501 unsigned length = storage->length(); 502 if (!length) { 503 if (!isLengthWritable()) 504 throwTypeError(exec, StrictModeReadonlyPropertyWriteError); 505 return jsUndefined(); 506 } 507 508 unsigned index = length - 1; 509 if (index < storage->vectorLength()) { 510 WriteBarrier<Unknown>& valueSlot = storage->m_vector[index]; 511 if (valueSlot) { 512 --storage->m_numValuesInVector; 513 JSValue element = valueSlot.get(); 514 valueSlot.clear(); 515 516 RELEASE_ASSERT(isLengthWritable()); 517 storage->setLength(index); 518 return element; 519 } 520 } 521 break; 522 } 523 524 default: 525 CRASH(); 526 return JSValue(); 527 } 528 529 unsigned index = getArrayLength() - 1; 530 // Let element be the result of calling the [[Get]] internal method of O with argument indx. 531 JSValue element = get(exec, index); 532 if (exec->hadException()) 533 return jsUndefined(); 534 // Call the [[Delete]] internal method of O with arguments indx and true. 535 if (!deletePropertyByIndex(this, exec, index)) { 536 throwTypeError(exec, "Unable to delete property."); 537 return jsUndefined(); 538 } 539 // Call the [[Put]] internal method of O with arguments "length", indx, and true. 540 setLength(exec, index, true); 541 // Return element. 542 return element; 543} 544 545// Push & putIndex are almost identical, with two small differences. 546// - we always are writing beyond the current array bounds, so it is always necessary to update m_length & m_numValuesInVector. 547// - pushing to an array of length 2^32-1 stores the property, but throws a range error. 548void JSArray::push(ExecState* exec, JSValue value) 549{ 550 switch (structure()->indexingType()) { 551 case ArrayClass: { 552 createInitialUndecided(exec->vm(), 0); 553 // Fall through. 554 } 555 556 case ArrayWithUndecided: { 557 convertUndecidedForValue(exec->vm(), value); 558 push(exec, value); 559 return; 560 } 561 562 case ArrayWithInt32: { 563 if (!value.isInt32()) { 564 convertInt32ForValue(exec->vm(), value); 565 push(exec, value); 566 return; 567 } 568 569 unsigned length = m_butterfly->publicLength(); 570 ASSERT(length <= m_butterfly->vectorLength()); 571 if (length < m_butterfly->vectorLength()) { 572 m_butterfly->contiguousInt32()[length].setWithoutWriteBarrier(value); 573 m_butterfly->setPublicLength(length + 1); 574 return; 575 } 576 577 if (length > MAX_ARRAY_INDEX) { 578 methodTable()->putByIndex(this, exec, length, value, true); 579 if (!exec->hadException()) 580 throwError(exec, createRangeError(exec, "Invalid array length")); 581 return; 582 } 583 584 putByIndexBeyondVectorLengthWithoutAttributes<Int32Shape>(exec, length, value); 585 return; 586 } 587 588 case ArrayWithContiguous: { 589 unsigned length = m_butterfly->publicLength(); 590 ASSERT(length <= m_butterfly->vectorLength()); 591 if (length < m_butterfly->vectorLength()) { 592 m_butterfly->contiguous()[length].set(exec->vm(), this, value); 593 m_butterfly->setPublicLength(length + 1); 594 return; 595 } 596 597 if (length > MAX_ARRAY_INDEX) { 598 methodTable()->putByIndex(this, exec, length, value, true); 599 if (!exec->hadException()) 600 throwError(exec, createRangeError(exec, "Invalid array length")); 601 return; 602 } 603 604 putByIndexBeyondVectorLengthWithoutAttributes<ContiguousShape>(exec, length, value); 605 return; 606 } 607 608 case ArrayWithDouble: { 609 if (!value.isNumber()) { 610 convertDoubleToContiguous(exec->vm()); 611 push(exec, value); 612 return; 613 } 614 double valueAsDouble = value.asNumber(); 615 if (valueAsDouble != valueAsDouble) { 616 convertDoubleToContiguous(exec->vm()); 617 push(exec, value); 618 return; 619 } 620 621 unsigned length = m_butterfly->publicLength(); 622 ASSERT(length <= m_butterfly->vectorLength()); 623 if (length < m_butterfly->vectorLength()) { 624 m_butterfly->contiguousDouble()[length] = valueAsDouble; 625 m_butterfly->setPublicLength(length + 1); 626 return; 627 } 628 629 if (length > MAX_ARRAY_INDEX) { 630 methodTable()->putByIndex(this, exec, length, value, true); 631 if (!exec->hadException()) 632 throwError(exec, createRangeError(exec, "Invalid array length")); 633 return; 634 } 635 636 putByIndexBeyondVectorLengthWithoutAttributes<DoubleShape>(exec, length, value); 637 break; 638 } 639 640 case ArrayWithSlowPutArrayStorage: { 641 unsigned oldLength = length(); 642 if (attemptToInterceptPutByIndexOnHole(exec, oldLength, value, true)) { 643 if (!exec->hadException() && oldLength < 0xFFFFFFFFu) 644 setLength(exec, oldLength + 1, true); 645 return; 646 } 647 // Fall through. 648 } 649 650 case ArrayWithArrayStorage: { 651 ArrayStorage* storage = m_butterfly->arrayStorage(); 652 653 // Fast case - push within vector, always update m_length & m_numValuesInVector. 654 unsigned length = storage->length(); 655 if (length < storage->vectorLength()) { 656 storage->m_vector[length].set(exec->vm(), this, value); 657 storage->setLength(length + 1); 658 ++storage->m_numValuesInVector; 659 return; 660 } 661 662 // Pushing to an array of invalid length (2^31-1) stores the property, but throws a range error. 663 if (storage->length() > MAX_ARRAY_INDEX) { 664 methodTable()->putByIndex(this, exec, storage->length(), value, true); 665 // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d. 666 if (!exec->hadException()) 667 throwError(exec, createRangeError(exec, "Invalid array length")); 668 return; 669 } 670 671 // Handled the same as putIndex. 672 putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage); 673 break; 674 } 675 676 default: 677 RELEASE_ASSERT_NOT_REACHED(); 678 } 679} 680 681bool JSArray::shiftCountWithArrayStorage(unsigned startIndex, unsigned count, ArrayStorage* storage) 682{ 683 unsigned oldLength = storage->length(); 684 RELEASE_ASSERT(count <= oldLength); 685 686 // If the array contains holes or is otherwise in an abnormal state, 687 // use the generic algorithm in ArrayPrototype. 688 if (oldLength != storage->m_numValuesInVector || inSparseIndexingMode() || shouldUseSlowPut(structure()->indexingType())) 689 return false; 690 691 if (!oldLength) 692 return true; 693 694 unsigned length = oldLength - count; 695 696 storage->m_numValuesInVector -= count; 697 storage->setLength(length); 698 699 unsigned vectorLength = storage->vectorLength(); 700 if (!vectorLength) 701 return true; 702 703 if (startIndex >= vectorLength) 704 return true; 705 706 if (startIndex + count > vectorLength) 707 count = vectorLength - startIndex; 708 709 unsigned usedVectorLength = min(vectorLength, oldLength); 710 711 vectorLength -= count; 712 storage->setVectorLength(vectorLength); 713 714 if (vectorLength) { 715 if (startIndex < usedVectorLength - (startIndex + count)) { 716 if (startIndex) { 717 memmove( 718 storage->m_vector + count, 719 storage->m_vector, 720 sizeof(JSValue) * startIndex); 721 } 722 m_butterfly = m_butterfly->shift(structure(), count); 723 storage = m_butterfly->arrayStorage(); 724 storage->m_indexBias += count; 725 } else { 726 memmove( 727 storage->m_vector + startIndex, 728 storage->m_vector + startIndex + count, 729 sizeof(JSValue) * (usedVectorLength - (startIndex + count))); 730 for (unsigned i = usedVectorLength - count; i < usedVectorLength; ++i) 731 storage->m_vector[i].clear(); 732 } 733 } 734 return true; 735} 736 737bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count) 738{ 739 RELEASE_ASSERT(count > 0); 740 741 switch (structure()->indexingType()) { 742 case ArrayClass: 743 return true; 744 745 case ArrayWithUndecided: 746 // Don't handle this because it's confusing and it shouldn't come up. 747 return false; 748 749 case ArrayWithInt32: 750 case ArrayWithContiguous: { 751 unsigned oldLength = m_butterfly->publicLength(); 752 RELEASE_ASSERT(count <= oldLength); 753 754 // We may have to walk the entire array to do the shift. We're willing to do 755 // so only if it's not horribly slow. 756 if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX) 757 return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm())); 758 759 // Storing to a hole is fine since we're still having a good time. But reading from a hole 760 // is totally not fine, since we might have to read from the proto chain. 761 // We have to check for holes before we start moving things around so that we don't get halfway 762 // through shifting and then realize we should have been in ArrayStorage mode. 763 unsigned end = oldLength - count; 764 for (unsigned i = startIndex; i < end; ++i) { 765 JSValue v = m_butterfly->contiguous()[i + count].get(); 766 if (UNLIKELY(!v)) 767 return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm())); 768 } 769 770 for (unsigned i = startIndex; i < end; ++i) { 771 JSValue v = m_butterfly->contiguous()[i + count].get(); 772 ASSERT(v); 773 // No need for a barrier since we're just moving data around in the same vector. 774 // This is in line with our standing assumption that we won't have a deletion 775 // barrier. 776 m_butterfly->contiguous()[i].setWithoutWriteBarrier(v); 777 } 778 for (unsigned i = end; i < oldLength; ++i) 779 m_butterfly->contiguous()[i].clear(); 780 781 m_butterfly->setPublicLength(oldLength - count); 782 return true; 783 } 784 785 case ArrayWithDouble: { 786 unsigned oldLength = m_butterfly->publicLength(); 787 RELEASE_ASSERT(count <= oldLength); 788 789 // We may have to walk the entire array to do the shift. We're willing to do 790 // so only if it's not horribly slow. 791 if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX) 792 return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm())); 793 794 // Storing to a hole is fine since we're still having a good time. But reading from a hole 795 // is totally not fine, since we might have to read from the proto chain. 796 // We have to check for holes before we start moving things around so that we don't get halfway 797 // through shifting and then realize we should have been in ArrayStorage mode. 798 unsigned end = oldLength - count; 799 for (unsigned i = startIndex; i < end; ++i) { 800 double v = m_butterfly->contiguousDouble()[i + count]; 801 if (UNLIKELY(v != v)) 802 return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm())); 803 } 804 805 for (unsigned i = startIndex; i < end; ++i) { 806 double v = m_butterfly->contiguousDouble()[i + count]; 807 ASSERT(v == v); 808 // No need for a barrier since we're just moving data around in the same vector. 809 // This is in line with our standing assumption that we won't have a deletion 810 // barrier. 811 m_butterfly->contiguousDouble()[i] = v; 812 } 813 for (unsigned i = end; i < oldLength; ++i) 814 m_butterfly->contiguousDouble()[i] = QNaN; 815 816 m_butterfly->setPublicLength(oldLength - count); 817 return true; 818 } 819 820 case ArrayWithArrayStorage: 821 case ArrayWithSlowPutArrayStorage: 822 return shiftCountWithArrayStorage(startIndex, count, arrayStorage()); 823 824 default: 825 CRASH(); 826 return false; 827 } 828} 829 830// Returns true if the unshift can be handled, false to fallback. 831bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, unsigned count, ArrayStorage* storage) 832{ 833 unsigned length = storage->length(); 834 835 RELEASE_ASSERT(startIndex <= length); 836 837 // If the array contains holes or is otherwise in an abnormal state, 838 // use the generic algorithm in ArrayPrototype. 839 if (length != storage->m_numValuesInVector || storage->inSparseMode() || shouldUseSlowPut(structure()->indexingType())) 840 return false; 841 842 bool moveFront = !startIndex || startIndex < length / 2; 843 844 unsigned vectorLength = storage->vectorLength(); 845 846 if (moveFront && storage->m_indexBias >= count) { 847 m_butterfly = storage->butterfly()->unshift(structure(), count); 848 storage = m_butterfly->arrayStorage(); 849 storage->m_indexBias -= count; 850 storage->setVectorLength(vectorLength + count); 851 } else if (!moveFront && vectorLength - length >= count) 852 storage = storage->butterfly()->arrayStorage(); 853 else if (unshiftCountSlowCase(exec->vm(), moveFront, count)) 854 storage = arrayStorage(); 855 else { 856 throwOutOfMemoryError(exec); 857 return true; 858 } 859 860 WriteBarrier<Unknown>* vector = storage->m_vector; 861 862 if (startIndex) { 863 if (moveFront) 864 memmove(vector, vector + count, startIndex * sizeof(JSValue)); 865 else if (length - startIndex) 866 memmove(vector + startIndex + count, vector + startIndex, (length - startIndex) * sizeof(JSValue)); 867 } 868 869 for (unsigned i = 0; i < count; i++) 870 vector[i + startIndex].clear(); 871 return true; 872} 873 874bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count) 875{ 876 switch (structure()->indexingType()) { 877 case ArrayClass: 878 case ArrayWithUndecided: 879 // We could handle this. But it shouldn't ever come up, so we won't. 880 return false; 881 882 case ArrayWithInt32: 883 case ArrayWithContiguous: { 884 unsigned oldLength = m_butterfly->publicLength(); 885 886 // We may have to walk the entire array to do the unshift. We're willing to do so 887 // only if it's not horribly slow. 888 if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX) 889 return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm())); 890 891 ensureLength(exec->vm(), oldLength + count); 892 893 // We have to check for holes before we start moving things around so that we don't get halfway 894 // through shifting and then realize we should have been in ArrayStorage mode. 895 for (unsigned i = oldLength; i-- > startIndex;) { 896 JSValue v = m_butterfly->contiguous()[i].get(); 897 if (UNLIKELY(!v)) 898 return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm())); 899 } 900 901 for (unsigned i = oldLength; i-- > startIndex;) { 902 JSValue v = m_butterfly->contiguous()[i].get(); 903 ASSERT(v); 904 m_butterfly->contiguous()[i + count].setWithoutWriteBarrier(v); 905 } 906 907 // NOTE: we're leaving being garbage in the part of the array that we shifted out 908 // of. This is fine because the caller is required to store over that area, and 909 // in contiguous mode storing into a hole is guaranteed to behave exactly the same 910 // as storing over an existing element. 911 912 return true; 913 } 914 915 case ArrayWithDouble: { 916 unsigned oldLength = m_butterfly->publicLength(); 917 918 // We may have to walk the entire array to do the unshift. We're willing to do so 919 // only if it's not horribly slow. 920 if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX) 921 return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm())); 922 923 ensureLength(exec->vm(), oldLength + count); 924 925 // We have to check for holes before we start moving things around so that we don't get halfway 926 // through shifting and then realize we should have been in ArrayStorage mode. 927 for (unsigned i = oldLength; i-- > startIndex;) { 928 double v = m_butterfly->contiguousDouble()[i]; 929 if (UNLIKELY(v != v)) 930 return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm())); 931 } 932 933 for (unsigned i = oldLength; i-- > startIndex;) { 934 double v = m_butterfly->contiguousDouble()[i]; 935 ASSERT(v == v); 936 m_butterfly->contiguousDouble()[i + count] = v; 937 } 938 939 // NOTE: we're leaving being garbage in the part of the array that we shifted out 940 // of. This is fine because the caller is required to store over that area, and 941 // in contiguous mode storing into a hole is guaranteed to behave exactly the same 942 // as storing over an existing element. 943 944 return true; 945 } 946 947 case ArrayWithArrayStorage: 948 case ArrayWithSlowPutArrayStorage: 949 return unshiftCountWithArrayStorage(exec, startIndex, count, arrayStorage()); 950 951 default: 952 CRASH(); 953 return false; 954 } 955} 956 957static int compareNumbersForQSortWithInt32(const void* a, const void* b) 958{ 959 int32_t ia = static_cast<const JSValue*>(a)->asInt32(); 960 int32_t ib = static_cast<const JSValue*>(b)->asInt32(); 961 return ia - ib; 962} 963 964static int compareNumbersForQSortWithDouble(const void* a, const void* b) 965{ 966 double da = *static_cast<const double*>(a); 967 double db = *static_cast<const double*>(b); 968 return (da > db) - (da < db); 969} 970 971static int compareNumbersForQSort(const void* a, const void* b) 972{ 973 double da = static_cast<const JSValue*>(a)->asNumber(); 974 double db = static_cast<const JSValue*>(b)->asNumber(); 975 return (da > db) - (da < db); 976} 977 978static int compareByStringPairForQSort(const void* a, const void* b) 979{ 980 const ValueStringPair* va = static_cast<const ValueStringPair*>(a); 981 const ValueStringPair* vb = static_cast<const ValueStringPair*>(b); 982 return codePointCompare(va->second, vb->second); 983} 984 985template<IndexingType indexingType> 986void JSArray::sortNumericVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) 987{ 988 ASSERT(indexingType == ArrayWithInt32 || indexingType == ArrayWithDouble || indexingType == ArrayWithContiguous || indexingType == ArrayWithArrayStorage); 989 990 unsigned lengthNotIncludingUndefined; 991 unsigned newRelevantLength; 992 compactForSorting<indexingType>( 993 lengthNotIncludingUndefined, 994 newRelevantLength); 995 996 ContiguousJSValues data = indexingData<indexingType>(); 997 998 if (indexingType == ArrayWithArrayStorage && arrayStorage()->m_sparseMap.get()) { 999 throwOutOfMemoryError(exec); 1000 return; 1001 } 1002 1003 if (!lengthNotIncludingUndefined) 1004 return; 1005 1006 bool allValuesAreNumbers = true; 1007 switch (indexingType) { 1008 case ArrayWithInt32: 1009 case ArrayWithDouble: 1010 break; 1011 1012 default: 1013 for (size_t i = 0; i < newRelevantLength; ++i) { 1014 if (!data[i].isNumber()) { 1015 allValuesAreNumbers = false; 1016 break; 1017 } 1018 } 1019 break; 1020 } 1021 1022 if (!allValuesAreNumbers) 1023 return sort(exec, compareFunction, callType, callData); 1024 1025 // For numeric comparison, which is fast, qsort is faster than mergesort. We 1026 // also don't require mergesort's stability, since there's no user visible 1027 // side-effect from swapping the order of equal primitive values. 1028 int (*compare)(const void*, const void*); 1029 switch (indexingType) { 1030 case ArrayWithInt32: 1031 compare = compareNumbersForQSortWithInt32; 1032 break; 1033 1034 case ArrayWithDouble: 1035 compare = compareNumbersForQSortWithDouble; 1036 ASSERT(sizeof(WriteBarrier<Unknown>) == sizeof(double)); 1037 break; 1038 1039 default: 1040 compare = compareNumbersForQSort; 1041 break; 1042 } 1043 ASSERT(data.length() >= newRelevantLength); 1044 qsort(data.data(), newRelevantLength, sizeof(WriteBarrier<Unknown>), compare); 1045 return; 1046} 1047 1048void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) 1049{ 1050 ASSERT(!inSparseIndexingMode()); 1051 1052 switch (structure()->indexingType()) { 1053 case ArrayClass: 1054 return; 1055 1056 case ArrayWithInt32: 1057 sortNumericVector<ArrayWithInt32>(exec, compareFunction, callType, callData); 1058 break; 1059 1060 case ArrayWithDouble: 1061 sortNumericVector<ArrayWithDouble>(exec, compareFunction, callType, callData); 1062 break; 1063 1064 case ArrayWithContiguous: 1065 sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData); 1066 return; 1067 1068 case ArrayWithArrayStorage: 1069 sortNumericVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData); 1070 return; 1071 1072 default: 1073 CRASH(); 1074 return; 1075 } 1076} 1077 1078template <IndexingType> struct ContiguousTypeAccessor { 1079 typedef WriteBarrier<Unknown> Type; 1080 static JSValue getAsValue(ContiguousData<Type> data, size_t i) { return data[i].get(); } 1081 static void setWithValue(VM& vm, JSArray* thisValue, ContiguousData<Type> data, size_t i, JSValue value) 1082 { 1083 data[i].set(vm, thisValue, value); 1084 } 1085 static void replaceDataReference(ContiguousData<Type>* outData, ContiguousJSValues inData) 1086 { 1087 *outData = inData; 1088 } 1089}; 1090 1091template <> struct ContiguousTypeAccessor<ArrayWithDouble> { 1092 typedef double Type; 1093 static JSValue getAsValue(ContiguousData<Type> data, size_t i) { ASSERT(data[i] == data[i]); return JSValue(JSValue::EncodeAsDouble, data[i]); } 1094 static void setWithValue(VM&, JSArray*, ContiguousData<Type> data, size_t i, JSValue value) 1095 { 1096 data[i] = value.asNumber(); 1097 } 1098 static NO_RETURN_DUE_TO_CRASH void replaceDataReference(ContiguousData<Type>*, ContiguousJSValues) 1099 { 1100 RELEASE_ASSERT_WITH_MESSAGE(0, "Inconsistent indexing types during compact array sort."); 1101 } 1102}; 1103 1104 1105template<IndexingType indexingType, typename StorageType> 1106void JSArray::sortCompactedVector(ExecState* exec, ContiguousData<StorageType> data, unsigned relevantLength) 1107{ 1108 if (!relevantLength) 1109 return; 1110 1111 VM& vm = exec->vm(); 1112 1113 // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that. 1114 // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary 1115 // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return 1116 // random or otherwise changing results, effectively making compare function inconsistent. 1117 1118 Vector<ValueStringPair, 0, UnsafeVectorOverflow> values(relevantLength); 1119 if (!values.begin()) { 1120 throwOutOfMemoryError(exec); 1121 return; 1122 } 1123 1124 Heap::heap(this)->pushTempSortVector(&values); 1125 1126 bool isSortingPrimitiveValues = true; 1127 1128 for (size_t i = 0; i < relevantLength; i++) { 1129 JSValue value = ContiguousTypeAccessor<indexingType>::getAsValue(data, i); 1130 ASSERT(indexingType != ArrayWithInt32 || value.isInt32()); 1131 ASSERT(!value.isUndefined()); 1132 values[i].first = value; 1133 if (indexingType != ArrayWithDouble && indexingType != ArrayWithInt32) 1134 isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive(); 1135 } 1136 1137 // FIXME: The following loop continues to call toString on subsequent values even after 1138 // a toString call raises an exception. 1139 1140 for (size_t i = 0; i < relevantLength; i++) 1141 values[i].second = values[i].first.toWTFStringInline(exec); 1142 1143 if (exec->hadException()) { 1144 Heap::heap(this)->popTempSortVector(&values); 1145 return; 1146 } 1147 1148 // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather 1149 // than O(N log N). 1150 1151#if HAVE(MERGESORT) 1152 if (isSortingPrimitiveValues) 1153 qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort); 1154 else 1155 mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort); 1156#else 1157 // FIXME: The qsort library function is likely to not be a stable sort. 1158 // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort. 1159 qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort); 1160#endif 1161 1162 // If the toString function changed the length of the array or vector storage, 1163 // increase the length to handle the orignal number of actual values. 1164 switch (indexingType) { 1165 case ArrayWithInt32: 1166 case ArrayWithDouble: 1167 case ArrayWithContiguous: 1168 ensureLength(vm, relevantLength); 1169 break; 1170 1171 case ArrayWithArrayStorage: 1172 if (arrayStorage()->vectorLength() < relevantLength) { 1173 increaseVectorLength(exec->vm(), relevantLength); 1174 ContiguousTypeAccessor<indexingType>::replaceDataReference(&data, arrayStorage()->vector()); 1175 } 1176 if (arrayStorage()->length() < relevantLength) 1177 arrayStorage()->setLength(relevantLength); 1178 break; 1179 1180 default: 1181 CRASH(); 1182 } 1183 1184 for (size_t i = 0; i < relevantLength; i++) 1185 ContiguousTypeAccessor<indexingType>::setWithValue(vm, this, data, i, values[i].first); 1186 1187 Heap::heap(this)->popTempSortVector(&values); 1188} 1189 1190void JSArray::sort(ExecState* exec) 1191{ 1192 ASSERT(!inSparseIndexingMode()); 1193 1194 switch (structure()->indexingType()) { 1195 case ArrayClass: 1196 case ArrayWithUndecided: 1197 return; 1198 1199 case ArrayWithInt32: { 1200 unsigned lengthNotIncludingUndefined; 1201 unsigned newRelevantLength; 1202 compactForSorting<ArrayWithInt32>( 1203 lengthNotIncludingUndefined, newRelevantLength); 1204 1205 sortCompactedVector<ArrayWithInt32>( 1206 exec, m_butterfly->contiguousInt32(), lengthNotIncludingUndefined); 1207 return; 1208 } 1209 1210 case ArrayWithDouble: { 1211 unsigned lengthNotIncludingUndefined; 1212 unsigned newRelevantLength; 1213 compactForSorting<ArrayWithDouble>( 1214 lengthNotIncludingUndefined, newRelevantLength); 1215 1216 sortCompactedVector<ArrayWithDouble>( 1217 exec, m_butterfly->contiguousDouble(), lengthNotIncludingUndefined); 1218 return; 1219 } 1220 1221 case ArrayWithContiguous: { 1222 unsigned lengthNotIncludingUndefined; 1223 unsigned newRelevantLength; 1224 compactForSorting<ArrayWithContiguous>( 1225 lengthNotIncludingUndefined, newRelevantLength); 1226 1227 sortCompactedVector<ArrayWithContiguous>( 1228 exec, m_butterfly->contiguous(), lengthNotIncludingUndefined); 1229 return; 1230 } 1231 1232 case ArrayWithArrayStorage: { 1233 unsigned lengthNotIncludingUndefined; 1234 unsigned newRelevantLength; 1235 compactForSorting<ArrayWithArrayStorage>( 1236 lengthNotIncludingUndefined, newRelevantLength); 1237 ArrayStorage* storage = m_butterfly->arrayStorage(); 1238 ASSERT(!storage->m_sparseMap); 1239 1240 sortCompactedVector<ArrayWithArrayStorage>(exec, storage->vector(), lengthNotIncludingUndefined); 1241 return; 1242 } 1243 1244 default: 1245 RELEASE_ASSERT_NOT_REACHED(); 1246 } 1247} 1248 1249struct AVLTreeNodeForArrayCompare { 1250 JSValue value; 1251 1252 // Child pointers. The high bit of gt is robbed and used as the 1253 // balance factor sign. The high bit of lt is robbed and used as 1254 // the magnitude of the balance factor. 1255 int32_t gt; 1256 int32_t lt; 1257}; 1258 1259struct AVLTreeAbstractorForArrayCompare { 1260 typedef int32_t handle; // Handle is an index into m_nodes vector. 1261 typedef JSValue key; 1262 typedef int32_t size; 1263 1264 Vector<AVLTreeNodeForArrayCompare, 0, UnsafeVectorOverflow> m_nodes; 1265 ExecState* m_exec; 1266 JSValue m_compareFunction; 1267 CallType m_compareCallType; 1268 const CallData* m_compareCallData; 1269 OwnPtr<CachedCall> m_cachedCall; 1270 1271 handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; } 1272 void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; } 1273 handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; } 1274 void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; } 1275 1276 int get_balance_factor(handle h) 1277 { 1278 if (m_nodes[h].gt & 0x80000000) 1279 return -1; 1280 return static_cast<unsigned>(m_nodes[h].lt) >> 31; 1281 } 1282 1283 void set_balance_factor(handle h, int bf) 1284 { 1285 if (bf == 0) { 1286 m_nodes[h].lt &= 0x7FFFFFFF; 1287 m_nodes[h].gt &= 0x7FFFFFFF; 1288 } else { 1289 m_nodes[h].lt |= 0x80000000; 1290 if (bf < 0) 1291 m_nodes[h].gt |= 0x80000000; 1292 else 1293 m_nodes[h].gt &= 0x7FFFFFFF; 1294 } 1295 } 1296 1297 int compare_key_key(key va, key vb) 1298 { 1299 ASSERT(!va.isUndefined()); 1300 ASSERT(!vb.isUndefined()); 1301 1302 if (m_exec->hadException()) 1303 return 1; 1304 1305 double compareResult; 1306 if (m_cachedCall) { 1307 m_cachedCall->setThis(jsUndefined()); 1308 m_cachedCall->setArgument(0, va); 1309 m_cachedCall->setArgument(1, vb); 1310 compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec)); 1311 } else { 1312 MarkedArgumentBuffer arguments; 1313 arguments.append(va); 1314 arguments.append(vb); 1315 compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, jsUndefined(), arguments).toNumber(m_exec); 1316 } 1317 return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent. 1318 } 1319 1320 int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); } 1321 int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); } 1322 1323 static handle null() { return 0x7FFFFFFF; } 1324}; 1325 1326template<IndexingType indexingType> 1327void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) 1328{ 1329 ASSERT(!inSparseIndexingMode()); 1330 ASSERT(indexingType == structure()->indexingType()); 1331 1332 // FIXME: This ignores exceptions raised in the compare function or in toNumber. 1333 1334 // The maximum tree depth is compiled in - but the caller is clearly up to no good 1335 // if a larger array is passed. 1336 ASSERT(m_butterfly->publicLength() <= static_cast<unsigned>(std::numeric_limits<int>::max())); 1337 if (m_butterfly->publicLength() > static_cast<unsigned>(std::numeric_limits<int>::max())) 1338 return; 1339 1340 unsigned usedVectorLength = relevantLength<indexingType>(); 1341 unsigned nodeCount = usedVectorLength; 1342 1343 if (!nodeCount) 1344 return; 1345 1346 AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items 1347 tree.abstractor().m_exec = exec; 1348 tree.abstractor().m_compareFunction = compareFunction; 1349 tree.abstractor().m_compareCallType = callType; 1350 tree.abstractor().m_compareCallData = &callData; 1351 tree.abstractor().m_nodes.grow(nodeCount); 1352 1353 if (callType == CallTypeJS) 1354 tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, jsCast<JSFunction*>(compareFunction), 2)); 1355 1356 if (!tree.abstractor().m_nodes.begin()) { 1357 throwOutOfMemoryError(exec); 1358 return; 1359 } 1360 1361 // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified 1362 // right out from under us while we're building the tree here. 1363 1364 unsigned numDefined = 0; 1365 unsigned numUndefined = 0; 1366 1367 // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree. 1368 for (; numDefined < usedVectorLength; ++numDefined) { 1369 if (numDefined >= m_butterfly->vectorLength()) 1370 break; 1371 JSValue v = getHolyIndexQuickly(numDefined); 1372 if (!v || v.isUndefined()) 1373 break; 1374 tree.abstractor().m_nodes[numDefined].value = v; 1375 tree.insert(numDefined); 1376 } 1377 for (unsigned i = numDefined; i < usedVectorLength; ++i) { 1378 if (i >= m_butterfly->vectorLength()) 1379 break; 1380 JSValue v = getHolyIndexQuickly(i); 1381 if (v) { 1382 if (v.isUndefined()) 1383 ++numUndefined; 1384 else { 1385 tree.abstractor().m_nodes[numDefined].value = v; 1386 tree.insert(numDefined); 1387 ++numDefined; 1388 } 1389 } 1390 } 1391 1392 unsigned newUsedVectorLength = numDefined + numUndefined; 1393 1394 // The array size may have changed. Figure out the new bounds. 1395 unsigned newestUsedVectorLength = currentRelevantLength(); 1396 1397 unsigned elementsToExtractThreshold = min(min(newestUsedVectorLength, numDefined), static_cast<unsigned>(tree.abstractor().m_nodes.size())); 1398 unsigned undefinedElementsThreshold = min(newestUsedVectorLength, newUsedVectorLength); 1399 unsigned clearElementsThreshold = min(newestUsedVectorLength, usedVectorLength); 1400 1401 // Copy the values back into m_storage. 1402 AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter; 1403 iter.start_iter_least(tree); 1404 VM& vm = exec->vm(); 1405 for (unsigned i = 0; i < elementsToExtractThreshold; ++i) { 1406 ASSERT(i < butterfly()->vectorLength()); 1407 if (structure()->indexingType() == ArrayWithDouble) 1408 butterfly()->contiguousDouble()[i] = tree.abstractor().m_nodes[*iter].value.asNumber(); 1409 else 1410 currentIndexingData()[i].set(vm, this, tree.abstractor().m_nodes[*iter].value); 1411 ++iter; 1412 } 1413 // Put undefined values back in. 1414 switch (structure()->indexingType()) { 1415 case ArrayWithInt32: 1416 case ArrayWithDouble: 1417 ASSERT(elementsToExtractThreshold == undefinedElementsThreshold); 1418 break; 1419 1420 default: 1421 for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i) { 1422 ASSERT(i < butterfly()->vectorLength()); 1423 currentIndexingData()[i].setUndefined(); 1424 } 1425 } 1426 1427 // Ensure that unused values in the vector are zeroed out. 1428 for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i) { 1429 ASSERT(i < butterfly()->vectorLength()); 1430 if (structure()->indexingType() == ArrayWithDouble) 1431 butterfly()->contiguousDouble()[i] = QNaN; 1432 else 1433 currentIndexingData()[i].clear(); 1434 } 1435 1436 if (hasArrayStorage(structure()->indexingType())) 1437 arrayStorage()->m_numValuesInVector = newUsedVectorLength; 1438} 1439 1440void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData) 1441{ 1442 ASSERT(!inSparseIndexingMode()); 1443 1444 switch (structure()->indexingType()) { 1445 case ArrayClass: 1446 case ArrayWithUndecided: 1447 return; 1448 1449 case ArrayWithInt32: 1450 sortVector<ArrayWithInt32>(exec, compareFunction, callType, callData); 1451 return; 1452 1453 case ArrayWithDouble: 1454 sortVector<ArrayWithDouble>(exec, compareFunction, callType, callData); 1455 return; 1456 1457 case ArrayWithContiguous: 1458 sortVector<ArrayWithContiguous>(exec, compareFunction, callType, callData); 1459 return; 1460 1461 case ArrayWithArrayStorage: 1462 sortVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData); 1463 return; 1464 1465 default: 1466 RELEASE_ASSERT_NOT_REACHED(); 1467 } 1468} 1469 1470void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args) 1471{ 1472 unsigned i = 0; 1473 unsigned vectorEnd; 1474 WriteBarrier<Unknown>* vector; 1475 1476 switch (structure()->indexingType()) { 1477 case ArrayClass: 1478 return; 1479 1480 case ArrayWithUndecided: { 1481 vector = 0; 1482 vectorEnd = 0; 1483 break; 1484 } 1485 1486 case ArrayWithInt32: 1487 case ArrayWithContiguous: { 1488 vectorEnd = m_butterfly->publicLength(); 1489 vector = m_butterfly->contiguous().data(); 1490 break; 1491 } 1492 1493 case ArrayWithDouble: { 1494 vector = 0; 1495 vectorEnd = 0; 1496 for (; i < m_butterfly->publicLength(); ++i) { 1497 double v = butterfly()->contiguousDouble()[i]; 1498 if (v != v) 1499 break; 1500 args.append(JSValue(JSValue::EncodeAsDouble, v)); 1501 } 1502 break; 1503 } 1504 1505 case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: { 1506 ArrayStorage* storage = m_butterfly->arrayStorage(); 1507 1508 vector = storage->m_vector; 1509 vectorEnd = min(storage->length(), storage->vectorLength()); 1510 break; 1511 } 1512 1513 default: 1514 CRASH(); 1515 vector = 0; 1516 vectorEnd = 0; 1517 break; 1518 } 1519 1520 for (; i < vectorEnd; ++i) { 1521 WriteBarrier<Unknown>& v = vector[i]; 1522 if (!v) 1523 break; 1524 args.append(v.get()); 1525 } 1526 1527 for (; i < length(); ++i) 1528 args.append(get(exec, i)); 1529} 1530 1531void JSArray::copyToArguments(ExecState* exec, CallFrame* callFrame, uint32_t length) 1532{ 1533 unsigned i = 0; 1534 WriteBarrier<Unknown>* vector; 1535 unsigned vectorEnd; 1536 1537 ASSERT(length == this->length()); 1538 switch (structure()->indexingType()) { 1539 case ArrayClass: 1540 return; 1541 1542 case ArrayWithUndecided: { 1543 vector = 0; 1544 vectorEnd = 0; 1545 break; 1546 } 1547 1548 case ArrayWithInt32: 1549 case ArrayWithContiguous: { 1550 vector = m_butterfly->contiguous().data(); 1551 vectorEnd = m_butterfly->publicLength(); 1552 break; 1553 } 1554 1555 case ArrayWithDouble: { 1556 vector = 0; 1557 vectorEnd = 0; 1558 for (; i < m_butterfly->publicLength(); ++i) { 1559 ASSERT(i < butterfly()->vectorLength()); 1560 double v = m_butterfly->contiguousDouble()[i]; 1561 if (v != v) 1562 break; 1563 callFrame->setArgument(i, JSValue(JSValue::EncodeAsDouble, v)); 1564 } 1565 break; 1566 } 1567 1568 case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: { 1569 ArrayStorage* storage = m_butterfly->arrayStorage(); 1570 vector = storage->m_vector; 1571 vectorEnd = min(length, storage->vectorLength()); 1572 break; 1573 } 1574 1575 default: 1576 CRASH(); 1577 vector = 0; 1578 vectorEnd = 0; 1579 break; 1580 } 1581 1582 for (; i < vectorEnd; ++i) { 1583 WriteBarrier<Unknown>& v = vector[i]; 1584 if (!v) 1585 break; 1586 callFrame->setArgument(i, v.get()); 1587 } 1588 1589 for (; i < length; ++i) 1590 callFrame->setArgument(i, get(exec, i)); 1591} 1592 1593template<IndexingType indexingType> 1594void JSArray::compactForSorting(unsigned& numDefined, unsigned& newRelevantLength) 1595{ 1596 ASSERT(!inSparseIndexingMode()); 1597 ASSERT(indexingType == structure()->indexingType()); 1598 1599 unsigned myRelevantLength = relevantLength<indexingType>(); 1600 1601 numDefined = 0; 1602 unsigned numUndefined = 0; 1603 1604 for (; numDefined < myRelevantLength; ++numDefined) { 1605 ASSERT(numDefined < m_butterfly->vectorLength()); 1606 if (indexingType == ArrayWithInt32) { 1607 JSValue v = m_butterfly->contiguousInt32()[numDefined].get(); 1608 if (!v) 1609 break; 1610 ASSERT(v.isInt32()); 1611 continue; 1612 } 1613 if (indexingType == ArrayWithDouble) { 1614 double v = m_butterfly->contiguousDouble()[numDefined]; 1615 if (v != v) 1616 break; 1617 continue; 1618 } 1619 JSValue v = indexingData<indexingType>()[numDefined].get(); 1620 if (!v || v.isUndefined()) 1621 break; 1622 } 1623 1624 for (unsigned i = numDefined; i < myRelevantLength; ++i) { 1625 ASSERT(i < m_butterfly->vectorLength()); 1626 if (indexingType == ArrayWithInt32) { 1627 JSValue v = m_butterfly->contiguousInt32()[i].get(); 1628 if (!v) 1629 continue; 1630 ASSERT(v.isInt32()); 1631 ASSERT(numDefined < m_butterfly->vectorLength()); 1632 m_butterfly->contiguousInt32()[numDefined++].setWithoutWriteBarrier(v); 1633 continue; 1634 } 1635 if (indexingType == ArrayWithDouble) { 1636 double v = m_butterfly->contiguousDouble()[i]; 1637 if (v != v) 1638 continue; 1639 ASSERT(numDefined < m_butterfly->vectorLength()); 1640 m_butterfly->contiguousDouble()[numDefined++] = v; 1641 continue; 1642 } 1643 JSValue v = indexingData<indexingType>()[i].get(); 1644 if (v) { 1645 if (v.isUndefined()) 1646 ++numUndefined; 1647 else { 1648 ASSERT(numDefined < m_butterfly->vectorLength()); 1649 indexingData<indexingType>()[numDefined++].setWithoutWriteBarrier(v); 1650 } 1651 } 1652 } 1653 1654 newRelevantLength = numDefined + numUndefined; 1655 1656 if (hasArrayStorage(indexingType)) 1657 RELEASE_ASSERT(!arrayStorage()->m_sparseMap); 1658 1659 switch (indexingType) { 1660 case ArrayWithInt32: 1661 case ArrayWithDouble: 1662 RELEASE_ASSERT(numDefined == newRelevantLength); 1663 break; 1664 1665 default: 1666 for (unsigned i = numDefined; i < newRelevantLength; ++i) { 1667 ASSERT(i < m_butterfly->vectorLength()); 1668 indexingData<indexingType>()[i].setUndefined(); 1669 } 1670 break; 1671 } 1672 for (unsigned i = newRelevantLength; i < myRelevantLength; ++i) { 1673 ASSERT(i < m_butterfly->vectorLength()); 1674 if (indexingType == ArrayWithDouble) 1675 m_butterfly->contiguousDouble()[i] = QNaN; 1676 else 1677 indexingData<indexingType>()[i].clear(); 1678 } 1679 1680 if (hasArrayStorage(indexingType)) 1681 arrayStorage()->m_numValuesInVector = newRelevantLength; 1682} 1683 1684} // namespace JSC 1685