JavaScriptCore/kjs/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
  31 #define CHECK_ARRAY_CONSISTENCY 0
  32
  33 using namespace std;
  34
  35 namespace KJS {
  36
  37 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
  38 static const unsigned maxArrayIndex = 0xFFFFFFFEU;
  39
  40 // Our policy for when to use a vector and when to use a sparse map.
  41 // For all array indices under sparseArrayCutoff, we always use a vector.
  42 // When indices greater than sparseArrayCutoff are involved, we use a vector
  43 // as long as it is 1/8 full. If more sparse than that, we use a map.
  44 // This value has to be a macro to be used in max() and min() without introducing
  45 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
  46 #define sparseArrayCutoff 10000U
  47 static const unsigned minDensityMultiplier = 8;
  48
  49 const ClassInfo JSArray::info = {"Array", 0, 0, 0};
  50
  51 static inline size_t storageSize(unsigned vectorLength)
  52 {
  53     return sizeof(ArrayStorage) - sizeof(JSValue*) + vectorLength * sizeof(JSValue*);
  54 }
  55
  56 static inline unsigned increasedVectorLength(unsigned newLength)
  57 {
  58     return (newLength * 3 + 1) / 2;
  59 }
  60
  61 static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
  62 {
  63     return length / minDensityMultiplier <= numValues;
  64 }
  65
  66 #if !CHECK_ARRAY_CONSISTENCY
  67
  68 inline void JSArray::checkConsistency(ConsistencyCheckType)
  69 {
  70 }
  71
  72 #endif
  73
  74 JSArray::JSArray(JSValue* prototype, unsigned initialLength)
  75     : JSObject(prototype)
  76 {
  77     unsigned initialCapacity = min(initialLength, sparseArrayCutoff);
  78
  79     m_length = initialLength;
  80     m_fastAccessCutoff = 0;
  81     m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
  82     m_storage->m_vectorLength = initialCapacity;
  83
  84     Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValue*));
  85
  86     checkConsistency();
  87 }
  88
  89 JSArray::JSArray(JSObject* prototype, const ArgList& list)
  90     : JSObject(prototype)
  91 {
  92     unsigned length = list.size();
  93
  94     m_length = length;
  95     m_fastAccessCutoff = length;
  96
  97     ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(length)));
  98
  99     storage->m_vectorLength = length;
 100     storage->m_numValuesInVector = length;
 101     storage->m_sparseValueMap = 0;
 102
 103     size_t i = 0;
 104     ArgList::const_iterator end = list.end();
 105     for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
 106         storage->m_vector[i] = *it;
 107
 108     m_storage = storage;
 109
 110     // When the array is created non-empty, its cells are filled, so it's really no worse than
 111     // a property map. Therefore don't report extra memory cost.
 112
 113     checkConsistency();
 114 }
 115
 116 JSArray::~JSArray()
 117 {
 118     checkConsistency(DestructorConsistencyCheck);
 119
 120     delete m_storage->m_sparseValueMap;
 121     fastFree(m_storage);
 122 }
 123
 124 JSValue* JSArray::lengthGetter(ExecState* exec, const Identifier&, const PropertySlot& slot)
 125 {
 126     return jsNumber(exec, static_cast<JSArray*>(slot.slotBase())->m_length);
 127 }
 128
 129 NEVER_INLINE bool JSArray::getOwnPropertySlotSlowCase(ExecState* exec, unsigned i, PropertySlot& slot)
 130 {
 131     ArrayStorage* storage = m_storage;
 132
 133     if (i >= m_length) {
 134         if (i > maxArrayIndex)
 135             return getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
 136         return false;
 137     }
 138
 139     if (i < storage->m_vectorLength) {
 140         JSValue*& valueSlot = storage->m_vector[i];
 141         if (valueSlot) {
 142             slot.setValueSlot(&valueSlot);
 143             return true;
 144         }
 145     } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 146         if (i >= sparseArrayCutoff) {
 147             SparseArrayValueMap::iterator it = map->find(i);
 148             if (it != map->end()) {
 149                 slot.setValueSlot(&it->second);
 150                 return true;
 151             }
 152         }
 153     }
 154
 155     return false;
 156 }
 157
 158 bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
 159 {
 160     if (propertyName == exec->propertyNames().length) {
 161         slot.setCustom(this, lengthGetter);
 162         return true;
 163     }
 164
 165     bool isArrayIndex;
 166     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 167     if (isArrayIndex)
 168         return JSArray::getOwnPropertySlot(exec, i, slot);
 169
 170     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
 171 }
 172
 173 bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
 174 {
 175     if (i < m_fastAccessCutoff) {
 176         slot.setValueSlot(&m_storage->m_vector[i]);
 177         return true;
 178     }
 179
 180     return getOwnPropertySlotSlowCase(exec, i, slot);
 181 }
 182
 183 // ECMA 15.4.5.1
 184 void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue* value)
 185 {
 186     bool isArrayIndex;
 187     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 188     if (isArrayIndex) {
 189         put(exec, i, value);
 190         return;
 191     }
 192
 193     if (propertyName == exec->propertyNames().length) {
 194         unsigned newLength = value->toUInt32(exec);
 195         if (value->toNumber(exec) != static_cast<double>(newLength)) {
 196             throwError(exec, RangeError, "Invalid array length.");
 197             return;
 198         }
 199         setLength(newLength);
 200         return;
 201     }
 202
 203     JSObject::put(exec, propertyName, value);
 204 }
 205
 206 void JSArray::put(ExecState* exec, unsigned i, JSValue* value)
 207 {
 208     checkConsistency();
 209
 210     if (i < m_fastAccessCutoff) {
 211         m_storage->m_vector[i] = value;
 212         checkConsistency();
 213         return;
 214     }
 215
 216     unsigned length = m_length;
 217     if (i >= length && i <= maxArrayIndex) {
 218         length = i + 1;
 219         m_length = length;
 220     }
 221
 222     if (i < m_storage->m_vectorLength) {
 223         JSValue*& valueSlot = m_storage->m_vector[i];
 224         if (valueSlot) {
 225             valueSlot = value;
 226             checkConsistency();
 227             return;
 228         }
 229         valueSlot = value;
 230         if (++m_storage->m_numValuesInVector == m_length)
 231             m_fastAccessCutoff = m_length;
 232         checkConsistency();
 233         return;
 234     }
 235
 236     putSlowCase(exec, i, value);
 237 }
 238
 239 NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue* value)
 240 {
 241     ArrayStorage* storage = m_storage;
 242     SparseArrayValueMap* map = storage->m_sparseValueMap;
 243
 244     if (i >= sparseArrayCutoff) {
 245         if (i > maxArrayIndex) {
 246             put(exec, Identifier::from(exec, i), value);
 247             return;
 248         }
 249
 250         // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
 251         // (which will only be compacted as we reach indices that are less than cutoff) - but this makes the check much faster.
 252         if (!isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
 253             if (!map) {
 254                 map = new SparseArrayValueMap;
 255                 storage->m_sparseValueMap = map;
 256             }
 257             map->set(i, value);
 258             return;
 259         }
 260     }
 261
 262     // We have decided that we'll put the new item into the vector.
 263     // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
 264     if (!map || map->isEmpty()) {
 265         increaseVectorLength(i + 1);
 266         storage = m_storage;
 267         ++storage->m_numValuesInVector;
 268         storage->m_vector[i] = value;
 269         checkConsistency();
 270         return;
 271     }
 272
 273     // Decide how many values it would be best to move from the map.
 274     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
 275     unsigned newVectorLength = increasedVectorLength(i + 1);
 276     for (unsigned j = max(storage->m_vectorLength, sparseArrayCutoff); j < newVectorLength; ++j)
 277         newNumValuesInVector += map->contains(j);
 278     if (i >= sparseArrayCutoff)
 279         newNumValuesInVector -= map->contains(i);
 280     if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
 281         unsigned proposedNewNumValuesInVector = newNumValuesInVector;
 282         while (true) {
 283             unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
 284             for (unsigned j = max(newVectorLength, sparseArrayCutoff); j < proposedNewVectorLength; ++j)
 285                 proposedNewNumValuesInVector += map->contains(j);
 286             if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
 287                 break;
 288             newVectorLength = proposedNewVectorLength;
 289             newNumValuesInVector = proposedNewNumValuesInVector;
 290         }
 291     }
 292
 293     storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength)));
 294
 295     unsigned vectorLength = storage->m_vectorLength;
 296     if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
 297         for (unsigned j = vectorLength; j < newVectorLength; ++j)
 298             storage->m_vector[j] = 0;
 299         if (i > sparseArrayCutoff)
 300             map->remove(i);
 301     } else {
 302         for (unsigned j = vectorLength; j < max(vectorLength, sparseArrayCutoff); ++j)
 303             storage->m_vector[j] = 0;
 304         for (unsigned j = max(vectorLength, sparseArrayCutoff); j < newVectorLength; ++j)
 305             storage->m_vector[j] = map->take(j);
 306     }
 307
 308     storage->m_vector[i] = value;
 309
 310     storage->m_vectorLength = newVectorLength;
 311     storage->m_numValuesInVector = newNumValuesInVector;
 312
 313     m_storage = storage;
 314
 315     checkConsistency();
 316 }
 317
 318 bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)
 319 {
 320     bool isArrayIndex;
 321     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 322     if (isArrayIndex)
 323         return deleteProperty(exec, i);
 324
 325     if (propertyName == exec->propertyNames().length)
 326         return false;
 327
 328     return JSObject::deleteProperty(exec, propertyName);
 329 }
 330
 331 bool JSArray::deleteProperty(ExecState* exec, unsigned i)
 332 {
 333     checkConsistency();
 334
 335     ArrayStorage* storage = m_storage;
 336
 337     if (i < storage->m_vectorLength) {
 338         JSValue*& valueSlot = storage->m_vector[i];
 339         if (!valueSlot) {
 340             checkConsistency();
 341             return false;
 342         }
 343         valueSlot = 0;
 344         --storage->m_numValuesInVector;
 345         if (m_fastAccessCutoff > i)
 346             m_fastAccessCutoff = i;
 347         checkConsistency();
 348         return true;
 349     }
 350
 351     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 352         if (i >= sparseArrayCutoff) {
 353             SparseArrayValueMap::iterator it = map->find(i);
 354             if (it != map->end()) {
 355                 map->remove(it);
 356                 checkConsistency();
 357                 return true;
 358             }
 359         }
 360     }
 361
 362     checkConsistency();
 363
 364     if (i > maxArrayIndex)
 365         return deleteProperty(exec, Identifier::from(exec, i));
 366
 367     return false;
 368 }
 369
 370 void JSArray::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
 371 {
 372     // FIXME: Filling PropertyNameArray with an identifier for every integer
 373     // is incredibly inefficient for large arrays. We need a different approach,
 374     // which almost certainly means a different structure for PropertyNameArray.
 375
 376     ArrayStorage* storage = m_storage;
 377
 378     unsigned usedVectorLength = min(m_length, storage->m_vectorLength);
 379     for (unsigned i = 0; i < usedVectorLength; ++i) {
 380         if (storage->m_vector[i])
 381             propertyNames.add(Identifier::from(exec, i));
 382     }
 383
 384     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 385         SparseArrayValueMap::iterator end = map->end();
 386         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
 387             propertyNames.add(Identifier::from(exec, it->first));
 388     }
 389
 390     JSObject::getPropertyNames(exec, propertyNames);
 391 }
 392
 393 bool JSArray::increaseVectorLength(unsigned newLength)
 394 {
 395     // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
 396     // to the vector. Callers have to account for that, because they can do it more efficiently.
 397
 398     ArrayStorage* storage = m_storage;
 399
 400     unsigned vectorLength = storage->m_vectorLength;
 401     ASSERT(newLength > vectorLength);
 402     unsigned newVectorLength = increasedVectorLength(newLength);
 403
 404     storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength)));
 405     if (!storage)
 406         return false;
 407
 408     storage->m_vectorLength = newVectorLength;
 409
 410     for (unsigned i = vectorLength; i < newVectorLength; ++i)
 411         storage->m_vector[i] = 0;
 412
 413     m_storage = storage;
 414     return true;
 415 }
 416
 417 void JSArray::setLength(unsigned newLength)
 418 {
 419     checkConsistency();
 420
 421     ArrayStorage* storage = m_storage;
 422
 423     unsigned length = m_length;
 424
 425     if (newLength < length) {
 426         if (m_fastAccessCutoff > newLength)
 427             m_fastAccessCutoff = newLength;
 428
 429         unsigned usedVectorLength = min(length, storage->m_vectorLength);
 430         for (unsigned i = newLength; i < usedVectorLength; ++i) {
 431             JSValue*& valueSlot = storage->m_vector[i];
 432             bool hadValue = valueSlot;
 433             valueSlot = 0;
 434             storage->m_numValuesInVector -= hadValue;
 435         }
 436
 437         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 438             SparseArrayValueMap copy = *map;
 439             SparseArrayValueMap::iterator end = copy.end();
 440             for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
 441                 if (it->first >= newLength)
 442                     map->remove(it->first);
 443             }
 444             if (map->isEmpty()) {
 445                 delete map;
 446                 storage->m_sparseValueMap = 0;
 447             }
 448         }
 449     }
 450
 451     m_length = newLength;
 452
 453     checkConsistency();
 454 }
 455
 456 void JSArray::mark()
 457 {
 458     JSObject::mark();
 459
 460     ArrayStorage* storage = m_storage;
 461
 462     unsigned usedVectorLength = min(m_length, storage->m_vectorLength);
 463     for (unsigned i = 0; i < usedVectorLength; ++i) {
 464         JSValue* value = storage->m_vector[i];
 465         if (value && !value->marked())
 466             value->mark();
 467     }
 468
 469     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 470         SparseArrayValueMap::iterator end = map->end();
 471         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
 472             JSValue* value = it->second;
 473             if (!value->marked())
 474                 value->mark();
 475         }
 476     }
 477 }
 478
 479 typedef std::pair<JSValue*, UString> ArrayQSortPair;
 480
 481 static int compareByStringPairForQSort(const void* a, const void* b)
 482 {
 483     const ArrayQSortPair* va = static_cast<const ArrayQSortPair*>(a);
 484     const ArrayQSortPair* vb = static_cast<const ArrayQSortPair*>(b);
 485     return compare(va->second, vb->second);
 486 }
 487
 488 void JSArray::sort(ExecState* exec)
 489 {
 490     unsigned lengthNotIncludingUndefined = compactForSorting();
 491     if (m_storage->m_sparseValueMap) {
 492         exec->setException(Error::create(exec, GeneralError, "Out of memory"));
 493         return;
 494     }
 495
 496     if (!lengthNotIncludingUndefined)
 497         return;
 498
 499     // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
 500     // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
 501     // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
 502     // random or otherwise changing results, effectively making compare function inconsistent.
 503
 504     Vector<ArrayQSortPair> values(lengthNotIncludingUndefined);
 505     if (!values.begin()) {
 506         exec->setException(Error::create(exec, GeneralError, "Out of memory"));
 507         return;
 508     }
 509
 510     for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
 511         JSValue* value = m_storage->m_vector[i];
 512         ASSERT(!value->isUndefined());
 513         values[i].first = value;
 514     }
 515
 516     // FIXME: While calling these toString functions, the array could be mutated.
 517     // In that case, objects pointed to by values in this vector might get garbage-collected!
 518
 519     // FIXME: The following loop continues to call toString on subsequent values even after
 520     // a toString call raises an exception.
 521
 522     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
 523         values[i].second = values[i].first->toString(exec);
 524
 525     if (exec->hadException())
 526         return;
 527
 528     // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
 529     // than O(N log N).
 530
 531 #if HAVE(MERGESORT)
 532     mergesort(values.begin(), values.size(), sizeof(ArrayQSortPair), compareByStringPairForQSort);
 533 #else
 534     // FIXME: The qsort library function is likely to not be a stable sort.
 535     // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
 536     qsort(values.begin(), values.size(), sizeof(ArrayQSortPair), compareByStringPairForQSort);
 537 #endif
 538
 539     // FIXME: If the toString function changed the length of the array, this might be
 540     // modifying the vector incorrectly.
 541
 542     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
 543         m_storage->m_vector[i] = values[i].first;
 544
 545     checkConsistency(SortConsistencyCheck);
 546 }
 547
 548 struct AVLTreeNodeForArrayCompare {
 549     JSValue* value;
 550
 551     // Child pointers.  The high bit of gt is robbed and used as the
 552     // balance factor sign.  The high bit of lt is robbed and used as
 553     // the magnitude of the balance factor.
 554     int32_t gt;
 555     int32_t lt;
 556 };
 557
 558 struct AVLTreeAbstractorForArrayCompare {
 559     typedef int32_t handle; // Handle is an index into m_nodes vector.
 560     typedef JSValue* key;
 561     typedef int32_t size;
 562
 563     Vector<AVLTreeNodeForArrayCompare> m_nodes;
 564     ExecState* m_exec;
 565     JSValue* m_compareFunction;
 566     CallType m_compareCallType;
 567     const CallData* m_compareCallData;
 568     JSValue* m_globalThisValue;
 569
 570     handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
 571     void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; }
 572     handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; }
 573     void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; }
 574
 575     int get_balance_factor(handle h)
 576     {
 577         if (m_nodes[h].gt & 0x80000000)
 578             return -1;
 579         return static_cast<unsigned>(m_nodes[h].lt) >> 31;
 580     }
 581
 582     void set_balance_factor(handle h, int bf)
 583     {
 584         if (bf == 0) {
 585             m_nodes[h].lt &= 0x7FFFFFFF;
 586             m_nodes[h].gt &= 0x7FFFFFFF;
 587         } else {
 588             m_nodes[h].lt |= 0x80000000;
 589             if (bf < 0)
 590                 m_nodes[h].gt |= 0x80000000;
 591             else
 592                 m_nodes[h].gt &= 0x7FFFFFFF;
 593         }
 594     }
 595
 596     int compare_key_key(key va, key vb)
 597     {
 598         ASSERT(!va->isUndefined());
 599         ASSERT(!vb->isUndefined());
 600
 601         if (m_exec->hadException())
 602             return 1;
 603
 604         ArgList arguments;
 605         arguments.append(va);
 606         arguments.append(vb);
 607         double compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, m_globalThisValue, arguments)->toNumber(m_exec);
 608         return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
 609     }
 610
 611     int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
 612     int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }
 613
 614     static handle null() { return 0x7FFFFFFF; }
 615 };
 616
 617 void JSArray::sort(ExecState* exec, JSValue* compareFunction, CallType callType, const CallData& callData)
 618 {
 619     checkConsistency();
 620
 621     // FIXME: This ignores exceptions raised in the compare function or in toNumber.
 622
 623     // The maximum tree depth is compiled in - but the caller is clearly up to no good
 624     // if a larger array is passed.
 625     ASSERT(m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
 626     if (m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
 627         return;
 628
 629     if (!m_length)
 630         return;
 631
 632     unsigned usedVectorLength = min(m_length, m_storage->m_vectorLength);
 633
 634     AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
 635     tree.abstractor().m_exec = exec;
 636     tree.abstractor().m_compareFunction = compareFunction;
 637     tree.abstractor().m_compareCallType = callType;
 638     tree.abstractor().m_compareCallData = &callData;
 639     tree.abstractor().m_globalThisValue = exec->globalThisValue();
 640     tree.abstractor().m_nodes.resize(usedVectorLength + (m_storage->m_sparseValueMap ? m_storage->m_sparseValueMap->size() : 0));
 641
 642     if (!tree.abstractor().m_nodes.begin()) {
 643         exec->setException(Error::create(exec, GeneralError, "Out of memory"));
 644         return;
 645     }
 646
 647     // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
 648     // right out from under us while we're building the tree here.
 649
 650     unsigned numDefined = 0;
 651     unsigned numUndefined = 0;
 652
 653     // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
 654     for (; numDefined < usedVectorLength; ++numDefined) {
 655         JSValue* v = m_storage->m_vector[numDefined];
 656         if (!v || v->isUndefined())
 657             break;
 658         tree.abstractor().m_nodes[numDefined].value = v;
 659         tree.insert(numDefined);
 660     }
 661     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
 662         if (JSValue* v = m_storage->m_vector[i]) {
 663             if (v->isUndefined())
 664                 ++numUndefined;
 665             else {
 666                 tree.abstractor().m_nodes[numDefined].value = v;
 667                 tree.insert(numDefined);
 668                 ++numDefined;
 669             }
 670         }
 671     }
 672
 673     unsigned newUsedVectorLength = numDefined + numUndefined;
 674
 675     if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
 676         newUsedVectorLength += map->size();
 677         if (newUsedVectorLength > m_storage->m_vectorLength) {
 678             if (!increaseVectorLength(newUsedVectorLength)) {
 679                 exec->setException(Error::create(exec, GeneralError, "Out of memory"));
 680                 return;
 681             }
 682         }
 683
 684         SparseArrayValueMap::iterator end = map->end();
 685         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
 686             tree.abstractor().m_nodes[numDefined].value = it->second;
 687             tree.insert(numDefined);
 688             ++numDefined;
 689         }
 690
 691         delete map;
 692         m_storage->m_sparseValueMap = 0;
 693     }
 694
 695     ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
 696
 697     // FIXME: If the compare function changed the length of the array, the following might be
 698     // modifying the vector incorrectly.
 699
 700     // Copy the values back into m_storage.
 701     AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
 702     iter.start_iter_least(tree);
 703     for (unsigned i = 0; i < numDefined; ++i) {
 704         m_storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value;
 705         ++iter;
 706     }
 707
 708     // Put undefined values back in.
 709     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
 710         m_storage->m_vector[i] = jsUndefined();
 711
 712     // Ensure that unused values in the vector are zeroed out.
 713     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
 714         m_storage->m_vector[i] = 0;
 715
 716     m_fastAccessCutoff = newUsedVectorLength;
 717     m_storage->m_numValuesInVector = newUsedVectorLength;
 718
 719     checkConsistency(SortConsistencyCheck);
 720 }
 721
 722 unsigned JSArray::compactForSorting()
 723 {
 724     checkConsistency();
 725
 726     ArrayStorage* storage = m_storage;
 727
 728     unsigned usedVectorLength = min(m_length, storage->m_vectorLength);
 729
 730     unsigned numDefined = 0;
 731     unsigned numUndefined = 0;
 732
 733     for (; numDefined < usedVectorLength; ++numDefined) {
 734         JSValue* v = storage->m_vector[numDefined];
 735         if (!v || v->isUndefined())
 736             break;
 737     }
 738     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
 739         if (JSValue* v = storage->m_vector[i]) {
 740             if (v->isUndefined())
 741                 ++numUndefined;
 742             else
 743                 storage->m_vector[numDefined++] = v;
 744         }
 745     }
 746
 747     unsigned newUsedVectorLength = numDefined + numUndefined;
 748
 749     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 750         newUsedVectorLength += map->size();
 751         if (newUsedVectorLength > storage->m_vectorLength) {
 752             if (!increaseVectorLength(newUsedVectorLength))
 753                 return 0;
 754             storage = m_storage;
 755         }
 756
 757         SparseArrayValueMap::iterator end = map->end();
 758         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
 759             storage->m_vector[numDefined++] = it->second;
 760
 761         delete map;
 762         storage->m_sparseValueMap = 0;
 763     }
 764
 765     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
 766         storage->m_vector[i] = jsUndefined();
 767     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
 768         storage->m_vector[i] = 0;
 769
 770     m_fastAccessCutoff = newUsedVectorLength;
 771     storage->m_numValuesInVector = newUsedVectorLength;
 772
 773     checkConsistency(SortConsistencyCheck);
 774
 775     return numDefined;
 776 }
 777
 778 void* JSArray::lazyCreationData()
 779 {
 780     return m_storage->lazyCreationData;
 781 }
 782
 783 void JSArray::setLazyCreationData(void* d)
 784 {
 785     m_storage->lazyCreationData = d;
 786 }
 787
 788 #if CHECK_ARRAY_CONSISTENCY
 789
 790 void JSArray::checkConsistency(ConsistencyCheckType type)
 791 {
 792     ASSERT(m_storage);
 793     if (type == SortConsistencyCheck)
 794         ASSERT(!m_storage->m_sparseValueMap);
 795
 796     ASSERT(m_fastAccessCutoff <= m_length);
 797     ASSERT(m_fastAccessCutoff <= m_storage->m_numValuesInVector);
 798
 799     unsigned numValuesInVector = 0;
 800     for (unsigned i = 0; i < m_storage->m_vectorLength; ++i) {
 801         if (JSValue* value = m_storage->m_vector[i]) {
 802             ASSERT(i < m_length);
 803             if (type != DestructorConsistencyCheck)
 804                 value->type(); // Likely to crash if the object was deallocated.
 805             ++numValuesInVector;
 806         } else {
 807             ASSERT(i >= m_fastAccessCutoff);
 808             if (type == SortConsistencyCheck)
 809                 ASSERT(i >= m_storage->m_numValuesInVector);
 810         }
 811     }
 812     ASSERT(numValuesInVector == m_storage->m_numValuesInVector);
 813
 814     if (m_storage->m_sparseValueMap) {
 815         SparseArrayValueMap::iterator end = m_storage->m_sparseValueMap->end();
 816         for (SparseArrayValueMap::iterator it = m_storage->m_sparseValueMap->begin(); it != end; ++it) {
 817             unsigned index = it->first;
 818             ASSERT(index < m_length);
 819             ASSERT(index >= m_storage->m_vectorLength);
 820             ASSERT(index <= maxArrayIndex);
 821             ASSERT(it->second);
 822             if (type != DestructorConsistencyCheck)
 823                 it->second->type(); // Likely to crash if the object was deallocated.
 824         }
 825     }
 826 }
 827
 828 #endif
 829
 830 JSArray* constructEmptyArray(ExecState* exec)
 831 {
 832     return new (exec) JSArray(exec->lexicalGlobalObject()->arrayPrototype(), 0);
 833 }
 834
 835 JSArray* constructEmptyArray(ExecState* exec, unsigned initialLength)
 836 {
 837     return new (exec) JSArray(exec->lexicalGlobalObject()->arrayPrototype(), initialLength);
 838 }
 839
 840 JSArray* constructArray(ExecState* exec, JSValue* singleItemValue)
 841 {
 842     ArgList values;
 843     values.append(singleItemValue);
 844     return new (exec) JSArray(exec->lexicalGlobalObject()->arrayPrototype(), values);
 845 }
 846
 847 JSArray* constructArray(ExecState* exec, const ArgList& values)
 848 {
 849     return new (exec) JSArray(exec->lexicalGlobalObject()->arrayPrototype(), values);
 850 }
 851
 852 }