Source/JavaScriptCore/runtime/JSArray.cpp

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