JavaScriptCore/kjs/array_instance.cpp

   1 /*
   2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
   3  *  Copyright (C) 2003, 2007 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 "array_instance.h"
  25
  26 #include "JSGlobalObject.h"
  27 #include "PropertyNameArray.h"
  28 #include <wtf/Assertions.h>
  29
  30 using std::min;
  31
  32 namespace KJS {
  33
  34 typedef HashMap<unsigned, JSValue*> SparseArrayValueMap;
  35
  36 struct ArrayStorage {
  37     unsigned m_numValuesInVector;
  38     SparseArrayValueMap* m_sparseValueMap;
  39     JSValue* m_vector[1];
  40 };
  41
  42 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer
  43 static const unsigned maxArrayIndex = 0xFFFFFFFEU;
  44
  45 // Our policy for when to use a vector and when to use a sparse map.
  46 // For all array indices under sparseArrayCutoff, we always use a vector.
  47 // When indices greater than sparseArrayCutoff are involved, we use a vector
  48 // as long as it is 1/8 full. If more sparse than that, we use a map.
  49 static const unsigned sparseArrayCutoff = 10000;
  50 static const unsigned minDensityMultiplier = 8;
  51
  52 static const unsigned copyingSortCutoff = 50000;
  53
  54 const ClassInfo ArrayInstance::info = {"Array", 0, 0};
  55
  56 static inline size_t storageSize(unsigned vectorLength)
  57 {
  58     return sizeof(ArrayStorage) - sizeof(JSValue*) + vectorLength * sizeof(JSValue*);
  59 }
  60
  61 static inline unsigned increasedVectorLength(unsigned newLength)
  62 {
  63     return (newLength * 3 + 1) / 2;
  64 }
  65
  66 static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
  67 {
  68     return length / minDensityMultiplier <= numValues;
  69 }
  70
  71 ArrayInstance::ArrayInstance(JSObject* prototype, unsigned initialLength)
  72     : JSObject(prototype)
  73 {
  74     unsigned initialCapacity = min(initialLength, sparseArrayCutoff);
  75
  76     m_length = initialLength;
  77     m_vectorLength = initialCapacity;
  78     m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
  79
  80     Collector::reportExtraMemoryCost(initialCapacity * sizeof(JSValue*));
  81 }
  82
  83 ArrayInstance::ArrayInstance(JSObject* prototype, const List& list)
  84     : JSObject(prototype)
  85 {
  86     unsigned length = list.size();
  87
  88     m_length = length;
  89     m_vectorLength = length;
  90
  91     ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(length)));
  92
  93     storage->m_numValuesInVector = length;
  94     storage->m_sparseValueMap = 0;
  95
  96     size_t i = 0;
  97     List::const_iterator end = list.end();
  98     for (List::const_iterator it = list.begin(); it != end; ++it, ++i)
  99         storage->m_vector[i] = *it;
 100
 101     m_storage = storage;
 102
 103     // When the array is created non-empty, its cells are filled, so it's really no worse than
 104     // a property map. Therefore don't report extra memory cost.
 105 }
 106
 107 ArrayInstance::~ArrayInstance()
 108 {
 109     delete m_storage->m_sparseValueMap;
 110     fastFree(m_storage);
 111 }
 112
 113 JSValue* ArrayInstance::getItem(unsigned i) const
 114 {
 115     ASSERT(i <= maxArrayIndex);
 116
 117     ArrayStorage* storage = m_storage;
 118
 119     if (i < m_vectorLength) {
 120         JSValue* value = storage->m_vector[i];
 121         return value ? value : jsUndefined();
 122     }
 123
 124     SparseArrayValueMap* map = storage->m_sparseValueMap;
 125     if (!map)
 126         return jsUndefined();
 127
 128     JSValue* value = map->get(i);
 129     return value ? value : jsUndefined();
 130 }
 131
 132 JSValue* ArrayInstance::lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot& slot)
 133 {
 134     return jsNumber(static_cast<ArrayInstance*>(slot.slotBase())->m_length);
 135 }
 136
 137 ALWAYS_INLINE bool ArrayInstance::inlineGetOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
 138 {
 139     ArrayStorage* storage = m_storage;
 140
 141     if (i >= m_length) {
 142         if (i > maxArrayIndex)
 143             return getOwnPropertySlot(exec, Identifier::from(i), slot);
 144         return false;
 145     }
 146
 147     if (i < m_vectorLength) {
 148         JSValue*& valueSlot = storage->m_vector[i];
 149         if (valueSlot) {
 150             slot.setValueSlot(this, &valueSlot);
 151             return true;
 152         }
 153     } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 154         if (i >= sparseArrayCutoff) {
 155             SparseArrayValueMap::iterator it = map->find(i);
 156             if (it != map->end()) {
 157                 slot.setValueSlot(this, &it->second);
 158                 return true;
 159             }
 160         }
 161     }
 162
 163     return false;
 164 }
 165
 166 bool ArrayInstance::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
 167 {
 168     if (propertyName == exec->propertyNames().length) {
 169         slot.setCustom(this, lengthGetter);
 170         return true;
 171     }
 172
 173     bool isArrayIndex;
 174     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 175     if (isArrayIndex)
 176         return inlineGetOwnPropertySlot(exec, i, slot);
 177
 178     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
 179 }
 180
 181 bool ArrayInstance::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
 182 {
 183     return inlineGetOwnPropertySlot(exec, i, slot);
 184 }
 185
 186 // ECMA 15.4.5.1
 187 void ArrayInstance::put(ExecState* exec, const Identifier& propertyName, JSValue* value, int attributes)
 188 {
 189     bool isArrayIndex;
 190     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 191     if (isArrayIndex) {
 192         put(exec, i, value, attributes);
 193         return;
 194     }
 195
 196     if (propertyName == exec->propertyNames().length) {
 197         unsigned newLength = value->toUInt32(exec);
 198         if (value->toNumber(exec) != static_cast<double>(newLength)) {
 199             throwError(exec, RangeError, "Invalid array length.");
 200             return;
 201         }
 202         setLength(newLength);
 203         return;
 204     }
 205
 206     JSObject::put(exec, propertyName, value, attributes);
 207 }
 208
 209 void ArrayInstance::put(ExecState* exec, unsigned i, JSValue* value, int attributes)
 210 {
 211     if (i > maxArrayIndex) {
 212         put(exec, Identifier::from(i), value, attributes);
 213         return;
 214     }
 215
 216     ArrayStorage* storage = m_storage;
 217
 218     unsigned length = m_length;
 219     if (i >= length) {
 220         length = i + 1;
 221         m_length = length;
 222     }
 223
 224     if (i < m_vectorLength) {
 225         JSValue*& valueSlot = storage->m_vector[i];
 226         storage->m_numValuesInVector += !valueSlot;
 227         valueSlot = value;
 228         return;
 229     }
 230
 231     if (i < sparseArrayCutoff) {
 232         increaseVectorLength(i + 1);
 233         storage = m_storage;
 234         ++storage->m_numValuesInVector;
 235         storage->m_vector[i] = value;
 236         return;
 237     }
 238
 239     SparseArrayValueMap* map = storage->m_sparseValueMap;
 240     if (!map || map->isEmpty()) {
 241         if (isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
 242             increaseVectorLength(i + 1);
 243             storage = m_storage;
 244             ++storage->m_numValuesInVector;
 245             storage->m_vector[i] = value;
 246             return;
 247         }
 248         if (!map) {
 249             map = new SparseArrayValueMap;
 250             storage->m_sparseValueMap = map;
 251         }
 252         map->set(i, value);
 253         return;
 254     }
 255
 256     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
 257     if (!isDenseEnoughForVector(i + 1, newNumValuesInVector)) {
 258         map->set(i, value);
 259         return;
 260     }
 261
 262     unsigned newVectorLength = increasedVectorLength(i + 1);
 263     for (unsigned j = m_vectorLength; j < newVectorLength; ++j)
 264         newNumValuesInVector += map->contains(j);
 265     newNumValuesInVector -= map->contains(i);
 266     if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
 267         unsigned proposedNewNumValuesInVector = newNumValuesInVector;
 268         while (true) {
 269             unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
 270             for (unsigned j = newVectorLength; j < proposedNewVectorLength; ++j)
 271                 proposedNewNumValuesInVector += map->contains(j);
 272             if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
 273                 break;
 274             newVectorLength = proposedNewVectorLength;
 275             newNumValuesInVector = proposedNewNumValuesInVector;
 276         }
 277     }
 278
 279     storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength)));
 280
 281     unsigned vectorLength = m_vectorLength;
 282     if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
 283         for (unsigned j = vectorLength; j < newVectorLength; ++j)
 284             storage->m_vector[j] = 0;
 285         map->remove(i);
 286     } else {
 287         for (unsigned j = vectorLength; j < newVectorLength; ++j)
 288             storage->m_vector[j] = map->take(j);
 289     }
 290
 291     storage->m_vector[i] = value;
 292
 293     m_vectorLength = newVectorLength;
 294     storage->m_numValuesInVector = newNumValuesInVector;
 295 }
 296
 297 bool ArrayInstance::deleteProperty(ExecState* exec, const Identifier& propertyName)
 298 {
 299     bool isArrayIndex;
 300     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 301     if (isArrayIndex)
 302         return deleteProperty(exec, i);
 303
 304     if (propertyName == exec->propertyNames().length)
 305         return false;
 306
 307     return JSObject::deleteProperty(exec, propertyName);
 308 }
 309
 310 bool ArrayInstance::deleteProperty(ExecState* exec, unsigned i)
 311 {
 312     ArrayStorage* storage = m_storage;
 313
 314     if (i < m_vectorLength) {
 315         JSValue*& valueSlot = storage->m_vector[i];
 316         bool hadValue = valueSlot;
 317         valueSlot = 0;
 318         storage->m_numValuesInVector -= hadValue;
 319         return hadValue;
 320     }
 321
 322     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 323         if (i >= sparseArrayCutoff) {
 324             SparseArrayValueMap::iterator it = map->find(i);
 325             if (it != map->end()) {
 326                 map->remove(it);
 327                 return true;
 328             }
 329         }
 330     }
 331
 332     if (i > maxArrayIndex)
 333         return deleteProperty(exec, Identifier::from(i));
 334
 335     return false;
 336 }
 337
 338 void ArrayInstance::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
 339 {
 340     // FIXME: Filling PropertyNameArray with an identifier for every integer
 341     // is incredibly inefficient for large arrays. We need a different approach.
 342
 343     ArrayStorage* storage = m_storage;
 344
 345     unsigned usedVectorLength = min(m_length, m_vectorLength);
 346     for (unsigned i = 0; i < usedVectorLength; ++i) {
 347         if (storage->m_vector[i])
 348             propertyNames.add(Identifier::from(i));
 349     }
 350
 351     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 352         SparseArrayValueMap::iterator end = map->end();
 353         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
 354             propertyNames.add(Identifier::from(it->first));
 355     }
 356
 357     JSObject::getPropertyNames(exec, propertyNames);
 358 }
 359
 360 void ArrayInstance::increaseVectorLength(unsigned newLength)
 361 {
 362     ArrayStorage* storage = m_storage;
 363
 364     unsigned vectorLength = m_vectorLength;
 365     ASSERT(newLength > vectorLength);
 366     unsigned newVectorLength = increasedVectorLength(newLength);
 367
 368     storage = static_cast<ArrayStorage*>(fastRealloc(storage, storageSize(newVectorLength)));
 369     m_vectorLength = newVectorLength;
 370
 371     for (unsigned i = vectorLength; i < newVectorLength; ++i)
 372         storage->m_vector[i] = 0;
 373
 374     m_storage = storage;
 375 }
 376
 377 void ArrayInstance::setLength(unsigned newLength)
 378 {
 379     ArrayStorage* storage = m_storage;
 380
 381     unsigned length = m_length;
 382
 383     if (newLength < length) {
 384         unsigned usedVectorLength = min(length, m_vectorLength);
 385         for (unsigned i = newLength; i < usedVectorLength; ++i) {
 386             JSValue*& valueSlot = storage->m_vector[i];
 387             bool hadValue = valueSlot;
 388             valueSlot = 0;
 389             storage->m_numValuesInVector -= hadValue;
 390         }
 391
 392         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 393             SparseArrayValueMap copy = *map;
 394             SparseArrayValueMap::iterator end = copy.end();
 395             for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
 396                 if (it->first >= newLength)
 397                     map->remove(it->first);
 398             }
 399             if (map->isEmpty()) {
 400                 delete map;
 401                 storage->m_sparseValueMap = 0;
 402             }
 403         }
 404     }
 405
 406     m_length = newLength;
 407 }
 408
 409 void ArrayInstance::mark()
 410 {
 411     JSObject::mark();
 412
 413     ArrayStorage* storage = m_storage;
 414
 415     unsigned usedVectorLength = min(m_length, m_vectorLength);
 416     for (unsigned i = 0; i < usedVectorLength; ++i) {
 417         JSValue* value = storage->m_vector[i];
 418         if (value && !value->marked())
 419             value->mark();
 420     }
 421
 422     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 423         SparseArrayValueMap::iterator end = map->end();
 424         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
 425             JSValue* value = it->second;
 426             if (!value->marked())
 427                 value->mark();
 428         }
 429     }
 430 }
 431
 432 static int compareByStringPairForQSort(const void* a, const void* b)
 433 {
 434     const std::pair<JSValue*, UString>* va = static_cast<const std::pair<JSValue*, UString>*>(a);
 435     const std::pair<JSValue*, UString>* vb = static_cast<const std::pair<JSValue*, UString>*>(b);
 436     return compare(va->second, vb->second);
 437 }
 438
 439 static ExecState* execForCompareByStringForQSort = 0;
 440 static int compareByStringForQSort(const void* a, const void* b)
 441 {
 442     ExecState* exec = execForCompareByStringForQSort;
 443
 444     JSValue* va = *static_cast<JSValue* const*>(a);
 445     JSValue* vb = *static_cast<JSValue* const*>(b);
 446     ASSERT(!va->isUndefined());
 447     ASSERT(!vb->isUndefined());
 448
 449     return compare(va->toString(exec), vb->toString(exec));
 450 }
 451
 452 void ArrayInstance::sort(ExecState* exec)
 453 {
 454     unsigned lengthNotIncludingUndefined = compactForSorting();
 455
 456     if (lengthNotIncludingUndefined < copyingSortCutoff) {
 457         // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
 458         // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
 459         // buffer.  For large arrays, we fall back to a qsort on the JavaScriptValues to avoid creating copies.
 460
 461         Vector<std::pair<JSValue*, UString> > values(lengthNotIncludingUndefined);
 462         for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
 463             JSValue* value = m_storage->m_vector[i];
 464             ASSERT(!value->isUndefined());
 465             values[i].first = value;
 466             values[i].second = value->toString(exec);
 467         }
 468
 469         // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
 470         // than O(N log N).
 471
 472 #if HAVE(MERGESORT)
 473         mergesort(values.begin(), values.size(), sizeof(std::pair<JSValue*, UString>), compareByStringPairForQSort);
 474 #else
 475         qsort(values.begin(), values.size(), sizeof(std::pair<JSValue*, UString>), compareByStringPairForQSort);
 476 #endif
 477         for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
 478             m_storage->m_vector[i] = values[i].first;
 479         return;
 480     }
 481
 482     ExecState* oldExec = execForCompareByStringForQSort;
 483     execForCompareByStringForQSort = exec;
 484     qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
 485     execForCompareByStringForQSort = oldExec;
 486 }
 487
 488 struct CompareWithCompareFunctionArguments {
 489     CompareWithCompareFunctionArguments(ExecState *e, JSObject *cf)
 490         : exec(e)
 491         , compareFunction(cf)
 492         , globalObject(e->dynamicGlobalObject())
 493     {
 494     }
 495
 496     ExecState *exec;
 497     JSObject *compareFunction;
 498     List arguments;
 499     JSGlobalObject* globalObject;
 500 };
 501
 502 static CompareWithCompareFunctionArguments* compareWithCompareFunctionArguments = 0;
 503
 504 static int compareWithCompareFunctionForQSort(const void* a, const void* b)
 505 {
 506     CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments;
 507
 508     JSValue* va = *static_cast<JSValue* const*>(a);
 509     JSValue* vb = *static_cast<JSValue* const*>(b);
 510     ASSERT(!va->isUndefined());
 511     ASSERT(!vb->isUndefined());
 512
 513     args->arguments.clear();
 514     args->arguments.append(va);
 515     args->arguments.append(vb);
 516     double compareResult = args->compareFunction->call
 517         (args->exec, args->globalObject, args->arguments)->toNumber(args->exec);
 518     return compareResult < 0 ? -1 : compareResult > 0 ? 1 : 0;
 519 }
 520
 521 void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction)
 522 {
 523     size_t lengthNotIncludingUndefined = compactForSorting();
 524
 525     CompareWithCompareFunctionArguments* oldArgs = compareWithCompareFunctionArguments;
 526     CompareWithCompareFunctionArguments args(exec, compareFunction);
 527     compareWithCompareFunctionArguments = &args;
 528
 529 #if HAVE(MERGESORT)
 530     // Because mergesort usually does fewer compares, it is faster than qsort here.
 531     // However, because it requires extra copies of the storage buffer, don't use it for very
 532     // large arrays.
 533
 534     // FIXME: A tree sort using a perfectly balanced tree (e.g. an AVL tree) could do an even
 535     // better job of minimizing compares.
 536
 537     if (lengthNotIncludingUndefined < copyingSortCutoff) {
 538         // During the sort, we could do a garbage collect, and it's important to still
 539         // have references to every object in the array for ArrayInstance::mark.
 540         // The mergesort algorithm does not guarantee this, so we sort a copy rather
 541         // than the original.
 542         size_t size = storageSize(m_vectorLength);
 543         ArrayStorage* copy = static_cast<ArrayStorage*>(fastMalloc(size));
 544         memcpy(copy, m_storage, size);
 545         mergesort(copy->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
 546         fastFree(m_storage);
 547         m_storage = copy;
 548         compareWithCompareFunctionArguments = oldArgs;
 549         return;
 550     }
 551 #endif
 552
 553     qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
 554     compareWithCompareFunctionArguments = oldArgs;
 555 }
 556
 557 unsigned ArrayInstance::compactForSorting()
 558 {
 559     ArrayStorage* storage = m_storage;
 560
 561     unsigned usedVectorLength = min(m_length, m_vectorLength);
 562
 563     unsigned numDefined = 0;
 564     unsigned numUndefined = 0;
 565
 566     for (; numDefined < usedVectorLength; ++numDefined) {
 567         JSValue* v = storage->m_vector[numDefined];
 568         if (!v || v->isUndefined())
 569             break;
 570     }
 571     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
 572         if (JSValue* v = storage->m_vector[i]) {
 573             if (v->isUndefined())
 574                 ++numUndefined;
 575             else
 576                 storage->m_vector[numDefined++] = v;
 577         }
 578     }
 579
 580     unsigned newUsedVectorLength = numDefined + numUndefined;
 581
 582     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 583         newUsedVectorLength += map->size();
 584         if (newUsedVectorLength > m_vectorLength) {
 585             increaseVectorLength(newUsedVectorLength);
 586             storage = m_storage;
 587         }
 588
 589         SparseArrayValueMap::iterator end = map->end();
 590         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
 591             storage->m_vector[numDefined++] = it->second;
 592
 593         delete map;
 594         storage->m_sparseValueMap = 0;
 595     }
 596
 597     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
 598         storage->m_vector[i] = jsUndefined();
 599     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
 600         storage->m_vector[i] = 0;
 601
 602     return numDefined;
 603 }
 604
 605 }