code.vuplus.com Git - vuplus_webkit/blob - 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};
  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 JSArray::~JSArray()
 240 {
 241     ASSERT(vptr() == JSGlobalData::jsArrayVPtr);
 242     checkConsistency(DestructorConsistencyCheck);
 243
 244     delete m_storage->m_sparseValueMap;
 245     fastFree(m_storage->m_allocBase);
 246 }
 247
 248 bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
 249 {
 250     ArrayStorage* storage = m_storage;
 251
 252     if (i >= storage->m_length) {
 253         if (i > MAX_ARRAY_INDEX)
 254             return getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
 255         return false;
 256     }
 257
 258     if (i < m_vectorLength) {
 259         JSValue value = storage->m_vector[i].get();
 260         if (value) {
 261             slot.setValue(value);
 262             return true;
 263         }
 264     } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 265         if (i >= MIN_SPARSE_ARRAY_INDEX) {
 266             SparseArrayValueMap::iterator it = map->find(i);
 267             if (it != map->end()) {
 268                 slot.setValue(it->second.get());
 269                 return true;
 270             }
 271         }
 272     }
 273
 274     return JSObject::getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
 275 }
 276
 277 bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
 278 {
 279     if (propertyName == exec->propertyNames().length) {
 280         slot.setValue(jsNumber(length()));
 281         return true;
 282     }
 283
 284     bool isArrayIndex;
 285     unsigned i = propertyName.toArrayIndex(isArrayIndex);
 286     if (isArrayIndex)
 287         return JSArray::getOwnPropertySlot(exec, i, slot);
 288
 289     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
 290 }
 291
 292 bool JSArray::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
 293 {
 294     if (propertyName == exec->propertyNames().length) {
 295         descriptor.setDescriptor(jsNumber(length()), DontDelete | DontEnum);
 296         return true;
 297     }
 298
 299     ArrayStorage* storage = m_storage;
 300
 301     bool isArrayIndex;
 302     unsigned i = propertyName.toArrayIndex(isArrayIndex);
 303     if (isArrayIndex) {
 304         if (i >= storage->m_length)
 305             return false;
 306         if (i < m_vectorLength) {
 307             WriteBarrier<Unknown>& value = storage->m_vector[i];
 308             if (value) {
 309                 descriptor.setDescriptor(value.get(), 0);
 310                 return true;
 311             }
 312         } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 313             if (i >= MIN_SPARSE_ARRAY_INDEX) {
 314                 SparseArrayValueMap::iterator it = map->find(i);
 315                 if (it != map->end()) {
 316                     descriptor.setDescriptor(it->second.get(), 0);
 317                     return true;
 318                 }
 319             }
 320         }
 321     }
 322     return JSObject::getOwnPropertyDescriptor(exec, propertyName, descriptor);
 323 }
 324
 325 // ECMA 15.4.5.1
 326 void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
 327 {
 328     bool isArrayIndex;
 329     unsigned i = propertyName.toArrayIndex(isArrayIndex);
 330     if (isArrayIndex) {
 331         put(exec, i, value);
 332         return;
 333     }
 334
 335     if (propertyName == exec->propertyNames().length) {
 336         unsigned newLength = value.toUInt32(exec);
 337         if (value.toNumber(exec) != static_cast<double>(newLength)) {
 338             throwError(exec, createRangeError(exec, "Invalid array length"));
 339             return;
 340         }
 341         setLength(newLength);
 342         return;
 343     }
 344
 345     JSObject::put(exec, propertyName, value, slot);
 346 }
 347
 348 void JSArray::put(ExecState* exec, unsigned i, JSValue value)
 349 {
 350     checkConsistency();
 351
 352     ArrayStorage* storage = m_storage;
 353
 354     unsigned length = storage->m_length;
 355     if (i >= length && i <= MAX_ARRAY_INDEX) {
 356         length = i + 1;
 357         storage->m_length = length;
 358     }
 359
 360     if (i < m_vectorLength) {
 361         WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
 362         if (valueSlot) {
 363             valueSlot.set(exec->globalData(), this, value);
 364             checkConsistency();
 365             return;
 366         }
 367         valueSlot.set(exec->globalData(), this, value);
 368         ++storage->m_numValuesInVector;
 369         checkConsistency();
 370         return;
 371     }
 372
 373     putSlowCase(exec, i, value);
 374 }
 375
 376 NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
 377 {
 378     ArrayStorage* storage = m_storage;
 379
 380     SparseArrayValueMap* map = storage->m_sparseValueMap;
 381
 382     if (i >= MIN_SPARSE_ARRAY_INDEX) {
 383         if (i > MAX_ARRAY_INDEX) {
 384             PutPropertySlot slot;
 385             put(exec, Identifier::from(exec, i), value, slot);
 386             return;
 387         }
 388
 389         // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
 390         // (which will only be compacted as we reach indices that are less than MIN_SPARSE_ARRAY_INDEX) - but this makes the check much faster.
 391         if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
 392             if (!map) {
 393                 map = new SparseArrayValueMap;
 394                 storage->m_sparseValueMap = map;
 395             }
 396
 397             WriteBarrier<Unknown> temp;
 398             pair<SparseArrayValueMap::iterator, bool> result = map->add(i, temp);
 399             result.first->second.set(exec->globalData(), this, value);
 400             if (!result.second) // pre-existing entry
 401                 return;
 402
 403             size_t capacity = map->capacity();
 404             if (capacity != storage->reportedMapCapacity) {
 405                 Heap::heap(this)->reportExtraMemoryCost((capacity - storage->reportedMapCapacity) * (sizeof(unsigned) + sizeof(JSValue)));
 406                 storage->reportedMapCapacity = capacity;
 407             }
 408             return;
 409         }
 410     }
 411
 412     // We have decided that we'll put the new item into the vector.
 413     // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
 414     if (!map || map->isEmpty()) {
 415         if (increaseVectorLength(i + 1)) {
 416             storage = m_storage;
 417             storage->m_vector[i].set(exec->globalData(), this, value);
 418             ++storage->m_numValuesInVector;
 419             checkConsistency();
 420         } else
 421             throwOutOfMemoryError(exec);
 422         return;
 423     }
 424
 425     // Decide how many values it would be best to move from the map.
 426     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
 427     unsigned newVectorLength = getNewVectorLength(i + 1);
 428     for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
 429         newNumValuesInVector += map->contains(j);
 430     if (i >= MIN_SPARSE_ARRAY_INDEX)
 431         newNumValuesInVector -= map->contains(i);
 432     if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
 433         unsigned needLength = max(i + 1, storage->m_length);
 434         unsigned proposedNewNumValuesInVector = newNumValuesInVector;
 435         // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
 436         while ((newVectorLength < needLength) && (newVectorLength < MAX_STORAGE_VECTOR_LENGTH)) {
 437             unsigned proposedNewVectorLength = getNewVectorLength(newVectorLength + 1);
 438             for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
 439                 proposedNewNumValuesInVector += map->contains(j);
 440             if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
 441                 break;
 442             newVectorLength = proposedNewVectorLength;
 443             newNumValuesInVector = proposedNewNumValuesInVector;
 444         }
 445     }
 446
 447     void* baseStorage = storage->m_allocBase;
 448
 449     if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) {
 450         throwOutOfMemoryError(exec);
 451         return;
 452     }
 453
 454     m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
 455     m_storage->m_allocBase = baseStorage;
 456     storage = m_storage;
 457
 458     unsigned vectorLength = m_vectorLength;
 459     WriteBarrier<Unknown>* vector = storage->m_vector;
 460
 461     if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
 462         for (unsigned j = vectorLength; j < newVectorLength; ++j)
 463             vector[j].clear();
 464         if (i > MIN_SPARSE_ARRAY_INDEX)
 465             map->remove(i);
 466     } else {
 467         for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
 468             vector[j].clear();
 469         JSGlobalData& globalData = exec->globalData();
 470         for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
 471             vector[j].set(globalData, this, map->take(j).get());
 472     }
 473
 474     ASSERT(i < newVectorLength);
 475
 476     m_vectorLength = newVectorLength;
 477     storage->m_numValuesInVector = newNumValuesInVector;
 478
 479     storage->m_vector[i].set(exec->globalData(), this, 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         WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
 507         if (!valueSlot) {
 508             checkConsistency();
 509             return false;
 510         }
 511         valueSlot.clear();
 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     WriteBarrier<Unknown>* vector = storage->m_vector;
 609     for (unsigned i = vectorLength; i < newVectorLength; ++i)
 610         vector[i].clear();
 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     ASSERT(newLength > vectorLength);
 647     unsigned delta = newLength - vectorLength;
 648     for (unsigned i = 0; i < delta; i++)
 649         m_storage->m_vector[i].clear();
 650     Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
 651
 652     return true;
 653 }
 654
 655
 656 void JSArray::setLength(unsigned newLength)
 657 {
 658     ArrayStorage* storage = m_storage;
 659
 660 #if CHECK_ARRAY_CONSISTENCY
 661     if (!storage->m_inCompactInitialization)
 662         checkConsistency();
 663     else
 664         storage->m_inCompactInitialization = false;
 665 #endif
 666
 667     unsigned length = storage->m_length;
 668
 669     if (newLength < length) {
 670         unsigned usedVectorLength = min(length, m_vectorLength);
 671         for (unsigned i = newLength; i < usedVectorLength; ++i) {
 672             WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
 673             bool hadValue = valueSlot;
 674             valueSlot.clear();
 675             storage->m_numValuesInVector -= hadValue;
 676         }
 677
 678         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 679             SparseArrayValueMap copy = *map;
 680             SparseArrayValueMap::iterator end = copy.end();
 681             for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
 682                 if (it->first >= newLength)
 683                     map->remove(it->first);
 684             }
 685             if (map->isEmpty()) {
 686                 delete map;
 687                 storage->m_sparseValueMap = 0;
 688             }
 689         }
 690     }
 691
 692     storage->m_length = newLength;
 693
 694     checkConsistency();
 695 }
 696
 697 JSValue JSArray::pop()
 698 {
 699     checkConsistency();
 700
 701     ArrayStorage* storage = m_storage;
 702
 703     unsigned length = storage->m_length;
 704     if (!length)
 705         return jsUndefined();
 706
 707     --length;
 708
 709     JSValue result;
 710
 711     if (length < m_vectorLength) {
 712         WriteBarrier<Unknown>& valueSlot = storage->m_vector[length];
 713         if (valueSlot) {
 714             --storage->m_numValuesInVector;
 715             result = valueSlot.get();
 716             valueSlot.clear();
 717         } else
 718             result = jsUndefined();
 719     } else {
 720         result = jsUndefined();
 721         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 722             SparseArrayValueMap::iterator it = map->find(length);
 723             if (it != map->end()) {
 724                 result = it->second.get();
 725                 map->remove(it);
 726                 if (map->isEmpty()) {
 727                     delete map;
 728                     storage->m_sparseValueMap = 0;
 729                 }
 730             }
 731         }
 732     }
 733
 734     storage->m_length = length;
 735
 736     checkConsistency();
 737
 738     return result;
 739 }
 740
 741 void JSArray::push(ExecState* exec, JSValue value)
 742 {
 743     checkConsistency();
 744
 745     ArrayStorage* storage = m_storage;
 746
 747     if (UNLIKELY(storage->m_length == 0xFFFFFFFFu)) {
 748         put(exec, storage->m_length, value);
 749         throwError(exec, createRangeError(exec, "Invalid array length"));
 750         return;
 751     }
 752
 753     if (storage->m_length < m_vectorLength) {
 754         storage->m_vector[storage->m_length].set(exec->globalData(), this, value);
 755         ++storage->m_numValuesInVector;
 756         ++storage->m_length;
 757         checkConsistency();
 758         return;
 759     }
 760
 761     if (storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
 762         SparseArrayValueMap* map = storage->m_sparseValueMap;
 763         if (!map || map->isEmpty()) {
 764             if (increaseVectorLength(storage->m_length + 1)) {
 765                 storage = m_storage;
 766                 storage->m_vector[storage->m_length].set(exec->globalData(), this, value);
 767                 ++storage->m_numValuesInVector;
 768                 ++storage->m_length;
 769                 checkConsistency();
 770                 return;
 771             }
 772             checkConsistency();
 773             throwOutOfMemoryError(exec);
 774             return;
 775         }
 776     }
 777
 778     putSlowCase(exec, storage->m_length++, value);
 779 }
 780
 781 void JSArray::shiftCount(ExecState* exec, int count)
 782 {
 783     ASSERT(count > 0);
 784
 785     ArrayStorage* storage = m_storage;
 786
 787     unsigned oldLength = storage->m_length;
 788
 789     if (!oldLength)
 790         return;
 791
 792     if (oldLength != storage->m_numValuesInVector) {
 793         // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
 794         // which means we need to go through each entry looking for the the "empty"
 795         // slots and then fill them with possible properties.  See ECMA spec.
 796         // 15.4.4.9 steps 11 through 13.
 797         for (unsigned i = count; i < oldLength; ++i) {
 798             if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
 799                 PropertySlot slot(this);
 800                 JSValue p = prototype();
 801                 if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
 802                     put(exec, i, slot.getValue(exec, i));
 803             }
 804         }
 805
 806         storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
 807
 808         // Need to decrement numValuesInvector based on number of real entries
 809         for (unsigned i = 0; i < (unsigned)count; ++i)
 810             if ((i < m_vectorLength) && (storage->m_vector[i]))
 811                 --storage->m_numValuesInVector;
 812     } else
 813         storage->m_numValuesInVector -= count;
 814
 815     storage->m_length -= count;
 816
 817     if (m_vectorLength) {
 818         count = min(m_vectorLength, (unsigned)count);
 819
 820         m_vectorLength -= count;
 821
 822         if (m_vectorLength) {
 823             char* newBaseStorage = reinterpret_cast<char*>(storage) + count * sizeof(JSValue);
 824             memmove(newBaseStorage, storage, storageSize(0));
 825             m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
 826
 827             m_indexBias += count;
 828         }
 829     }
 830 }
 831
 832 void JSArray::unshiftCount(ExecState* exec, int count)
 833 {
 834     ArrayStorage* storage = m_storage;
 835
 836     ASSERT(m_indexBias >= 0);
 837     ASSERT(count >= 0);
 838
 839     unsigned length = storage->m_length;
 840
 841     if (length != storage->m_numValuesInVector) {
 842         // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
 843         // which means we need to go through each entry looking for the the "empty"
 844         // slots and then fill them with possible properties.  See ECMA spec.
 845         // 15.4.4.13 steps 8 through 10.
 846         for (unsigned i = 0; i < length; ++i) {
 847             if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
 848                 PropertySlot slot(this);
 849                 JSValue p = prototype();
 850                 if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
 851                     put(exec, i, slot.getValue(exec, i));
 852             }
 853         }
 854     }
 855
 856     storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
 857
 858     if (m_indexBias >= count) {
 859         m_indexBias -= count;
 860         char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(JSValue);
 861         memmove(newBaseStorage, storage, storageSize(0));
 862         m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
 863         m_vectorLength += count;
 864     } else if (!increaseVectorPrefixLength(m_vectorLength + count)) {
 865         throwOutOfMemoryError(exec);
 866         return;
 867     }
 868
 869     WriteBarrier<Unknown>* vector = m_storage->m_vector;
 870     for (int i = 0; i < count; i++)
 871         vector[i].clear();
 872 }
 873
 874 void JSArray::visitChildren(SlotVisitor& visitor)
 875 {
 876     ASSERT_GC_OBJECT_INHERITS(this, &s_info);
 877     COMPILE_ASSERT(StructureFlags & OverridesVisitChildren, OverridesVisitChildrenWithoutSettingFlag);
 878     ASSERT(structure()->typeInfo().overridesVisitChildren());
 879     visitChildrenDirect(visitor);
 880 }
 881
 882 static int compareNumbersForQSort(const void* a, const void* b)
 883 {
 884     double da = static_cast<const JSValue*>(a)->uncheckedGetNumber();
 885     double db = static_cast<const JSValue*>(b)->uncheckedGetNumber();
 886     return (da > db) - (da < db);
 887 }
 888
 889 static int compareByStringPairForQSort(const void* a, const void* b)
 890 {
 891     const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
 892     const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
 893     return codePointCompare(va->second, vb->second);
 894 }
 895
 896 void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
 897 {
 898     ArrayStorage* storage = m_storage;
 899
 900     unsigned lengthNotIncludingUndefined = compactForSorting();
 901     if (storage->m_sparseValueMap) {
 902         throwOutOfMemoryError(exec);
 903         return;
 904     }
 905
 906     if (!lengthNotIncludingUndefined)
 907         return;
 908
 909     bool allValuesAreNumbers = true;
 910     size_t size = storage->m_numValuesInVector;
 911     for (size_t i = 0; i < size; ++i) {
 912         if (!storage->m_vector[i].isNumber()) {
 913             allValuesAreNumbers = false;
 914             break;
 915         }
 916     }
 917
 918     if (!allValuesAreNumbers)
 919         return sort(exec, compareFunction, callType, callData);
 920
 921     // For numeric comparison, which is fast, qsort is faster than mergesort. We
 922     // also don't require mergesort's stability, since there's no user visible
 923     // side-effect from swapping the order of equal primitive values.
 924     qsort(storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort);
 925
 926     checkConsistency(SortConsistencyCheck);
 927 }
 928
 929 void JSArray::sort(ExecState* exec)
 930 {
 931     ArrayStorage* storage = m_storage;
 932
 933     unsigned lengthNotIncludingUndefined = compactForSorting();
 934     if (storage->m_sparseValueMap) {
 935         throwOutOfMemoryError(exec);
 936         return;
 937     }
 938
 939     if (!lengthNotIncludingUndefined)
 940         return;
 941
 942     // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
 943     // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
 944     // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
 945     // random or otherwise changing results, effectively making compare function inconsistent.
 946
 947     Vector<ValueStringPair> values(lengthNotIncludingUndefined);
 948     if (!values.begin()) {
 949         throwOutOfMemoryError(exec);
 950         return;
 951     }
 952
 953     Heap::heap(this)->pushTempSortVector(&values);
 954
 955     for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
 956         JSValue value = storage->m_vector[i].get();
 957         ASSERT(!value.isUndefined());
 958         values[i].first = value;
 959     }
 960
 961     // FIXME: The following loop continues to call toString on subsequent values even after
 962     // a toString call raises an exception.
 963
 964     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
 965         values[i].second = values[i].first.toString(exec);
 966
 967     if (exec->hadException()) {
 968         Heap::heap(this)->popTempSortVector(&values);
 969         return;
 970     }
 971
 972     // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
 973     // than O(N log N).
 974
 975 #if HAVE(MERGESORT)
 976     mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 977 #else
 978     // FIXME: The qsort library function is likely to not be a stable sort.
 979     // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
 980     qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 981 #endif
 982
 983     // If the toString function changed the length of the array or vector storage,
 984     // increase the length to handle the orignal number of actual values.
 985     if (m_vectorLength < lengthNotIncludingUndefined)
 986         increaseVectorLength(lengthNotIncludingUndefined);
 987     if (storage->m_length < lengthNotIncludingUndefined)
 988         storage->m_length = lengthNotIncludingUndefined;
 989
 990     JSGlobalData& globalData = exec->globalData();
 991     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
 992         storage->m_vector[i].set(globalData, this, values[i].first);
 993
 994     Heap::heap(this)->popTempSortVector(&values);
 995
 996     checkConsistency(SortConsistencyCheck);
 997 }
 998
 999 struct AVLTreeNodeForArrayCompare {
1000     JSValue value;
1001
1002     // Child pointers.  The high bit of gt is robbed and used as the
1003     // balance factor sign.  The high bit of lt is robbed and used as
1004     // the magnitude of the balance factor.
1005     int32_t gt;
1006     int32_t lt;
1007 };
1008
1009 struct AVLTreeAbstractorForArrayCompare {
1010     typedef int32_t handle; // Handle is an index into m_nodes vector.
1011     typedef JSValue key;
1012     typedef int32_t size;
1013
1014     Vector<AVLTreeNodeForArrayCompare> m_nodes;
1015     ExecState* m_exec;
1016     JSValue m_compareFunction;
1017     CallType m_compareCallType;
1018     const CallData* m_compareCallData;
1019     JSValue m_globalThisValue;
1020     OwnPtr<CachedCall> m_cachedCall;
1021
1022     handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
1023     void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; }
1024     handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; }
1025     void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; }
1026
1027     int get_balance_factor(handle h)
1028     {
1029         if (m_nodes[h].gt & 0x80000000)
1030             return -1;
1031         return static_cast<unsigned>(m_nodes[h].lt) >> 31;
1032     }
1033
1034     void set_balance_factor(handle h, int bf)
1035     {
1036         if (bf == 0) {
1037             m_nodes[h].lt &= 0x7FFFFFFF;
1038             m_nodes[h].gt &= 0x7FFFFFFF;
1039         } else {
1040             m_nodes[h].lt |= 0x80000000;
1041             if (bf < 0)
1042                 m_nodes[h].gt |= 0x80000000;
1043             else
1044                 m_nodes[h].gt &= 0x7FFFFFFF;
1045         }
1046     }
1047
1048     int compare_key_key(key va, key vb)
1049     {
1050         ASSERT(!va.isUndefined());
1051         ASSERT(!vb.isUndefined());
1052
1053         if (m_exec->hadException())
1054             return 1;
1055
1056         double compareResult;
1057         if (m_cachedCall) {
1058             m_cachedCall->setThis(m_globalThisValue);
1059             m_cachedCall->setArgument(0, va);
1060             m_cachedCall->setArgument(1, vb);
1061             compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec));
1062         } else {
1063             MarkedArgumentBuffer arguments;
1064             arguments.append(va);
1065             arguments.append(vb);
1066             compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, m_globalThisValue, arguments).toNumber(m_exec);
1067         }
1068         return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
1069     }
1070
1071     int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
1072     int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }
1073
1074     static handle null() { return 0x7FFFFFFF; }
1075 };
1076
1077 void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
1078 {
1079     checkConsistency();
1080
1081     ArrayStorage* storage = m_storage;
1082
1083     // FIXME: This ignores exceptions raised in the compare function or in toNumber.
1084
1085     // The maximum tree depth is compiled in - but the caller is clearly up to no good
1086     // if a larger array is passed.
1087     ASSERT(storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
1088     if (storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
1089         return;
1090
1091     unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
1092     unsigned nodeCount = usedVectorLength + (storage->m_sparseValueMap ? storage->m_sparseValueMap->size() : 0);
1093
1094     if (!nodeCount)
1095         return;
1096
1097     AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
1098     tree.abstractor().m_exec = exec;
1099     tree.abstractor().m_compareFunction = compareFunction;
1100     tree.abstractor().m_compareCallType = callType;
1101     tree.abstractor().m_compareCallData = &callData;
1102     tree.abstractor().m_globalThisValue = exec->globalThisValue();
1103     tree.abstractor().m_nodes.grow(nodeCount);
1104
1105     if (callType == CallTypeJS)
1106         tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, asFunction(compareFunction), 2));
1107
1108     if (!tree.abstractor().m_nodes.begin()) {
1109         throwOutOfMemoryError(exec);
1110         return;
1111     }
1112
1113     // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
1114     // right out from under us while we're building the tree here.
1115
1116     unsigned numDefined = 0;
1117     unsigned numUndefined = 0;
1118
1119     // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
1120     for (; numDefined < usedVectorLength; ++numDefined) {
1121         JSValue v = storage->m_vector[numDefined].get();
1122         if (!v || v.isUndefined())
1123             break;
1124         tree.abstractor().m_nodes[numDefined].value = v;
1125         tree.insert(numDefined);
1126     }
1127     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
1128         JSValue v = storage->m_vector[i].get();
1129         if (v) {
1130             if (v.isUndefined())
1131                 ++numUndefined;
1132             else {
1133                 tree.abstractor().m_nodes[numDefined].value = v;
1134                 tree.insert(numDefined);
1135                 ++numDefined;
1136             }
1137         }
1138     }
1139
1140     unsigned newUsedVectorLength = numDefined + numUndefined;
1141
1142     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
1143         newUsedVectorLength += map->size();
1144         if (newUsedVectorLength > m_vectorLength) {
1145             // Check that it is possible to allocate an array large enough to hold all the entries.
1146             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) {
1147                 throwOutOfMemoryError(exec);
1148                 return;
1149             }
1150         }
1151
1152         storage = m_storage;
1153
1154         SparseArrayValueMap::iterator end = map->end();
1155         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
1156             tree.abstractor().m_nodes[numDefined].value = it->second.get();
1157             tree.insert(numDefined);
1158             ++numDefined;
1159         }
1160
1161         delete map;
1162         storage->m_sparseValueMap = 0;
1163     }
1164
1165     ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
1166
1167     // FIXME: If the compare function changed the length of the array, the following might be
1168     // modifying the vector incorrectly.
1169
1170     // Copy the values back into m_storage.
1171     AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
1172     iter.start_iter_least(tree);
1173     JSGlobalData& globalData = exec->globalData();
1174     for (unsigned i = 0; i < numDefined; ++i) {
1175         storage->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
1176         ++iter;
1177     }
1178
1179     // Put undefined values back in.
1180     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
1181         storage->m_vector[i].setUndefined();
1182
1183     // Ensure that unused values in the vector are zeroed out.
1184     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
1185         storage->m_vector[i].clear();
1186
1187     storage->m_numValuesInVector = newUsedVectorLength;
1188
1189     checkConsistency(SortConsistencyCheck);
1190 }
1191
1192 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
1193 {
1194     ArrayStorage* storage = m_storage;
1195
1196     WriteBarrier<Unknown>* vector = storage->m_vector;
1197     unsigned vectorEnd = min(storage->m_length, m_vectorLength);
1198     unsigned i = 0;
1199     for (; i < vectorEnd; ++i) {
1200         WriteBarrier<Unknown>& v = vector[i];
1201         if (!v)
1202             break;
1203         args.append(v.get());
1204     }
1205
1206     for (; i < storage->m_length; ++i)
1207         args.append(get(exec, i));
1208 }
1209
1210 void JSArray::copyToRegisters(ExecState* exec, Register* buffer, uint32_t maxSize)
1211 {
1212     ASSERT(m_storage->m_length >= maxSize);
1213     UNUSED_PARAM(maxSize);
1214     WriteBarrier<Unknown>* vector = m_storage->m_vector;
1215     unsigned vectorEnd = min(maxSize, m_vectorLength);
1216     unsigned i = 0;
1217     for (; i < vectorEnd; ++i) {
1218         WriteBarrier<Unknown>& v = vector[i];
1219         if (!v)
1220             break;
1221         buffer[i] = v.get();
1222     }
1223
1224     for (; i < maxSize; ++i)
1225         buffer[i] = get(exec, i);
1226 }
1227
1228 unsigned JSArray::compactForSorting()
1229 {
1230     checkConsistency();
1231
1232     ArrayStorage* storage = m_storage;
1233
1234     unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
1235
1236     unsigned numDefined = 0;
1237     unsigned numUndefined = 0;
1238
1239     for (; numDefined < usedVectorLength; ++numDefined) {
1240         JSValue v = storage->m_vector[numDefined].get();
1241         if (!v || v.isUndefined())
1242             break;
1243     }
1244
1245     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
1246         JSValue v = storage->m_vector[i].get();
1247         if (v) {
1248             if (v.isUndefined())
1249                 ++numUndefined;
1250             else
1251                 storage->m_vector[numDefined++].setWithoutWriteBarrier(v);
1252         }
1253     }
1254
1255     unsigned newUsedVectorLength = numDefined + numUndefined;
1256
1257     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
1258         newUsedVectorLength += map->size();
1259         if (newUsedVectorLength > m_vectorLength) {
1260             // Check that it is possible to allocate an array large enough to hold all the entries - if not,
1261             // exception is thrown by caller.
1262             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength))
1263                 return 0;
1264
1265             storage = m_storage;
1266         }
1267
1268         SparseArrayValueMap::iterator end = map->end();
1269         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
1270             storage->m_vector[numDefined++].setWithoutWriteBarrier(it->second.get());
1271
1272         delete map;
1273         storage->m_sparseValueMap = 0;
1274     }
1275
1276     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
1277         storage->m_vector[i].setUndefined();
1278     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
1279         storage->m_vector[i].clear();
1280
1281     storage->m_numValuesInVector = newUsedVectorLength;
1282
1283     checkConsistency(SortConsistencyCheck);
1284
1285     return numDefined;
1286 }
1287
1288 void* JSArray::subclassData() const
1289 {
1290     return m_storage->subclassData;
1291 }
1292
1293 void JSArray::setSubclassData(void* d)
1294 {
1295     m_storage->subclassData = d;
1296 }
1297
1298 #if CHECK_ARRAY_CONSISTENCY
1299
1300 void JSArray::checkConsistency(ConsistencyCheckType type)
1301 {
1302     ArrayStorage* storage = m_storage;
1303
1304     ASSERT(storage);
1305     if (type == SortConsistencyCheck)
1306         ASSERT(!storage->m_sparseValueMap);
1307
1308     unsigned numValuesInVector = 0;
1309     for (unsigned i = 0; i < m_vectorLength; ++i) {
1310         if (JSValue value = storage->m_vector[i]) {
1311             ASSERT(i < storage->m_length);
1312             if (type != DestructorConsistencyCheck)
1313                 value.isUndefined(); // Likely to crash if the object was deallocated.
1314             ++numValuesInVector;
1315         } else {
1316             if (type == SortConsistencyCheck)
1317                 ASSERT(i >= storage->m_numValuesInVector);
1318         }
1319     }
1320     ASSERT(numValuesInVector == storage->m_numValuesInVector);
1321     ASSERT(numValuesInVector <= storage->m_length);
1322
1323     if (storage->m_sparseValueMap) {
1324         SparseArrayValueMap::iterator end = storage->m_sparseValueMap->end();
1325         for (SparseArrayValueMap::iterator it = storage->m_sparseValueMap->begin(); it != end; ++it) {
1326             unsigned index = it->first;
1327             ASSERT(index < storage->m_length);
1328             ASSERT(index >= storage->m_vectorLength);
1329             ASSERT(index <= MAX_ARRAY_INDEX);
1330             ASSERT(it->second);
1331             if (type != DestructorConsistencyCheck)
1332                 it->second.isUndefined(); // Likely to crash if the object was deallocated.
1333         }
1334     }
1335 }
1336
1337 #endif
1338
1339 } // namespace JSC