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