Source/JavaScriptCore/runtime/JSObject.cpp

   1 /*
   2  *  Copyright (C) 1999-2001 Harri Porten (porten@kde.org)
   3  *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
   4  *  Copyright (C) 2003, 2004, 2005, 2006, 2008, 2009, 2012, 2013 Apple Inc. All rights reserved.
   5  *  Copyright (C) 2007 Eric Seidel (eric@webkit.org)
   6  *
   7  *  This library is free software; you can redistribute it and/or
   8  *  modify it under the terms of the GNU Library 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  *  Library General Public License for more details.
  16  *
  17  *  You should have received a copy of the GNU Library General Public License
  18  *  along with this library; see the file COPYING.LIB.  If not, write to
  19  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  20  *  Boston, MA 02110-1301, USA.
  21  *
  22  */
  23
  24 #include "config.h"
  25 #include "JSObject.h"
  26
  27 #include "ButterflyInlines.h"
  28 #include "CopiedSpaceInlines.h"
  29 #include "CopyVisitor.h"
  30 #include "CopyVisitorInlines.h"
  31 #include "DatePrototype.h"
  32 #include "ErrorConstructor.h"
  33 #include "Executable.h"
  34 #include "GetterSetter.h"
  35 #include "IndexingHeaderInlines.h"
  36 #include "JSFunction.h"
  37 #include "JSGlobalObject.h"
  38 #include "Lookup.h"
  39 #include "NativeErrorConstructor.h"
  40 #include "Nodes.h"
  41 #include "ObjectPrototype.h"
  42 #include "Operations.h"
  43 #include "PropertyDescriptor.h"
  44 #include "PropertyNameArray.h"
  45 #include "Reject.h"
  46 #include "SlotVisitorInlines.h"
  47 #include <math.h>
  48 #include <wtf/Assertions.h>
  49
  50 namespace JSC {
  51
  52 // We keep track of the size of the last array after it was grown. We use this
  53 // as a simple heuristic for as the value to grow the next array from size 0.
  54 // This value is capped by the constant FIRST_VECTOR_GROW defined in
  55 // ArrayConventions.h.
  56 static unsigned lastArraySize = 0;
  57
  58 JSCell* getCallableObjectSlow(JSCell* cell)
  59 {
  60     Structure* structure = cell->structure();
  61     if (structure->typeInfo().type() == JSFunctionType)
  62         return cell;
  63     if (structure->classInfo()->isSubClassOf(InternalFunction::info()))
  64         return cell;
  65     return 0;
  66 }
  67
  68 ASSERT_HAS_TRIVIAL_DESTRUCTOR(JSObject);
  69 ASSERT_HAS_TRIVIAL_DESTRUCTOR(JSFinalObject);
  70
  71 const char* StrictModeReadonlyPropertyWriteError = "Attempted to assign to readonly property.";
  72
  73 const ClassInfo JSObject::s_info = { "Object", 0, 0, 0, CREATE_METHOD_TABLE(JSObject) };
  74
  75 const ClassInfo JSFinalObject::s_info = { "Object", &Base::s_info, 0, 0, CREATE_METHOD_TABLE(JSFinalObject) };
  76
  77 static inline void getClassPropertyNames(ExecState* exec, const ClassInfo* classInfo, PropertyNameArray& propertyNames, EnumerationMode mode, bool didReify)
  78 {
  79     // Add properties from the static hashtables of properties
  80     for (; classInfo; classInfo = classInfo->parentClass) {
  81         const HashTable* table = classInfo->propHashTable(exec);
  82         if (!table)
  83             continue;
  84         table->initializeIfNeeded(exec);
  85         ASSERT(table->table);
  86
  87         int hashSizeMask = table->compactSize - 1;
  88         const HashEntry* entry = table->table;
  89         for (int i = 0; i <= hashSizeMask; ++i, ++entry) {
  90             if (entry->key() && (!(entry->attributes() & DontEnum) || (mode == IncludeDontEnumProperties)) && !((entry->attributes() & Function) && didReify))
  91                 propertyNames.add(entry->key());
  92         }
  93     }
  94 }
  95
  96 ALWAYS_INLINE void JSObject::copyButterfly(CopyVisitor& visitor, Butterfly* butterfly, size_t storageSize)
  97 {
  98     ASSERT(butterfly);
  99
 100     Structure* structure = this->structure();
 101
 102     size_t propertyCapacity = structure->outOfLineCapacity();
 103     size_t preCapacity;
 104     size_t indexingPayloadSizeInBytes;
 105     bool hasIndexingHeader = this->hasIndexingHeader();
 106     if (UNLIKELY(hasIndexingHeader)) {
 107         preCapacity = butterfly->indexingHeader()->preCapacity(structure);
 108         indexingPayloadSizeInBytes = butterfly->indexingHeader()->indexingPayloadSizeInBytes(structure);
 109     } else {
 110         preCapacity = 0;
 111         indexingPayloadSizeInBytes = 0;
 112     }
 113     size_t capacityInBytes = Butterfly::totalSize(preCapacity, propertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes);
 114     if (visitor.checkIfShouldCopy(butterfly->base(preCapacity, propertyCapacity))) {
 115         Butterfly* newButterfly = Butterfly::createUninitializedDuringCollection(visitor, preCapacity, propertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes);
 116
 117         // Copy the properties.
 118         PropertyStorage currentTarget = newButterfly->propertyStorage();
 119         PropertyStorage currentSource = butterfly->propertyStorage();
 120         for (size_t count = storageSize; count--;)
 121             (--currentTarget)->setWithoutWriteBarrier((--currentSource)->get());
 122
 123         if (UNLIKELY(hasIndexingHeader)) {
 124             *newButterfly->indexingHeader() = *butterfly->indexingHeader();
 125
 126             // Copy the array if appropriate.
 127
 128             WriteBarrier<Unknown>* currentTarget;
 129             WriteBarrier<Unknown>* currentSource;
 130             size_t count;
 131
 132             switch (structure->indexingType()) {
 133             case ALL_UNDECIDED_INDEXING_TYPES:
 134             case ALL_CONTIGUOUS_INDEXING_TYPES:
 135             case ALL_INT32_INDEXING_TYPES:
 136             case ALL_DOUBLE_INDEXING_TYPES: {
 137                 currentTarget = newButterfly->contiguous().data();
 138                 currentSource = butterfly->contiguous().data();
 139                 RELEASE_ASSERT(newButterfly->publicLength() <= newButterfly->vectorLength());
 140                 count = newButterfly->vectorLength();
 141                 break;
 142             }
 143
 144             case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
 145                 newButterfly->arrayStorage()->copyHeaderFromDuringGC(*butterfly->arrayStorage());
 146                 currentTarget = newButterfly->arrayStorage()->m_vector;
 147                 currentSource = butterfly->arrayStorage()->m_vector;
 148                 count = newButterfly->arrayStorage()->vectorLength();
 149                 break;
 150             }
 151
 152             default:
 153                 currentTarget = 0;
 154                 currentSource = 0;
 155                 count = 0;
 156                 break;
 157             }
 158
 159             memcpy(currentTarget, currentSource, count * sizeof(EncodedJSValue));
 160         }
 161
 162         m_butterfly = newButterfly;
 163         visitor.didCopy(butterfly->base(preCapacity, propertyCapacity), capacityInBytes);
 164     }
 165 }
 166
 167 ALWAYS_INLINE void JSObject::visitButterfly(SlotVisitor& visitor, Butterfly* butterfly, size_t storageSize)
 168 {
 169     ASSERT(butterfly);
 170
 171     Structure* structure = this->structure();
 172
 173     size_t propertyCapacity = structure->outOfLineCapacity();
 174     size_t preCapacity;
 175     size_t indexingPayloadSizeInBytes;
 176     bool hasIndexingHeader = this->hasIndexingHeader();
 177     if (UNLIKELY(hasIndexingHeader)) {
 178         preCapacity = butterfly->indexingHeader()->preCapacity(structure);
 179         indexingPayloadSizeInBytes = butterfly->indexingHeader()->indexingPayloadSizeInBytes(structure);
 180     } else {
 181         preCapacity = 0;
 182         indexingPayloadSizeInBytes = 0;
 183     }
 184     size_t capacityInBytes = Butterfly::totalSize(preCapacity, propertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes);
 185
 186     // Mark the properties.
 187     visitor.appendValues(butterfly->propertyStorage() - storageSize, storageSize);
 188     visitor.copyLater(
 189         this, ButterflyCopyToken,
 190         butterfly->base(preCapacity, propertyCapacity), capacityInBytes);
 191
 192     // Mark the array if appropriate.
 193     switch (structure->indexingType()) {
 194     case ALL_CONTIGUOUS_INDEXING_TYPES:
 195         visitor.appendValues(butterfly->contiguous().data(), butterfly->publicLength());
 196         break;
 197     case ALL_ARRAY_STORAGE_INDEXING_TYPES:
 198         visitor.appendValues(butterfly->arrayStorage()->m_vector, butterfly->arrayStorage()->vectorLength());
 199         if (butterfly->arrayStorage()->m_sparseMap)
 200             visitor.append(&butterfly->arrayStorage()->m_sparseMap);
 201         break;
 202     default:
 203         break;
 204     }
 205 }
 206
 207 void JSObject::visitChildren(JSCell* cell, SlotVisitor& visitor)
 208 {
 209     JSObject* thisObject = jsCast<JSObject*>(cell);
 210     ASSERT_GC_OBJECT_INHERITS(thisObject, info());
 211 #if !ASSERT_DISABLED
 212     bool wasCheckingForDefaultMarkViolation = visitor.m_isCheckingForDefaultMarkViolation;
 213     visitor.m_isCheckingForDefaultMarkViolation = false;
 214 #endif
 215
 216     JSCell::visitChildren(thisObject, visitor);
 217
 218     Butterfly* butterfly = thisObject->butterfly();
 219     if (butterfly)
 220         thisObject->visitButterfly(visitor, butterfly, thisObject->structure()->outOfLineSize());
 221
 222 #if !ASSERT_DISABLED
 223     visitor.m_isCheckingForDefaultMarkViolation = wasCheckingForDefaultMarkViolation;
 224 #endif
 225 }
 226
 227 void JSObject::copyBackingStore(JSCell* cell, CopyVisitor& visitor, CopyToken token)
 228 {
 229     JSObject* thisObject = jsCast<JSObject*>(cell);
 230     ASSERT_GC_OBJECT_INHERITS(thisObject, info());
 231
 232     if (token != ButterflyCopyToken)
 233         return;
 234
 235     Butterfly* butterfly = thisObject->butterfly();
 236     if (butterfly)
 237         thisObject->copyButterfly(visitor, butterfly, thisObject->structure()->outOfLineSize());
 238 }
 239
 240 void JSFinalObject::visitChildren(JSCell* cell, SlotVisitor& visitor)
 241 {
 242     JSFinalObject* thisObject = jsCast<JSFinalObject*>(cell);
 243     ASSERT_GC_OBJECT_INHERITS(thisObject, info());
 244 #if !ASSERT_DISABLED
 245     bool wasCheckingForDefaultMarkViolation = visitor.m_isCheckingForDefaultMarkViolation;
 246     visitor.m_isCheckingForDefaultMarkViolation = false;
 247 #endif
 248
 249     JSCell::visitChildren(thisObject, visitor);
 250
 251     Butterfly* butterfly = thisObject->butterfly();
 252     if (butterfly)
 253         thisObject->visitButterfly(visitor, butterfly, thisObject->structure()->outOfLineSize());
 254
 255     size_t storageSize = thisObject->structure()->inlineSize();
 256     visitor.appendValues(thisObject->inlineStorage(), storageSize);
 257
 258 #if !ASSERT_DISABLED
 259     visitor.m_isCheckingForDefaultMarkViolation = wasCheckingForDefaultMarkViolation;
 260 #endif
 261 }
 262
 263 String JSObject::className(const JSObject* object)
 264 {
 265     const ClassInfo* info = object->classInfo();
 266     ASSERT(info);
 267     return info->className;
 268 }
 269
 270 bool JSObject::getOwnPropertySlotByIndex(JSObject* thisObject, ExecState* exec, unsigned i, PropertySlot& slot)
 271 {
 272     // NB. The fact that we're directly consulting our indexed storage implies that it is not
 273     // legal for anyone to override getOwnPropertySlot() without also overriding
 274     // getOwnPropertySlotByIndex().
 275
 276     if (i > MAX_ARRAY_INDEX)
 277         return thisObject->methodTable()->getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
 278
 279     switch (thisObject->structure()->indexingType()) {
 280     case ALL_BLANK_INDEXING_TYPES:
 281     case ALL_UNDECIDED_INDEXING_TYPES:
 282         break;
 283
 284     case ALL_INT32_INDEXING_TYPES:
 285     case ALL_CONTIGUOUS_INDEXING_TYPES: {
 286         Butterfly* butterfly = thisObject->m_butterfly;
 287         if (i >= butterfly->vectorLength())
 288             return false;
 289
 290         JSValue value = butterfly->contiguous()[i].get();
 291         if (value) {
 292             slot.setValue(thisObject, None, value);
 293             return true;
 294         }
 295
 296         return false;
 297     }
 298
 299     case ALL_DOUBLE_INDEXING_TYPES: {
 300         Butterfly* butterfly = thisObject->m_butterfly;
 301         if (i >= butterfly->vectorLength())
 302             return false;
 303
 304         double value = butterfly->contiguousDouble()[i];
 305         if (value == value) {
 306             slot.setValue(thisObject, None, JSValue(JSValue::EncodeAsDouble, value));
 307             return true;
 308         }
 309
 310         return false;
 311     }
 312
 313     case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
 314         ArrayStorage* storage = thisObject->m_butterfly->arrayStorage();
 315         if (i >= storage->length())
 316             return false;
 317
 318         if (i < storage->vectorLength()) {
 319             JSValue value = storage->m_vector[i].get();
 320             if (value) {
 321                 slot.setValue(thisObject, None, value);
 322                 return true;
 323             }
 324         } else if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
 325             SparseArrayValueMap::iterator it = map->find(i);
 326             if (it != map->notFound()) {
 327                 it->value.get(thisObject, slot);
 328                 return true;
 329             }
 330         }
 331         break;
 332     }
 333
 334     default:
 335         RELEASE_ASSERT_NOT_REACHED();
 336         break;
 337     }
 338
 339     return false;
 340 }
 341
 342 // ECMA 8.6.2.2
 343 void JSObject::put(JSCell* cell, ExecState* exec, PropertyName propertyName, JSValue value, PutPropertySlot& slot)
 344 {
 345     JSObject* thisObject = jsCast<JSObject*>(cell);
 346     ASSERT(value);
 347     ASSERT(!Heap::heap(value) || Heap::heap(value) == Heap::heap(thisObject));
 348     VM& vm = exec->vm();
 349
 350     // Try indexed put first. This is required for correctness, since loads on property names that appear like
 351     // valid indices will never look in the named property storage.
 352     unsigned i = propertyName.asIndex();
 353     if (i != PropertyName::NotAnIndex) {
 354         putByIndex(thisObject, exec, i, value, slot.isStrictMode());
 355         return;
 356     }
 357
 358     // Check if there are any setters or getters in the prototype chain
 359     JSValue prototype;
 360     if (propertyName != exec->propertyNames().underscoreProto) {
 361         for (JSObject* obj = thisObject; !obj->structure()->hasReadOnlyOrGetterSetterPropertiesExcludingProto(); obj = asObject(prototype)) {
 362             prototype = obj->prototype();
 363             if (prototype.isNull()) {
 364                 ASSERT(!thisObject->structure()->prototypeChainMayInterceptStoreTo(exec->vm(), propertyName));
 365                 if (!thisObject->putDirectInternal<PutModePut>(vm, propertyName, value, 0, slot, getCallableObject(value))
 366                     && slot.isStrictMode())
 367                     throwTypeError(exec, ASCIILiteral(StrictModeReadonlyPropertyWriteError));
 368                 return;
 369             }
 370         }
 371     }
 372
 373     JSObject* obj;
 374     for (obj = thisObject; ; obj = asObject(prototype)) {
 375         unsigned attributes;
 376         JSCell* specificValue;
 377         PropertyOffset offset = obj->structure()->get(vm, propertyName, attributes, specificValue);
 378         if (isValidOffset(offset)) {
 379             if (attributes & ReadOnly) {
 380                 ASSERT(thisObject->structure()->prototypeChainMayInterceptStoreTo(exec->vm(), propertyName) || obj == thisObject);
 381                 if (slot.isStrictMode())
 382                     throwError(exec, createTypeError(exec, ASCIILiteral(StrictModeReadonlyPropertyWriteError)));
 383                 return;
 384             }
 385
 386             JSValue gs = obj->getDirect(offset);
 387             if (gs.isGetterSetter()) {
 388                 callSetter(exec, cell, gs, value, slot.isStrictMode() ? StrictMode : NotStrictMode);
 389                 return;
 390             } else
 391                 ASSERT(!(attributes & Accessor));
 392
 393             // If there's an existing property on the object or one of its
 394             // prototypes it should be replaced, so break here.
 395             break;
 396         }
 397
 398         prototype = obj->prototype();
 399         if (prototype.isNull())
 400             break;
 401     }
 402
 403     ASSERT(!thisObject->structure()->prototypeChainMayInterceptStoreTo(exec->vm(), propertyName) || obj == thisObject);
 404     if (!thisObject->putDirectInternal<PutModePut>(vm, propertyName, value, 0, slot, getCallableObject(value)) && slot.isStrictMode())
 405         throwTypeError(exec, ASCIILiteral(StrictModeReadonlyPropertyWriteError));
 406     return;
 407 }
 408
 409 void JSObject::putByIndex(JSCell* cell, ExecState* exec, unsigned propertyName, JSValue value, bool shouldThrow)
 410 {
 411     JSObject* thisObject = jsCast<JSObject*>(cell);
 412
 413     if (propertyName > MAX_ARRAY_INDEX) {
 414         PutPropertySlot slot(shouldThrow);
 415         thisObject->methodTable()->put(thisObject, exec, Identifier::from(exec, propertyName), value, slot);
 416         return;
 417     }
 418
 419     switch (thisObject->structure()->indexingType()) {
 420     case ALL_BLANK_INDEXING_TYPES:
 421         break;
 422
 423     case ALL_UNDECIDED_INDEXING_TYPES: {
 424         thisObject->convertUndecidedForValue(exec->vm(), value);
 425         // Reloop.
 426         putByIndex(cell, exec, propertyName, value, shouldThrow);
 427         return;
 428     }
 429
 430     case ALL_INT32_INDEXING_TYPES: {
 431         if (!value.isInt32()) {
 432             thisObject->convertInt32ForValue(exec->vm(), value);
 433             putByIndex(cell, exec, propertyName, value, shouldThrow);
 434             return;
 435         }
 436         // Fall through.
 437     }
 438
 439     case ALL_CONTIGUOUS_INDEXING_TYPES: {
 440         Butterfly* butterfly = thisObject->m_butterfly;
 441         if (propertyName >= butterfly->vectorLength())
 442             break;
 443         butterfly->contiguous()[propertyName].set(exec->vm(), thisObject, value);
 444         if (propertyName >= butterfly->publicLength())
 445             butterfly->setPublicLength(propertyName + 1);
 446         return;
 447     }
 448
 449     case ALL_DOUBLE_INDEXING_TYPES: {
 450         if (!value.isNumber()) {
 451             thisObject->convertDoubleToContiguous(exec->vm());
 452             // Reloop.
 453             putByIndex(cell, exec, propertyName, value, shouldThrow);
 454             return;
 455         }
 456         double valueAsDouble = value.asNumber();
 457         if (valueAsDouble != valueAsDouble) {
 458             thisObject->convertDoubleToContiguous(exec->vm());
 459             // Reloop.
 460             putByIndex(cell, exec, propertyName, value, shouldThrow);
 461             return;
 462         }
 463         Butterfly* butterfly = thisObject->m_butterfly;
 464         if (propertyName >= butterfly->vectorLength())
 465             break;
 466         butterfly->contiguousDouble()[propertyName] = valueAsDouble;
 467         if (propertyName >= butterfly->publicLength())
 468             butterfly->setPublicLength(propertyName + 1);
 469         return;
 470     }
 471
 472     case NonArrayWithArrayStorage:
 473     case ArrayWithArrayStorage: {
 474         ArrayStorage* storage = thisObject->m_butterfly->arrayStorage();
 475
 476         if (propertyName >= storage->vectorLength())
 477             break;
 478
 479         WriteBarrier<Unknown>& valueSlot = storage->m_vector[propertyName];
 480         unsigned length = storage->length();
 481
 482         // Update length & m_numValuesInVector as necessary.
 483         if (propertyName >= length) {
 484             length = propertyName + 1;
 485             storage->setLength(length);
 486             ++storage->m_numValuesInVector;
 487         } else if (!valueSlot)
 488             ++storage->m_numValuesInVector;
 489
 490         valueSlot.set(exec->vm(), thisObject, value);
 491         return;
 492     }
 493
 494     case NonArrayWithSlowPutArrayStorage:
 495     case ArrayWithSlowPutArrayStorage: {
 496         ArrayStorage* storage = thisObject->m_butterfly->arrayStorage();
 497
 498         if (propertyName >= storage->vectorLength())
 499             break;
 500
 501         WriteBarrier<Unknown>& valueSlot = storage->m_vector[propertyName];
 502         unsigned length = storage->length();
 503
 504         // Update length & m_numValuesInVector as necessary.
 505         if (propertyName >= length) {
 506             if (thisObject->attemptToInterceptPutByIndexOnHole(exec, propertyName, value, shouldThrow))
 507                 return;
 508             length = propertyName + 1;
 509             storage->setLength(length);
 510             ++storage->m_numValuesInVector;
 511         } else if (!valueSlot) {
 512             if (thisObject->attemptToInterceptPutByIndexOnHole(exec, propertyName, value, shouldThrow))
 513                 return;
 514             ++storage->m_numValuesInVector;
 515         }
 516
 517         valueSlot.set(exec->vm(), thisObject, value);
 518         return;
 519     }
 520
 521     default:
 522         RELEASE_ASSERT_NOT_REACHED();
 523     }
 524
 525     thisObject->putByIndexBeyondVectorLength(exec, propertyName, value, shouldThrow);
 526 }
 527
 528 ArrayStorage* JSObject::enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(VM& vm, ArrayStorage* storage)
 529 {
 530     SparseArrayValueMap* map = storage->m_sparseMap.get();
 531
 532     if (!map)
 533         map = allocateSparseIndexMap(vm);
 534
 535     if (map->sparseMode())
 536         return storage;
 537
 538     map->setSparseMode();
 539
 540     unsigned usedVectorLength = std::min(storage->length(), storage->vectorLength());
 541     for (unsigned i = 0; i < usedVectorLength; ++i) {
 542         JSValue value = storage->m_vector[i].get();
 543         // This will always be a new entry in the map, so no need to check we can write,
 544         // and attributes are default so no need to set them.
 545         if (value)
 546             map->add(this, i).iterator->value.set(vm, this, value);
 547     }
 548
 549     DeferGC deferGC(vm.heap);
 550     Butterfly* newButterfly = storage->butterfly()->resizeArray(vm, this, structure(), 0, ArrayStorage::sizeFor(0));
 551     RELEASE_ASSERT(newButterfly);
 552
 553     m_butterfly = newButterfly;
 554     newButterfly->arrayStorage()->m_indexBias = 0;
 555     newButterfly->arrayStorage()->setVectorLength(0);
 556     newButterfly->arrayStorage()->m_sparseMap.set(vm, this, map);
 557
 558     return newButterfly->arrayStorage();
 559 }
 560
 561 void JSObject::enterDictionaryIndexingMode(VM& vm)
 562 {
 563     switch (structure()->indexingType()) {
 564     case ALL_BLANK_INDEXING_TYPES:
 565     case ALL_UNDECIDED_INDEXING_TYPES:
 566     case ALL_INT32_INDEXING_TYPES:
 567     case ALL_DOUBLE_INDEXING_TYPES:
 568     case ALL_CONTIGUOUS_INDEXING_TYPES:
 569         // NOTE: this is horribly inefficient, as it will perform two conversions. We could optimize
 570         // this case if we ever cared.
 571         enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(vm, ensureArrayStorageSlow(vm));
 572         break;
 573     case ALL_ARRAY_STORAGE_INDEXING_TYPES:
 574         enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(vm, m_butterfly->arrayStorage());
 575         break;
 576
 577     default:
 578         break;
 579     }
 580 }
 581
 582 void JSObject::notifyPresenceOfIndexedAccessors(VM& vm)
 583 {
 584     if (mayInterceptIndexedAccesses())
 585         return;
 586
 587     setStructure(vm, Structure::nonPropertyTransition(vm, structure(), AddIndexedAccessors));
 588
 589     if (!vm.prototypeMap.isPrototype(this))
 590         return;
 591
 592     globalObject()->haveABadTime(vm);
 593 }
 594
 595 Butterfly* JSObject::createInitialIndexedStorage(VM& vm, unsigned length, size_t elementSize)
 596 {
 597     ASSERT(length < MAX_ARRAY_INDEX);
 598     IndexingType oldType = structure()->indexingType();
 599     ASSERT_UNUSED(oldType, !hasIndexedProperties(oldType));
 600     ASSERT(!structure()->needsSlowPutIndexing());
 601     ASSERT(!indexingShouldBeSparse());
 602     unsigned vectorLength = std::max(length, BASE_VECTOR_LEN);
 603     Butterfly* newButterfly = Butterfly::createOrGrowArrayRight(
 604         m_butterfly, vm, this, structure(), structure()->outOfLineCapacity(), false, 0,
 605         elementSize * vectorLength);
 606     newButterfly->setPublicLength(length);
 607     newButterfly->setVectorLength(vectorLength);
 608     return newButterfly;
 609 }
 610
 611 Butterfly* JSObject::createInitialUndecided(VM& vm, unsigned length)
 612 {
 613     DeferGC deferGC(vm.heap);
 614     Butterfly* newButterfly = createInitialIndexedStorage(vm, length, sizeof(EncodedJSValue));
 615     Structure* newStructure = Structure::nonPropertyTransition(vm, structure(), AllocateUndecided);
 616     setStructureAndButterfly(vm, newStructure, newButterfly);
 617     return newButterfly;
 618 }
 619
 620 ContiguousJSValues JSObject::createInitialInt32(VM& vm, unsigned length)
 621 {
 622     DeferGC deferGC(vm.heap);
 623     Butterfly* newButterfly = createInitialIndexedStorage(vm, length, sizeof(EncodedJSValue));
 624     Structure* newStructure = Structure::nonPropertyTransition(vm, structure(), AllocateInt32);
 625     setStructureAndButterfly(vm, newStructure, newButterfly);
 626     return newButterfly->contiguousInt32();
 627 }
 628
 629 ContiguousDoubles JSObject::createInitialDouble(VM& vm, unsigned length)
 630 {
 631     DeferGC deferGC(vm.heap);
 632     Butterfly* newButterfly = createInitialIndexedStorage(vm, length, sizeof(double));
 633     for (unsigned i = newButterfly->vectorLength(); i--;)
 634         newButterfly->contiguousDouble()[i] = QNaN;
 635     Structure* newStructure = Structure::nonPropertyTransition(vm, structure(), AllocateDouble);
 636     setStructureAndButterfly(vm, newStructure, newButterfly);
 637     return newButterfly->contiguousDouble();
 638 }
 639
 640 ContiguousJSValues JSObject::createInitialContiguous(VM& vm, unsigned length)
 641 {
 642     DeferGC deferGC(vm.heap);
 643     Butterfly* newButterfly = createInitialIndexedStorage(vm, length, sizeof(EncodedJSValue));
 644     Structure* newStructure = Structure::nonPropertyTransition(vm, structure(), AllocateContiguous);
 645     setStructureAndButterfly(vm, newStructure, newButterfly);
 646     return newButterfly->contiguous();
 647 }
 648
 649 ArrayStorage* JSObject::createArrayStorage(VM& vm, unsigned length, unsigned vectorLength)
 650 {
 651     DeferGC deferGC(vm.heap);
 652     IndexingType oldType = structure()->indexingType();
 653     ASSERT_UNUSED(oldType, !hasIndexedProperties(oldType));
 654     Butterfly* newButterfly = Butterfly::createOrGrowArrayRight(
 655         m_butterfly, vm, this, structure(), structure()->outOfLineCapacity(), false, 0,
 656         ArrayStorage::sizeFor(vectorLength));
 657     RELEASE_ASSERT(newButterfly);
 658
 659     ArrayStorage* result = newButterfly->arrayStorage();
 660     result->setLength(length);
 661     result->setVectorLength(vectorLength);
 662     result->m_sparseMap.clear();
 663     result->m_numValuesInVector = 0;
 664     result->m_indexBias = 0;
 665     Structure* newStructure = Structure::nonPropertyTransition(vm, structure(), structure()->suggestedArrayStorageTransition());
 666     setStructureAndButterfly(vm, newStructure, newButterfly);
 667     return result;
 668 }
 669
 670 ArrayStorage* JSObject::createInitialArrayStorage(VM& vm)
 671 {
 672     return createArrayStorage(vm, 0, BASE_VECTOR_LEN);
 673 }
 674
 675 ContiguousJSValues JSObject::convertUndecidedToInt32(VM& vm)
 676 {
 677     ASSERT(hasUndecided(structure()->indexingType()));
 678     setStructure(vm, Structure::nonPropertyTransition(vm, structure(), AllocateInt32));
 679     return m_butterfly->contiguousInt32();
 680 }
 681
 682 ContiguousDoubles JSObject::convertUndecidedToDouble(VM& vm)
 683 {
 684     ASSERT(hasUndecided(structure()->indexingType()));
 685
 686     for (unsigned i = m_butterfly->vectorLength(); i--;)
 687         m_butterfly->contiguousDouble()[i] = QNaN;
 688
 689     setStructure(vm, Structure::nonPropertyTransition(vm, structure(), AllocateDouble));
 690     return m_butterfly->contiguousDouble();
 691 }
 692
 693 ContiguousJSValues JSObject::convertUndecidedToContiguous(VM& vm)
 694 {
 695     ASSERT(hasUndecided(structure()->indexingType()));
 696     setStructure(vm, Structure::nonPropertyTransition(vm, structure(), AllocateContiguous));
 697     return m_butterfly->contiguous();
 698 }
 699
 700 ArrayStorage* JSObject::constructConvertedArrayStorageWithoutCopyingElements(VM& vm, unsigned neededLength)
 701 {
 702     unsigned publicLength = m_butterfly->publicLength();
 703     unsigned propertyCapacity = structure()->outOfLineCapacity();
 704     unsigned propertySize = structure()->outOfLineSize();
 705
 706     Butterfly* newButterfly = Butterfly::createUninitialized(
 707         vm, this, 0, propertyCapacity, true, ArrayStorage::sizeFor(neededLength));
 708
 709     memcpy(
 710         newButterfly->propertyStorage() - propertySize,
 711         m_butterfly->propertyStorage() - propertySize,
 712         propertySize * sizeof(EncodedJSValue));
 713
 714     ArrayStorage* newStorage = newButterfly->arrayStorage();
 715     newStorage->setVectorLength(neededLength);
 716     newStorage->setLength(publicLength);
 717     newStorage->m_sparseMap.clear();
 718     newStorage->m_indexBias = 0;
 719     newStorage->m_numValuesInVector = 0;
 720
 721     return newStorage;
 722 }
 723
 724 ArrayStorage* JSObject::convertUndecidedToArrayStorage(VM& vm, NonPropertyTransition transition, unsigned neededLength)
 725 {
 726     DeferGC deferGC(vm.heap);
 727     ASSERT(hasUndecided(structure()->indexingType()));
 728
 729     ArrayStorage* storage = constructConvertedArrayStorageWithoutCopyingElements(vm, neededLength);
 730     // No need to copy elements.
 731
 732     Structure* newStructure = Structure::nonPropertyTransition(vm, structure(), transition);
 733     setStructureAndButterfly(vm, newStructure, storage->butterfly());
 734     return storage;
 735 }
 736
 737 ArrayStorage* JSObject::convertUndecidedToArrayStorage(VM& vm, NonPropertyTransition transition)
 738 {
 739     return convertUndecidedToArrayStorage(vm, transition, m_butterfly->vectorLength());
 740 }
 741
 742 ArrayStorage* JSObject::convertUndecidedToArrayStorage(VM& vm)
 743 {
 744     return convertUndecidedToArrayStorage(vm, structure()->suggestedArrayStorageTransition());
 745 }
 746
 747 ContiguousDoubles JSObject::convertInt32ToDouble(VM& vm)
 748 {
 749     ASSERT(hasInt32(structure()->indexingType()));
 750
 751     for (unsigned i = m_butterfly->vectorLength(); i--;) {
 752         WriteBarrier<Unknown>* current = &m_butterfly->contiguousInt32()[i];
 753         double* currentAsDouble = bitwise_cast<double*>(current);
 754         JSValue v = current->get();
 755         if (!v) {
 756             *currentAsDouble = QNaN;
 757             continue;
 758         }
 759         ASSERT(v.isInt32());
 760         *currentAsDouble = v.asInt32();
 761     }
 762
 763     setStructure(vm, Structure::nonPropertyTransition(vm, structure(), AllocateDouble));
 764     return m_butterfly->contiguousDouble();
 765 }
 766
 767 ContiguousJSValues JSObject::convertInt32ToContiguous(VM& vm)
 768 {
 769     ASSERT(hasInt32(structure()->indexingType()));
 770
 771     setStructure(vm, Structure::nonPropertyTransition(vm, structure(), AllocateContiguous));
 772     return m_butterfly->contiguous();
 773 }
 774
 775 ArrayStorage* JSObject::convertInt32ToArrayStorage(VM& vm, NonPropertyTransition transition, unsigned neededLength)
 776 {
 777     ASSERT(hasInt32(structure()->indexingType()));
 778
 779     DeferGC deferGC(vm.heap);
 780     ArrayStorage* newStorage = constructConvertedArrayStorageWithoutCopyingElements(vm, neededLength);
 781     for (unsigned i = m_butterfly->publicLength(); i--;) {
 782         JSValue v = m_butterfly->contiguous()[i].get();
 783         if (!v)
 784             continue;
 785         newStorage->m_vector[i].setWithoutWriteBarrier(v);
 786         newStorage->m_numValuesInVector++;
 787     }
 788
 789     Structure* newStructure = Structure::nonPropertyTransition(vm, structure(), transition);
 790     setStructureAndButterfly(vm, newStructure, newStorage->butterfly());
 791     return newStorage;
 792 }
 793
 794 ArrayStorage* JSObject::convertInt32ToArrayStorage(VM& vm, NonPropertyTransition transition)
 795 {
 796     return convertInt32ToArrayStorage(vm, transition, m_butterfly->vectorLength());
 797 }
 798
 799 ArrayStorage* JSObject::convertInt32ToArrayStorage(VM& vm)
 800 {
 801     return convertInt32ToArrayStorage(vm, structure()->suggestedArrayStorageTransition());
 802 }
 803
 804 template<JSObject::DoubleToContiguousMode mode>
 805 ContiguousJSValues JSObject::genericConvertDoubleToContiguous(VM& vm)
 806 {
 807     ASSERT(hasDouble(structure()->indexingType()));
 808
 809     for (unsigned i = m_butterfly->vectorLength(); i--;) {
 810         double* current = &m_butterfly->contiguousDouble()[i];
 811         WriteBarrier<Unknown>* currentAsValue = bitwise_cast<WriteBarrier<Unknown>*>(current);
 812         double value = *current;
 813         if (value != value) {
 814             currentAsValue->clear();
 815             continue;
 816         }
 817         JSValue v;
 818         switch (mode) {
 819         case EncodeValueAsDouble:
 820             v = JSValue(JSValue::EncodeAsDouble, value);
 821             break;
 822         case RageConvertDoubleToValue:
 823             v = jsNumber(value);
 824             break;
 825         }
 826         ASSERT(v.isNumber());
 827         currentAsValue->setWithoutWriteBarrier(v);
 828     }
 829
 830     setStructure(vm, Structure::nonPropertyTransition(vm, structure(), AllocateContiguous));
 831     return m_butterfly->contiguous();
 832 }
 833
 834 ContiguousJSValues JSObject::convertDoubleToContiguous(VM& vm)
 835 {
 836     return genericConvertDoubleToContiguous<EncodeValueAsDouble>(vm);
 837 }
 838
 839 ContiguousJSValues JSObject::rageConvertDoubleToContiguous(VM& vm)
 840 {
 841     return genericConvertDoubleToContiguous<RageConvertDoubleToValue>(vm);
 842 }
 843
 844 ArrayStorage* JSObject::convertDoubleToArrayStorage(VM& vm, NonPropertyTransition transition, unsigned neededLength)
 845 {
 846     DeferGC deferGC(vm.heap);
 847     ASSERT(hasDouble(structure()->indexingType()));
 848
 849     ArrayStorage* newStorage = constructConvertedArrayStorageWithoutCopyingElements(vm, neededLength);
 850     for (unsigned i = m_butterfly->publicLength(); i--;) {
 851         double value = m_butterfly->contiguousDouble()[i];
 852         if (value != value)
 853             continue;
 854         newStorage->m_vector[i].setWithoutWriteBarrier(JSValue(JSValue::EncodeAsDouble, value));
 855         newStorage->m_numValuesInVector++;
 856     }
 857
 858     Structure* newStructure = Structure::nonPropertyTransition(vm, structure(), transition);
 859     setStructureAndButterfly(vm, newStructure, newStorage->butterfly());
 860     return newStorage;
 861 }
 862
 863 ArrayStorage* JSObject::convertDoubleToArrayStorage(VM& vm, NonPropertyTransition transition)
 864 {
 865     return convertDoubleToArrayStorage(vm, transition, m_butterfly->vectorLength());
 866 }
 867
 868 ArrayStorage* JSObject::convertDoubleToArrayStorage(VM& vm)
 869 {
 870     return convertDoubleToArrayStorage(vm, structure()->suggestedArrayStorageTransition());
 871 }
 872
 873 ArrayStorage* JSObject::convertContiguousToArrayStorage(VM& vm, NonPropertyTransition transition, unsigned neededLength)
 874 {
 875     DeferGC deferGC(vm.heap);
 876     ASSERT(hasContiguous(structure()->indexingType()));
 877
 878     ArrayStorage* newStorage = constructConvertedArrayStorageWithoutCopyingElements(vm, neededLength);
 879     for (unsigned i = m_butterfly->publicLength(); i--;) {
 880         JSValue v = m_butterfly->contiguous()[i].get();
 881         if (!v)
 882             continue;
 883         newStorage->m_vector[i].setWithoutWriteBarrier(v);
 884         newStorage->m_numValuesInVector++;
 885     }
 886
 887     Structure* newStructure = Structure::nonPropertyTransition(vm, structure(), transition);
 888     setStructureAndButterfly(vm, newStructure, newStorage->butterfly());
 889     return newStorage;
 890 }
 891
 892 ArrayStorage* JSObject::convertContiguousToArrayStorage(VM& vm, NonPropertyTransition transition)
 893 {
 894     return convertContiguousToArrayStorage(vm, transition, m_butterfly->vectorLength());
 895 }
 896
 897 ArrayStorage* JSObject::convertContiguousToArrayStorage(VM& vm)
 898 {
 899     return convertContiguousToArrayStorage(vm, structure()->suggestedArrayStorageTransition());
 900 }
 901
 902 void JSObject::convertUndecidedForValue(VM& vm, JSValue value)
 903 {
 904     if (value.isInt32()) {
 905         convertUndecidedToInt32(vm);
 906         return;
 907     }
 908
 909     if (value.isDouble()) {
 910         convertUndecidedToDouble(vm);
 911         return;
 912     }
 913
 914     convertUndecidedToContiguous(vm);
 915 }
 916
 917 void JSObject::convertInt32ForValue(VM& vm, JSValue value)
 918 {
 919     ASSERT(!value.isInt32());
 920
 921     if (value.isDouble()) {
 922         convertInt32ToDouble(vm);
 923         return;
 924     }
 925
 926     convertInt32ToContiguous(vm);
 927 }
 928
 929 void JSObject::setIndexQuicklyToUndecided(VM& vm, unsigned index, JSValue value)
 930 {
 931     ASSERT(index < m_butterfly->publicLength());
 932     ASSERT(index < m_butterfly->vectorLength());
 933     convertUndecidedForValue(vm, value);
 934     setIndexQuickly(vm, index, value);
 935 }
 936
 937 void JSObject::convertInt32ToDoubleOrContiguousWhilePerformingSetIndex(VM& vm, unsigned index, JSValue value)
 938 {
 939     ASSERT(!value.isInt32());
 940     convertInt32ForValue(vm, value);
 941     setIndexQuickly(vm, index, value);
 942 }
 943
 944 void JSObject::convertDoubleToContiguousWhilePerformingSetIndex(VM& vm, unsigned index, JSValue value)
 945 {
 946     ASSERT(!value.isNumber() || value.asNumber() != value.asNumber());
 947     convertDoubleToContiguous(vm);
 948     setIndexQuickly(vm, index, value);
 949 }
 950
 951 ContiguousJSValues JSObject::ensureInt32Slow(VM& vm)
 952 {
 953     ASSERT(inherits(info()));
 954
 955     switch (structure()->indexingType()) {
 956     case ALL_BLANK_INDEXING_TYPES:
 957         if (UNLIKELY(indexingShouldBeSparse() || structure()->needsSlowPutIndexing()))
 958             return ContiguousJSValues();
 959         return createInitialInt32(vm, 0);
 960
 961     case ALL_UNDECIDED_INDEXING_TYPES:
 962         return convertUndecidedToInt32(vm);
 963
 964     case ALL_DOUBLE_INDEXING_TYPES:
 965     case ALL_CONTIGUOUS_INDEXING_TYPES:
 966     case ALL_ARRAY_STORAGE_INDEXING_TYPES:
 967         return ContiguousJSValues();
 968
 969     default:
 970         CRASH();
 971         return ContiguousJSValues();
 972     }
 973 }
 974
 975 ContiguousDoubles JSObject::ensureDoubleSlow(VM& vm)
 976 {
 977     ASSERT(inherits(info()));
 978
 979     switch (structure()->indexingType()) {
 980     case ALL_BLANK_INDEXING_TYPES:
 981         if (UNLIKELY(indexingShouldBeSparse() || structure()->needsSlowPutIndexing()))
 982             return ContiguousDoubles();
 983         return createInitialDouble(vm, 0);
 984
 985     case ALL_UNDECIDED_INDEXING_TYPES:
 986         return convertUndecidedToDouble(vm);
 987
 988     case ALL_INT32_INDEXING_TYPES:
 989         return convertInt32ToDouble(vm);
 990
 991     case ALL_CONTIGUOUS_INDEXING_TYPES:
 992     case ALL_ARRAY_STORAGE_INDEXING_TYPES:
 993         return ContiguousDoubles();
 994
 995     default:
 996         CRASH();
 997         return ContiguousDoubles();
 998     }
 999 }
1000
1001 ContiguousJSValues JSObject::ensureContiguousSlow(VM& vm, DoubleToContiguousMode mode)
1002 {
1003     ASSERT(inherits(info()));
1004
1005     switch (structure()->indexingType()) {
1006     case ALL_BLANK_INDEXING_TYPES:
1007         if (UNLIKELY(indexingShouldBeSparse() || structure()->needsSlowPutIndexing()))
1008             return ContiguousJSValues();
1009         return createInitialContiguous(vm, 0);
1010
1011     case ALL_UNDECIDED_INDEXING_TYPES:
1012         return convertUndecidedToContiguous(vm);
1013
1014     case ALL_INT32_INDEXING_TYPES:
1015         return convertInt32ToContiguous(vm);
1016
1017     case ALL_DOUBLE_INDEXING_TYPES:
1018         if (mode == RageConvertDoubleToValue)
1019             return rageConvertDoubleToContiguous(vm);
1020         return convertDoubleToContiguous(vm);
1021
1022     case ALL_ARRAY_STORAGE_INDEXING_TYPES:
1023         return ContiguousJSValues();
1024
1025     default:
1026         CRASH();
1027         return ContiguousJSValues();
1028     }
1029 }
1030
1031 ContiguousJSValues JSObject::ensureContiguousSlow(VM& vm)
1032 {
1033     return ensureContiguousSlow(vm, EncodeValueAsDouble);
1034 }
1035
1036 ContiguousJSValues JSObject::rageEnsureContiguousSlow(VM& vm)
1037 {
1038     return ensureContiguousSlow(vm, RageConvertDoubleToValue);
1039 }
1040
1041 ArrayStorage* JSObject::ensureArrayStorageSlow(VM& vm)
1042 {
1043     ASSERT(inherits(info()));
1044
1045     switch (structure()->indexingType()) {
1046     case ALL_BLANK_INDEXING_TYPES:
1047         if (UNLIKELY(indexingShouldBeSparse()))
1048             return ensureArrayStorageExistsAndEnterDictionaryIndexingMode(vm);
1049         return createInitialArrayStorage(vm);
1050
1051     case ALL_UNDECIDED_INDEXING_TYPES:
1052         ASSERT(!indexingShouldBeSparse());
1053         ASSERT(!structure()->needsSlowPutIndexing());
1054         return convertUndecidedToArrayStorage(vm);
1055
1056     case ALL_INT32_INDEXING_TYPES:
1057         ASSERT(!indexingShouldBeSparse());
1058         ASSERT(!structure()->needsSlowPutIndexing());
1059         return convertInt32ToArrayStorage(vm);
1060
1061     case ALL_DOUBLE_INDEXING_TYPES:
1062         ASSERT(!indexingShouldBeSparse());
1063         ASSERT(!structure()->needsSlowPutIndexing());
1064         return convertDoubleToArrayStorage(vm);
1065
1066     case ALL_CONTIGUOUS_INDEXING_TYPES:
1067         ASSERT(!indexingShouldBeSparse());
1068         ASSERT(!structure()->needsSlowPutIndexing());
1069         return convertContiguousToArrayStorage(vm);
1070
1071     default:
1072         RELEASE_ASSERT_NOT_REACHED();
1073         return 0;
1074     }
1075 }
1076
1077 ArrayStorage* JSObject::ensureArrayStorageExistsAndEnterDictionaryIndexingMode(VM& vm)
1078 {
1079     switch (structure()->indexingType()) {
1080     case ALL_BLANK_INDEXING_TYPES: {
1081         createArrayStorage(vm, 0, 0);
1082         SparseArrayValueMap* map = allocateSparseIndexMap(vm);
1083         map->setSparseMode();
1084         return arrayStorage();
1085     }
1086
1087     case ALL_UNDECIDED_INDEXING_TYPES:
1088         return enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(vm, convertUndecidedToArrayStorage(vm));
1089
1090     case ALL_INT32_INDEXING_TYPES:
1091         return enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(vm, convertInt32ToArrayStorage(vm));
1092
1093     case ALL_DOUBLE_INDEXING_TYPES:
1094         return enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(vm, convertDoubleToArrayStorage(vm));
1095
1096     case ALL_CONTIGUOUS_INDEXING_TYPES:
1097         return enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(vm, convertContiguousToArrayStorage(vm));
1098
1099     case ALL_ARRAY_STORAGE_INDEXING_TYPES:
1100         return enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(vm, m_butterfly->arrayStorage());
1101
1102     default:
1103         CRASH();
1104         return 0;
1105     }
1106 }
1107
1108 void JSObject::switchToSlowPutArrayStorage(VM& vm)
1109 {
1110     switch (structure()->indexingType()) {
1111     case ALL_UNDECIDED_INDEXING_TYPES:
1112         convertUndecidedToArrayStorage(vm, AllocateSlowPutArrayStorage);
1113         break;
1114
1115     case ALL_INT32_INDEXING_TYPES:
1116         convertInt32ToArrayStorage(vm, AllocateSlowPutArrayStorage);
1117         break;
1118
1119     case ALL_DOUBLE_INDEXING_TYPES:
1120         convertDoubleToArrayStorage(vm, AllocateSlowPutArrayStorage);
1121         break;
1122
1123     case ALL_CONTIGUOUS_INDEXING_TYPES:
1124         convertContiguousToArrayStorage(vm, AllocateSlowPutArrayStorage);
1125         break;
1126
1127     case NonArrayWithArrayStorage:
1128     case ArrayWithArrayStorage: {
1129         Structure* newStructure = Structure::nonPropertyTransition(vm, structure(), SwitchToSlowPutArrayStorage);
1130         setStructure(vm, newStructure);
1131         break;
1132     }
1133
1134     default:
1135         CRASH();
1136         break;
1137     }
1138 }
1139
1140 void JSObject::setPrototype(VM& vm, JSValue prototype)
1141 {
1142     ASSERT(prototype);
1143     if (prototype.isObject())
1144         vm.prototypeMap.addPrototype(asObject(prototype));
1145
1146     Structure* newStructure = Structure::changePrototypeTransition(vm, structure(), prototype);
1147     setStructure(vm, newStructure);
1148
1149     if (!newStructure->anyObjectInChainMayInterceptIndexedAccesses())
1150         return;
1151
1152     if (vm.prototypeMap.isPrototype(this)) {
1153         newStructure->globalObject()->haveABadTime(vm);
1154         return;
1155     }
1156
1157     if (!hasIndexedProperties(structure()->indexingType()))
1158         return;
1159
1160     if (shouldUseSlowPut(structure()->indexingType()))
1161         return;
1162
1163     switchToSlowPutArrayStorage(vm);
1164 }
1165
1166 bool JSObject::setPrototypeWithCycleCheck(ExecState* exec, JSValue prototype)
1167 {
1168     ASSERT(methodTable()->toThis(this, exec, NotStrictMode) == this);
1169     JSValue nextPrototype = prototype;
1170     while (nextPrototype && nextPrototype.isObject()) {
1171         if (nextPrototype == this)
1172             return false;
1173         nextPrototype = asObject(nextPrototype)->prototype();
1174     }
1175     setPrototype(exec->vm(), prototype);
1176     return true;
1177 }
1178
1179 bool JSObject::allowsAccessFrom(ExecState* exec)
1180 {
1181     JSGlobalObject* globalObject = this->globalObject();
1182     return globalObject->globalObjectMethodTable()->allowsAccessFrom(globalObject, exec);
1183 }
1184
1185 void JSObject::putDirectAccessor(ExecState* exec, PropertyName propertyName, JSValue value, unsigned attributes)
1186 {
1187     ASSERT(value.isGetterSetter() && (attributes & Accessor));
1188
1189     unsigned index = propertyName.asIndex();
1190     if (index != PropertyName::NotAnIndex) {
1191         putDirectIndex(exec, index, value, attributes, PutDirectIndexLikePutDirect);
1192         return;
1193     }
1194
1195     VM& vm = exec->vm();
1196
1197     PutPropertySlot slot;
1198     putDirectInternal<PutModeDefineOwnProperty>(vm, propertyName, value, attributes, slot, getCallableObject(value));
1199
1200     // putDirect will change our Structure if we add a new property. For
1201     // getters and setters, though, we also need to change our Structure
1202     // if we override an existing non-getter or non-setter.
1203     if (slot.type() != PutPropertySlot::NewProperty)
1204         setStructure(vm, Structure::attributeChangeTransition(vm, structure(), propertyName, attributes));
1205
1206     if (attributes & ReadOnly)
1207         structure()->setContainsReadOnlyProperties();
1208
1209     structure()->setHasGetterSetterProperties(propertyName == vm.propertyNames->underscoreProto);
1210 }
1211
1212 bool JSObject::hasProperty(ExecState* exec, PropertyName propertyName) const
1213 {
1214     PropertySlot slot(this);
1215     return const_cast<JSObject*>(this)->getPropertySlot(exec, propertyName, slot);
1216 }
1217
1218 bool JSObject::hasProperty(ExecState* exec, unsigned propertyName) const
1219 {
1220     PropertySlot slot(this);
1221     return const_cast<JSObject*>(this)->getPropertySlot(exec, propertyName, slot);
1222 }
1223
1224 // ECMA 8.6.2.5
1225 bool JSObject::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName)
1226 {
1227     JSObject* thisObject = jsCast<JSObject*>(cell);
1228
1229     unsigned i = propertyName.asIndex();
1230     if (i != PropertyName::NotAnIndex)
1231         return thisObject->methodTable()->deletePropertyByIndex(thisObject, exec, i);
1232
1233     if (!thisObject->staticFunctionsReified())
1234         thisObject->reifyStaticFunctionsForDelete(exec);
1235
1236     unsigned attributes;
1237     JSCell* specificValue;
1238     if (isValidOffset(thisObject->structure()->get(exec->vm(), propertyName, attributes, specificValue))) {
1239         if (attributes & DontDelete && !exec->vm().isInDefineOwnProperty())
1240             return false;
1241         thisObject->removeDirect(exec->vm(), propertyName);
1242         return true;
1243     }
1244
1245     // Look in the static hashtable of properties
1246     const HashEntry* entry = thisObject->findPropertyHashEntry(exec, propertyName);
1247     if (entry) {
1248         if (entry->attributes() & DontDelete && !exec->vm().isInDefineOwnProperty())
1249             return false; // this builtin property can't be deleted
1250
1251         putEntry(exec, entry, propertyName, jsUndefined(), thisObject);
1252     }
1253
1254     return true;
1255 }
1256
1257 bool JSObject::hasOwnProperty(ExecState* exec, PropertyName propertyName) const
1258 {
1259     PropertySlot slot(this);
1260     return const_cast<JSObject*>(this)->methodTable()->getOwnPropertySlot(const_cast<JSObject*>(this), exec, propertyName, slot);
1261 }
1262
1263 bool JSObject::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
1264 {
1265     JSObject* thisObject = jsCast<JSObject*>(cell);
1266
1267     if (i > MAX_ARRAY_INDEX)
1268         return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, i));
1269
1270     switch (thisObject->structure()->indexingType()) {
1271     case ALL_BLANK_INDEXING_TYPES:
1272     case ALL_UNDECIDED_INDEXING_TYPES:
1273         return true;
1274
1275     case ALL_INT32_INDEXING_TYPES:
1276     case ALL_CONTIGUOUS_INDEXING_TYPES: {
1277         Butterfly* butterfly = thisObject->m_butterfly;
1278         if (i >= butterfly->vectorLength())
1279             return true;
1280         butterfly->contiguous()[i].clear();
1281         return true;
1282     }
1283
1284     case ALL_DOUBLE_INDEXING_TYPES: {
1285         Butterfly* butterfly = thisObject->m_butterfly;
1286         if (i >= butterfly->vectorLength())
1287             return true;
1288         butterfly->contiguousDouble()[i] = QNaN;
1289         return true;
1290     }
1291
1292     case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
1293         ArrayStorage* storage = thisObject->m_butterfly->arrayStorage();
1294
1295         if (i < storage->vectorLength()) {
1296             WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
1297             if (valueSlot) {
1298                 valueSlot.clear();
1299                 --storage->m_numValuesInVector;
1300             }
1301         } else if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
1302             SparseArrayValueMap::iterator it = map->find(i);
1303             if (it != map->notFound()) {
1304                 if (it->value.attributes & DontDelete)
1305                     return false;
1306                 map->remove(it);
1307             }
1308         }
1309
1310         return true;
1311     }
1312
1313     default:
1314         RELEASE_ASSERT_NOT_REACHED();
1315         return false;
1316     }
1317 }
1318
1319 static ALWAYS_INLINE JSValue callDefaultValueFunction(ExecState* exec, const JSObject* object, PropertyName propertyName)
1320 {
1321     JSValue function = object->get(exec, propertyName);
1322     CallData callData;
1323     CallType callType = getCallData(function, callData);
1324     if (callType == CallTypeNone)
1325         return exec->exception();
1326
1327     // Prevent "toString" and "valueOf" from observing execution if an exception
1328     // is pending.
1329     if (exec->hadException())
1330         return exec->exception();
1331
1332     JSValue result = call(exec, function, callType, callData, const_cast<JSObject*>(object), exec->emptyList());
1333     ASSERT(!result.isGetterSetter());
1334     if (exec->hadException())
1335         return exec->exception();
1336     if (result.isObject())
1337         return JSValue();
1338     return result;
1339 }
1340
1341 bool JSObject::getPrimitiveNumber(ExecState* exec, double& number, JSValue& result) const
1342 {
1343     result = methodTable()->defaultValue(this, exec, PreferNumber);
1344     number = result.toNumber(exec);
1345     return !result.isString();
1346 }
1347
1348 // ECMA 8.6.2.6
1349 JSValue JSObject::defaultValue(const JSObject* object, ExecState* exec, PreferredPrimitiveType hint)
1350 {
1351     // Must call toString first for Date objects.
1352     if ((hint == PreferString) || (hint != PreferNumber && object->prototype() == exec->lexicalGlobalObject()->datePrototype())) {
1353         JSValue value = callDefaultValueFunction(exec, object, exec->propertyNames().toString);
1354         if (value)
1355             return value;
1356         value = callDefaultValueFunction(exec, object, exec->propertyNames().valueOf);
1357         if (value)
1358             return value;
1359     } else {
1360         JSValue value = callDefaultValueFunction(exec, object, exec->propertyNames().valueOf);
1361         if (value)
1362             return value;
1363         value = callDefaultValueFunction(exec, object, exec->propertyNames().toString);
1364         if (value)
1365             return value;
1366     }
1367
1368     ASSERT(!exec->hadException());
1369
1370     return throwError(exec, createTypeError(exec, ASCIILiteral("No default value")));
1371 }
1372
1373 const HashEntry* JSObject::findPropertyHashEntry(ExecState* exec, PropertyName propertyName) const
1374 {
1375     for (const ClassInfo* info = classInfo(); info; info = info->parentClass) {
1376         if (const HashTable* propHashTable = info->propHashTable(exec)) {
1377             if (const HashEntry* entry = propHashTable->entry(exec, propertyName))
1378                 return entry;
1379         }
1380     }
1381     return 0;
1382 }
1383
1384 bool JSObject::hasInstance(ExecState* exec, JSValue value)
1385 {
1386     TypeInfo info = structure()->typeInfo();
1387     if (info.implementsDefaultHasInstance())
1388         return defaultHasInstance(exec, value, get(exec, exec->propertyNames().prototype));
1389     if (info.implementsHasInstance())
1390         return methodTable()->customHasInstance(this, exec, value);
1391     throwError(exec, createInvalidParameterError(exec, "instanceof" , this));
1392     return false;
1393 }
1394
1395 bool JSObject::defaultHasInstance(ExecState* exec, JSValue value, JSValue proto)
1396 {
1397     if (!value.isObject())
1398         return false;
1399
1400     if (!proto.isObject()) {
1401         throwError(exec, createTypeError(exec, ASCIILiteral("instanceof called on an object with an invalid prototype property.")));
1402         return false;
1403     }
1404
1405     JSObject* object = asObject(value);
1406     while ((object = object->prototype().getObject())) {
1407         if (proto == object)
1408             return true;
1409     }
1410     return false;
1411 }
1412
1413 bool JSObject::getPropertySpecificValue(ExecState* exec, PropertyName propertyName, JSCell*& specificValue) const
1414 {
1415     unsigned attributes;
1416     if (isValidOffset(structure()->get(exec->vm(), propertyName, attributes, specificValue)))
1417         return true;
1418
1419     // This could be a function within the static table? - should probably
1420     // also look in the hash?  This currently should not be a problem, since
1421     // we've currently always call 'get' first, which should have populated
1422     // the normal storage.
1423     return false;
1424 }
1425
1426 void JSObject::getPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
1427 {
1428     propertyNames.setBaseObject(object);
1429     object->methodTable()->getOwnPropertyNames(object, exec, propertyNames, mode);
1430
1431     if (object->prototype().isNull())
1432         return;
1433
1434     JSObject* prototype = asObject(object->prototype());
1435     while(1) {
1436         if (prototype->structure()->typeInfo().overridesGetPropertyNames()) {
1437             prototype->methodTable()->getPropertyNames(prototype, exec, propertyNames, mode);
1438             break;
1439         }
1440         prototype->methodTable()->getOwnPropertyNames(prototype, exec, propertyNames, mode);
1441         JSValue nextProto = prototype->prototype();
1442         if (nextProto.isNull())
1443             break;
1444         prototype = asObject(nextProto);
1445     }
1446 }
1447
1448 void JSObject::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
1449 {
1450     // Add numeric properties first. That appears to be the accepted convention.
1451     // FIXME: Filling PropertyNameArray with an identifier for every integer
1452     // is incredibly inefficient for large arrays. We need a different approach,
1453     // which almost certainly means a different structure for PropertyNameArray.
1454     switch (object->structure()->indexingType()) {
1455     case ALL_BLANK_INDEXING_TYPES:
1456     case ALL_UNDECIDED_INDEXING_TYPES:
1457         break;
1458
1459     case ALL_INT32_INDEXING_TYPES:
1460     case ALL_CONTIGUOUS_INDEXING_TYPES: {
1461         Butterfly* butterfly = object->m_butterfly;
1462         unsigned usedLength = butterfly->publicLength();
1463         for (unsigned i = 0; i < usedLength; ++i) {
1464             if (!butterfly->contiguous()[i])
1465                 continue;
1466             propertyNames.add(Identifier::from(exec, i));
1467         }
1468         break;
1469     }
1470
1471     case ALL_DOUBLE_INDEXING_TYPES: {
1472         Butterfly* butterfly = object->m_butterfly;
1473         unsigned usedLength = butterfly->publicLength();
1474         for (unsigned i = 0; i < usedLength; ++i) {
1475             double value = butterfly->contiguousDouble()[i];
1476             if (value != value)
1477                 continue;
1478             propertyNames.add(Identifier::from(exec, i));
1479         }
1480         break;
1481     }
1482
1483     case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
1484         ArrayStorage* storage = object->m_butterfly->arrayStorage();
1485
1486         unsigned usedVectorLength = std::min(storage->length(), storage->vectorLength());
1487         for (unsigned i = 0; i < usedVectorLength; ++i) {
1488             if (storage->m_vector[i])
1489                 propertyNames.add(Identifier::from(exec, i));
1490         }
1491
1492         if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
1493             Vector<unsigned, 0, UnsafeVectorOverflow> keys;
1494             keys.reserveInitialCapacity(map->size());
1495
1496             SparseArrayValueMap::const_iterator end = map->end();
1497             for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
1498                 if (mode == IncludeDontEnumProperties || !(it->value.attributes & DontEnum))
1499                     keys.uncheckedAppend(static_cast<unsigned>(it->key));
1500             }
1501
1502             std::sort(keys.begin(), keys.end());
1503             for (unsigned i = 0; i < keys.size(); ++i)
1504                 propertyNames.add(Identifier::from(exec, keys[i]));
1505         }
1506         break;
1507     }
1508
1509     default:
1510         RELEASE_ASSERT_NOT_REACHED();
1511     }
1512
1513     object->methodTable()->getOwnNonIndexPropertyNames(object, exec, propertyNames, mode);
1514 }
1515
1516 void JSObject::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
1517 {
1518     getClassPropertyNames(exec, object->classInfo(), propertyNames, mode, object->staticFunctionsReified());
1519
1520     bool canCachePropertiesFromStructure = !propertyNames.size();
1521     object->structure()->getPropertyNamesFromStructure(exec->vm(), propertyNames, mode);
1522
1523     if (canCachePropertiesFromStructure)
1524         propertyNames.setNumCacheableSlotsForObject(object, propertyNames.size());
1525 }
1526
1527 double JSObject::toNumber(ExecState* exec) const
1528 {
1529     JSValue primitive = toPrimitive(exec, PreferNumber);
1530     if (exec->hadException()) // should be picked up soon in Nodes.cpp
1531         return 0.0;
1532     return primitive.toNumber(exec);
1533 }
1534
1535 JSString* JSObject::toString(ExecState* exec) const
1536 {
1537     JSValue primitive = toPrimitive(exec, PreferString);
1538     if (exec->hadException())
1539         return jsEmptyString(exec);
1540     return primitive.toString(exec);
1541 }
1542
1543 JSValue JSObject::toThis(JSCell* cell, ExecState*, ECMAMode)
1544 {
1545     return jsCast<JSObject*>(cell);
1546 }
1547
1548 void JSObject::seal(VM& vm)
1549 {
1550     if (isSealed(vm))
1551         return;
1552     preventExtensions(vm);
1553     setStructure(vm, Structure::sealTransition(vm, structure()));
1554 }
1555
1556 void JSObject::freeze(VM& vm)
1557 {
1558     if (isFrozen(vm))
1559         return;
1560     preventExtensions(vm);
1561     setStructure(vm, Structure::freezeTransition(vm, structure()));
1562 }
1563
1564 void JSObject::preventExtensions(VM& vm)
1565 {
1566     enterDictionaryIndexingMode(vm);
1567     if (isExtensible())
1568         setStructure(vm, Structure::preventExtensionsTransition(vm, structure()));
1569 }
1570
1571 // This presently will flatten to an uncachable dictionary; this is suitable
1572 // for use in delete, we may want to do something different elsewhere.
1573 void JSObject::reifyStaticFunctionsForDelete(ExecState* exec)
1574 {
1575     ASSERT(!staticFunctionsReified());
1576     VM& vm = exec->vm();
1577
1578     // If this object's ClassInfo has no static properties, then nothing to reify!
1579     // We can safely set the flag to avoid the expensive check again in the future.
1580     if (!classInfo()->hasStaticProperties()) {
1581         structure()->setStaticFunctionsReified();
1582         return;
1583     }
1584
1585     if (!structure()->isUncacheableDictionary())
1586         setStructure(vm, Structure::toUncacheableDictionaryTransition(vm, structure()));
1587
1588     for (const ClassInfo* info = classInfo(); info; info = info->parentClass) {
1589         const HashTable* hashTable = info->propHashTable(globalObject()->globalExec());
1590         if (!hashTable)
1591             continue;
1592         PropertySlot slot(this);
1593         for (HashTable::ConstIterator iter = hashTable->begin(vm); iter != hashTable->end(vm); ++iter) {
1594             if (iter->attributes() & Function)
1595                 setUpStaticFunctionSlot(globalObject()->globalExec(), *iter, this, Identifier(&vm, iter->key()), slot);
1596         }
1597     }
1598
1599     structure()->setStaticFunctionsReified();
1600 }
1601
1602 bool JSObject::removeDirect(VM& vm, PropertyName propertyName)
1603 {
1604     if (!isValidOffset(structure()->get(vm, propertyName)))
1605         return false;
1606
1607     PropertyOffset offset;
1608     if (structure()->isUncacheableDictionary()) {
1609         offset = structure()->removePropertyWithoutTransition(vm, propertyName);
1610         if (offset == invalidOffset)
1611             return false;
1612         putDirectUndefined(offset);
1613         return true;
1614     }
1615
1616     setStructure(vm, Structure::removePropertyTransition(vm, structure(), propertyName, offset));
1617     if (offset == invalidOffset)
1618         return false;
1619     putDirectUndefined(offset);
1620     return true;
1621 }
1622
1623 NEVER_INLINE void JSObject::fillGetterPropertySlot(PropertySlot& slot, JSValue getterSetter, unsigned attributes, PropertyOffset offset)
1624 {
1625     if (structure()->isDictionary()) {
1626         slot.setGetterSlot(this, attributes, jsCast<GetterSetter*>(getterSetter));
1627         return;
1628     }
1629
1630     slot.setCacheableGetterSlot(this, attributes, jsCast<GetterSetter*>(getterSetter), offset);
1631 }
1632
1633 void JSObject::putIndexedDescriptor(ExecState* exec, SparseArrayEntry* entryInMap, const PropertyDescriptor& descriptor, PropertyDescriptor& oldDescriptor)
1634 {
1635     if (descriptor.isDataDescriptor()) {
1636         if (descriptor.value())
1637             entryInMap->set(exec->vm(), this, descriptor.value());
1638         else if (oldDescriptor.isAccessorDescriptor())
1639             entryInMap->set(exec->vm(), this, jsUndefined());
1640         entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor) & ~Accessor;
1641         return;
1642     }
1643
1644     if (descriptor.isAccessorDescriptor()) {
1645         JSObject* getter = 0;
1646         if (descriptor.getterPresent())
1647             getter = descriptor.getterObject();
1648         else if (oldDescriptor.isAccessorDescriptor())
1649             getter = oldDescriptor.getterObject();
1650         JSObject* setter = 0;
1651         if (descriptor.setterPresent())
1652             setter = descriptor.setterObject();
1653         else if (oldDescriptor.isAccessorDescriptor())
1654             setter = oldDescriptor.setterObject();
1655
1656         GetterSetter* accessor = GetterSetter::create(exec);
1657         if (getter)
1658             accessor->setGetter(exec->vm(), getter);
1659         if (setter)
1660             accessor->setSetter(exec->vm(), setter);
1661
1662         entryInMap->set(exec->vm(), this, accessor);
1663         entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor) & ~ReadOnly;
1664         return;
1665     }
1666
1667     ASSERT(descriptor.isGenericDescriptor());
1668     entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor);
1669 }
1670
1671 // Defined in ES5.1 8.12.9
1672 bool JSObject::defineOwnIndexedProperty(ExecState* exec, unsigned index, const PropertyDescriptor& descriptor, bool throwException)
1673 {
1674     ASSERT(index <= MAX_ARRAY_INDEX);
1675
1676     if (!inSparseIndexingMode()) {
1677         // Fast case: we're putting a regular property to a regular array
1678         // FIXME: this will pessimistically assume that if attributes are missing then they'll default to false
1679         // however if the property currently exists missing attributes will override from their current 'true'
1680         // state (i.e. defineOwnProperty could be used to set a value without needing to entering 'SparseMode').
1681         if (!descriptor.attributes()) {
1682             ASSERT(!descriptor.isAccessorDescriptor());
1683             return putDirectIndex(exec, index, descriptor.value(), 0, throwException ? PutDirectIndexShouldThrow : PutDirectIndexShouldNotThrow);
1684         }
1685
1686         ensureArrayStorageExistsAndEnterDictionaryIndexingMode(exec->vm());
1687     }
1688
1689     if (descriptor.attributes() & (ReadOnly | Accessor))
1690         notifyPresenceOfIndexedAccessors(exec->vm());
1691
1692     SparseArrayValueMap* map = m_butterfly->arrayStorage()->m_sparseMap.get();
1693     RELEASE_ASSERT(map);
1694
1695     // 1. Let current be the result of calling the [[GetOwnProperty]] internal method of O with property name P.
1696     SparseArrayValueMap::AddResult result = map->add(this, index);
1697     SparseArrayEntry* entryInMap = &result.iterator->value;
1698
1699     // 2. Let extensible be the value of the [[Extensible]] internal property of O.
1700     // 3. If current is undefined and extensible is false, then Reject.
1701     // 4. If current is undefined and extensible is true, then
1702     if (result.isNewEntry) {
1703         if (!isExtensible()) {
1704             map->remove(result.iterator);
1705             return reject(exec, throwException, "Attempting to define property on object that is not extensible.");
1706         }
1707
1708         // 4.a. If IsGenericDescriptor(Desc) or IsDataDescriptor(Desc) is true, then create an own data property
1709         // named P of object O whose [[Value]], [[Writable]], [[Enumerable]] and [[Configurable]] attribute values
1710         // are described by Desc. If the value of an attribute field of Desc is absent, the attribute of the newly
1711         // created property is set to its default value.
1712         // 4.b. Else, Desc must be an accessor Property Descriptor so, create an own accessor property named P of
1713         // object O whose [[Get]], [[Set]], [[Enumerable]] and [[Configurable]] attribute values are described by
1714         // Desc. If the value of an attribute field of Desc is absent, the attribute of the newly created property
1715         // is set to its default value.
1716         // 4.c. Return true.
1717
1718         PropertyDescriptor defaults;
1719         entryInMap->setWithoutWriteBarrier(jsUndefined());
1720         entryInMap->attributes = DontDelete | DontEnum | ReadOnly;
1721         entryInMap->get(defaults);
1722
1723         putIndexedDescriptor(exec, entryInMap, descriptor, defaults);
1724         if (index >= m_butterfly->arrayStorage()->length())
1725             m_butterfly->arrayStorage()->setLength(index + 1);
1726         return true;
1727     }
1728
1729     // 5. Return true, if every field in Desc is absent.
1730     // 6. Return true, if every field in Desc also occurs in current and the value of every field in Desc is the same value as the corresponding field in current when compared using the SameValue algorithm (9.12).
1731     PropertyDescriptor current;
1732     entryInMap->get(current);
1733     if (descriptor.isEmpty() || descriptor.equalTo(exec, current))
1734         return true;
1735
1736     // 7. If the [[Configurable]] field of current is false then
1737     if (!current.configurable()) {
1738         // 7.a. Reject, if the [[Configurable]] field of Desc is true.
1739         if (descriptor.configurablePresent() && descriptor.configurable())
1740             return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property.");
1741         // 7.b. Reject, if the [[Enumerable]] field of Desc is present and the [[Enumerable]] fields of current and Desc are the Boolean negation of each other.
1742         if (descriptor.enumerablePresent() && current.enumerable() != descriptor.enumerable())
1743             return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property.");
1744     }
1745
1746     // 8. If IsGenericDescriptor(Desc) is true, then no further validation is required.
1747     if (!descriptor.isGenericDescriptor()) {
1748         // 9. Else, if IsDataDescriptor(current) and IsDataDescriptor(Desc) have different results, then
1749         if (current.isDataDescriptor() != descriptor.isDataDescriptor()) {
1750             // 9.a. Reject, if the [[Configurable]] field of current is false.
1751             if (!current.configurable())
1752                 return reject(exec, throwException, "Attempting to change access mechanism for an unconfigurable property.");
1753             // 9.b. If IsDataDescriptor(current) is true, then convert the property named P of object O from a
1754             // data property to an accessor property. Preserve the existing values of the converted property's
1755             // [[Configurable]] and [[Enumerable]] attributes and set the rest of the property's attributes to
1756             // their default values.
1757             // 9.c. Else, convert the property named P of object O from an accessor property to a data property.
1758             // Preserve the existing values of the converted property's [[Configurable]] and [[Enumerable]]
1759             // attributes and set the rest of the property's attributes to their default values.
1760         } else if (current.isDataDescriptor() && descriptor.isDataDescriptor()) {
1761             // 10. Else, if IsDataDescriptor(current) and IsDataDescriptor(Desc) are both true, then
1762             // 10.a. If the [[Configurable]] field of current is false, then
1763             if (!current.configurable() && !current.writable()) {
1764                 // 10.a.i. Reject, if the [[Writable]] field of current is false and the [[Writable]] field of Desc is true.
1765                 if (descriptor.writable())
1766                     return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property.");
1767                 // 10.a.ii. If the [[Writable]] field of current is false, then
1768                 // 10.a.ii.1. Reject, if the [[Value]] field of Desc is present and SameValue(Desc.[[Value]], current.[[Value]]) is false.
1769                 if (descriptor.value() && !sameValue(exec, descriptor.value(), current.value()))
1770                     return reject(exec, throwException, "Attempting to change value of a readonly property.");
1771             }
1772             // 10.b. else, the [[Configurable]] field of current is true, so any change is acceptable.
1773         } else {
1774             ASSERT(current.isAccessorDescriptor() && current.getterPresent() && current.setterPresent());
1775             // 11. Else, IsAccessorDescriptor(current) and IsAccessorDescriptor(Desc) are both true so, if the [[Configurable]] field of current is false, then
1776             if (!current.configurable()) {
1777                 // 11.i. Reject, if the [[Set]] field of Desc is present and SameValue(Desc.[[Set]], current.[[Set]]) is false.
1778                 if (descriptor.setterPresent() && descriptor.setter() != current.setter())
1779                     return reject(exec, throwException, "Attempting to change the setter of an unconfigurable property.");
1780                 // 11.ii. Reject, if the [[Get]] field of Desc is present and SameValue(Desc.[[Get]], current.[[Get]]) is false.
1781                 if (descriptor.getterPresent() && descriptor.getter() != current.getter())
1782                     return reject(exec, throwException, "Attempting to change the getter of an unconfigurable property.");
1783             }
1784         }
1785     }
1786
1787     // 12. For each attribute field of Desc that is present, set the correspondingly named attribute of the property named P of object O to the value of the field.
1788     putIndexedDescriptor(exec, entryInMap, descriptor, current);
1789     // 13. Return true.
1790     return true;
1791 }
1792
1793 SparseArrayValueMap* JSObject::allocateSparseIndexMap(VM& vm)
1794 {
1795     SparseArrayValueMap* result = SparseArrayValueMap::create(vm);
1796     arrayStorage()->m_sparseMap.set(vm, this, result);
1797     return result;
1798 }
1799
1800 void JSObject::deallocateSparseIndexMap()
1801 {
1802     if (ArrayStorage* arrayStorage = arrayStorageOrNull())
1803         arrayStorage->m_sparseMap.clear();
1804 }
1805
1806 bool JSObject::attemptToInterceptPutByIndexOnHoleForPrototype(ExecState* exec, JSValue thisValue, unsigned i, JSValue value, bool shouldThrow)
1807 {
1808     for (JSObject* current = this; ;) {
1809         // This has the same behavior with respect to prototypes as JSObject::put(). It only
1810         // allows a prototype to intercept a put if (a) the prototype declares the property
1811         // we're after rather than intercepting it via an override of JSObject::put(), and
1812         // (b) that property is declared as ReadOnly or Accessor.
1813
1814         ArrayStorage* storage = current->arrayStorageOrNull();
1815         if (storage && storage->m_sparseMap) {
1816             SparseArrayValueMap::iterator iter = storage->m_sparseMap->find(i);
1817             if (iter != storage->m_sparseMap->notFound() && (iter->value.attributes & (Accessor | ReadOnly))) {
1818                 iter->value.put(exec, thisValue, storage->m_sparseMap.get(), value, shouldThrow);
1819                 return true;
1820             }
1821         }
1822
1823         JSValue prototypeValue = current->prototype();
1824         if (prototypeValue.isNull())
1825             return false;
1826
1827         current = asObject(prototypeValue);
1828     }
1829 }
1830
1831 bool JSObject::attemptToInterceptPutByIndexOnHole(ExecState* exec, unsigned i, JSValue value, bool shouldThrow)
1832 {
1833     JSValue prototypeValue = prototype();
1834     if (prototypeValue.isNull())
1835         return false;
1836
1837     return asObject(prototypeValue)->attemptToInterceptPutByIndexOnHoleForPrototype(exec, this, i, value, shouldThrow);
1838 }
1839
1840 template<IndexingType indexingShape>
1841 void JSObject::putByIndexBeyondVectorLengthWithoutAttributes(ExecState* exec, unsigned i, JSValue value)
1842 {
1843     ASSERT((structure()->indexingType() & IndexingShapeMask) == indexingShape);
1844     ASSERT(!indexingShouldBeSparse());
1845
1846     // For us to get here, the index is either greater than the public length, or greater than
1847     // or equal to the vector length.
1848     ASSERT(i >= m_butterfly->vectorLength());
1849
1850     VM& vm = exec->vm();
1851
1852     if (i >= MAX_ARRAY_INDEX - 1
1853         || (i >= MIN_SPARSE_ARRAY_INDEX
1854             && !isDenseEnoughForVector(i, countElements<indexingShape>(m_butterfly)))
1855         || indexIsSufficientlyBeyondLengthForSparseMap(i, m_butterfly->vectorLength())) {
1856         ASSERT(i <= MAX_ARRAY_INDEX);
1857         ensureArrayStorageSlow(vm);
1858         SparseArrayValueMap* map = allocateSparseIndexMap(vm);
1859         map->putEntry(exec, this, i, value, false);
1860         ASSERT(i >= arrayStorage()->length());
1861         arrayStorage()->setLength(i + 1);
1862         return;
1863     }
1864
1865     ensureLength(vm, i + 1);
1866
1867     RELEASE_ASSERT(i < m_butterfly->vectorLength());
1868     switch (indexingShape) {
1869     case Int32Shape:
1870         ASSERT(value.isInt32());
1871         m_butterfly->contiguousInt32()[i].setWithoutWriteBarrier(value);
1872         break;
1873
1874     case DoubleShape: {
1875         ASSERT(value.isNumber());
1876         double valueAsDouble = value.asNumber();
1877         ASSERT(valueAsDouble == valueAsDouble);
1878         m_butterfly->contiguousDouble()[i] = valueAsDouble;
1879         break;
1880     }
1881
1882     case ContiguousShape:
1883         m_butterfly->contiguous()[i].set(vm, this, value);
1884         break;
1885
1886     default:
1887         CRASH();
1888     }
1889 }
1890
1891 void JSObject::putByIndexBeyondVectorLengthWithArrayStorage(ExecState* exec, unsigned i, JSValue value, bool shouldThrow, ArrayStorage* storage)
1892 {
1893     VM& vm = exec->vm();
1894
1895     // i should be a valid array index that is outside of the current vector.
1896     ASSERT(i <= MAX_ARRAY_INDEX);
1897     ASSERT(i >= storage->vectorLength());
1898
1899     SparseArrayValueMap* map = storage->m_sparseMap.get();
1900
1901     // First, handle cases where we don't currently have a sparse map.
1902     if (LIKELY(!map)) {
1903         // If the array is not extensible, we should have entered dictionary mode, and created the sparse map.
1904         ASSERT(isExtensible());
1905
1906         // Update m_length if necessary.
1907         if (i >= storage->length())
1908             storage->setLength(i + 1);
1909
1910         // Check that it is sensible to still be using a vector, and then try to grow the vector.
1911         if (LIKELY(!indexIsSufficientlyBeyondLengthForSparseMap(i, storage->vectorLength())
1912             && isDenseEnoughForVector(i, storage->m_numValuesInVector)
1913             && increaseVectorLength(vm, i + 1))) {
1914             // success! - reread m_storage since it has likely been reallocated, and store to the vector.
1915             storage = arrayStorage();
1916             storage->m_vector[i].set(vm, this, value);
1917             ++storage->m_numValuesInVector;
1918             return;
1919         }
1920         // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
1921         map = allocateSparseIndexMap(exec->vm());
1922         map->putEntry(exec, this, i, value, shouldThrow);
1923         return;
1924     }
1925
1926     // Update m_length if necessary.
1927     unsigned length = storage->length();
1928     if (i >= length) {
1929         // Prohibit growing the array if length is not writable.
1930         if (map->lengthIsReadOnly() || !isExtensible()) {
1931             if (shouldThrow)
1932                 throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
1933             return;
1934         }
1935         length = i + 1;
1936         storage->setLength(length);
1937     }
1938
1939     // We are currently using a map - check whether we still want to be doing so.
1940     // We will continue  to use a sparse map if SparseMode is set, a vector would be too sparse, or if allocation fails.
1941     unsigned numValuesInArray = storage->m_numValuesInVector + map->size();
1942     if (map->sparseMode() || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(exec->vm(), length)) {
1943         map->putEntry(exec, this, i, value, shouldThrow);
1944         return;
1945     }
1946
1947     // Reread m_storage after increaseVectorLength, update m_numValuesInVector.
1948     storage = arrayStorage();
1949     storage->m_numValuesInVector = numValuesInArray;
1950
1951     // Copy all values from the map into the vector, and delete the map.
1952     WriteBarrier<Unknown>* vector = storage->m_vector;
1953     SparseArrayValueMap::const_iterator end = map->end();
1954     for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
1955         vector[it->key].set(vm, this, it->value.getNonSparseMode());
1956     deallocateSparseIndexMap();
1957
1958     // Store the new property into the vector.
1959     WriteBarrier<Unknown>& valueSlot = vector[i];
1960     if (!valueSlot)
1961         ++storage->m_numValuesInVector;
1962     valueSlot.set(vm, this, value);
1963 }
1964
1965 void JSObject::putByIndexBeyondVectorLength(ExecState* exec, unsigned i, JSValue value, bool shouldThrow)
1966 {
1967     VM& vm = exec->vm();
1968
1969     // i should be a valid array index that is outside of the current vector.
1970     ASSERT(i <= MAX_ARRAY_INDEX);
1971
1972     switch (structure()->indexingType()) {
1973     case ALL_BLANK_INDEXING_TYPES: {
1974         if (indexingShouldBeSparse()) {
1975             putByIndexBeyondVectorLengthWithArrayStorage(
1976                 exec, i, value, shouldThrow,
1977                 ensureArrayStorageExistsAndEnterDictionaryIndexingMode(vm));
1978             break;
1979         }
1980         if (indexIsSufficientlyBeyondLengthForSparseMap(i, 0) || i >= MIN_SPARSE_ARRAY_INDEX) {
1981             putByIndexBeyondVectorLengthWithArrayStorage(
1982                 exec, i, value, shouldThrow, createArrayStorage(vm, 0, 0));
1983             break;
1984         }
1985         if (structure()->needsSlowPutIndexing()) {
1986             ArrayStorage* storage = createArrayStorage(vm, i + 1, getNewVectorLength(0, 0, i + 1));
1987             storage->m_vector[i].set(vm, this, value);
1988             storage->m_numValuesInVector++;
1989             break;
1990         }
1991
1992         createInitialContiguous(vm, i + 1)[i].set(vm, this, value);
1993         break;
1994     }
1995
1996     case ALL_UNDECIDED_INDEXING_TYPES: {
1997         CRASH();
1998         break;
1999     }
2000
2001     case ALL_INT32_INDEXING_TYPES: {
2002         putByIndexBeyondVectorLengthWithoutAttributes<Int32Shape>(exec, i, value);
2003         break;
2004     }
2005
2006     case ALL_DOUBLE_INDEXING_TYPES: {
2007         putByIndexBeyondVectorLengthWithoutAttributes<DoubleShape>(exec, i, value);
2008         break;
2009     }
2010
2011     case ALL_CONTIGUOUS_INDEXING_TYPES: {
2012         putByIndexBeyondVectorLengthWithoutAttributes<ContiguousShape>(exec, i, value);
2013         break;
2014     }
2015
2016     case NonArrayWithSlowPutArrayStorage:
2017     case ArrayWithSlowPutArrayStorage: {
2018         // No own property present in the vector, but there might be in the sparse map!
2019         SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get();
2020         if (!(map && map->contains(i)) && attemptToInterceptPutByIndexOnHole(exec, i, value, shouldThrow))
2021             return;
2022         // Otherwise, fall though.
2023     }
2024
2025     case NonArrayWithArrayStorage:
2026     case ArrayWithArrayStorage:
2027         putByIndexBeyondVectorLengthWithArrayStorage(exec, i, value, shouldThrow, arrayStorage());
2028         break;
2029
2030     default:
2031         RELEASE_ASSERT_NOT_REACHED();
2032     }
2033 }
2034
2035 bool JSObject::putDirectIndexBeyondVectorLengthWithArrayStorage(ExecState* exec, unsigned i, JSValue value, unsigned attributes, PutDirectIndexMode mode, ArrayStorage* storage)
2036 {
2037     VM& vm = exec->vm();
2038
2039     // i should be a valid array index that is outside of the current vector.
2040     ASSERT(hasArrayStorage(structure()->indexingType()));
2041     ASSERT(arrayStorage() == storage);
2042     ASSERT(i >= storage->vectorLength() || attributes);
2043     ASSERT(i <= MAX_ARRAY_INDEX);
2044
2045     SparseArrayValueMap* map = storage->m_sparseMap.get();
2046
2047     // First, handle cases where we don't currently have a sparse map.
2048     if (LIKELY(!map)) {
2049         // If the array is not extensible, we should have entered dictionary mode, and created the spare map.
2050         ASSERT(isExtensible());
2051
2052         // Update m_length if necessary.
2053         if (i >= storage->length())
2054             storage->setLength(i + 1);
2055
2056         // Check that it is sensible to still be using a vector, and then try to grow the vector.
2057         if (LIKELY(
2058                 !attributes
2059                 && (isDenseEnoughForVector(i, storage->m_numValuesInVector))
2060                 && !indexIsSufficientlyBeyondLengthForSparseMap(i, storage->vectorLength()))
2061                 && increaseVectorLength(vm, i + 1)) {
2062             // success! - reread m_storage since it has likely been reallocated, and store to the vector.
2063             storage = arrayStorage();
2064             storage->m_vector[i].set(vm, this, value);
2065             ++storage->m_numValuesInVector;
2066             return true;
2067         }
2068         // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
2069         map = allocateSparseIndexMap(exec->vm());
2070         return map->putDirect(exec, this, i, value, attributes, mode);
2071     }
2072
2073     // Update m_length if necessary.
2074     unsigned length = storage->length();
2075     if (i >= length) {
2076         if (mode != PutDirectIndexLikePutDirect) {
2077             // Prohibit growing the array if length is not writable.
2078             if (map->lengthIsReadOnly())
2079                 return reject(exec, mode == PutDirectIndexShouldThrow, StrictModeReadonlyPropertyWriteError);
2080             if (!isExtensible())
2081                 return reject(exec, mode == PutDirectIndexShouldThrow, "Attempting to define property on object that is not extensible.");
2082         }
2083         length = i + 1;
2084         storage->setLength(length);
2085     }
2086
2087     // We are currently using a map - check whether we still want to be doing so.
2088     // We will continue  to use a sparse map if SparseMode is set, a vector would be too sparse, or if allocation fails.
2089     unsigned numValuesInArray = storage->m_numValuesInVector + map->size();
2090     if (map->sparseMode() || attributes || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(exec->vm(), length))
2091         return map->putDirect(exec, this, i, value, attributes, mode);
2092
2093     // Reread m_storage after increaseVectorLength, update m_numValuesInVector.
2094     storage = arrayStorage();
2095     storage->m_numValuesInVector = numValuesInArray;
2096
2097     // Copy all values from the map into the vector, and delete the map.
2098     WriteBarrier<Unknown>* vector = storage->m_vector;
2099     SparseArrayValueMap::const_iterator end = map->end();
2100     for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
2101         vector[it->key].set(vm, this, it->value.getNonSparseMode());
2102     deallocateSparseIndexMap();
2103
2104     // Store the new property into the vector.
2105     WriteBarrier<Unknown>& valueSlot = vector[i];
2106     if (!valueSlot)
2107         ++storage->m_numValuesInVector;
2108     valueSlot.set(vm, this, value);
2109     return true;
2110 }
2111
2112 bool JSObject::putDirectIndexBeyondVectorLength(ExecState* exec, unsigned i, JSValue value, unsigned attributes, PutDirectIndexMode mode)
2113 {
2114     VM& vm = exec->vm();
2115
2116     // i should be a valid array index that is outside of the current vector.
2117     ASSERT(i <= MAX_ARRAY_INDEX);
2118
2119     if (attributes & (ReadOnly | Accessor))
2120         notifyPresenceOfIndexedAccessors(vm);
2121
2122     switch (structure()->indexingType()) {
2123     case ALL_BLANK_INDEXING_TYPES: {
2124         if (indexingShouldBeSparse() || attributes) {
2125             return putDirectIndexBeyondVectorLengthWithArrayStorage(
2126                 exec, i, value, attributes, mode,
2127                 ensureArrayStorageExistsAndEnterDictionaryIndexingMode(vm));
2128         }
2129         if (i >= MIN_SPARSE_ARRAY_INDEX) {
2130             return putDirectIndexBeyondVectorLengthWithArrayStorage(
2131                 exec, i, value, attributes, mode, createArrayStorage(vm, 0, 0));
2132         }
2133         if (structure()->needsSlowPutIndexing()) {
2134             ArrayStorage* storage = createArrayStorage(vm, i + 1, getNewVectorLength(0, 0, i + 1));
2135             storage->m_vector[i].set(vm, this, value);
2136             storage->m_numValuesInVector++;
2137             return true;
2138         }
2139
2140         createInitialContiguous(vm, i + 1)[i].set(vm, this, value);
2141         return true;
2142     }
2143
2144     case ALL_UNDECIDED_INDEXING_TYPES: {
2145         convertUndecidedForValue(exec->vm(), value);
2146         // Reloop.
2147         return putDirectIndex(exec, i, value, attributes, mode);
2148     }
2149
2150     case ALL_INT32_INDEXING_TYPES: {
2151         if (attributes & (ReadOnly | Accessor)) {
2152             return putDirectIndexBeyondVectorLengthWithArrayStorage(
2153                 exec, i, value, attributes, mode, convertInt32ToArrayStorage(vm));
2154         }
2155         if (!value.isInt32()) {
2156             convertInt32ForValue(vm, value);
2157             return putDirectIndexBeyondVectorLength(exec, i, value, attributes, mode);
2158         }
2159         putByIndexBeyondVectorLengthWithoutAttributes<Int32Shape>(exec, i, value);
2160         return true;
2161     }
2162
2163     case ALL_DOUBLE_INDEXING_TYPES: {
2164         if (attributes & (ReadOnly | Accessor)) {
2165             return putDirectIndexBeyondVectorLengthWithArrayStorage(
2166                 exec, i, value, attributes, mode, convertDoubleToArrayStorage(vm));
2167         }
2168         if (!value.isNumber()) {
2169             convertDoubleToContiguous(vm);
2170             return putDirectIndexBeyondVectorLength(exec, i, value, attributes, mode);
2171         }
2172         double valueAsDouble = value.asNumber();
2173         if (valueAsDouble != valueAsDouble) {
2174             convertDoubleToContiguous(vm);
2175             return putDirectIndexBeyondVectorLength(exec, i, value, attributes, mode);
2176         }
2177         putByIndexBeyondVectorLengthWithoutAttributes<DoubleShape>(exec, i, value);
2178         return true;
2179     }
2180
2181     case ALL_CONTIGUOUS_INDEXING_TYPES: {
2182         if (attributes & (ReadOnly | Accessor)) {
2183             return putDirectIndexBeyondVectorLengthWithArrayStorage(
2184                 exec, i, value, attributes, mode, convertContiguousToArrayStorage(vm));
2185         }
2186         putByIndexBeyondVectorLengthWithoutAttributes<ContiguousShape>(exec, i, value);
2187         return true;
2188     }
2189
2190     case ALL_ARRAY_STORAGE_INDEXING_TYPES:
2191         return putDirectIndexBeyondVectorLengthWithArrayStorage(exec, i, value, attributes, mode, arrayStorage());
2192
2193     default:
2194         RELEASE_ASSERT_NOT_REACHED();
2195         return false;
2196     }
2197 }
2198
2199 void JSObject::putDirectNativeFunction(ExecState* exec, JSGlobalObject* globalObject, const PropertyName& propertyName, unsigned functionLength, NativeFunction nativeFunction, Intrinsic intrinsic, unsigned attributes)
2200 {
2201     StringImpl* name = propertyName.publicName();
2202     ASSERT(name);
2203
2204     JSFunction* function = JSFunction::create(exec, globalObject, functionLength, name, nativeFunction, intrinsic);
2205     putDirect(exec->vm(), propertyName, function, attributes);
2206 }
2207
2208 void JSObject::putDirectNativeFunctionWithoutTransition(ExecState* exec, JSGlobalObject* globalObject, const PropertyName& propertyName, unsigned functionLength, NativeFunction nativeFunction, Intrinsic intrinsic, unsigned attributes)
2209 {
2210     StringImpl* name = propertyName.publicName();
2211     ASSERT(name);
2212
2213     JSFunction* function = JSFunction::create(exec, globalObject, functionLength, name, nativeFunction, intrinsic);
2214     putDirectWithoutTransition(exec->vm(), propertyName, function, attributes);
2215 }
2216
2217 ALWAYS_INLINE unsigned JSObject::getNewVectorLength(unsigned currentVectorLength, unsigned currentLength, unsigned desiredLength)
2218 {
2219     ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);
2220
2221     unsigned increasedLength;
2222     unsigned maxInitLength = std::min(currentLength, 100000U);
2223
2224     if (desiredLength < maxInitLength)
2225         increasedLength = maxInitLength;
2226     else if (!currentVectorLength)
2227         increasedLength = std::max(desiredLength, lastArraySize);
2228     else {
2229         increasedLength = timesThreePlusOneDividedByTwo(desiredLength);
2230     }
2231
2232     ASSERT(increasedLength >= desiredLength);
2233
2234     lastArraySize = std::min(increasedLength, FIRST_VECTOR_GROW);
2235
2236     return std::min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
2237 }
2238
2239 ALWAYS_INLINE unsigned JSObject::getNewVectorLength(unsigned desiredLength)
2240 {
2241     unsigned vectorLength;
2242     unsigned length;
2243
2244     if (hasIndexedProperties(structure()->indexingType())) {
2245         vectorLength = m_butterfly->vectorLength();
2246         length = m_butterfly->publicLength();
2247     } else {
2248         vectorLength = 0;
2249         length = 0;
2250     }
2251
2252     return getNewVectorLength(vectorLength, length, desiredLength);
2253 }
2254
2255 template<IndexingType indexingShape>
2256 unsigned JSObject::countElements(Butterfly* butterfly)
2257 {
2258     unsigned numValues = 0;
2259     for (unsigned i = butterfly->publicLength(); i--;) {
2260         switch (indexingShape) {
2261         case Int32Shape:
2262         case ContiguousShape:
2263             if (butterfly->contiguous()[i])
2264                 numValues++;
2265             break;
2266
2267         case DoubleShape: {
2268             double value = butterfly->contiguousDouble()[i];
2269             if (value == value)
2270                 numValues++;
2271             break;
2272         }
2273
2274         default:
2275             CRASH();
2276         }
2277     }
2278     return numValues;
2279 }
2280
2281 unsigned JSObject::countElements()
2282 {
2283     switch (structure()->indexingType()) {
2284     case ALL_BLANK_INDEXING_TYPES:
2285     case ALL_UNDECIDED_INDEXING_TYPES:
2286         return 0;
2287
2288     case ALL_INT32_INDEXING_TYPES:
2289         return countElements<Int32Shape>(m_butterfly);
2290
2291     case ALL_DOUBLE_INDEXING_TYPES:
2292         return countElements<DoubleShape>(m_butterfly);
2293
2294     case ALL_CONTIGUOUS_INDEXING_TYPES:
2295         return countElements<ContiguousShape>(m_butterfly);
2296
2297     default:
2298         CRASH();
2299         return 0;
2300     }
2301 }
2302
2303 bool JSObject::increaseVectorLength(VM& vm, unsigned newLength)
2304 {
2305     // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
2306     // to the vector. Callers have to account for that, because they can do it more efficiently.
2307     if (newLength > MAX_STORAGE_VECTOR_LENGTH)
2308         return false;
2309
2310     ArrayStorage* storage = arrayStorage();
2311
2312     if (newLength >= MIN_SPARSE_ARRAY_INDEX
2313         && !isDenseEnoughForVector(newLength, storage->m_numValuesInVector))
2314         return false;
2315
2316     unsigned indexBias = storage->m_indexBias;
2317     unsigned vectorLength = storage->vectorLength();
2318     ASSERT(newLength > vectorLength);
2319     unsigned newVectorLength = getNewVectorLength(newLength);
2320
2321     // Fast case - there is no precapacity. In these cases a realloc makes sense.
2322     if (LIKELY(!indexBias)) {
2323         DeferGC deferGC(vm.heap);
2324         Butterfly* newButterfly = storage->butterfly()->growArrayRight(
2325             vm, this, structure(), structure()->outOfLineCapacity(), true,
2326             ArrayStorage::sizeFor(vectorLength), ArrayStorage::sizeFor(newVectorLength));
2327         if (!newButterfly)
2328             return false;
2329         m_butterfly = newButterfly;
2330         newButterfly->arrayStorage()->setVectorLength(newVectorLength);
2331         return true;
2332     }
2333
2334     // Remove some, but not all of the precapacity. Atomic decay, & capped to not overflow array length.
2335     DeferGC deferGC(vm.heap);
2336     unsigned newIndexBias = std::min(indexBias >> 1, MAX_STORAGE_VECTOR_LENGTH - newVectorLength);
2337     Butterfly* newButterfly = storage->butterfly()->resizeArray(
2338         vm, this,
2339         structure()->outOfLineCapacity(), true, ArrayStorage::sizeFor(vectorLength),
2340         newIndexBias, true, ArrayStorage::sizeFor(newVectorLength));
2341     if (!newButterfly)
2342         return false;
2343
2344     m_butterfly = newButterfly;
2345     newButterfly->arrayStorage()->setVectorLength(newVectorLength);
2346     newButterfly->arrayStorage()->m_indexBias = newIndexBias;
2347     return true;
2348 }
2349
2350 void JSObject::ensureLengthSlow(VM& vm, unsigned length)
2351 {
2352     ASSERT(length < MAX_ARRAY_INDEX);
2353     ASSERT(hasContiguous(structure()->indexingType()) || hasInt32(structure()->indexingType()) || hasDouble(structure()->indexingType()) || hasUndecided(structure()->indexingType()));
2354     ASSERT(length > m_butterfly->vectorLength());
2355
2356     unsigned newVectorLength = std::min(
2357         length << 1,
2358         MAX_STORAGE_VECTOR_LENGTH);
2359     unsigned oldVectorLength = m_butterfly->vectorLength();
2360     DeferGC deferGC(vm.heap);
2361     m_butterfly = m_butterfly->growArrayRight(
2362         vm, this, structure(), structure()->outOfLineCapacity(), true,
2363         oldVectorLength * sizeof(EncodedJSValue),
2364         newVectorLength * sizeof(EncodedJSValue));
2365     if (hasDouble(structure()->indexingType())) {
2366         for (unsigned i = oldVectorLength; i < newVectorLength; ++i)
2367             m_butterfly->contiguousDouble().data()[i] = QNaN;
2368     }
2369     m_butterfly->setVectorLength(newVectorLength);
2370 }
2371
2372 Butterfly* JSObject::growOutOfLineStorage(VM& vm, size_t oldSize, size_t newSize)
2373 {
2374     ASSERT(newSize > oldSize);
2375
2376     // It's important that this function not rely on structure(), for the property
2377     // capacity, since we might have already mutated the structure in-place.
2378
2379     return m_butterfly->growPropertyStorage(vm, this, structure(), oldSize, newSize);
2380 }
2381
2382 bool JSObject::getOwnPropertyDescriptor(ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor)
2383 {
2384     JSC::PropertySlot slot(this);
2385     if (!methodTable()->getOwnPropertySlot(this, exec, propertyName, slot))
2386         return false;
2387     /* Workaround, JSDOMWindow::getOwnPropertySlot searches the prototype chain. :-( */
2388     if (slot.slotBase() != this && slot.slotBase() && slot.slotBase()->methodTable()->toThis(slot.slotBase(), exec, NotStrictMode) != this)
2389         return false;
2390     if (slot.isAccessor())
2391         descriptor.setAccessorDescriptor(slot.getterSetter(), slot.attributes());
2392     else
2393         descriptor.setDescriptor(slot.getValue(exec, propertyName), slot.attributes());
2394     return true;
2395 }
2396
2397 static bool putDescriptor(ExecState* exec, JSObject* target, PropertyName propertyName, const PropertyDescriptor& descriptor, unsigned attributes, const PropertyDescriptor& oldDescriptor)
2398 {
2399     if (descriptor.isGenericDescriptor() || descriptor.isDataDescriptor()) {
2400         if (descriptor.isGenericDescriptor() && oldDescriptor.isAccessorDescriptor()) {
2401             GetterSetter* accessor = GetterSetter::create(exec);
2402             if (oldDescriptor.getterPresent())
2403                 accessor->setGetter(exec->vm(), oldDescriptor.getterObject());
2404             if (oldDescriptor.setterPresent())
2405                 accessor->setSetter(exec->vm(), oldDescriptor.setterObject());
2406             target->putDirectAccessor(exec, propertyName, accessor, attributes | Accessor);
2407             return true;
2408         }
2409         JSValue newValue = jsUndefined();
2410         if (descriptor.value())
2411             newValue = descriptor.value();
2412         else if (oldDescriptor.value())
2413             newValue = oldDescriptor.value();
2414         target->putDirect(exec->vm(), propertyName, newValue, attributes & ~Accessor);
2415         if (attributes & ReadOnly)
2416             target->structure()->setContainsReadOnlyProperties();
2417         return true;
2418     }
2419     attributes &= ~ReadOnly;
2420     GetterSetter* accessor = GetterSetter::create(exec);
2421
2422     if (descriptor.getterPresent())
2423         accessor->setGetter(exec->vm(), descriptor.getterObject());
2424     else if (oldDescriptor.getterPresent())
2425         accessor->setGetter(exec->vm(), oldDescriptor.getterObject());
2426     if (descriptor.setterPresent())
2427         accessor->setSetter(exec->vm(), descriptor.setterObject());
2428     else if (oldDescriptor.setterPresent())
2429         accessor->setSetter(exec->vm(), oldDescriptor.setterObject());
2430
2431     target->putDirectAccessor(exec, propertyName, accessor, attributes | Accessor);
2432     return true;
2433 }
2434
2435 void JSObject::putDirectMayBeIndex(ExecState* exec, PropertyName propertyName, JSValue value)
2436 {
2437     unsigned asIndex = propertyName.asIndex();
2438     if (asIndex == PropertyName::NotAnIndex)
2439         putDirect(exec->vm(), propertyName, value);
2440     else
2441         putDirectIndex(exec, asIndex, value);
2442 }
2443
2444 class DefineOwnPropertyScope {
2445 public:
2446     DefineOwnPropertyScope(ExecState* exec)
2447         : m_vm(exec->vm())
2448     {
2449         m_vm.setInDefineOwnProperty(true);
2450     }
2451
2452     ~DefineOwnPropertyScope()
2453     {
2454         m_vm.setInDefineOwnProperty(false);
2455     }
2456
2457 private:
2458     VM& m_vm;
2459 };
2460
2461 bool JSObject::defineOwnNonIndexProperty(ExecState* exec, PropertyName propertyName, const PropertyDescriptor& descriptor, bool throwException)
2462 {
2463     // Track on the globaldata that we're in define property.
2464     // Currently DefineOwnProperty uses delete to remove properties when they are being replaced
2465     // (particularly when changing attributes), however delete won't allow non-configurable (i.e.
2466     // DontDelete) properties to be deleted. For now, we can use this flag to make this work.
2467     DefineOwnPropertyScope scope(exec);
2468
2469     // If we have a new property we can just put it on normally
2470     PropertyDescriptor current;
2471     if (!getOwnPropertyDescriptor(exec, propertyName, current)) {
2472         // unless extensions are prevented!
2473         if (!isExtensible()) {
2474             if (throwException)
2475                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to define property on object that is not extensible.")));
2476             return false;
2477         }
2478         PropertyDescriptor oldDescriptor;
2479         oldDescriptor.setValue(jsUndefined());
2480         return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributes(), oldDescriptor);
2481     }
2482
2483     if (descriptor.isEmpty())
2484         return true;
2485
2486     if (current.equalTo(exec, descriptor))
2487         return true;
2488
2489     // Filter out invalid changes
2490     if (!current.configurable()) {
2491         if (descriptor.configurable()) {
2492             if (throwException)
2493                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to configurable attribute of unconfigurable property.")));
2494             return false;
2495         }
2496         if (descriptor.enumerablePresent() && descriptor.enumerable() != current.enumerable()) {
2497             if (throwException)
2498                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change enumerable attribute of unconfigurable property.")));
2499             return false;
2500         }
2501     }
2502
2503     // A generic descriptor is simply changing the attributes of an existing property
2504     if (descriptor.isGenericDescriptor()) {
2505         if (!current.attributesEqual(descriptor)) {
2506             methodTable()->deleteProperty(this, exec, propertyName);
2507             return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
2508         }
2509         return true;
2510     }
2511
2512     // Changing between a normal property or an accessor property
2513     if (descriptor.isDataDescriptor() != current.isDataDescriptor()) {
2514         if (!current.configurable()) {
2515             if (throwException)
2516                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change access mechanism for an unconfigurable property.")));
2517             return false;
2518         }
2519         methodTable()->deleteProperty(this, exec, propertyName);
2520         return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
2521     }
2522
2523     // Changing the value and attributes of an existing property
2524     if (descriptor.isDataDescriptor()) {
2525         if (!current.configurable()) {
2526             if (!current.writable() && descriptor.writable()) {
2527                 if (throwException)
2528                     throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change writable attribute of unconfigurable property.")));
2529                 return false;
2530             }
2531             if (!current.writable()) {
2532                 if (descriptor.value() && !sameValue(exec, current.value(), descriptor.value())) {
2533                     if (throwException)
2534                         throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change value of a readonly property.")));
2535                     return false;
2536                 }
2537             }
2538         }
2539         if (current.attributesEqual(descriptor) && !descriptor.value())
2540             return true;
2541         methodTable()->deleteProperty(this, exec, propertyName);
2542         return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
2543     }
2544
2545     // Changing the accessor functions of an existing accessor property
2546     ASSERT(descriptor.isAccessorDescriptor());
2547     if (!current.configurable()) {
2548         if (descriptor.setterPresent() && !(current.setterPresent() && JSValue::strictEqual(exec, current.setter(), descriptor.setter()))) {
2549             if (throwException)
2550                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change the setter of an unconfigurable property.")));
2551             return false;
2552         }
2553         if (descriptor.getterPresent() && !(current.getterPresent() && JSValue::strictEqual(exec, current.getter(), descriptor.getter()))) {
2554             if (throwException)
2555                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change the getter of an unconfigurable property.")));
2556             return false;
2557         }
2558     }
2559     JSValue accessor = getDirect(exec->vm(), propertyName);
2560     if (!accessor)
2561         return false;
2562     GetterSetter* getterSetter = asGetterSetter(accessor);
2563     if (descriptor.setterPresent())
2564         getterSetter->setSetter(exec->vm(), descriptor.setterObject());
2565     if (descriptor.getterPresent())
2566         getterSetter->setGetter(exec->vm(), descriptor.getterObject());
2567     if (current.attributesEqual(descriptor))
2568         return true;
2569     methodTable()->deleteProperty(this, exec, propertyName);
2570     unsigned attrs = descriptor.attributesOverridingCurrent(current);
2571     putDirectAccessor(exec, propertyName, getterSetter, attrs | Accessor);
2572     return true;
2573 }
2574
2575 bool JSObject::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, const PropertyDescriptor& descriptor, bool throwException)
2576 {
2577     // If it's an array index, then use the indexed property storage.
2578     unsigned index = propertyName.asIndex();
2579     if (index != PropertyName::NotAnIndex) {
2580         // c. Let succeeded be the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing P, Desc, and false as arguments.
2581         // d. Reject if succeeded is false.
2582         // e. If index >= oldLen
2583         // e.i. Set oldLenDesc.[[Value]] to index + 1.
2584         // e.ii. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", oldLenDesc, and false as arguments. This call will always return true.
2585         // f. Return true.
2586         return object->defineOwnIndexedProperty(exec, index, descriptor, throwException);
2587     }
2588
2589     return object->defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException);
2590 }
2591
2592 bool JSObject::getOwnPropertySlotSlow(ExecState* exec, PropertyName propertyName, PropertySlot& slot)
2593 {
2594     unsigned i = propertyName.asIndex();
2595     if (i != PropertyName::NotAnIndex)
2596         return getOwnPropertySlotByIndex(this, exec, i, slot);
2597     return false;
2598 }
2599
2600 JSObject* throwTypeError(ExecState* exec, const String& message)
2601 {
2602     return throwError(exec, createTypeError(exec, message));
2603 }
2604
2605 } // namespace JSC