JavaScriptCore/runtime/JSArray.cpp

   1 /*
   2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
   3  *  Copyright (C) 2003, 2007, 2008 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 "PropertyNameArray.h"
  28 #include <wtf/AVLTree.h>
  29 #include <wtf/Assertions.h>
  30 #include <Operations.h>
  31
  32 #define CHECK_ARRAY_CONSISTENCY 0
  33
  34 using namespace std;
  35 using namespace WTF;
  36
  37 namespace JSC {
  38
  39 ASSERT_CLASS_FITS_IN_CELL(JSArray);
  40
  41 // Overview of JSArray
  42 //
  43 // Properties of JSArray objects may be stored in one of three locations:
  44 //   * The regular JSObject property map.
  45 //   * A storage vector.
  46 //   * A sparse map of array entries.
  47 //
  48 // Properties with non-numeric identifiers, with identifiers that are not representable
  49 // as an unsigned integer, or where the value is greater than  MAX_ARRAY_INDEX
  50 // (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit
  51 // integer) are not considered array indices and will be stored in the JSObject property map.
  52 //
  53 // All properties with a numeric identifer, representable as an unsigned integer i,
  54 // where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the
  55 // storage vector or the sparse map.  An array index i will be handled in the following
  56 // fashion:
  57 //
  58 //   * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector.
  59 //   * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either
  60 //     be stored in the storage vector or in the sparse array, depending on the density of
  61 //     data that would be stored in the vector (a vector being used where at least
  62 //     (1 / minDensityMultiplier) of the entries would be populated).
  63 //   * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored
  64 //     in the sparse array.
  65
  66 // The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
  67 // function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
  68 // size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(JSValuePtr)) +
  69 // (vectorLength * sizeof(JSValuePtr)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
  70 #define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(JSValuePtr))) / sizeof(JSValuePtr))
  71
  72 // These values have to be macros to be used in max() and min() without introducing
  73 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
  74 #define MIN_SPARSE_ARRAY_INDEX 10000U
  75 #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
  76 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
  77 #define MAX_ARRAY_INDEX 0xFFFFFFFEU
  78
  79 // Our policy for when to use a vector and when to use a sparse map.
  80 // For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
  81 // When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
  82 // as long as it is 1/8 full. If more sparse than that, we use a map.
  83 static const unsigned minDensityMultiplier = 8;
  84
  85 const ClassInfo JSArray::info = {"Array", 0, 0, 0};
  86
  87 static inline size_t storageSize(unsigned vectorLength)
  88 {
  89     ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);
  90
  91     // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
  92     // - as asserted above - the following calculation cannot overflow.
  93     size_t size = (sizeof(ArrayStorage) - sizeof(JSValuePtr)) + (vectorLength * sizeof(JSValuePtr));
  94     // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
  95     // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
  96     ASSERT(((size - (sizeof(ArrayStorage) - sizeof(JSValuePtr))) / sizeof(JSValuePtr) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValuePtr))));
  97
  98     return size;
  99 }
 100
 101 static inline unsigned increasedVectorLength(unsigned newLength)
 102 {
 103     ASSERT(newLength <= MAX_STORAGE_VECTOR_LENGTH);
 104
 105     // Mathematically equivalent to:
 106     //   increasedLength = (newLength * 3 + 1) / 2;
 107     // or:
 108     //   increasedLength = (unsigned)ceil(newLength * 1.5));
 109     // This form is not prone to internal overflow.
 110     unsigned increasedLength = newLength + (newLength >> 1) + (newLength & 1);
 111     ASSERT(increasedLength >= newLength);
 112
 113     return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
 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(PassRefPtr<Structure> structure)
 130     : JSObject(structure)
 131 {
 132     unsigned initialCapacity = 0;
 133
 134     m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
 135     m_fastAccessCutoff = 0;
 136     m_storage->m_vectorLength = initialCapacity;
 137     m_storage->m_length = 0;
 138
 139     checkConsistency();
 140 }
 141
 142 JSArray::JSArray(PassRefPtr<Structure> structure, unsigned initialLength)
 143     : JSObject(structure)
 144 {
 145     unsigned initialCapacity = min(initialLength, MIN_SPARSE_ARRAY_INDEX);
 146
 147     m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
 148     m_fastAccessCutoff = 0;
 149     m_storage->m_vectorLength = initialCapacity;
 150     m_storage->m_length = initialLength;
 151
 152     Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValuePtr));
 153
 154     checkConsistency();
 155 }
 156
 157 JSArray::JSArray(ExecState* exec, PassRefPtr<Structure> structure, const ArgList& list)
 158     : JSObject(structure)
 159 {
 160     unsigned length = list.size();
 161
 162     m_fastAccessCutoff = length;
 163
 164     ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(length)));
 165
 166     storage->m_vectorLength = length;
 167     storage->m_numValuesInVector = length;
 168     storage->m_sparseValueMap = 0;
 169     storage->m_length = length;
 170
 171     size_t i = 0;
 172     ArgList::const_iterator end = list.end();
 173     for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
 174         storage->m_vector[i] = (*it).jsValue(exec);
 175
 176     m_storage = storage;
 177
 178     Heap::heap(this)->reportExtraMemoryCost(storageSize(length));
 179
 180     checkConsistency();
 181 }
 182
 183 JSArray::~JSArray()
 184 {
 185     checkConsistency(DestructorConsistencyCheck);
 186
 187     delete m_storage->m_sparseValueMap;
 188     fastFree(m_storage);
 189 }
 190
 191 bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
 192 {
 193     ArrayStorage* storage = m_storage;
 194
 195     if (i >= storage->m_length) {
 196         if (i > MAX_ARRAY_INDEX)
 197             return getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
 198         return false;
 199     }
 200
 201     if (i < storage->m_vectorLength) {
 202         JSValuePtr& valueSlot = storage->m_vector[i];
 203         if (valueSlot) {
 204             slot.setValueSlot(&valueSlot);
 205             return true;
 206         }
 207     } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 208         if (i >= MIN_SPARSE_ARRAY_INDEX) {
 209             SparseArrayValueMap::iterator it = map->find(i);
 210             if (it != map->end()) {
 211                 slot.setValueSlot(&it->second);
 212                 return true;
 213             }
 214         }
 215     }
 216
 217     return false;
 218 }
 219
 220 bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
 221 {
 222     if (propertyName == exec->propertyNames().length) {
 223         slot.setValue(jsNumber(exec, length()));
 224         return true;
 225     }
 226
 227     bool isArrayIndex;
 228     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 229     if (isArrayIndex)
 230         return JSArray::getOwnPropertySlot(exec, i, slot);
 231
 232     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
 233 }
 234
 235 // ECMA 15.4.5.1
 236 void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValuePtr value, PutPropertySlot& slot)
 237 {
 238     bool isArrayIndex;
 239     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 240     if (isArrayIndex) {
 241         put(exec, i, value);
 242         return;
 243     }
 244
 245     if (propertyName == exec->propertyNames().length) {
 246         unsigned newLength = value.toUInt32(exec);
 247         if (value.toNumber(exec) != static_cast<double>(newLength)) {
 248             throwError(exec, RangeError, "Invalid array length.");
 249             return;
 250         }
 251         setLength(newLength);
 252         return;
 253     }
 254
 255     JSObject::put(exec, propertyName, value, slot);
 256 }
 257
 258 void JSArray::put(ExecState* exec, unsigned i, JSValuePtr value)
 259 {
 260     checkConsistency();
 261
 262     unsigned length = m_storage->m_length;
 263     if (i >= length && i <= MAX_ARRAY_INDEX) {
 264         length = i + 1;
 265         m_storage->m_length = length;
 266     }
 267
 268     if (i < m_storage->m_vectorLength) {
 269         JSValuePtr& valueSlot = m_storage->m_vector[i];
 270         if (valueSlot) {
 271             valueSlot = value;
 272             checkConsistency();
 273             return;
 274         }
 275         valueSlot = value;
 276         if (++m_storage->m_numValuesInVector == m_storage->m_length)
 277             m_fastAccessCutoff = m_storage->m_length;
 278         checkConsistency();
 279         return;
 280     }
 281
 282     putSlowCase(exec, i, value);
 283 }
 284
 285 NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValuePtr value)
 286 {
 287     ArrayStorage* storage = m_storage;
 288     SparseArrayValueMap* map = storage->m_sparseValueMap;
 289
 290     if (i >= MIN_SPARSE_ARRAY_INDEX) {
 291         if (i > MAX_ARRAY_INDEX) {
 292             PutPropertySlot slot;
 293             put(exec, Identifier::from(exec, i), value, slot);
 294             return;
 295         }
 296
 297         // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
 298         // (which will only be compacted as we reach indices that are less than cutoff) - but this makes the check much faster.
 299         if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
 300             if (!map) {
 301                 map = new SparseArrayValueMap;
 302                 storage->m_sparseValueMap = map;
 303             }
 304             map->set(i, value);
 305             return;
 306         }
 307     }
 308
 309     // We have decided that we'll put the new item into the vector.
 310     // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
 311     if (!map || map->isEmpty()) {
 312         if (increaseVectorLength(i + 1)) {
 313             storage = m_storage;
 314             storage->m_vector[i] = value;
 315             if (++storage->m_numValuesInVector == storage->m_length)
 316                 m_fastAccessCutoff = storage->m_length;
 317             checkConsistency();
 318         } else
 319             throwOutOfMemoryError(exec);
 320         return;
 321     }
 322
 323     // Decide how many values it would be best to move from the map.
 324     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
 325     unsigned newVectorLength = increasedVectorLength(i + 1);
 326     for (unsigned j = max(storage->m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
 327         newNumValuesInVector += map->contains(j);
 328     if (i >= MIN_SPARSE_ARRAY_INDEX)
 329         newNumValuesInVector -= map->contains(i);
 330     if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
 331         unsigned proposedNewNumValuesInVector = newNumValuesInVector;
 332         // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
 333         while (newVectorLength < MAX_STORAGE_VECTOR_LENGTH) {
 334             unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
 335             for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
 336                 proposedNewNumValuesInVector += map->contains(j);
 337             if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
 338                 break;
 339             newVectorLength = proposedNewVectorLength;
 340             newNumValuesInVector = proposedNewNumValuesInVector;
 341         }
 342     }
 343
 344     storage = static_cast<ArrayStorage*>(tryFastRealloc(storage, storageSize(newVectorLength)));
 345     if (!storage) {
 346         throwOutOfMemoryError(exec);
 347         return;
 348     }
 349
 350     unsigned vectorLength = storage->m_vectorLength;
 351
 352     Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
 353
 354     if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
 355         for (unsigned j = vectorLength; j < newVectorLength; ++j)
 356             storage->m_vector[j] = noValue();
 357         if (i > MIN_SPARSE_ARRAY_INDEX)
 358             map->remove(i);
 359     } else {
 360         for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
 361             storage->m_vector[j] = noValue();
 362         for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
 363             storage->m_vector[j] = map->take(j);
 364     }
 365
 366     storage->m_vector[i] = value;
 367
 368     storage->m_vectorLength = newVectorLength;
 369     storage->m_numValuesInVector = newNumValuesInVector;
 370
 371     m_storage = storage;
 372
 373     checkConsistency();
 374 }
 375
 376 bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)
 377 {
 378     bool isArrayIndex;
 379     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 380     if (isArrayIndex)
 381         return deleteProperty(exec, i);
 382
 383     if (propertyName == exec->propertyNames().length)
 384         return false;
 385
 386     return JSObject::deleteProperty(exec, propertyName);
 387 }
 388
 389 bool JSArray::deleteProperty(ExecState* exec, unsigned i)
 390 {
 391     checkConsistency();
 392
 393     ArrayStorage* storage = m_storage;
 394
 395     if (i < storage->m_vectorLength) {
 396         JSValuePtr& valueSlot = storage->m_vector[i];
 397         if (!valueSlot) {
 398             checkConsistency();
 399             return false;
 400         }
 401         valueSlot = noValue();
 402         --storage->m_numValuesInVector;
 403         if (m_fastAccessCutoff > i)
 404             m_fastAccessCutoff = i;
 405         checkConsistency();
 406         return true;
 407     }
 408
 409     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 410         if (i >= MIN_SPARSE_ARRAY_INDEX) {
 411             SparseArrayValueMap::iterator it = map->find(i);
 412             if (it != map->end()) {
 413                 map->remove(it);
 414                 checkConsistency();
 415                 return true;
 416             }
 417         }
 418     }
 419
 420     checkConsistency();
 421
 422     if (i > MAX_ARRAY_INDEX)
 423         return deleteProperty(exec, Identifier::from(exec, i));
 424
 425     return false;
 426 }
 427
 428 void JSArray::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
 429 {
 430     // FIXME: Filling PropertyNameArray with an identifier for every integer
 431     // is incredibly inefficient for large arrays. We need a different approach,
 432     // which almost certainly means a different structure for PropertyNameArray.
 433
 434     ArrayStorage* storage = m_storage;
 435
 436     unsigned usedVectorLength = min(storage->m_length, storage->m_vectorLength);
 437     for (unsigned i = 0; i < usedVectorLength; ++i) {
 438         if (storage->m_vector[i])
 439             propertyNames.add(Identifier::from(exec, i));
 440     }
 441
 442     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 443         SparseArrayValueMap::iterator end = map->end();
 444         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
 445             propertyNames.add(Identifier::from(exec, it->first));
 446     }
 447
 448     JSObject::getPropertyNames(exec, propertyNames);
 449 }
 450
 451 bool JSArray::increaseVectorLength(unsigned newLength)
 452 {
 453     // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
 454     // to the vector. Callers have to account for that, because they can do it more efficiently.
 455
 456     ArrayStorage* storage = m_storage;
 457
 458     unsigned vectorLength = storage->m_vectorLength;
 459     ASSERT(newLength > vectorLength);
 460     ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
 461     unsigned newVectorLength = increasedVectorLength(newLength);
 462
 463     storage = static_cast<ArrayStorage*>(tryFastRealloc(storage, storageSize(newVectorLength)));
 464     if (!storage)
 465         return false;
 466
 467     Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
 468     storage->m_vectorLength = newVectorLength;
 469
 470     for (unsigned i = vectorLength; i < newVectorLength; ++i)
 471         storage->m_vector[i] = noValue();
 472
 473     m_storage = storage;
 474     return true;
 475 }
 476
 477 void JSArray::setLength(unsigned newLength)
 478 {
 479     checkConsistency();
 480
 481     ArrayStorage* storage = m_storage;
 482
 483     unsigned length = m_storage->m_length;
 484
 485     if (newLength < length) {
 486         if (m_fastAccessCutoff > newLength)
 487             m_fastAccessCutoff = newLength;
 488
 489         unsigned usedVectorLength = min(length, storage->m_vectorLength);
 490         for (unsigned i = newLength; i < usedVectorLength; ++i) {
 491             JSValuePtr& valueSlot = storage->m_vector[i];
 492             bool hadValue = valueSlot;
 493             valueSlot = noValue();
 494             storage->m_numValuesInVector -= hadValue;
 495         }
 496
 497         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 498             SparseArrayValueMap copy = *map;
 499             SparseArrayValueMap::iterator end = copy.end();
 500             for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
 501                 if (it->first >= newLength)
 502                     map->remove(it->first);
 503             }
 504             if (map->isEmpty()) {
 505                 delete map;
 506                 storage->m_sparseValueMap = 0;
 507             }
 508         }
 509     }
 510
 511     m_storage->m_length = newLength;
 512
 513     checkConsistency();
 514 }
 515
 516 JSValuePtr JSArray::pop()
 517 {
 518     checkConsistency();
 519
 520     unsigned length = m_storage->m_length;
 521     if (!length)
 522         return jsUndefined();
 523
 524     --length;
 525
 526     JSValuePtr result;
 527
 528     if (m_fastAccessCutoff > length) {
 529         JSValuePtr& valueSlot = m_storage->m_vector[length];
 530         result = valueSlot;
 531         ASSERT(result);
 532         valueSlot = noValue();
 533         --m_storage->m_numValuesInVector;
 534         m_fastAccessCutoff = length;
 535     } else if (length < m_storage->m_vectorLength) {
 536         JSValuePtr& valueSlot = m_storage->m_vector[length];
 537         result = valueSlot;
 538         valueSlot = noValue();
 539         if (result)
 540             --m_storage->m_numValuesInVector;
 541         else
 542             result = jsUndefined();
 543     } else {
 544         result = jsUndefined();
 545         if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
 546             SparseArrayValueMap::iterator it = map->find(length);
 547             if (it != map->end()) {
 548                 result = it->second;
 549                 map->remove(it);
 550                 if (map->isEmpty()) {
 551                     delete map;
 552                     m_storage->m_sparseValueMap = 0;
 553                 }
 554             }
 555         }
 556     }
 557
 558     m_storage->m_length = length;
 559
 560     checkConsistency();
 561
 562     return result;
 563 }
 564
 565 void JSArray::push(ExecState* exec, JSValuePtr value)
 566 {
 567     checkConsistency();
 568
 569     if (m_storage->m_length < m_storage->m_vectorLength) {
 570         ASSERT(!m_storage->m_vector[m_storage->m_length]);
 571         m_storage->m_vector[m_storage->m_length] = value;
 572         if (++m_storage->m_numValuesInVector == ++m_storage->m_length)
 573             m_fastAccessCutoff = m_storage->m_length;
 574         checkConsistency();
 575         return;
 576     }
 577
 578     if (m_storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
 579         SparseArrayValueMap* map = m_storage->m_sparseValueMap;
 580         if (!map || map->isEmpty()) {
 581             if (increaseVectorLength(m_storage->m_length + 1)) {
 582                 m_storage->m_vector[m_storage->m_length] = value;
 583                 if (++m_storage->m_numValuesInVector == ++m_storage->m_length)
 584                     m_fastAccessCutoff = m_storage->m_length;
 585                 checkConsistency();
 586                 return;
 587             }
 588             checkConsistency();
 589             throwOutOfMemoryError(exec);
 590             return;
 591         }
 592     }
 593
 594     putSlowCase(exec, m_storage->m_length++, value);
 595 }
 596
 597 void JSArray::mark()
 598 {
 599     JSObject::mark();
 600
 601     ArrayStorage* storage = m_storage;
 602
 603     unsigned usedVectorLength = min(storage->m_length, storage->m_vectorLength);
 604     for (unsigned i = 0; i < usedVectorLength; ++i) {
 605         JSValuePtr value = storage->m_vector[i];
 606         if (value && !value.marked())
 607             value.mark();
 608     }
 609
 610     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 611         SparseArrayValueMap::iterator end = map->end();
 612         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
 613             JSValuePtr value = it->second;
 614             if (!value.marked())
 615                 value.mark();
 616         }
 617     }
 618 }
 619
 620 static int compareNumbersForQSort(const void* a, const void* b)
 621 {
 622     double da = static_cast<const JSValuePtr*>(a)->uncheckedGetNumber();
 623     double db = static_cast<const JSValuePtr*>(b)->uncheckedGetNumber();
 624     return (da > db) - (da < db);
 625 }
 626
 627 typedef std::pair<JSValuePtr, UString> ValueStringPair;
 628
 629 static int compareByStringPairForQSort(const void* a, const void* b)
 630 {
 631     const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
 632     const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
 633     return compare(va->second, vb->second);
 634 }
 635
 636 void JSArray::sortNumeric(ExecState* exec, JSValuePtr compareFunction, CallType callType, const CallData& callData)
 637 {
 638     unsigned lengthNotIncludingUndefined = compactForSorting();
 639     if (m_storage->m_sparseValueMap) {
 640         throwOutOfMemoryError(exec);
 641         return;
 642     }
 643
 644     if (!lengthNotIncludingUndefined)
 645         return;
 646
 647     bool allValuesAreNumbers = true;
 648     size_t size = m_storage->m_numValuesInVector;
 649     for (size_t i = 0; i < size; ++i) {
 650         if (!m_storage->m_vector[i].isNumber()) {
 651             allValuesAreNumbers = false;
 652             break;
 653         }
 654     }
 655
 656     if (!allValuesAreNumbers)
 657         return sort(exec, compareFunction, callType, callData);
 658
 659     // For numeric comparison, which is fast, qsort is faster than mergesort. We
 660     // also don't require mergesort's stability, since there's no user visible
 661     // side-effect from swapping the order of equal primitive values.
 662     qsort(m_storage->m_vector, size, sizeof(JSValuePtr), compareNumbersForQSort);
 663
 664     checkConsistency(SortConsistencyCheck);
 665 }
 666
 667 void JSArray::sort(ExecState* exec)
 668 {
 669     unsigned lengthNotIncludingUndefined = compactForSorting();
 670     if (m_storage->m_sparseValueMap) {
 671         throwOutOfMemoryError(exec);
 672         return;
 673     }
 674
 675     if (!lengthNotIncludingUndefined)
 676         return;
 677
 678     // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
 679     // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
 680     // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
 681     // random or otherwise changing results, effectively making compare function inconsistent.
 682
 683     Vector<ValueStringPair> values(lengthNotIncludingUndefined);
 684     if (!values.begin()) {
 685         throwOutOfMemoryError(exec);
 686         return;
 687     }
 688
 689     for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
 690         JSValuePtr value = m_storage->m_vector[i];
 691         ASSERT(!value.isUndefined());
 692         values[i].first = value;
 693     }
 694
 695     // FIXME: While calling these toString functions, the array could be mutated.
 696     // In that case, objects pointed to by values in this vector might get garbage-collected!
 697
 698     // FIXME: The following loop continues to call toString on subsequent values even after
 699     // a toString call raises an exception.
 700
 701     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
 702         values[i].second = values[i].first.toString(exec);
 703
 704     if (exec->hadException())
 705         return;
 706
 707     // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
 708     // than O(N log N).
 709
 710 #if HAVE(MERGESORT)
 711     mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 712 #else
 713     // FIXME: The qsort library function is likely to not be a stable sort.
 714     // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
 715     qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 716 #endif
 717
 718     // FIXME: If the toString function changed the length of the array, this might be
 719     // modifying the vector incorrectly.
 720
 721     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
 722         m_storage->m_vector[i] = values[i].first;
 723
 724     checkConsistency(SortConsistencyCheck);
 725 }
 726
 727 struct AVLTreeNodeForArrayCompare {
 728     JSValuePtr value;
 729
 730     // Child pointers.  The high bit of gt is robbed and used as the
 731     // balance factor sign.  The high bit of lt is robbed and used as
 732     // the magnitude of the balance factor.
 733     int32_t gt;
 734     int32_t lt;
 735 };
 736
 737 struct AVLTreeAbstractorForArrayCompare {
 738     typedef int32_t handle; // Handle is an index into m_nodes vector.
 739     typedef JSValuePtr key;
 740     typedef int32_t size;
 741
 742     Vector<AVLTreeNodeForArrayCompare> m_nodes;
 743     ExecState* m_exec;
 744     JSValuePtr m_compareFunction;
 745     CallType m_compareCallType;
 746     const CallData* m_compareCallData;
 747     JSValuePtr m_globalThisValue;
 748
 749     handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
 750     void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; }
 751     handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; }
 752     void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; }
 753
 754     int get_balance_factor(handle h)
 755     {
 756         if (m_nodes[h].gt & 0x80000000)
 757             return -1;
 758         return static_cast<unsigned>(m_nodes[h].lt) >> 31;
 759     }
 760
 761     void set_balance_factor(handle h, int bf)
 762     {
 763         if (bf == 0) {
 764             m_nodes[h].lt &= 0x7FFFFFFF;
 765             m_nodes[h].gt &= 0x7FFFFFFF;
 766         } else {
 767             m_nodes[h].lt |= 0x80000000;
 768             if (bf < 0)
 769                 m_nodes[h].gt |= 0x80000000;
 770             else
 771                 m_nodes[h].gt &= 0x7FFFFFFF;
 772         }
 773     }
 774
 775     int compare_key_key(key va, key vb)
 776     {
 777         ASSERT(!va.isUndefined());
 778         ASSERT(!vb.isUndefined());
 779
 780         if (m_exec->hadException())
 781             return 1;
 782
 783         ArgList arguments;
 784         arguments.append(va);
 785         arguments.append(vb);
 786         double compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, m_globalThisValue, arguments).toNumber(m_exec);
 787         return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
 788     }
 789
 790     int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
 791     int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }
 792
 793     static handle null() { return 0x7FFFFFFF; }
 794 };
 795
 796 void JSArray::sort(ExecState* exec, JSValuePtr compareFunction, CallType callType, const CallData& callData)
 797 {
 798     checkConsistency();
 799
 800     // FIXME: This ignores exceptions raised in the compare function or in toNumber.
 801
 802     // The maximum tree depth is compiled in - but the caller is clearly up to no good
 803     // if a larger array is passed.
 804     ASSERT(m_storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
 805     if (m_storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
 806         return;
 807
 808     if (!m_storage->m_length)
 809         return;
 810
 811     unsigned usedVectorLength = min(m_storage->m_length, m_storage->m_vectorLength);
 812
 813     AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
 814     tree.abstractor().m_exec = exec;
 815     tree.abstractor().m_compareFunction = compareFunction;
 816     tree.abstractor().m_compareCallType = callType;
 817     tree.abstractor().m_compareCallData = &callData;
 818     tree.abstractor().m_globalThisValue = exec->globalThisValue();
 819     tree.abstractor().m_nodes.resize(usedVectorLength + (m_storage->m_sparseValueMap ? m_storage->m_sparseValueMap->size() : 0));
 820
 821     if (!tree.abstractor().m_nodes.begin()) {
 822         throwOutOfMemoryError(exec);
 823         return;
 824     }
 825
 826     // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
 827     // right out from under us while we're building the tree here.
 828
 829     unsigned numDefined = 0;
 830     unsigned numUndefined = 0;
 831
 832     // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
 833     for (; numDefined < usedVectorLength; ++numDefined) {
 834         JSValuePtr v = m_storage->m_vector[numDefined];
 835         if (!v || v.isUndefined())
 836             break;
 837         tree.abstractor().m_nodes[numDefined].value = v;
 838         tree.insert(numDefined);
 839     }
 840     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
 841         JSValuePtr v = m_storage->m_vector[i];
 842         if (v) {
 843             if (v.isUndefined())
 844                 ++numUndefined;
 845             else {
 846                 tree.abstractor().m_nodes[numDefined].value = v;
 847                 tree.insert(numDefined);
 848                 ++numDefined;
 849             }
 850         }
 851     }
 852
 853     unsigned newUsedVectorLength = numDefined + numUndefined;
 854
 855     if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
 856         newUsedVectorLength += map->size();
 857         if (newUsedVectorLength > m_storage->m_vectorLength) {
 858             // Check that it is possible to allocate an array large enough to hold all the entries.
 859             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) {
 860                 throwOutOfMemoryError(exec);
 861                 return;
 862             }
 863         }
 864
 865         SparseArrayValueMap::iterator end = map->end();
 866         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
 867             tree.abstractor().m_nodes[numDefined].value = it->second;
 868             tree.insert(numDefined);
 869             ++numDefined;
 870         }
 871
 872         delete map;
 873         m_storage->m_sparseValueMap = 0;
 874     }
 875
 876     ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
 877
 878     // FIXME: If the compare function changed the length of the array, the following might be
 879     // modifying the vector incorrectly.
 880
 881     // Copy the values back into m_storage.
 882     AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
 883     iter.start_iter_least(tree);
 884     for (unsigned i = 0; i < numDefined; ++i) {
 885         m_storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value;
 886         ++iter;
 887     }
 888
 889     // Put undefined values back in.
 890     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
 891         m_storage->m_vector[i] = jsUndefined();
 892
 893     // Ensure that unused values in the vector are zeroed out.
 894     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
 895         m_storage->m_vector[i] = noValue();
 896
 897     m_fastAccessCutoff = newUsedVectorLength;
 898     m_storage->m_numValuesInVector = newUsedVectorLength;
 899
 900     checkConsistency(SortConsistencyCheck);
 901 }
 902
 903 void JSArray::fillArgList(ExecState* exec, ArgList& args)
 904 {
 905     unsigned fastAccessLength = min(m_storage->m_length, m_fastAccessCutoff);
 906     unsigned i = 0;
 907     for (; i < fastAccessLength; ++i)
 908         args.append(getIndex(i));
 909     for (; i < m_storage->m_length; ++i)
 910         args.append(get(exec, i));
 911 }
 912
 913 unsigned JSArray::compactForSorting()
 914 {
 915     checkConsistency();
 916
 917     ArrayStorage* storage = m_storage;
 918
 919     unsigned usedVectorLength = min(m_storage->m_length, storage->m_vectorLength);
 920
 921     unsigned numDefined = 0;
 922     unsigned numUndefined = 0;
 923
 924     for (; numDefined < usedVectorLength; ++numDefined) {
 925         JSValuePtr v = storage->m_vector[numDefined];
 926         if (!v || v.isUndefined())
 927             break;
 928     }
 929     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
 930         JSValuePtr v = storage->m_vector[i];
 931         if (v) {
 932             if (v.isUndefined())
 933                 ++numUndefined;
 934             else
 935                 storage->m_vector[numDefined++] = v;
 936         }
 937     }
 938
 939     unsigned newUsedVectorLength = numDefined + numUndefined;
 940
 941     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 942         newUsedVectorLength += map->size();
 943         if (newUsedVectorLength > storage->m_vectorLength) {
 944             // Check that it is possible to allocate an array large enough to hold all the entries - if not,
 945             // exception is thrown by caller.
 946             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength))
 947                 return 0;
 948             storage = m_storage;
 949         }
 950
 951         SparseArrayValueMap::iterator end = map->end();
 952         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
 953             storage->m_vector[numDefined++] = it->second;
 954
 955         delete map;
 956         storage->m_sparseValueMap = 0;
 957     }
 958
 959     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
 960         storage->m_vector[i] = jsUndefined();
 961     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
 962         storage->m_vector[i] = noValue();
 963
 964     m_fastAccessCutoff = newUsedVectorLength;
 965     storage->m_numValuesInVector = newUsedVectorLength;
 966
 967     checkConsistency(SortConsistencyCheck);
 968
 969     return numDefined;
 970 }
 971
 972 void* JSArray::lazyCreationData()
 973 {
 974     return m_storage->lazyCreationData;
 975 }
 976
 977 void JSArray::setLazyCreationData(void* d)
 978 {
 979     m_storage->lazyCreationData = d;
 980 }
 981
 982 #if CHECK_ARRAY_CONSISTENCY
 983
 984 void JSArray::checkConsistency(ConsistencyCheckType type)
 985 {
 986     ASSERT(m_storage);
 987     if (type == SortConsistencyCheck)
 988         ASSERT(!m_storage->m_sparseValueMap);
 989
 990     ASSERT(m_fastAccessCutoff <= m_storage->m_length);
 991     ASSERT(m_fastAccessCutoff <= m_storage->m_numValuesInVector);
 992
 993     unsigned numValuesInVector = 0;
 994     for (unsigned i = 0; i < m_storage->m_vectorLength; ++i) {
 995         if (JSValuePtr value = m_storage->m_vector[i]) {
 996             ASSERT(i < m_storage->m_length);
 997             if (type != DestructorConsistencyCheck)
 998                 value->type(); // Likely to crash if the object was deallocated.
 999             ++numValuesInVector;
1000         } else {
1001             ASSERT(i >= m_fastAccessCutoff);
1002             if (type == SortConsistencyCheck)
1003                 ASSERT(i >= m_storage->m_numValuesInVector);
1004         }
1005     }
1006     ASSERT(numValuesInVector == m_storage->m_numValuesInVector);
1007
1008     if (m_storage->m_sparseValueMap) {
1009         SparseArrayValueMap::iterator end = m_storage->m_sparseValueMap->end();
1010         for (SparseArrayValueMap::iterator it = m_storage->m_sparseValueMap->begin(); it != end; ++it) {
1011             unsigned index = it->first;
1012             ASSERT(index < m_storage->m_length);
1013             ASSERT(index >= m_storage->m_vectorLength);
1014             ASSERT(index <= MAX_ARRAY_INDEX);
1015             ASSERT(it->second);
1016             if (type != DestructorConsistencyCheck)
1017                 it->second->type(); // Likely to crash if the object was deallocated.
1018         }
1019     }
1020 }
1021
1022 #endif
1023
1024 JSArray* constructEmptyArray(ExecState* exec)
1025 {
1026     return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure());
1027 }
1028
1029 JSArray* constructEmptyArray(ExecState* exec, unsigned initialLength)
1030 {
1031     return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure(), initialLength);
1032 }
1033
1034 JSArray* constructArray(ExecState* exec, JSValuePtr singleItemValue)
1035 {
1036     ArgList values;
1037     values.append(singleItemValue);
1038     return new (exec) JSArray(exec, exec->lexicalGlobalObject()->arrayStructure(), values);
1039 }
1040
1041 JSArray* constructArray(ExecState* exec, const ArgList& values)
1042 {
1043     return new (exec) JSArray(exec, exec->lexicalGlobalObject()->arrayStructure(), values);
1044 }
1045
1046 } // namespace JSC