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